Parallel Computing

A. DEFINISI

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. Kasus kedua umum ditemui di kalkulasi numerik untuk menyelesaikan persamaan matematis di bidang fisika (fisika komputasi), kimia (kimia komputasi) dll.

Tujuan utama komputasi paralel adalah untuk mempersingkat waktu eksekusi program yang menggunakan komputasi serial. Beberapa alasan lain yang menjadikan suatu program menggunakan komputasi paralel antara lain: 

1. Untuk komputasi yang sangat kompleks, terkadang sumber daya (resource) yang ada sekarang belum cukup mampu untuk mendukung penyelesaian terhadap permasalahan secara cepat. 
2. Adanya keterbatasan memori pada mesin untuk komputasi serial. 
3. Adanya sumber daya non-lokal yang dapat digunakan melalui jaringan lokal atau internet. 
4. Penghematan biaya pengadaan perangkat keras, dengan menggunakan beberapa mesin yang murah sebagai alternatif penggunaan satu mesin yang bagus tapi mahal, walaupun menggunakan Processor (Multicore).

B. PENGGUNAAN PARALLEL COMPUTING

Penggunaan komputasi paralel sebagai solusi untuk mempersingkat waktu yang dibutuhkan, namun untuk eksekusi program mempunyai beberapa hambatan. Hambatan-hambatan tersebut antara lain adalah: 

1. Hukum Amdahl, yaitu percepatan waktu eksekusi program dengan menggunakan komputasi paralel tidak akan pernah mencapai kesempurnaan karena selalu ada bagian program yang harus dieksekusi secara serial. 
2. Hambatan yang diakibatkan karena beban jaringan, dalam eksekusi program secara paralel, prosesor yang berada di mesin yang berbeda memerlukan pertukaran data melalui jaringan. Untuk program yang dibagi menjadi task-task membutuhkan sinkronisasi, network latency (keterlambatan jaringan) menjadi masalah utama. Permasalahan ini muncul karena ketika suatu task membutuhkan data dari task yang lain, bagian ini dikirimkan melalui jaringan dimana kecepatan transfer data kurang dari kecepatan prosesor yang mengeksekusi instruksi task tersebut. Hal ini menyebabkan task tersebut harus menunggu sampai data tiba terlebih dahulu, sebelum mengeksekusi instruksi selanjutnya. 
3. Hambatan yang terkait dengan beban waktu untuk inisialisasi task, terminasi task, dan sinkronisasi.

Dalam sebuah artikel yang direferensikan oleh Flynn, Dalam mendesain sebuah komputer di karakteristikkan oleh perjalanan (alur) dari instruksi-instruksi yang akan diselesaikan oleh suatu arsitektur komputer. Taksonomi ini diklasifikasikan yang disesuaikan melalui perjalanan dari gabungan instruksi dan data. Taksonomi ini menghasilkan empat kemungkinan kombinasi dari pengoperasian instruksi. Yang terlihat pada tabel dibawah ini:

Keterangan:

1. SISD (Single Instruction, Single Data), Pada arsitektur ini adalah arsitektur yang mewakili komputer serial, dimana hanya ada satu prosesor dan satu aliran masukan data (memori), sehingga hanya ada satu task yang dapat dieksekusi pada suatu waktu. Arsitektur Von-Neumann termasuk dalam jenis ini. 
2. SIMD (Single Instruction, Multiple Data). Pada arsitektur ini, eksekusi sebuah instruksi akan dilakukan bersamaan oleh beberapa prosesor, dimana sebuah prosesor dapat menggunakan data yang berbeda dengan prsesor lain. 
3. MISD (Multiple Instruction, Single Data), Pada arsitektur ini, berbagai instruksi akan di eksekusi secara bersamaan oleh beberapa prosesor dengan menggunakan data yang sama. 
4. MIMD (Multiple Instruction, Multiple Data), Pada arsitektur ini, berbagai instruksi dapat dieksekusi oleh beberapa prosesor dimana masing-masing prosesor dapat menggunakan data yang berbeda.

C. PARADIGMA PEMROGRAMAN PARALEL

Secara umum, paradigma komputasi paralel dapat dibagi menjadi dua jenis, yaitu paralelisme implisit dan paralelisme eksplisit. Paralelisme implisit merupakan suatu pendekatan dimana penulis program (programmer) tidak perlu memperhatikan masalah pembagian task ke beberapa prosesor dan memori beserta sinkronisasinya. Pembagian task dan sinkronisasi ditangani sepenuhnya oleh sistem dibawah program (sistem operasi atau mesin virtual) atau compiler. Berbeda dengan paradigma paralelisme eksplisit harus memperhatikan dan menangani masalah pembagian task dan komunikasinya. Komunikasi antar dua atau lebih task pada umumnya dilakukan dengan menggunakan shared-memory atau message-passing.

• Shared memory. Pada model komunikasi ini, task-task menggunakan memori (address space) yang sama, dimana masing-masing task dapat menulis atau membaca secara asinkron. 
• Message Passing. Pada model komunikasi ini, setiap task mempunyai memori (address space) lokal masing-masing, dan paradigma yang digunakan adalah parallelisme eksplisit. Contoh sumber daya komputasi yang cocok menggunakan pemodelan ini adalah beberapa workstation yang dijadikan cluster.

D. MODEL PEMROGRAMAN

Untuk mempermudah pengembangan program di lingkungan komputasi paralel, dikembangkan model pemrograman yang menjadi cara untuk menggambarkan struktur algoritma paralel, sesuai dengan pilihan metode pemetaan proses dan dekomposisi data. 6Pada tugas akhir ini model pemrograman yang digunakan yaitu model Data- Paralel . Task dipetakan secara statik pada masing-masing proses dan masing-masing proses tersebut melakukan operasi yang sama terhadap data yang berbeda secara bersama-sama (concurent). Karena setiap task melakukan operasi yang sama, maka metode dekomposisi yang digunakan adalah dekomposisi data (Data Decomposition).

E. CLUSTER

Cluster adalah kumpulan komputer yang terhubung melalui interkoneksi jaringan. Setiap node pada cluster bisa sebagai sebuah server, komputer-personal atau komputer yang memiliki dua atau lebih prosesor yang terintegrasi sebagai bagian dari sistem multiprosesor. Setiap node adalah sebuah komputer yang memiliki sistem input/output (I/O) dan sistem operasi sendiri. Ketika semua node pada sebuah cluster memiliki arsitektur yang sama dan beroperasi pada sistem operasi yang sama maka cluster ini disebut sebagai cluster homogen (homogeneous cluster), Begitu juga sebaliknya jika cluster dengan sistem operasi maupun arsitektur yang berbeda disebut cluster heterogen (heterogeneous cluster).

F. WAKTU EKSEKUSI PROGRAM PARALEL

Waktu eksekusi program paralel adalah lamanya waktu sejak dimulai sampai berakhirnya ekeskusi program paralel. Secara praktis, waktu ini dimulai sejak input untuk memulai program dimasukkan oleh user sampai dengan konfirmasi bahwa program telah selesai muncul ke layar. Dalam eksekusi serial, waktu total eksekusi program hanyalah waktu eksekusi komputasi program tersebut. Sedangkan dalam eksekusi paralel, waktu total eksekusi adalah waktu komputasi program tersebut ditambah dengan waktu untuk melakukan komunikasi antar proses yang bisa berupa pertukaran data maupun sinkronisasi, Jika waktu keseluruhan eksekusi program paralel dilambangkan dengan t paralel maka persamaan untuk waktu eksekusi program paralel adalah:

G. TEORI PERKALIAN MATRIKS

Perkalian antara Matriks A[M][N] yang terdiri dari M baris dan N kolom dengan Matriks (B[N][L]) yang terdiri dari N baris dan L kolom akan menghasilkan Matriks C[M][L] dengan M baris dan L kolom. Setiap elemen Matriks C dihitung berdasarkan persamaan berikut:

Keterangan:

Untuk setiap elemen dari Matriks C adalah hasil dari perkalian bagian luar dari baris pada Matriks A dengan kolom bagian terdalam dari Matriks B, dimana nilai i lebih kecil dari atau sama dengan M dan nilai j lebih kecil dari atau sama dengan L.

Jika pada kasus tugas akhir ini menggunakan matriks persegi dengan ukuran Matriks (N x N), dimana N adalah banyaknya baris dan kolom pada setiap matriks adalah sama, maka kompleksitas matriks sekuensial sebesar Ο(N3).

Referensi:

https://id.wikipedia.org/wiki/Komputasi_paralel

http://raharjo.staff.telkomuniversity.ac.id/files/2015/08/Week1.2.pdf

http://elib.unikom.ac.id/files/disk1/367/jbptunikompp-gdl-syahrilnas-18320-3-babii.pdf