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, penjelasan singkat adalah sebagai berikut:
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, Oracle Corporation, dan masih banyak lagi.
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. Teknik pembangunan algoritma paralel dapat dibedakan sebagai berikut :
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.
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.
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.
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.
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.
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.
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.
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, Oracle Corporation, dan masih banyak lagi.
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. Teknik pembangunan algoritma paralel dapat dibedakan sebagai berikut :
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.
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.
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.
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.
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.
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.
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.
.jpg){kind=small}
Postingan
0 komentar:
Posting Komentar