NAMA : Ansari Milah Ibrahim
KELAS : 4IA19
NPM : 50410935
BLOG
: ansorpunya.blogspot.com
DOSEN : KUWAT S.
========================================================
ALGORITMA
PARALEL
BAB
I
PENDAHULUAN
Seiring dengan perkembangan komputer dari
berbagai generasi, kebutuhan akan kinerja dan performa dari komputerpun semakin
meningkat. Belum lagi untuk mengelola data yang banyak dan besar, diperlukan
teknik dan algoritma yang handal untuk
menanganinya. Oleh dari itu berbagai solusi dan teori mulai bermunculan.
Perkembangan tekhnologi dari software hingga hardware gencar dilakukan. Salah
satu cara yang memungkin untuk meningkatkan kinerja dan performa dari komputer
adalah dengan menerapkan tekhnik algoritma paralel.
Maka pada kesempatan ini saya ingin berbagi sedikit informasi tentang satu algoritma
yang sangat populer pada era ini, yaitu algoritma paralel.
BAB
II
TEORI
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.
Desain
- SISD Single Instruction stream, Single Data Stream
Istilah yang mengacu pada arsitektur
komputer di mana prosesor tunggal, sebuah uniprocessor, mengeksekusi aliran
instruksi tunggal, untuk beroperasi pada data yang tersimpan dalam memori
tunggal. Ini sesuai dengan arsitektur von Neumann . SISD adalah salah satu dari
empat klasifikasi utama sebagaimana didefinisikan dalam taksonomi Flynn . Dalam
sistem ini klasifikasi didasarkan pada jumlah instruksi bersamaan dan data stream
hadir dalam arsitektur komputer. Menurut Michael J. Flynn , SISD dapat memiliki
karakteristik pemrosesan konkuren. Instruksi fetching dan eksekusi pipelined
instruksi adalah contoh umum ditemukan di komputer SISD paling modern.
- MISD Multiple Instruction Stream, Single Data Stream
Jenis komputasi paralel arsitektur
di mana banyak unit fungsional melakukan operasi yang berbeda pada data yang
sama. Pipa arsitektur termasuk tipe ini, meskipun purist mungkin mengatakan
bahwa data berbeda setelah pengolahan oleh setiap tahap dalam pipa. Komputer
toleransi kegagalan mengeksekusi instruksi yang sama secara berlebihan dalam
rangka untuk mendeteksi dan masker kesalahan, dengan cara yang dikenal sebagai
replikasi tugas , dapat dianggap milik jenis ini. Tidak banyak contoh
arsitektur ini ada, sebagai MIMD dan SIMD sering lebih tepat untuk data teknik
paralel umum. Secara khusus, mereka memungkinkan skala yang lebih baik dan
penggunaan sumber daya komputasi daripada MISD tidak. Namun, salah satu contoh
yang menonjol dari MISD dalam komputasi adalah Space Shuttle komputer kontrol
penerbangan.
- SIMD Single Instruction Stream, Multiple Data Stream
Kelas
komputer paralel dalam taksonomi Flynn . Ini menggambarkan komputer dengan
beberapa elemen pemrosesan yang melakukan operasi yang sama pada beberapa titik
data secara bersamaan. Dengan demikian, mesin tersebut memanfaatkan data
tingkat paralelisme . SIMD ini terutama berlaku untuk tugas umum seperti
menyesuaikan kontras dalam citra digital atau menyesuaikan volume audio digital
. Paling modern CPU desain termasuk instruksi SIMD dalam rangka meningkatkan
kinerja multimedia digunakan.
Keuntungan
SIMD antara lain sebuah aplikasi yang dapat mengambil keuntungan dari SIMD
adalah salah satu di mana nilai yang sama sedang ditambahkan ke (atau
dikurangkan dari) sejumlah besar titik data, operasi umum di banyak multimedia
aplikasi. Salah satu contoh akan mengubah kecerahan gambar. Setiap pixel dari
suatu gambar terdiri dari tiga nilai untuk kecerahan warna merah (R), hijau (G)
dan biru (B) bagian warna. Untuk mengubah kecerahan, nilai-nilai R, G dan B
yang dibaca dari memori, nilai yang ditambahkan dengan (atau dikurangi dari)
mereka, dan nilai-nilai yang dihasilkan ditulis kembali ke memori.
Dengan
prosesor SIMD ada dua perbaikan proses ini. Untuk satu data dipahami dalam
bentuk balok, dan sejumlah nilai-nilai dapat dimuat sekaligus. Alih-alih
serangkaian instruksi mengatakan “mendapatkan pixel ini, sekarang mendapatkan
pixel berikutnya”, prosesor SIMD akan memiliki instruksi tunggal yang efektif
mengatakan “mendapatkan n piksel” (dimana n adalah angka yang bervariasi dari
desain untuk desain). Untuk berbagai alasan, ini bisa memakan waktu lebih
sedikit daripada “mendapatkan” setiap pixel secara individual, seperti desain
CPU tradisional.
Keuntungan
lain adalah bahwa sistem SIMD biasanya hanya menyertakan instruksi yang dapat
diterapkan pada semua data dalam satu operasi. Dengan kata lain, jika sistem
SIMD bekerja dengan memuat delapan titik data sekaligus, add operasi yang
diterapkan pada data akan terjadi pada semua delapan nilai pada waktu yang
sama. Meskipun sama berlaku untuk setiap desain prosesor super-skalar, tingkat
paralelisme dalam sistem SIMD biasanya jauh lebih tinggi.
Kekurangannya
adalah :
- Tidak semua algoritma dapat vectorized. Misalnya, tugas aliran-kontrol-berat seperti kode parsing tidak akan mendapat manfaat dari SIMD.
- Ia juga memiliki file-file register besar yang meningkatkan konsumsi daya dan area chip.
- Saat ini, menerapkan algoritma dengan instruksi SIMD biasanya membutuhkan tenaga manusia, sebagian besar kompiler tidak menghasilkan instruksi SIMD dari khas C Program, misalnya. vektorisasi dalam kompiler merupakan daerah aktif penelitian ilmu komputer. (Bandingkan pengolahan vektor .)
- Pemrograman dengan khusus SIMD set instruksi dapat melibatkan berbagai tantangan tingkat rendah.
- SSE (Streaming SIMD Ekstensi) memiliki pembatasan data alignment , programmer akrab dengan arsitektur x86 mungkin tidak mengharapkan ini.
- Mengumpulkan data ke dalam register SIMD dan hamburan itu ke lokasi tujuan yang benar adalah rumit dan dapat menjadi tidak efisien.
- Instruksi tertentu seperti rotasi atau penambahan tiga operan tidak tersedia dalam beberapa set instruksi SIMD.
- Set instruksi adalah arsitektur-spesifik: prosesor lama dan prosesor non-x86 kekurangan SSE seluruhnya, misalnya, jadi programmer harus menyediakan implementasi non-Vectorized (atau implementasi vectorized berbeda) untuk mereka.
- Awal MMX set instruksi berbagi register file dengan tumpukan floating-point, yang menyebabkan inefisiensi saat pencampuran kode floating-point dan MMX. Namun, SSE2 mengoreksi ini.
SIMD
dibagi menjadi beberapa bentuk lagi yaitu :
- Exclusive-Read, Exclusive-Write (EREW) SM SIMD
- Concurent-Read, Exclusive-Write (CREW) SM SIMD
- Exclusive-Read, Concurrent-Write (ERCW) SM SIMD
- Concurrent-Read, Concurrent-Write (CRCW) SM SIMD
- MIMD Multiple Instruction Stream, Multiple Data Stream
Teknik
yang digunakan untuk mencapai paralelisme. Mesin menggunakan MIMD memiliki
sejumlah prosesor yang berfungsi asynchronous dan independen. Setiap saat,
prosesor yang berbeda dapat mengeksekusi instruksi yang berbeda pada bagian
yang berbeda dari data. Arsitektur MIMD dapat digunakan di sejumlah area
aplikasi seperti desain dibantu komputer / manufaktur dibantu komputer ,
simulasi , pemodelan , dan sebagai switch komunikasi . Mesin MIMD dapat menjadi
baik memori bersama atau memori terdistribusi kategori. Klasifikasi ini
didasarkan pada bagaimana prosesor MIMD memori akses. Mesin memori bersama
mungkin dari berbasis bus , diperpanjang, atau hirarkis jenis. Mesin memori
terdistribusi mungkin memiliki hypercube atau jala skema interkoneksi.
BAB III
ANALISA
3.1
Contoh
implementasi dalam bidang ilmu Komputasi Modern
Seperti
yang dijelaskan diatas, 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).
3.2
Pengertian
PVM
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
kefile system dilakukan melalui protokol rsh yang berjalan di unix atau
windows.
• Buat file hostfile yang
berisi daftar node komputer dan nama user yang akan dipakai untuk komputasi
parallel. 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.
BAB IV
KESIMPULAN
Setiap
hari, kebutuhan akan teknologi semakin tak terbantahkan. Seiringan dengan itu perkembangan
teknologi lambat-laun semakin maju. Tak dapat dipungkiri jaman sekarang ini,
banyak kehidupan manusia yang bergantung pada perkembangan teknologi, dengan
begitu performa dan kecepatan dari teknologi semakin di perhitungkan. Perkembangan
komputasi dengan menggunakan 2 atau
lebih CPU/Processor dalam suatu komputer yang sama semakin menunjukkan keunggulannya,
sehingga diharapkan algoritma parallel ini dapat menjadi solusi dari
permasalahan ini.
SUMBER:
http://smartgen.wordpress.com/2010/03/17/contoh-software-algoritma-paralel/
http://smartgen.wordpress.com/2010/03/17/contoh-software-algoritma-paralel/
http://fikrilookup.wordpress.com/2013/05/12/algoritma-paralel/
Hi. I’m Designer of Ansorpunya.blogspot.com. I’m graduate from Khairul Bariyyah Islamic Boarding School and Gunadarma University, Java Programmer, Pro Evolution Soccer Player, Dreamer, IELTS score Hunter, Scholarship Hunter, Writer and I am not sure who I’m actually. Just inspired to make things looks better and better.
0 komentar :
Posting Komentar