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://nonachubby-artha.blogspot.com/2013/05/algoritma-paralel_12.html
