ALGORITMA PARALEL

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.llnl.gov/computing/tutorials/parallel_comp

http://www.lam-mpi.org

www.en.wikipedia.org

.