UNIVERSITAS GUNADARMA
FAKULTAS TEKNOLOGI
INDUSTRI
MAKALAH TUGAS ALGORITMA PARALEL
Nama :
Mustika Ningrum 54410874
Jurusan :
Teknik Informatika
Kelas : 4ia19
Tugas : Softkill ke 2
Dosen : Kuwat Setiyanto
Diajukan Guna Melengkapi Sebagian Syarat
UNTUK MENCAPAI JENJANG SETARA SARJANA
MUDA
Universitas Gunadarma
2014
BAB
I
PENDAHULUAN
1.1 LATAR BELAKANG
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 maka dari itu dibutuhkan
penyelesain yang koknrit yaitu dengan melakukan pemecahan masalah dengan 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.
1.2 TUJUAN
UTAMA
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.
Analogi yang paling gampang adalah, bila anda dapat merebus air sambil
memotong-motong bawang saat anda akan memasak, waktu yang anda butuhkan akan
lebih sedikit dibandingkan bila anda mengerjakan hal tersebut secara berurutan
(serial). Atau waktu yg anda butuhkan memotong bawang akan lebih sedikit jika
anda kerjakan berdua.
Performa dalam pemrograman paralel diukur dari berapa
banyak peningkatan
kecepatan (speed up) yang diperoleh dalam menggunakan tehnik
paralel. Secara informal, bila anda memotong bawang sendirian membutuhkan waktu
1 jam dan dengan bantuan teman, berdua anda bisa melakukannya dalam 1/2 jam
maka anda memperoleh peningkatan kecepatan sebanyak 2 kali.
1.1.1. TEORI
Pemrograman
paralel adalah teknik pemrograman komputer yang memungkinkan eksekusi perintah/operasi secara bersamaan
(komputasi
paralel), baik dalam komputer dengan satu (prosesor tunggal)
ataupun banyak (prosesor ganda dengan mesin paralel) CPU. Bila
komputer yang digunakan secara bersamaan tersebut dilakukan oleh
komputer-komputer terpisah yang terhubung dalam suatu jaringan komputer lebih sering istilah yang digunakan adalah sistem terdistribusi(distributed computing).Komputasi paralel adalah
salah satu teknik melakukan komputasi secara
bersamaan dengan memanfaatkan beberapakomputer 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.
Kasus kedua umum ditemui di kalkulasi numerik untukmenyelesaikan persamaanmatematis dibidang fisika (fisikakomputasi), kimia (kimia komputasi) dll. Untuk melakukan aneka jenis komputasi paralel ini
diperlukan infrastruktur mesin paralel yang terdiri dari banyak komputeryang
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.
1.1.2. Desain & Analisis
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.
DAFTAR
PUSTAKA
Rancangan dan Implementasi Sistem Keamanan pada Parallel Prosessing Komputasi dengan menggunakan PC Cluster, MUSTIKA NINGRUM 54410874
http://www.beritanet.com
http://www.ilmukomputer.com
http://www.lam-mpi.org
.