Perkalian Matrik pada Mesh

Asumsikan bahwa kita akan mengalikan dua matrik A dan B yang berukuran n x n pada komputer SIMD Mesh Connected dengan n² prosesor.

1. Batas bawah untuk Perkalian Matrik pada Mesh

Asumsi :

(A1) Setiap anggota matrik yang akan diperkalikan hanya diwakilkan hanya satu kali pada model komputasi

(A2) Tidak ada 2 (dua) anggota matrik yang sama disimpan pada prosesor yang sama

Teorema :

Berdasarkan asumsi A1 dan A2 di atas, dan tanpa menggunakan sembarang fasilitas broadcast, perkalian dari dua matrik A dan B yang berukuran n x n yang akan menghasilkan C yang juga berukuran n x n, paling tidak akan membutuhkan d langkah pergerakan data, dimana \( \beta (2d) \geq n^2 \)

2. Perkalian Matrik pada Mesh dengan Koneksi Berkeliling (Wraparound)

Komputer Mesh Connected dengan Koneksi Berkeliling bisa digambarkan seperti gambar berikut :

Asumsi bahwa matrik yang akan diperkalikan berukuran n x n dan banyaknya prosesor di Mesh adalah n² . p_ij adalah prosesor pada baris ke i dan kolom ke j, dan terhubung dengan prosesor p_(i-1)j , p_i(j+1), p_(i+1)j, dan p_i(j-1), jika ada. Sebagai tambahan, diasumsikan bahwa pada bagian batas-batas tepian dari Mesh saling terhubung. Keterhubungan keliling ini menjadikan semua proses penjumlahan dan pengurangan menggunakan modulo n.

Algoritma MESH_MATRIX_MULT1

Input : anggota-2  A[i,j] dan B{i,j] dari matrik A dan B tersedia di prosesor p_ij, \( 0 \leq i, j \leq n – 1 \)

Ouput : Elemen C[i,j] dari produk matrix tersedia di prosesor p_ij , \( 0 \leq i, j \leq 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

forj = 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 i = 0 to n – 1 dopar

for j = 0 to n – 1 dopar

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

odpar

odpar

for k = 0 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] := A[i,j] x B[i,j]

odpar

odpar

od

Analisa Kompleksitas

 

 

 

 

Tampak jelas bahwai perulangan for paralel pertama membutuhkan tidak lebih dari O(n) waktu.

Kita bisa melakukan pergeseran baris (row-shifting) dalam n/2 langkah paralel dengan cara menggeser elemen tersebut ke kanan ketika angka perpindahan lebih besar dari n/2.

Begitupun, paralel kedua statemen for perpindahan kolomnya membutuhkan O(n) waktu. Kita belum memulai operasi aritmatika. Operasi aritmatika ditampilkan pada perulangan for yang ketiga dan keempat. Perulangan for yang ketiga secara nyata membutuhkan O(1) waktu paralel. Terakhir, perulangan for yang keempat membutuhkan O(n) waktu sejak badan dari perulangan for ini terdiri dari dua perulangan for paralel bersarang bisa diimplementasikan pada O(1) waktu. Karena itu, waktu keseluruhan kompleksitas algoritma MESH_MATRIX_MULTI adalah O(n) pada sebuah mesh dengan n² prosesor. Dengan jelas, algoritma ini optimal untuk melihat ?(n) untuk bound yang lebih rendah pada waktu komputasi untuk perkalian matrik pada mesh dua dimensi. Nilai dari algoritma adalah O(n³ ) yang seperti algoritma straightforward serial matrix multiplication.

 

 

 

 

 

 

…

3. Perkalian Matrik pada Mesh tanpa Koneksi Berkeliling (Wraparound) 

 

 

 

 

Pada bagian ini, kita membahas algoritma perkalian matrik pada mesh dua dimensi yang terhubung dengan komputer tanpa koneksi wraparound. Pada model ini prosesor dihubungkan denga keempat yang terdekat kecuali prosesor yang ada di perbatasan yang juga terhubung dengan keduanya (Kasus : permasalahan disudut- sudut prosesor), atau ketiganya (perbatasan disetiap empat sudut prosesor).

Kita mengasumsikan bahwa algoritma dari elemen A dan B dikirim ke batas prosesor di dalam baris dan kolom pertama dari permasalahan masing- masing. Elemen- elemen dari matriks dikirimkan melalui baris 1 dari A setelah baris i-1, untuk 1 ? j ? n-1. Begitupun kolom j dari B dilaksanakan setelah kolom j-1, untuk 1 ? j ? n-1. ini menjelaskan dari gambar 6.3a untuk kasus- kasus matriks 2 x 2. tiap prosesor pij diatas menerima A[i,k] dan B[k,j, untuk 0 ? k ? n-1, melipatgandakan dan menambahkan hasil ke bagian hasil C[i,j] (C[i,j] menginisialkan ke 0 dari semula). Akhirnya, p_ij mengirim A[i,k] ke p_i(j+1) jika 1 < n-1 dan B[k,j] ke p_(i+1)j jika i < n-1. proses ini terus berulang hingga produk matriks C = A x B terpenuhi sebagai output. Algoritma paralel berdasarkan ide diatas seperti dibawah ini.

Algoritma MESH_MATRIX_MULT2

 

 

 

 

Input: elemen- elemen A[i,j] dan B[i,j,i] = 0,1,…,n-1 dari A dan B dikirimkan ke prosesor dari kolom paling kiri (j=0) dan baris paling atas (i-0), masing- masing.

Ouput: matriks C = A x B disimpan jadi elemen- elemen C[i,j] tersedia diprosesor p_ij,i,j = 0,1,…,n-1

For i = 0 to n-1 dopar

For j = 0 to n-1 dopar

C[i,j] := 0

Odpar

Odpar

For i = 0 to n-1

For j = 0 to n-1 dopar

While (p_ij receives A[i,k] and B[k,j], k ? (0,1,…,n-1) do

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

If i<n-1

Then send B[k,j] to p_(i+1)j

Fi

If j < n-1

Then send A[i,k] to p_i(j+1)

Fi

Od

Odpar

Odpar