Algoritma Parallel Perkalian Matrix: Cannon Vs Fox

Wayan Sriyasa/G651080154 Departemen Ilmu Komputer, FMIPA, IPB

Algoritma Parallel Perkalian Matrix: CANNON vs FOX Latar Belakang Perkalian dua matrix yang masing-masing berukuran n x n dari matrix persegi A dan B untuk menghasilkan matrix C (C = AxB) secara parallel dengan menggunakan prosesor sebanyak m, dimana m ≤ n pada dasarnya mirip dengan perkalian matrix dengan metode konvensional (algoritma sekuensial). Dengan mengasumsikan bahwa: 1. n sel matrix adalah hasil pangkat 2. 2. Jumlah processor yang digunakan adalah m = n^3 sehingga n > m 3. processor di disusun dalam array tiga dimensi. Processor Pi,j,k masing-masing dengan index (i,j,k) 4. digunakan 3 dimensi array C[1..n,1..n,1..n] dalam shared memory sebagai tempat kerja 5. Hasil matrix akan disimpan dalam lokasi C[i,j,n], dimana 1≤ i,j ≤ n Algoritma sekuensial-nya adalah Algoritma 1 1. 2. 3. 4. 5. 6. 7. 8. 9. 10.

procedure MAT_MULT (A, B, C) begin for i := 0 to n - 1 do for j := 0 to n - 1 do begin C[i, j] := 0; for k := 0 to n - 1 do C[i, j] := C[i, j] + A[i, k] x B[k, j]; endfor; end MAT_MULT

Sekilas dapat diketahui bahwa waktu terburuk yang dibutuhkan oleh algoritma diatas adalah sebanyak n3 atau θ(n3). Proses parallelisasi algoritma diatas dapat dilakukan dengan menggunakan pendekatan block matrix operations, dimana matrix asal yang relatif berukuran besar dipecah menjadi blok kecil, misal matrix dengan ukuran nxn dapat dibagi menjadi beberapa matrix kecil dengan ukuran qxq dimana Ai,j (0 ≤ i, j < q)). Sedemikian sehingga setiap block akan berukuran (n/q) x (n/q). Dengan demikian algoritma diatas dapat dimodifikasi menjadi: Algoritma 2 1. 2. 3. 4. 5. 6. 7. 8. 9. 10.

procedure BLOCK_MAT_MULT (A, B, C) begin for i := 0 to q - 1 do for j := 0 to q - 1 do begin Initialize all elements of Ci,j to zero; for k := 0 to q - 1 do Ci,j := Ci,j + Ai,k x Bk,j; endfor; end BLOCK_MAT_MULT

Pada algoritma 2, terlihat pada baris 8 dilakukan operasi penjumlahan dan perkalian sekaligus. Berbeda dengan algoritma 1, pada algoritma 2 terjadi perkalian matrix sebanyak q3 yang melibatkan matrix (n/q) x (n/q) dan memerlukan sebanyak (n/q)3 1

Wayan Sriyasa/G651080154 Departemen Ilmu Komputer, FMIPA, IPB

penjumlahan serta perkalian. Proses ini dapat kita bagi kedalam p prosesor secara parallel dengan memilih q  p dan melakukan komputasi blok kecil Ci,j ke setiap ptosesor. Teknik Partisi Data - Checkerboard Ada tiga teknik dekomposisi data yang dapat digunakan dalam implementasi perkalian matrix ini, antara lain: dekomposisi berdasarkan baris, kolom atau dengan menggunakan teknik blok checkerboard. Pada tulisan ini, teknik dekomposisi data yang akan digunakan adalah teknik checkerboard. Teknik checkerboard, matrix dibagi menjadi blok 2 dimensi yang disesuaikan dengan grid-nya. Dengan mengasumsikan p merupakan sejumlah prosesor yang membentuk grid dengan sebanyak r baris dan c kolom. Setiap proses bertanggung jawab atas komputasi blok matrix yang setidaknya mengandung sebanyak [m/r] baris dan [n/c] kolom (ukuran matrix = m x n). Dengan mengasumsikan matrix berukuran nxn A dan B dipecah sebanyak p blok    n   x  . Blok ini Ai,j dan Bi,j dengan 0  k  p dengan ukuran tiap bloknya  n   p  p   dipetakan kedalam jaring proses berukuran P0,0 hingga P

p 1 , p 1

p x

p , tiap proses diberi nama mulai dari

. Proses Pi,j biasanya menyimpan nilai Ai,j dan Bi,j menghitung hasil

perkalian blok Ci,j. Menghitung sub-matrix Ci,j membutuhkan sub-matrix Ai,k dan Bk,j ( 0  i , j  p ). Untuk memperoleh nilai setiap blok, dilakukan all-to-all broadcast blok matrix A disetiap baris dan all-to-all broadcast blok matrix B disetiap kolom. Setelah nilai Pi,j diperoleh Ai ,0 , Ai ,1,..., Ai , p 1 dan B 0, j , B1, j ,..., B p1 kemudian dilakukan perkalian dan penjumlahan sub-matrix ini (algoritma 2, baris 7 & 8). Algoritma Cannon Algoritma cannon merupakan salah satu algoritma yang dapat digunakan untuk melakukan perkalian matrix dengan pemakaian memori yang efisien. Berikut merupakan detail dari algoritma Cannon: 1. inisialisasi prosesor Pi,j dengan elemen ai,j dan bi,j (0≤ i < n; 0 ≤ j < n). 2. elemen dipindahkan dari posisi awal sebagai berikut: matrix A beris ke-i diputar satu putaran ke kiri dan matrix B kolom ke-j diputar satu putaran keatas sehingga akan dihasilkan matrix baru dengan elemen ai,j+i dan bi+j,j . j i

A Pi,j

Gambar 1. perputaran elemen matrix A dan B.

B

3. setiap prosesor Pi,j melakukan perkalian masing-masing elemennya. 4. setelah proses 3 selesai, kemudian putaran matrix kembali dilakukan, dimana elemen baris ke-i matrix A akan diputar satu putaran ke kiri dan elemen kolom ke-1 matrix B akan diputar satu putaran ke atas. 5. kemudian setiap prosesor Pi,j kembali melakukan perkalian elemen yang baru hasil putaran pada langkah 4 dan hasilnya disimpan pada variabel jumlah total perkalian ini. 2

Wayan Sriyasa/G651080154 Departemen Ilmu Komputer, FMIPA, IPB

6. langkah 4 dan 5 dilakukan secara berulang sampai dengan seluruh elemen baris dan kolom diputar (n-1 putaran baris dan kolom). Berikut desain foster untuk algoritma tersebut:  Partitioning & Agglomeration, algoritma ini menggunakan teknik checkerboard untuk melakukan partisi data kedalam blok matrix yang lebih kecil. Misalkan matrix A dan B dibagi menjadi masing-masing p blok matrix. Masing-masing proses dari P0,0 hingga P p 1, p 1 akan memiliki blok Ai,j dan Bi,j. Agglomerasi dilakukan dengan orientasi baris, dimana setiap prosesor akan melakukan komputasi terhadap seluruh elemen C, dan ini memerlukan akses terhadap seluruh elemen B (gambar 2a). Sesuai dengan teknik checkerboard diatas, setiap prosesor akan melakukan    n   x  , untuk melakukan komputasi blok matrix C dengan ukuran  n   p  p   komputasi elemen ini prosesor memerlukan referensi dari elemen matrix B sebanyak

 n    baris dan p  

 n    kolom (gambar 2b.). p  

x

=

A

B

C

2a

x A

= B

C 2b

Gambar 1. Perbandingan banyaknya elemen A dan B yang perlu dihitung oleh setiap prosesor. a) Perkalian berdasarkan baris, setiap prosesor akan menghitung sebanyak n/p baris dari C dan perlu untuk mengakses sebanyak n/p baris A dan seluruh elemen B. b) Pada algoritma cannon, setiap prosesor akan melakukan



 



 x n  blok matrix C. Proses komputasi sebanyak  n p   p  



ini akan mengakses sebanyak  n



3

  baris A dan .B p 

Wayan Sriyasa/G651080154 Departemen Ilmu Komputer, FMIPA, IPB 3 Setiap blok/proses akan melakukan komputasi sebanyak  2n



 setiap blok akan mengakses sebanyak 2n n 

2n dan komunikasi yang terjadi adalah

2n

 , dimana p 

  elemen. Rasio antara komputasi p 

3

p

2



n

.

p

p  Communication, diperlukan untuk melakukan perputaran elemen matrix A dan B. Setiap proses pada baris ke-i matrix A akan memindahkan isi blok tersebut ke kiri sebanyak 1 putaran, demikian juga pada kolom matrix B akan memindahkan isi blok-nya sebanyak satu putaran ke atas (ilustrasi gambar 3).

Gambar 3. Proses komunikasi yang terjadi pada algoritma Cannon dengan mengunakan sebanyak 16 prosesor/blok.

Pada ilustrasi diatas terlihat proses komunikasi terjadi ketika algoritma melakukan inisialisasi elemen matrix dengan melakukan pergeseran elemen baris matrix A kekiri dan kolom matrix B keatas. Dan setiap blok melakukan perkalian elemen-ya, dan kembali diputar dengan arah yang sama sampai dengan baris ke n-1 dan kolom ke n-1 juga.

4

Wayan Sriyasa/G651080154 Departemen Ilmu Komputer, FMIPA, IPB

Proses putaran elemen ini melibatkan sebanyak

B(i  j ) mod

p, j

Ai ,( j  i ) mod

p

dan

. Berikut cuplikan kode program untuk melakukan putaran elemen

matrix sekaligus menggantikan nilai blok dengan elemen yang baru tersebut: /*********************************************************/ /*putar blok & isikan nilai perhitungan*/ MPI_Cart_shift(GRID_COMM,1,-1,&source,&dest); MPI_Sendrecv_replace(TA,S2,MPI_INT,dest,0,source, 0,GRID_COMM,&status); MPI_Cart_shift(GRID_COMM,0,-1,&source,&dest); MPI_Sendrecv_replace(TB,S2,MPI_INT,dest,0,source, 0,GRID_COMM,&status); /*********************************************************/

Cuplikan kode berikut merupakan topologi virtual yang digunakan pada algoritma cannon ini: /*********************************************************/ /*untuk buat topologi*/ M=(int)sqrt(nproc); S=N/M; /*dimensi blok*/ S2=S*S; /*dimensi blok*/ dims[0]=dims[1]=M; /*dimensi topologi*/ periods[0]=periods[1]=1; //membuat comm baru MPI_Cart_create(MPI_COMM_WORLD,2,dims,periods,0,&GRID_COMM); MPI_Comm_rank(GRID_COMM,&grid_rank); MPI_Cart_coords(GRID_COMM,grid_rank,2,coords); myid=grid_rank; source=coords[0]; dest=coords[1]; /*********************************************************/

