Algoritma Pemrosesan Paralel

2.1.1 Pengertian Algoritma
Algoritma pada sistem kerja komputer dapat meliputi brainware, hardware, dan software. Tanpa salah satu dari ketiga sistem tersebut, komputer tidak akan berguna. Kita akan lebih fokus pada software komputer. Software terbangun atas susunan program dan syntax. Untuk menyusun program atau syntax, diperlukannya langkah-langkah yang sistematis dan logis untuk dapat menyelesaikan masalah atau tujuan dalam proses pembuatan suatu software. Maka algoritma berperan penting dalam penyusunan program atau syntax tersebut.

Pengertian algoritma adalah susunan yang logis dan sistematis untuk memecahkan suatu masalah atau untuk mencapai tujuan tertentu. Dalam dunia komputer, algoritma sangat berperan penting dalam pembangunan suatu software.
Dalam dunia sehari-hari, mungkin tanpa kita sadari algoritma telah masuk dalam kehidupan kita. Jadi perlu diingat bahwa algoritma tidak hanya diterapkan pada dunia komputasi, tetapi juga algoritma diterapkan dalam kehidupan sehari-hari.
Sedangkan dalam dunia komputasi, contoh penggunaan algoritma adalah dalam pembuatan program pada bahasa pemrograman seperti bahasa C, C#, dan Visual Basic. Dengan syntax pada tiap bahasa pemrograman dan algoritma, maka akan tersusun program-program dan terlahirlah software.

2.1.2 Algoritma Paralel
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.
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 masing-masing 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.

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

2.1.4 Paralelisme Sinkron
Aplikasi praktis dari komputasi paralel adalah untuk masalah yang melibatkan array multi-dimensi yang sangat besar. Masalah 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 paralel dapat dibentuk untuk bekerja pada array bagian yang berbeda. Namun setelah setiap iterasi, proses-proses 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.

2.1.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.
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. Masalah 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.

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


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.

2.1.6 PVM (Parallel Virtual Machine)
PVM (Parallel Virtual Machine) adalah paket software yang mendukung pengiriman pesan untuk komputasi parallel antar komputer. PVM dapat berjalan diberbagai macam variasi UNIX atau pun windows dan telah portable untuk banyak arsitektur seperti PC, workstation, multiprocessor dan superkomputer.
Sistem PVM terbagi menjadi dua. Pertama adalah daemon, pvmd, yang berjalan pada mesin virtual masing-masing komputer. Mesin virtual akan dibuat, ketika user mengeksekusi aplikasi PVM. PVM dapat dieksekusi melalui prompt UNIX disemua host. Bagian kedua adalah library interface rutin yang mempunyai banyak fungsi untuk komunikasi antar task . Library ini berisikan rutin yang dapat dipanggil untuk pengiriman pesan, membuat proses baru, koordinasi task dan konfigurasi mesin virtual.
Salah aturan main yang penting dalam PVM adalah adanya mekanisme program master dan slave/worker. Programmer harus membuat kode master yang menjadi koordinator proses dan kode slave yang menerima, menjalankan, dan mengembalikan hasil proses ke komputer master. Kode master dieksekusi paling awal dan kemudian melahirkan proses lain dari kode master. Masing-masing program ditulis menggunakan C atau Fortran dan dikompilasi dimasing-masing komputer. Jika arsitektur komputer untuk komputasi paralel semua sama, (misalnya pentium 4 semua), maka program cukup dikompilasi pada satu komputer saja. Selanjutnya hasil kompilasi didistribusikan kekomputer lain yang akan menjadi node komputasi parallel. Program master hanya berada pada satu node sedangkan program slave berada pada semua node.
Komunikasi dapat berlangsung bila masing-masing komputer mempunyai hak akses ke filesystem semua komputer. Akses ke file system dilakukan melalui protokol rsh yang berjalan di unix atau windows.
Berikut adalah langkah pengaturan pada masing-masing komputer :
• Buat file hostfile yang berisi daftar node komputer dan nama user yang akan dipakai untuk komputasi paralel. Bila nama user pada semua komputer sama misalnya nama user riset pada komputer C1, C2,C3 dan C4, maka hostfile ini boleh tidak ada. Hostfile ini dapat digunakan bila nama user di masing-masing komputer berbeda.
• Daftarkan IP masing-masing komputer pada file/etc/hosts/hosts.allow dan /etc/hosts/hosts.equiv.
• Penambahan dan penghapusan host secara dinamis dapat dilakukan melalui konsole PVM. Bila IP tidak didefinisikan pada hostfile¸ cara ini dapat digunakan.
Program PVM terdiri dari master dan slave, dimana program master dieksekusi paling awal dan kemudian melahirkan proses lain. PVM memanggil rutin pvm_spawn() untuk melahirkan satu atau dua proses lebih yang sama. Fungsi-fungsi untuk PVM versi bahasa C mempunyai rutin awalan pvm. Pengiriman dan penerimaan task diidentifikasi dengan TID (Task Identifier). TID ini bersifat unik dan digenerate oleh pvmd lokal. PVM berisi beberapa rutine yang mengembalikan nilai TID sehingga aplikasi user dapat mengidentifikasi task lain disistem.

