Pengantar Komputasi Matrik

Komputasi Matrik telah menjadi dasar dalam berbagai komputasi sains. Salah satu komputasi matrik yang sangat penting adalah perkalian matrik. Beberapa bahasan komputasi matrik dalam kaitan dengan algoritma paralel akan kita bahas cukup banyak disini, diantaranya akan meliputi matrik transpos, perkalian matrik-vektor dan masalah konvolusi.

Algoritma perkalian matrik telah banyak digunakan diberbagai aplikasi sebagai salah satu komponen komputasinya, baik pada masalah numerik maupun non-numerik. Contoh non masalah non-numerik misalnya pada Teori Graph. Pada teori ini banyak menggunakan Perkalian Matrik Boolean.

Produk dari matrik A (p x q) dan matrik B (q x r) adalah matrik C (p x r) yang elemen-elemen nya didefinisikan sebagai berikut :

Untuk \( 0 \leq i \leq p-1 \) dan  \( 0 \leq j \leq r-1 \) dimana \( \vee \) berarti operasi exclusice-OR dan \( \wedge \) adalah operasi AND bitwise.

Jika A dan B adalah matrik Boolean, maka matrik produk C juga akan berupa boolean matrik

Dalam komputasi serial, batas bawah dari kompleksitas perkalian matrik dengan dua matrik n x n diketahui sebesar Ω(n2), karena ada n2 elemen yang terlibat dalam menghasilkan matrik perkalian ini dan diperlukan waktu selama O(n2).

Dalam algoritma perkalian serial baik matrik pada umumnya maupun matrik boolean, akan membutuhkan O(n3) jika semua matrik yang terlibat berukuran n x n

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

Perkalian Matrik pada Model PRAM

Berikut adalah algoritma perkalian dua buah matrik yang mempunyai ukuran n x n pada model SIMD shared memory dan kemudian kita akan menganalisa pada batasan-batasan akses memory yang berbeda-beda.

Walaupun untuk penyederhanaan, disini dibahas menggunakan matrik yang berukuran n x n , tetapi kita bisa mengenralisir hal ini dengan mengasumsikan ukuran matrik A, B, dan C sebagai p x n, n x q dan p x q. Hal ini masih akan valid selama \(p \leq n \) dan  \(q \leq n \)

Algorithm PRAM_MATRIX_MULT

Input : dua buah matrik A dan B

Ouput : sebuah matrik C = A x B

for i = 0 to n – 1 dopar

for j = 0 to n – 1 dopar

C[i,j] := 0

for k = 0 to n – 1 do

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

od

odpar

odpar

 

Analisa Kompleksitas

Jika kita asumsikan model komputasi yang digunakan adalah EREW PRAM, maka pembacaan matrik A dan matrik B secara bersamaan dapat dilakukan dengan menggunakan buah prosesor dan dalam waktu O(log n) menggunakan algoritma PARALLEL_BCAST (bab 5.3.2 Chaudhuri)

Ada 2 (dua) pernyataan di dalam for-loops bersarang pada algoritma PRAM_MATRIX_MULT. Yang pertama adalah menginisalisasi semua elemen dari Matrik C menjadi 0 (nol) dan yang lainnya menghitung elemen-elemen di C menggunakan produk kumulatif. Sebuah produk kumulatif adalah operasi perkalian-tambah dalam bentuk c + a x b. Inisialisasi (pemberian nilai awal) dari C membutuhkan waktu O(1) dengan menggunakan n2 buah prosessor. Perkalian kumulatif dapat dilakukan secara mudah, dalam paralel, dengan pertama kali menghitung semua produk dalam bentuk A[i,k] x B[k,j] untuk k = 0, 1, . . ., n – 1 dalam waktu O(1) menggunakan n buah prosessor.

 

 

 

 

 

 

 

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 n2prosesor.

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 membutuhkandlangkah 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 :

matrix0007

Asumsi bahwa matrik yang akan diperkalikan berukuran n x n dan banyaknya prosesor di Mesh adalah n2 . pijadalah prosesor pada baris keidan kolom kej, dan terhubung dengan prosesor p(i-1)j,pi(j+1),p(i+1)j, danpi(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 menggunakanmodulo n.

Algoritma MESH_MATRIX_MULT1

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

Ouput : Elemen C[i,j] dari produk matrix tersedia di prosesor pij ,\( 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 perulanganforparalel pertamamembutuhkan tidak lebih dari O(n) waktu.

Kita bisa melakukan pergeseran baris (row-shifting) dalam n/2langkahparalel 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 n2 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(n3 ) yang seperti algoritma straightforward serial matrix multiplication.

 

 

 

 

 

 

3. Perkalian Matrik pada Mesh tanpaKoneksi 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, pij mengirim A[i,k] ke pi(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 pij,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 (pij 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 pi(j+1)

Fi

Od

Odpar

Odpar