sor: url("http://downloads.totallyfreecursors.com/thumbnails/banana1.gif

Kamis, 21 Mei 2015

PEMROGRAMAN PARALLEL

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:


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