Komputasi Paralel

Selalu saja ada kebutuhan yang tidak ada putusnya akan kemampuan komputasi yang lebih besar dari sistem komputer saat ini. Beberapa bidang yang membutuhkan komputasi tingkat tinggi adalah simulasi numerik problem-problem ilmiah dan teknik. Problem-problem tersebut seringkali membutuhkan kalkulasi repetitif pada sejumlah data yang besar guna memperoleh hasil yang valid. Sistem komputasi harus dapat diselesaikan dalam periode waktu yang masuk akal. Pada kenyataannya, perusahaan seringkali menuntut agar simulasi dan perhitungan teknik dapat diselesaikan dalam hitungan menit bahkan detik.

Komputer tradisional memiliki prosesor tunggal untuk melaksanakan tugas-tugas dari suatu program. Salah satu cara untuk meningkatkan kecepatan komputer adalah dengan menggunakan beberapa prosesor dalam satu komputer (multiprocessor) maupun beberapa komputer yang mengerjakan satu tugas. Dalam kasus lain, program dibagi menjadi beberapa bagian. Masing-masing bagian terdiri atas beberapa prosesor terpisah secara paralel. Pemrograman dengan metode itu disebut pemrograman paralel (parallel programming). Platform komputer yang digunakan, komputer paralel (parallel computer) bisa berupa komputer dengan beberapa prosesor maupun beberapa komputer yang terhubung dengan cara tertentu. Pendekatan tersebut seharusnya mampu meningkatkan kemampuan komputer secara signifikan.

Berdasarkan Kamus Besar Bahasa Indonesia (KBBI), kata paralel berarti sejajar. Komputasi paralel adalah salah satu teknik melakukan komputasi secara sejajar 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.

Hukum-Hukum dalam Komputasi Paralel

Terdapat dua hukum yang berlaku dalam sebuah parallel processing. yaitu:

• Hukum Amdahl. Amdahl berpendapat, “Peningkatan kecepatan secara paralel akan menjadi linear, melipatgandakan kemampuan proses sebuah komputer dan mengurangi separuh dari waktu proses yang diperlukan untuk menyelesaikan sebuah masalah.
• Hukum Gustafson. Pendapat yang dikemukakan Gustafson  hampir sama dengan Amdahl, tetapi dalam pemikiran Gustafson, sebuah komputasi paralel berjalan dengan menggunakan dua atau lebih mesin untuk mempercepat penyelesaian masalah dengan memperhatikan faktor eksternal, seperti kemampuan mesin dan kecepatan proses tiap-tiap mesin yang digunakan.

Baik hukum Amdahl dan hukum Gustafson berasumsi bahwa waktu berjalan bagian sekuensial program tidak tergantung pada jumlah prosesor. Hukum Amdahl mengasumsikan bahwa seluruh masalah adalah ukuran tetap sehingga jumlah total pekerjaan yang harus dilakukan secara paralel juga tidak tergantung pada jumlah prosesor, sedangkan hukum Gustafson mengasumsikan bahwa jumlah total pekerjaan yang dilakukan secara paralel bervariasi secara linier dengan jumlah prosesor.

Tujuan Komputasi Paralel

Tujuan utama dari pemrograman paralel adalah untuk meningkatkan performa komputasi. Semakin banyak hal yang bisa dilakukan secara bersamaan, semakin banyak pekerjaan yang bisa diselesaikan. Dengan membagi sebuah masalah besar ke dalam beberapa masalah kecil, membuat kinerja menjadi cepat. Performa dalam pemrograman paralel diukur dari berapa banyak peningkatan kecepatan (speed up) yang diperoleh dalam menggunakan teknik paralel. 

Tantangan dalam Implementasi Komputasi Parallel

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.

Arsitektur Komputasi Paralel

    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:

Tabel 1 Arsitektur Flyns Taksonomi

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.

Arsitektur Memori pada Komputasi Paralel

Arsitektur memori utama pada komputasi paralel, adalah:

• Shared memory

Dalam arsitektur memori bersama, beberapa prosesor beroperasi secara independen tetapi berbagi sumber daya memori yang sama. Hanya satu prosesor yang dapat mengakses lokasi memori bersama pada satu waktu.

Gambar 1. Arsitektur Shared Memory

Perubahan lokasi memori yang dipengaruhi oleh satu prosesor dapat dilihat oleh semua prosesor lainnya. Sinkronisasi dicapai dengan mengontrol tugas membaca dan menulis ke memori bersama. Mesin memori bersama dapat dibagi menjadi dua kelas utama berdasarkan waktu akses memori: UMA dan NUMA.

Uniform Memory Access (UMA) adalah arsitektur memori bersama yang digunakan pada komputer paralel. Semua prosesor dalam model UMA berbagi memori fisik secara seragam.

Gambar 2. Arsitektur UMA

Dalam arsitektur UMA, waktu akses ke lokasi memori tidak tergantung pada prosesor mana yang membuat permintaan atau chip memori mana yang berisi data yang ditransfer. Dalam arsitektur UMA, setiap prosesor dapat menggunakan cache pribadi. Periferal juga dibagikan dalam beberapa mode. Model UMA cocok untuk tujuan umum dan aplikasi berbagi waktu oleh banyak pengguna. Ini dapat digunakan untuk mempercepat pelaksanaan satu program besar dalam aplikasi yang membutuhkan waktu singkat.

