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.
|
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
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.
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.
Thx infonya ....lagi belajar algo nih
BalasHapusSama-sama
Hapus