Dalam beberapa
kasus, algoritma sekuensial dengan mudah dapat diadaptasi ke dalam lingkungan
paralel. Namun dalam kebanyakan kasus, problem komputasi harus dianalisa ulang
dan menghasilkan algoritma paralel yang baru. Terdapat beberapa penelitian
mengenai perancangan algoritma paralel untuk problem-problem praktis seperti
pengurutan, pemrosesan geraf, solusi untuk persamaan lanjar, solusi untuk
persamaan diferensial, dan untuk simulasi. 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. 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.