Algoritma Paralel

2:12 AM

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 .