NAMA : Cintya Elsa Triani
KELAS : 4IA19
NPM : 51410597
ALAMAT BLOG : smartwomenn.blogspot.com
DOSEN : KUWAT S.
PENDAHULUAN
Pada
awalnya kata algorisma adalah istilah yang merujuk kepada aturan-aturan
aritmetis untuk menyelesaikan persoalan dengan menggunakan bilangan numerik
arab, namun pada abad ke-18 istilah ini telah berkembang menjadi algoritma
suatu urutan langkah atau prosedur yang jelas dan diperlukan untuk
menyelesaikan suatu permasalahan.
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 menja
di 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
Langkah-langkah yang diambil oleh sebuah algoritma dibedakan
ke dalam dua jenis yaitu :
·
Computational
step
Sebuah computational step adalah
sebuah operasi aritmetika atau operasi logika yang dilakukan terhadap sebuah
data dalam sebuah prosesor.
·
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
:
1. Tiap instruksi dikerjakan satu per
satu.
2. 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 (multi processor). Aktivitas komputasi ini
dikerjakan oleh seluruh prosesor secara paralel.
Running Time ditentukan dengan 2
cara, yaitu:
·
Counting
Step
·
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).
SUMBER:
http://fikrilookup.wordpress.com/2013/05/12/algoritma-paralel/
http://fikrilookup.wordpress.com/2013/05/12/algoritma-paralel/
http://prezi.com/ufzritj1dzya/analisa-algoritma-sekuensial/
