Tugas Pemrosesan Parallel (Parallel Random Access Machine)

PARALLEL RANDOM ACCESS MACHINE

Algoritma-algoritma PRAM memiliki 2 (dua) fase :

1. Mengaktifkan sejumlah prosesor

2. Prosesor yang sudah diaktifkan (pada fase 1), melaksanakan komputasi secara paralel

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

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

spawn ()

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

for all

do

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.

Algoritma lain yang mengalirkan data secara bottom-up (daun -akar) adalah operasi reduksi atau “fan-in”.

DEFINISI

Diberikan sekumpulan n nilai a1, a2, … ,an dan operator biner asosiatif Å, “reduksi” adalah proses menghitung dari :

a1 Å a2 Å … Å an

Salah satu contoh dari operasi reduksi adalah penjumlahan paralel (parallel summation).

Algoritma yang dibahas :

1. Parallel reduction (Reduksi paralel)

2. Prefix sums (sering disebut parallel prefixes, scan)

3. List ranking

4. Pre-order tree traversal`

5. Merging two sorted lists

6. Graph coloring

Untuk lebih lengkapnya silahkan download disini