Detail lengkap kode program dapat dilihat pada lampiran 1. Algoritma Fox Mirip dengan algoritma Cannon, algoritma Fox juga melakukan rotasi elemen, tetapi rotasi elemen yang terjadi melibatkan broadcast elemen baris matrix A dan perputaran kolom matrix B pada setiap tahap komputasinya. Berikut merupakan langkah yang dilakukan pada algoritma Fox: 1. dilakukan perkalian elemen matrix ai,j x bi,j, ci,j  ai,j x bi,j 2. tahap berikutnya (tahap ke k, 1 ≤ k < n) dilakukan: ci,j  ci,j + ai,k x bk,j dimana k = (i+k)mod n, n = merupakan ukuran matrix tersebut. Pada tahap 1, ci,j dihitung sebagai hasil perkalian dari ai,j dan bi,j, dan pada tahap ke-k, ci,j dihitung sebagai hasil perkalian antara ai,k dengan bk,j. Algoritma sekuensial diatas dapat diparallelkan kedalam sejumlah prosesor (p
Ukuran setiap blok matrix adalah q x q dimana q 

p dan n 

n . Pada setiap langkah q

ke-k>0, proses pi,j (0 ≤ i, j ≤ q) akan menghitung sub-blok ci,j sebagai hasil perkalian dari sub-blok ai,k yang di-broadcast oleh proses pi,k (pada baris yang sama) dan bi,k dari pi,j proses dari atas kebawah dari pk ,j.

5

Wayan Sriyasa/G651080154 Departemen Ilmu Komputer, FMIPA, IPB

Berikut algoritma parallel Fox: set C = 0 for (stage = 0 ∶ o

p − 1) do

Tiap baris prosesor i, mem-broadcast sub-blok Ai ,( j i ) mod

p

ke prosesor lain pada

baris yang sama, setiap prosesor menyimpan subblok broadcast dalam sebuah array T o

Kalikan sub-matriks temporer T pada tiap prosesor dengan sub-blok B sekarang dan tambahkan hasilnya ke C

o

Setiap prosesor mengirimkan sub-blok B sekarang ke prosesor di atasnya dan menerima sub-blok dari prosesor di bawahnya dan dijadikan sebagai sub-blok sekarang yang baru. Wrap around dari atas ke bawah.

end Berikut desain Foster untuk algoritma tersebut:  Partitioning & Agglomeration, algoritma ini menggunakan teknik checkerboard untuk melakukan partisi data kedalam blok matrix yang lebih kecil. Misalkan matrix A dan B dibagi menjadi masing-masing p blok matrix. Masing-masing proses dari P0,0 hingga P p 1, p 1 akan memiliki blok Ai,j dan Bi,j. Agglomerasi dilakukan dengan orientasi baris, dimana setiap prosesor akan melakukan komputasi terhadap seluruh elemen C, dan ini memerlukan akses terhadap seluruh elemen B (gambar 2a). Sesuai dengan teknik checkerboard diatas, setiap prosesor akan melakukan    n   x  , untuk melakukan komputasi blok matrix C dengan ukuran  n   p  p   komputasi elemen ini prosesor memerlukan referensi dari elemen matrix B sebanyak

 n    baris dan p  

 n    kolom. Gambar 4, merupakan model pembagian blok p  

matrix yang akan ditangani oleh setiap prosesor.

Gambar 4. Pembagian matrix kedalam blok.

 Communication, proses komunikasi terjadi sesuai dengan ilustrasi pada gambar 5, komunikasi yang terjadi adalah komunikasi kolektif. Algoritma Fox memiliki 3 langkah proses yang dikenal dengan broadcast, multiply dan roll yang terjadi disetiap iterasinya. Komunikasi kolektif yang terjadi adalah ketika terjadi broadcast sepanjang baris dan roll/pergeseran pada kolom. Rowbroadcast adalah 6

Wayan Sriyasa/G651080154 Departemen Ilmu Komputer, FMIPA, IPB

broadcast pada sub-grup khusus dari prosesor. Roll dilakukan sebagai varian dari operasi MPI_Sendrecv dengan kondisi batas melingkar (wrapped). Berikut merupakan ilustrasi proses komunikasi yang terjadi pada algoritma Fox:

5a.

Gambar 5. langlah-langkah algoritma Fox: 5a. langkah ke-1, row broadcast, inisialisasi, perkalian elemen matrix A dan B menghasilkan matrix C 5b. langkah ke-2, n=1, dilakukan perputaran elemen matrix b ke atas dan diikuti dengan broadcast elemen matrix A ke arah kanan. 5c. langkah berikutnya, mengalikan sub-blok dan menjumlahkannya kedalam matrix C.

7

Wayan Sriyasa/G651080154 Departemen Ilmu Komputer, FMIPA, IPB

5c.

Gambar 5. Proses komunikasi yang terjadi pada algoritma Fox.

Implementasi dan hasil Running Implementasi kedua algoritma ini dilakukan dengan menggunakan bahasa C dan modul MPI dari Microsoft ClusterPack dengan IDE Visual Studio Express. Detail lengkap kode program kami sertakan pada lampiran. Pada bagian ini akan ditampilkan fungsi utama-nya saja dari kode program yang telah dibuat. Algoritma Cannon Input dan output untuk program ini adalah berupa file text yang berisi data. File yang dibaca terdiri dari file matrix A dan file matrix B (contoh file terlampir pada softcopy). Berikut adalah hasil run dari program yang dibuat:

Gambar 6. Contoh tampilan layar hasil eksekusi program Cannon. Output tampilan layar dari program ini adalah berupa informasi prosesor yang bekerja dan waktu yang butuhkan untuk melakukan komputasi. Sebagai input digunakan matrix berukuran 100 x 100 dan disimpan didalam file text. Hasil tidak ditampilkan pada console.

8

Wayan Sriyasa/G651080154 Departemen Ilmu Komputer, FMIPA, IPB

Algoritma Fox Berikut merupakan contoh tampilan layar dari program Fox yang dibut.

Gambar 7. Contoh tampilan layar hasil eksekusi program Fox.

Hubungan Ukuran Matrix v s Waktu Komputasi waktu eksekusi 6 5 ms

4 3 2 1 0 0

20

40

60

80

ordo matrix

Gambar 8. Grafik hubungan antara waktu eksekusi dengan ukuran matrix.

9

Wayan Sriyasa/G651080154 Departemen Ilmu Komputer, FMIPA, IPB

Hubungan Waktu Eksekusi vs Jumlah Prosesor jumlah prosesor 0.7 0.6

ms

0.5 0.4 0.3 0.2 0.1 0 0

5

10

15

20

25

30

#prosesor

Gambar 9. Hubungan jumlah prosesor dengan waktu eksekusi

Performa Dan Skalabilitas Algoritma Beberapa parameter yang dapat digunakan untuk mengukur kinerja sebuah algoritma antara lain speed up, efisiensi dan isoefisiensi. Berikut merupakan analisa paremeter tersebut untuk kedua algoritma diatas. Algoritma Cannon Seperti terlihat pada gambar 3, terjadi perputaran baris dan kolom dimana, jarak maksimum yang ditempuh oleh satu blok shift adalah p  1 . Operasi untuk dua putaran tersebut memerlukan waktu total sebanyak 2 t s  t w n



2 memerlukan waktu sebesar t s  t w n

2 adalah 2 t s  t w n



p

2

 . Setiap langkah dari p proses p 

. Sehingga total waktu komunikasi yang diperlukan

 p. p 

Sedangkan untuk proses komputasinya sendiri memerlukan waktu sebagai berikut,    n   x . setiap proses akan melakukan sebanyak p perkalian dari sub-blok  n   p  p   Dengan mengasumsikan bahwa setiap proses perkalian dan penjumlahan menggunakan satu satuan waktu, maka total waktu yang diperlukan untuk setiap proses untuk 3 melakukan komputasi adalah sebesar n

p

. Dengan demikian total waktu parallel yang

dibutuhkan oleh algoritma cannon adalah:

n3 n2 Tp   2 p t s  2t w p p

10

.

Wayan Sriyasa/G651080154 Departemen Ilmu Komputer, FMIPA, IPB

o

Speed up untuk algoritma ini menjadi:

SN 

o

Efisiensinya adalah

E ff 

o

Ts n3  3 Tp n n2  2 pt s  2t w p p

Ts  pT p

n3  n3 n 2  p   2 pt s  2t w  p p  

Isoefisiensi, dengan memperhatikan waktu proses dari algoritma ini yaitu

 n3 n 2  p  2 p t s  2t w dan cost optimum untuk algoritma parallel ini adalah  p p   3

p=O(n2). Sehingga fungsi isoefisiensi untuk ts dan tw adalah 2 p 2 t s dan 8t w  p 3

3

2

,

dengan demikian isoefisiensi sebagai akibat adanya overhead komunikasi adalah

 p 

3

2

 Dengan melihat nilai pangkat dari fungsi isoefisiensi tersebut diketahui 

bahwa untuk mendapatkan efisiensi yang sama dengan ketika jumlah prosesor p maka ukuran masalah juga harus bertambah sebesar

p

x3

2

p

3

. Dengan kata lain, 2

apabila misalnya jumlah masalah semula adalah n3 dengan prosesor semula adalah 4 (22) kemudian ditingkatkan menjadi 16(24) maka jumlah masalah harus bertambah menjadi (2n)3. Algoritma Fox Berikut merupakan analisa kinerja algoritm Fox: ada tiga komponen waktu yang harus dihitung untuk menentukan waktu parallel yang diperlukan oleh algoritma Fox ini, antara lain: waktu untuk broadcast (tbroad): 2     log p  t s  n t w  t broad  log p  t s  t w n  n p  p p  

waktu untuk mengalikan matrix (tmul): 3

t mull

3     n   n p p p 

waktu untuk melakukan rolling (troll):

t roll  t s  n

p

 n

p

tw  ts  n

2

p

tw

sehingga total waktu parallel untuk satu iterasi adalah Tp = tbroad + tmul + troll 2 2  3   T p  log p  t s  n t w   n  t s  n t  p  p     p p    3 2 Tp  n  log 4 p  t s  n t w  p  p p 

11

Wayan Sriyasa/G651080154 Departemen Ilmu Komputer, FMIPA, IPB

Dengan demikian total waktu yang dibutuhkan untuk seluruh proses yaitu sebanyak

p

iterasi adalah

Tp  Tp  p 2  3  p  n  log 4 p  t s  n t w  p    p p 3 2  n  p log 4 p  t s  n t w  p p   3 2  n  log 4 pt s  n log 4 pt w p p

Tp 

o

Speed up, dengan demikian speed up algoritma ini dapat ditentukan sebagai berikut:

SN  o

n3 p

 log 4 p t s  n

2

p

log 4 pt w

Efisiensinya adalah

E ff 

o

Ts  Tp n3

Ts  pT p

n3 2  3 p n  log 4 pt s  n p 

 log 4 pt w  p 

Isoefisiensi, dengan memperhatikan waktu proses dari algoritma ini yaitu 2  3 p n  log 4 p ts  n p 

 log 4 pt w  dan cost optimum untuk algoritma parallel ini p 

adalah p=O(n2). Sehingga fungsi isoefisiensi untuk ts dan tw adalah

p

3

2

1

log(4 p) 2 t s dan n 2 p

1

2

1

log( 4 p) 2 t w , dengan demikian isoefisiensi sebagai akibat

adanya overhead komunikasi logaritmik dari fungsi broadcast adalah

 p 

3

2

log 3 (4 p )

1

2

  

Perbandingan Dengan melihat nilai speed up, effisiensi dan isoefisiensi diatas, dapat disimpulkan bahwa algoritma cannon memiliki kinerja yang lebih baik daripada algoritma Fox. Dimana algoritma cannon memiliki skalabilitas yang lebih baik daripada algoritma Fox (koefisien isoefisiensi Fox > isoefisiensi Cannon). Sebuah ekperimen yang dilakukan oleh Alqadi et.al (2008) menunjukkan bawah algoritma Cannon memang memiliki kinerja yang lebih baik daripada algoritm Fox (cuplikan tabel berikut)

12

Wayan Sriyasa/G651080154 Departemen Ilmu Komputer, FMIPA, IPB

Eksperimen tersebut menunjukkan bahwa faktor Speed up (SP) dan efisiensi (E) yang dihasilkan oleh algoritma Cannon lebih baik dari pada Fox. Ulasan lebih lengkap mengenai eksperimen ini dapat merujuk pada referensi terlampir. Kesimpulan Algoritma Cannon dan Fox merupakan algoritma perkalian matrix yang dapat diimplementasikan dengan menggunakan teknik virtual topologi. Kedua algoritma menggunakan beberapa tahapan untuk menghitung hasil perkalian dua buah matrix persegi. Pada algoritma Cannon, pendekatan yang digunakan dengan orientasi putaran blok matrix berdasarkan baris dan kolom, sedangkan algoritma Fox menggunakan pendekatan broadcast baris matrix A dan putaran keatas kolom matrix B. Algoritma ini memiliki kesamaan yaitu sangat efisien dalam pemakaian memori,tetapi jika dibandingkan dengan lebih detail algoritma Cannon memiliki efisiensi dan skalabilitas yang lebih daripada algoritma Fox.

Referensi Akpan, O.H. ____. Efficient Parallel Implementation of The Fox Algorithm. Computer Science Dept. Bowie State Univ. Alqadi, Z.A.A; Aqel,M; Emary, I.M.M.E. 2008. Performance Analysis and Evaluation of Parallel Matrix Multiplication Algorithms. World Applied Sciences Journal 5 (2): 211-214, 2008. IDOSI Publications Grama, A; Gupta, A; Karypis, George; dan Kumar, V. 2003. Introduction to Parallel Computing, Second Edition – Chapter 8. Dense Matrix Algorithms. Addison Wesley. USA Quinn, M.J. 2004. Parallel Programming in C with MPI and OpenMP. McGrawHill. USA. Wilkinson, B; Allen, M. 2005. Parallel Programming: Techniques and Applications Using Networked Workstations and Parallel Computers, 2nd edition. Prentice Hall. USA.

13

Wayan Sriyasa/G651080154 Departemen Ilmu Komputer, FMIPA, IPB

Lampiran 1. Source Code Algoritma Cannon #include #include #include #include

<mpi.h> <stdio.h> <math.h> <stdlib.h>

#define N 100 /* 512*/ void Print_Matrix(int x, int y, int myid,int S, int *M); int A[N][N],B[N][N],C[N][N]; int main(int argc, char **argv){ int myid, S, M, nproc,source,dest; int i,j,k,m,l,repeat,temp,S2; int namelen; char processor_name[MPI_MAX_PROCESSOR_NAME]; MPI_Status status; double t1, t2,t3,t4; int *T,*TA,*TB,*t,*TC; MPI_Comm GRID_COMM; int ndims,dims[2]; int periods[2],coords[2],grid_rank; MPI_Init(&argc, &argv); /* inisialisasi MPI */ MPI_Comm_rank(MPI_COMM_WORLD,&myid); MPI_Comm_size(MPI_COMM_WORLD,&nproc); /* #procesor */ MPI_Get_processor_name(processor_name,&namelen); printf("Process %d of %d on %s\n",myid, nproc, processor_name); if(myid==0) { /* baca data dari files: "A_file", "B_file"*/ if (readmat("A_file.txt", (int *) A,N) < 0) exit( 1 + printf("file problem\n") ); if (readmat("B_file.txt", (int *) B, N) < 0) exit( 1 + printf("file problem\n") ); /*catat waktu*/ t1=MPI_Wtime(); } /*untuk buat topologi*/ M=(int)sqrt(nproc); S=N/M; /*dimensi blok*/ S2=S*S; /*dimensi blok*/ dims[0]=dims[1]=M; /*dimensi topologi*/ periods[0]=periods[1]=1; MPI_Cart_create(MPI_COMM_WORLD,2,dims,periods,0,&GRID_COMM); MPI_Comm_rank(GRID_COMM,&grid_rank); MPI_Cart_coords(GRID_COMM,grid_rank,2,coords); myid=grid_rank; source=coords[0]; dest=coords[1]; /*siapin untuk wadah matrix input dan output*/ TA=(int *)malloc(sizeof(MPI_INT)*S2); TB=(int *)malloc(sizeof(MPI_INT)*S2); TC=(int *)malloc(sizeof(MPI_INT)*S2); for(i=0; i<S2; i++) TC[i]=0; /*mulai proses canon*/ if(myid==0) { T=(int *)malloc(sizeof(MPI_INT)*S2); t3=MPI_Wtime(); /*timing*/ for(k=0; k
14

Wayan Sriyasa/G651080154 Departemen Ilmu Komputer, FMIPA, IPB } } else{ t=T; for(i=coords[0]*S; i<(coords[0]+1)*S; i++) for(j=coords[1]*S; j<(coords[1]+1)*S; j++){ *t=A[i][j]; t++; } MPI_Send(T,S2,MPI_INT,k,0,GRID_COMM); } } for(k=0; k
15

Wayan Sriyasa/G651080154 Departemen Ilmu Komputer, FMIPA, IPB t2= MPI_Wtime(); printf("Total Time: %lf msecs \n",(t2 - t1) / 0.001); //printf("Transmit Time: %lf msecs \n",(t4 - t3) / 0.001); writemat("C_file_par", (int *) C, N); free(T); free(TA); free(TB); free(TC); } else { MPI_Recv(TA,S2,MPI_INT,0,0,GRID_COMM,&status); MPI_Recv(TB,S2,MPI_INT,0,1,GRID_COMM,&status); MPI_Cart_shift(GRID_COMM,1,-coords[0],&source,&dest); MPI_Sendrecv_replace(TA,S2,MPI_INT,dest,0,source,0,GRID_COMM,&status); MPI_Cart_shift(GRID_COMM,0,-coords[1],&source,&dest); MPI_Sendrecv_replace(TB,S2,MPI_INT,dest,0,source,0,GRID_COMM,&status); for(repeat=0; repeat
16

Wayan Sriyasa/G651080154 Departemen Ilmu Komputer, FMIPA, IPB printf("\n"); } }

