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. Umumnya, setiap iterasi mempergunakan data yang dihasilkan
oleh iterasi sebelumnya dan program akhirnya menuju suatu solusi dengan akurasi
yang dibutuhkan. Algoritma iterasi ini mempunyai peluang paralelisme pada
setiap iterasinya. Beberapa proses parallel dapat dibentuk untuk bekerja pada
array bagian yang berbeda. Namun setelah setiap iterasi, prosesproses harus
disinkronkan, karena hasil yang diproduksi oleh satu proses dipergunakan oleh
prosesproses lain pada iterasi berikutnya. Teknik pemrograman paralel seperti
ini disebut paralelisme sinkron. Contohnya adalah perhitungan numerik pada
Metode Eliminasi Gauss. Pada paralelisme sinkron ini, struktur umum programnya
biasanya terdiri dari perulangan FORALL yang akan membentuk sejumlah besar
proses paralel untuk dioperasikan pada bagian array data yang berbeda. Setiap
proses diulang dan disinkronkan pada akhir iterasi. Tujuan dari sinkronisasi
ini adalah untuk meyakinkan bahwa seluruh proses telah menyelesaikan iterasi
yang sedang berlangsung, sebelum terdapat suatu proses yang memulai iterasi
berikutnya.
Komputasi Pipeline
Pada komputasi pipeline, data dialirkan melalui seluruh
struktur proses, dimana masing-masing proses membentuk tahap-tahap tertentu
dari keseluruhan komputasi . Algoritma ini dapat berjalan dengan baik pada
multikomputer, karena adanya aliran data dan tidak banyak memerlukan akses ke
data bersama. Contoh komputasi pipeline adalah teknik penyulihan mundur yang
merupakan bagian dari metoda Eliminasi.
Dalam merancang suatu algoritma paralel kita harus
mempertimbangkan pula hal-hal yang dapat mengurangi kinerja program paralel.
Hal-hal tersebut adalah :
- 1. Memory Contention
Eksekusi prosesor tertunda
ketika prosesor menunggu hak ases ke sel memori yang sedang dipergunakan oleh
prosesor lain. Problem ini muncul pada arsitektur multiprosesor dengan memori
bersama.
- 2. Excessive Sequential Code
Pada beberapa algoritma paralel,
akan terdapat kode sekuensial murni dimana tipe tertentu dari operasi pusat
dibentuk, seperti misalnya pada proses inisialisasi. Dalam beberapa algoritma,
kode sekuensial ini dapat mengurangi keseluruhan speedup yang dapat dicapai. Process
Creation Time Pembentukan proses paralel akan membutuhkan waktu eksekusi. Jika
proses yang dibentuk relative berjalan dalam waktu yang relatif lebih singkat
dibandingkan dengan waktu pembentukan proses itu sendiri, maka overhead
pembuatan akan lebih besar dibandingkan dengan waktu eksekusi paralel
algoritma. Communication Delay Overhead ini muncul hanya pada multikomputer.
Hal ini disebabkan karena interaksi antar prosesor melalui jaringan komunikasi.
Dalam beberapa kasus, komunikasi antar dua prosesor mungkin melibatkan beberapa
prosesor antara dalam jaringan komunikasi. Jumlah waktu tunda komunikasi dapat
menurunkan kinerja beberapa algoritma paralel.
Synchronization Delay
Ketika proses paralel disinkronkan, berarti bahwa suatu
proses akan harus menunggu proses lainnya. Dalam beberapa program paralel,
jumlah waktu tunda ini dapat menyebabkan bottleneck dan mengurangi speedup
keseluruhan. Load Imbalance Dalam beberapa program paralel, tugas komputasi
dibangun secara dinamis dan tidak dapat diperkirakan sebelumnya. Karena itu
harus selalu ditugaskan ke prosesor-prosesor sejalan dengan pembangunan tugas
tersebut. Hal ini dapat menyebabkan suatu prosesor tidak bekerja (idle),
sementara prosesor lainnya tidak dapat mengerjakan task yang ditugaskannya.