TUGAS AKHIR PRAKTIKUM PEMROSESAN PARALEL
IMPLEMENTASI PARALEL MERGE SORT DENGAN MENGGUNAKAN MPICH2 DAN PERBANDINGANNYA DENGAN IMPLEMENTASI SEKUENSIAL
Disusun Oleh: Auriza Rahmad Akbar Herbet Sianipar Rifki Yusri Haidar Syariful Mizan Fathoni Arief Musyaffa Hasanul Fajri Nuras Sendi Banio Desca Marwan Toni Andi Sasmita
G64050089 G64051976 G64050964 G64052201 G64053198 G64051421 G64050114 G64050979 G64051082
DEPARTEMEN ILMU KOMPUTER FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM INSTITUT PERTANIAN BOGOR BOGOR 2009 i
DAFTAR ISI Halaman DAFTAR GAMBAR............................................................................................................... iii BAB I PENDAHULUAN ......................................................................................................... 1 1.1
Paradigma Komputasi ......................................................................................... 1
1.2
Paradigma Grid Computing................................................................................. 2
1.3
Perangkat Pendukung Grid Computing .............................................................. 4
BAB II MPICH2 ..................................................................................................................... 5 2.1
Komponen-komponen Utama MPICH2 .............................................................. 5
2.2
Fitur-Fitur pada MPICH2 ..................................................................................... 6
BAB III INSTALASI DAN KONFIGURASI MPICH2 ................................................................... 8 BAB IV EKSPERIMEN DAN ANALISIS .................................................................................. 15 4.1.
Program Penguji: Merge Sort Paralel................................................................ 15
4.1.1. Cara Kerja ........................................................................................................ 15 4.1.2. Batasan............................................................................................................ 15 4.1.3. Kode Program ................................................................................................. 15 4.2. Hasil Eksperimen .................................................................................................... 21 4.2.1. Dua Prosesor pada Dua Komputer.................................................................. 21 4.2.2. Dua Prosesor pada Satu Komputer ................................................................. 22 4.3. Analisis ................................................................................................................... 23 BAB V KESIMPULAN .......................................................................................................... 24
ii
DAFTAR GAMBAR Halaman 1 Arsitektur sistem grid computing. ................................................................................... 3 2 Struktur MPICH2. ............................................................................................................. 5 3 Ilustrasi proses sorting paralel dengan menggunakan MergeSort. ............................... 15 4 Skema komunikasi tree. ................................................................................................. 20 5 Proses komunikasi dan komputasi antar proses............................................................ 20 6 Hasil uji coba dengan menggunakan berbagai jumlah data pada dua. ......................... 21 7 Hasil uji coba dengan menggunakan berbagai jumlah data pada dua komputer. ........ 22 8 Grafik perbandingan antara Speed-Up dan Banyak Data. ............................................. 23
iii
BAB I PENDAHULUAN 1.1
Paradigma Komputasi Teknologi yang semakin maju memicu beragam paradigma komputasi untuk
terus
berkembang.
Paradigma
komputasi
diawali
dengan
proses
komputasi
menggunakan prosessor tunggal. Untuk meningkatkan kecepatan waktu komputasi, penggunaan multi prosessor bagi eksekusi proses komputasi mulai diperkenalkan. Paradigma yang kedua ini lebih dikenal sebagai parallel computing (komputasi pararel). Saat ini muncul kembali paradigma ketiga yang dikenal dengan grid computing (komputasi tersebar). Penggunaan pendekatan multi-prosesor bagi eksekusi proses komputasi telah terbukti memberikan peningkatan kecepatan proses eksekusi (jika dibandingkan dengan eksekusi proses komputasi menggunakan prosesor tunggal). Peningkatan kecepatan proses komputasi sering direpresentasikan sebagai nilai speedup. Speedup diberikan sebagai nilai rasio antara waktu eksekusi menggunakan prosesor tunggal dibanding dengan waktu eksekusi menggunakan N-buah prosesor. Untuk menghitung nilai speedup diberikan pada Persamaan 1.
SpeedUp =
T1 (Persamaan 1) TN
T1 = Waktu eksekusi menggunakan prosesor tunggal TN = Waktu eksekusi menggunakan N-buah prosesor
Selain nilai speedup, sebuah sistem pararel sering kali dievaluasi dengan nilai efeciency (efesiensi). Efeciency diberikan sebagai nilai perbandingan antara nilai speedup yang dicapai terhadap ukuran prosesor (N) yang digunakan untuk mencapai speedup tersebut. Nilai efeciency sering digunakan untuk menggambarkan seberapa signifikan peningkatan kecepatan ketika diberikan penambahan prosesor. Untuk selanjutnya informasi ini dapat digunakan sebagai acuan bagi penentuan jumlah prosesor optimal yang tepat untuk digunakan pada sebuah sistem komputasi pararel. Secara singkat persamaan efeciency dapat dituliskan seperti pada Persamaan 2.
1
Efeciency =
Speedup (Persamaan 2) N
N = Jumlah prosesor yang digunakan 1.2
Paradigma Grid Computing Telah dipaparkan bahwa paradigma parallel computing telah memberikan nilai
speedup bagi proses komputasi, lalu kenapa muncul kembali paradigma yang ketiga dalam wujud grid computing? Pertanyaan tersebut cukup layak untuk diajukan, mengingat bahwa menjadi keniscayaan bahwa tiada hal yang muncul dan terjadi tanpa suatu sebab dan makna yang menyertainya. Jelas bahwa pendekatan parallel computing telah memberikan peningkatan kecepatan waktu komputasi, yang dalam hal ini sering direpresentasikan dengan nilai speedup. Akan tetapi yang menjadi kekurangan paling kentara dari pendekatan parallel computing adalah sifat pendekatannya yang terlalu berorientasi pada prosesor. Sebuah mesin pada parallel computing memiliki sejumlah prosesor yang dilengkapi seperangkat sumber daya lainnya yang masing-masing berjumlah tunggal. Dengan sifatnya yang tunggal ini berimplikasi kepada terbatasnya ketersediaan sumberdaya-sumberdaya tersebut. Padahal kita ketahui bahwa pendukung eksekusi proses komputasi tidak hanya berupa prosesor. Asumsi ini memberikan potensi bahwa penambahan sumberdaya lainnya dapat pula mendukung proses komputasi. Penambahan sumberdaya-sumberdaya yang lain bukan merupakan suatu hal yang mudah, mungkin lebih tepatnya hal yang tidak murah. Karena pada sebuah sistem komputer pada parallel computing, perangkat yang dapat ditambahkan harus benarbenar cocok baik secara fisik maupun konfigurasi sistem. Keterbatasan inilah yang menjadikan mesin-mesin dengan pendekatan parallel computing cenderung bersifat homogen dan sulit untuk diekspansi. Dengan kata lain memiliki skalabilitas yang rendah. Di sisi lain kita tidak pernah tahu seberapa besar ukuran mesin yang kita butuhkan sebagai alat pemroses permasalahan-permasalahan komputasi yang kian kompleks. Fenomena tersebut membawa kepada pergeseran paradigma parallel computing kepada computer cluster. Selanjutnya untuk lebih mendapatkan lingkup yang lebih luas cluster computer dapat terbentuk dari node-node yang tersebar secara geografis mewujudkan paradigma grid computing. Paradigma grid computing merupakan suatu paradigma komputasi tersebar yang memungkinkan pembagian, pengaturan, dan 2
penggunaan sumber daya komputasi yang tersebar dari beragam posisi geografis secara efektif dan efisien. Sistem grid computing mengatur pembagian penggunaan sumber daya yang heterogen, dengan platform yang berbeda-beda, dan umumnya tersebar ditempat yang berbeda-beda serta dalam domain administratif yang berbeda pula. Sekilas telah kita gunakan istilah cluster computer, secara makna cluster computer dapat diartikan sebagai sekumpulan komputer yang terhubung dan bekerja bersama-sama, sehingga seolah-olah dapat dipandang sebagai satu komputer dengan multi perangkat sumberdaya . Umumnya komputer-komputer yang tergabung dalam satu cluster dihubungkan dengan menggunakan Local Area Network (LAN). Arsitektur umum pada sistem grid computing
diberikan pada Gambar 1. Sistem pada grid
computing dapat menghubungkan berbagai cluster komputer dalam berbagai platform yang berbeda-beda. Grid computing juga memiliki cakupan dan fleksibilitas yang lebih luas daripada parallel computing dan cluster computer itu sendiri.
Gambar 1 Arsitektur sistem grid computing. Sistem grid computing atau sistem komputasi grid telah banyak diterapkan dalam berbagai organisasi di dunia. Beberapa contoh organisasi yang telah menerapkan sistem komputasi grid adalah National Science Foundation's National Technology Grid, NASA's Information Power Grid, Pratt & Whitney, Bristol-Myers Squibb Co., dan American Express.
3
1.3
Perangkat Pendukung Grid Computing Paradigma parallel computing telah bergeser kepada paradigma computer
cluster. Computer cluster yang tersebar mewujudkan paradigma grid computing. Untuk menunjang penelitian dan kajian dalam bidang grid computing, berbagai perangkat lunak pendukung sistem komputasi grid dan cluster telah dikembangkan. Beberapa perangkat lunak pendukung tersebut diantaranya sebagai berikut: 1. MPI (Message Passing Interface), merupakan suatu library komunikasi yang digunakan dalam pemrograman secara paralel. MPI dapat digunakan dengan berbagai bahasa pemrograman, seperti C, Phyton, Fortran, dan lain sebagainya. 2. Globus Toolkit, merupakan suatu perangkat untuk membangun suatu sistem komputasi Grid. Globus Toolkit mengimplementasikan berbagai standar yang dibutuhkan dalam suatu Sistem Grid, yaitu Open Grid Services Architecture (OGSA), Open Grid Services Infrastructure (OGSI), Web Services Resource Framework (WSRF), Job Submission Description Language (JSDL), Distributed Resource Management Application API (DRMAA), WS-Management, WS-BaseNotification, SOAP, WSDL, dan Grid Security Infrastructure (GSI). 3. Sun Grid Engine, merupakan perangkat pembentuk Sistem komputasi Grid yang dikembangkan oleh Sun Microsystem. Sun Grid Engine ini bertugas mengatur penggunaan sumber daya komputasi yang tersebar. Sumber daya yang dapat diatur meliputi prosessor, memori, disk space, dan lisensi perangkat lunak. 4. MPICH2 adalah implementasi portabel dari MPI, standar untuk message-passing libraries, yang tersedia secara free. MPICH2 dikembangkan oleh Matematics and Computer Science Division pada laboratorium nasional Argonne. Pada penelitian kali ini akan dikaji suatu studi kasus berupa komputasi paralel untuk pengurutan bilangan menggunakan algoritme Merge Sort dengan MPICH2. Pengkajian dilakukan melalui ekseperimen pengukuran running time kasus uji dan analisis hasil eksperimen. Secara lebih mendalam pembahasan tentang MPICH2 akan diberikan secara lebih rinci pada bagian selanjutnya.
4
BAB II MPICH2 2.1
Komponen-komponen Utama MPICH2 MPICH2 merupakan pengembangan dari MPICH1 yang menggunakan MPI1
untuk standar message passing library. Pada MPICH2 mampu mengimplementasikan baik MPI1 maupun MPI2 sebagai pengembangan dari MPI1. MPI sendiri merupakan singkatan dari Message Passing Interface sedangkan kata CH berasal dari Chameleon, layer portabilitas yang digunakan pada MPICH asli untuk menyediakan portabilitas pada sistem message-passing. Struktur serta komponen-komponen yang terdapat pada MPICH2 ditunjukkan oleh Gambar 2.1.
Gambar 2 Struktur MPICH2. Pada gambar diatas diperlihatkan ada tiga komponen utama yang terdapat pada MPICH2. Komponen-komponen tersebut adalah sebagai berikut: 1. PMI (Process Manager Interface) – bertugas untuk menyediakan suatu penghubung (interface) dalam pembuatan dua buah proses dan saluran komunikasi. PMI ini di desain untuk digunakan pada banyak hal, termasuk dengan/tanpa demons dan juga proses manager pihak ketiga. 2. ADIO merupakan suatu I/O interface – ADIO pada MPICH2 tidak banyak mengalami perubahan dari versi sebelumnya kecuali untuk menangani error reporting and request management. 5
3. ADI3 - merupakan device baru yang digunakan untuk meningkatkan performa jaringan dan juga kapabilitas jaringan yang baru. Secara berurutan tahapan pengerjaan sebuah task dengan menggunakan MPICH2 pada platform Windows dapat berlangsung sebagai berikut: 1. Instal MPICH2 pada setiap mesin. 2. Buat user account yang sama pada setiap mesin serta password yang sama. 3. Setiap user account yang telah dibuat harus bersifat administratif. 4. Buatlah sebuah path yang menuju kepada direktori bin pada MPICH2. 5. Salin program yang akan dijalankan secara paralel dan letakkan pada masingmasing mesin. 6. Pastikan program yang telah disalin terletak pada struktur direktori yang sama pada masing-masing mesin. 7. Setelah login dengan user account yang telah kita buat tadi, jalankan program pada salah satu mesin yang selanjutkan kita gunakan sebagai komputer master. 2.2
Fitur-Fitur pada MPICH2 1. Merupakan implementasi penuh dari MPI1 dan MPI2, termasuk Pembatalan pesan yang dikirim. 2. Program MPMD (Multiple Program Multiple Data) dan cluster yang memiliki platform yang berbeda telah di-support. 3. Binding standar C++ yang terdapat dalam MPI2 telah tersedia dalam fungsifungsi MPI1. 4. Memiliki binding Fortan 77 dan Fortan 90, termasuk kedua jenis ‘mpif.h’ dan modul MPI. 5. Telah tersedia versi open source dari MPICH pada windows NT. 6. Mendukung banyak jenis environments, termasuk klaster-klaster dari SMP dan komputer paralel yang sangat besar. 7. Mengikuti banyak target-target rekomendasi GNU untuk build dan install, termasuk VPATH. 6
8. Bagian-bagian dari MPI2 juga mendukung : •
Sebagian besar dari MPI-IO di dukung melalui implementasi ROMIO.
•
Mendukung MPI_INIT_THREAD (namun hanya MPI_THREAD_SINGLE dan MPI_THREAD _FUNNELLED).
•
Routine-routine MPI_Info dan MPI_Datatype yang bermacam-macam.
9. MPICH juga menyediakan komponen-komponen lingkungan pemrograman paralel, termasuk: • Tool-tool untuk melacak dan mencatat log berdasarkan interface profile MPI, termasuk format file log yang bisa diubah-ubah(SLOG). • Tool untuk visualisai kinerja paralel (upshot dan jumpshot). • Pengujian kinerja dan kebenaran nilai secara ekstensif.
7
BAB III INSTALASI DAN KONFIGURASI MPICH2 3.1 Kebutuhan Sistem Grid MPICH Persiapan MPICH memerlukan sistem operasi dan beberapa program lain untuk brjalan. Sistem yang diperlukan haruslah terlebih dulu ada sebelum MPICH di-install. Adapun kebutuhan sistem tersebut antara lain: 1. Sistem Operasi Windows 2000/XP/2003 2. Visual C++ 2005 dengan IDE Visual Studio 2005 (dalam laporan ini, digunakan Visual C++ 2005 Express Edition) Instalasi MPI Setelah kebutuhan instalasi MPICH2 terpenuhi, dilakukan instalasi MPICH2, 1. Klik ganda pada file setup MPICH2 yang telah didownload, sehingga akan mucul screenshot sebagai berikut:
2. Setelah muncul screenshot seperti di atas, klik Next, sehingga akan muncul jendela yang menampilkan kebutuhan system seperti berikut:
3. Selanjutnya akan muncul jendela yang menampilkan hak cipta dan persetujuan lisensi. Pilih radio button “I Agree”, kemudian klik next.
8
4. Kemudian, muncul jendela Process Manager Setup. Di dalam jendela ini terdapat pemberitahuan untuk mengingat kata kunci atau passphrase yang akan digunakan untuk menjalankan service SPMD. SPMD merupakan process manager yang berjalan baik pada Unix maupun Windows. SPMD mampu menjalankan proses dari berbagai platform jika format binernya sama. Passphrase yang sama pada MPICH harus digunakan untuk semua komputer.
5. Berikutnya, tentukan direktori dimana kita akan meng-install MPICH2. Jika tidak diberikan, secara default installer MPICH2 akan meletakkannya di C:\Program Files\MPICH2\. Tentukan juga siapa yang bisa menggunakan MPICH pada komputer, hanya user yang sedang login atau semua user.
9
6. Muncul notifikasi bahwa installer telah siap untuk melakukan instalasi MPICH2, untuk melanjutkan instalasi, klik next.
7. Tunggu proses instalasi hingga selesai. Klik Close jika proses instalasi sudah selesai.
Konfigurasi 1. Pertama, dibuat projek melalui File – New – Project. Berikan nama projek, dalam hal ini, misalnya MPI_Hello.
10
2. Selanjutnya, Klik OK. Pada window Win32 Application Wizard, klik Next.
3. Hilangkan centang “Precompiled Header” yang secara default tercentang, kemudian klik Finish.
11
Konfigurasi Projek 1. Setelah projek dibuat, klik Project – Properties. Pilih pada menu C/C++ General. Pada bagian “Additional Include Directories” berikan direktori dimana direktori include instalasi MPICH berada, secara default, direktori include ini berada ada direktori C:\Program Files\MPICH2\include.
2. Selanjutnya, pada menu tree C/C++ - Advanced di bagian Compile As, pilih Compile as C Code (TC)
12
3. Kemudian pada menu tree C/C++ - Linker di bagian Additional Library Directories, berikan direktori dimana direktori library instalasi MPICH berada, secara default, direktori include ini berada ada direktori C:\Program Files\MPICH2\lib.
4. Langkah terakhir, pada bagian additional dependencies, tambahkan mpi.lib.
5. Langkah selanjutnya (opsional) adalah memberikan path pada folder bin MPICH2 sehingga windows akan mengenali mpiexec.exe yang selalu diperlukan untuk menjalankan aplikasi MPI yang kita compile dari visual C++. Path dapat 13
dilakukan melalui Windows Explorer, klik kanan pada My Computer kemudian pada tab advanced, klik Environment Variables. Hasilnya akan muncul pada window seperti screenshot di bawah:
6. Pada bagian system variables – Path, klik bagian edit, dan tambahkan direktori bin dari MPICH pada bagian Variable Value. Secara default, direktori bin berada pada C:\Program Files\MPICH2\bin.
14
BAB IV EKSPERIMEN DAN ANALISIS 4.1.
Program Penguji: Merge Sort Paralel
Program yang akan digunakan untuk eksperimen pemrosesan paralel adalah program merge sort paralel untuk mengurutkan sebanyak n bilangan intejer yang dibangkitkan secara acak. Program ini merupakan modifikasi dari algoritme merge sort sekuensial. Merge sort sekuensial relatif mudah diparalelkan karena menggunakan teknik divide and conquer. Jenis paralelisme yang dapat dipakai adalah paralelisme data. 4.1.1. Cara Kerja Secara garis besar, algoritme merge sort paralel ini bekerja dalam tahap-tahap berikut ini: 1. 2. 3. 4.
Root membangkitkan sejumlah n data acak Root mendistribusikan n/p data ke tiap prosesor Tiap proses melakukan sorting lokal Hasil sorting dari tiap proses di-merge ke Root.
Gambar 3 Ilustrasi proses sorting paralel dengan menggunakan MergeSort. 4.1.2. Batasan Untuk menyederhanakan program, diberikan beberapa batasan yang harus dipenuhi agar program merge sort paralel dapat berjalan dengan benar. Batasan tersebut adalah: 1. Jumlah data n harus kelipatan dari jumlah prosesor p (n mod p = 0). 2. Jumlah prosesor harus pangkat dari dua (p = 2d). 4.1.3. Kode Program Dari cara kerja di atas, program ini akan memerlukan fungsi-fungsi pada pustaka MPI (mpi.h) sebagai berikut: 15
• • • • • • • •
MPI_Init(), untuk menginisialisasi program MPI MPI_Comm_size(), untuk mendapatkan jumlah proses MPI_Comm_rank(), untuk mendapatkan rank tiap proses MPI_Scatter(), untuk mendistribusikan data ke tiap proses MPI_Send(), untuk mengirimkan data MPI_Recv(), untuk menerima data MPI_Wtime(), untuk mencatat waktu eksekusi MPI_Finalize(), untuk mengakhiri program MPI
Sedangkan dari pustaka standar bahasa C (stdio.h, stdlib.h), akan digunakan fungsifungsi sebagai berikut: • malloc(), untuk mengalokasikan memori secara dinamis • free(), untuk membebaskan memori yang telah dialokasikan • rand(), untuk membangkitkan data pseudorandom • qsort(), untuk mengurutkan data Kode program lengkap untuk merge sort paralel adalah sebagai berikut: #include <stdio.h> #include <stdlib.h> #include <mpi.h>
#define DEBUG #define ROOT 0 #define ISPOWER2(x) (!((x)&((x)-1)))
/* Merge 2 arrays with same size */ int *merge(int array1[], int array2[], int size) { int *result = (int *)malloc(2*size*sizeof(int)); int i=0, j=0, k=0;
while ((i < size) && (j < size)) result[k++] = (array1[i] <= array2[j])? array1[i++] : array2[j++];
while (i < size) result[k++] = array1[i++];
while (j < size) result[k++] = array2[j++];
return result; }
/* Validate sorted data */
16
int sorted(int array[], int size) { int i; for (i=1; i<size; i++) if (array[i-1] > array[i]) return 0; return 1; }
/* Needed by qsort() */ int compare(const void *p1, const void *p2) { return *(int *)p1 - *(int *)p2; }
int main(int argc, char** argv) {
int i, b=1, npes, myrank; long datasize; int localsize, *localdata, *otherdata, *data = NULL; int active = 1; MPI_Status status; double start, finish, p, s;
MPI_Init(&argc, &argv); MPI_Comm_rank(MPI_COMM_WORLD, &myrank); MPI_Comm_size(MPI_COMM_WORLD, &npes);
/* Read datasize argument */ datasize = strtol(argv[1], argv, 10);
/* Check argument */ if (!ISPOWER2(npes)) { if (myrank == ROOT) printf("Processor number must be power of two.\n"); return MPI_Finalize(); } if (datasize%npes != 0) { if (myrank == ROOT) printf("Datasize must be divisible by processor number.\n"); return MPI_Finalize(); }
/* Generate data */ if (myrank == ROOT) {
17
data = (int *)malloc(datasize * sizeof(int)); for (i = 0; i < datasize; i++) data[i] = rand()%99 + 1; }
/* Start point of parallel processing */ start = MPI_Wtime();
/* Scatter data */ localsize = datasize / npes; localdata = (int *) malloc(localsize * sizeof(int)); MPI_Scatter(data, localsize, MPI_INT, localdata, localsize, MPI_INT, ROOT, MPI_COMM_WORLD);
/* Sort localdata */ qsort(localdata, localsize, sizeof(int), compare);
/* Merge sorted data */ while (b < npes) { if (active) { if ((myrank/b)%2 == 1) { MPI_Send(localdata, b * localsize, MPI_INT, myrank - b, 1, MPI_COMM_WORLD); free(localdata); active = 0; } else { otherdata = (int *) malloc(b * localsize * sizeof(int)); MPI_Recv(otherdata, b * localsize, MPI_INT, myrank + b, 1, MPI_COMM_WORLD, &status); localdata = merge(localdata, otherdata, b * localsize); free(otherdata); } } b <<= 1; } /* End point of parallel processing */ finish = MPI_Wtime();
/* Runtime and speed-up analysis */ if (myrank == ROOT) {
#ifdef DEBUG if (sorted(localdata, npes*localsize)) {
18
printf("\nParallel sorting succeed.\n\n"); } else { printf("\nParallel sorting failed.\n\n"); } #endif
free(localdata); p = finish - start; printf("
Parallel : %.8f\n", p);
/* Sequential sort */ start = MPI_Wtime(); qsort(data, datasize, sizeof(int), compare); finish = MPI_Wtime();
free(data); s = finish - start; printf("Sequential : %.8f\n", s);
printf("
Speed-up : %.8f\n", s/p);
} return MPI_Finalize(); }
4.1.3.1. Merge Paralel /* Merge sorted data */ while (b < npes) { if (active) { if ((myrank/b)%2 == 1) { MPI_Send(localdata, b * localsize, MPI_INT, myrank - b, 1, MPI_COMM_WORLD); free(localdata); active = 0; } else { otherdata = (int *) malloc(b * localsize * sizeof(int)); MPI_Recv(otherdata, b * localsize, MPI_INT, myrank + b, 1, MPI_COMM_WORLD, &status); localdata = merge(localdata, otherdata, b * localsize); free(otherdata); } } b <<= 1; }
19
Kode di atas akan menggabungkan hasil data terurut dari tiap proses dengan skema komunikasi tree. Sehingga semua hasil pada akhirnya akan terkumpul ke Root. Skema komunikasi tersebut diilustrasikan pada gambar di bawah ini dengan menggunakan 4 proses (P0, P1, P2, dan P3). Iterasinya sebagai berikut: I0 : P1 P0, P3 P2 I1 : P2 P0
Gambar 4 Skema komunikasi tree. Kode merge paralel ini menggunakan fungsi merge() untuk menggabungkan 2 array dari proses yang berbeda. Proses komunikasi dan komputasi antar proses diilustrasikan pada gambar di bawah. Proses B mengirimkan datanya ke proses A. Proses A menggabungkan data sehingga dihasilkan data yang terurut, dan disimpan di proses A. Kemudian proses B diberi tanda non-aktif (active = 0).
Gambar 5 Proses komunikasi dan komputasi antar proses. 4.1.2.2. Merge 2 Array /* Merge 2 arrays with same size */ int *merge(int array1[], int array2[], int size) { int *result = (int *)malloc(2*size*sizeof(int)); int i=0, j=0, k=0;
while ((i < size) && (j < size))
20
result[k++] = (array1[i] <= array2[j])? array1[i++] : array2[j++];
while (i < size) result[k++] = array1[i++];
while (j < size) result[k++] = array2[j++]; return result; }
Fungsi merge() akan menggabungkan 2 array dengan ukuran yang sama. Fungsi ini akan mengembalikan hasil berupa array gabungan yang sudah terurut. 4.2. Hasil Eksperimen 4.2.1. Dua Prosesor pada Dua Komputer Eksperimen dilakukan menggunakan dua komputer yang dihubungkan melalui kabel LAN. Spesifikasi komputer yang digunakan adalah: 1. Prosesor AMD Sempron 1.6 GHz 2. Prosesor AMD Athlon64 1.8 GHz Hasil yang didapatkan kurang memuaskan karena overhead komunikasi data yang tinggi karena melalui kabel LAN. Berikut ini adalah gambar cuplikan hasil eksperimen dengan jumlah data 1000, 1 juta, dan 10 juta.
Gambar 6 Hasil uji coba dengan menggunakan berbagai jumlah data pada dua. komputer Dengan menggunakan beberapa kombinasi data akan ditampilkan perbandingan waktu, seperti pada tabel di bawah ini : 21
Jumlah Data (n)
Waktu sekuensial (Ts) ( second)
Waktu Paralel (Tp) (second)
SpeedUp(Tp/Ts)
1000
0.00051822
0.00382814
0.13537182
1000000
0.49885782
0.59219985
0.84238086
10000000
4.99542260
5.89395943
0.84754954
4.2.2. Dua Prosesor pada Satu Komputer Eksperimen dilakukan menggunakan satu komputer dual core. Spesifikasi komputer yang digunakan adalah menggunakan prosesor Intel Core 2 Duo 2.0 GHz. Hasil yang didapatkan memuaskan karena overhead komunikasi data yang minimum. Berikut ini adalah gambar cuplikan hasil eksperimen untuk jumlah data 1000, 10.000, dan 100.000.
Gambar 7 Hasil uji coba dengan menggunakan berbagai jumlah data pada dua komputer.
Jumlah data (n)
Waktu Paralel(Tp)(second)
Waktu Sekuensial (Ts)(second)
Speed-up (Ts/Tp)
10
0.00102387
0.00000754
0.00736698
100
0.00055035
0.00004693
0.08527919
1000
0.00078725
0.00045983
0.58410220
10000
0.00317275
0.00453158
1.42828212
100000
0.02650840
0.04411902
1.66434112
1000000
0.25299193
0.45558332
1.80078203 22
10000000
2.56146885
4.44673918
1.73601142
20000000
5.01108241
8.69271039
1.73469715
30000000
8.03057288
13.08271442
1.62911347
40000000
10.11727831
17.62084958
1.74165907
50000000
16.22151698
21.73200085
1.33970213
60000000
23.28106365
28.09910422
1.20695105
Gambar 8 Grafik perbandingan antara Speed-Up dan Banyak Data. 4.3. Analisis Program merge sort paralel telah diimplementasikan dan dievaluasi hasilnya. Pengujian hanya dilakukan dengan menggunakan 2 prosesor saja. Hasil eksperimen pada dua komputer kurang memuaskan, karena overhead komunikasi yang tinggi. Hasil eksperimen pada satu komputer dengan menggunakan dua prosesor (dual core) menunjukkan hasil yang sesuai harapan. Speed up maksimum terjadi pada jumlah data n = 106.
23
BAB V KESIMPULAN 1. Sistem cluster MPICH2 telah dibangun dan dapat digunakan untuk melakukan komputasi paralel. 2. Setiap komputer pada sistem cluster MPICH2 akan menjalankan program yang sama. 3. Untuk aplikasi merge sort paralel yang dijalankan pada sistem cluster MPICH2, speed-up dan efisiensi yang diperoleh cukup baik. 4. Pada aplikasi merge sort paralel, semakin besar jumlah data (n) maka speed-up akan semakin naik sampai batas tertentu.
24
