Matrix Multiplication'in Paralel Programlama Analizi

Bu makale iceriginde Suleyman Demirel Universitesi – Bilgisayar Muhendisligi bolumu’nun Paralel Programlama dersi icin gelistirilen .Matrix Multiplication'in seri ve paralel programlama ile analiz sonuclarini C programlama dili ile birlikte kullanilarak yapilmis bir ornegini paylasiyor olacagim.

Seri Programlama Kod Ve Analizleri

Seri Programlama kodlari ve ornek ekran ciktisi su sekildedir.

        #include <stdlib.h> #include <stdio.h> #include <time.h> #include <float.h> #include <iostream> #include <conio.h> int main() { int **A_Matrix, **B_Matrix, **C_Matrix; int A_Matrix_Satir, A_Matrix_Sutun, B_Matrix_Satir, B_Matrix_Sutun; clock_t HesaplamayaBasla, HesaplamayiBitir; double SureFarki; int i,j,k; printf("\nHesaplanacak Matrix'lerin Boyutunu Giriniz : ... ... "); scanf("%d%d",&A_Matrix_Satir,&A_Matrix_Sutun); B_Matrix_Satir = A_Matrix_Satir; B_Matrix_Sutun = A_Matrix_Sutun; printf("\nA Matrix Degerleriniz : %d X %d ", A_Matrix_Satir, A_Matrix_Sutun); printf("\nB Matrix Degerleriniz : %d X %d ", B_Matrix_Satir, B_Matrix_Sutun); A_Matrix=(int **) malloc(10*A_Matrix_Satir); B_Matrix=(int **) malloc(10*B_Matrix_Satir); C_Matrix=(int **) malloc(10*A_Matrix_Satir); for( i=0;i<A_Matrix_Sutun; i++) { A_Matrix

=(int *) malloc(10*A_Matrix_Sutun); } for( i=0;i<B_Matrix_Sutun; i++) { B_Matrix

=(int *) malloc(10*B_Matrix_Sutun); } for( i=0;i< B_Matrix_Sutun; i++) { C_Matrix

=(int *) malloc(10*B_Matrix_Sutun); } printf("\nHesaplama Islemine Basladi : "); HesaplamayaBasla = clock(); printf("%f saniye surdu. \n", (double) HesaplamayaBasla ); for(i=0;i<A_Matrix_Satir; i++) { for(j=0;j<A_Matrix_Sutun; j++) { A_Matrix

= i+j; } } for(i=0;i<B_Matrix_Satir; i++) { for(j=0;j<B_Matrix_Sutun; j++) { B_Matrix

= i*j; } } for(i=0;i<A_Matrix_Satir; i++) { for(j=0;j<B_Matrix_Sutun; j++) { C_Matrix

=0; } } for(i=0;i<A_Matrix_Satir; i++) { for(j=0;j<A_Matrix_Sutun; j++) { for(k=0;k<B_Matrix_Sutun; k++) { C_Matrix

= C_Matrix

+ A_Matrix

* B_Matrix

; } } } printf ("Hesaplama Islemi Sona Erdi : "); HesaplamayiBitir = clock(); printf("%f saniye surdu. \n",(double) HesaplamayiBitir ); SureFarki = ((double) (HesaplamayiBitir - HesaplamayaBasla)) / CLOCKS_PER_SEC ; printf("Hesaplanan Sure Farki : %f  saniyedir.", SureFarki); getche(); return 0; free(A_Matrix); free(B_Matrix); free(C_Matrix); }

Paralel Programlama 1.Deney Kod Ve Analizleri

Paralel Programlama kodlari ve ornek ekran ciktilari su sekildedir.

                  #include <stdlib.h> #include <stdio.h> #include <iostream> #include <conio.h> #include <omp.h> int main() { int **A_Matrix, **B_Matrix, **C_Matrix; int A_Matrix_Satir, A_Matrix_Sutun, B_Matrix_Satir, B_Matrix_Sutun; int i,j,k; int ToplamThreadSayisi, ThreadID, chunk =10; double HesaplamayaBasla, HesaplamayiBitir; double SureFarki; printf("\nHesaplanacak Matrix'lerin Boyutunu Giriniz : ... ... "); scanf("%d %d", &A_Matrix_Satir, &A_Matrix_Sutun); B_Matrix_Satir = A_Matrix_Satir; B_Matrix_Sutun = A_Matrix_Sutun; printf("\nA Matrix Degerleriniz : %d X %d ", A_Matrix_Satir, A_Matrix_Sutun); printf("\nB Matrix Degerleriniz : %d X %d ", B_Matrix_Satir, B_Matrix_Sutun); A_Matrix=(int **) malloc(10*A_Matrix_Satir); B_Matrix=(int **) malloc(10*B_Matrix_Satir); C_Matrix=(int **) malloc(10*A_Matrix_Satir); for( i=0;i<A_Matrix_Sutun; i++) { A_Matrix

=(int *) malloc(10*A_Matrix_Sutun); } for( i=0;i<B_Matrix_Sutun; i++) { B_Matrix

=(int *) malloc(10*B_Matrix_Sutun); } for( i=0;i< B_Matrix_Sutun; i++) { C_Matrix

=(int *) malloc(10*B_Matrix_Sutun); } printf("\nHesaplama Islemine Basladi : "); HesaplamayaBasla = omp_get_wtime(); printf("%f saniye surdu. \n",  HesaplamayaBasla );

    #pragma omp parallel shared(A_Matrix,B_Matrix,C_Matrix,ToplamThreadSayisi,chunk) private(ThreadID,i,j,k)

