Nama: Danny Novan
hernawan
Kelas: 4ia19
Npm: 51410681
Algoritma Paralel
Pendahuluan
Sebelum membahas mengenai perancangan ataupun analisis
algoritma, tentunya kita terlebih dahulu harus mendefinisikan arti dari “Algoritma”.
Apa itu algoritma? Algoritma
merupakan langkah-langkah (prosedur) yang harus dilakukan untuk menyelesaikan
sebuah masalah.Program komputer umumnya dibangun dengan menggunakan beberapa
algoritma untuk menyelesaikan sebuah permasalahan. Misalnya sebuah program
pencarian teks seperti grep akan memerlukan algoritma khusus untuk membaca dan
menelusuri file, algoritma lain untuk mencari teks yang tepat di dalam file,
dan satu algoritma lagi untuk menampilkan hasil pencarian ke pengguna. 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.
Teori
Mengadaptasi suatu algoritma sekuensial ke dalam
algoritma paralel. Mempelajari mengenai konsep pemrosesan paralel dan bagaimana
proses-proses dapat berlangsung secara paralel. 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.
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 :
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. Umumnya, setiap iterasi mempergunakan data yang dihasilkan
oleh iterasi sebelumnya dan program akhirnya menuju suatu solusi dengan akurasi
yang dibutuhkan. Algoritma iterasi ini mempunyai peluang paralelisme pada
setiap iterasinya. Beberapa proses parallel dapat dibentuk untuk bekerja pada
array bagian yang berbeda. Namun setelah setiap iterasi, prosesproses harus
disinkronkan, karena hasil yang diproduksi oleh satu proses dipergunakan oleh prosesproses
lain pada iterasi berikutnya. 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.
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.
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. 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.
Analisis
Seperti yang telah dibahas
diatas, bahwa algoritma paralel adalah algoritma yang mengeksekusi suatu proses
secara terbagi-bagi dan hasilnya akan disatukan sehingga akan mendapatkan hasil
yang maksimal. Namun pada penggunaannya algoritm aparalel tersebut membutuhkan
memory ya ng cukup besar dalam beroperasi dan kecepatan prosesor yang tinggi
karena bila memakai prosesosr dan memory yang dipakai rendah maka penerapan
algoritma paralel akan memakan waktu yang lama dan menjadi tidak efisien waktu.
Keuntungannya adalah hasil yang dikerjakan jadi lebih cepat karena dikerjakan
dalam waktu yang bersamaan jika prosessor yang dipakai memadai dan memaksimal
hasil pekerjaan yang kita lakukan.
Refrensi
