1. 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. Beberapa
masalah yang sangat sulit untuk memparalelkan, meskipun mereka rekursif. Salah
satu contohnya adalah pencarian mendalam-pertama grafik.
Algoritma paralel berharga karena perbaikan
substansial dalam sistem multiprocessing dan munculnya prosesor multi-core.
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.
2. TEORI
Algoritma Paralel
adalah algoritma yang dapat dieksekusi sepotong pada waktu pada banyak
perangkat pengolahan yang berbeda, 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
eknik 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.
3. ANALISA
Langkah-langkah
yang diambil oleh sebuah algoritma dibedakan ke dalam dua jenis yaitu:
a. Computational
step
Sebuah
computational step adalah sebuah operasi aritmetika atau operasi logika yang
dilakukan terhadap sebuah data dalam sebuah prosesor.
b. Routing step.
Pada routing
step, sebuah data akan melakukan perjalanan dari satu prosesor ke prosesor lain
melalui shared memory atau melalui jaringan komunikasi. RUNNING TIME (COUNTING
STEP & SPEED UP) Analisa Algoritma Sekuensial Pada Algoritma Sekuensial
instruksi dikerjakan secara berurutan baris perbaris mulai dari baris pertama
hingga baris terakhir, tanpa ada loncatan atau perulangan. Adapun ciri dari
algoritma Sekuensial yaitu:
a. Tiap instruksi
dikerjakan satu per satu.
b. Tiap instruksi
dilaksanakan tepat sekali, tidak ada instruksi yang diulang.
Dalam Arsitektur
Komputer,penerapan algoritma sekuensial termasuk dalam kelompok komputer SISD
(berdasarkan klasifikasi Flynn) yaitu hanya mempunyai satu unit pengendali
untuk menentukan instruksi yang akan dieksekusi. Analisa Algoritma Paralel Pada
Komputer Pararel (Algoritma Pararel) terdapat lebih dari satu elemen pemrosesan
yang dikendalikan oleh sebuah unit pengendali yang sama. Pada dasarnya
aktivitas sebuah prosesor pada komputer paralel adalah sama dengan aktivitas
sebuah prosesor pada komputer sekuensial. Tiap prosesor membaca (read) data
dari memori, memprosesnya dan menuliskannya (write) kembali ke memori namun
jumlah procesor dapat lebih dari satu (multiprocessor). Aktivitas komputasi ini
dikerjakan oleh seluruh prosesor secara paralel. Running Time ditentukan dengan
2 cara, yaitu:
1. Counting Step
2. Speedup Contoh
Counting Step Terdapat sebuah file komputer dengan n entri berbeda. Pada file
tersebut akan diperiksa apakah x terdapat di dalamnya.
Dengan algoritma
sekuensial,keadaan terburuknya (worst case) untuk menemukan x membutuhkan n
langkah, dimana tiap langkah adalah membandingkan x dengan sebuah entri pada
file. Keadaan terburuk terjadi jika x ternyata sama dengan entri terakhir pada
file atau x tidak terdapat pada file tersebut.
Dengan EREW SM
SIMD (Exclusive Read Exclusive Write Shared Memory SIMD) komputer dengan N
prosesor, dimana N n, pada worst casenya (keadaan terburuk) dibutuhkan log N +
n/N langkah. Dimana:
N: Jumlah N
processor (banyaknya processor)
N: Jumlah n
langkah (banyaknya langkah)
Misalkan P1, P2,…
PN prosesor-prosesor pada EREW SM SIMD komputer tersebut. Proses pencarian
entri yang sama dengan x adalah:
-Broadcasting, x
dikomunikasikan pada semua prosesor dengan cara:
1. P1 membaca x
dan mengkomunikasikan dengan P2.
2. P1 dan P2
secara simultan mengkomunikasikan x dengan P3 dan P4
3. P1, P2, P3 dan
P4 secara simultan meng-komunikasikan x dengan P5, P6, P7 dan P8.
Dan seterusnya
hingga semua prosesor mengenal x. Proses ini dilakukan dalam log N langkah.
-Searching, File dimana x akan dicari dibagi ke dalam sub file dan secara
simultan dilakukan pencarian oleh prosesor-prosesor:
P1 mencari pada
n/N entri pertama,
P2 mencari pada
n/N entri kedua,
P3 mencari pada
n/N entri ketiga,
PN mencari pada
n/N entri ke-N.
Proses ini
membutuhkan n/N langkah.
Jadi total
langkah yang dibutuhkan oleh algoritma tersebut adalah: log N + n/N langkah.
Contoh Speedup –
Dari contoh Counting step tadi
Running time
proses searching dengan mesin sekuensial adalah 0(n).
Running time dari
proses searching pada komputer EREW SM SIMD adalah 0(n/N).
Jadi speedup =
0(N).
