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 n² 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.

C11 C12 C13 C21 C22 C23 C31 C32 C33		A11 A12 A13   A21 A22 A23   A31 A32 A33
B13   B12 B23 B11 B22 B33 B21 B32   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.

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

• Matriks A, B, dan C adalah matriks n x n
• Untuk proses paralel, digunakan sebanyak n² prosesor
• Perkalian dihitung sebagai satu buah proses
• Penjumlahan dihitung sebagai satu buah proses
• Menerima satu data dihitung sebagai satu buah proses
• Mengirim satu data dihitung sebagai satu buah proses
• Proses yang terjadi dibatasi hanya pada penjumlahan, perkalian, menerima data, mengirim data

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 n² elemen matriks C yang akan dihasilkan, maka banyaknya proses yang terjadi adalah (2n)n² pada satu prosesor tersebut.

Perkalian matriks dilakukan paralel dengan n² 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 C₃₃

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 n² prosesor dibanding dengan 1 prosesor.

• Untuk 1 prosesor waktu yang diperlukan adalah : 2n³t
  
  
• Untuk proses paralel dengan n² prosesor dengan meniadakan waktu komunikasi, waktu yang diperlukan adalah :
  Langkah yang diperlukan sebanyak : 3n - 2
  Untuk satu langkah dilakukan : 2 buah proses [1 perkalian dan 1 penjumlahan]
  Jadi waktu yang diperlukan adalah : (3n - 2) x 2t
  
  
• Untuk proses paralel dengan n² prosesor, dengan memperhitungkan waktu komunikasi, waktu yang diperlukan adalah :
  Langkah yang diperlukan sebanyak : 3n - 2
  Untuk satu langkah dilakukan : 6 buah proses
  Jadi waktu yang diperlukan adalah : (3n - 2) x 6t

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.