Perkalian Matrik pada model SIMD Mesh 2-D

 

Berikut adalah algoritma perkalian matrik paralel yang disampaikan oleh Quinn

Algoritma MATRIX MULTIPLICATION (2-D MESH SIMD)

 

Global n (dimensi dari matrik), k

Local   a, b, c

begin

{stagger matrices}

for k $latex \leftarrow $ 1 to n – 1 do

for all P(i, j) where 1 \( \leqslant \) i, j \( \leqslant \) n do

if i > k then

a \(\Leftarrow\) east(a)

endif

if j > k then

b \(\Leftarrow\) south(b)

endif

endfor

endfor

{ Compute dot products }

for all P(i, j) where 1 \( \leqslant \) i, j \( \leqslant \) n do

c \(\leftarrow\) a x b

endfor

for k \(\leftarrow\) 1 to n – 1 do

for all P(i, j) where 1 \( \leqslant \) i, j \( \leqslant \) n do

a \(\Leftarrow\) east(a)

b \(\Leftarrow\) south(b)

c \(\leftarrow\) c + a x b

endfor

endfor

end

 

Berikut adalah alogritma Perkalian Matrik Paralel pada Komputer Mesh dengan koneksi memutar (wraparound) menurut Pranay Chaudhury

Komputer Mesh Connected dengan Koneksi Berputar (wraparound connection) di gambaran sebagai berikut :

 

(Gambar 6.2 : (a) Penempatan Data Awal; (b) pengaturan data sebelum proses perkalian matrik dimulai

Algorithm MESH_MATRIX_MULTI1

Input : Elemen A[i,j] dan B[i,j] dari matrik A dan B yang akan diperkalikan tersedia di dalam prosesor-prosesor pij , 1 \( \leqslant \) i, j \( \leqslant \) n-1

Ouput : Elemen C[i,j] yang akan tersimpan di dalam prosesor pij , 0 \( \leqslant \) i, j \( \leqslant \) n-1

for i = 1 to n – 1 dopar

for s = 1 to i do

     for j = 0 to n – 1 dopar

A [i,j] := A[i,(j+1) mod n]

odpar

   od

odpar

for j = 1 to n – 1 dopar

for t = 1 to j do

     for i = 0 to n – 1 dopar

B [i,j] := B[(i+1) mod n, j ]

odpar

   od

odpar

for j = 1 to n – 1 dopar

     for i = 0 to n – 1 dopar

C [i,j] := A[i,j] x B[i,j]

odpar

odpar

for k = 1 to n – 1 do

for i = 0 to n – 1 dopar

     for j = 0 to n – 1 dopar

A [i,j] := A[i,(j+1) mod n];

B [i,j] := B[(i+1) mod n, j ];

C [i,j] := C [i,j] + A[i,j] x B[i,j]

odpar

   odpar

odpar

Leave a Reply

Your email address will not be published.

Captcha Captcha Reload