Pengantar Komputasi Modern

Andiko Bayu                                       Parallelism Concept

Jeffry Akbar                                        Pengantar Thread Programming

Andre Purwandono                        Pengantar Massage Passing, OpenMP

Alija Nur Farizi                                   Pengantar pemrograman CUDA GPU

Paralelism Concept

Pengertian Komputasi Parallel

Komputasi parallel 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 mengelolah data dalam jumlah besar (di industri keuangan, bioinformatika, dll) ataupun karena tuntutan proses komputasi yang banyak.

Secara prinsip komputer parallel membagi permasalahan sehingga menjadi lebih kecil untuk dikerjakan oleh setiap prosesor (CPU) dalam waktu yang bersamaan/simultan (concurrent).

Komputasi parallel membutuhkan:

-          Algoritma

-          Bahasa pemrograman

-          Compiler

Pemrograman Parallel

Di dalam komputasi parallel ada yang dinamakan dengan pemrograman parallel. Pemrograman parallel adalah teknik pemrograman komputer yang memungkinkan eksekusi perintah/operasi secara bersamaan, baik dalam komputer satu (prosesor tunggal) ataupun banyak (prosesor ganda dengan mesin parallel) CPU.

Tujuan utama dari pemrograman parallel adalah untuk meningkatkan performa komputasi. Semakin banyak hal yang bisa dilakukan secara bersamaan, semakin banyak pekerjaan yang bisa diselesaikan.

Bahasa Pemrograman pada Pemrograman Parallel

Message Passing Interface (MPI) adalah sebuah standard pemrograman yang memungkinkan pemrogram untuk memuat sebuah aplikasi yang dapat dijalankan secara parallel dengan spesifikasi library pemrograman untuk meneruskan pesan (message passing), yang diajukan sebagai standar oleh berbagai komite dari vendor, pelaksana dan pemakai. Message Passing Interface bertugas untuk mengirim data antar komputer di dalam sistem parallel (biasanya disebut dengan node atau host).

Kegunaan MPI:

-          Menyediakan fungsi-fungsi untuk menukar pesan.

-          Menulis kode parallel secara portable.

-          Mendapatkan performa yang tinggi dalam pemrograman parallel.

-          Menghadapi permasalahan yang melibatkan hubungan data irregular atau dinamis yang tidak begitu cocok dengan model data parallel.

Private Virtual Machine adalah perangkat lunak yang memungkinkan sekumpulan komputer yang heterogen terlihat seperti satu sistem komputer parallel dan dapat digunakan sebagai sebuah sumber daya komputasi yang koheren.

PVM terdiri dari beberapa komponen yaitu:

-          PVM daemon

Daemon merupakan semacam program yang berjalan di “belakang” dan biasanya menangani program dari klien. Komponen ini berada pada setiap komputer yang terhubung dalam virtual machine.

-          PVM libraries

Komponen ini berisi rutin-rutin antarmuka pemakai PVM untuk melakukan pengiriman pesan, pembuatan proses, koordinasi proses dan modifikasi virtual machine.

Arsitektur Komputer Parallel

Berdasarkan jumlah dan prinsip kerja prosesor pada komputer parallel, A.J. Van der Steen dan J.Donggara menyebutkan terdapat empat arsitektur utama komputer parallel menurut Flynn (1972) yaitu :

                     I.            SISD (Single Instruction – Single Data)

Komputer ini memiliki hanya satu prosesor dan satu instruksi yang dieksekusi secara serial. Komputer ini adalah tipe komputer konvensional.

                   II.            SIMD (Single Instruction – Multiple Data)

Komputer ini memiliki lebih dari satu prosesor, tetapi hanya mengeksekusi satu instruksi secara parallel pada data yang berbeda pada level lock-step. Komputer vektor adalah salah satu komputer yang meggunakan arsitektur ini.

                 III.            MISD (Multiple Instructions – Single Data)