1. 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 paralel 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 sistem komputasi ini.
Komputasi paralel adalah melakukan perhitungan komputasi dengan menggunakan 2 atau lebih CPU/Prosesor dalam suatu komputer yang sama atau komputer yang berbeda dimana dalam hal ini setiap instruksi dibagi kedalam beberapa instruksi kemudian dikirim ke prosesor 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 sistem (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 paralel adalah untuk melakukan sharing data sehingga setiap node slave dapat mengakses program yang sama pada node master.

2. Langkah – Langkah Penggunaan Parallel Virtual Machine (PVM)
Secara umum, langkah implementasi komputasi parallel sebagai berikut :
a. Jalankan PVM daemon pada setiap mesin dalam cluster.
b. Jalankan program master pada master daemon.
c. Master daemon akan menjalankan proses slave.
Untuk mengimplementasikannya, dapat memakai tools :
- PVM, virtual machine dan routine untuk komputasi paralel
- rsh (remote shell), aplikasi untuk authentikasi dan komunikasi proses antar komputer.
- Xpvm versi 1.2, interface grafis untuk PVM dengan animasi eksekusi komputasi paralel yang dapat dilihat dilayar.

3. Pola Pemrograman Paralel pada PVM
Komputasi paralel dapat didekati dengan 3 tinjauan dasar yaitu
a. Crowd Computation
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.
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.
b. Tree Computation
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 search dan algoritma recursive divide and conquer.
c. Hybrid Computation
Hybrid computation adalah model komputasi yang merupakan kombinasi model tree dan model crowd. Model ini memiliki struktur penyebaran proses yang lebih bebas.

2.2 Proses

2.2.1 Konsep Proses
Untuk membangun suatu algoritma program paralel, pengertian mengenai konsep proses merupakan alat bantu yang sangat berguna. Proses sendiri diartikan sebagai sederatan operasi yang dapat dibentuk oleh sebuah prosesor tunggal. Proses dapat dipergunakan sebagai blok pembangunan dasar dari pemrograman paralel, setiap prosesor mengeksekusi proses tertentu pada saat tertentu. Secara informal, proses dapat berupa sub rutin atau prosedur yang dieksekusi oleh prosesor tertentu. Ketersediaan sejumlah besar prosesor secara fisik berarti bahwa sejumlah besar proses dapat dieksekusi secara paralel oleh perangkat keras komputer. Dengan asumsi bahwa setiap aktifitas dari setiap proses mempunyai kontribusi terhadap keseluruhan komputasi, maka eksekusi komputasi tersebut akan lebih cepat dibandingkan jika dilakukan dengan prosesor tunggal. Agar konsep proses berguna dalam pembuatan program, konsep proses ini menjadi feature tambahan dalam bahasa pemrograman paralel.
Untuk menggabungkan konsep proses ke dalam bahasa pemrograman paralel, harus terdapat beberapa mekanisme dalam bahasa tersebut untuk mendefinisikan dan membentuk proses baru. Harus terdapat pula beberapa feature dalam bahasa tersebut untuk membagi (sharing) data antar prosesor paralel, dengan demikian setiap proses dapat berinteraksi satu sama lainnya untuk menyelesaikan keseluruhan komputasi. Setiap proses dapat mengeksekusi dengan kecepatan yang berbeda pada prosesor yang berbeda.

2.2.2 Status Proses
Pada dasarnya terdapat lima kemungkinan status untuk proses yang sedang aktif, yaitu :
- Ready, proses dikatakan dalam status ready jika proses tersebut memungkinkan untuk dieksekusi tetapi pada saat tersebut tidak dieksekusi oleh prosesor yang telah ditentukan. Pada saat pertama kali proses dibentuk, proses tersebut mempunyai status ready.
- Running, tiap satuan waktu hanya terdapat satu proses yang dapat berjalan pada satu prosesor.
- Blocked, suatu proses yang dalam status ready harus menunggu event dari proses lainnya, misalnya menunggu data hasil proses lain, maka proses tersebut berubah status menjadi blocked. Jika semua proses dalam status blocked, maka kondisi ini disebut deadlock. Hal ini menyebabkan eksekusi program tidak dapat diteruskan.
- Delayed, status delayed pada dasarnya hampir sama dengan status blocked, kecuali bahwa event yang ditunggu sebenarnya telah muncul. Karena waktu tunda komunikasi dalam arsitektur komputer, maka event tersebut belum tiba pada proses yang sedang blocked tersebut. Status delayed hanya akan muncul pada arsitektur multikomputer.
- Spinning, status proses spinning hanya akan muncul pada arsitektur multiprosesor.Status ini muncul pada saat proses tersebut harus menunda eksekusinya karena diharuskan menunggu proses lain selesai dieksekusi. Teknik menunda proses tersebut dengan menggunakan operasi lock, menunggu sampai proses lain melakukan operasi unlock. Teknik ini disebut busy-waiting. Pada dasarnya status ini sama dengan blocked, perbedaannya terletak pada teknik penundaan proses yang dipergunakan.

2.2.3 Pembentukan Proses
Aktifitas komputasi dimulai ketika suatu proses ditugaskan ke suatu prosesor dalam komputer paralel. Proses dapat digambarkan sebagai suatu kumpulan kode program yang ditugaskan ke suatu prosesor tertentu untuk dieksekusi. Dalam program paralel, eksekusi program dimulai sama seperti halnya program sekuensial biasa. Program paralel memerlukan suatu statement untuk pembentukan proses. Statement tersebut menyebabkan program membentuk proses baru untuk ditugaskan pada prosesor lain, yang kemudian mengeksekusi proses tersebut. Gambaran umum aktifitas paralel adalah sebagai berikut : proses yang sedang berjalan pada prosesor mengeksekusi statemen pembentukan proses, proses yang dibentuk disebut child process (proses anak), sedangkan pembentuk proses disebut parent process (proses induk). Program di bawah ini merupakan program sekuensial untuk mendapatkan akar dari elemenelemen array. Pada contoh program tersebut terdapat satu perulangan FOR. Perulangan ini menunjukkan potensi paralelisme program. Modifikasi yang dilakukan adalah dengan mengubah statement FOR dengan statement FORALL untuk membentuk proses anak. Statemen FORALL ini merupakan statement yang terdapat pada sistem Multi-Pascal.
PROGRAM SQRT;
VAR A: ARRAY [1..100] OF REAL;
I : INTEGER;
BEGIN
…
FOR i := 1 TO 100 DO
A[I] := SQRT([I]);
END.
Hasil modifikasi statement FOR menjadi FORALL dapat dilihat pada program di bawah ini :
PROGRAM SQRTParalel;
VAR A: ARRAY [1..100] OF REAL;
I : INTEGER;
BEGIN
…
FORALL i := 1 TO 100 DO
A[I] := SQRT([I]);
END.
Pada awal program utama, proses induk mengeksekusi statemen FORALL, dalam keadaan demikian status induk proses adalah running. Statemen FORALL pada program di atas membentuk 100 salinan statemen A[i]:=SQRT([i]) dan setiap satu proses paralel mempunyai variabel indeks i. Ke- 100 proses anak tersebut dieksekusi pada prosesor yang berbeda dan berlangsung secara paralel. Sewaktu proses induk menunda eksekusinya hingga seluruh proses anak selesai dieksekusi, proses induk tersebut dalam status blocked. Sedangkan seluruh proses anak yang sedang dieksekusi mempunyai status running. Setelah seluruh Proses anak selesai dieksekusi, proses induk berstatus running hingga terminasi. Pembentukan proses ini digambarkan sebagai berikut.

Pada contoh di atas, array A disimpan ke dalam memori bersama yang mudah diakses oleh prosesor-prosesor. Setiap prosesor akan bekerja dengan bagian elemen array, seluruhnya berlangsung secara paralel. Hal yang penting pada contoh di atas adalah mengenai variabel indeks i. Pada perulangan FOR sekuensial, indeks i adalah variabel integer tunggal yang bernilai 1 pada iterasi pertama, kemudian bernilai 2 pada iterasi kedua dan seterusnya. Pada saat iterasi dimulai, indeks variabel i secara otomatis berubah menjadi nilai berikutnya dan dapat dipergunakan dalam perulangan (loop). Hal ini merupakan karakter standar perulangan FOR dalam Perangkat Lunak Pascal.
Pada perulangan FOR paralel, indeks variabel i - seperti pada statemen FOR – dideklarasikan sebagai variabel INTEGER di awal program. Setelah itu, variabel i akan menjadi variabel local tunggal yang disimpan di memori bersama. Jika iterasi akan dieksekusi secara paralel, maka satu indeks variabel tunggal i tidak akan mencukupi. Semua nilai i dari 1 sampai 100 harus diperoleh secara simultan. Hal ini ditangani oleh perlangkat lunak secara otomatis, dengan jaminan setiap prosesor mempunyai salinan lokal indeks i sendiri. Jadi prosesor 1 mempunyai variabel lokal i dengan nilai 1, prosesor 2 mempunyai nilai i = 2 dan seterusnya.

2.2.4 Granularitas Proses
Hal penting yang perlu dipertimbangkan dalam pembentukan proses adalah granularitas proses, yaitu waktu berlangsungnya atau waktu eksekusi setiap proses. Dari contoh di atas, ketika statemen FORALL diekseskusi di prosesor 0, maka aktifitas komputasi yang terjadi di prosesor 0 adalah sebagai berikut :
Buat Proses Anak dan diberikan ke prosesor 1
Buat Proses Anak dan diberikan ke prosesor 2
.
.
Buat Proses Anak dan diberikan ke prosesor 100
Jika waktu pembentukan proses anak adalah 10 unit waktu, maka statemen FORALL akan membutuhkan 100.10 = 1000 unit waktu untuk membentuk seluruh proses anak. Jika statemen penugasan A[i] := SQRT(A[i]) membutuhkan waktu eksekusi 10 unit waktu, maka keseluruhan waktu yang statement FORALL adalah 1000+10=1010 unit waktu. (Proses Induk yang berjalan pada prosesor 0 membutuhkan 1000 unit waktu untuk membuat 100 Proses Anak, dan keseluruhan proses anak ini akan berjalan secara paralel dalam waktu 10 unit waktu). Jika menggunakan FOR secara sekuensial, maka seluruh perulangan akan dilaksanakan di prosesor 0. Misalkan statemen penugasan A[i] := SQRT(A[i]) membutuhkan waktu eksekusi 10 unit waktu, maka waktu keseluruhan yang dibutuhkan oleh statemen FOR adalah 100.10 = 1000 unit waktu.
Dibandingkan dengan menggunakan statemen FORALL yang membutuhkan waktu sebesar 1010 unit waktu, maka eksekusi secara sekuensial menghasilkan waktu yang lebih baik. Pada contoh di atas, terjadi kegagalan speedup. Jika waktu untuk pembentukan proses anak adalah tetap 10 unit waktu dan setiap proses anak mempunyai granularitas yang besar, misalnya 10000 unit waktu, maka total waktu eksekusi secara paralel adalah 11000. 1000 unit waktu untuk pembentukan 100 proses anak dan 10000 unit waktu untuk eksekusi proses. Dibandingkan dengan eksekusi yang dilakukan secara sekuensial yang akan membutuhkan 100.10000 = 1000000 unit waktu, maka speedup yang diperoleh adalah 1000000/11000 = 91.
Untuk meningkatkan efisiensi, granularitas dapat ditingkatkan dengan cara mengelompokkan beberapa nilai indeks ke dalam proses yang sama. Pada contoh algoritma di atas, misalkan dibentuk 10 proses dengan masing-masing 10 nilai indeks variabel i. Contohnya seperti di bawah ini :
PROGRAM SQRTParallelGroup;
VAR A: ARRAY [1..100] OF REAL;
I : INTEGER;
BEGIN
FORALL I := 1 TO 10 GROUPING 10 DO
A[I] := SQRT([I]);
END.
Pada contoh di atas, prosesor 0 hanya membentuk 10 proses. Masing-masing proses secara sekuensial melakukan pengulangan 10 kali. Proses 1 melakukan iterasi dengan nilai indeks 1 sampai 10, proses 2 melakukan iterasi nilai indeks 11 sampai 20 dan seterusnya. Jika ukuran kelompok tidak genap dibagi dengan nilai indeks, maka proses anak terakhir akan mempunyai nilai indeks yang lebih kecil daripada nilai indeks ukuran. Seperti halnya statemen FOR, statemen FORALL dapat dipergunakan dalam perulangan bersarang. Contohnya adalah program pertambahan matrik berikut ini :
PROGRAM TambahMatrik;
VAR i, j : INTEGER;
A,B,C : ARRAY [1..20,1..30] OF REAL;
BEGIN
FORALL i := 1 to 20 DO
FORALL j:= 1 to 30 DO
C[i,j] := A[i,j] + B[i,j];
END.
Contoh program di atas menunjukkan 600 proses telah dibentuk. Pembentukan ini terdiri dari dua tahap. Tahap pertama - pada statemen FORALL pertama dengan nilai indeks i dari 1 sampai 20 -, menghasilkan 20 proses anak, masing-masing untuk nilai indeks i. Setiap proses anak ini terdiri dari statemen FORALL kedua. Ketika setiap proses anak generasi pertama ini dieksekusi pada prosesor yang telah ditugaskan, ke-20 proses tersebut masing-masing akan membentuk 30 proses anak, sesuai dengan nilai indeks j. Jadi total proses anak yang dibentuk adalah 600 proses. Masing-masing proses dibentuk untuk setiap elemen dari Matrik. Pembuatan proses secara bertingkat ini akan mereduksi keseluruhan waktu pembentukan proses. Hal ini disebabkan generasi pertama dari proses anak akan dieksekusi secara paralel pada prosesor yang berbeda. Dibandingkan dengan hanya satu prosesor membentuk seluruh proses, maka akan terdapat 20 prosesor yang membentuk proses anak baru secara paralel. Misalkan terdapat dua perulangan FORALL bersarang dengan perulangan terluar mempunyai nilai indeks n dan perulangan terdalam mempunyai nilai indeks m. Jika waktu untuk membentuk satu proses adalah C, maka total waktu untuk membentuk semua nm proses adalah C(n+m). Jika seluruh proses dibentuk oleh satu proses induk, maka waktu total pembentukan adalah Cnm. Secara umum aktifitas yang terjadi pada saat statement FORALL tersebut dieksekusi adalah sebagai berikut :
Buat sejumlah n proses anak (dengan statemen FORALL),
Tunggu sampai seluruh n proses anak tersebut selesai dieksekusi,
Lanjutkan eksekusi setelah FORALL
Dapat dilihat bahwa ketika proses anak sedang dieksekusi, maka proses induk akan menunda eksekusinya – berstatus blocked - sampai seluruh proses anak selesai dieksekusi. Untuk beberapa algoritma tertentu, akan lebih efisien jika seluruh proses anak running secara parallel dengan proses induk. Konsekuensinya, meskipun proses induk telah mencapai terminasi program sewaktu proses anak sedang berjalan, proses induk tidak diijinkan untuk berhenti sampai seluruh proses anaknya selesai dieksekusi. Dengan kata lain diperlukan featuring untuk menahan proses induk mencapai terminasi program utama agar seluruh proses anak dapat dieksekusi dengan benar. Featuring ini terdapat dalam beberapa beberapa perangkat lunak paralel.

2.2.5 Proses Komunikasi
Pada algoritma relaksasi, setiap proses paralel berjalan secara independen tanpa interaksi dengan proses-proses lain. Dalam algoritma relaksasi paralel, tidak ada proses yang menulis nilai yang kemudian digunakan oleh proses lain. Algoritma ini sederhana dan menghasilkan speedup yang baik sewaktu diterapkan pada berbagai arsitektur komputer paralel. Untuk algoritma yang tidak termasuk algoritma relaksasi, diperlukan mekanisme tertentu dalam menangani proses komunikasi yang terjadi. Misalkan terdapat 2 proses pada multiprosesor, P1 dan P2. Dalam ekseskusinya P1 menghasilkan suatu nilai dan menulis nilai tersebut ke variabel bersama C yang kemudian dipergunakan oleh P2 untuk komputasi berikutnya, seperti pada gambar .13. Selama P1 dan P2 merupakan proses paralel, tidak ada jaminan bahwa P1 akan menulis nilai ke variable C sebelum P2 membacanya. Jika P1 dibiarkan menyelesaikan eksekusinya dan kemudian P2 memulai eksekusi, berarti paralelisme proses tidak diperoleh. Tipe komunikasi proses ini sering muncul dalam berbagai program paralel, satu proses melakukan komputasi terhadap beberapa nilai yang akan dipergunakan oleh proses paralel lainnya. Untuk menangani masalah ini, diperlukan suatu kanal (channel) yang mempunyai properti ‘kosong’. Ketika suatu proses membaca kanal yang kosong, maka eksekusi proses secara otomatis akan tertunda sampai terdapat proses lain yang menulis suatu nilai ke dalam kanal tersebut. Untuk contoh di atas, dengan membuat variabel C menjadi variabel kanal yang diinisiasi ‘kosong’, proses P2 akan menunggu pembacaan variabel C sebelum proses P1 selesai menuliskan suatu nilai ke dalam variabel C. Dengan demikian komunikasi proses dijamin berlangsung dengan benar.

Variabel kanal ini akan sangat berguna untuk komputasi pipeline, dimana data hasil komputasi proses dikirimkan ke proses berikutnya melalui variabel kanal. Terdapat perbedaan yang sangat mendasar pada pemodelan perangkat lunak konseptual untuk multiprosesor dan multikomputer. Hal ini dikarenakan adanya perbedaan dalam hal variable bersama, yang dapat diakses oleh seluruh prosesor. Pada multikomputer, yang tidak mengenal variabel bersama, tiap prosesor mempunyai memori lokal sendiri untuk mengakses variabel lokalnya sendiri. Prosesor tersebut terhubung secara fisik melalui jaringan, yang dapat mengirim blok data dari suatu proses ke proses lain. Secara fisik, prosesor dapat berkomunikasi dengan prosesor lain dengan mengirimkan message melalui sambungan saluran penghubung (connection link). Jika proses merupakan abstraksi perangkat lunak dari prosesor fisik, maka abstraksi perangkat lunak untuk saluran komunikasi dapat berupa kanal komunikasi antara proses-proses. Dengan kata lain, proses dapat berkomunikasi dengan proses lain dengan mengirimkan message melalui variabel kanal. Untuk menyesuaikan variabel kanal dalam program multikomputer, fungsi dan semantiknya harus diubah. Pada multiprosesor, variabel kanal serupa dengan variabel bersama yang dapat diakses oleh semua prosesor. Variabel ini tidak seperti saluran komunikasi dari suatu multikomputer, yang secara fisik menghubungkan dua prosesor yang spesifik. Untuk membuat variabel kanal dapat mencerminkan sifat saluran komunikasi, ujung penerima (receiving end) dari tiap kanal haruslah dihubungkan ke suatu proses yang spesifik.

Karakteristik penting pada komunikasi adalah adanya jaminan bahwa pesan yang dikirim oleh suatu sumber tertentu ke tujuan yang sama, akan datang sesuai dengan urutan pengirimannya. Variabel kanal yang ditugaskan pada proses spesifik dalam multikomputer akan memiliki sifat yang sedikit berbeda dengan variabel kanal biasa pada multiprosesor. Untuk itu membedakannya, variabel kanal tersebut disebut port komunikasi. Pembentukan port komunikasi ini dapat dilaksanakan bersamaan dengan pembentukan proses anak. Port komunikasi hanya dapat dibaca oleh satu proses yang spesifik. Pada operasi penulisan ke port terdapat waktu tunda sebelum message sampai ke kanal tujuan. Besar waktu tunda tergantung dari topologi arsitektur multikomputer. Waktu tunda yang terjadi pada penulisan port memiliki implikasi penting yang mempengaruhi kinerja program.
Secara umum, aktifitas proses induk pada program multikomputer dapat digambarkan sebagai berikut :
Interaksi dengan user untuk mendapatkan data awal, baik dari disk maupun dari piranti masukan.
Membentuk proses-proses anak yang akan membangun komputasi paralel.
Mengumpulkan hasil komputasi proses anak dan melaporkannya ke user atau menuliskan ke disk.
Dari aktifitas di atas, terlihat perlu adanya komunikasi antara proses induk dengan proses anak. Komunikasi proses induk yang berjalan dua arah ini, yaitu kirim (send) dan terima (receive) pesan, dilakukan dengan menggunakan port komunikasi. Pengiriman hasil komputasi dari proses anak ke proses induk dapat juga dilakukan melalui parameter-parameter proses anak.
Parameter yang dipergunakan dapat berupa parameter value dan parameter VAR. Parameter value digunakan untuk memberikan data awal ke proses anak, sedangkan parameter VAR digunakan untuk mengumpulkan data hasil komputasi proses anak. Parameter VAR di sini merupakan remote var yang mempunyai dua karakteristik penting, yaitu bahwa parameter ini hanya dapat ditulis dan tidak dapat dibaca. Proses penulisan dilakukan di prosesor anak, sedangkan yang ditulis sebenarnya adalah alamat parameter yang ada di remote prosesor. Untuk topologi multikomputer yang mempertimbangkan waktu komunikasi antar prosesor, lokasi relative dari prosesor akan sangat mempengaruhi waktu tunda komunikasi tersebut. Prosesor yang jauh letaknya akan mempunyai waktu tunda komunikasi lebih lama dibandingkan dengan prosesor yang dekat. Untuk itu perlu dipertimbangkan pengalokasian prosesor untuk proses tertentu secara eksplisit oleh pemrogram.

2.3 Pemrosesan Paralel

2.3.1 Pengertian Pemrosesan Paralel
Pemrosesan paralel (parallel processing) adalah penggunakan lebih dari satu CPU untuk menjalankan sebuah program secara simultan. Idealnya, paralel processing membuat program berjalan lebih cepat karena semakin banyak CPU yang digunakan. Tetapi dalam praktek, seringkali sulit membagi program sehingga dapat dieksekusi oleh CPU yang berbea-beda tanpa berkaitan di antaranya.


1. Komputasi paralel
Komputasi paralel adalah salah satu teknik melakukan komputasi secara bersamaan dengan memanfaatkan beberapa komputer secara bersamaan. Biasanyadiperlukan saat kapasitas yang diperlukan sangat besar, baik karena harus mengolah data dalam jumlah besar ataupun karena tuntutan proses komputasi yang banyak. Untuk melakukan aneka jenis komputasi paralel ini diperlukan infrastruktur mesin paralel yang terdiri dari banyak komputer yang dihubungkan dengan jaringan dan mampu bekerja secara paralel untuk menyelesaikan satu masalah. Untuk itu diperlukan aneka perangkat lunak pendukung yang biasa disebut sebagai middleware yang berperan untuk mengatur distribusi pekerjaan antar node dalam satu mesin paralel. Selanjutnya pemakai harus membuat pemrograman paralel untuk merealisasikan komputasi.
Komputasi paralel membutuhkan:
• algoritma
• bahasa pemrograman
• compiler

2. Pemrograman paralel
Pemrograman parallel adalah teknik pemrograman komputer yang memungkinkan eksekusi perintah/operasi secara bersamaan baik dalam komputer dengan satu (prosesor tunggal) ataupun banyak (prosesor ganda dengan mesin paralel) CPU. Tujuan utama dari pemrograman paralel adalah untuk meningkatkan performa komputasi. Semakin banyak hal yang bisa dilakukan secara bersamaan (dalam waktu yang sama), semakin banyak pekerjaan yang bisa diselesaikan.
Sebagai besar komputer hanya mempunyai satu CPU, namun ada yang mempunyai lebih dari satu. Bahkan juga ada komputer dengan ribuan CPU. Komputer dengan satu CPU dapat melakukan parallel processing dengan menghubungkannya dengan komputer lain pada jaringan. Namun, parallel processing ini memerlukan software canggih yang disebut distributed processing software.
Parallel processing berbeda dengan multitasking, yaitu satu CPU mengeksekusi beberapa program sekaligus. Parallel processing disebut juga parallel computing.

2.3.2 Hubungan Antar Prosesor
Sistem komputer paralel dengan banyak prosesor yang bekerja secara simultan memerlukan kemampuan untuk membagi data dan berkomunikasi antar prosesor. Berdasarkan kedua kebutuhan tersebut, terdapat dua arsitektur komputer paralel, yaitu memori bersama dan message passing. Pada arsitektur memori bersama, biasanya disebut multiprosesor (multiprocessor), setiap prosesor dapat mengakses memori global dan menggunakan isi data dan struktur data yang disimpan dalam memori bersama (shared memory). Prosesor berkomunikasi dengan prosesor lain dengan menulis pesan ke memori global dimana prosesor kedua dapat membaca pesan tersebut pada lokasi memori yang sama. Skema arsitektur memori bersama dapat dilihat pada gambar.

Semua prosesor dapat melakukan komputasi secara paralel dan masing-masing dapat mengakses memori melalui bus. Bus bertanggung jawab mengatur permintaan pemakaian memori yang berlangsung secara simultan oleh beberapa prosesor. Bus juga bertanggung jawab untuk meyakinkan bahwa semua prosesor dilayani secara adil dengan waktu tunda (delay) akses yang minimum.
Salah satu kesulitan utama dari arsitektur multiprosesor dengan memori bersama adalah kemungkinan adanya tabrakan memori (memory contention). Peristiwa ini terjadi ketika beberapa prosesor mencoba untuk mengakses memori bersama dalam periode waktu yang sangat singkat, sehingga memori tidak akan dapat menampung semua permintaan secara simultan. Akibatnya beberapa prosesor akan harus menunggu sampai prosesor lainnya dilayani. Kemungkinan terjadinya tabrakan memori ini berbanding lurus dengan bertambahnya jumlah prosesor. Beberapa teknik telah dikembangkan untuk mereduksi tabrakan memori dan membuat sistem menjadi lebih efisien. Salah satu teknik adalah dengan adanya cache memory lokal pada masing-masing prosesor. Cache memory ini digunakan untuk menyimpan salinan isi memori yang paling baru dipergunakan. Hal ini menimbulkan masalah baru, yaitu cache coherent problem, dimana akan banyak salinan isi memori pada cache yang berbeda yang menimbulkan adanya kemungkinan isi cache yang outdate setelah isi memori bersama diperbaharui (update). Teknik lain untuk mereduksi tabrakan memori adalah dengan membagi memori bersama tersebut menjadi beberapa bagian modul yang dapat diakses secara paralel oleh prosesor yang berbeda. Data disebar ke beberapa modul memori untuk menghindari kemungkinan permintaan yang simultan ke modul memori yang sama oleh beberapa prosesor. Setiap n prosesor dapat mengakses m modul memori melalui jaringan penghubung prosesor - memori (processor -memory connection network).
Skema arsitektur memori bersama dengan jaringan penghubung prosesor - memori dapat dilihat pada gambar.

Jaringan penghubung ini menyebabkan beberapa prosesor dapat mengakses modul-modul memori yang berbeda secara simultan. Biaya dan kinerja tipe multiprosesor ini tergantung pada rancangan internal jaringan penghubung.
Beberapa contoh jaringan penghubung ini adalah jaringan butterfly, shuffle-exchange, cross-bar dan omega. Pendekatan lain untuk mereduksi tabrakan memori adalah dengan mengeliminasi seluruh memori bersama dan menyediakan memori lokal untuk setiap prosesor. Jenis komputer parallel dengan memori yang tersebar ini disebut multicomputer. Setiap pasangan memori - prosesor ini berlaku seperti halnya komputer sekuensial. Prosesor - prosesor dapat membaca (read) dan menulis (write) data secara bebas dengan menggunakan local memorinya masing-masing. Sebuah prosesor tidak dapat mengakses lokal memori prosesor lain dengan secara langsung, tetapi prosesor tersebut dapat mengirim atau menerima data dari prosesor lain dengan mengunakan jaringan komunikasi message passing. Sehingga data dapat disebar dan ditukar sesuai dengan kebutuhan.
Message Passing Interface (MPI) adalah sebuah standard pemrograman yang memungkinkan pemrogram untuk membuat sebuah aplikasi yang dapat dijalankan secara paralel. Proses yang dijalankan oleh sebuah aplikasi dapat dibagi untuk dikirimkan ke masing – masing compute node yang kemudian masing – masing compute node tersebut mengolah dan mengembalikan hasilnya ke komputer head node. Untuk merancang aplikasi paralel tentu membutuhkan banyak pertimbangan – pertimbangan diantaranya adalah latensi dari jaringan dan lama sebuah tugas dieksekusi oleh prosesor.
MPI ini merupakan standard yang dikembangkan untuk membuat aplikasi pengirim pesan secara portable. Sebuah komputasi paralel terdiri dari sejumlah proses, dimana masing-masing bekerja pada beberapa data lokal. Setiap proses mempunyai variabel lokal, dan tidak ada mekanisme suatu proses yang bisa mengakses secara langsung memori yang lain. Pembagian data antar proses dilakukan dengan message passing, yaitu dengan mengirim dan menerima pesan antar proses.
MPI menyediakan fungsi-fungsi untuk menukarkan antar pesan. Kegunaan MPI yang lain adalah.
1. menulis kode paralel secara portable,
2. mendapatkan performa yang tinggi dalam pemrograman paralel, dan
3. menghadapi permasalahan yang melibatkan hubungan data irregular atau dinamis yang tidak begitu cocok dengan model data paralel.
Skema arsitektur Message-Passing Muticomputer dapat dilihat pada gambar.

Keterangan :
P : Prosesor
M : Memori