algoritma parallel

NAMA                 : OKKE DEWI ASOKA

KELAS                : 4IA19

NPM                    : 55410258

ALAMAT BLOG : okkedewi.blogspot.com

DOSEN               : KUWAT S.

MATERI             : ALGORITMA PARALLEL

1. PENDAHULUAN

Algoritma parallel merupakan suatu metode penyelesaian bagi permasalahan tertentu yang dirancang untuk computer parallel. Simulasi diaplikasikan dalam operasi perkalian matriks dan matriks dengan vector dalam algoritma dan prosedur PASCAL.

Algoritma parallel ini dirancang untuk diproses pada computer SM SISD (Shares Memory, Single Instruction stream – Single Data stream) dengan model kubus terhubung dan pohon terhubung. Difokuskan system computer yang digunakan saat ini masih satu personil computer dengan asumsi memori yang dipakai adalah virtual memory dengan beberapa address.

2. TEORI PENJELASAN

A. Pengertian Algoritma Parallel   

Algoritma parallel atau algoritma konkuren, ini merupakan kebalikan dari algoritma tradisional sekuensial (serial). Algoritma parallel merupakan algoritma yang dapat dieksekusi dalam satu waktu pada banyak perangkat processing yang berbeda, dan pada akhirnya akan digabungkan kembali untuk mendapatkan hasil yang benar. Beberapa algoritma mudah untuk dibagi ke dalam cara ini. Contohnya, memisahkan pekerjaan dengan mengcek semua nomor dari satu sampat 100ribu untuk melihat pernyataan mana yang akan dijadikan landasan untuk menetapkan subset dari nomor setiap prosesor yang ada, dan kemudian menaruh data dengan hasil yang akan dkembalikan bersama-sama.

Algoritma ini juga telah diterapkan untuk algoritma seperti rubik kubus dan dekripsi hash. Untuk penjelasan lebih lanjut dari algoritma parallel ini, perlu diketahui terdapat beberapa platform yang biasa digunakan dalam pemrograman parallel, yaitu OpenMp, MPI, CUDA, dan lain sebagainya.

Di bawah ini akan dijelaskan mengenai platform tersebut :

 
1.OpenMP
OpenMP yaitu API yang mendukung multiplatform untuk pemrograman multiprocessing shared memory pada C, C++, dan Fortran, di semua arsitektur prosesor dan OS termasuk platform Solaris, AIX, HP-UX, GNU/Linux. Max OS X, dan Windows. Ini terdiri dari kumpulan compiler directive, library routines, dan environment variable yang akan membuat run time pada semua keadaan. OpenMP merupakan suatu teknologi nonprofit yang diatur oleh OpenMP Architecture Review Board (or OpenMP ARB) termasuk didalamnyaa vendor hardware dan software yaitu AMD, IBM, Intel, Cray, HP, Fujitsu, Nvidia, NEC, Microsoft, Texas Instruments dll.

2. MPI (Message Passing Interface) .

MPI (Message Passing Interface) yaitu suatu standard dan message passing interface partabel system yang didesain oleh grup penelitian dari akademi dan industry untuk mengembangkan fungsi dan macam-macam dari computer parallel. Standar ini mendifinisikan sintaks dan semantic dari core library routine yang berguna untuk memperbesar jangkauan kepada user menulis portable program message passing pada Fortran 77 dan bahasa C. Bebedapa keebaikan dirasakan dan implementasi efisien dari  MPI termasuk beberapa free da nada pada domain public. Ini dipupuk kedalam pengembangan dalam parallel industry software, dan kemajuan portable development,

dan kemampuan skala lebih besari aplikasi parallel.

3. CUDA (Compute Unified Device Architecture).

CUDA (Compute Unified Device Architecture) merupakan platform parallel computing dan model pemrograman yang telah dibuat oleh NVIDIDA dan diimplementasikan oleh GPU(Graphic Processing Unit). CUDA memberikan akses pengembangan untuk kumpulan visual instruction dan ingatan dari parallel computasional elemen CUDA GPU. Dalam beberapa kasus, algoritma sekuensial dengan mudah dapat diadaptasi ke dalam lingkungan paralel. Namun dalam kebanyakan kasus, problem komputasi harus dianalisa ulang dan menghasilkan algoritma paralel yang baru. Terdapat beberapa penelitian mengenai perancangan algoritma paralel untuk problem-problem praktis seperti pengurutan, pemrosesan geraf, solusi untuk persamaan lanjar, solusi untuk persamaan diferensial, dan untuk simulasi.