Komputer ini memiliki satu prosesor dan mengeksekusi beberapa instruksi secara parallel tetapi praktiknya tidak ada komputer yang dibangun dengan arsitektur ini karena sistemnya tidak mudah dipahami.

                IV.            MIMD (Multiple Instructions – Multiple Data)

Komputer ini memiliki lebih dari satu prosesor dan mengeksekusi lebih dari satu instruksi secara parallel. Tipe komputer ini yang paling banyak digunakan untuk membangun komputer parallel.

Pengantar Thread Programming

Dalam pemrograman komputer, sebuah thread adalah informasi terkait dengan penggunaan sebuah program tunggal yang dapat menangani beberapa pengguna secara bersamaan. Dari program point-of-view, sebuah thread adalah informasi yang dibutuhkan untuk melayani satu pengguna individu atau permintaan layanan tertentu. Jika beberapa pengguna menggunakan program atau permintaan bersamaan dari program lain yang sedang terjadi, thread yang dibuat dan dipelihara untuk masing-masing proses. Thread memungkinkan program untuk mengetahui user sedang masuk didalam program secara bergantian dan akan kembali ma
suk atas nama pengguna yang berbeda. Salah satu informasi thread disimpan dengan cara menyimpannya di daerah data khusus dan menempatkan alamat dari daerah data dalam register. Sistem operasi selalu menyimpan isi register saat program interrupted dan restores ketika memberikan program kontrol lagi.

Sebagian besar komputer hanya dapat mengeksekusi satu instruksi program pada satu waktu, tetapi karena mereka beroperasi begitu cepat, mereka muncul untuk menjalankan berbagai program dan melayani banyak pengguna secara bersamaan. Sistem operasi komputer memberikan setiap program "giliran" pada prosesnya, maka itu memerlukan untuk menunggu sementara program lain mendapat giliran. Masing-masing program dipandang oleh sistem operasi sebagai suatu tugas dimana sumber daya tertentu diidentifikasi dan terus berlangsung. Sistem operasi mengelola setiap program aplikasi dalam sistem PC (spreadsheet, pengolah kata, browser Web) sebagai tugas terpisah dan memungkinkan melihat dan mengontrol item pada daftar tugas. Jika program memulai permintaan I / O, seperti membaca file atau menulis ke printer, itu menciptakan thread. Data disimpan sebagai bagian dari thread yang memungkinkan program yang akan masuk kembali di tempat yang tepat pada saat operasi I / O selesai. Sementara itu, penggunaan bersamaan dari program diselenggarakan pada thread lainnya. Sebagian besar sistem operasi saat ini menyediakan dukungan untuk kedua multitasking dan multithreading. Mereka juga memungkinkan multithreading dalam proses program agar sistem tersebut disimpan dan  menciptakan proses baru untuk setiap thread.

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 protocol 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.

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.

Model Multi-Threading

      1.  Many-to-One

          -  Memetakan beberapa thread tingkatan pengguna ke sebuah thread tingkatan kernel.

          -  Pengaturan thread dilakukan dalam ruang pengguna, sehingga efisien.

          -  Hanya satu thread pengguna yang dapat mengakses thread kernel pada satu saat.

      2.   One-to-One

           - Memetakan setiap thread tingkatan pengguna ke thread kernel.

           - Model ini menyediakan lebih banyak concurrency dibandingkan model Many-to-One.

      3.  Many-to-Many

           -  Mengelompokkan banyak thread pengguna untuk dipetakan ke thread kernel yang jumlahnya lebih sedikit atau sama dengan tingkatan pengguna.

           - Mengijinkan sistem operasi untuk membuat sejumlah thread kernel.

Thread cancellation

Thread cancellation/ pembatalan thread ialah pemberhentian thread sebelum tugasnya selesai. Misalnya jika dalam program Java hendak mematikan Java Virtual Machine (JVM). Sebelum JVM dimatikan, maka seluruh thread yang berjalan harus dihentikan terlebih dahulu.

Thread yang akan diberhentikan disebut sebagai target thread. Pembatalan Thread terdiri dari 2 jenis:

     Asynchronous cancellation: suatu thread seketika itu juga memberhentikan target thread.

     Deffered cancellation: target thread secara perodik memeriksa apakah dia harus berhenti, cara ini memperbolehkan target thread untuk memberhentikan dirinya sendiri secara terurut.

Pengantar Massage Passing, OpenMP

Message Passing

Message passing adalah proses pengiriman data, dimana data dari suatu memori disalin ke memori pada prosesor lain. Karena proses pengiriman datanya antar memori lokal maka teknik message passing biasanya  digunakan untuk model komputasi paralel dengan memori terdistribusi. Dalam model ini, proses atau objek dapat mengirim dan menerima pesan (sinyal, fungsi, struktur data kompleks, atau paket data) ke proses atau objek lain.

Operasi dasar yang dibutuhkan untuk mendukung paradigma message passing adalah send dan receive. Operasi pengirim membutuhkan proses pengiriman untuk menspesifikasikan  lokasi data, ukuran, tipe dan tujuan. Operasi penerima harus melakukan penyesuaian dengan operasi pengirim. Konsep message passing membuat lebih mudah untuk membangun sistem yang memodelkan atau mensimulasikan masalah dunia nyata.

Terdapat dua metode dalam pengiriman pesan yaitu :

Synchronous Message Passing

Sistem pengiriman pesan secara sinkron mengharuskan pengirim dan penerima untuk menunggu satu sama lain saat mentransfer pesan. Pengirim menunggu untuk mengirim pesan sampai penerima siap untuk menerima pesan. Oleh karena itu tidak ada buffering. Selain itu pengirim tidak bisa mengirim pesan untuk dirinya sendiri. (contoh: chatting)

Ansynchronous Message Passing

Sedangkan dalam komunikasi asinkron pengirim dan penerima tidak saling menunggu dan dapat melakukan perhitungan sendiri saat pengiriman pesan sedang dilakukan. Pengirim akan mengirim pesan kapanpun dia mau. Pengirim tidak peduli ketika penerima belum siap untuk menerima pesan. Oleh karena itu diperlukan buffering untuk menampung pesan sementara sampai penerima siap menerima pesan. Selain itu pengirim dapat pesan untuk dirinya sendiri.

Selain berdasarkan metode pengiriman pesan diatas, pengiriman pesan (message passing) dapat dibedakan berdasarkan jumlah penerima pesan yaitu: Point to Point dan Broadcast. Perbedaan mendasar keduanya adalah jumlah penerima yang menerima pesan. Pada Point to Point penerimanya tunggal sedangkan pada broadcast jumlah penerimanya banyak. (contoh mail, bulletin board, dll).

OpenMP (Open Multiprocessing)

OpenMP merupakan standar yang digunakan untuk pemrograman paralel multithreading pada arsitektur shared memory. OpenMP adalah sebuah antarmuka pemrograman aplikasi (API) untuk menulis aplikasi multithread, berupa satu set direktif compiler dan library untuk pemrograman aplikasi paralel yang menyederhanakan penulisan program multithread pada C, C++, dan Fortran pada berbagai arsitektur, termasuk Unix dan Microsoft Windows platform. Program multithread dapat ditulis dalam berbagai cara. Beberapa diantaranya memungkinkan untuk melakukan interaksi yang kompleks antar thread. OpenMP mencoba untuk memberikan kemudahan pemrograman serta membantu dalam menghindari kesalahan program, melalui pendekatan terstruktur. Pendekatan ini dikenal sebagai model pemrograman fork-join. OpenMP dikelola oleh nirlaba teknologi konsorsium OpenMP Arsitektur Review Board (ARB atau OpenMP), bersama-sama didefinisikan oleh sekelompok perangkat keras komputer utama dan vendor perangkat lunak, termasuk AMD, IBM, Intel, Cray, HP, Fujitsu, Nvidia, NEC, Microsoft, Texas Instruments, Oracle Corporation, dan banyak lagi.

Pengantar pemrograman CUDA GPU

CUDA (Compute Unified Device Architecture) adalah suatu skema yang dibuat oleh NVIDIA agar NVIDIA selaku GPU (Graphic Processing Unit) mampu melakukan komputasi tidak hanya untuk pengolahan grafis namun juga untuk tujuan umum. Jadi, dengan CUDA, kita dapat memanfaatkan cukup banyak processor yang dimiliki oleh NVIDIA untuk berbagai perhitungan. GPU yang ada  saat ini seperti ATI pun sudah memiliki banyak processor di dalamnya. Pada ATI, skema yang mereka bangun disebut ATI Stream. Saat ini pemrograman paralel menjadi sangat penting karena kebutuhan kemampuan komputasi komputer yang terus meningkat seperti kemampuan multitasking dan pengolahan grafis yang andal. Metode saat ini dalam peningkatan peforma komputer juga berbeda dengan masa lampau dimana peningkatan clock dari processor yang diutamakan.  

Peningkatan clock juga dibatasi oleh kemampuan fisik dari perangkat digital yaitu persoalan daya dan panas. Pada 2005 berbagai industri komputer mulai menawakan komputer dengan beberapa core mulai dari 2, 3, 4, 6, dst. Pada awal perkembangan GPU dengan banyak core, pemanfaatan GPU hanya dapat dilakukan dengan antarmuka seperti OpenGL dan DirectX dimana antarmuka tersebut dikhususkan hanya untuk pengolahan grafis. 

Seri-seri terbaru dari NVIDIA saat ini telah mendukung CUDA tepatnya keluaran setelah tahun 2006.  Untuk daftar dari seri yang mendukung CUDA dapat dilihat pada http://nvidia.com/cuda. Sebagai tahap awal dalam belajar pemrograman paralel dengan memanfaatkan CUDA sebaiknya menggunakan bahasa pemrograman C atau C++. CUDA C telah menjadi bahasa pemrograman khusus pertama yang dikembangkan oleh suatu perusahaan GPU untuk memfasilitasi general-purpose computing pada GPU. Beberapa hal yang perlu dipersiapkan dalam penggunaan CUDA C untuk membuat suatu aplikasi adalah sebagai berikut.

Kebutuhan seperti toolkit dan driver dapat diunduh di

http://developer.nvidia.com/cuda-downloads. CUDA C menyediakan kebutuhan tersebut untuk Windows, Linux, dan Mac. Jika telah memasang CUDA toolkit pada komputer Anda maka akan ada aplikasi compiler yang dapat Anda gunakan yaitu nvcc. Selain itu, jika Anda menggunakan Windows sebaiknya Anda juga memasang Visual Studio untuk kemudahan pembuatan aplikasi dan ada program bernama cl.exe dari Visual Studio yang diperlukan dalam kompilasi.

Hal khusus dalam kode program yang menggunakan CUDA C adalah adanya kernel call. Sebagai contoh adalah cuplikan kode berikut.

#include

__global__ void kernel( void ) {

}

int main( void ) {

    kernel<<<1>>>();

    printf( "Hello, World!\n" );

    return 0;

}

Penambahan variabel __global__ pada fungsi kernel()berfungsi untuk menunjukkan pada compiler bahwa program tersebut dikompilasi untuk berjalan pada device dan bukan pada host. Selanjutnya kita akan melihat contoh program lagi dimana terdapat bagian pengiriman nilai.

#include

#include "book.h"

__global__ void add( int a, int b, int *c ) {

    *c = a + b;

}

int main( void ) {

    int c;

    int *dev_c;

    HANDLE_ERROR( cudaMalloc( (void**)&dev_c, sizeof(int) ) );

    add<<<1>>>( 2, 7, dev_c );

    HANDLE_ERROR( cudaMemcpy( &c, dev_c, sizeof(int), cudaMemcpyDeviceToHost   ) );

    printf( "2 + 7 = %d\n", c );

    cudaFree( dev_c );

    return 0;

}

Variabel dev_c adalah variabel yang akan digunakan untuk menampung nilai yang akan dilewatkan dari host ke  device dan setelah itu nilai tersebut akan diambil dari device dan dikirim ke host. Metode pengalokasian memori memanfaatkan fungsi cudaMalloc() yang fungsinya mirip malloc() pada C. Untuk mengambil nilai dari device memanfaakan fungsi cudaMemcpy().

Sekarang bagaimanakah  paralel pada GPU? Kita lihat program penjumlahan vektor berikut ini.

#include "../common/book.h"

#define N 10

__global__ void add( int *a, int *b, int *c ) {

 int tid = blockIdx.x;

 // handle the data at this index

 if (tid < N) {

  c[tid] = a[tid] + b[tid];

 }

}

int main( void ) {

int a[N], b[N], c[N];

int *dev_a, *dev_b, *dev_c;

// allocate the memory on the GPU

HANDLE_ERROR( cudaMalloc( (void**)&dev_a, N * sizeof(int) ) );

HANDLE_ERROR( cudaMalloc( (void**)&dev_b, N * sizeof(int) ) );

HANDLE_ERROR( cudaMalloc( (void**)&dev_c, N * sizeof(int) ) );

// fill the arrays 'a' and 'b' on the CPU

for (int i = 0; i < N; i++) { a[i] = -i; b[i] = i * i; }

// copy the arrays 'a' and 'b' to the GPU

HANDLE_ERROR( cudaMemcpy( dev_a, a, N * sizeof(int), cudaMemcpyHostToDevice ) );

HANDLE_ERROR( cudaMemcpy( dev_b, b, N * sizeof(int), cudaMemcpyHostToDevice ) );

add<<< N,1 >>>( dev_a, dev_b, dev_c );

// copy the array 'c' back from the GPU to the CPU

HANDLE_ERROR( cudaMemcpy( c, dev_c, N * sizeof(int), cudaMemcpyDeviceToHost ) );

// display the results

for (int i = 0; i < N; i++) { printf( "%d + %d = %d\n", a[i], b[i], c[i] ); }

// free the memory allocated on the GPU

cudaFree( dev_a ); cudaFree( dev_b ); cudaFree( dev_c ); return 0;

Program yang dapat dijadikan paralel adalah program yang digunakan untuk menghasilkan satu nilai dimana nilai keluarannya tersebut tidak dipengaruhi oleh nilai lain dari komputasi dengan fungsi yang sama. Contohnya adalah dalam program penjumlahan vektor ini. Dalam penjumlahan vektor nilai c(0)adalah penjumlahan antara a(0) dan b(0) dan tidak dipengaruhi oleh nilai c(1), c(2), dst.

Pada program ini juga terdapat bagian yang bertuliskan add<<<N,1>>>. Bagian ini menunjukkan bahwa program memanfaatkan N buah thread. Nilai N buah ini diperoleh dari :

 N buah block x 1 threadper block

Untuk menentukan jumlah thread yang akan digunakan dapat  diatur dengan mengubah kedua nilai tersebut. Fungsi add<<<1,N>>> akan menghasilkan penggunaan jumlah thread yang sama dengan fungsi ini add<<<N,1>>>. Jumlahblock dan thread per block tentu saja terbatas dan untuk setiap device akan berbeda jumlahnya. Anda dapat melihatnya menggunakan fungsi properti dari CUDA. Program di atas juga hanya menggunakan 1 thread pada setiap block. Oleh karena itu identifikasi posisi cukup dengan mengambil posisi block yang menjalankan komputasi dengan memanggil variabel blockIdx.x.