Non-Uniform Memory Access (NUMA) dirancang untuk mengambil atribut terbaik dari sistem MPP dan SMP. Mesin berbasis NUMA dapat sangat hemat biaya dan dapat diskalakan sambil menjaga semantik memori bersama Symmetric Multiprocessor: arsitektur NUMA memungkinkan pengguna untuk mempertahankan investasi mereka dalam aplikasi SMP. NUMA adalah sarana untuk mengimplementasikan sistem memori bersama yang didistribusikan yang dapat membuat interaksi prosesor / memori tampak transparan untuk perangkat lunak aplikasi.

Dalam mesin NUMA, memori fisik didistribusikan di antara node komputasi sehingga sebagian kecil dari total memori mesin adalah lokal untuk masing-masing. Karena ini adalah arsitektur memori bersama, memori mesin yang tersisa dapat diakses dari jarak jauh melalui jaringan interkoneksi. Akses lokal memiliki latensi yang hampir sama dengan akses dalam sistem SMP, sementara akses data jarak jauh dapat menjadi urutan yang lebih lambat; maka istilah "Akses Memori Tidak Seragam".

Gambar 3. Arsitektur NUMA

Sistem NUMA terdiri dari node yang dihubungkan bersama melalui interkoneksi cepat, dengan setiap node berisi sejumlah kecil prosesor, busnya sendiri, dan memori fisiknya sendiri. Dalam sebagian besar arsitektur NUMA, setiap node tidak hanya memiliki memori lokalnya sendiri, tetapi juga cache lokal untuk menyimpan salinan lokal dari data yang baru-baru ini diakses yang secara asli berada di node lain (Gambar 1.7). Pada tingkat perangkat keras, NUMA memperkenalkan konsep "memori lokal" (yaitu memori yang secara fisik berada di simpul itu) dan "memori jarak jauh" (yaitu memori yang secara fisik berada di node lain). Untuk mengurangi latensi akses ke data lokal dan yang dimiliki dari jarak jauh, digunakan cache. Namun, ini memperkenalkan masalah menjaga salinan data yang di-cache koheren ketika satu node dalam sistem memodifikasi item data. Tugas ini mungkin jatuh ke perangkat keras sistem memori: "Cache Coherent" -NUMA (cc-NUMA).

Cache only Memory Architecture (COMA), Sama seperti NUMA tetapi memori terdistribusi dikonversi menjadi cache. Tidak ada hierarki memori di setiap node prosesor. Semua cache membentuk ruang alamat global. Dalam NUMA, setiap alamat dalam ruang alamat global biasanya ditetapkan sebagai simpul rumah tetap. Ketika prosesor mengakses beberapa data, salinan dibuat dalam cache lokal mereka, tetapi ruang tetap dialokasikan di simpul rumah. Sebaliknya, dengan COMA, tidak memiliki rumah. Akses dari titik jauh dapat menyebabkan data tersebut dimigrasi. Dibandingkan dengan NUMA, ini mengurangi jumlah salinan yang berlebihan dan memungkinkan penggunaan sumber daya memori yang lebih efisien. Di sisi lain, ini menimbulkan masalah tentang bagaimana menemukan data tertentu dan apa yang harus dilakukan jika memori lokal terisi. Mekanisme koherensi memori perangkat keras biasanya digunakan untuk mengimplementasikan migrasi. Ketika semua salinan dijaga konsisten dalam model COMA maka itu disebut Cache-Coherent COMA.

• Distributed memory

Prosesor memiliki memori lokal mereka sendiri. Alamat memori dalam satu prosesor tidak memetakan ke prosesor lain, sehingga tidak ada konsep ruang alamat global di semua prosesor. Karena setiap prosesor memiliki memori lokal sendiri, ia beroperasi secara independen. Perubahan yang dilakukan pada memori lokal tidak berpengaruh pada memori prosesor lain. Oleh karena itu, konsep koherensi cache tidak berlaku. Ketika sebuah prosesor membutuhkan akses ke data dalam prosesor lain, biasanya tugas programmer untuk secara eksplisit menentukan bagaimana dan kapan data dikomunikasikan. Sinkronisasi antar tugas juga merupakan tanggung jawab programmer.

Gambar 4. Arsitektur Distributed Memory

• Hybrid Distributed-Shared Memory 

Komputer terbesar dan tercepat di dunia saat ini menggunakan arsitektur memori bersama dan didistribusikan. Komponen memori bersama biasanya mesin SMP2 cache koheren. Prosesor pada SMP yang diberikan dapat mengatasi memori mesin tersebut sebagai global. Komponen memori terdistribusi adalah jaringan beberapa SMP. SMP hanya tahu tentang ingatan mereka sendiri - bukan ingatan pada SMP lain. Oleh karena itu, komunikasi jaringan diperlukan untuk memindahkan data dari satu SMP ke SMP lainnya. Tren saat ini tampaknya menunjukkan bahwa jenis arsitektur memori ini akan terus menang dan meningkat pada komputasi tingkat tinggi untuk masa yang akan datang.

Gambar 5. Arsitektur Hybrid Distributed-Shared Memory 

Referensi:

Wilkinson, Barry, et al. "Parallel Programming Technicques and Applications Using Networked Workstations and Parallel Computers second Edition". Upper Saddle River, New Jersey. Pearson Education, Inc, 2005.

Trobec, Roman, et al. "Introduction to Parallel Computing: From Algorithms to Programming on State-of-the-Art Platforms". Springer, 2018.

https://shodhganga.inflibnet.ac.in/bitstream/10603/3398/7/07_chapter%201.pdf

https://pdfs.semanticscholar.org/6d2c/00e5bd12a61f832ccaf2b1e27f96162d4d8c.pdf