B. Teknik Dasar Algoritma Parallel

Teknik pembangunan algoritma paralel dapat dibedakan sebagai berikut :

1.Paralisme Data

Teknik paralelisme data merupakan teknik yang paling banyak digunakan dalam program paralel. Teknik ini lahir dari penelitian bahwa aplikasi utama komputasi paralel adalah dalam bidang sain dan engineer, yang umumnya melibatkan array multi-dimensi yang sangat besar. Dalam program sekuensial biasa, array ini dimanipulasi dengan mempergunakan perulangan bersarang untuk mendapatkan hasil. Kebanyakan program paralel dibentuk dengan mengatur ulang algoritma sekuensial agar perulangan bersarang tersebut dapat dilaksanakan secara paralel. Paralelisme data menunjukkan bahwa basis data dipergunakan sebagai dasar untuk membentuk aktifitas paralel, dimana bagian yang berbeda dari basis data akan diproses secara paralel. Dengan kata lain paralelisme dalam program ini dibentuk dari penerapan operasi-operasi yang sama ke bagian array data yang berbeda. Prinsip paralelisme data ini berlaku untuk

pemrograman multiprosesor dan multikomputer.

2.Partisi Data

Merupakan teknik khusus dari Paralelisme Data, dimana data disebar ke dalam memori-memori lokal multikomputer. Sebuah proses paralel kemudian ditugaskan untuk mengoperasikan masingmasing bagian data. Proses tersebut harus terdapat dalam lokal memori yang sama dengan bagian data, karena itu proses dapat mengakses data tersebut secara lokal. Untuk memperoleh kinerja yang baik, setiap proses harus memperhatikan variabel-variabel dan data-data lokalnya masing-masing. Jika suatu proses membutuhkan akses data yang terdapat dalam remote memori, maka hal ini dapat dilakukan melalui jaringan message passing yang menghubungkan prosesor-prosesor. Karena komunikasi antar prosesor ini menyebabkan terjadinya waktu tunda, maka messsage passing ini sebaiknya dilakukan dalam frekuensi yang relatif kecil. Dapat disimpulkan bahwa tujuan dari partisi data adalah untuk mereduksi waktu tunda yang diakibatkan komunikasi messsage passing antar prosesor. Algoritma paralel mengatur agar setiap proses dapat melakukan komputasi dengan local data masing-masing.

3.Algoritma Relaksasi

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.

4.Paralelisme Sinkron

Aplikasi praktis dari komputasi paralel adalah untuk problem yang melibatkan array multi-dimensi yang sangat besar. Problem tersebut mempunyai peluang yang baik untuk paralelisme data karena elemen yang berbeda dalam array dapat diproses secara paralel. Teknik komputasi numerik pada array ini biasanya iteratif, dan setiap iterasi akan mempengaruhi iterasi berikutnya untuk menuju solusi akhir. Misalnya saja untuk solusi persamaan numerik pada sistem yang besar. Umumnya, setiap iterasi mempergunakan data yang dihasilkan oleh iterasi sebelumnya dan program akhirnya menuju suatu solusi dengan akurasi yang dibutuhkan. Algoritma iterasi ini mempunyai peluang paralelisme pada setiap iterasinya. Beberapa proses parallel dapat dibentuk untuk bekerja pada array bagian yang berbeda. Namun setelah setiap iterasi, prosesproses harus disinkronkan, karena hasil yang diproduksi oleh satu proses dipergunakan oleh prosesproses lain pada

iterasi berikutnya.

Teknik pemrograman paralel seperti ini disebut paralelisme sinkron.

Contohnya adalah perhitungan numerik pada Metode Eliminasi Gauss. Pada paralelisme sinkron ini, struktur umum programnya biasanya terdiri dari perulangan FORALL yang akan membentuk sejumlah besar proses paralel untuk dioperasikan pada bagian array data yang berbeda. Setiap proses diulang dan disinkronkan pada akhir iterasi. Tujuan dari sinkronisasi ini adalah untuk meyakinkan bahwa seluruh proses telah menyelesaikan iterasi yang sedang berlangsung, sebelum terdapat suatu proses yang memulai iterasi berikutnya.

5.Komputasi Pipeline

Pada komputasi pipeline, data dialirkan melalui seluruh struktur proses, dimana masing-masing proses membentuk tahap-tahap tertentu dari keseluruhan komputasi . Algoritma ini dapat berjalan dengan baik pada multikomputer, karena adanya aliran data dan tidak banyak memerlukan akses ke data bersama. Contoh komputasi pipeline adalah teknik penyulihan mundur yang merupakan bagian dari metoda Eliminasi.

