Algoritma Paralel

Dalam ilmu komputer, sebuah algoritma paralel atau algoritma bersamaan, sebagai lawan berurutan (atau serial) algoritma tradisional, merupakan 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.

Sebagian besar algoritma yang tersedia untuk menghitung pi (π), di sisi lain, tidak dapat dengan mudah dibagi menjadi bagian-bagian paralel. Mereka membutuhkan hasil dari langkah sebelumnya untuk secara efektif melanjutkan dengan langkah berikutnya. Masalah seperti ini disebut masalah inheren serial. Iteratif metode numerik, seperti metode Newton atau masalah tiga-badan, juga algoritma yang secara inheren serial. Beberapa masalah yang sangat sulit untuk memparalelkan, meskipun mereka rekursif. Salah satu contohnya adalah pencarian mendalam-pertama grafik.

Algoritma paralel berharga karena perbaikan substansial dalam sistem multiprocessing dan munculnya prosesor multi-core. Secara umum, lebih mudah untuk membangun komputer dengan prosesor cepat tunggal dari satu dengan banyak prosesor lambat dengan throughput yang sama. Tapi kecepatan prosesor meningkat terutama dengan mengecilkan sirkuit, dan prosesor modern yang mendorong ukuran fisik dan batas panas. Hambatan kembar telah membalik persamaan, membuat multiprocessing praktis bahkan untuk sistem kecil.

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.