Artikel ini dapat digunakan, disalin, dan disebarluaskan. Cukup cantumkan sumber asli. Jika isinya mengandung kebenaran, semoga memberi kebaikan bagi kita yang memanfaatkannya. Jika ada yang salah, mohon kiranya penulis dimaafkan. Dan sangat baik, jika kesalahan tersebut dapat diberitahukan kepada penulis.
Yanmarshus, 27 Desember 2005, yan[at]daunsalam[dot]net

Perkalian Matriks Menggunakan Algoritma Cannon

Tulisan ini memaparkan tantang perkalian matriks, menggunakan algoritma Cannon. Kemudian dibuat sebuah kalkulasi sederhana. Kalkulasi waktu proses dilihat untuk 1 prosesor, dan dengan n2 prosesor secara paralel. Bagian penghitungan speedup yang diperoleh dengan prosesor paralel belum dilengkapi.

Perkalian matriks A x B = C yang berukuran 3 x 3 dengan menggunakan algoritma Cannon digambarkan pada diagram berikut ini.

C11C12C13
C21C22C23
C31C32C33
  A11A12A13
 A21A22A23 
A31A32A33  
       
  B13
 B12B23
B11B22B33
B21B32 
B31  
  Diagram 1


Matriks A dan matriks B yang akan dikalikan, terlebih dahulu di-skew seperti pada diagram 1. Pada proses perkaliannya, matriks B digeser ke arah atas, dan matriks A digeser ke arah kiri, sehingga kedua matriks melewati matriks C. Nilai awal dari semua elemen matriks C adalah 0. Langkah demi langkah yang terjadi, dapat dilihat seperti pada tabel berikut ini. Setiap hasil perkalian yang terjadi pada satu elemen matriks C, langsung ditambahkan ke nilai elemen matriks C tersebut.

 Langkah 1Langkah 2Langkah 3Langkah 4Langkah 5Langkah 6Langkah 7
C11    A11 x B11A12 x B21A13 x B31
C12   A11 x B12A12 x B22A13 x B32 
C13  A11 x B13A12 x B23A13 x B33  
C21   A21 x B11A22 x B21A23 x B31 
C22  A21 x B12A22 x B22A23 x B32  
C23 A21 x B13A22 x B23A23 x B33   
C31  A31 x B11A32 x B21A33 x B31  
C32 A31 x B12A32 x B22A33 x B32   
C33A31 x B13A32 x B23A33 x B33    


Dengan menggunakan asumsi-asumsi berikut ini, akan dilihat berapa banyak proses yang terjadi pada perkalian matriks tersebut :

Banyaknya proses yang terjadi bila menggunakan 1 prosesor

Kita lihat terlebih dahulu, jika perkalian ini dilakukan oleh 1 buah prosesor. Dengan menggunakan satu buah prosesor, proses komunikasi antar prosesor tidak ada, jadi yang dihitung hanyalah proses perkalian dan penjumlahan. Banyaknya perkalian untuk satu elemen matriks C yang dihasilkan adalah n kali perkalian. Banyaknya penjumlahan dihitung sebanyak n kali penjumlahan juga, bukan (n - 1). Karena ada sebanyak n2 elemen matriks C yang akan dihasilkan, maka banyaknya proses yang terjadi adalah (2n)n2 pada satu prosesor tersebut.

Perkalian matriks dilakukan paralel dengan n2 prosesor

Masing-masing prosesor melakukan proses untuk satu buah elemen matriks C. Kita lihat proses untuk mendapatkan hasil satu elemen matriks C yang terjadi di elemen matriks C33

Terima data A31
Terima data B13
Perkalian (A31 x B13)
Jumlahkan ke C33
Kirim data A31 ke C32
Kirim data B13 ke C23
Terima data A32
Terima data B23
Perkalian (A32 x B23)
Jumlahkan ke C33
Kirim data A32 ke C32
Kirim data B23 ke C23
Terima data A33
Terima data B33
Perkalian (A33 x B33)
Jumlahkan ke C33
Kirim data A33 ke C32
Kirim data B33 ke C23

Terlihat di sini, muncul proses komunikasi berupa menerima dan mengirim data yang cukup banyak. Proses komputasi yang dilakukan adalah 3 kali perkalian, dan 3 kali penjumlahan = 6 kali proses. Proses komunikasi yang dilakukan adalah 6 kali menerima data, dan 6 kali mengirim data = 12 kali proses. Sementara terlihat proses komunikasi lebih banyak dilakukan dibanding proses komputasi, yaitu proses komunikasi 2 kali dari proses komputasi. Ini merupakan kerugian yang cukup besar ketika dilakukan perkalian secara paralel.

Jika kita ambil asumsi bahwa waktu yang diperlukan untuk masing-masing proses adalah sama sebesar t, bisa dilihat perbandingan waktu yang diperlukan antara proses paralel dengan n2 prosesor dibanding dengan 1 prosesor.

Untuk keperluan melihat pengaruh proses komunikasi, hasil tersebut ditulis ulang sebagai berikut :

  (3n - 2) = L
  6t = 4tcomm + 2tcomp   [comm = komunikasi , comp = komputasi]
  (4tcomm)L + (2tcomp)L

Dengan keadaan satu proses komunikasi membutuhkan waktu yang sama dengan satu proses komputasi, sebesar 66% waktu yang diperlukan untuk perkalian matriks ini adalah untuk komunikasi.