Komputasi Paralel
Komputasi
Komputasi adalah algoritma yang
digunakan untuk menemukan suatu cara dalam memecahkan masalah dari sebuah data
input. Data input disini adalah sebuah masukan yang berasal dari luar
lingkungan sistem. Komputasi ini merupakan bagian dari ilmu komputer berpadu
dengan ilmu matematika. Secara umum ilmu komputasi adalah bidang ilmu yang
mempunyai perhatian pada penyusunan model matematika dan teknik penyelesaian
numerik serta penggunaan komputer untuk menganalisis dan memecahkan
masalah-masalah ilmu (sains).
Komputasi Modern
Komputasi modern bisa disebut sebuah
konsep sistem yang menerima intruksi-intruksi dan menyimpannya dalam sebuah
memory, memory disini bisa juga dari memory komputer. Oleh karena pada saat ini
kita melakukan komputasi menggunakan komputer maka bisa dibilang komputer
merupakan sebuah komputasi modern. Konsep ini pertama kali digagasi oleh John
Von Neumann (1903-1957). Dalam kerjanya komputasi modern menghitung dan mencari
solusi dari masalah yang ada, dan perhitungan yang dilakukan itu meliputi:
1. Akurasi
2. Kecepatan
3. ProblemVolume
Besar
4. Modelling
5. Kompleksitas
Paralel Processing
Pemrosesan paralel (parallel
processing) adalah penggunakan lebih dari satu CPU untuk menjalankan sebuah
program secara simultan. Idealnya, parallel processing membuat program berjalan
lebih cepat karena semakin banyak CPU yang digunakan.
Pemrograman
paralel adalah teknik pemrograman komputer yang
memungkinkan eksekusi perintah/operasi secara bersamaan (komputasi paralel),
baik dalam komputer dengan satu (prosesor tunggal) ataupun banyak (prosesor
ganda dengan mesin paralel) CPU. Bila komputer
yang digunakan secara bersamaan tersebut dilakukan oleh komputer-komputer
terpisah yang terhubung dalam suatu jaringan komputer lebih sering istilah yang digunakan adalah sistem terdistribusi (distributed computing).
TUJUAN PARALLEL
PROCESSING
Tujuan utama dari pemrosesan paralel
adalah untuk meningkatkan performa komputasi. Semakin banyak hal yang bisa
dilakukan secara bersamaan (dalam waktu yang sama), semakin banyak pekerjaan
yang bisa diselesaikan.
Jadi Komputasi paralel adalah salah satu teknik melakukan komputasi secara bersamaan dengan memanfaatkan beberapa komputer secara bersamaan. Biasanya diperlukan saat kapasitas yang diperlukan sangat besar, baik karena harus mengolah data dalam jumlah besar ataupun karena tuntutan proses komputasi yang banyak. Untuk melakukan aneka jenis komputasi paralel ini diperlukan infrastruktur mesin paralel yang terdiri dari banyak komputer yang dihubungkan dengan jaringan dan mampu bekerja secara paralel untuk menyelesaikan satu masalah. Untuk itu diperlukan aneka perangkat lunak pendukung yang biasa disebut sebagai middleware yang berperan untuk mengatur distribusi pekerjaan antar node dalam satu mesin paralel. Selanjutnya pemakai harus membuat pemrograman paralel untuk merealisasikan komputasi.
Hubungan antara
Komputasi Modern dengan Paralel Processing
Hubungan antara komputasi modern dan
parallel processing sangat berkaitan, karena penggunaan komputer saat ini atau
komputasi dianggap lebih cepat dibandingkan dengan penyelesaian masalah secara
manual. Dengan begitu peningkatan kinerja atau proses komputasi semakin
diterapkan, dan salah satu caranya adalah dengan meningkatkan kecepatan
perangkat keras. Dimana komponen utama dalam perangkat keras komputer adalah processor.
Sedangkan parallel processing adalah penggunaan beberapa processor
(multiprocessor atau arsitektur komputer dengan banyak processor) agar kinerja
computer semakin cepat.
Kinerja komputasi dengan menggunakan
paralel processing menggunakan dan memanfaatkan beberapa komputer atau CPU
untuk menemukan suatu pemecahan masalah dari masalah yang ada. Sehingga dapat
diselesaikan dengan cepat daripada menggunakan satu komputer saja. Komputasi
dengan paralel processing akan menggabungkan beberapa CPU, dan membagi-bagi
tugas untuk masing-masing CPU tersebut. Jadi, satu masalah terbagi-bagi
penyelesaiannya. Tetapi ini untuk masalah yang besar saja, komputasi yang
masalah kecil, lebih murah menggunakan satu CPU saja.
Embarasingly Parallel adalah pemrograman paralel yang digunakan
pada masalah-masalah yang bisa diparalelkan tanpa membutuhkan komunikasi satu
sama lain. Sebenarnya pemrograman ini bisa dibilang sebagai pemrograman paralel
yang ideal, karena tanpa biaya komunikasi, lebih banyak peningkatan kecepatan
yang bisa dicapai.
Taksonomi dari model pemrosesan paralel dibuat berdasarkan alur instruksi dan alur data yang digunakan:
Taksonomi dari model pemrosesan paralel dibuat berdasarkan alur instruksi dan alur data yang digunakan:
1. - SISD Single Instruction
Single Datapath, ini prosesor tunggal,yang bukan paralel
2. - SIMD Single Instruction
Multiple Datapath, alur instruksi yang sama dijalankan terhadap banyak alur
data yang berbeda. Alur instruksi di sini kalau tidak salah maksudnya ya
program komputer itu. trus datapath itu paling ya inputnya, jadi inputnya lain-lain
tapi program yang digunakan sama
3. - MIMD Multiple Instruction
Multiple Datapath, alur instruksinya banyak, alur datanya juga banyak, tapi
masing-masing bisa berinteraksi
4. - MISD Multiple Instruction
Single Datapath, alur instruksinya banyak tapi beroperasi pada data yang
sama.
Contoh
pemrograman paralel dengan 3 metode
1. MPI
(Message Passing Interface)
MPI
atau Mesage Passing Interface adalah spesifikasi yang
perlu diterapkan pengembang dan pengguna pemrograman parallel.
Secara umum,
pemrograman parallel menggunakan spesifikasi MPI membutuhkan tiga tahapan. Hal
ini terlepas dari kebutuhan lain terkait eksekusi seperti mem-boot layanan
ini. Ketiganya adalah:
1.
Inisialisasi
2.
Dekomposisi,
distribusi dan pengambilan kembali sub pekerjaan
3.
De-inisialisasi
Bagaimana ketiganya
diterapkan dalam C/C++, berikut adalah contoh prrogram sederhana.
Program berikut ini
hanya bertugas menampilkan karakter/informasi ke layar oleh masing-masing node
yang terlibat dalam komunkasi MPI. Kode sumber pertama dibuat dalam C.
#include <stdio.h>
#include
"mpi.h"
int main(int argc, char
** argv) {
int
p;
int
id;
double
wtime;
//Inisialisasi
MPI
MPI_Init(&argc,&argv);
//Mendapatkan
id dan jumlah proses
MPI_Comm_size(MPI_COMM_WORLD,&p);
MPI_Comm_rank(MPI_COMM_WORLD,&id);
wtime=MPI_Wtime();
//Mendistribusi
pekerjaan
if(id==0)
{
printf("MPI
Hello - Master Process\n");
printf("
C / MPI version\n");
printf("
An example program\n\n");
printf("
The number of process = %d\n",p);
}
else
{
printf("Process
%d says 'Hello World!'\n",id);
}
if(id==0)
{
printf("\n");
printf("Hello
MPI - Master Process:\n");
printf("
Normal end of execution: 'Goodbye World!'\n\n");
wtime=MPI_Wtime()
- wtime;
printf("Elapsed
wall clock time = %g seconds\n", wtime);
}
//De-inisialisasi
MPI_Finalize();
return
0;
}
2. openMP
OpenMP (Open Multi-Processing) adalah
sebuah API (application programming interface) yang mendukung multi-platform
memori bersama pemrograman multiprocessing dalam C, C + +, dan Fortran, pada
arsitektur prosesor paling dan sistem operasi, termasuk Linux, Unix, AIX,
Solaris, Mac OS X, dan Microsoft Windows platform. Ini terdiri dari satu set
arahan kompiler, rutinitas perpustakaan, dan variabel lingkungan yang
mempengaruhi perilaku saat run-time
Contoh model program
parallel openMP
#include <omp.h>
|
#include <sdl.h>
|
#include
<windows.h>
|
|
#include <math.h>
|
void __putpixel(SDL_Surface*
buffer, int x, int y, Uint32 color)
|
{
|
|
int bpp =
buffer->format->BytesPerPixel;
|
/*
Here p is the address to the pixel we want to set */
|
|
Uint8
*p = (Uint8 *)buffer->pixels + y * buffer->pitch + x * bpp;
|
switch(bpp)
{
|
case 1:
|
|
*p
= color;
|
break;
|
|
case 2:
|
|
*(Uint16
*)p = color;
|
break;
|
|
case 3:
|
|
if(SDL_BYTEORDER
== SDL_BIG_ENDIAN) {
|
p[0]
= (color >> 16) & 0xff;
|
p[1]
= (color >> 8 ) & 0xff;
|
p[2]
= color & 0xff;
|
|
}
else {
|
p[0]
= color & 0xff;
|
|
p[1]
= (color >> 8 ) & 0xff;
|
p[2]
= (color >> 16) & 0xff;
|
|
}
|
break;
|
|
case 4:
|
|
*(Uint32
*)p = color;
|
break;
|
|
}
|
}
|
|
Uint32
__getpixel(SDL_Surface* buffer, int x, int y)
|
|
{
|
int bpp =
buffer->format->BytesPerPixel;
|
|
/*
Here p is the address to the pixel we want to retrieve */
|
Uint8
*p = (Uint8 *)buffer->pixels + y * buffer->pitch + x * bpp;
|
|
switch(bpp)
{
|
|
case 1:
|
return *p;
|
|
case 2:
|
|
return *(Uint16 *)p;
|
case 3:
|
if(SDL_BYTEORDER
== SDL_BIG_ENDIAN)
|
|
return p[0] << 16 | p[1]
<< 8 | p[2];
|
else
|
|
return p[0] | p[1] << 8
| p[2] << 16;
|
case 4:
|
return *(Uint32 *)p;
|
|
default:
|
|
return 0;
/* shouldn't happen, but avoids warnings */
|
}
|
|
}
|
int WINAPI
WinMain(HINSTANCE hInst, HINSTANCE hPrev, LPSTR lpCmdLine, intnShowCmd)
|
{
|
|
SDL_Surface
*tmp, *screen;
|
|
|
int i, j, w, h;
|
int nThread, tid;
|
|
Uint32
starttick;
|
SDL_Event
evt;
|
|
int done = 0;
|
FILE *deb =
fopen("debug.txt", "w");
|
|
|
fprintf(deb,
"start \n");
|
SDL_Init(SDL_INIT_VIDEO);
|
atexit(SDL_Quit);
|
|
tmp
= SDL_LoadBMP("alfa256.bmp");
|
w
= tmp->w;
|
h
= tmp->h;
|
screen
= SDL_SetVideoMode(w, h, tmp->format->BitsPerPixel,
SDL_SWSURFACE|SDL_ANYFORMAT);
|
|
SDL_BlitSurface(tmp,
NULL, screen, NULL);
|
SDL_FreeSurface(tmp);
|
|
tmp
= screen;
|
|
|
if ( SDL_MUSTLOCK(tmp) ) {
|
if ( SDL_LockSurface(tmp)
< 0 ) {
|
|
fprintf(stderr,
"Can't lock screen: %s\n", SDL_GetError());
|
return;
|
|
}
|
}
|
|
|
fprintf(deb,
"starting block \n");
|
|
starttick
= SDL_GetTicks();
|
#pragma
omp parallel shared(tmp, w, h)
|
|
{
|
Uint8
r, g, b, a, tmpi;
|
|
int i,j;
|
|
|
#pragma
omp for schedule(dynamic) nowait
|
for (j=0; j<h; ++j){
|
|
for (i=0; i<w; ++i){
|
SDL_GetRGBA(__getpixel(tmp,
i, j), tmp->format, &r, &g, &b, &a);
|
|
tmpi
= (Uint8)round(0.299 * r + 0.587 * g + 0.114 * b);
|
tmpi
= (tmpi>128)?255:0;
|
|
__putpixel(tmp,
i, j, SDL_MapRGBA(tmp->format, tmpi, tmpi, tmpi, a));
|
}
|
|
|
SDL_UpdateRect(screen,
0, 0, 0, 0);
|
|
}
|
}
|
|
|
SDL_UpdateRect(screen,
0, 0, 0, 0);
|
|
fprintf(deb,
"end block %d\n", SDL_GetTicks()-starttick);
|
|
|
if ( SDL_MUSTLOCK(tmp) ) {
|
SDL_UnlockSurface(tmp);
|
|
}
|
|
|
while(!done){
|
while(SDL_PollEvent(&evt)){
|
|
switch(evt.type){
|
case SDL_QUIT:
|
|
done
= 1;
|
break;
|
|
}
|
}
|
|
}
|
|
|
fclose(deb);
|
|
SDL_SaveBMP(tmp,
"alfagrey.bmp");
|
return 0;
|
}
|
3. POSIX
thread
POSIX Thread, biasanya
disebut sebagai pthreads, adalah
standar POSIX untuk thread. Standar,POSIX.1c, Thread ekstensi (IEEE Std 1003.1c-1995), mendefinisikan sebuah
API untuk menciptakan dan memanipulasi thread.
Implementasi dari API yang
tersedia pada banyak Unix-seperti POSIX-konforman sistem
operasi seperti FreeBSD, NetBSD, OpenBSD, GNU / Linux, Mac
OS X dan Solaris. DR-DOS dan Microsoft Windows implementasi juga ada: dalam subsistem SFU / SUA yang
menyediakan implementasi aslidari sejumlah POSIX API, dan
juga di dalam paket pihak ketiga seperti pthreads-W32, yang mengimplementasikan pthreads di atas ada Windows API.
Contoh Posix thread
#include <stdlib.h>
#include <unistd.h>
#include <stdio.h>
#include
<sys/types.h>
#include
<sys/time.h>
#include
<pthread.h>
#include <time.h>
#define MAX_THREAD
16
/* maximum number of threads */
#define NDIM
1024
/*
number of NDIMs */
double
a[NDIM][NDIM];
double
b[NDIM][NDIM];
double
c[NDIM][NDIM];
struct timeval tvstart,
tvstop;
typedef struct
{
int
id;
/* identification */
int
noproc;
/* process */
int
dim;
/* number of threads */
double
(*a)[NDIM][NDIM],(*b)[NDIM][NDIM],(*c)[NDIM][NDIM];
} parm;
void mm(int me_no, int
noproc, int n, double a[NDIM][NDIM], double b[NDIM][NDIM], double
c[NDIM][NDIM])
{
int
i,j,k;
double
sum;
i=me_no;
while
(i<n) {
for (j = 0; j < n; j++) {
sum = 0.0;
for (k = 0; k < n; k++) {
sum = sum + a[i][k] * b[k][j];
}
c[i][j] = sum;
}
i+=noproc;
}
}
void * worker(void *arg)
{
parm *p = (parm *)
arg;
mm(p->id, p->noproc, p->dim, *(p->a), *(p->b), *(p->c));
}
int main(int argc, char
*argv[])
{
int
j, k, noproc, me_no;
double sum;
double t1, t2;
pthread_t *threads;
parm *arg;
int n,
i;
for (i = 0;
i < NDIM; i++)
for (j = 0; j < NDIM; j++) {
a[i][j] = i + j;
b[i][j] = i + j;
}
if (argc
< 2) {
n = MAX_THREAD;
}
else {
n = atoi(argv[1]);
}
// start the
bechmark timer
gettimeofday(&tvstart, NULL);
threads =
(pthread_t *) malloc(n * sizeof(pthread_t));
arg=(parm
*)malloc(sizeof(parm)*n);
for (i = 0;
i < n; i++) {
arg[i].id = i;
arg[i].noproc = n;
arg[i].dim = NDIM;
arg[i].a = &a;
arg[i].b = &b;
arg[i].c = &c;
pthread_create(&threads[i], NULL, worker, (void *)(arg+i));
}
for (i
= 0; i < n; i++) {
pthread_join(threads[i], NULL);
}
gettimeofday(&tvstop, NULL);
double
t = (tvstop.tv_sec - tvstart.tv_sec) * 1000 +
(tvstop.tv_usec
- tvstart.tv_usec) * 1e-3;
printf("Pthread: %d :
Dim: %d : Time: %f\n", n, NDIM, t);
free(arg);
return
0;
}
Contoh b
Diasumsikan
graf dengan n buah verteks. Diberikan matriks ajasensi
(bertetangga)
mxn dan konstanta positif c, sebuah prosesor dibuat untuk setiap
pewarnaan
graf yang mungkin.
Prosesor
P(i0, i1, i2, …, in-1) mengilustrasikan pewarnaan verteks 0 dengan warna
i0, verteks 1
dengan warna i1 hingga verteks n-1 dengan warna in-1.
Contoh
algoritma pewarnaan graf CREW PRAM Algoritma mendapatkan 2 warna untuk 3 buah vertex
PSEUDOCODE
GRAPH.COLORING
(CREW PRAM):
Global n {Number
of vertices}
c {Number of
colors}
A[1…n][1…n]
{Adjacency matrix}
candidate[1…c][1…c]
… [1…c] {n-dimensional
boolean matrix}
valid {Number of
valid colorings}
j, k
begin
spawn(P(i0,
i1, i2, …, in-1)) where 0 £ iv
< c for 0 £ v < n
for all P(i0, i1,
i2, …, in-1) where 0 £ iv < c for 0 £
v < n do
candidate[i0, i1,
i2, …, in-1] ¬1
for j ¬
0 to n-1 do
for k ¬
0 to n-1 do
if a[j][k] and ij
= ik then
candidate[i0, i1,
i2, …, in] ¬ 0
endif
endfor
endfor
valid
¬ S candidate {Sum of all elements of candidate}
endfor
if valid > 0
then print “Valid coloring exists”
else print “Valid
coloring does not exist”
endif
end
Algoritma CREW PRAM
untuk menunjukkan jika graf dengan n verteks diwarnai dengan c warna
NAMA KELOMPOK (4IA14)
1.
Arief Iman Rahman 51411100
2.
Asep Rohmana 51411242
3.
Cella Rofi 57411950
4.
Kutfu Dany 57411997
5.
Latifah 54411074
6.
M Fuad Fazri 54411663
7.
M Isan Guci 54411670
8.
Netty Herawaty 59411443
9.
Reni Marintan 55411973