Algoritma Paralel

ALGORITMA PARALEL

PENDAHULUAN

Dalam matematika dan komputasi, Algoritma merupakan kumpulan perintah untuk menyelesaikan suatu masalah. Perintah-perintah ini dapat diterjemahkan secara bertahap dari awal hingga akhir. Masalah tersebut dapat berupa apa saja, dengan catatan untuk setiap masalah, ada kriteria kondisi awal yang harus dipenuhi sebelum menjalankan algoritma. Algoritma akan dapat selalu berakhir untuk semua kondisi awal yang memenuhi kriteria, dalam hal ini berbeda dengan heuristik. Algoritma sering mempunyai langkah pengulangan (iterasi) atau memerlukan keputusan (logika Boolean dan perbandingan) sampai tugasnya selesai.

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. Secara umum, lebih mudah untuk membangun komputer dengan prosesor cepat tunggal dari satu dengan banyak prosesor lambat dengan sama throughput yang . 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. Biaya atau kompleksitas algoritma serial diperkirakan dalam hal ruang (memori) dan waktu (siklus prosesor) yang mereka ambil. Algoritma paralel perlu mengoptimalkan satu sumber daya yang lebih, komunikasi antara prosesor yang berbeda. Ada dua cara paralel prosesor berkomunikasi, memori bersama atau pesan lewat.

TEORI

Dalam ilmu komputer, sebuah algoritma paralel, sebagai lawan berurutan 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. 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 :

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.

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.

Pada algoritma parallel terdapat beberapa teknik pembangunan yang 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. 

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.

Komputasi paralel dapat didekati dengan 3 tinjauan dasar yaitu :

Crowd Computation

Adalah model paling umum dan terdiri dari kumpulan proses yang saling berhubungan sangat erat. Melakukan komputasi pada bagian-bagian yang berbeda dari workload. Contoh untuk pola ini adalah Model Master-Slave. Program master bertugas penyebaran proses (spawn proses), inisialisasi, collection, display hasil dan mungkin display fungsi-fungsi waktu. Sedang program slave bertugas melaksanakan komputasi yang sebenarnya, menerima alokasi task/workload dari master baik secara statis maupun dinamis dan melakukan komputasi task-task dari alokasi dirinya sendiri.

Tree Computation

Adalah pola pemrograman dimana proses disebar secara dinamis seperti tree. Hubungan antar node sebagai hubungan parent-child.Cocok untuk aplikasi dimana total proses yang akan terbentuk tidak diketahui sebelumnya. Biasanya tree computation ini dipakai urituk algoritma-algoritma branch and bound, alpa beta searchdan algoritma recursive divide and conquer.

Hybrid Computation

Adalah model komputasi yang merupakan kombinasi model treedan model crowd. Model ini memiliki struktur penyebaran proses yang lebih bebas.

ANALISA DAN KESIMPULAN

Dalam pembuatan suatu program yang sangat rumit, dibutuhkan suatu metode atau suatu algoritma yang mampu menyelesaikan masalah atau kegiatan dengan cepat dan mudah. Dibutuhkan pula algoritma yang memudahkan dalam melakukan trouble shooting atau penyelesaian masalah baik dari segi design maupun atau hal hal yang berhubungan dengan program kompeks yang dibuat tersebut. Oleh karena itu banyak programmer yang menggunakan algoritma parallel yang memang mendukung komputasi dalam segi kecepatan dan kemudahan. Oleh karena itu, pentingnya suatu pemahaman yang baik bagi para programmer untuk algoritma yang menjadi dasar sampai algoritma parallel agar terciptanya suatu konsep komputasi yang lebih baik.

REFERENSI

http://id.wikipedia.org/wiki/Algoritma
http://nonachubby-artha.blogspot.com/2013/05/algoritma-paralel_12.html

http://fikrilookup.wordpress.com/2013/05/12/algoritma-paralel/

http://imadeyudierawan.blogspot.com/2010/08/algoritma-paralel.html