review algoritma paralel

Apakah Komputasi Paralel itu ?
Apakah Parallel Virtual Machine tersebut ?
dan Apa yang dimaksud dengan peningkatan kinerja komputasi ?

3 pertanyaan ini pasti akan berputar-putar di kepala kalian semua..saya akan coba meringkas dan mengambil intisari dari sebuah jurnal yang berjudul "Komputasi Paralel Menggunakan Parallel Virtual machine Untuk Peningkatan Kinerja Komputasi", jurnal ini ditulis oleh Tomiputra Lauwali, Maria A. Kartawidjaja dari Jur.Teknik Elektro, Universitas Katolik Indonesia Atma Jaya.

KOMPUTASI PARALEL adalah.......
Michael J. Flynn membagi komputer dalam 4 kategori yaitu :
1. SISD (Single Instruction, Single Data Stream)
2. MISD (Multiple Instruction, Single Data Stream)
3. SIMD (Single Instruction, Multiple Data Streams)
4. MIMD (Multiple Instruction, Multiple Data Streams)
Dalam penelitian ini, komputasi paralel digunakan dengan menggunakan paradigma master-slave, yaitu satu proses bertindak sebagai master (tuan) yang dapat membangkitkan proses dari slave (hamba). 
Ukuran yang dapat digunakan untuk mengevaluasi kinerja sistem adalah waktu eksekusi, peningkatan kecepatan (speedup), efisiensi dan biaya.

A. Waktu Eksekusi Program Paralel adalah.......
Penjumlahan waktu komputasi dan waktu komunikasi. Waktu eksekusi dapat diperpanjang dengan adanya Overhead. Overhead dapat dilakukan dengan :
1. Adanya prosessor yang berhenti bekerja
2. Adanya pekerjaan komputasi ekstra pada program paralel
3. Adanya proses sinkronisasi

B. Peningkatan Kecepatan 
Rumus dari Peningkatan Kecepatan adalah Sp = ts/tp
ket : ts = waktu eksekusi program pada satu prosesor
tp = waktu eksekusi program pada p prosesor
Peningkatan kecepatan dibagi 2 yaitu :
1. Peningkatan Kecepatan Mutlak yaitu perbandingan antara waktu eksekusi program serial tercepat dan waktu eksekusi suatu program paralel.
2. Peningkatan Kecepatan Relatif yaitu perbandingan antara waktu eksekusi program paralel pada satu prosesor dan waktu eksekusi program paralel yang sama pada p prosesor. 
Pada penelitian ini yang digunakan adalah Peningkatan Kecepatan Relatif yaitu untuk menginvestasi seberapa besar peningkatan kerja yang diperoleh dengan menggunakan sejumlah prosesor yang bekerja bersama-sama dalam mengeksekusi suatu program.

> PARALLEL VIRTUAL MACHINE (PVM) adalah.......
Suatu perangkat lunak yang telah menjadi standar pemrograman paralel yang umum digunakan. 
Penelitian ini dilakukan dengan menggunakan bahasa C.

Proses yang dilakukan adalah dengan melakukan perkalian Matriks dan Quicksort.

Kesimpulan yang didapat dari tulisan penelitian diatas adalah program paralel perkalian matriks memberikan peningkatan kinerja yang cukup baik.


