Algoritma-algoritma PRAM

[Ke Urutan Pembelajaran Paralel]

PRAM adalah singkatan dari Parallel Random Access Machine

Ini adalah salah satu model komputasi paralel. Model ini sangat sederhana, PRAM belum memperhitungkan jumlah prosesor dan komunikasi antar prosesor. Karena kompleksitas komunikasi ini tidak menjadi isu/masalah akhirnya para desainer/pembuat algoritma PRAM dapat lebih fokus pada paralalisme komputasinya.

Model Komputasi Serial

 

Model Komputasi Paralel PRAM

x

Algoritma-algoritma PRAM

  1. Parallel Reduction
  2. Prefix Sums
  3. List Ranking
  4. Preorder Tree Traversal
  5. Merging Two Sorted Lists
  6. Graph Coloring

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 \(\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.