PENDAHULUAN
Algoritma paralel
adalah algoritma 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.
TEORI
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 :
Paralisme Data
Paralisme 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 local 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
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 :
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
Seqential 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.
Komputasi Paralel dengan Parallel
Virtual Machine (PVM)
Komputasi
paralel adalah salah satu
teknik melakukan komputasi secara bersamaan dengan memanfaatkan
beberapa komputer independen secara bersamaan. Ini umumnya diperlukan saat
kapasitas yang diperlukan sangat besar, baik karena harus mengolah data dalam
jumlah besar (di industri keuangan, bioinformatika, dll) ataupun karena
tuntutan proses komputasi yang banyak.
Penggunaan komputasi parallel
prosessing merupakan pilihan yang cukup handal untuk saat ini untuk pengolahan
data yang besar dan banyak, hal ini apabila dibandingkan dengan membeli suatu
super komputer yang harganya sangat mahal maka penggunaan komputasi parallel
prosessing merupakan pilihan yang sangat tepat untuk pengolahan data tersebut.
Aspek keamanan merupakan suatu
aspek penting dalam sistem parallel prosessing komputasi ini, karena di dalam
sistem akan banyak berkaitan dengan akses data, hak pengguna, keamanan data,
keamanan jaringan terhadap peyerangan sesorang atau bahkan virus sehingga akan
menghambat kinerja dari system komputasi ini.
Komputasi
parallel adalah
melakukan perhitungan
komputasi dengan menggunakan 2 atau lebih CPU/Processor
dalam suatu komputer yang sama atau komputer yang berbeda dimana dalam hal ini
setiap instruksi dibagi kedalam beberapa instruksi kemudian dikirim ke
processor yang terlibat komputasi dan dilakukan secara bersamaan. Untuk proses
pembagian proses komputasi tersebut dilakukan oleh suatu software yang betugas
untuk mengatur komputasi dalam hal makalah ini akan digunakan Parallel Virtual
Machine (PVM).
Pada sistem komputasi parallel
terdiri dari beberapa unit prosesor dan beberapa unit memori. Ada dua teknik
yang berbeda untuk mengakses data di unit memori, yaitu shared memory address
dan message passing. Berdasarkan cara mengorganisasikan memori ini komputer
paralel dibedakan menjadi shared memory parallel machine dan distributed memory
parallel machine.
Prosesor dan memori ini didalam
mesin paralel dapat dihubungkan (interkoneksi) secara statis maupun dinamis.
Interkoneksi statis umumnya digunakan oleh distributed memory system (sistem
memori terdistribusi). Sambungan langsung peer to peer digunakan untuk
menghubungkan semua prosesor. Interkoneksi dinamis umumnya menggunakan switch
untuk menghubungkan antar prosesor dan memori.
Komunikasi data pada sistem
paralel memori terdistribusi, memerlukan alat bantu komunikasi. Contoh alat
bantu yang sering digunakan oleh sistem seperti PC Jaringan pada saat ini
adalah standar PVM (Parallel Virtual Machine) yang bekerja diatas TCP/IP
communication layer. Standar ini memerlukan fungsi remote access agar dapat
menjalankan program pada masing-masing unit prosesor.
Salah satu protocol yang
dipergunakan pada komputasi parallel adalah Network File System (NFS), NFS
adalah protokol yang dapat membagi sumber daya melalui jaringan. NFS dibuat
untuk dapat independent dari jenis mesin, jenis sistem operasi, dan jenis
protokol transport yang digunakan. Hal ini dilakukan dengan menggunakan RPC.
NFS memperbolehkan user yang telah diijinkan untuk mengakses file-file yang
berada di remote host seperti mengakses file yang
berada di lokal. Protokol yang digunakan
protokol mount menentukan host remote dan jenis file sistem yang akan diakses
dan menempatkan di suatu direktori, protokol NFS melakukan I/O pada remote file
system. Protokol mount dan protokol NFS bekerja
dengan menggunakan RPC dan mengiri dengan protokol TCP
dan UDP. Kegunaan dari NFS pada komputasi parallel adalah untuk melakukan
sharing data sehingga setiap node slave dapat mengakses program yang sama pada
node master.
ANALISA
Waktu
yang diperlukan, biaya untuk memproses dan efisien penggunaan sumber daya.
Kriteria berikutnya adalah biaya dari suatu algoritma parallel yang
didefinisikan sebagai hasil kali dua ukuran sebelumnya, dinyatakan sebagai
berikut : “ Biaya = running time
parallel x jumlah prosessor yang digunakan”
Biaya
sama dengan jumlah langkah yang dilaksanakan secara bersama prosesor dalam
memecahkan masalah dengan kasus terburuk (worst case) pada algoritma.
Diasumsikan sejumlah prosecor melaksanakan sejumlah langkah yang sama. Apabila
tidak demikian, maka biayanya adalah batas atas jumlah langkah yang
dilaksanakn. Untuk permasalahan berukuran n processor maka biaya diperkirakan
sebagai fungsi dari n yaitu c(n) = p (n)
x t(n), walapun demikian tergantung pula dari masing-masing persoaln yang
dibahas. Pada bab ini juga akan menjelaskan contoh prinsip kerja dari algoritma
pencarian nilai terbesar secara parallel dan algoritma penghitungan rerata secara
parallel.
