Algoritma Paralel

BAB I

PENDAHULUAN

1.1     1.1 Latar Belakang Masalah

            Dalam perkembangan teknologi saat ini, untuk memperoleh suatu penjelasan tentang Algoritma Paralel. Dimana 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.

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

1.2       Batasan Masalah

            Dalam penulisan ini hanya membahas tentang Pada ilmu computer, algoritma parallel atau algoritma konkuren, ini merupakan kebalikan dari algoritma tradisional sekuensial (serial). Beberapa algoritma mudah untuk dibagi ke dalam cara ini. Contohnya, memisahkan pekerjaan dengan mengecek semua nomor dari satu sampai 100000 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.

1.3       Tujuan Penulisan

Melakukan eksperimen untuk mengetahui kinerja algoritma paralel pada prosesor multicore. Eksperimen akan menerapkan algoritma paralel pada operasi perkalian matriks dan pengurutan data (sorting) dengan menggunakan Teknik dan Strategi Pembangunan Algoritma Paralel.

1.4       Metode Penulisan

Dalam pembuatan komputasi modern, penulis menggunakan beberapa tahapan-tahapan diantaranya:

1.      Perencanaan

Pada tahap ini, penulis menentukan konsep dari algoritma pararel.

2.      Analisa     

Pada tahap ini, penulis mencari informasi tentang algoritma paralel melalui media internet dan media informasi lainnya seperti buku.

1.5       Sistematika Penulisan

            Dalam penulisan ini, penulis menyajikan sistematika penulisan yang di bagi dalam 4 bab, yaitu :

bab I :           pendahuluan

Berisi tentang latar belakang masalah, batasan masalah, tujuan penulisan, metode penulisan dan sistematika penulisan.

BAB II            :          landasan teori

Menjelaskan tentang komputasi modern, jenis-jenis komputasi modern serta sejarah komputasi modern.

BAB III :        PEMBAHASAN MASALAH

Menjelaskan tentang pengaruh komputasi modern pada pengalaman pribadi serta termasuk masyarakat.

BAB IV :        PENUTUP

Menjelaskan tentang kesimpulan dan saran dari seluruh penulisan yang telah dijelaskan pada bab-bab sebelumnya beserta referensi.

BAB II

landasan Teori

2.1. Pengertian Algoritma Paralel

 Algoritma paralel 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 mengecek semua nomor dari 1 sampai 100000 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.

2.2. Platform Algoritma Paralel

·         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.

·         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, implementasi efisien dari  MPI.

·         CUDA (Compute Unified Device Architecture)

CUDA (Compute Unified Device Architecture) merupakan platform parallel computing dan model pemrograman yang telah dibuat oleh NVIDIA dan diimplementasikan oleh GPU (Graphic Processing Unit). CUDA memberikan akses pengembangan untuk kumpulan visual instruction dan ingatan dari parallel computasional elemen CUDA GPU.

2.3. Teknik Pembangunan Algoritma Paralel       

·         Paralelisme 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.

·         Partisi Data

Merupakan teknik khusus dari Paralelisme Data, dimana data disebar ke dalam memori-memori lokal multikomputer. Sebuah proses paralel dimana ditugaskan untuk mengoperasikan masing-masing 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.

·         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.

·         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.

·         Synchronization Delay

Ketika proses paralel disinkronkan, berarti bahwa suatu proses 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.

2.4       Desain

·        SISD Single Instruction Stream dan 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 dan 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.

SIMD dibagi menjadi beberapa bentuk lagi yaitu :

1.     Exclusive-Read, Exclusive-Write (EREW) SM SIMD

2.     Concurent-Read, Exclusive-Write (CREW) SM SIMD

3.     Exclusive-Read, Concurrent-Write (ERCW) SM SIMD

4.     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 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.

2.5       Implementasi Algoritma Paralel

            Dalam merancang suatu algoritma paralel kita harus mempertimbangkan pula hal-hal yang dapat mengurangi kinerja program paralel. Hal-hal tersebut adalah : 

·         Memory Contention

Eksekusi prosesor tertunda ketika prosesor menunggu hak ases ke sel memori yang sedang dipergunakan oleh  prosesor lain. Problem ini muncul pada arsitektur multiprosesor dengan memori bersama.

·         Excessive Sequential Code

Pada beberapa algoritma paralel, akan terdapat kode sekuensial murni dimana tipe tertentu dari operasi pusat dibentuk, seperti misalnya pada proses inisialisasi. Dalam beberapa algoritma, kode sekuensial ini dapat mengurangi keseluruhan speedup yang dapat dicapai.