6.Synchronization Delay

Ketika proses paralel disinkronkan, berarti bahwa suatu proses akan harus menunggu proses lainnya. Dalam beberapa program paralel, jumlah waktu tunda ini dapat menyebabkan bottleneck dan mengurangi speedup keseluruhan. Load Imbalance Dalam beberapa program paralel, tugas komputasi dibangun secara dinamis dan tidak dapat diperkirakan sebelumnya. Karena itu harus selalu ditugaskan ke prosesor-prosesor sejalan dengan pembangunan tugas tersebut. Hal ini dapat menyebabkan suatu prosesor tidak bekerja (idle), sementara prosesor lainnya tidak dapat mengerjakan task yang ditugaskannya.

C.Contoh Software algoritma parallel

1. Komputasi Parallel

Komputer parallel adalah salah satu teknik melakukan komputasi secara bersamaan dengan memanfaatkan beberapa computer independen secara bersamaan.

2. Parallel Virtual Machine (PVM)

PVM (Parallel Virtual Machine) adalah paket software yang mendukung pengiriman pesan untuk komputasi parallel antar computer. PVM dapat berjalan diberbagai macam variasi UNIX ataupun windows dan telah portable untuk banyak arsitektur seperti PC, workstasion, multiprocessor dan supercomputer.

Komputasi Paralel dengan Parallel Virtual Machine (PVM)

            Komputasi  paralel   adalah   salah   satu   teknik  melakukan  komputasi  secara bersamaan dengan memanfaatkan beberapa komputer 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. Penggunaan komputasi parallel prosessing merupakan pilihan yang cukup handal untuk saat ini untuk pengolahan data yang besar dan banyak, hal ini apabila dibandingkan dengan membeli suatu super komputer yang harganya sangat mahal maka penggunaan komputasi parallel prosessing merupakan pilihan yang sangat tepat untuk pengolahan data tersebut. Aspek keamanan merupakan suatu aspek penting dalam sistem parallel prosessing komputasi ini, karena di dalam sistem akan banyak berkaitan dengan akses data, hak pengguna, keamanan data, keamanan jaringan terhadap peyerangan sesorang atau bahkan virus sehingga akan menghambat kinerja dari system komputasi ini.

Komputasi     parallel     adalah     melakukan     perhitungan  komputasi dengan

menggunakan 2 atau lebih CPU/Processor dalam suatu komputer yang sama atau komputer yang berbeda dimana dalam hal ini setiap instruksi dibagi kedalam beberapa instruksi kemudian dikirim ke processor yang terlibat komputasi dan dilakukan secara bersamaan. Untuk proses pembagian proses komputasi tersebut dilakukan oleh suatu software yang betugas untuk mengatur komputasi dalam hal makalah ini akan digunakan Parallel Virtual Machine (PVM).

            Pada sistem komputasi parallel terdiri dari beberapa unit prosesor dan beberapa unit memori. Ada dua teknik yang berbeda untuk mengakses data di unit memori, yaitu shared memory address dan message passing. Berdasarkan cara mengorganisasikan memori ini komputer paralel dibedakan menjadi shared memory parallel machine dan distributed memory parallel machine.

Prosesor dan memori ini didalam mesin paralel dapat dihubungkan (interkoneksi) secara statis maupun dinamis. Interkoneksi statis umumnya digunakan oleh distributed memory system (sistem memori terdistribusi). Sambungan langsung peer to peer digunakan untuk menghubungkan semua prosesor. Interkoneksi dinamis umumnya menggunakan switch untuk menghubungkan antar prosesor dan memori.

            Komunikasi data pada sistem paralel memori terdistribusi, memerlukan alat bantu komunikasi. Contoh alat bantu yang sering digunakan oleh sistem seperti PC Jaringan pada saat ini adalah standar PVM (Parallel Virtual Machine) yang bekerja diatas TCP/IP communication layer. Standar ini memerlukan fungsi remote access agar dapat menjalankan program pada masing-masing unit prosesor. Salah satu protocol yang dipergunakan pada komputasi parallel adalah Network File System (NFS), NFS adalah protokol yang dapat membagi sumber daya melalui jaringan. NFS dibuat untuk dapat independent dari jenis mesin, jenis sistem operasi, dan jenis protokol transport yang digunakan. Hal ini dilakukan dengan menggunakan RPC. NFS memperbolehkan user yang telah diijinkan untuk mengakses file-file yang berada di remote  host  seperti  mengakses  file  yang  berada  di  lokal.  Protokol  yang  digunakan protokol mount menentukan host remote dan jenis file sistem yang akan diakses dan menempatkan di suatu direktori, protokol NFS melakukan I/O pada remote file system. Protokol  mount  dan  protokol  NFS  bekerja  dengan  menggunakan RPC  dan  mengiri dengan protokol TCP dan UDP. Kegunaan dari NFS pada komputasi parallel adalah untuk melakukan sharing data sehingga setiap node slave dapat mengakses program yang sama pada node master.

