Algoritma 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.

Berikut merupakan komputer paralel :

Dua tipe utama:

1. Shared memory multiprocessor
   Cara natural untuk mengembangkan model prosesor tunggal - multiple processor dihubungkan ke multiple memory modules, sedemikian sehingga setiap prosesor dapat mengakses memory module yang manapun

2.      Distributed memory multicomputer

NOTASI UNTUK ALGORITMA PARALEL

-          Untuk Shared-Memory Model

·         Global

·         Local

-          Untuk Distributed Memory Machine

·         Parameter → suatu konstanta yang sudah dikomunikasikan antar prosesor.

-          Umum

·         +, x, ¬

·         if … else … endif ; while … endwhile ; for … endfor

·         for all … → data paralelism

-          SIMD : diasumsikan ada lockstep

-          MIMD : diasumsikan berjalan asynchronous

-          ¬ menyatakan suatu prosesor store/retrieve nilai local dari prosesor lain.

-          [x] a menyatakan nilai dari prosesor.

tmp ¬ [s] a

TEKNIK PEMBANGUNAN ALGORITMA PARALEL

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 :

1.      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.

2.      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.

3.      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.

4.      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. Algoritma iterasi ini mempunyai peluang paralelisme pada setiap iterasinya. Beberapa proses parallel dapat dibentuk untuk bekerja pada array bagian yang berbeda. 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.

5.      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.

Source :

http://imadeyudierawan.blogspot.com/2010/08/algoritma-paralel.html?m=1

http://freddykurnia.web.ugm.ac.id/?p=397