·         Process Creation Time

Pembentukan proses paralel akan membutuhkan waktu eksekusi. Jika proses yang dibentuk relative berjalan dalam waktu yang relatif lebih singkat dibandingkan dengan waktu pembentukan proses itu sendiri, maka overhead pembuatan akan lebih besar dibandingkan dengan waktu eksekusi paralel algoritma.

·         Communication Delay

Overhead ini muncul hanya pada multikomputer. Hal ini disebabkan karena interaksi antar prosesor melalui jaringan komunikasi. Dalam beberapa kasus, komunikasi antar dua prosesor mungkin melibatkan beberapa prosesor antara dalam jaringan komunikasi. Jumlah waktu tunda komunikasi dapat menurunkan kinerja beberapa algoritma paralel.

·       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.

BAB III

pembahasan masalah

Pada bab ini, penulis membuat salah satu dampak dari adanya menyelesaikan masalah numerik, karena masalah numerik merupakan salah satu masalah yang memerlukan kecepatan komputasi yang sangat tinggi.

3.1.            Dampak Adanya Komputasi Modern

            Salah satu dampak dari adanya Algoritma paralel 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.

           

3.2       Implementasi Algoritma Paralel Dalam Kehidupan Sehari-hari

                Dalam kehidupan sehari-hari dimana pengimplementasian Algoritma Paralel diterapkan pada teknologi mobile computing. Sekalipun didukung oleh teknologi prosesor yang berkembang sangat pesat,  komputer sekuensial tetap akan mengalami keterbatasan dalam hal kecepatan pemrosesannya. Hal ini menyebabkan lahirnya konsep keparalelan (parallelism) untuk menangani masalah dan aplikasi yang membutuhkan kecepatan pemrosesan yang sangat tinggi, seperti misalnya prakiraan cuaca, simulasi pada reaksi kimia, perhitungan aerodinamika dan lain-lain.

            Konsep keparalelan itu sendiri dapat ditinjau dari aspek design mesin paralel, perkembangan bahasa pemrograman paralel atau dari aspek pembangunan dan analisis algoritma paralel. Algoritma paralel itu sendiri lebih banyak difokuskan kepada algoritma untuk menyelesaikan masalah numerik, karena masalah numerik merupakan salah satu masalah yang memerlukan kecepatan komputasi yang sangat tinggi.

            Untuk dapat mengadaptasi suatu algoritma sekuensial ke dalam algoritma paralel, terlebih dahulu harus dipelajari mengenai konsep pemrosesan paralel dan bagaimana proses-proses dapat berlangsung secara paralel. Konsep pemrosesan paralel secara tidak langsung melibatkan studi mengenai aristektur komputer paralel. Dimulai dengan pengelompokkan Flynn, Arsitektur Komputer Paralel, Konsep Paralelisme, Pembangunan Algoritma Paralel, Konsep Proses dan Proses Komunikasi .

BAB IV

PENUTUP

4.1. Kesimpulan

Berdasarkan uraian yang ditulis pada bab-bab sebelumnya dapat diambil kesimpulan bahwa bahasan diatas, dapat diambil sebuah kesimpulan bahwa ilmu Algoritma paralel cenderung digunakan untuk menyelesaikan masalah numerik, karena masalah numerik merupakan salah satu masalah yang memerlukan kecepatan komputasi yang sangat tinggi. Untuk dapat mengadaptasi suatu algoritma sekuensial ke dalam algoritma paralel, terlebih dahulu harus dipelajari mengenai konsep pemrosesan paralel dan bagaimana proses-proses dapat berlangsung secara paralel.

Saran

Dari tinjau aspek diatas dimana perkembangan Algoritma paralel itu sendiri lebih banyak difokuskan kepada algoritma untuk menyelesaikan masalah numerik, karena masalah numerik merupakan salah satu masalah yang memerlukan kecepatan komputasi yang sangat tinggi termasuk dalam kehidupan sehari-hari seperti untuk menangani masalah dan aplikasi yang membutuhkan kecepatan pemrosesan yang sangat tinggi, seperti misalnya prakiraan cuaca, simulasi pada reaksi kmia, perhitungan aerodinamika dan lain-lain.

.

Referensi :

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

http://vanderdrago.blogspot.com/2013/05/algoritma-paralel.html

http://fikrilookup.wordpress.com/2013/05/12/algoritma-paralel/

Posted in: