5 Apr 2013

ALGORITMA PRAM (PARALLEL RANDOM ACCESS MACHINE)


PENDAHULUAN

Pada Matakuliah Algoritma Pengolahan Paralel diketahui Terdapat beberapa model untuk abstract machine models diantaranya adalah BSP(Bulk Synchronous Parallel), PPM(Phase Parallel Model), dan salah satunya adalah PRAM (Parallel Random Access Machine). Algoritma PRAM, merupakan salah satu algoritma yang digunakan untuk menyelesaikan suatu masalah atau kasus yang berhubungan dengan parallel random dari akses mesin. Bagan dari beberapa pembuatan algoritma secara umum terdiri dari:
1.       Adanya Problem
2.       Melakukan Gambaran / Konsep
3.       Pseudocode
 Pada Algoritma PRAM terdapat enam sub pembelajaran yang wajib kita ketahui antara lain adalah Parallel Reduction, Prefix Sums, List Ranking, Pre-Order Tree Traversal, Merging Two Sorted Lists, dan Graph Coloring, dari semua sub-bab yang ada keseluruhannya kita selalu melakukan tahap pseudocode atau dengan kata lain setelah kita berhasil mempelajari setiap algoritma, kita dirujukkan untuk dapat membuat pengkodingannya.
Tujuan dari pembelajaran Algoritma PRAM ini adalah diharapkan agar teman-teman atau pun adik-adik yang lain dapat memahami komputasi parallel dari model-model PRAM, algoritma PRAM, dan kompleksitasnya.

Materi Pembelajaran Algoritma PRAM:
1.       Parallel Reduction
2.       Prefix Sums
3.       List Ranking
4.       Pre-Order Tree Traversal
5.       Merging Two Sorted Lists
6.       Graph Coloring

Algoritma PRAM terdiri dari dua kata, yaitu Algoritma dan PRAM. Algoritma mempunyai arti sebagai kumpulan perintah yang ada untuk menyelesaikan suatu masalah atau kasus dan PRAM merupakan singkatan dari PARALLEL RANDOM ACCESS MACHINE atau dengan kata lain dapat disebut dengan parallel random untuk mesin akses, jadi dengan kata lain Algoritma PRAM adalah salah satu algoritma yang digunakan dalam abstraksi model mesin yang menyangkut tentang pemodelan parallel random dari akses mesin.

Fase pada Algoritma PRAM:
Gambar 1.0
Terlihat pada gambar 1, terdapat beberapa computer dimana salah satunya sebagai server dan yang lainnya sebagai client. Pada fase 1 kita menyalakan sejumlah computer atau PC tersebut. Kemudian langkah selanjutnya adalah dalam pengerjaannya kita melakukan komputasi secara parallel.
Perbedaan Komputasi secara parallel dan tunggal adalah:
Pada komputasi parallel kita melakukan komputasi secara bersamaan dengan memanfaatkan beberapa computer independen secara bersamaan, sedangkan pada komputasi secara tunggal kita melakukan komputasi secara bertahap.  

Secara ringkas fase Algoritma PRAM adalah:
1.       Mengaktifkan Sejumlah Prosesor
2.       Prosesor yang sudah diaktifkan, melakukan komputasi secara parallel

 

*      Parallel Reduction / pengurangan paralel
Pengurangan atau penyingkatan dari banyaknya alur atau kasus yang ada.
Konsep / gambaran parallel reduction:

Gambar 1.1

Proses ini disebut juga dengan reduksi parallel



 Contoh sederhana dari konsep reduksi parallel diatas:

Setelah mengetahui konsep dari reduksi parallel maka kita harus bisa menjabarkan code yang kita gunakan untuk kasus reduksi tersebut (lihat gambar dibawah ini):

*      Prefix Sums
Prefix Sums: melakukan penjumlahan (sum) dengan yang sebelumnya (pre).
Contoh :



