PENDAHULUAN
Dalam ilmu komputer,
sebuah algoritma paralel atau algoritma bersamaan, sebagai lawan berurutan
(atau serial) algoritma tradisional, merupakan 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. Sebagian
besar algoritma yang tersedia untuk menghitung pi (π), di sisi lain, tidak
dapat dengan mudah dibagi menjadi bagian-bagian paralel. Mereka membutuhkan
hasil dari langkah sebelumnya untuk secara efektif melanjutkan dengan langkah
berikutnya. Masalah seperti ini disebut masalah inheren serial. Iteratif metode
numerik, seperti metode Newton atau masalah tiga-badan, juga algoritma yang
secara inheren serial.
TEORI
Pengertian
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
throughput yang sama. 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.
ANALISIS
Algoritma pararel memiliki
banyak desain atau model yaitu SISD, MISD, SIMD, dan MIMD. Untuk setiap model
yang ada memiliki kelebihan kekurangan dan mempunyai fungsi masing - masing. Menurut
saya model MIMD merupakan model yang paling efisien karena memiliki banyak
prosessor yang bisa mengeksekusi instruksi yang berbeda sehingga tidak terjadi
penumpukan atau antrian instruksi.
REFERENSI
