Pada
Tugas kali ini saya akan membahas tentang Algoritma Paralel yang saya
ketahui. yang dimana di bawah ini adalah beberapa penjelasan tentang
teknik dan komputasi Algoritma Paralel.
Teknik
pembangunan algoritma paralel dapat dibedakan sebagai berikut :
Paralelisme Data
Teknik paralelisme data merupakan teknik yang paling banyak digunakan dalam program paralel. Teknik ini lahir dari penelitian bahwa aplikasi utama komputasi paralel adalah dalam bidang sain dan engineer, yang umumnya melibatkan array multi-dimensi yang sangat besar. Dalam program sekuensial biasa, array ini dimanipulasi dengan mempergunakan perulangan bersarang untuk mendapatkan hasil. Kebanyakan program paralel dibentuk dengan mengatur ulang algoritma sekuensial agar perulangan bersarang tersebut dapat dilaksanakan secara paralel. Paralelisme data menunjukkan bahwa basis data dipergunakan sebagai dasar untuk membentuk aktifitas paralel, dimana bagian yang berbeda dari basis data akan diproses secara paralel. Dengan kata lain paralelisme dalam program ini dibentuk dari penerapan operasi-operasi yang sama ke bagian array data yang berbeda. Prinsip paralelisme data ini berlaku untuk pemrograman multiprosesor dan multikomputer.
Partisi Data
Merupakan teknik khusus dari Paralelisme Data, dimana data disebar ke dalam memori-memori lokal multikomputer. Sebuah proses paralel kemudian ditugaskan untuk mengoperasikan masingmasing bagian data. Proses tersebut harus terdapat dalam lokal memori yang sama dengan bagian data, karena itu proses dapat mengakses data tersebut secara lokal. Untuk memperoleh kinerja yang baik, setiap proses harus memperhatikan variabel-variabel dan data-data lokalnya masing-masing. Jika suatu proses membutuhkan akses data yang terdapat dalam remote memori, maka hal ini dapat dilakukan melalui jaringan message passing yang menghubungkan prosesor-prosesor. Karena komunikasi antar prosesor ini menyebabkan terjadinya waktu tunda, maka messsage passing ini sebaiknya dilakukan dalam frekuensi yang relatif kecil. Dapat disimpulkan bahwa tujuan dari partisi data adalah untuk mereduksi waktu tunda yang diakibatkan komunikasi messsage passing antar prosesor. Algoritma paralel mengatur agar setiap proses dapat melakukan komputasi dengan lokal data masing-masing.
Algoritma Relaksasi
Pada algoritma ini, setiap proses tidak membutuhkan sinkronisasi dan komunikasi antar proses. Meskipun prosesor mengakses data yang sama, setiap prosesor dapat melakukan komputasi sendiri tanpa tergantung pada data antara yang dihasilkan oleh proses lain. Contoh algoritma relaksasi adalah algoritma perkalian matrik, pengurutan dengan mengunakan metode ranksort dan lain sebagainya.
Paralelisme Sinkron
Aplikasi praktis dari komputasi paralel adalah untuk problem yang melibatkan array multi-dimensi yang sangat besar. Problem tersebut mempunyai peluang yang baik untuk paralelisme data karena elemen yang berbeda dalam array dapat diproses secara paralel. Teknik komputasi numerik pada array ini biasanya iteratif, dan setiap iterasi akan mempengaruhi iterasi berikutnya untuk menuju solusi akhir. Misalnya saja untuk solusi persamaan numerik pada sistem yang besar.
Paralelisme Data
Teknik paralelisme data merupakan teknik yang paling banyak digunakan dalam program paralel. Teknik ini lahir dari penelitian bahwa aplikasi utama komputasi paralel adalah dalam bidang sain dan engineer, yang umumnya melibatkan array multi-dimensi yang sangat besar. Dalam program sekuensial biasa, array ini dimanipulasi dengan mempergunakan perulangan bersarang untuk mendapatkan hasil. Kebanyakan program paralel dibentuk dengan mengatur ulang algoritma sekuensial agar perulangan bersarang tersebut dapat dilaksanakan secara paralel. Paralelisme data menunjukkan bahwa basis data dipergunakan sebagai dasar untuk membentuk aktifitas paralel, dimana bagian yang berbeda dari basis data akan diproses secara paralel. Dengan kata lain paralelisme dalam program ini dibentuk dari penerapan operasi-operasi yang sama ke bagian array data yang berbeda. Prinsip paralelisme data ini berlaku untuk pemrograman multiprosesor dan multikomputer.
Partisi Data
Merupakan teknik khusus dari Paralelisme Data, dimana data disebar ke dalam memori-memori lokal multikomputer. Sebuah proses paralel kemudian ditugaskan untuk mengoperasikan masingmasing bagian data. Proses tersebut harus terdapat dalam lokal memori yang sama dengan bagian data, karena itu proses dapat mengakses data tersebut secara lokal. Untuk memperoleh kinerja yang baik, setiap proses harus memperhatikan variabel-variabel dan data-data lokalnya masing-masing. Jika suatu proses membutuhkan akses data yang terdapat dalam remote memori, maka hal ini dapat dilakukan melalui jaringan message passing yang menghubungkan prosesor-prosesor. Karena komunikasi antar prosesor ini menyebabkan terjadinya waktu tunda, maka messsage passing ini sebaiknya dilakukan dalam frekuensi yang relatif kecil. Dapat disimpulkan bahwa tujuan dari partisi data adalah untuk mereduksi waktu tunda yang diakibatkan komunikasi messsage passing antar prosesor. Algoritma paralel mengatur agar setiap proses dapat melakukan komputasi dengan lokal data masing-masing.
Algoritma Relaksasi
Pada algoritma ini, setiap proses tidak membutuhkan sinkronisasi dan komunikasi antar proses. Meskipun prosesor mengakses data yang sama, setiap prosesor dapat melakukan komputasi sendiri tanpa tergantung pada data antara yang dihasilkan oleh proses lain. Contoh algoritma relaksasi adalah algoritma perkalian matrik, pengurutan dengan mengunakan metode ranksort dan lain sebagainya.
Paralelisme Sinkron
Aplikasi praktis dari komputasi paralel adalah untuk problem yang melibatkan array multi-dimensi yang sangat besar. Problem tersebut mempunyai peluang yang baik untuk paralelisme data karena elemen yang berbeda dalam array dapat diproses secara paralel. Teknik komputasi numerik pada array ini biasanya iteratif, dan setiap iterasi akan mempengaruhi iterasi berikutnya untuk menuju solusi akhir. Misalnya saja untuk solusi persamaan numerik pada sistem yang besar.
Pola Pemrograman Paralel pada PVM
Komputasi paralel dapat didekati dengan 3
tinjauan dasar yaitu :
a. Crowd Computation
Adalah model paling umum dan terdiri dari
kumpulan proses yang saling berhubungan sangat erat. Melakukan komputasi pada
bagian-bagian yang berbeda dari workload. Contoh untuk pola ini adalah Model
Master-Slave. Program master bertugas penyebaran proses (spawn
proses), inisialisasi, collection, display hasil dan mungkin display
fungsi-fungsi waktu. Sedang program slave bertugas melaksanakan komputasi yang
sebenarnya, menerima alokasi task/workload dari master baik secara statis
maupun dinamis dan melakukan komputasi task-task dari alokasi dirinya sendiri.
b. Tree Computation
Adalah pola pemrograman dimana proses disebar
secara dinamis seperti tree. Hubungan antar node sebagai hubungan parent-child.
Cocok untuk aplikasi dimana total proses yang akan terbentuk tidak
diketahui sebelumnya. Biasanya tree computation ini dipakai urituk
algoritma-algoritma branch and bound, alpa beta search dan algoritma
recursive divide and conquer.
c. Hybrid Computation
Adalah model komputasi yang
merupakan kombinasi model tree dan model crowd. Model ini memiliki struktur penyebaran
proses yang lebih bebas.