{ ThreadID = omp_get_thread_num(); if (ThreadID == 0) { ToplamThreadSayisi = omp_get_num_threads(); printf("Kullandiginiz Toplam Thread Sayisi : %d \n",ToplamThreadSayisi); }

       #pragma omp for schedule (static, chunk)

for(i=0;i<A_Matrix_Satir; i++) { for(j=0;j<A_Matrix_Sutun; j++) { A_Matrix

= i+j; } }

        #pragma omp for schedule (static, chunk)

for(i=0;i<B_Matrix_Satir; i++) { for(j=0;j<B_Matrix_Sutun; j++) { B_Matrix

= i*j; } }

     #pragma omp for schedule (static, chunk)

for(i=0;i<A_Matrix_Satir; i++) { for(j=0;j<B_Matrix_Sutun; j++) { C_Matrix

=0; } } printf("%d .Thread Kosuyor. \n",ThreadID);

    #pragma omp for schedule (static, chunk)

for(i=0;i<A_Matrix_Satir; i++) { for(j=0;j<A_Matrix_Sutun; j++) { for(k=0;k<B_Matrix_Sutun; k++) { C_Matrix

= C_Matrix

+ A_Matrix

* B_Matrix

; } } } } printf ("Hesaplama Islemi Sona Erdi : "); HesaplamayiBitir = omp_get_wtime(); printf("%f saniye surdu. \n", HesaplamayiBitir ); SureFarki = (HesaplamayiBitir - HesaplamayaBasla); printf("Hesaplanan Sure Farki : %f  saniyedir.", SureFarki); getche(); return 0; free(A_Matrix); free(B_Matrix); free(C_Matrix); } Paralel programla gelen surelerin her bir thread'e gore sahip oldugu matrix boyutlarinin tablolari iki sekilde asagida gosterilmektedir. ilkinde tek bir bir matrix degerine sahip olan tum thread'lerde ki gelen gecen toplam sureler bulunmaktadir. Sonraki tablolarda ise herhangi secilmis thread sayisinin her bir matrix boyutuna gore gelen toplam surelerinin degerleri bulunmaktadir.

                                  Seri kodla yazmis oldugum programi paralel kodla tekrar derledigim zaman makinamin 4 cekirdeginde olusan bir grafik normal bir sekilde artan bir egri olusturmustur. Fakat cekirdek yani thread sayisini birer birer azalttigimda aldigim sonuclara baktigimda her defasinda bu surelerin daha asagilara indigi fakat yine bunun matrix boyutunu arttirdikca yine grafikteki egrinin artan bir sekilde ilerledigini gozlemleyebiliyoruz. Thread sayisinin her degisimde thread basina dusen is yukusu sayisida ayni sekilde degisecektir.

Paralel Programlama 2.Deney Kod Ve Analizleri

Paralel kodun icerisinde uc for kullanildigini 1.Deney basliginda gorebilirsiniz. Bu baslik altinda ise kullanilan uc for'luk dongulerden ilki olani #pragma omp for kodunun disina aliyoruz. Aslinda buradaki amac for dongusunu boldugumuzde acaba islemlerimizin toplam suresi artacak mi yoksa azalacak mi? Ilk bakista mantik olarak bunun artabilecegini dusunmem cok normal. Cunku sonucta ilk kodu seri kod olarak goren bir master thread'in oldugunu dusundugumuzde ikinci ve ucuncu for'larin birinci for'a ne kadar bagimli olarak calisacaklar olsalarda yine her defasinda thread sayisi birken coka, cokken de bire seklinde degisimlere ugruyor. Is yuku uzerlerinde calisirken islerin surekli bir suru birlestirme ve bolme islemi yapmak gibi dusunebiliriz. Peki bir onceki deneyde almis oldugum sonuclari bir de asagidaki gibi kodlari degistirdigimde alacagim sonuclarin analiz tablolarini ve grafiklarini inceleyelecek olursak;

(Not; Ilk deneyde en fazla 3000X3000 aldigim matrix boyutunu bu deneyde 2000X2000 seklinde aldim.)

                                    Thread sayisi degistikce hizda ilk baslarda az olan fakat matrix boyutu arttikca gozle gorulebilen bir fark oldugunu asagidaki grafik sonuclarindan da anlayabiliyoruz.

Seri/Paralel Programlama'da Hiz Karsilastirilmasi (Paralel'de 4 Thread)

Seri kodla yazmis oldugum bir uygulamayi paralel bir kodla yeniden duzenleyip derledikten sonra hiz konusunda ne kadar fazla artabilecegini gostermek icin mazx 4thred ile calisarak bir analiz yapacak olursak;

                    Degisimi grafik uzerinde inceleyecek olursak; Matrix boyutlarinin dusuk oldugu durumlarda hem seri hem de paralel kodlarin birbirlerine yakin bir surede calistiklarini grafigimizde gorunuyor. Fakat matrix boyutu gittikce arttiyor ve bu artisla dogru orantili olarakta yine aralarinda yine gozle gorulebilecek bir fark olusmus oluyor. Peki bu degisimi sayilara dokecek olursak nasil ifade edebiliriz? Matrix boyutu dusuk oldugu siralarda seri kod ile paralel kod arasindaki sure farkinin saniye bakiminda gozlemlendiginde yaklasik 0.4 ile 1.5 arasinda degistigini goruyoruz. Matrix boyutu yukseldikce seri kod ile paralel kod arasindaki sure farkinin saniye bakimindan gozlemlendiginde ise artisin yaklasik 2.1'den 2.9 lara kadar ciktigini gozlemleyebiliriz.