Komputasi Paralel

1. Overview

A. Apa itu komputasi paralel ?

 1) Serial Computing

            Secara tradisional, perangkat lunak telah ditulis untuk perhitungan serial :

            a) Masalah dipecah menjadi serangkaian intruksi yang terpisah.

            b) Instruksi dieksekusi berurutan satu demi satu.

            c) Di laksanakan pada satu prosesor.

            d) Hanya satu instruksi dapat dijalanka kapan saja.

 2) Parallel Computers

            Hampir semua komputer yang berdiri sendiri saat ini sejajar dengan perspekstif perangkat keras :

            a) Beberapa unit fungsional (L1 cache, L2 cache, cabang, prefetch, decode,floating-point,                        pemrosesan grafis (GPU), integer, dll).

            b) Beberapa pelaksanaan unit/core.

            c) Beberapa perangkat keras.

B. Kenapa harus menggunakan komputer paralel?

1) Dunia nyata secara paralel masif :

            a) Di dunia alami, banyak peristiwa kompleks dan saling terkait terjadi pada saat yang sama,                   namun dalam urutan temporal.

            b) Dibandingkan dengan komputasi serial, komputasi paralel jauh lebih cocok untuk                               pemodelan, simulasi dan pemahaman fenomena dunia nyata yang kompleks.

2) Alasan utama :

            a) Hemat waktu dan uang.

            b) Dapat memecahkan masalah yang besar dan kompleks.

            c) Menyediakan konsurensi.

            d) Keunggulan sumber daya non-lokal.

            e) Membuat penggunaan hardware paralel yang lebih baik.

C. Siapa yang menggunakan komputasi paralel ?

1) Teknik dan Sains

2) Industri dan Komersil

3) Aplikasi Global

2. Konsep dan Terminologi

A. Von Neuman Architecture

  Nama ahli matematika asal Hungaria yang pertama kali menulis persyaratan umum untuk komputer elektronik dalam makalahnya tahun 1945. Juga dikenal sebagai “komputer program tersimpan” baik instruksi program dan data disimpan dalam memori elektronik. Berbeda dari komputer sebelumnya yang diprogram melalui “kabel keras”.

B. Flynn’s Classical Taxonomy

  Salah satu klasifikasi yang lebih banyak digunakan sejak 1966 disebut Flynn’s Taxonomy. Flynn’s Taxonomy membedakan arsitektur komputer multi-prosesor berdasarkan bagaimana mereka dapat diklasifikasikan di sepanjang dua dimensi independen dari instruction Stream dan Data Stream. Masing-masing dimensi ini hanya dapat memiliki satu dari dua status yang mungkin tunggal atau banyak.

  Matriks dibawah ini mendefinisikan 4 klasifikasi yang mungkin menurut Flynn:

a) Single Instruction, Single Data (SISD) :

1) Komputer Serial

2) Single Instruction : Hanya satu aliran instruksi yang dijalankan oleh CPU selama satu siklus satu jam.

3) Single Data : Hanya satu aliran data yang digunakan sebagai input selama satu siklus satu jam.

b) Single Instruction, Multiple data (SIMD) :

1) Sebuah jenis komputer paralel.

2) Single Instruction : Semua unit pemrosesan menjalankan instruksi yang sama pada setiap siklus clock yang diberikan.

3) Multiple Data : Setiap unit pemrosesan dapat beroperasi pada elemen data yang berbeda.

c) Multiple Instruction, Single Data (MISD) :

1) Sebuah jenis komputer paralel.

2) Multiple Instruction : Setiap unit pemrosesan beroperasi pada data secara independen melalui aliran instruksi terpisah.

3) Single Data : Aliran data tunggal dimasukkan ke dalam beberapa unit pemrosesan.

d) Multiple Instruction, Multiple Data (MIMD) :

1) Sebuah jenis komputer paralel

2) Multiple Instruction : Setiap prosesor dapat menjalankan aliran instruksi yang     berbeda.

3) Multiple Data : Setiap prosesor dapat bekerja dengan aliran data yang berbeda.

e) Beberapa terminologi paralel umum :

1) Supercomputing / High Performance Computing (HPC).

2) Node.

3) CPU / Socket/ Processor/ Core.     

4) Task.

5) Pipelining.

6) Shared Memory.

7) Symmetric Multi-Processor (SMP).

8) Distributed Memory.

9) Synchronization.

10) Scalability.

C. Batas dan Biaya Pemrograman Paralel

  Hukum amdal menyatakan bahwa potensi program speedup didefinisikan oleh fraksi kode (P) yang dapat diparalelkan :

  Jika tidak ada kode yang dapat diparalelkan, P = 0 dan speedup = 1 (tidak ada speedup). Jika semua kode diparalelkan, P = 1 dan speedup tidak terbatas (dalam teori). Jika 50% kode dapat diparalelkan, speedup maksimum = 2, artinya kode akan berjalan dua kali lebih cepat.

D. Shared Memory