ALGORITMA PARALEL INTEGRASI NUMERIK ADAPTIF. Akan disajikan suatu algoritma otomasi integrasi dengan menggunakan metode trapesium adaptif. Pembagian interval dilakukan secara adaptif dimana lebar sub-sub-interval tidak sama disesuaikan dengan perilaku lokal dari fungsi. Tinjau suatu integral pada interval [a,b] dengan toleransi maksimumS , estimasi(f,a,b,Z ) . Solusi dari es(imasi(f,a,b,E) akan diterima bila galat yang didapat telah memenuhi kriteria yang ditentukan. Sebaliknya bila kriteria belum terpenuhi, problem tersebut akan dibagi menjadi dua sub-problem yang serupa dan tidak saling tergantung, masing-masing pada interval [a,(a+b)/2] dan [(a+b)/2,b] yaitu estimasi(f,a,(a+b)/2,B /2) dan estimasi(f,(a+b)/2,b,E /2). Selanjutnya kedua sub-problem tersebut akan dikerjakan pada dua prosesor yang berbeda sehingga bisa dikerjakan secara simultan. Mekanisme pembagian ini mungkin akan terus berlanjut sampai kedalaman tertentu. Prosesor utama (root processor) mengatur alokasi sub-problem ke prosesor pekerja (worker processor). Begitu seterusnya akan berlangsung sampai semua sub-problem yang muncul dapat diselesaikan. Kemudian solusi setiap subproblem akan dikirim oleh prosesor pekerja ke prosesor utama untuk digabungkan sehingga diperoleh solusi problem utama. Algoritma ini akan diimplementasikan pada sistem jaringan komputer terdistribusi berbasis C programming dengan parallel virtual machine.


PENDAHULUAN

Berbagai masalah sains dan teknik seringkali iebih mudah diselesaikan bila terlebih dulu dibuat model matematisnya. Sehingga dalam penyelesaiannya akan melibatkan operasi-operasi aritmatik pada model yang terbentuk. Dalam banyak hal metode komputasi numerik memegang peranan yang sangat penting dan telah mampu memberikan solusi dengan tingkat akurasi yang cukup tinggi. Salah satu metode komputasi numerik yang akan dibahas disini adalah metode integrasi numerik, untuk menghitung nilai pendekatan integral suatu fungsi pada interval tertentu, dengan tingkat akurasi yang diinginkan. Perhitungan integral suatu fungsi tidak selamanya dapat dilakukan secara analitik, sehingga perhitungan integral secara numerik tetap diperlukan. Metode-metode integrasi numerik yang ada, selalu membagi interval ke dalam sub-sub-interval dengan iebar yang sama. Untuk itu daiam makalah ini akan dibahas

cara melakukan pembagian lebar sub-interval dengan memperhatikan perilaku iokal dari fungsi. Satu kunci pembuka perkembangan teknologi komputasi modern adalah dengan dikembangkannya teknologi komputasi paralel. Komputasi paralel adalah komputasi yang terdiri dari banyak proses dan setiap proses dapat dieksekusi secara bersama-sama pada prosesor yang berbeda dan antar proses dapat saling berinteraksi. Komputasi parale! akan memberikan kinerja lebih tinggi dengan cost yang rendah bila dilakukan dengan perancangan algoritma paralel yang benar. Pada makalah ini juga akan dibahas sekilas tentang komputasi paralel pada sistem jaringan computer berbasis C programming dengan parallel virtual machine.

SEKELAS TENTANG KOMPUTASI PARALEL PADA PVM

Implementasi dari komputasi paralel telah muncul dua model utama yaitu Massively Parallel Processing (MPP) dan Sistem Terdistribusi. MPP adalah komputer dengan kemampuan yang tinggi, yang menggabungkan ratusan sampai ribuan CPU dalam satu kabinet besar terhubung ke memori dengan kapasitas ratusan Gigabyte dengan model pemrograman shared memory. Sistem Terdistribusi adalah

proses komputasi yang dieksekusi pada sekumpulan komputer yang terhubung dalam suatu network dan digunakan secara bersama-sama untuk menyelesaikan satu problem yang besar, dengan model .pemrograman message passing.

Pola Pemrograman Paralel pada PVM

Komputasi paralel dapat didekati dengan 3 tinjauan dasar yaitu

a. 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, seperti digambarkan di bawah ini.



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

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

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



PENGUKURAN DAN ANALISA

Parameter-parameter yang akan diukur dalam komputasi paralel ini adalah speedup dan c/c ratio. Dengan menghitung speedup bisa diketahui efisiensi penggunaan prosesor dan dengan menghitung c/c ratio dapat diketahui granularitas. Speedup adalah perbandingan kecepatan eksekusi suatu program yang dijalankan pada komputer paralel terhadap kecepatan eksekusi program tersebut pada komputer sekuensial.



Efisiensi Penggunaan Prosesor, untuk memperoieh efisiensi yang tinggi, usahakan agar semua prosesor dalam sistem digunakan secara optimal, tidak ada prosesor yang idle selama prosesor lain bekerja.



Computation to communication ratio adalah perbandingan waktu komputasi terhadap waktu komunikasi dalam komputer MIMD berbasis message passing. c/c ratio adalah salah satu cara memprediksi kinerja dari komputer paralel.

c/c ratio = t_komp_par/ t_komu

Granularitas adalah jumlah operasi yang dilaksanakan sebelum sinkronisasi berlangsung. Berdasarkan Granularitas, algoritma paralel dikategorikan dalam tiga kelompok yaitu fine grain (lebih banyak komunikasi dari pada komputasi), medium-grain (komputasi dan komunikasi seimbang) dan coarse-grain (lebih banyak komputasi dari pada komunikasi), Ditunjukkan hubungan antara c/c ratio dengan granularitas. Jika 0l maka coarse grain.