3. BAB ANALISIS DAN STUDI KASUS

            Waktu yang diperlukan, biaya untuk memproses dan efisien penggunaan sumber daya. Kriteria berikutnya adalah biaya dari suatu algoritma parallel yang didefinisikan sebagai hasil kali dua ukuran sebelumnya, dinyatakan sebagai berikut : “ Biaya = running time parallel x jumlah prosessor yang digunakan” . Biaya sama dengan jumlah langkah yang dilaksanakan secara bersama prosesor dalam memecahkan masalah dengan kasus terburuk (worst case) pada algoritma. Diasumsikan sejumlah prosecor melaksanakan sejumlah langkah yang sama. Apabila tidak demikian, maka biayanya adalah batas atas jumlah langkah yang dilaksanakn. Untuk permasalahan berukuran n processor maka biaya diperkirakan sebagai fungsi dari n yaitu c(n) = p (n) x t(n), walapun demikian tergantung pula dari masing-masing persoaln yang dibahas. Pada bab ini juga akan menjelaskan contoh prinsip kerja dari algoritma pencarian nilai terbesar secara parallel dan algoritma penghitungan rerata secara parallel.

Contoh untuk algoritma pencarian nilai terbesar secara parallel :

A memiliki nilai = 1, 9, 2, 8, 3, 7, 4, 6, 5, 0

1.      i←0

2.      besar←false

3.      Selama (tidak  besar) dan (i<=N) kerjakan baris 4

4.      Jika (Data[i] > i+1) maka besar←true, jika tidak i←i+1

5.      Jika (besar) maka i adalah indeks dari data yang besar dan tampilkan.

Maka :

1.      i←0

2.      Besar←False

3.      Selama (tidak besar) dan (i<=N) kerjakan baris 4

4.      Jika (Data[1] > 9) maka besar←true, jika tidak i←9

5.      Jika (Besar) maka i adalah indeks dari data yang besar dan tampilkan.

6.      Maka akan memperoleh hasil 9

Contoh untuk algoritma penghitungan rerata secara parallel.

Contoh : A = 6, 3, 2, 9, 7

1.      i = 0

2.      for i=0 to i<=N do

3.      Data[i] +

Kondisi awal : daftar dari n >= 1 adalah element dari A[0 …(n-1)]

Kondisi akhir : Penjumlahan dari element di bagi jumlah element A dan simpan di A[0]

Variable global : n, A[0, …(n-1)],j

Begin

   Spawn(P₀, P₁, P₂, …, P_{[n/2 j-1]})

   For all P_i where 0 <= i <= [n/2]-1 do

               For j = o to [log n] -1 do

                           If i modulo 2^j = 0 and 2i + 2^j < n then

                                       A[2i]=A[2i]+A[2i+2^J]

                           End if

               End For

            End For

            A[0]/max[j]

End

4. KESIMPULAN

            Jadi Algoritma parallel itu merupakan suatu uruta-urutan logis dari suatu pernyataan yang ditekankan pada manipulasi elemen data yang dimiliki oleh satu atau lebih dari satu proses secara bersamaan dalam rangka menyelesaikan sebuah masalah yang biasanya dieksekusi dengan asumsi satu instruksi pada suatu waktu yamg dimana menggunakan komputer parallel yang memiliki banyak prosesor (multi prosesor) dan memiliki kemampuan pengolahan/pemrosesan parallel serta melakukan proses running time untuk suatu penilaian algoritma dalam analisa algoritma pengolahan parallel dimana waktu yang digunakan oleh sebuah algoritma untuk menyelesaikan masalah pada sebuah komputer parallel dihitung dari saat algoritma mulai hingga saat algoritma berhenti.

5. DAFTAR PUSTAKA

1.http://www.mcs.anl.gov/~itf/dbpp/
2.http://en.wikipedia.org/wiki/OpenMP
3.http://en.wikipedia.org/wiki/Parallel_algorithm

5.http://beringas19.blogspot.com/2013/05/algoritma-parallel.html