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 \(\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. Required fields are marked *

Captcha Captcha Reload