Parallel Random Access Machine

Algoritma PRAM (Parallel Random Access Machine) memiliki dua fase yaitu :

  1. mengaktifkan sejumlah prosesor
  2. prosesor yang sudah diaktifkan (pada fase 1), melaksanakan komputasi secara parallel

pro

Gambar, Untuk mengubah 1 prosesor yang aktif ke p prosesor dibutuhkan |log p|Langkah

Jumlah prosesor yang aktif merupakan lipat-2 (2n) dari prosesor tunggal atau alogaritma dari basis 2.

Instruksi meta untuk mengaktifkan prosesor yang digunakan (dalam fase 1) :

spawn (<nama prosesor>)

Instruksi meta untuk melakukan komputasi secara paralel (dalam fase 2) :

for all <processor list>

do

<statement list>

endfor

Pohon biner menjadi paradigma yang penting dalam komputasi paralel. Pada beberapa algoritma ada yang menggunakan aliran data top-down (akar –daun).

Contoh :

  • broadcast : akar mengalirkan (mengirimkan) data yang sama ke setiap daunnya
  • divide-and-conquer : pohon menggambarkan adanya perulangan sub divisi suatu masalah ke sub masalah yang lebih kecil.

Parallel Reduction (Reduksi paralel)

Reduksi secara paralel dapat digambarkan dengan pohon biner. Sekelompok n nilai ditambahkan dalam |log p| langkah penambahan paralel.

tree

Implementasi algoritma penjumlahan, setiap node dari pohon merupakan elemen dalam array

treadpada gambar diatas merupakan salah satu teknik kerja parallel computing yaitu parallel reduction. Untuk cara perhitungan tersebut dibagi menjadi 4 step .

pada step 1 setiap thread akan dipasangkan dengan thread sampingnya dan dijumlahkan. Setelah dijumlahkan maka hasilnya akan diletakkan dibawah, yang selanjutnya akan dijumlahkan pada step 2 dengan cara yang sama yaitu menjumlahkan dengan thread sampingnya, proses tersebut akan terus dilakukan hingga didapat hasil akhir dan tidak ada lagi pasangan nilai yang harus dijumlahkan.

jadi pada step 1

10 + 1 + 8 + (-1) + 0 + (-2) + (3) + (5) + (-2) + (-3) + 2 + 7 + 0 + 11 + 0 + 2

maka hasilnya :

11  7  (-2)  8  (-5)  9  11  2

step 2

11 + 7 + (-2) + 8 + (-5) + 9 + 11 + 2

maka hasilnya :

18  6  4  13

step 3

18 + 6 + 4 + 13

maka hasilnya :

24  17

step 4

24 + 17

maka hasilnya :

41

karena tidak ada lagi pasangan untuk penjumlahan maka proses akan berhenti. Karena untuk menjalankan proses paralel minimal harus ada 2 pasang angka yg akan dihitung.Maka hasil dari proses penjumlahan secara parellel di atas adalah 41

referensi :

http://developer.download.nvidia.com/compute/cuda/1.1-Beta/x86_website/projects/reduction/doc/reduction.pdf

//

Categories: Uncategorized | Tags: , , , , , , | Tinggalkan komentar

Navigasi pos

Tinggalkan Balasan

Isikan data di bawah atau klik salah satu ikon untuk log in:

Logo WordPress.com

You are commenting using your WordPress.com account. Logout / Ubah )

Gambar Twitter

You are commenting using your Twitter account. Logout / Ubah )

Foto Facebook

You are commenting using your Facebook account. Logout / Ubah )

Foto Google+

You are commenting using your Google+ account. Logout / Ubah )

Connecting to %s

Buat situs web atau blog gratis di WordPress.com.

%d blogger menyukai ini: