1.1 Parallel Processing
Pemrosesan parallel (parallel processing) adalah
penggunaan lebih dari satu CPU untuk menjalankan sebuah program secara
simultan. Idealnya, parallel processing membuat program berjalan lebih cepat
karena semakin banyak CPU yang digunakan. Tetapi dalam praktek, seringkali
sulit membagi program sehingga dapat dieksekusi oleh CPU yang berbea-beda tanpa
berkaitan di antaranya.
1.2.
Pemrograman Parallel
Teknik pemrograman
komputer yang memungkinkan eksekusi perintah atau operasi secara bersamaan baik
dalam komputer dengan satu (prosesor tunggal) ataupun banyak (prosesor ganda dengan
mesin paralel) CPU.
Bahasa
Pemrograman yang digunakan pada Pemrograman Parallel
1.MPI (Message
Passing Interface)
2.PVM (Parallel
Virtual Machine)
1.3.
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 (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.
Komputasi Paralel
membutuhkan
• Algoritma
• Bahasa
pemrograman
• Compiler
Teknologi komputasi paralel sudah berkembang lebih dari dua
dekade, penggunaannya semakin beragam mulai dari kebutuhan perhitungan di
laboratorium fisika nuklir, simulasi pesawat luar angkasa, hingga prakiraan cuaca.
Komputasi paralel didefinisikan sebagai penggunaan sekumpulan sumberdaya
komputer secara simultan untuk menyelesaikan permasalahan komputasi. Secara
prinsip komputer paralel membagi permasalahan sehingga menjadi lebih kecil
untuk dikerjakan oleh setiap prosesor (CPU) dalam waktu yang bersamaan/simultan
(concurrent). Prinsip ini disebut paralelisme.
Paralelisme
dalam komputasi paralel merupakan hal yang diciptakan dan dimanfaatkan. Sebenarnya
prinsip paralelisme juga sudah diterapkan dalam komputer serial misal dengan pipelining
dan superscalar-nya namun demikian tidak memberikan solusi terbaik dalam
hal meningkatkan performansi dikarenakan terbatasnya kemampuan untuk menambah kecepatan
prosesor dan fenomena memory bottleneck. Perkembangan
penerapan paralelisme pada prosesor dari masa ke masa ditunjukkan pada Gambar
1.1.
1)
Paralelisme bit-level. Contoh : prosesor 32 bit dan
prosesor 64 bit.
2)
Paralelisme instruction set-level. Contoh : CISC dan RISC.
3)
Paralelisme thread-level. Contoh : Intel hyperthreading.
Paralelisme
lain yang juga berkembang dalam komputasi paralel adalah paralelisme data dan
paralelisme fungsi (task).
Perkembangan
teknologi prosesor memberikan pengaruh yang besar pada komputasi paralel. Mulai
dari prosesor singlecore superscalar, chip multiprocessor,
prosesor multicore, hingga prosesor cell memberikan kontribusi
terhadap peningkatan performansi komputer paralel. Supercomputer
seperti Roadrunner misalnya menggunakan teknologi multiprosesor,
prosesor cell, atau gabungan dari keduanya (hybrid system).
Jumlah prosesor yang dipakai HPC juga semakin tidak terbatas sehingga
arsitekturnya disebut Massively Parallel Processing (MPP). Namun
demikian penggunaan cluster PC menjadi tren dalam komputasi
paralel karena faktor biaya dan skalabilitas. Dari Tabel 1.1. diperoleh data
bahwa cluster menjadi pilihan terbanyak para pengembang HPC.
1.3.1
Arsitektur Komputer Paralel
Berdasarkan
jumlah dan prinsip kerja prosesor pada komputer paralel, A.J. Van der Steen dan
J. Donggara menyebutkan terdapat empat arsitektur utama komputer paralel
menurut Flynn (1972) yaitu:
1) SISD (Single Instruction
– Single Data). Komputer ini memiliki hanya satu prosesor dan satu
instruksi yang dieksekusi secara serial. Komputer ini adalah tipe komputer
konvensional. Menurut mereka tipe komputer ini tidak ada dalam praktik komputer
paralel karena bahkan mainframe pun tidak lagi menggunakan satu prosesor.
Klasifikasi ini sekedar untuk melengkapi definisi komputer paralel. Skema SISD
ditunjukkan pada Gambar 1.2.
2)
SIMD (Single Instruction
– Multiple Data). Komputer ini memiliki lebih dari satu prosesor, tetapi
hanya mengeksekusi satu instruksi secara paralel pada data yang berbeda pada
level lock-step. Komputer vektor adalah salah satu komputer paralel yang
menggunakan arsitektur ini. Skema SIMD ditunjukkan pada Gambar 2.3.
3)
MISD (Multiple
Instructions – Single Data). Teorinya komputer ini memiliki satu prosesor
dan mengeksekusi beberapa instruksi secara paralel tetapi praktiknya tidak ada
komputer yang dibangun dengan arsitektur ini karena sistemnya tidak mudah
dipahami. Skema MISD ditunjukkan pada Gambar 1.4.
4)
MIMD (Multiple
Instructions – Multiple Data). Komputer ini memiliki lebih dari satu
prosesor dan mengeksekusi lebih dari satu instruksi secara paralel. Tipe
komputer ini yang paling banyak digunakan untuk membangun komputer paralel,
bahkan banyak supercomputer yang menerapkan arsitektur ini. Skema MIMD
ditunjukkan pada Gambar 1.5.
Sistem
komputer paralel dibedakan dari cara kerja memorinya menjadi shared memory dan
distributed memory. Shared memory berarti memori tunggal diakses
oleh satu atau lebih prosesor untuk menjalankan instruksi sedangkan distributed
memory berarti setiap prosesor memiliki memori sendiri untuk menjalankan
instruksi. Menurut A.J. Van der Steen dan J. Donggara baik sistem shared
memory maupun distributed memory merupakan SIMD atau MIMD.
Top500 Team
membagi arsitektur komputer paralel dalam 6 kelompok berdasarkan daftarnya
sejak tahun 1993 yaitu : SIMD, Single Processor, SMP, MPP, Constellation
dan Cluster. Dari keenam arsitektur tersebut hanya 3 kelompok yang masih
bertahan dalam daftar di Nopember 2009 seperti ditunjukkan dalam Gambar 1.6.
Pada
penelitian ini arsitektur yang digunakan adalah cluster PC multicore
yang merupakan penerapan arsitektur MIMD dengan distributed shared memory.
Skema arsitektur ini ditunjukkan pada Gambar 1.7. Adapun komponen-komponen
utama dari arsitektur komputer paralel cluster PC antara lain :
- Prosesor (CPU). Bagian paling penting dalam sistem, untuk multicore terdapat lebih dari satu core yang mengakses sebuah memori (shared memory).
- Memori. Bagian ini dapat diperinci lagi menjadi beberapa bagian penyusunnya seperti RAM, cache memory dan memori eksternal.
- Sistem Operasi. Software dasar untuk menjalankan sistem komputer.
- Cluster Middleware. Antarmuka antara hardware dan software.
- Programming Environment dan Software Tools. Software yang digunakan untuk pemrograman paralel termasuk software pendukungnya.
- User Interface. Software yang menjadi perantara hardware dengan user.
- Aplikasi. Software berisi program permasalahan yang akan diselesaikan.
- Jaringan. Penghubung satu PC (prosesor) dengan PC yang lain sehingga memungkinkan pemanfaatan sumberdaya secara simultan.
1.3.1 Komputer Multicore
Pada saat
ini PC secara umum telah menggunakan paralelisme thread-level dengan
berkembangnya teknologi multicore. Teknologi ini menempatkan lebih dari
satu general purpose processor pada satu keping mikroprosesor sehingga
memungkinkan lebih dari satu thread bekerja secara simultan. Prosesor multicore
umumnya menggunakan prinsip shared-memory, dimana masing-masing core
processor terhubung dengan sebuah memori internal (cache memory)
yang menjadi perantara baginya dengan memori eksternal seperti RAM. Hal
ini ditunjukkan dengan Gambar 1.8. Namun demikian adapula prosesor multicore
yang menggunakan prinsip message passing untuk berkomunikasi antar core.
Paralelisme fisik pada
prosesor multicore sebenarnya tidak serta merta mendorong peningkatan
performansi komputer. Jumlah core yang banyak tidak akan berpengaruh
bila tidak didukung dengan algoritma dan aplikasinya. Program paralel dengan
berbagai level paralelisme dapat diterapkan untuk mengoptimalkan kinerja
prosesor, mulai dari instruction-level parallelism (ILP) hingga thread-level
parallelism (TLP).
Keuntungan teknologi multicore di
antaranya adalah :
- Percepatan proses dengan adanya cache coherency circuitry.
- Penghematan ruang yang berarti semakin kecil ukuran fisik mikroprosesor.
- Penghematan energi karena daya yang digunakan oleh dua singlecore lebih besar dibandingkan dengan sebuah dualcore.
Selain
keuntungan, prosesor multicore juga tidak lepas dari kekurangan yaitu :
- Perlu pembaruan software sehingga mendukung kinerja core yang tersedia.
- Kesulitan mengelola panas yang dihasilkan oleh kerja prosesor.
- Kesulitan meningkatkan performansi prosesor karena keterbatasan bandwidth memori dan bus sharing.
1.3.1
Algoritma
Paralel
Komputasi paralel
digunakan untuk menyelesaikan permasalahan komputasi yang besar atau komplek.
Program paralel dibuat khusus atau dimodifikasi dari program serial. Algoritma
paralel digunakan untuk menggantikan algoritma serial menyesuaikan arsitektur
komputer yang digunakan. Berdasarkan klasifikasi
arsitektur komputer paralel di atas
komputer paralel shared memory dan distributed memory tentu saja
menggunakan algortima paralel yang berbeda.
Algoritma paralel
menjelaskan langkah-langkah yang ditempuh oleh komputer paralel dalam
menyelesaikan permasalahan. Hal-hal yang ada dalam algoritma paralel meliputi :
1)
Identifikasi terhadap beban permasalahan yang akan dikerjakan
secara paralel.
2)
Pemetaan porsi pekerjaan yang dibebankan kepada tiap-tiap proses.
3)
Distribusi data input, output dan perantara yang terkait dengan
program.
4)
Pengaturan data yang diakses bersamaan oleh beberapa prosesor.
5)
Menyelaraskan fungsi prosesor pada setiap langkah pekerjaan.
Ada
beberapa model algortima paralel, di antaranya : data parallel, task
graph, work pool, master-slave (message passing),
dan pipeline. Algoritma paralel yang digunakan untuk arsitektur cluster
PC umumnya menggunakan message passing, di mana data dari memori sebuah
PC dikirimkan ke memori PC lain melalui suatu jaringan. Beberapa konsep
penting terkait dengan hal di atas adalah dekomposisi, mapping, dan
granularitas.
1.3.3.1
Dekomposisi (pembagian beban kerja)
Pembagian beban pekerjaan
adalah hal utama dalam algoritma paralel, karena tujuan utama komputasi paralel
adalah mempercepat proses dengan mengerjakan permasalahan menggunakan
sumberdaya yang dimiliki secara bersamaan. Berdasarkan obyek yang dibagi, dekomposisi
dibedakan menjadi dekomposisi data (domain) dan dekomposisi fungsi.
Dekomposisi menyesuaikan
permalasahan yang dikerjakan, semisal untuk permasalahan yang melibatkan
pengulangan (iterasi) input data yang besar di mana fungsi yang digunakan sulit
untuk diparalelkan maka dekomposisi data lebih baik digunakan. Untuk
permasalahan lain dengan fungsi yang beragam bisa menggunakan dekomposisi
fungsi. Pemilihan dekomposisi ini sangat berpengaruh pada performansi komputer
paralel.
1.3.3.2
Mapping (pemetaan
beban kerja)
Mapping terkait erat dengan arsitektur dan kapasitas komputer paralel yang
digunakan. Mapping juga terkait erat dengan dekomposisi, di mana
beban pekerjaan yang dibagi-bagi akan diberikan pada proses-proses secara
paralel.
Pada arsitektur homogen di mana
kemampuan dan kapasitas setiap node sama maka mapping menjadi lebih
mudah, setiap node mendapatkan porsi yang sama untuk dekomposisi data.
Untuk komputer paralel heterogen, mapping akan dilakukan dengan terlebih
dahulu mengukur kapasitas dari setiap node, sehingga mapping beban
kerja memberikan porsi yang berbeda-beda kepada setiap node.
1.3.3.3
Granularitas
Faktor
penting lain dalam algoritma paralel adalah perbandingan komputasi dan
komunikasi. Komputasi di sini diartikan proses yang dilakukan pada setiap
prosesor sedangkan komunikasi adalah proses pertukaran informasi yang dilakukan
antar prosesor. Permasalahan dengan fungsi sederhana biasanya memberikan porsi
komputasi lebih besar dari pada komunikasi (coarse grain), sebaliknya
permasalahan dengan banyak fungsi menyebabkan porsi komunikasi hampir sama
dengan porsi komputasinya (fine grain).
Algoritma
paralel mengatur granularitas sehingga tidak terjadi defisiensi proses baik
komputasi maupun komunikasi. Porsi komputasi dan komunikasi juga disesuaikan
dengan arsitektur komputer paralel.
1.3.4
Algortima
Multithreading
Definisi
komputasi paralel memberikan pemahaman bahwa komponen-komponen dalam komputer
menjadi bagian yang dieksploitasi untuk meningkatkan performansi terutama
kecepatannya. Selain pengembangan hardware seperti prosesor dan memori,
yang juga dikembangkan adalah eksploitasi terhadap pemrograman
aplikasinya (software). Eksploitasi software merupakan solusi
yang mungkin dilakukan dengan biaya ringan, salah satunya penggunaan teknik
pemrograman paralel dengan multithreading.
Komputasi
paralel sangat dipengaruhi oleh perkembangan teknologi komputer, terutama
prosesor. Komputer singlecore telah menggunakan teknik pemrograman
paralel untuk meningkatkan kinerjanya, sebagai contoh penggunaan hyperthreading
pada prosesor Intel. Sedangkan untuk komputer multicore ada beberapa
teknik yang diterapkan, salah satunya adalah multithreading. Bila dalam
sistem operasi kita mengenal task, process dan thread,
maka multithreading adalah paralelisme thread-level sebagaimana
penerapan multitasking dan multiprocessing.
Sebuah thread adalah sebuah aliran kendali tunggal di dalam suatu
program sehingga teknik multithreading diartikan sebagai teknik yang
memanfaatkan lebih dari satu aliran kendali di dalam suatu program.
Teknik multithreading
berdasarkan survey bila dipadukan dengan teknologi multicore terbukti
meningkatkan performansi CPU. Dalam beberapa penelitian termasuk, penggunaan thread-level
programming menjadi solusi bagi peningkatan performansi komputer paralel,
sehingga keunggulan message passing dipadukan di antara dua
pustaka paralel seperti MPI dan OpenMP.
1.3.4.1
Static Threading
Teknik ini
biasa digunakan untuk komputer dengan chip multiprocessors dan jenis
komputer shared-memory lainnya. Teknik ini memungkinkan thread berbagi
memori yang tersedia, menggunakan program counter dan mengeksekusi program
secara independen. Sistem operasi menempatkan satu thread pada prosesor
dan menukarnya dengan thread lain yang hendak menggunakan prosesor itu.
Mekanisme
ini terhitung lambat, karenanya disebut dengan static. Selain itu teknik
ini tidak mudah diterapkan dan rentan kesalahan. Alasannya, pembagian pekerjaan
yang dinamis di antara thread-thread menyebabkan load balancing-nya
cukup rumit. Untuk memudahkannya programmer harus menggunakan protokol
komunikasi yang kompleks untuk menerapkan scheduler load balancing.
Kondisi ini mendorong pemunculan concurrency platforms yang menyediakan layer
untuk mengkoordinasi, menjadwalkan, dan mengelola sumberdaya komputasi paralel.
Sebagian platform dibangun sebagai runtime libraries atau sebuah bahasa
pemrograman paralel lengkap dengan compiler dan pendukung runtime-nya.
1.3.4.2
Dynamic Multithreading
Teknik ini
merupakan pengembangan dari teknik sebelumnya yang bertujuan untuk kemudahan
karena dengannya programmer tidak harus pusing dengan protokol komunikasi, load
balancing, dan kerumitan lain yang ada pada static threading. Concurrency
platform ini menyediakan scheduler yang melakukan load balacing
secara otomatis. Walaupun platformnya masih dalam pengembangan namun secara
umum mendukung dua fitur : nested parallelism dan parallel loops.
Nested parallelism memungkinkan sebuah subroutine
di-spawned (ditelurkan dalam
jumlah banyak seperti telur katak) sehingga program utama tetap berjalan
sementara subroutine menghitung hasilnya. Sedangkan parallel loops
seperti halnya fungsi for namun memungkinkan iterasi loop dilakukan secara
bersamaan. Salah satu contoh paltform ini adalah Cilk++.
1.3.5
Aplikasi Pengujian
Membahas tentang aplikasi yang digunakan
dalam pengujian algortima paralel yaitu perkalian matrik dan pengurutan data.
1.3.5.1
Perkalian Matriks
Perkalian
matriks adalah sebuah operasi dasar pada berbagai aplikasi aljabar linier.
Perkalian matrik digunakan di banyak penelitian yang berhubungan dengan
pengujian kinerja komputasi paralel. Ukuran-ukuran matriks yang digunakan
merupakan range sampel pengujian algoritma paralel.
Untuk mengalikan dua matriks n x n digunakan
algoritma rekursif. Misal matriks C adalah hasil perkalian matriks A dan
matriks B seperti ditunjukkan oleh Persamaan 1.1 maka operasi yang dilakukan
adalah 8 perkalian dan 4 penjumlahan dari submatriks (n/2) x (n/2).
1.3.5.1
Pengurutan Data (Sorting)
Pengurutan
data (sorting) adalah operasi sederhana yang melibatkan iterasi yang
besarnya tergantung pada jumlah dan komposisi datanya. Operasi ini juga
digunakan dalam berbagai penelitian sebagai aplikasi pengujian komputasi
paralel. Panjang rangkaian data acak yang digunakan merupakan range
sampel pengujian algoritma paralel. Ilustrasi sorting abjad ditunjukkan
pada Gambar 1.9.
Algortima
sorting yang dikenal ada beberapa di antaranya : insertion sort, merge
sort, dan quick sort. Adapun secara umum algoritma sorting
menggunakan prinsip divide and conquer.
1.3.6
Algoritma
Serial Aplikasi Pengujian
Kedua aplikasi
tersebut biasa dikerjakan secara serial (sekuensial) dengan algortima seperti
terlihat pada Gambar 1.10 dan Gambar 1.11. Dari algoritma tersebut diperoleh
jumlah operasi untuk aplikasi perkalian matriks yang harus diproses adalah
berjumlah n x n x n perkalian dan n penjumlahan atau total n3 + n2 operasi.
Sedangkan
untuk aplikasi sorting jumlah operasi yang harus diproses adalah
berjumlah n log n (dengan asumsi menggunakan algoritma quick sort).
2.1.
Kontribusi Parallel
Processing
Parallel Processing 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) dan lain lain.
2.1.1
Bioinformatika
Bioinformatika adalah ilmu yang
mempelajari penerapan teknik komputasional untuk mengelola dan menganalisis
informasi biologis. Bidang ini mencakup penerapan metode-metode matematika,
statistika, dan informatika untuk memecahkan masalah-masalah biologis, terutama
dengan menggunakan sekuens DNA dan asam amino serta informasi yang berkaitan
dengannya. Contoh topik utama bidang ini meliputi basis data untuk mengelola
informasi biologis, penyejajaran sekuens (sequence alignment), prediksi
struktur untuk meramalkan bentuk struktur protein maupun struktur sekunderRNA,
analisis filogenetik, dan analisis ekspresi gen.
Bioinformatika adalah teknologi
pengumpulan, penyimpanan, analisis, interpretasi, penyebaran dan aplikasi dari
data-data biologi molekul. Perangkat utama Bioinformatika adalah software dan
didukung oleh kesediaan internet dan server World Wide Web (WWW).
Dengan Bioinformatika, data-data yang
dihasilkan dari proyek genom dapat disimpan dengan teratur dalam waktu yang
singkat dengan tingkat akurasi yang tinggi serta sekaligus dianalisa dengan
program-program yang dibuat untuk tujuan tertentu. Sebaliknya Bioinformatika
juga mempercepat penyelesaian proyek genom karena Bioinformatika memberikan
program-program yang diperlukan untuk proses pembacaan genom ini.
Dalam dunia kedokteran, keberhasilan
proyek genom ini membuka kemungkinan luas untuk menangani berbagai penyakit
genetik serta memprediksi resiko terkena penyakit genetik. Juga dapat digunakan
untuk mengetahui respon tubuh terhadap obat sehingga efektivitas pengobatan
bisa ditingkatkan.
Karena Bioinformatika merupakan suatu
bidang interdisipliner, maka Bioinformatika juga tidak bisa berdiri sendiri dan
harus didukung oleh disiplin ilmu lain yang mengakibatkan saling bantu dan
saling menunjang sehingga bermanfaat untuk kepentingan manusia. Bidang yang
terkait dengan Bioinformatika diantaranya adalah Biophysics, Computational
Biology, Medical Informatics, Cheminformatics, Genomics, Mathematical Biology,
Proteomics, Pharmacogenomics.
Meskipun merupakan kajian yang masih
baru, Indonesia telah berperan aktif dalam mengembangkan Bioinformatika ini.
Ada sejumlah pakar yang telah mengikuti perkembangan Bioinformatika ini, antara
lain para peneliti dalam Lembaga Biologi Molekul Eijkman
2.1.2
Perkembangan Parallel Processing di Indonesia
Di Indonesia, usaha untuk membangun infrastruktur
mesin paralel sudah dimulai sejak era 90-an, meski belum pada tahap serius dan
permanen. Namun untuk pemrograman paralel sudah sejak awal menjadi satu
mata-kuliah wajib di banyak perguruan tinggi terkait. Baru pada tahun 2005
dimulai pembuatan infrastruktur mesin paralel permanen, misalnya yang
dikembangkan oleh Grup Fisika Teoritik dan Komputasi di P2 Fisika LIPI.
Didorong oleh perkembangan pemrograman paralel yang lambat, terutama terkait
dengan sumber daya manusia (SDM) yang menguasainya, mesin paralel LIPI ini
kemudian dibuka untuk publik secara cuma-cuma dalam bentuk LIPI Public Cluster
(LPC). Saat ini LPC telah dikembangkan lebih jauh menjadi gerbang komputasi
GRID di Indonesia dengan kerjasama global menjadi IndoGRID.
Pada tahun berikutnya, dengan dukungan dana dari
proyek Inherent Dikti, Fasilkom UI juga membangun mesin paralel[4]. Sementara
itu pada tahun 2009, ITB membuat kluster hibrid CPU dan GPU yang pertama di
Indonesia dengan kemampuan hingga 60 inti CPU dan 1920 inti GPU.
Download makalah : Makalah Softskill Pengantar Komputasi Modern
DAFTAR PUSTAKA
- http://lib.ui.ac.id/file?file=digital/134234-T%2027918-Studi%20kinerja-Literatur.pdf
- http://dewi_anggraini.staff.gunadarma.ac.id/Downloads/files/43470/10+Parallel+Processing.pdf
- https://id.wikipedia.org/wiki/Komputasi_paralel
- http://coretanmuvi.blogspot.co.id/2012/03/paralel-processing.html
- https://dikky12.wordpress.com/2011/04/22/bioinformatika/
- https://dikky12.wordpress.com/2011/04/01/parallel-processing/
- http://gina-itsme.blogspot.co.id/2013/06/parallel-processing-dan-hubungan-dengan.html
- http://rakhapermanasblog.blogspot.co.id/2015/05/parallel-processing-dan-bioinformatika.html?view=snapshot&m=1
