Algoritma dan Pemrograman Parallel by Dr. Asep Juarna
VI. OPERASI MATRIKS (Part 2) Oleh Dr. Asep Juarna
2.
Perkalian Matriks dengan Vektor
Sebagai ilustrasi awal, diberikan matriks A dan vektor U masing-masing dengan ukuran 3 × 4 dan 4 × 1; hasilnya adalah vektor V yang tentu saja berukuran 3 × 1, seperti terlihat di bawah ini: a11 A × U = V ⇔ a 21 a31
2.1.
a12
a13
a 22 a32
a 23 a33
u a14 1 a11u1 + a12 u 2 + a13 u 3 + a14 u 4 v1 u a 24 × 2 = a 21u1 + a 22 u 2 + a 23 u 3 + a 24 u 4 = v 2 u a34 3 a31u1 + a32 u 2 + a33 u 3 + a34 u 4 v3 u 4
Algoritma Sekuensial
Ilustrasi di atas menunjukkan bahwa perkalian matriks dengan vektor hanya mungkin jika banyaknya kolom matriks sama dengan dimensi vektor, dan hasilnya adalah sebuah vektor berdimensi sama dengan jumlah baris vektor dengan komponen sebagai berikut: 4
vi = ∑ a i , j × u j , untuk i = 1, 2, dan 3 j =1
Secara umum, untuk matriks A berukuran m × n dan vektor U berukuran n × 1 komponen vektor V di atas adalah: n
vi = ∑ a i , j × u j , untuk i = 1, 2, ... m j =1
Dengan demikian, algoritma sekuensial perkalian matriks dengan vektor adalah sebagai berikut: procedure seq_mult-mat-vec (A, U, V) (1) for i = 1 to m do (2) vi ← 0 (3) for j = 1 to n do (4) vi ← vi + ai,j × uj end for end for Sebanyak n iterasi pada loop (3) diulang sebanyak m kali pada loop (1) sehingga running time procedure seq_mult-mat-vec adalah t(n) = n × m. Jika m < n maka running time ini adalah O(n2); sesuai dengan definisi big-Oh, ini artinya berapapun m, selama m < n, perkalian n × m tidak akan melebihi n2.
2.2.
Algoritma Paralel
2.2.1. Linear Array Banyaknya prosesor pada linear array (LA) adalah sebanyak jumlah baris matriks yang diperkalikan, yaitu n. Prosesor-prosesor tersebut disusun vertikal sedemikain rupa sehingga prosesor ke-n berada paling bawah dan prosesor pertama paling atas. Vektor diinputkan dari bawah sedangkan baris-baris matriks diinputkan dari samping seperti
vi-5
Algoritma dan Pemrograman Parallel by Dr. Asep Juarna
terlihat pada Gambar 6.3. Setiap prosesor mempunyai 3 register a, u, dan v. Ketika prosesor Pi menerima 2 input ai,j dan uj, prosesor tersebut melakukan hal-hal berikut: (i) menyimpan ai,j dan uj masing-masing di register a dan u (ii) mengalikan isi register a dengan isi register u (iii) menambahkan hasil (ii) ke isi register v (iv) mengirim uj ke Pi-1 (kecuali i = 1, artinya prosesor P1 tidak mengirim uj karena P1 adalah prosesor terakhir yang menerima uj). Perhatikan pada konfigurasi di atas bahwa baris ke i matriks A terlambat satu langkah daripada baris ke i + 1 untuk 1 ≤ i ≤ m -1, sebagaimana ditunjukkan oleh adanya h1, h2 dan h3; hal ini sengaja dilakukan untuk memastikan ai,j diperkalikan dengan uj pada waktu yang tepat. Procedure paralel perkalian matriks 3 × 4 dengan vektor 4 × 1 menggunakan 3 prosesor larik linier (linear array processors) diilustrasikan dengan gambar berikut: P1
v1
h1
P2
v2
h3
P3
v3
h2
a11 a12 a13 a21 a22
a23
a31 a32 a33
a34
a14
a24
u1 u2 u3 u4 Gambar 6.3. Ilustrasi prosedur paralel perkalian matriks 3 × 4 dengan vektor kolom berdimensi 4 menggunakan array linear berprosesor 3
Algoritma sekuensial perkalian matriks dengan vektor, dengan demikian, adalah sebagai berikut: procedure par_LA-mult-mat-vec (A, U, V) for i = 1 to m do in parallel vi ← 0 while prosesor Pi menerima dua input a dan u do (1) vi ← vi + (a + u) (2) if i > 1 then prosesor Pi mengirim u ke prosesor Pi-1 end if end while end for Elemen matriks a1,n adalah elemen terakhir yang diterima prosesor, yaitu prosesor P1. Dari posisi awalnya, elemen a1,n ini membutuhkan m + n - 1 langkah untuk sampai ke prosesor P1. Dengan demikian, jika m < n maka running time procedure par_LA-multmat-vec adalah t(n) = O(n). Banyaknya prosesor yang digunakan procedure par_LA-
vi-6
Algoritma dan Pemrograman Parallel by Dr. Asep Juarna
mult-mat-vec ini adalah p(n) = n, dengan demikian cost procedure ini adalah c(n) = p(n) × t(n) = O(n2); nilai ini adalah cost optimal. Latihan: Diberikan matriks A berukuran m × n dan vektor U berukuran n × 1 sebagai input procedure par_LA-mult-mat-vec menggunakan n prosesor. Tentukan selisih langkah antara selesainya pekerjaan prosesor Pn dengan selesainya pekerjaan prosesor P1! Bagaimana dengan selisih langkah antara selesainya pekerjaan prosesor Pn dengan selesainya pekerjaan prosesor Pk, 1 < k < n? 2.2.2. Tree Prosedur paralel perkalian matriks dengan vektor akan diimplementasikan dengan menggunakan tree of processor, tepatnya complette binary tree of processor dengan d level (bernomor 0 s.d. d - 1) dan jumlah prosesor N = 2d - 1. Matriks yang dikalikan berukuran m × n sedangkan dimensi vektornya adalah n di mana n = 2d - 1. Untuk m = 3 dan d = 3 (yaitu n = 23-1 = 22 = 4) situasinya terlihat pada gambar berikut: v1 v2 v3
level 0
P7
P5
P1
u1
a11 a21 a31
P6
P2
u2
a12 a22 a32
P3
u3
a13 a23 a33
level 1
P4
u4
level 2
a14 a24 a34
Gambar 6.4. Ilustrasi prosedur paralel perkalian matriks 3 × 4 dengan vektor kolom berdimensi 4 menggunakan tree berprosesor 17 atau dengan level d = 3.
Pada Gambar 6.4 di atas, P1 s.d. P4, yang merupakan prosesor-prosesor daun (leaf), bertugas mengalikan sebuah elemen matriks dengan sebuah elemen vektor dan mengirimkan hasilnya ke prosesor induknya (parent). P5 dan P6, yang merupakan prosesor-prosesor dalam (inner), bertugas menjumlahkan bilangan yang diperoleh dari kedua anaknya (children) dan mengirimkan hasilnya ke induknya. P7, yang merupakan akar (root) bertugas menjumlahkan bilangan yang diperoleh dari kedua anaknya dan mengeluarkannya sebagai output. Perhatikan bahwa ketika P1 s.d. P4 mengalikan sebuah elemen matriks dengan sebuah elemen vektor dan mengirimkan hasilnya ke prosesor induknya, pada saat yang sama P5 dan P6 melakukan penjumlahan dua bilangan, jika ada, yang sebelumnya diterima dari kedua anaknya mengirimkan hasilnya P1, dan pada saat yang sama pula P7 menjumlahan dan mengirimkan hasilnya vi-7
Algoritma dan Pemrograman Parallel by Dr. Asep Juarna
sebagai output prosedur. Dengan demikian, algoritma prosedur paralel perkalian matriks menggunakan tree tersebut adalah sebagai berikut: procedure par_Tree-mult-mat-vec (A, U, V) do step 1 dan 2 in parallel (1) for i = 1 to n do in parallel for j = 1 to m do in parallel (1.1) hitung ui × ai,j (1.2) kirim hasilnya ke induk (parent) end for end for (2) for i = n + 1 to 2n - 1 do in parallel while Pi menerima 2 input do (2.1) hitung jumlah kedua input (2.2) if i < 2n - 1 then kirim hasilnya ke induk else kirim hasilnya sebagai output algoritma end if end while end for Diperlukan log n langkah setelah baris pertama matriks A diterima prosesor-prosesor daun (leaf processors) untuk dikeluarkan prosesor akar (root processor) sebagai output v1. Karena matriks A mempunya m baris, diperlukan m - 1 langkah berikutnya sehingga semua baris matriks A dikeluarkan prosesor akar sebagai output. Dengan demikian running time procedure par_Tree-mult-mat-vec adalah t(n) = (m - 1) + log n. Jumlah prosesor yang digunakan adalah p(n) = N = 2d - 1 = 2 × 2d-1 - 1 = 2n - 1. Jika m < n maka t(n) = O(n), p(n) = O(n), dan c(n) = t(n) × p(n) = O(n2), dan ini adalah cost optimal.
3. Perkalian Matriks dengan Matriks Diberikan dua matriks A berukuran m × n dan matriks B berukuran n × k. Perkalian matriks A dengan B adalah matriks C berukuran m × k di mana: n
c i , j = ∑ a i , s × bs , j s =1
Contoh: Diberikan matriks A berukuran 3 × 2 (yaitu 3 baris 2 kolom) dengan matriks B berukuran 2 × 3 (yaitu 2 baris dan 3 kolom) beserta matriks C = A × B sebagai berikut: 1 2 (1 × 7) + ( 2 × 10) (1 × 8) + ( 2 × 11) (1 × 9) + ( 2 × 12) 27 30 33 7 8 9 A = 3 4 , B = 10 11 12 ⇒ C = (3 × 7) + ( 4 × 10) (3 × 8) + ( 4 × 11) (3 × 9) + ( 4 × 12) = 61 68 75 5 6 (5 × 7) + (6 × 10) (5 × 8) + (6 × 11) (5 × 9) + (6 × 12) 95 106 117 Perhatikan bahwa, misalnya, c2,3 = 75 = (3 × 9) + (4 × 12) = (a2,1 × b1,3) + (a2,2 × b2,3) = 2
∑ a2,s × bs,3 , c3,1 = 95 = (5 × 7) + (6 × 10) = (a3,1 × b1,1) + (a3,2 × b2,1) = s =1
dan seterusnya.
vi-8
2
∑a s =1
3, s
× bs ,1 ,
Algoritma dan Pemrograman Parallel by Dr. Asep Juarna
3.1.
Algoritma Sekuensial
Berdasarkan contoh di atas, algoritma sekuensial perkalian matriks A berukuran m × n dengan matriks B berukuran n × k (hasilnya adalah matriks C berukuran m × n) adalah sebagai berikut: procedure seq_mult-mat (A, B, C) {Input: A(m × n), B(n × k) Output: C(m × k)} (1) for i = 1 to m do (2) for j = 1 to k do (3) ci,j ← 0 (4) for s = 1 to n do ci,j ← ci,j + (ai,s × bs,j) (5) (6) end for (7) end for (8) end for
Running time procedure seq_mult-mat di atas adalah n × k × m. Jika m ≤ n dan k ≤ n maka running time procedure ini adalah O(n3).
3.2.
Algoritma Paralel
3.2.1. Mesh Diberikan matriks A berukuran m × n dengan matriks B berukuran n × k; algoritma paralel perkalian matriks berikut adalah pada struktur prosesor mesh dengan m × k prosesor. Sebagai ilustrasi awal, diberikan matriks A berukuran 4 × 5 dengan matriks B berukuran 5 × 3 menggunakan mesh prosesor 4 × 3.
b12 b22 b32 b42 b52
b11 b21 b31 b41 b51
a41
a11
a12
a13
a14
a21
a22
a23
a24
a25
a31
a32
a33
a34 a35
a42
a43
a44
a45
a15
b13 b23 b33 b43 b53
P(1,1)
P(1,2)
P(1,3)
P(2,1)
P(2,2)
P(2,3)
P(3,1)
P(3,2)
P(3,3)
P(4,1)
P(4,2)
P(4,3)
Gambar 6.5. Ilustrasi prosedur paralel perkalian matriks A berukuran 4 × 5 dengan matriks B berukuran 5 × 3 menggunakan mesh berprosesor 4 × 3.
vi-9
Algoritma dan Pemrograman Parallel by Dr. Asep Juarna
Seperti pada perkalian matriks dengan vektor menggunakan linear array, pada perkalian matriks dengan matriks menggunakan mesh terjadi proses keterlambatan yang memang disengaja agar perkalian ai,s dengan bs,j, yang merupakan prosedur utama n
perkalian matriks sesuasi formula ci , j = ∑ ai , s × bs , j , terjadi pada waktu yang tepat. s =1
Kali ini keterlambatan tersebut terjadi saat penginputan baris-baris matriks A dan kolom-kolom matriks B. Baris ke-m matriks A dan kolom ke-k matriks B adalah baris dan kolom terakhir yang diinput ke mesh, sedangkan dua elemen terakhir yang diinput adalah am,1 dan b1,k. Pada contoh di atas, seperti terlihat pada Gambar 6.5, baris ke-4 matriks A, kolom ke-3 matriks B adalah baris dan kolom yang terakhir diinput ke mesh, sedangkan dua elemen terakhir yang diinput adalah a4,1 dan b1,3. Dengan demikian, algoritma paralel perkalian matriks A berukuran m × n dengan matriks B berukuran n × k (hasilnya adalah matriks C berukuran m × n) menggunakan mesh adalah sebagai berikut: procedure par_Mesh_mult-mat (A, B, C) {Input: A(m × n), B(n × k) Output: C(m × k)} for i = 1 to m do in parallel for j = 1 to k do in parallel (1) ci,j ← 0 (2) while P(i,j) menerima dua input a dan b (a) ci,j ← ci,j + (a × b) (b) if i < m then kirim b ke (i+1,j) end if (c) if j < k then kirim a ke (i,j+1) end if end while end for end for Elemen-elemen a1,n dan bn,1 membutuhkan (m + k + n - 2) langkah sejak awal komputasi (yaitu sejak elemen-elemen am,1 dan b1,k masuk mesh) sampai a1,n dan bn,1 mencapai prosesor yang tepat yaitu P(m,k). Dengan asumsi m ≤ n dan k ≤ n, running time procedure par_Mesh_mult-mat adalah t(n) = O(n), p(n) = O(n2), sehingga c(n) = t(n) × p(n) = O(n3), dan ini adalah cost optimal jika mengacu kepada algoritma sekuensial dengan running time t(n) = O(n3). 3.2.2. CRCW SM-SIMD Algoritma paralel perkalian matriks dengan matriks menggunakan CRCW SM-SIMD adalah implementasi paralelisasi langsung dari algoritma sekuensial problem yang sama. Jumlah prosesor yang digunakan adalah m × k × n. Setiap prosesor tersebut mempunyai 3 indeks, sehingga notasinya adalah P(i,j,s). CRCW mempunya masalah n
write conflict. Prosedur utama perkalian matriks adalah formula ci , j = ∑ ai , s × bs , j . s =1
Mengacu kepada formula ini, write conflict pada CRCW diselesaikan dengan prosedur berikut: Jika terdapat lebih dari satu prosesor (ditandai dengan indeks s yang berbeda) mencoba menuliskan hasil ke ci,j maka yang akhirnya dituliskan adalah jumlah semua
vi-10
Algoritma dan Pemrograman Parallel by Dr. Asep Juarna
hasil yang mau dituliskan semua prosesor tersebut. Dengan fakta dan pemikiran tersebut maka algoritma paralel perkalian matriks A berukuran m × n dengan matriks B berukuran n × k (hasilnya adalah matriks C berukuran m × n) adalah sebagai berikut: procedure par_Mesh_mult-mat (A, B, C) {Input: A(m × n), B(n × k) Output: C(m × k)} for i = 1 to m do in parallel for j = 1 to k do in parallel for s = 1 to n do (1) ci,j ← 0 (2) ci,j ← ai,s × bs,j end for end for end for
Running time procedure par_Mesh_mult-mat di atas adalah t(n) = O(1). Dengan asumsi m ≤ n dan k ≤ n, jumlah prosesor yang digunakan adalah t(n) = O(n3), sehingga c(n) = t(n) × p(n) = O(n3), dan ini adalah cost optimal jika mengacu kepada algoritma sekuensial dengan running time t(n) = O(n3). Latihan: Pada procedure seq_mult-mat, inisialisasi ci,j ← 0 dilakukan sebelum loop for s = 1 to n do dan ci,j ← ci,j + (ai,s × bs,j). Pada procedure par_Mesh_mult-mat inisialisasi ci,j ← 0 dilakukan sesudah loop for s = 1 to n do dan ci,j ← ci,j + (ai,s × bs,j). Jelaskan bahwa bahwa procedure par_Mesh_mult-mat tersebut menyelesaikan masalah write conflict CRCW.
vi-11
