Algoritma Paralel adalah sebuah algoritma yang dapat
dieksekusi sepotong pada waktu pada banyak perangkat pengolahan yang berbeda,
dan kemudian digabungkan bersama-sama lagi pada akhir untuk mendapatkan hasil
yang benar. Algoritma paralel berharga karena perbaikan substansial dalam
multiprocessing sistem dan munculnya multi-core prosesor. Algoritma paralel cenderung digunakan untuk menyelesaikan
masalah numerik, karena masalah numerik merupakan salah satu masalah yang
memerlukan kecepatan komputasi yang sangat tinggi. Untuk dapat mengadaptasi
suatu algoritma sekuensial ke dalam algoritma paralel, terlebih dahulu harus
dipelajari mengenai konsep pemrosesan paralel dan bagaimana proses-proses dapat
berlangsung secara paralel.
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.
3. 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.
4. 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.
5. 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.
6. 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.
Desain
- SISD Single Instruction stream, Single Data Stream
istilah yang mengacu pada arsitektur komputer di mana
prosesor tunggal, sebuah uniprocessor, mengeksekusi aliran instruksi tunggal,
untuk beroperasi pada data yang tersimpan dalam memori tunggal. Ini sesuai
dengan arsitektur von Neumann . SISD adalah salah satu dari empat klasifikasi
utama sebagaimana didefinisikan dalam taksonomi Flynn . Sering dijumpai pada
aplikasi PC.
- ISD Multiple Instruction Stream, Single Data Stream
Jenis komputasi paralel arsitektur di mana banyak unit
fungsional melakukan operasi yang berbeda pada data yang sama. Pipa arsitektur
termasuk tipe ini, meskipun purist mungkin mengatakan bahwa data berbeda
setelah pengolahan oleh setiap tahap dalam pipa. Komputer toleransi kegagalan
mengeksekusi instruksi yang sama secara berlebihan dalam rangka untuk
mendeteksi dan masker kesalahan, dengan cara yang dikenal sebagai replikasi
tugas , dapat dianggap milik jenis ini.
Contoh
aplikasi:
- Komputasi untuk menentukan suatu bilangan integer merupakan bilangan prima atau bukan.
- Mesin robot untuk scanning laut yang dalam untuk membedakan suatu objek apakah ikan, batu karang, bangkai kapal, atau benda lainnya.
- SIMD Single Instruction Stream, Multiple Data Stream
Kelas komputer paralel dalam taksonomi Flynn . Ini
menggambarkan komputer dengan beberapa elemen pemrosesan yang melakukan operasi
yang sama pada beberapa titik data secara bersamaan. Dengan demikian, mesin
tersebut memanfaatkan data tingkat paralelisme . SIMD ini terutama berlaku
untuk tugas umum seperti menyesuaikan kontras dalam citra digital atau
menyesuaikan volume audio digital . Komputer memiliki N prosesor yang identik.
Tiap prosesor memiliki memori local untuk simpan data atau program. Semua
prosesor di bawah control satu aliran instruksi dari suatu sentral unit
control. Prosesor prosesor beroperasi secara sinkron.
- MIMD Multiple Instruction Stream, Multiple Data Stream
Teknik yang digunakan untuk mencapai paralelisme.
Mesin menggunakan MIMD memiliki sejumlah prosesor yang berfungsi asynchronous
dan independen. Setiap saat, prosesor yang berbeda dapat mengeksekusi instruksi
yang berbeda pada bagian yang berbeda dari data. Arsitektur MIMD dapat
digunakan di sejumlah area aplikasi seperti desain dibantu komputer /
manufaktur dibantu komputer , simulasi , pemodelan , dan sebagai switch
komunikasi .