Algoritma Fox #include #include #include #include

<stdio.h> <string.h> <math.h> <mpi.h>

typedef struct{ int p; //#prosesor int mypid; //procesor id int oldpid; //id prosesor yg lama int myrow; //jumlah baris int mycol; //jumlah kolom int q; //ukuran blok MPI_Comm comm; //communicator utk seluruh blok MPI_Comm r_comm;//communicator utk blok baris MPI_Comm c_comm;//communicator utk blok kolom }GRID_TOP_TYPE; /*fungsi yang dipakai*/ double **inMatrix(int i,int j,int n,double r); void Pmatrix(int n,double **A,double **B,double **C); void Tmatrix(int n,double **A,double **B,double **C); void MinMatrix(double **A,double **B,int n); void Mprint(int i,int j,int n,double **A); void create_grid(GRID_TOP_TYPE *grid); /*fungsi utama*/ main(int argc,char **argv){ int n1,step,k; int source,dest; int tag=22; double **A,**B,**C; double **localA,**localB,**localC,**temp_A; double t1,t2; MPI_Status status; GRID_TOP_TYPE *grid; /*start MPI*/ MPI_Init(&argc,&argv); /*buat blok*/ grid=(GRID_TOP_TYPE *)malloc(sizeof(GRID_TOP_TYPE)); create_grid(grid); printf("jum prosesor:%d, ukuran grid: %d\n",grid->p,grid->q); /*baca input ukuran matrix*/ if(grid->oldpid==0){ printf("Masukkan ukuran matrix yang mau dihitung:\n"); scanf("%d",&n1); } MPI_Bcast(&n1,1,MPI_INT,0,MPI_COMM_WORLD); /*bikin matrix input*/ A=inMatrix(grid->myrow,grid->mycol,n1,2.0); B=inMatrix(grid->myrow,grid->mycol,n1,1.0); C=inMatrix(0,0,n1,0); localA=inMatrix(0,0,n1,0); localB=inMatrix(grid->myrow,grid->mycol,n1,1); localC=inMatrix(0,0,n1,0); temp_A=inMatrix(0,0,n1,0); printf("Matrix A:\n"); Mprint(grid->myrow,grid->mycol,n1,A); printf("\n"); printf("Matrix B:\n"); Mprint(grid->myrow,grid->mycol,n1,B);

/*hitung address yang diperlukan untuk putaran shift*/ source=(grid->myrow+1)%grid->q; dest=(grid->myrow+grid->q-1)%grid->q; t1=MPI_Wtime(); for(step=0;stepq;step++){ k=(grid->myrow+step)%grid->q;

17

Wayan Sriyasa/G651080154 Departemen Ilmu Komputer, FMIPA, IPB /*inisialisasi blok localA dengan A*/ if(grid->mycol==k){ MinMatrix(localA,A,n1); MPI_Bcast(localA[0],n1*n1,MPI_DOUBLE,k,grid->r_comm); /*hitung C=localA*B dan localC=localC+C*/ Tmatrix(n1,localA,localB,C); Pmatrix(n1,C,localC,localC);} else { MPI_Bcast(temp_A[0],n1*n1,MPI_DOUBLE,k,grid->r_comm); Tmatrix(n1,localA,localB,C); Pmatrix(n1,C,localC,localC); } MPI_Sendrecv_replace(localB[0],n1*n1,MPI_DOUBLE,dest,tag,source,tag,grid>c_comm,&status); } t2=MPI_Wtime(); printf("\n"); printf("hasilnya:\n"); Mprint(grid->myrow,grid->mycol,n1,C); printf("\n"); printf("\n\nWaktu yang diperlukan %d processes = %lf msecs\n",grid->p,(t2-t1)/0.001); MPI_Finalize(); } /*fungsi untuk inisialisasi matrix*/ double **inMatrix(int i,int j,int n,double r){ int a,b; double **p; double *pp; //alokasi memori untuk matrix yang dibuat p=(double **)malloc(n*sizeof(double *)); pp=(double *)malloc(n*n*sizeof(double)); for(a=0;a
18

Wayan Sriyasa/G651080154 Departemen Ilmu Komputer, FMIPA, IPB if(b==n-1)printf("\n"); } } /*buat topologi grid*/ void create_grid(GRID_TOP_TYPE *grid){ int dim[2]; int period[2]; int coord[2]; int vary_coord[2]; /*buat topologi global*/ MPI_Comm_size(MPI_COMM_WORLD,&(grid->p)); MPI_Comm_rank(MPI_COMM_WORLD,&(grid->oldpid)); grid->q=(int)sqrt((double)grid->p); dim[0]=dim[1]=grid->q; period[0]=period[1]=1; MPI_Cart_create(MPI_COMM_WORLD,2,dim,period,1,&(grid->comm)); MPI_Comm_rank(grid->comm,&(grid->mypid)); MPI_Cart_coords(grid->comm,grid->mypid,2,coord); grid->myrow=coord[0]; grid->mycol=coord[1]; /*setting untuk communicator untuk baris dan kolom*/ vary_coord[0]=0;vary_coord[1]=1; MPI_Cart_sub(grid->comm,vary_coord,&(grid->r_comm)); vary_coord[0]=1;vary_coord[1]=0; MPI_Cart_sub(grid->comm,vary_coord,&(grid->c_comm)); }

19