Pada gambar diatas diketahui bahwa terdapat sebuah nilai a dan b, dengan komponen a terdiri dari AbCDeFghI dan komponen nilai b adalah 101101001. Maka langkah awalnya adalah melakukan penjumlahan dari nilai yang sudah diketahui bilangannya dengan melakukan compute prefix sums, maka didapatlah hasilnya:

Baru kemudian dari komponen a, kita lakukan pack upper-case letter. Memilah komponen alphabet yang terdiri dari huruf capital:

*      List Ranking















Gambar diatas memenuhi ketentuan dari List Ranking, cara membaca polanya adalah Ketika nilai-nilai yang ada merupakan nilai yang berbeda dan secara berurut maka semua nilai secara langsung akan menuju 0 dan jika nilai-nilainya terdapat nilai yang sama secara berurut maka nilai pertama yang berbeda dari angka 1 akan langsung menuju nilai 0 dan yang selain dari akan menuju nilai 1, kemudian jika masih ada maka akan menuju nilai 2, dan seterusnya.

*      Preorder Tree Traversal
Algoritma preoerder tree traversal memiliki 4 fase:
1.       Algoritma membentuk singly –linked list (ada penelusuran edge turun dan naik)
2.       Bobot verterksnya (naik = 0 dan turun = 1)
3.       Setiap elemen singly-linked list menghitung ranknya dari list secara parallel
4.       Prosesor yang diasosiasikan dengan edge yang turun menggunakan rank yang sudah dihitung sebagai nomor dari dari penelusuran preorder.

Contoh, Diketahui sebuah pohon pada gambar (a) disamping, maka dapat diketahui edgenya (gambar b)
Pada gambar b, terlihat jelas alur naik dan alur turun dari edge-edgenya. Maka dengan gambar b ini kita dapat membuat linked-listnya:

Setelah membuat linked listnya, pada gambar d (jumping pointer) semua pointer kita arahkan menuju linked list yang terakhir yang artinya menuju C,A. kemudian hitung total bobot dari setiap verteksnya pada akhir list.


gambar e merupakan nilai-nilai penelusuran dari depan (preorder traversal).


*      Merging Two Sorted Lists
Menggabungkan dua daftar list menjadi satu kesatuan elemen pada setiap waktu.


Pada gambar 1.7 dapat diketahui terdapat 2 short list dengan komponennya masing-masing. Dari dua short list tersebut digabung menjadi satu elemen satu kesatuan dengan waktu kompleksitasnya secara sekuensial n log n.

*      Graph Coloring
Problem klasik algoritma tentang bagaimana caranya mewarnai graph dengan warna berbeda untuk setiap node yang “berdekatan”. “Berdekatan” artinya ada edge yang menghubungkan kedua node tersebut. “Problemnya” adalah bagaimana caranya mengusahakan agar jumlah warna yang digunakan seminimal mungkin.
Contoh Sederhana:
Pada gambar diatas diketahui bahwa kita memerlukan 3 warna untuk mewarnai graph diatas.


PENUTUP

Penulis ingin menyampaikan rasa Terima Kasih kepada Alloh SWT yang selalu memberi rizki dan hidayah-Nya disetiap nafas yang diberikan, kepada Ke-dua Orang tua yang selalu membuka tangannya, dan juga teman-teman yang telah menambah warna kehidupan.
Semoga dari pembelajaran yang ada dapat menambah pengetahuan teman-teman dan juga adik –adik menyangkut tentang Algoritma PRAM dan perbedaan dari setiap sub-bab yang ada. Pembelajaran tentang apa itu Parallel Reduction, edge, node, bagaimana caranya menggabungkan dua short list, dan sebagainya.
Penulis menyadari masih banyak kekurangan dari materi yang sudah disediakan dan diharapkan jika teman-teman atau pun adik-adik ingin belajar ulang atau memahami lebih dalam tentang Algoritma PRAM dimohon untuk menutup kekurangan tersebut.

Daftar Pustaka:                                                                                                


2 komentar: