Komputasi Paralel

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 ataupun karena tuntutan proses komputasi yang banyak. 

Apa bedanya kompitasi serial dengan komputasi paralel?

Singkatnya > Transmisi data serial mengirimkan bit data satu demi satu melalui saluran tunggal. Transmisi data paralel mengirimkan beberapa bit data secara bersamaan melalui beberapa saluran.

Sederhananya, software dituliskan untuk serial komputasi :

·         Masalah dipecah menjadi serangkaian instruksi terpisah

·         Instruksi dijalankan secara berurutan satu demi satu

·         Dieksekusi pada satu prosesor

·         Hanya satu instruksi yang dapat dijalankan setiap saat

Contohnya :

Secara dasarnya komputasi paralel adalah penggunaan beberapa sumber daya komputasi secara bersamaan untuk memecahkan masalah komputasi:

·         Masalah dipecah menjadi beberapa bagian yang dapat diselesaikan secara bersamaan

·         Setiap bagian selanjutnya dipecah menjadi serangkaian instruksi

·         Instruksi dari setiap bagian dijalankan secara bersamaan pada prosesor yang berbeda

·         Mekanisme kontrol / koordinasi keseluruhan digunakan

Contohnya :

Masalah komputasi harus mampu dipecah menjadi beberapa bagian pekerjaan yang dapat diselesaikan secara bersamaan, menjalankan beberapa instruksi program kapan saja dan dipecahkan dalam waktu yang lebih singkat dengan beberapa sumber daya komputasi dibandingkan dengan satu sumber daya komputasi.

Sumber daya komputasi biasanya satu komputer dengan banyak prosesor / inti dan sejumlah sembarang komputer yang terhubung oleh jaringan.

Di kehidupan ini banyak peristiwa kompoleks dan saling terkait terjadi pada waktu yang sama tetapi dalam urutan waktu tertentu. Pada komputasi ibandingkan dengan komputasi serial, komputasi paralel jauh lebih cocok untuk pemodelan, simulasi, dan pemahaman fenomena dunia nyata yang kompleks.

Alasan komputasi paralel digunakan

1.      Hemat waktu dan uang, secara teori, membuang lebih banyak sumber daya pada suatu tugas akan mempersingkat waktu penyelesaiannya, dengan potensi penghematan biaya pada komputer paralel dapat dibuat dari komponen komoditas yang murah.

2.      Pemecahan masalah yang lebih kompleks, banyak masalah yang begitu besar atau kompleks sehingga tidak praktis atau tidak mungkin diselesaikan dengan menggunakan program serial, terutama mengingat memori komputer yang terbatas.

3.      Memberikan Konsuransi atau persaingan, komputasi tunggal hanya dapat melakukan satu hal dalam satu waktu sedangkan dalam multi komputasi dapat melakukan banyak hal secara bersamaan.

4.      Keuntungan dengan mengambil sumber daya non-lokal (asing), menggunakan komputasi di wide area network atau bahkan Internet ketika sumber daya komputasi lokal langka atau tidak mencukupi.

5.      Lebih baik menggunakan perangkat kesar paralel dasar, perangkat lunak paralel secara khusus ditujukan untuk perangkat keras paralel dengan banyak inti atau prosessor.

Selama kurung waktu lebih dari 20 tahun terakhir, tren yang ditunjukkan oleh jaringan yang semakin cepat, sistem terdistribusi, dan arsitektur komputer multi-prosesor (bahkan di tingkat desktop) dengan jelas menunjukkan bahwa paralelisme adalah masa depan komputasi. Dalam periode yang sama, telah terjadi peningkatan kinerja superkomputer lebih dari 500.000x , tanpa akhir yang terlihat saat ini. Exaflop = 10 ¹⁸ perhitungan per detik

Bidang yang menggunakan komputasi paralel

1.      Science and Engineering

Sejarahnya, komputasi paralel telah dianggap sebagai "the high end of computing", dan telah digunakan untuk memodelkan masalah yang sulit di banyak bidang sains dan teknik. Misalnya :

·     Fisika - terapan, nuklir, partikel, materi terkondensasi, tekanan tinggi, fusi, fotonik

·     Biosains - Bioteknologi, Genetika, Atmosfer, Bumi, Lingkungan

·     Kimia- Ilmu Molekuler

·     Geologi - Seismologi

·     Teknik Mesin - dari prostetik hingga pesawat ruang angkasa

·     Teknik Elektro - Desain Sirkuit, Mikroelektronika

·     Pertahanan - Senjata

·     Ilmu Komputer dan Matematika

(gambar di ambil dari : https://fineartamerica.com/art/brain+tumour)

2.      Industrial and Commercial

Saat ini gadget sudah tak asing lagi, banyak aplikasi yang terpasang untuk mendukung fasilitas. Dengan demikian aplikasi komersial memberikan kekuatan pendorong yang sama atau lebih besar dalam pengembangan komputer yang lebih cepat. Aplikasi ini membutuhkan pemrosesan data dalam jumlah besar dengan cara yang canggih.  Contoh penggunaan komputasi dalam perindustrial dan komesial seperti, "Big Data", database, penambangan data, Kecerdasan Buatan (AI), Grafik canggih dan virtual reality, khususnya di industri hiburan, Video berjaringan dan teknologi multi-media.

(gambar di ambil : https://balesin.id/)

3.      Global Applications

Komputasi paralel sekarang digunakan secara luas di seluruh dunia, dalam berbagai macam aplikasi.

Konsep dan terminologi Arsitektur Komputasi Paralel

1.     Von Neumann Computer Architecture

Arsitektur Komputer Von Neumann merupakan arsitektur yang diciptakan oleh Jhon Von Neumann(1903 – 1957). Nama Von Neumann sendiri diambil dari namanya karena dialah yang pertama kali mempublikasikan konsep tersebut, arsitektur komputer ini banyak digunakan di sebagian besar sistem komputer non paralel seperti komputer rumahan atau notebook. Di tahun 1945 dia pertama kali menulis persyaratan umum untuk komputer elektronik. Dikenal sebagai " stored-program computer" - baik instruksi program maupun data disimpan dalam memori elektronik. Berbeda dari komputer sebelumnya yang diprogram melalui "hard wiring" sejak itu, hampir semua komputer mengikuti desain dasar ini: Terdiri dari empat komponen utama:

<ol style = "list-style-type: lower-alpha;">
<li> Memory </li>
<li> Control Unit</li>
<li> Arithmetic Logic Unit</li>
<li> Input / Output </li>
</ol>

a.   Read/write, memori akses acak digunakan untuk menyimpan instruksi program dan data

<ol style = "list-style-type: lower-alpha;">

<li> Instruksi program adalah kode data yang memberitahu komputer untuk melakukan sesuatu </li>
<li> Data hanyalah informasi yang akan digunakan oleh program </li>
</ol>

b.  Control unit mengambil instruksi / data dari memori, menerjemahkan instruksi dan kemudian secara berurutan mengoordinasikan operasi untuk menyelesaikan tugas yang diprogram.

c.        Arithmetic Unit melakukan operasi aritmatika dasar

d.       Input / Output adalah antarmuka ke operator manusia

komputer paralel masih mengikuti desain dasar ini, hanya dikalikan dalam satuan. Arsitektur dasar dan fundamental tetap sama.

2.      Flynn's Classical Taxonomy

Taksonomi Flynn membedakan arsitektur komputer multi-prosesor menurut bagaimana mereka dapat diklasifikasikan sepanjang dua dimensi independen Arus Instruksi dan Aliran Data . Masing-masing dimensi ini hanya dapat memiliki satu dari dua kemungkinan status: Tunggal atau Banyak . 4 kemungkinan klasifikasi menurut Flynn:

a.       Single Instruction, Single Data (SISD)

Sebuah komputer yang tidak memiliki cara untuk melakukan paralelisasi terhadap instruksi atau data. Adalah satu-satunya yang menggunakan arsitektur Von Neumann. ini dikarenakan pada model hanya menggunkan 1 processor saja.

• Instruksi Tunggal: Hanya satu aliran instruksi yang sedang ditindaklanjuti oleh CPU selama satu siklus clock
• Data Tunggal: Hanya satu aliran data yang digunakan sebagai input selama satu siklus jam

Contoh: mainframe generasi lama, minikomputer, workstation, dan prosesor / inti PC tunggal.

b.      Single Instruction, Multiple Data (SIMD)

Sebuah komputer yang mampu memproses banyak aliran data dengan hanya satu instruksi, sehingga operasi yang dilakukan adalah operasi pararel.

• Instruksi Tunggal: Semua unit pemrosesan menjalankan instruksi yang sama pada siklus jam tertentu
• Beberapa Data: Setiap unit pemrosesan dapat beroperasi pada elemen data yang berbeda
• Dua jenis: Array Prosesor dan Pipa Vektor

Paling cocok untuk masalah khusus yang ditandai dengan tingkat keteraturan yang tinggi, seperti pemrosesan grafik / gambar. Contoh: 

Array Prosesor: Mesin Berpikir CM-2, MasPar MP-1 & MP-2, ILLIAC IV

Pipa Vektor: IBM 9000, Cray X-MP, Y-MP & C90, Fujitsu VP, NEC SX-2, Hitachi S820, ETA10

Sebagian besar komputer modern, terutama yang memiliki unit prosesor grafis (GPU) menggunakan instruksi SIMD dan unit eksekusi.

(gambar merupakan contoh Cray X-MP)

c.       Multiple Instruction, Single Data (MISD)

menggunakan banyak processor dengan setiap processor menggunakan instruksi yang berbeda namun mengolah data yang sama. hal ini merupakan kebalikan dari model SIMD.

• Beberapa Instruksi: Setiap unit pemrosesan beroperasi pada data secara independen melalui aliran instruksi terpisah.
• Data Tunggal: Aliran data tunggal dimasukkan ke dalam beberapa unit pemrosesan.

Beberapa (jika ada) contoh aktual dari kelas komputer paralel ini yang pernah ada. Beberapa kemungkinan penggunaan mungkin adalah:

o  beberapa filter frekuensi yang beroperasi pada aliran sinyal tunggal

o  beberapa algoritma kriptografi mencoba memecahkan pesan berkode tunggal.

 

d.      Multiple Instruction, Multiple Data (MIMD)

menggunakan banyak processor dengan setiap processor memiliki instruksi yang berbeda dan mengolah data yang berbeda, namun banyak komputer  yang menggunakan model MIMD juga memasukkan komponen untuk model SIMD. 

Multiple Instruction: Setiap prosesor mungkin menjalankan aliran instruksi yang berbeda

Beberapa Data: Setiap prosesor mungkin bekerja dengan aliran data yang berbeda

Eksekusi bisa sinkron atau asinkron, deterministik atau non-deterministik. Saat ini, jenis komputer paralel yang paling umum - superkomputer paling modern termasuk dalam kategori ini.

Contoh: superkomputer terkini, cluster komputer paralel berjaringan dan "grid", komputer SMP multi-prosesor, PC multi-core.

Perhatikan bahwa  banyak arsitektur MIMD juga menyertakan sub-komponen eksekusi SIMD.

Arsitektur Memori Komputer Paralel

1.      Shared Memory

Pada arsitektur jenis ini, prosesor dapat mengakses semua memori sebagai space alamat global. Shared momory dibagi menjadi dua kelas yaitu UMA (Uniform Memory Access) dan NUMA (Non-Uniform Memory Access).

• UMA sendiri merupakan kelas dari shared memory dengan karakteristik semua prosesor dapat mengakses semua memori sebagai ruang alamat global. Multiprosesor pada jenis ini dapat beroperasi secara independen namun dapat saling berbagi memori. 
• NUMA memiliki karakteristik prosesor memiliki bank alamat memori sendiri, sehingga prosesor dapat mengakses memori lokal dengan cepat, sedangkan untuk memori remote lebih lambat. Pengaksesan pada data lokal dapat meningkatkan throughput memori pada jenis arsitektur ini.

Keseluruhan dua tipe pada jenis Shared Memory bahwa space alamat memori global menyediakan perspektif pemrograman user-friendly ke memori, selain itu sharing data antar task cepat dan uniform karena dekatnya memori ke CPU. Namun apabila dilihat dari kelemahan pada bangunan arsitektur ini adalah tidak scalable artinya menambah CPU dapat meningkatkan trafik di jalur shared memory--CPU. Kelemahan yang lainnya adalah programmer bertanggungjawab untuk sinkronisasi yang memastikan akses yang tepat ke memori global. Tentunya hal ini akan berdampak semakin kompleks dan mahal seiring semakin bertambahnya jumlah prosesor.

2.      Distributed Memory

Arsitektur jenis ini prosesornya mempunyai memori lokal sendiri, sehingga inter-prosesor memori membutuhkan networking. Kelebihan yang didapatkan dari jenis distributed ini adalah scalable jumlah prosesor dan ukuran memori dapat ditingkatkan. Tiap prosesornya dapat mengakses memorinya tanpa interferensi dan overhead, seperti dikoheren cache. Pada jenis ini menjadi cost effecitve apabila menggunakan PC komoditas, off the self processor. Tetapi kelemahan yang ditemukan pada arsitektur ini adalah tugas programmer akan semakin kompleks terkait dengan detail komunikasi datanya, selain itu mapping data struktur berbasis memori global bisa jadi susah.

3.      Hybrid distributed-shared memory

Arsitektur ini menggabungkan tipe shared dan distributed. Komponen memori shared biasanya mesin Symmetric Multiprocessor (SMP) koheren (prosesor di mesin SMP mempunyai akses global ke memori mesin tersebut), sedangkan komponen distributed adalah jaringan  SMP multiple (SMP hanya tahu memorinya saja). Komunikasi jaringan diperlukan untuk memindahkan data dari satu SMP ke lainnya.

Model Pemrograman Paralel

1.      Model shared memory

Pada model ini task berbagi bersama space alamat memori, dengan penulisan dan pembacaan secara asinkron. Mekanisme yang digunakan adalah semaphore / lock untuk mengontrol akses ke shared memori

Keuntungannya (dari sudut programmer): ownership data tidak diperlukan, sehingga tidak perlu untuk menyatakan dengan eksplisit komunikasi data antar task. Pengembangan program dapat disederhanakan

Kelemahannya adalah di performansi, yaitu akan lebih susah untuk memanage locality data

Menjaga data lokal untuk prosesor yang mengirimnya akan memerlukan alokasi/akses memori dan mempengaruhi trafik bus saat prosesor yang lain menggunakan data yang sama. Kompiler akan mentranslate variabel program user ke dalam alamat memori aktualnya yang global. Implementasi model di atas platform distributed belum ada, kecuali KSR ALLCACHE

2.      Model Thread

Satu proses dapat mempunyai beberapa jalur eksekusi yang konkuren. Program utama dijadwalkan untuk berjalan oleh OS, program load dan mengambil semua kebutuhan resource sistem. Program membuat thread yang dijadwalkan dapat dijalankan secara bersamaan. Tiap thread mempunyai data lokal, namun shared resources dari program. Menghemat resources (bandingkan dengan clone). Komunikasi antar thread lewat memori global.

3.      Model Message Passing

Pada model ini set task menggunakan memori lokalnya sendiri saat komputasi. Beberapa task dapat ditempatkan di mesin fisik sama. Task transfer data lewat pesan komunikasi. Implementasi menggunakan library subrutin yang diembed-kan di source code. Programmer bertugas menentukan semua paralelism

·         Standar Message Passing Interface (MPI) direlease tahun 1994, dan part-2 di tahun 1996

·         Tersedia di http://www-unix.mcs.anl.gov/mpi/

4.      Model Data Paralel

Disebut sebagai model Partitioned Global Address Space (PGAS). Model paralel data menunjukkan karakteristik berikut:

o  Ruang alamat diperlakukan secara global

o  Sebagian besar pekerjaan paralel berfokus pada melakukan operasi pada kumpulan data. Kumpulan data biasanya diatur ke dalam struktur umum, seperti larik atau kubus.

o  Sekumpulan tugas bekerja secara kolektif pada struktur data yang sama, namun, setiap tugas bekerja pada partisi yang berbeda dari struktur data yang sama.

o  Tugas melakukan operasi yang sama pada partisi kerja mereka, misalnya, "tambahkan 4 ke setiap elemen array".

Pada arsitektur memori bersama, semua tugas mungkin memiliki akses ke struktur data melalui memori global. Pada arsitektur memori terdistribusi, struktur data global dapat dipisahkan secara logis dan / atau fisik di seluruh tugas.

5.      Hybrid Model

Model hybrid menggabungkan lebih dari satu model pemrograman yang dijelaskan sebelumnya. Contoh umum model hybrid adalah kombinasi dari message passing model (MPI) dengan model threads (OpenMP).

o  Thread melakukan kernel intensif komputasi menggunakan data lokal pada node

o  Komunikasi antar proses pada node yang berbeda terjadi melalui jaringan menggunakan MPI

Model hybrid ini cocok untuk lingkungan perangkat keras yang paling populer (saat ini) dari mesin multi / banyak-inti yang berkerumun. Contoh model hybrid lain yang serupa dan semakin populer adalah menggunakan MPI dengan pemrograman CPU-GPU (Graphics Processing Unit).

6.      SPMD dan MPMD

a.       Single Program Multiple Data (SPMD)

SPMD sebenarnya adalah model pemrograman "tingkat tinggi" yang dapat dibangun di atas kombinasi model pemrograman paralel yang disebutkan sebelumnya.

·   PROGRAM TUNGGAL: Semua tugas menjalankan salinannya dari program yang sama secara bersamaan. Program ini dapat berupa utas, penyampaian pesan, data paralel atau hibrid.

·       GANDA DATA: Semua tugas mungkin menggunakan data yang berbeda

Program SPMD biasanya memiliki logika yang diperlukan yang diprogram ke dalamnya untuk memungkinkan tugas yang berbeda untuk bercabang atau hanya mengeksekusi secara bersyarat bagian-bagian dari program yang dirancang untuk dieksekusi. Artinya, tugas tidak harus menjalankan seluruh program - mungkin hanya sebagian saja.

Model SPMD, menggunakan message passing atau hybrid programming, mungkin merupakan model pemrograman paralel yang paling umum digunakan untuk cluster multi-node.

b.      Multiple Program Multiple Data (MPMD)

Seperti SPMD, MPMD sebenarnya adalah model pemrograman "tingkat tinggi" yang dapat dibangun di atas kombinasi model pemrograman paralel yang disebutkan sebelumnya.

· PROGRAM GANDA: Tugas dapat menjalankan program yang berbeda secara bersamaan. Program dapat berupa utas, penyampaian pesan, data paralel atau hibrid.

·       GANDA DATA: Semua tugas mungkin menggunakan data yang berbeda

Aplikasi MPMD tidak umum seperti aplikasi SPMD, tetapi mungkin lebih cocok untuk jenis masalah tertentu, terutama yang lebih cocok untuk dekomposisi fungsional daripada dekomposisi domain (dibahas nanti di bagian Partisi).

Referensi 

https://hpc.llnl.gov/training/tutorials/introduction-parallel-computing-tutorial

https://docplayer.info/39702073-Model-pemrograman-paralel.html

https://core.ac.uk/download/157583695.pdf