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