1) Karakteristik Umum

  Memori paralel komputer bersama sangat bervariasi, tetapi umumnya memiliki kemampuan yang sama untuk semua prosesor mengakses semua memori sebagai ruang alamat global. Secara historis, mesin memori bersama telah diklasifikasikan sebagai UMA dan NUMA berdasarkan waktu akses memori.

4. Arsitektur Memori Komputer Paralel

A. Distributed Memory

1) Karakteristik Umum

  Seperti sistem memori bersama, sistem memori terdistribusi sangat bervariasi tetapi berbagi karakteristik umum. Sistem memori terdistribusi memerlukan jaringan komunikasi untuk menghubungkan memori antar prosesor.

B. Hybrid Distributed-Shared Memory

1) Karakterisik Umum

  Komponen memori dapat berupa mesin memori atau GPU. Komponen memori terdistribusi adalah jaringan beberapa mesin memori atau GPU yang hanya tahu tentang memori mereka sendiri, bukan memori pada komputer lain. Oleh karena itu, komunikasi jaringan diperlukan untuk memindahkan data dari satu mesin ke mesin lainnya.

5. Paralel Programming Models

A. Shared Memory Model

  Dalam model pemograman ini, proses berbagi ruang alamat bersama yang mereka baca dan tulis secara asinkron. Berbagai mekanisme seperti kunci digunakan untuk mengontrol akses ke memori, menyelesaikan perselisihan dan untuk mencegah kondisi kebuntuan.

B. Threads Model

   Ini adalah jenis pemrograman memori bersama. Dalam model thread pemograman paralel, proses “berat” tunggal dapat memiliki beberapa “bobot ringan”, jalur eksekusi bersamaan.

C. Distributed Memory / Message Passing Model

  Dari perspektif pemograman, implementasi message passing biasanya terdiri dari perpustakaan subrutin. Panggilan ke subrutin ini tertanam dalam kode sumber. Programmer bertanggung jawab untuk menentukan semua paralelisme.

D. Data Paralel Model

  Pada arsitektur memori bersama, semua tugas mungkin memiliki akses ke struktur data melalui memori global. Pada arsitektur memori terdistribusi, struktur data global dapat dibagi secara logis dan secara fisik diseluruh tugas.

E. Hybrid Model

  Model Hybrid menggabungkan lebih dari satu model pemrograman yang dijelaskan sebelumnya. Saat ini, contoh umum dari model hybrid adalah kombinasi dari message passing model (MPI) dengan model threads (OpenMP).

F. SPMD and MPMD

  Program SPMD biasanya memiliki logika yang diperlukan dan diprogram ke dalamnya untuk memungkinkan berbagai tugas untuk bercabang atau hanya menjalankan bagian-bagian dari program yang dirancang untuk dieksekusi. Aplikasi MPMD tidak biasa seperti aplikasi SPMD, tetapi mungkin lebih cocok untuk jenis masalah tertentu, khususnya yang meberikan dekomposisi fungsional yang lebih baik dari pada dekomposisi domain.

6. Designing Parallel Programs

A. Automatic vs Manual Parallelization

  Merancang dan mengembangkan program paralel sudah menjadi proses yang sangat manual. Programmer biasanya bertangung jawab untuk mengidentifikasi dan mengimplementasikan paralelisme.

B. Pahami Masalah dan Programnya

  Langkah pertama dalam mengembangkan perangkat lunak paralel adalah terlebih dahulu memahami masalah yang ingin di selesaikan secara paralel. Jika memulai dengan program serial, perlu memahami kode yang ada juga. Sebelum menghabiskan waktu dalam upaya mengembangkan solusi paralel untuk suatu masalah, tentukan apakah masalah tersebut benar-benar dapat diparalelkan.

C. Partitioning

  Salah satu langkah pertama dalam merancang program paralel adalah memecah masalah menjadi “bongkahan” diskrit pekerjaan yang dapat didistribusikan ke berbagai tugas. Ini dikenal sebagai dekomposisi atau partisi.

D. Synchronization

  Mengelola urutan pekerjaan dan tugas yang dilakukan adalah pertimbangan desain kritis untuk sebagian besar program paralel.

E. Data Dependence

  Ketergantungan data dihasilkan dari beberapa penggunaan lokasi yang sama dalam penyimpanan oleh tugas yang berbeda.

F. Load Balancing

  Load Balancing mengacu pada praktik mendistribusikan sekitar jumlah pekerjaan yang sama di antara tugas-tugas sehingga semua tugas tetap sibuk sepanjang waktu. Ini dapat dianggap sebagai minimalisasi waktu idle tugas.

7. Parallel Examples

A. Simple Heat Equation

  Sebagian besar masalah dalam komptasi paralel memerlukan komunikasi di antara tugas-tugas tersebut. Sejumlah masalah umum membutuhkan komunikasi dengan tugas.

B. 1-D Wave Equation

  Dalam contoh ini, amplitudo sepanjang string bergetar seragam dihitung setelah jumlah waktu yang ditentukan berlalu.