ANALISIS DAN IMPLEMENTASI MODEL PARALEL HYBRID DENGAN MPI DAN OPENMP PADA METODE CONJUGATE GRADIENT
ANGGI HARYO SAKSONO
DEPARTEMEN ILMU KOMPUTER FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM INSTITUT PERTANIAN BOGOR BOGOR 2010
ANALISIS DAN IMPLEMENTASI MODEL PARALEL HYBRID DENGAN MPI DAN OPENMP PADA METODE CONJUGATE GRADIENT
ANGGI HARYO SAKSONO
Skripsi Sebagai salah satu syarat untuk memperoleh gelar Sarjana Komputer pada Departemen Ilmu Komputer
DEPARTEMEN ILMU KOMPUTER FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM INSTITUT PERTANIAN BOGOR BOGOR 2010
ABSTRACT ANGGI HARYO SAKSONO. The Analysis and Implementation of Parallel Hybrid Model with MPI and OpenMP on Conjugate Gradient Method. Supervised by HENDRA RAHMAWAN. Conjugate Gradient method is one of the iterative methods to solve linear equation system. The method consumes much time to get the solution. Therefore to reduce its execution time, parallel processing is implemented on this method. There was a research related to this topic by Hoefler et al (2007). On their research, they were optimizing a pure MPI implementation by modifying collective functions into a non-blocking collective communication. This research used parallel hybrid model by combining MPI and OpenMP. The aim of this research is to analyze and implement the complexity and the performance of sequential, MPI and hybrid conjugate gradient algorithm. The analysis performed in this research includes the analysis of performance metrics and the experimental results of every implementation. This research uses 8 computers for running MPI processes and for hybrid experiment added 4 threads for running OpenMP on every computer. There are five matrices uses in this research obtained from matrices collection of University of Florida. The results of this research show that the execution time of all implementation for matrices with greater sizes give longer time. For example, on sequential implementation a matrice size of 2548 x 2548 takes 28.94 seconds and a matrice size of 4884 x 4884 takes 48.24 seconds. The execution time of MPI conjugate gradient is less than its sequential implementation, and the execution time of hybrid conjugate gradient is less than its MPI conjugate gradient. The speedup of MPI and hybrid conjugate gradient grows but not proportionally with the increasing size of matrices used. The overall result of hybrid implementation is quite good when the number of thread used is the same as the number of processor available on the computer. Keywords : parallel processing, parallel hybrid model, mixed mode MPI/OpenMP programming, conjugate gradient, parallel conjugate gradient.
Penguji: 1. Endang Purnama Giri. S.Kom., M.Kom 2. Dr. Ir. Sri Nurdiati., M.Sc
Judul Skripsi Nama NIM
: Analisis dan Implementasi Model Paralel Hybrid dengan MPI dan OpenMP pada Metode Conjugate Gradient : Anggi Haryo Saksono : G64076008
Menyetujui:
Pembimbing
Hendra Rahmawan, S.Kom, M.T
Mengetahui : Ketua Departemen Ilmu Komputer,
Dr. Ir. Sri Nurdiati, M.Sc NIP. 19601126 198601 2 001
Tanggal Lulus :
PRAKATA Alhamdulillahi Rabbil 'alamin, puji dan syukur penulis panjatkan kepada Allah SWT atas segala limpahan rahmat, hidayah, serta karunia-Nya sehingga skripsi ini berhasil diselesaikan. Shalawat dan salam tidak lupa saya tujukan kepada baginda Nabi Muhammad SAW, sebab karena beliaulah penulis bisa merasakan nikmat iman dan islam. Tema yang dipilih pada penelitian yang dilaksanakan sejak bulan September 2009 ini adalah pemrosesan paralel, dengan judul Analisis dan Implementasi Model Paralel Hybrid dengan MPI dan OpenMP Pada Metode Conjugate Gradient. Terima kasih penulis ucapkan kepada pihak-pihak yang telah membantu penyelesaian tugas akhir ini, diantaranya: 1. Kedua orang tua dan seluruh keluarga yang selalu memberi dukungan dan doa kepada penulis. 2. Bapak Hendra Rahmawan selaku dosen pembimbing yang telah banyak membantu, memberi saran dan membimbing penulisi selama melakukan penelitian. 3. Bapak Endang Purnama Giri dan Ibu Sri Nurdiati yang telah menguji penulis dengan materimateri yang masih dapat ditangani oleh penulis. 4. Teman sejawat Purwa Purdiawan, R. A Fakih Basyarudin, Iqbal Nurdiansyah, Dimas Cahyo P, dan Indra Rusdiansyah atas segala kerja sama dan bantuan selama penelitian maupun saat seminar dan ujian sidang. 5. Seluruh teman-teman penghuni kos Pak Timo yang memberikan dukungan moril dan materi serta canda-tawa penghilang penat selama penelitian ini. 6. Kepada para “penunggu” laboratorium komputer yaitu pak Edi, Aput, Dayat, Toni, dan Yudha yang telah membantu dan menemani penulis selama percobaan. 7. Semua teman-teman Ilmu Komputer Ekstensi Angkatan Dua atas persahabatan, kebersamaan, semangat dan segala bantuannya. Kritik dan saran yang membangun sangat penulisi harapkan untuk kemajuan di masa depan. Semoga tulisan ini dapat bermanfaat bagi akademisi Ilmu Komputer.
Bogor, April 2010 Anggi Haryo Saksono
RIWAYAT HIDUP Penulis dilahirkan di Jakarta pada tanggal 28 Januari 1987 sebagai anak keempat dari lima bersaudara dari pasangan Suwardoyo dan Sumeni. Tahun 2004 penulis berhasil menamatkan pendidikan di SMA Negeri 91, Pondok Kelapa, Jakarta dan pada tahun yang sama penulis lulus seleksi masuk Program Diploma IPB melalui jalur reguler. Penulis memilih Program Studi Teknik Informatika, Departemen Ilmu Komputer, Fakultas Matematika dan Ilmu Pengetahuan Alam. Pada tahun 2007 penulis berhasil lulus dari Program Diploma IPB dan langsung diterima bekerja sebagai staf di KPSI IPB. Pada tahun yang sama pula penulis melanjutkan pendidikan ke jenjang Strata 1 di IPB pada Jurusan Ilmu Komputer, Fakultas Matematika dan Ilmu Pengetahuan Alam.
DAFTAR ISI Halaman DAFTAR GAMBAR............................................................................................................................viii DAFTAR LAMPIRAN...........................................................................................................................ix PENDAHULUAN....................................................................................................................................1 Latar Belakang....................................................................................................................................1 Tujuan.................................................................................................................................................1 Ruang Lingkup...................................................................................................................................1 Manfaat...............................................................................................................................................2 TINJAUAN PUSTAKA...........................................................................................................................2 Disain Algoritme Paralel....................................................................................................................2 Model Pemrograman Paralel..............................................................................................................2 Speedup...............................................................................................................................................3 Efisiensi..............................................................................................................................................4 Cost.....................................................................................................................................................4 Total Parallel Overhead.....................................................................................................................4 Isoefisiensi..........................................................................................................................................4 Matriks Simetri...................................................................................................................................4 Matriks Definit Positif........................................................................................................................4 Conjugate............................................................................................................................................4 Conjugate Gradient (CG)...................................................................................................................4 METODE PENELITIAN.........................................................................................................................4 Tahapan Penelitian..............................................................................................................................4 Studi Pustaka......................................................................................................................................5 Analisis Algoritme CG.......................................................................................................................5 Implementasi CG Sekuensial..............................................................................................................5 Penerapan Metode Foster...................................................................................................................5 Analisis dan Implementasi MPI Algoritme CG..................................................................................5 Identifikasi, Analisis dan Implementasi Hybrid.................................................................................6 Perancangan Percobaan......................................................................................................................6 Percobaan............................................................................................................................................6 Analisis Hasil Percobaan....................................................................................................................7 HASIL DAN PEMBAHASAN................................................................................................................7 Analisis dan Implementasi Algoritme CG Sekuensial........................................................................7 Penerapan Metode Foster...................................................................................................................7 Analisis dan Implementasi Algoritme CG MPI..................................................................................9 Penerapan Model Hybrid..................................................................................................................11 Analisis dan Implementasi Algoritme CG Hybrid...........................................................................12 Analisis Hasil Waktu Eksekusi.........................................................................................................14 Analisis Hasil Speedup.....................................................................................................................16 Analisis Hasil Efisiensi.....................................................................................................................17 Analisis Cost.....................................................................................................................................18 Analisis Total Parallel Overhead.....................................................................................................18 KESIMPULAN DAN SARAN..............................................................................................................19 Kesimpulan.......................................................................................................................................19 Saran.................................................................................................................................................20 DAFTAR PUSTAKA.............................................................................................................................20 LAMPIRAN...........................................................................................................................................21
vii
DAFTAR GAMBAR Halaman 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35
Metode Conjugate Gradient..............................................................................................................4 Skema tahapan penelitian..................................................................................................................5 Skema jaringan yang digunakan pada percobaan..............................................................................6 Kompleksitas tahapan pada fungsi CG sekuensial............................................................................7 Grafik perhitungan kompleksitas CG sekuensial..............................................................................7 Skema keterkaitan fungsi pada iterasi CG........................................................................................8 Struktur algoritme CG MPI pada bagian iterasi................................................................................9 Struktur algoritme dan kompleksitas fungsi CG MPI.....................................................................10 Grafik perhitungan kompleksitas CG MPI......................................................................................10 Grafik perhitungan speedup CG MPI..............................................................................................10 Grafik perhitungan efisiensi CG MPI..............................................................................................11 Struktur algoritme CG hybrid pada bagian iterasi...........................................................................12 Struktur algoritme dan kompleksitas fungsi CG hybrid..................................................................12 Grafik perhitungan kompleksitas untuk tiap jumlah thread dengan ukuran matriks 2548 x 2548. 13 Grafik perhitungan kompleksitas untuk tiap ukuran matriks dengan 2 thread...............................13 Grafik perhitungan speedup untuk tiap jumlah thread dengan ukuran matriks 2548 x 2548.........13 Grafik perhitungan speedup untuk tiap ukuran matriks dengan 2 thread.......................................13 Grafik perhitungan efisiensi untuk tiap jumlah thread dengan ukuran matriks 2548 x 2548.........14 Grafik perhitungan efisiensi untuk tiap ukuran matriks dengan 2 thread.......................................14 Grafik waktu eksekusi implementasi CG sekuensial......................................................................14 Grafik waktu eksekusi implementasi MPI......................................................................................15 Grafik waktu eksekusi untuk setiap implementasi dengan ukuran matriks 2548 x 2548...............15 Grafik waktu eksekusi untuk setiap implementasi dengan ukuran matriks 4884 x 4884...............15 Grafik waktu eksekusi implementasi hybrid untuk tiap ukuran matriks dengan 2 thread..............15 Grafik waktu eksekusi dan waktu iterasi implementasi MPI dan hybrid 2 thread untuk ukuran matriks 2548 x 2548........................................................................................................................16 Grafik speedup hasil percobaan implementasi MPI........................................................................16 Grafik speedup hasil percobaan hybrid untuk setiap ukuran matriks dengan 2 thread...................17 Grafik speedup hasil percobaan untuk setiap implementasi dengan ukuran matriks 2548 x 2548.17 Grafik efisiensi hasil percobaan implementasi MPI........................................................................17 Grafik efisiensi hasil percobaan hybrid untuk setiap ukuran matriks dengan 2 thread..................17 Grafik efisiensi hasil percobaan untuk setiap implementasi dengan ukuran matriks 2548 x 2548.17 Grafik cost hasil percobaan implementasi MPI..............................................................................18 Grafik cost hasil percobaan untuk setiap implementasi dengan ukuran matriks 2548 x 2548.......18 Grafik overhead hasil percobaan implementasi MPI......................................................................18 Grafik overhead hasil percobaan untuk setiap implementasi dengan ukuran matriks 2548 x 2548.................................................................................................................................................18
viii
DAFTAR LAMPIRAN Halaman 1 2 3 4 5
Grafik waktu eksekusi implementasi MPI dan hybrid pada untuk setiap kombinasi......................22 Grafik speedup implementasi MPI dan hybrid pada untuk setiap kombinasi.................................23 Grafik efisiensi implementasi MPI dan hybrid pada untuk setiap kombinasi.................................24 Grafik cost implementasi MPI dan hybrid pada untuk setiap kombinasi........................................25 Grafik overhead implementasi MPI dan hybrid pada untuk setiap kombinasi...............................26
ix
PENDAHULUAN Latar Belakang Model pemrograman paralel dibutuhkan dalam implementasi pemrograman paralel pada suatu sistem paralel. Sistem distributed memory dapat menggunakan model pemrograman message-passing. Implementasi dari model message-passing yang banyak digunakan adalah Message Passing Interface (MPI). Pada sistem shared memory dapat menggunakan model pemrograman shared-memory dan implementasi yang biasa digunakan adalah Open MultiProcessing (OpenMP). Sistem distributedshared memory merupakan hasil kombinasi dua sistem paralel. Model pemrograman sistem ini harus mampu memanfaatkan kemampuan kedua sistem penyusunnya, sehingga model ini haruslah model kombinasi juga, yaitu model hybrid. Model hybrid adalah hasil kombinasi dua atau lebih model pemrograman paralel (Smith, 2000; Dongara et al. 2003). Pada penelitian ini, model hybrid akan diimplementasikan pada metode Conjugate Gradient (CG). CG adalah metode yang paling terkenal yang digunakan dalam penyelesaian sistem persamaan linear (SPL) yang besar dengan matriks simetris dan definit positif (Schewchuk, 1994). Metode ini bersifat iteratif, sehingga dapat diaplikasikan pada SPL yang mana akan sulit jika diselesaikan dengan metode secara langsung. Dipilihnya metode CG dalam penelitian ini karena metode ini membutuhkan waktu komputasi yang lama dalam penyelesaiannya, sehingga baik jika dioptimasi secara paralel. Penelitian yang terkait dengan hal ini telah dilakukan oleh Hoefler et al. (2007), dengan judul Optimizing a Conjugate Gradient Solver with Non-Blocking Collective Operations. Penelitian tersebut menggunakan library MPI yang sudah dimodifikasi pada bagian fungsi kolektif, yakni dimodikasi secara non-blocking. Pada penelitian tersebut diperoleh kesimpulan bahwa peningkatan waktu eksekusi sampai dengan 34% dari pada sekedar fungsi kolektif yang standar. Berdasarkan hasil penelitian tersebut, maka pada penelitian ini digunakan cara lain untuk mengoptimasi paralel CG MPI, yaitu dengan mengimplementasikan model hybrid. Pada penelitian ini untuk model messagepassing digunakan library MPI, sedangkan untuk model shared-memory digunakan library
OpenMP. Penggunaan kedua library ini karena berdasarkan fakta bahwa keduanya paling banyak digunakan secara luas pada model hybrid, dikarenakan keunggulan keduanya berdasarkan tingkat portability. Kedua library ini juga dianggap mewakili standar industri untuk sistem distributed memory dan shared memory (Smith, 2000). Tujuan Tujuan dari penelitian ini adalah: 1. Mengimplementasikan konsep pemrosesan paralel dengan model pemrograman paralel hybrid secara bertahap pada metode CG. 2. Menganalisis kinerja algoritme CG sekuensial, CG MPI, dan CG hybrid dari performance metric. 3. Menganalisis kinerja algoritme CG sekuensial, CG MPI, dan CG hybrid dari hasil percobaan yang diperoleh. Ruang Lingkup Ruang lingkup dan batasan yang digunakan pada penelitian ini yaitu: 1. Seluruh tahapan penelitian dilakukan pada sistem operasi Linux. 2. Implementasi model hybrid menggunakan library MPI untuk mewakili model message-passing dan library OpenMP untuk mewakili model shared-memory. Bahasa pemrograman yang digunakan adalah C dengan kompilator GNU C. 3. Penelitian ini menggunakan delapan buah komputer untuk eksekusi implementasi MPI dan untuk implementasi hybrid menggunakan maksimal 4 thread. 4. Matriks koefisien SPL yang digunakan adalah model dense. Ada 5 buah matriks yang digunakan dan diperoleh dari koleksi matriks University of Florida. 5. Percobaan yang dilakukan hanya mengukur tingkat performance berdasarkan waktu eksekusi, speedup, efisiensi, cost, total parallel overhead, dan isoefisiensi. 6. Pada percobaan yang dilakukan, eksekusi program dari metode CG tidak sampai terpenuhinya toleransi residu yang diinginkan. Banyaknya iterasi dibatasi hanya sampai 1000 iterasi, karena pada penelitian ini ingin melihat pengaruh ukuran data, bukan dari banyaknya iterasi. Selain itu 1
dengan 1000 iterasi sudah cukup untuk melihat performance dari hasil implementasi. Manfaat Dengan dilakukannya implementasi permrosesan paralel pada metode CG, kecepatannya dalam menyelesaikan sistem persamaan linear akan meningkat, sehingga akan mengurangi waktu komputasi. Lebih jauh lagi implementasi model hybrid pada penelitian ini dapat lebih meningkatkan performance komputasi paralel dibandingkan dengan implementasi MPI murni, dan akan menghasilkan strategi paralel yang lebih efisien. TINJAUAN PUSTAKA Disain Algoritme Paralel Dalam mendisain suatu algoritme paralel, menurut Foster (1995), ada beberapa langkah yang harus dilakukan, yaitu partitioning, communication, agglomeration, dan mapping. 1. Partitioning Ada dua pendekatan pada tahap partitioning, yaitu domain decomposition dan functional decomposition. Pada pendekatan domain decomposition, hal yang pertama dilakukan adalah memisahkan data dan jika mungkin membaginya menjadi bagian-bagian yang sama besar, kemudian mengasosiasikan komputasi pada data tersebut. Pendekatan yang kedua adalah functional decomposition, yaitu membagi komputasi terlebih dahulu, kemudian menentukan data yang dibutuhkan oleh komputasi tersebut. 2. Communication Pada tahap ini diatur bagaimana bentuk komunikasi yang digunakan untuk mengirim data antar task. Ada dua pola komunikasi yang digunakan, yaitu local communication dan global communication. Pada local communication tiap task berkomunikasi dengan sekumpulan kecil task-task tetangga, sedangkan pada global communication tiap task berkomunikasi dengan banyak task. 3. Agglomeration Pada tahap agglomeration beberapa task dikombinasi menjadi task-task yang lebih besar untuk meningkatkan performance dan meminimumkan global communication.
4. Mapping Pada tahap ini diatur bagaimana tiap task dipetakan ke suatu processor. Mapping digunakan untuk memaksimalkan penggunaan processor dan meminimalkan biaya komunikasi. Model Pemrograman Paralel Model pemrograman paralel hadir sebagai abstraksi di atas arsitektur hardware dan memory, jadi seorang programmer harus berhadapan dengan model pemrograman ini untuk membuat suatu program paralel. Ada tiga model pemrograman yang banyak digunakan, yaitu message-passing, shared-memory, dan hybrid. 1. Message-passing Message-passing telah digunakan secara luas sebagai pendekatan untuk mencapai komputasi paralel. Pada model ini suatu komputasi terdiri dari satu atau lebih proses yang saling berkomunikasi dengan mengirim dan menerima messages. Komunikasi dilakukan dengan memanggil fungsi-fungsi yang telah didefinisikan pada library yang digunakan (Dongara et al. 2003). Menurut Dongara et al (2003) salah satu implementasi message-passing yang banyak digunakan adalah Message Passing Interface (MPI). MPI bukanlah suatu bahasa pemrograman, melainkan suatu library yang menyediakan banyak fungsi yang dapat dipanggil oleh program. MPI dapat digunakan pada beberapa bahasa pemrograman, di antaranya C/C++ dan Fortran. Menurut Barney (2009) ada dua tipe komunikasi yang digunakan pada MPI, yaitu point-to-point dan kolektif. •
Point-to-point Tipe komunikasi point-to-point merupakan komunikasi yang melibatkan hanya dua proses pada grup yang sama. Salah satu proses melakukan operasi send, dan proses lainnya melakukan operasi receive pasangannya.
•
Kolektif Komunikasi kolektif harus melibatkan keseluruhan proses yang ada pada suatu grup. Ada tiga tipe operasi dari komunikasi ini, pertama sinkronisasi, semua proses pada operasi ini akan menunggu sampai keseluruhan proses pada grup yang sama mencapai titik sinkronisasi yang sudah 2
ditentukan. Tipe kedua adalah perpindahan data, tipe operasi ini digunakan untuk mengirim atau menerima data dari dan ke semua proses pada grup yang sama. Ketiga adalah komputasi kolektif, salah satu proses akan mengumpulkan data dari seluruh proses pada grup yang sama, selanjutnya dilakukan suatu operasi pada data tersebut, seperti penjumlahan atau pengurangan. 2. Shared-memory Menurut El-Rewini et al (2005) model pemrograman shared-memory barangkali menjadi model yang paling mudah untuk dimengerti karena memiliki kesamaan dengan pemrograman pada sistem operasi. Pada model ini semua proses berbagi alamat memory yang sama, dan melakukan operasi baca dan tulis secara asynchronous, sehingga mekanisme seperti semaphores dapat digunakan untuk mengontrol akses ke memory tersebut. Pada model pemrograman shared-memory harus ada tiga konstruksi utama pada program, yaitu task creation, komunikasi, dan sinkronisasi. •
Task creation Sekumpulan proses dibentuk melalui perintah fork, exec, dan perintah lainnya yang terkait. Secara keseluruhan suatu aplikasi merupakan kumpulan konstruksi fork-join.
•
Komunikasi Komunikasi di antara proses paralel dapat dilakukan dengan menulis dan membaca shared variable pada segmen data shared yang ada pada proses paralel.
•
Sinkronisasi Sinkronisasi dibutuhkan untuk melindungi shared variable dengan meyakinkan bahwa variabel tersebut hanya diakses oleh satu proses pada waktu yang sama.
Implementasi model shared-memory salah satunya adalah Open Multi-Processing (OpenMP). OpenMP diimplementasikan sebagai suatu kombinasi dari penggunaan library, sekumpulan compiler directive atau pragma dan environment variable. OpenMP menggunakan model fork-join dalam eksekusi secara paralel. Program OpenMP dimulai dengan sebuah proses, yaitu master thread. Master thread melakukan eksekusi secara sekuensial sampai daerah paralel pertama yang dijumpai. Master thread kemudian memulai
operasi Fork, yaitu membuat sekumpulan thread paralel. Perintah-perintah yang ada pada daerah yang diparalelkan dieksekusi secara paralel oleh thread-thread tersebut. Setelah semua thread selesai melakukan eksekusi dan mencapai akhir bagian paralel, kemudian dilakukan operasi Join, yaitu semua thread melakukan sinkronisasi dan mengakhiri thread masing-masing, dan hanya menyisakan master thread (Barney 2009). 3. Hybrid Menurut Smith (2000) model pemrograman hybrid adalah model pemrograman yang mengombinasikan dua atau lebih model pemrograman paralel. Dengan digunakannya model pemrograman ini, maka seharusnya keunggulan-keunggulan dari model pemrograman penyusunnya dapat diperoleh. Sistem ini akan menggunakan model pemrograman message-passing untuk mengakomodir komunikasi antar komputer, dan model shared-shared memory untuk mengakomodir komunikasi antar processor pada komputer yang sama. Kombinasi MPI dengan OpenMP biasanya banyak digunakan pada sistem hybrid distributed-memory. Secara teori, kombinasi tersebut akan menghasilkan strategi paralel yang lebih efisien dan optimal dibandingkan dengan penggunaan murni MPI. Ada beberapa keuntungan dari penggunaan model pemrograman hybrid, di antaranya: •
Program yang memiliki skalabilitas proses MPI yang buruk, dapat dioptimasi dengan model ini.
•
Program yang memiliki skalabilitas OpenMP yang buruk, dapat dioptimasi dengan model ini.
•
Program yang memiliki masalah kekurangan memory lokal dapat teratasi karena penggunaan MPI.
•
Lebih mudah dalam dibandingkan dengan MPI.
implementasi
Speedup Speedup S didefinisikan sebagai rasio dari waktu yang digunakan untuk menyelesaikan masalah dalam sekuensial T s terhadap waktu yang diperlukan untuk menyelesaikan masalah yang sama dalam paralel T p , dirumuskan pada Persamaan 1 (Grama et al. 2003). 3
S=
Ts . Tp
[1]
Efisiensi Efisiensi E adalah rasio antara speedup dengan banyaknya processor p . Efisiensi didefinisikan sebagai berikut berikut (Grama et al. 2003) yang dirumuskan pada Persamaan 2. Ts S E= = . p pTp
[2]
Cost Cost C untuk menyelesaikan masalah dalam sistem paralel didefinisikan sebagai hasil perkalian waktu pelaksanaan dengan jumlah processor yang digunakan. Fungsi biaya paralel dirumuskan pada Persamaan 3 (Grama et al. 2003). C= p T p .
[3]
Total Parallel Overhead Overhead biasanya disebabkan oleh faktor idle, waktu komunikasi dan komputasi. Fungsi overhead dinotasikan dengan simbol T o . Fungsi overhead dirumuskan pada Persamaan 4 (Grama et al. 2003). T o = pT p−T s .
[4]
Conjugate Menurut Schewchuk (1994), jika ada sebuath matriks A , dua vektor x dan y disebut conjugate jika T x Ay=0, x≠ y .
Conjugate Gradient (CG) Metode Conjugate Gradient (CG) adalah sebuah algoritme untuk mencari solusi numerik dari suatu sistem persamaan linear tertentu, yaitu yang dengan matriks simetri dan definit positif. Metode ini bersifat iteratif, sehingga dapat diaplikasikan pada SPL yang berukuran besar dan akan sangat sulit jikalau diselesaikan dengan metode langsung, seperti eliminasi Gauss. Disamping itu, metode CG juga dapat diterapkan untuk menyelesaikan masalah optimasi tak berkendala. Secara umum, metode ini membangkitkan vektor-vektor yang saling berkonjugasi dan juga merupakan gradient dari fungsi kuadrat. Metode ini menyelesaikan sistem persamaan linear dengan cara menemukan titik minimum dari fungsi kuadrat (Schewchuk, 1994). Secara lengkapnya metode CG disajikan pada Gambar 1. 1
Diberikan SPL Ax=b
2
Pilih x 0 awal, x 0 =0 r 0 =b – Ax 0
3
Isoefisiensi
4
d 0 =r 0
Menurut Grama et al. (2003) efisiensi akan menurun jika jumlah processor meningkat dan efisiensi akan meningkat jika ukuran data juga ditingkatkan. Jadi efisiensi dapat dibuat konstan jika jumlah processor dan ukuran data sama-sama ditingkatkan. Efisiensi yang konstan ini disebut sebagai isoefisiensi. Fungsi Isoefisiensi dirumuskan pada Persamaan 5, dimana K= E / E−1 .
5
i=0
6
rr =r T i r i
W = K T o W , p .
[5]
Matriks Simetri Menurut Schewchuk (1994) sebuah matriks A disebut simetri jika T A =A .
[6]
Matriks Definit Positif Menurut Schewchuk (1994) sebuah matriks A disebut definit positif jika untuk semua vektor x≠0 , T
x Ax0 .
[7]
[8]
7 8
While imax and ∥r i∥≥tol q= A d i
10
dq=d T i q i=rr / dq
11
x i1= x i i d i
12
r i 1=r i − i q i
13 14
rr2=r T i1 r i1 i =rr2 / rr
15
d i1=r i1 i d i
16
i=i1
9
Gambar 1 Metode Conjugate Gradient. METODE PENELITIAN Tahapan Penelitian Untuk menunjang keberhasilan suatu penelitian, maka dibuatlah tahapan-tahapan penelitian yang terstruktur. Pada penelitian ini ada beberapa tahapan yang dilakukan. Adapun tahapan tersebut disajikan pada Gambar 2. 4
yang dibuat membutuhkan argumen input yang harus dimasukkan pada saat program dijalankan, yaitu berupa ukuran matriks, nama file matriks, nama file vektor, dan banyaknya iterasi CG. Pada kode program juga ditambahkan fungsi pencatat waktu yang digunakan untuk menghitung waktu eksekusi. Fungsi pencatat waktu yang digunakan harus mampu mencatat waktu sampai dengan tingkat akurasi mili detik, agar memiliki tingkat presisi yang tinggi. Waktu eksekusi kemudian dicetak pada bagian akhir program sebagai log dari program. Penerapan Metode Foster
Gambar 2 Skema tahapan penelitian. Studi Pustaka Pada tahap ini dikumpulkan informasi mengenai algoritme CG dan metode yang biasanya digunakan dalam pengembangan aplikasi paralel hybrid. Pustaka-pustaka yang digunakan diperoleh dari beberapa buku cetak dan elektronik, dan juga dari beberapa halaman internet. Analisis Algoritme CG Hal yang pertama dilakukan pada penelitian ini yaitu mempelajari dan memahami langkahlangkah yang ada pada algoritme CG. Dengan memahaminya, maka dapat dengan mudah dibuat implementasi programnya. Pada tahap ini dilakukan analisis dari algoritme CG sekuensial yaitu meliputi cara kerja dan perhitungan tingkat kompleksitas dari algoritme. Implementasi CG Sekuensial Pada tahap ini dibuat implementasi sekuensial dari algoritme CG berdasarkan cara kerja yang telah dipelajari ditahap sebelumnya. Kode program sekuensial yang dibuat terdiri dari fungsi-fungsi yang mewakili proses-proses pada algoritme CG. Penggunaan fungsi ini dilakukan agar mempermudah dalam tahaptahap pengembangan selanjutnya. Program
Setelah implementasi sekuensial dibuat, langkah selanjutnya algoritme sekuensial diubah agar dapat dieksekusi secara paralel, yaitu dengan menerapkan metode Foster. Berdasarkan algoritme dan kode program CG sekuensial yang telah dibuat, kemudian dipelajari bagian atau fungsi mana saja yang dapat diparalelkan. Output dari tahap ini adalah seperti apa algoritme dan strategi paralel yang akan digunakan, meliputi konsep dekomposisi komputasi dan data, konsep komunikasi yang digunakan, dan bagaimana komputasi yang ada dijalankan secara paralel. Analisis dan Implementasi MPI Algoritme CG Selanjutnya pada tahap ini dilakukan analisis dan implementasi terhadap algoritme dan strategi yang telah dibuat pada tahap sebelumnya. Analisis yang dilakukan meliputi perhitungan kompleksitas komputasi dan komunikasi dari algoritme paralel, serta perhitungan tingkat performance paralelnya. Menurut Smith (2000) tahapan pertama dalam mengembangkan program paralel model hybrid adalah melakukan implementasi paralel secara message-passing terlebih dulu. Implementasi message-passing dibuat dengan bahasa pemrograman C dan menggunakan library MPI. Penggunaan fungsi-fungsi MPI baik dalam dekomposisi data maupun dalam komunikasi antar proses dipilih yang paling sesuai dengan strategi paralel yang telah ditentukan. Argumen program MPI juga tidak berbeda dengan argumen program sekuensial. Begitupun dengan perhitungan waktu eksekusi program, cara yang digunakan juga sama dengan program sekuensial.
5
Identifikasi, Analisis dan Implementasi Hybrid Tahap selanjutnya dalam pengembangan model hybrid adalah identifikasi algoritme MPI. Identifikasi dilakukan untuk mencari tahu fungsi-fungsi mana saja pada program yang dapat diparalelkan secara shared-memory yaitu dengan OpenMP. Menurut Chapman et al. (2008) paralel OpenMP dapat dilakukan salah satunya dengan cara membagi beban komputasi. Beban komputasi pada suatu algoritme biasanya terdapat pada pada konstruksi loop, atau dapat juga diketahui dengan membuat skema keterkaitan input dan output pada fungsi-fungsi yang digunakan, kemudian dicari tahu fungsifungsi yang tidak saling terkait. Kedua hal inilah yang kemudian diparalelkan secara OpenMP, sehingga algoritme CG MPI bisa menjadi algoritme CG hybrid. Setelah melakukan identifikasi, selanjutnya dilakukan analisis terhadap algoritme CG hybrid yang telah dibuat. Analisis yang dilakukan yaitu hasil analisis pada algoritme CG MPI ditambah dengan pengubahan hybrid. Implementasi pada kode program dilakukan sebagai tahap akhir dalam pengembangan model hybrid. Implementasi ini diterapkan pada fungsi-fungsi yang telah teridentifikasi dapat diparalelkan secara shared-memory. Pada kode program, ditambahkan baris-baris perintah dan directive OpenMP. Argumen input dari program juga ditambah satu lagi, yaitu argumen jumlah thread, sehingga jumlah thread yang diciptakan saat eksekusi program bisa dikontrol.
Tabel 1 Matriks yang digunakan pada percobaan Nama Matriks
Dimensi
662_bus
662 x 662
sherman1
1000 x 1000
ex10hs
2548 x 2548
bcsstk16
4884 x 4884
bloweybq
10001 x 10001
Percobaan Semua percobaan yang dilakukan pada tiap implementasi dilakukan dengan tiga kali perulangan atau iterasi, kemudian diambil ratarata waktu komputasinya. Percobaan implementasi MPI dan hybrid dilakukan dengan 1-8 buah komputer untuk komputasi, tetapi pada implementasi hybrid ditambahkan kombinasi jumlah 1-4 thread pada tiap penggunaan kombinasi komputer, sehingga ada 32 kombinasi untuk implementasi hybrid. Semua tahapan percobaan tersebut dilakukan pada lingkungan sistem operasi Linux. Pada saat percobaan dilakukan, komputer-komputer yang digunakan sudah dalam keadaan dikondisikan, maksudnya yaitu kondisi processor dalam keadaan idle. Output waktu yang keluar pada setiap eksekusi program dicatat dalam bentuk tabel yang selanjutnya akan digunakan dalam tahap analisis.
Perancangan Percobaan Pada tahap ini ditentukan rancangan dari percobaan yang akan dilakukan, termasuk di dalamnya metode percobaan dan data matriks yang digunakan. Ada lima buah matriks yang digunakan pada percobaan, matriks-matriks tersebut dapat dilihat pada Tabel 1. Percobaan implementasi MPI dan hybrid dilakukan dengan mengombinasikan argumenargumen input program. Untuk implementasi MPI, skema percobaan yang dilakukan yaitu mengombinasikan argumen matriks dan jumlah komputer, sedangkan untuk implementasi hybrid, skema percobaan yang dilakukan yaitu mengombinasikan argumen matriks, jumlah komputer dan jumlah thread.
Gambar 3 Skema jaringan yang digunakan pada percobaan. Pada saat percobaan digunakan tambahan dua komputer lagi yang salah satu digunakan sebagai file server untuk menyimpan kode program dan programnya, file matriks, dan file vektor, serta satu buah komputer lagi untuk running MPI. Skema jaringan yang digunakan dalam percobaan disajikan pada Gambar 3. 6
Spesifikasi dari masing-masing komputer yang digunakan adalah: 1. 2. 3. 4. 5. 6. 7. 8.
Intel Pentium® Core 2 Duo ( 2,20 GHz). DDR2 RAM 1024 MB. Hard disk 80 GB. Mouse dan Keyboard. LAN 100 Mbps. Sistem operasi Linux (openSUSE 11.2). Library MPI ( OpenMPI 1.4.7). OpenMP runtime library (libgomp44).
Analisis Hasil Percobaan Pada tahap ini akan dianalisis dengan menghitung performance metric berdasarkan waktu eksekusi dari hasil percobaan yang diperoleh. Analisis dilakukan terhadap hasil percobaan implementasi sekuensial, MPI, dan hybrid. HASIL DAN PEMBAHASAN
proses-proses yang ada pada algoritme CG sekuensial, seperti fungsi untuk membaca file matriks, membaca file vektor, dan fungsi CG. Di dalam fungsi CG terdapat beberapa fungsi lagi, seperti fungsi perkalian matriks vektor, fungsi perkalian dua vektor, dan fungsi saxpy. Fungsi pencatat waktu diletakkan di bagian awal sebelum proses membaca file matriks dan sesudah fungsi CG. 1
Diberikan SPL Ax=b
2
Pilih x 0 awal, x 0 =0 r 0 =b – Ax0
3 4
d 0 =r 0
5
i=0
6
rr =r T i r i
7 8 9
While imax and ∥r i∥≥tol q= A d i dq=d T i q i=rr / dq
n2 n
Analisis dan Implementasi Algoritme CG Sekuensial
10 11
x i1= x i i d i
n
Analisis algoritme CG sekuensial hanya diukur berdasarkan persamaan kompleksitas, namun karena pembahasan meliputi keseluruhan waktu eksekusi, maka tiap-tiap tahap akan dihitung, termasuk dalam pembacaan file matriks berukuran n x n maupun file vektor berukuran n . Adapun keseluruhan tahap dalam algoritme sekuensial adalah:
12
r i 1=r i − i q i
n
T i1
rr2=r r i1 i =rr2 / rr
n
14 15
d i1=r i1 i d i
n
16
i=i1
13
Gambar 4 Kompleksitas tahapan pada fungsi CG sekuensial.
1. Membaca file matriks ( n x n blok) sebagai koefisien SPL. 2. Membaca file vektor ( n blok) sebagai nilai target dari SPL. 3. Fungsi CG sekuensial untuk menghasilkan solusi SPL. Kompleksitas fungsi CG sekuensial berdasarkan Gambar 1 untuk tiap tahap disajikan pada Gambar 4. Untuk N kali iterasi pada CG, maka total kompleksitas pada keseluruhan tahap yaitu: 2
t sekuensial = N n 5n .
[9]
Gambar 5 Grafik perhitungan kompleksitas CG sekuensial. Penerapan Metode Foster
Dari Persamaan 10 dapat diketahui bahwa kompleksitas sangat tergantung dari ukuran matriks/vektor n dan banyaknya iterasi CG N . Waktu eksekusi dari implementasi sekuensial dapat direpresentasikan oleh Persamaan 9. Grafik hasil perhitungan Persamaan 9 disajikan pada Gambar 5.
Algoritme CG paralel didisain berdasarkan metode Foster, namun penggunaan metode Foster ini hanya digunakan untuk membuat algoritme CG MPI. Berikut ini adalah penjelasan dari tahapan-tahapannya.
Implementasi atau kode program yang dibuat terdiri atas fungsi-fungsi yang mewakili
Dalam menentukan strategi dekomposisi yang digunakan, pertama-tama harus diketahui
1. Partitioning
7
dulu komputasi yang ada. Komputasi yang ada dapat terlihat dari stuktur atau alur algoritme dan dari skema keterkaitan antar fungsi yang ada pada algoritme yang akan diparalelkan. Berdasarkan Gambar 1, skema keterkaitan antar fungsi di dalam iterasi CG disajikan pada Gambar 6.
Di dalam fungsi CG, komputasi perkalian matriks vektor dilakukan oleh tiap node. Komputasi ini dilakukan sesuai dengan matriks yang didapatkan masing-masing node. Hasil yang diperoleh masing-masing node n / p didistribusikan kepada keseluruhan node untuk digunakan pada tahapan komputasi berikutnya. Jadi seluruh tahapan yang ada pada Gambar 6 akan dikerjakan oleh seluruh node yang terlibat saat eksekusi. Untuk perkalian matriks vektor (no 1), masing-masing node akan melakukan komputasi dengan data matriks yang berbeda, sedangkan untuk komputasi no 2-8 masing-masing node akan mengerjakannya dengan data vektor yang sama. 2. Communication
Gambar 6 Skema keterkaitan fungsi pada iterasi CG. Dari gambar tersebut dapat dilihat bahwa tiap tahap pada algoritme CG saling memiliki keterkaitan, sehingga sulit jika diterapkan teknik pipeline. Untuk penerapan functional decomposition sebenarnya dapat dilakukan pada bagian komputasi saxpy (no 4, dan 5), hanya saja kurang tepat untuk diterapkan pada paralel MPI, karena biaya komunikasi yang dibutuhkan lebih besar dari pada beban komputasi yang ada. Oleh karena itu dekomposisi yang paling mungkin dan mudah dilakukan adalah domain decomposition. Domain decomposition yang dilakukan tidak pada semua tahapan algoritme CG, hanya pada perkalian matriks vektor saja. Pada perkalian dua vektor dan saxpy sebenarnya dapat diterapkan domain decomposition, hanya saja kurang tepat untuk paralel MPI, karena beban komputasinya terlalu kecil, sehingga jika dipaksakan untuk diparalelkan hanya akan menambah besar biaya komunikasi. Dalam melakukan domain decomposition, file matriks dengan ukuran n2 akan dibaca oleh node root, kemudian didistribusikan kepada p . Tiap node akan seluruh node mendapatkan matriks sebesar n2 / p . Matriks akan didekomposisi secara row-wised bukan secara column-wised, karena kompleksitas komunikasi secara row-wised lebih kecil. Pada distribusi vektor, file vektor dengan ukuran n akan dibaca oleh node root, kemudian didistribusikan kepada seluruh node. Tiap node akan mendapatkan vektor yang sama dengan ukuran n pula.
Berdasarkan tahap partitioning, proses komunikasi yang diterapkan yaitu secara global communication. Proses komunikasi ini dibutuhkan pada setiap tahap. Komunikasi pertama terjadi pada saat pendistribusian matriks oleh node root yang dilakukan dengan fungsi MPI_Scatterv. Proses komunikasi yang kedua pada saat pendistribusian vektor oleh node root dengan menggunakan fungsi MPI_Bcast. Komunikasi ketiga yaitu di dalam fungsi CG, pada saat tiap-tiap node mendistribusikan hasil perkalian matriks vektor ke seluruh node dan ini dilakukan pada setiap iterasi. Fungsi yang digunakan pada komunikasi ini adalah MPI_Allgatherv. 3. Agglomeration Berdasarkan pengertian dari agglomeration, maka tidak terdapat proses agglomeration secara eksplisit pada disain algoritme CG paralel. Hal ini dikarenakan memang tidak ada pengombinasian task-task yang saling terkait, namun secara implisit terdapat pada fungsifungsi MPI yang digunakan, seperti MPI_Gatherv, MPI_Bcast, dan MPI_Allgatherv. 4. Mapping Komputasi yang diparalelkan secara MPI hanyalah pada bagian perkalian matriks vektor, jadi mapping yang dilakukan yaitu menugaskan seluruh node yang tersedia untuk melakukan komputasi tersebut sesuai komputasi yang didapat masing-masing node. Berdasarkan strategi paralel yang telah dirancang dengan metode Foster, maka struktur algoritme CG pada bagian iterasinya disajikan pada Gambar 7. 8
Komputasi
q local = Alocal d i
q= Allgather qlocal
Keterangan Perkalian MatVec, tiap node memiliki matriks berbeda A local , dan memiliki vektor d i yang sama, dihasilkan vektor q local berukuran n/ p yang berbeda pada tiap node. Semua node melakukan allgather, sehingga tiap node memiliki vektor q yang berukuran n secara utuh.
dq=d T i q i=rr / dq x i1= x i i d i r i 1=r i − i q i rr2=rTi1 r i1 i =rr2 / rr
Semua node akan melakukan komputasi pada bagian ini dan akan menghasilkan data vektor yang sama.
d i1=r i1 i d i
2
t matriks =
t wn p – 1 . p
[11]
2. Distribusi vektor Dalam mendistribusikan vektor, ukuran vektor yang didapatkan oleh seluruh node adalah sama besar, yaitu n . Fungsi MPI_Bcast digunakan dalam pendistribusian vektor ke seluruh node. Menurut Grama et al (2003), kompleksitas MPI_Bcast dengan mengabaikan startup time t s yaitu: t w m log p .
[12]
sehingga kompleksitas mendistribusikan file vektor t vektor adalah: t vektor =t w n log p .
i=i1
Gambar 7 Struktur algoritme CG MPI pada bagian iterasi. Analisis dan Implementasi Algoritme CG MPI Algoritme paralel MPI yang dibuat terdiri dari tiga bagian, pertama bagian distribusi matriks, kedua distribusi vektor dan ketiga bagian iterasi fungsi CG. Dalam menganalisis kompleksitas algoritme MPI yang telah dibuat, ketiga bagian tersebut diikutsertakan seluruhnya dalam perhitungan. Berikut ini adalah kompleksitas dari masing-masing bagian tersebut: 1. Distribusi matriks Dalam mendistribusikan file matriks 2 berukuran masing-masing node n , 2 mendapatkan bagian matriks sebesar n / p . Dalam mendistribusikan file matriks tersebut, implementasi MPI yang dibuat yaitu menggunakan fungsi MPI_Scatterv. Menurut Grama et al (2003), kompleksitas MPI_Scatter / MPI_Scatterv dan MPI_Gather dengan mengabaikan startup time t s yaitu: t w m p – 1 .
m : ukuran message yang akan dikirim. p : banyaknya node yang menerima message. Ukuran message yang akan dikirim m adalah sehingga berdasarkan n2/ p , kompleksitas MPI_Scatterv, maka kompleksitas dalam mendistribusikan file matriks t matriks yaitu:
[10]
t w : waktu dibutuhkan untuk mentransfer message per word.
[13]
3. Iterasi fungsi CG Berdasarkan partitioning yang telah ditentukan, maka pada bagian iterasi fungsi CG bagian yang diparalelkan secara MPI adalah pada perkalian matriks vektor. Hasil perkalian ini kemudian didistribusikan ke seluruh node. Pada implementasinya, fungsi-fungsi sekuensial yang digunakan tidak mengalami perubahan, namun hanya dilakukan penambahan fungsi dalam pendistribusian hasil perkalian matriks vektor saja. Fungsi yang digunakan dalam hal ini adalah MPI_Allgatherv. Pada dasarnya fungsi MPI_Allgatherv hampir sama dengan MPI_Gatherv, hanya saja pada MPI_Allgatherv seluruh node melakukan pengiriman data, sehingga kompleksitasnya pun sama. Dengan demikian kompleksitas pada bagian iterasi ini t iterasi adalah: t iterasi = N n
n tw p – 15 . p p
[14]
Struktur algoritme MPI dan kompleksitasnya tiap tahap pada bagian iterasi CG disajikan pada Gambar 8. Berdasarkan Gambar 8, maka total kompleksitas algoritme CG MPI t mpi pada tiga bagian yang telah dijelaskan diatas adalah: 9
t mpi =tmatriks t vektor titerasi . t mpi =n
.
t w p−1 n N nt w log p N 5 p p
[16]
1
Diberikan SPL Ax=b
2
Pilih x 0 awal, x 0 =0
3
r 0 =b – Ax0
4
d 0 =r 0
5
i=0
6
rr =r T i r i
7
[15]
q local = Alocal d i
9
q= Allgather q local T i
S=
N n5 t w p−1 n . N nt w log p N 5 p p
[17]
Pada Gambar 10 disajikan grafik hasil perhitungan speedup berdasarkan Persamaan 17 terhadap lima ukuran matriks yang digunakan. n 2/ p
t w n/ p p – 1 n
10
dq=d
11
i=rr / dq
12
x i1= x i i d i
n
13
r i1=r i − i q i
n
q
T i1
1. Speedup Berdasarkan Persamaan 1, 9, dan 16 maka speedup dapat dihitung menggunakan Persamaan 17.
While imax and ∥r i ∥≥tol
8
Setelah diketahui kompleksitas total dari implementasi yang telah dibuat, selanjutnya dilakukan analisis performance-nya.
14
rr2=r
15
i =rr2 / rr
16
d i1=r i1 i d i
17
i=i1
r i1
n
n
Gambar 8 Struktur algoritme dan kompleksitas fungsi CG MPI. Dalam perhitungan kompleksitas pada penelitian ini, kecepatan jaringan (LAN) yang digunakan adalah 100 Mbps dan tipe data yang digunakan adalah double. Karena tipe data double, maka ukuran message per word adalah 8 byte, sehingga nilai t w adalah 0.64 x 106 .
Gambar 10 Grafik perhitungan speedup CG MPI. Dari Gambar 10, dapat diketahui bahwa: •
Nilai speedup yang diperoleh hampir mendekati dengan nilai ideal dari speedup untuk setiap jumlah node yang digunakan, yaitu mendekati linear.
•
Untuk setiap ukuran matriks yang diinputkan, semakin tinggi jumlah node yang digunakan, semakin tinggi speedup yang diperoleh.
•
Semakin tinggi jumlah digunakan, untuk ukuran semakin kecil, maka nilai diperoleh semakin menurun nilai ideal.
node yang matriks yang speedup yang dan menjauhi
2. Efisiensi Nilai efisiensi didapatkan menggunakan Persamaan 18. Gambar 9 Grafik perhitungan kompleksitas CG MPI. Grafik hasil perhitungan kompleksitas berdasarkan Persamaan 16 terhadap lima ukuran matriks yang digunakan disajikan pada Gambar 9.
E=
dengan
N n5 . [18] t w p−1 N nt w p log pN n5 p
Pada Gambar 11, disajikan grafik hasil perhitungan efisiensi berdasarkan Persamaan 18 terhadap lima ukuran matriks yang digunakan.
10
digunakan dapat diketahui dengan persamaan 21. Penerapan Model Hybrid Dalam penerapan model paralel hybrid dari model paralel message-passing atau MPI, hal pertama yang dilakukan adalah identifikasi bagian-bagian yang dapat diparalelkan secara shared-memory atau OpenMP. Berdasarkan struktur algoritme CG MPI yang telah dibuat, terdapat tiga bagian utama, yaitu distribusi matriks, distribusi vektor, dan iterasi fungsi CG. Gambar 11 Grafik perhitungan efisiensi CG MPI. Dari Gambar 11, dapat diketahui bahwa: •
Efisiensi yang diperoleh hampir mendekati nilai ideal dari efisiensi, yaitu 1.
•
Semakin tinggi jumlah node yang digunakan, nilai efisiensinya mengalami penurunan, namun tingkat penurunannya kecil.
•
Semakin tinggi jumlah digunakan, untuk ukuran semakin kecil, maka nilai diperoleh semakin menurun nilai ideal.
node yang matriks yang efisiensi yang dan menjauhi
3. Cost Untuk nilai Persamaan 19.
cost
didapatkan
dengan
C=n t w p−1 N nt w p log p N n5 p .
[19] 4. Total Parallel Overhead Untuk nilai overhead didapatkan dengan Persamaan 20. T o =nt w p−1 N nt w plog p5 N p−1 .
[20] 5. Isoefisiensi Dari Persamaan overhead yang diperoleh, maka dapat diketahui isoefisiensi dari algoritme yang dibuat. Untuk setiap peningkatan jumlah node, seberapa besar problem size W yang harus menjadi input untuk mempertahankan nilai efisiensi yang ingin diperoleh. W=
E n t w p − 1 N n t w p log p 5 N p − 1 E − 1
. [21]
Jadi jika ingin diperoleh nilai efisiensi sebesar E untuk setiap peningkatan jumlah node, maka ukuran problem size yang harus
Dari kompleksitas tiga bagian tersebut, kompleksitas tertinggi ada pada bagian iterasi dikarenakan pada bagian ini terjadi komputasi, sehingga pada bagian inilah yang lebih tepat diparalelkan secara OpenMP. Sebenarnya pada bagian distribusi matriks dan distribusi vektor dapat diparalelkan secara OpenMP, namun pada kedua bagian ini komputasi yang terjadi hanyalah baca file dan distribusi data lewat jaringan. Oleh karena itu lamanya waktu komputasi pada bagian ini lebih ditentukan oleh kecepatan hardware, sehingga tidak tepat diparalelkan secara OpenMP. Pada bagian Penerapan Metode Foster pada tahap partitioning, disebutkan bahwa ada beberapa komputasi yang tidak tepat bila dipararelkan secara MPI. Bagian-bagian inilah yang akan dipararelkan secara OpenMP. Berdasarkan Gambar 8, komputasi-komputasi yang ada adalah perkalian matriks vektor, perkalian dua vektor, dan saxpy. Pada ketiga komputasi ini terdapat konstruksi-konstruksi loop yang dapat diparalelkan, jadi pada komputasi-komputasi inilah dilakukan pararel OpenMP. Cara seperti ini sama saja dengan melakukan domain decomposition, karena pada hakikatnya yang dipararelkan adalah data. Selain dengan melakukan pararel pada kontruksi loop, bila dilihat Gambar 6 pada no 4 dan 5, bagian ini dapat dilakukan partitioning secara functional decomposition. Bagian ini tidak tepat jika dipararelkan secara MPI, namun lebih tepat dipararelkan secara OpenMP. Dengan dilakukannya functional decomposition, maka pada bagian ini terjadi dua pararelisasi, yaitu pararelisasi fungsi secara struktural dan paralelisasi data didalamnya. Berdasarkan strategi paralel hybrid yang telah dirancang, maka struktur algoritme CG hybrid pada bagian iterasinya disajikan pada Gambar 12.
11
Komputasi
Keterangan
q local = Alocal d i
Perkalian MatVec akan dilakukan oleh semua node secara MPI, dan dilakukan oleh semua thread secara OpenMP pada tiap node.
q= Allgather q local
Semua node melakukan allgather, sehingga tiap node memiliki vektor q yang berukuran n secara utuh.
dq=d T i q
Semua node akan melakukan komputasi secara paralel OpenMP.
i=rr / dq x i1= x i i d i
r i 1=r i − i q i
rr2=rT i1 r i1
Semua node akan melakukan komputasi secara paralel OpenMP dan kedua operasi saxpy ini diparalel secara data dan fungsi Semua node akan melakukan komputasi secara paralel OpenMP.
i =rr2 / rr Semua
akan komputasi secara paralel OpenMP.
d i1=r i 1 i d i melakukan
node
i=i1
Gambar 12 Struktur algoritme CG hybrid pada bagian iterasi. Analisis dan Implementasi Algoritme CG Hybrid Dalam eksekusi bagian loop yang diparalelkan secara OpenMP, sejumlah thread akan dibangkitkan untuk mengeksekusi bagian loop tersebut secara bersamaan. Jika suatu konstruksi loop memiliki kompleksitas n t dieksekusi oleh thread, maka kompleksitasnya menjadi n / t . Dengan demikian kompleksitas algoritme CG hybrid akan ditentukan oleh banyaknya node p , banyaknya thread t , ukuran matriks dan vektor n , serta banyaknya iterasi CG N . Agar suatu loop dieksekusi secara paralel OpenMP, maka digunakanlah compiler directive atau pragma. Berikut ini adalah kode program pada bagian perkalian matriks vektor yang sudah ditambahkan pragma.
#pragma omp parallel for default(none) shared(rowSize, colSize, q, A, x) private(i, j) for(i=0;i
Pada kode program tersebut, matriks A akan dipartisi secara row-wised, karena yang diparalelkan adalah outer loop. Jika dieksekusi oleh t thread, maka masing-masing thread akan melakukan outer loop sebanyak rowSize /t dan melakukan inner loop sebanyak colSize . Berdasarkan strategi paralel hybrid yang telah ditentukan, maka struktur dan kompleksitas dari algoritme CG hybrid disajikan pada Gambar 13. 1 2 3 4 5 6 7 8 9 10 11
Diberikan SPL Ax=b Pilih x 0 awal, x 0 =0 r 0 =b – Ax0 d 0 =r 0 i=0
12
x i1= x i i d i
13
r i1=r i − i q i
14 15 16 17
rr2=rT i1 r i1 i =rr2 / rr d i1=r i1 i d i i=i1
rr =r T i r i While imax and ∥r i∥≥tol q local = Alocal d i n 2 / pt q= Allgather q local t w n / p p – 1 T n/ t dq=d i q i=rr / dq n/ t n/ t n/ t
Gambar 13 Struktur algoritme dan kompleksitas fungsi CG hybrid. Berdasarkan Gambar 13, maka kompleksitas pada bagian fungsi CG hybrid adalah: t iterasi = N n
n tw 4 p – 1 . pt p t
[22]
Dengan demikian kompleksitas algoritme CG t hybrid hybrid menjadi: t hybrid =n
total
.
t w p−1 N n N n t w log p 4 p t p
[23]
Pada Gambar 14 disajikan hasil perhitungan kompleksitas berdasarkan Persamaan 23 untuk 12
setiap jumlah thread dengan ukuran matriks tetap. Sedangkan pada Gambar 15 ditampilkan hasil perhitungan terhadap lima ukuran matriks yang digunakan dengan jumlah thread tetap.
•
Speedup yang diperoleh hampir mendekati nilai ideal pada tiap-tiap kombinasi node dan thread.
•
Untuk setiap ukuran matriks yang diinputkan, semakin tinggi jumlah node dan thread yang digunakan, semakin tinggi speedup yang diperoleh.
•
Semakin tinggi jumlah node yang digunakan dengan jumlah thread tetap, untuk ukuran matriks yang semakin kecil, maka nilai speedup yang diperoleh semakin menurun dan menjauhi nilai ideal.
Gambar 14 Grafik perhitungan kompleksitas untuk tiap jumlah thread dengan ukuran matriks 2548 x 2548 .
Gambar 16 Grafik perhitungan speedup untuk tiap jumlah thread dengan ukuran matriks 2548 x 2548 . Gambar 15 Grafik perhitungan kompleksitas untuk tiap ukuran matriks dengan 2 thread. Setelah diketahui kompleksitas total dari implementasi hybrid yang telah dibuat, selanjutnya dilakukan analisis performance-nya. 1. Speedup Berdasarkan Persamaan 23, maka speedup dari implementasi hybrid dihitung dengan Persamaan 24. S=
N n5
t w p−1 . N n N n t w log p 4 p t p [24]
Berdasarkan Persamaan 24, pada Gambar 16 disajikan grafik hasil perhitungan speedup hybrid dengan jumlah thread 1, 2, 3, dan 4 pada salah satu ukuran matriks yang digunakan. Kemudian pada Gambar 17 disajikan grafik speedup hybrid untuk setiap ukuran matriks yang digunakan dengan dua thread. Dari Gambar 16 dan Gambar 17 dapat diketahui bahwa:
Gambar 17 Grafik perhitungan speedup untuk tiap ukuran matriks dengan 2 thread. 2. Efisiensi Untuk nilai efisiensi, maka dapat dihitung dengan persamaan 25. E=
N n5 t w p−1 N n t w p log p
N . n4 p t [25]
Grafik hasil perhitungan dari Persamaan 25, disajikan pada Gambar 18 dan Gambar 19. Grafik untuk salah satu matriks yang digunakan disajikan pada Gambar 18, sedangkan pada Gambar 19 disajikan grafik untuk setiap ukuran 13
matriks yang digunakan dengan dua thread.
4. Total Parallel Overhead
Dari kedua Gambar 18 dan Gambar 19 dapat diketahui bahwa:
Untuk nilai overhead didapatkan dengan Persamaan 27.
•
•
•
Efisiensi yang diperoleh hampir mendekati nilai ideal dari efisiensi, yaitu 1 pada tiaptiap kombinasi node dan thread. Semakin tinggi jumlah node yang digunakan dengan jumlah thread tetap, semakin kecil ukuran matriks, maka nilai efisiensinya semakin menurun. Semakin tinggi jumlah node dan jumlah thread yang digunakan, untuk ukuran matriks yang semakin kecil, nilai efisiensi yang diperoleh mengalami penurunan dan menjauhi nilai ideal, namun tingkat penurunannya kecil.
T o= n t w p −1 N n t w p log p
.
N n 4 p − n t −5 t t
[27]
5. Isoefisiensi Kemudian untuk memperoleh efisiensi yang tetap E , maka untuk setiap peningkatan jumlah node dan jumlah thread, problem size W yang harus digunakan dihitung dengan Persamaan 28. W=
E T . E − 1 o
[28]
Analisis Hasil Waktu Eksekusi Untuk menganalisis hasil waktu eksekusi, dilakukan perbandingan hasil perhitungan kompleksitas dengan hasil waktu percobaan yang diperoleh. Waktu eksekusi hasil percobaan implementasi CG sekuensial dibandingkan dengan hasil kompleksitas yang telah dihitung pada Persamaan 9. Grafik waktu eksekusi implementasi CG sekuensial disajikan pada Gambar 20.
Gambar 18 Grafik perhitungan efisiensi untuk tiap jumlah thread dengan ukuran matriks 2548 x 2548 .
Setelah dibandingkan dengan seksama antara Gambar 5 dan Gambar 20, terlihat bahwa keduanya memiliki kesamaan bentuk, berarti hal ini menunjukkan hasil perhitungan kompleksitas dan hasil percobaan memiliki kesesuaian. Semakin besar ukuran matriks semakin tinggi waktu eksekusinya, jadi waktu eksekusi sekuensial benar dipengaruhi oleh ukuran matriks/vektor.
Gambar 19 Grafik perhitungan efisiensi untuk tiap ukuran matriks dengan 2 thread. 3. Cost Untuk nilai Persamaan 26.
cost
didapatkan
. C = n t w p −1 N nt w p log p
dengan
N n 4 p . t
[26]
Gambar 20 Grafik waktu eksekusi implementasi CG sekuensial. Pada implementasi MPI, grafik waktu eksekusi percobaan pada tiap ukuran matriks disajikan pada Gambar 21. Jika Gambar 9 dibandingkan dengan Gambar 21, maka akan 14
terlihat memiliki kesesuaian bentuk walaupun tidak terlalu sama persis. Hal ini menunjukkan bahwa hasil perhitungan kompleksitas CG MPI bersesuaian dengan hasil percobaan implementasi MPI.
Gambar 21 Grafik waktu eksekusi implementasi MPI.
memiliki 2 core. Sehingga penggunaan jumlah thread lebih dari jumlah core processor menjadi penyebab waktu eksekusi lebih lambat atau paling tidak hampir menyamai waktu eksekusi 2 thread.
Gambar 22 Grafik waktu eksekusi untuk setiap implementasi dengan ukuran matriks 2548 x 2548 .
Dari Gambar 21 juga dapat diketahui bahwa waktu eksekusi dipengaruhi oleh jumlah node yang digunakan, namun bukan berarti semakin banyak node yang digunakan waktu eksekusi akan menurun signifikan. Grafik tersebut menunjukkan untuk jumlah node mendekati 8, maka semakin landai bentuk garisnya. Hal ini berarti menunjukkan pengaruh jumlah node semakin berkurang terhadap menurunnya waktu eksekusi. Selanjutnya disajikan grafik perbandingan waktu eksekusi untuk implementasi MPI dan hybrid untuk ukuran matriks 2548 x 2548 dan 4884 x 4884 pada Gambar 22 dan Gambar 23. Sedangkan pada Gambar 24, disajikan grafik waktu eksekusi pada tiap matriks dengan menggunakan 2 thread. Jika dibandingkan Gambar 22 dan Gambar 23 dengan Gambar 14, maka ada kesesuaian bentuk yakni menurun pada setiap thread yang digunakan, namun tingkat penurunannya lebih rendah dibandingkan Gambar 14. Selain itu pada Gambar 22 dan Gambar 23, urutan waktu eksekusi hybrid pada penggunaan 1 thread sampai 4 thread tidak sesuai dengan hasil perhitungan kompleksitas seperti pada Gambar 8. Seharusnya semakin tinggi jumlah thread yang digunakan, semakin rendah waktu eksekusi, namun tidak demikian adanya. Waktu eksekusi dengan 3 thread lebih rendah dari pada waktu eksekusi 2 thread, dan waktu eksekusi 4 thread hampir menyamai waktu eksekusi 2 thread walaupun masih lebih rendah sedikit pada 2 thread. Anomali ini terjadi karena processor pada komputer yang digunakan hanya
Gambar 23 Grafik waktu eksekusi untuk setiap implementasi dengan ukuran matriks 4884 x 4884 .
Gambar 24 Grafik waktu eksekusi implementasi hybrid untuk tiap ukuran matriks dengan 2 thread. Berdasarkan hasil perhitungan kompleksitas, untuk perbandingan waktu eksekusi hybrid 1 thread dengan MPI, seharusnya nilai kompleksitas implementasi MPI lebih tinggi sedikit dari hybrid 1, akan tetapi pada hasil waktu eksekusi memperlihatkan sebaliknya. 15
Kemudian dilakukan pengamatan processor usage pada saat eksekusi program berlangsung. Saat eksekusi hybrid 1 thread, pada masingmasing komputer hanya 1 core processor yang melakukan komputasi dengan nilai usage hampir 100%. Sedangkan pada saat eksekusi MPI, 2 core processor yang tersedia pada masing-masing komputer melakukan eksekusi dengan nilai usage sekitar 50%. Jadi pada eksekusi MPI, komputasi didistribusikan pada seluruh core processor yang tersedia. Hal inilah yang menyebabkan waktu eksekusi implementasi MPI lebih rendah dibandingkan dengan hybrid 1 thread. Pada Gambar 24, grafik yang dihasilkan sedikit berbeda dengan hasil perhitungan kompleksitas pada Gambar 15. Garis-garis pada Gambar 24 terlihat lebih landai, namun secara keseluruhan masih menurun seiring semakin tinggi jumlah node yang digunakan. Grafik untuk setiap kombinasi matriks, jumlah node, dan jumlah thread yang digunakan lebih lengkapnya disajikan pada Lampiran 1. Dari Gambar 22, Gambar 23, dan Gambar 24, dapat diketahui bahwa waktu eksekusi implementasi hybrid memang sangat dipengaruhi oleh ukuran matriks/vektor, jumlah node, dan jumlah thread yang digunakan. Waktu eksekusi tercepat diperoleh oleh hybrid 2 thread dengan 8 node. Secara umum pada grafik-grafik waktu eksekusi hasil percobaan MPI dan hybrid, seharusnya waktu eksekusi semakin menurun drastis untuk setiap peningkatan jumlah node pada ukuran matriks 10001. Akan tetapi tidak demikian adanya, penurunan waktu eksekusi tidak terlampau tinggi sebagaimana mestinya. Kemudian dilakukan analisis lebih lanjut, yaitu dengan dilakukan pemisahan waktu komputasi yang ada, seperti waktu distribusi matriks/vektor dan waktu iterasi CG. Grafik hasil pemisahan disajikan pada Gambar 25. Dari pemisahan tersebut dapat diketahui bahwa waktu iterasi CG pada kedua implementasi jauh lebih kecil dari pada total waktu eksekusi. Berarti lamanya waktu eksekusi pada ukuran matriks 10001 disebabkan oleh lamanya waktu distribusi matriks/vektor. Lebih tepatnya waktu distribusi matriks yang menjadi penyebab lamanya waktu eksekusi. Lamanya waktu ini lebih disebabkan oleh proses I/O. Pada masing-masing komputer, hanya terdapat main memory (RAM) sebesar 1 GB, sehingga swap memory yang terdapat di
hard disk dilibatkan dalam proses pembacaan matriks yang berukuran besar. Jadi lamanya waktu distribusi matriks dikarenakan saat eksekusi berlangsung terdapat proses baca tulis ke hard disk.
Gambar 25 Grafik waktu eksekusi dan waktu iterasi implementasi MPI dan hybrid 2 thread untuk ukuran matriks 10001 x10001 . Analisis Hasil Speedup Berdasarkan hasil waktu eksekusi, kemudian dihitung nilai speedup dari tiap-tiap implementasi dan tiap-tiap kombinasi. Grafik speedup untuk implementasi MPI disajikan pada Gambar 26.
Gambar 26 Grafik speedup hasil percobaan implementasi MPI. Jika dilakukan perbandingan antara Gambar 26 dengan Gambar 16, maka akan tampak sangat berbeda. Pada Gambar 16 nilai speedup hampir mendekati nilai idealnya pada tiap jumlah node, namun pada Gambar 26 nilai speedup tertinggi tidak sampai 4. Hal ini diakibatkan dari waktu eksekusi yang dihasilkan implementasi MPI tidak sesuai dengan hasil perhitungan kompleksitas. Pada Gambar 21 semakin tinggi jumlah node, maka semakin landai grafiknya, sehingga pada Gambar 26 semakin tinggi jumlah node, maka speedup yang diperoleh semakin menjauhi nilai ideal. 16
Kemudian untuk grafik speedup implementasi hybrid disajikan pada Gambar 27 dan Gambar 28. Grafik speedup untuk setiap kombinasi matriks, jumlah node, dan jumlah thread yang digunakan lebih lengkapnya disajikan pada Lampiran 2.
Gambar 27 Grafik speedup hasil percobaan hybrid untuk setiap ukuran matriks dengan 2 thread.
penurunan efisiensi tidak sampai 0.9, namun pada Gambar 29 penurunan efisiensi sampai pada 0.2. Dari grafik ini dapat diketahui bahwa nilai efisiensi semakin menurun seiring bertambahnya jumlah node yang digunakan.
Gambar 29 Grafik efisiensi hasil percobaan implementasi MPI. Kemudian untuk efisiensi hasil percobaan hybrid disajikan pada Gambar 30 dan Gambar 31. Jika kedua gambar ini dibandingkan dengan Gambar 18 dan Gambar 19, maka efisiensi yang diperoleh juga terlihat menurun drastis sesuai dengan speedup yang diperoleh.
Gambar 28 Grafik speedup hasil percobaan untuk setiap implementasi dengan ukuran matriks 2548 x 2548 . Jika Gambar 27 dan Gambar 28 dibandingkan dengan Gambar 16 dan Gambar 17, maka terlihat perbedaannya. Seharusnya speedup tertinggi diperoleh dengan penggunaan 4 thread, namun tidak demikian pada hasil percobaan. Pada hybrid 4 thread, speedup yang diperoleh hampir sama dengan hybrid 2 thread, sesuai dengan waktu komputasi yang diperoleh. Namun begitu secara keseluruhan speedup yang diperoleh semakin tinggi seiring dengan bertambahnya jumlah node. Speedup implementasi hybrid tertinggi diperoleh pada penggunaan 8 node dengan 2 thread. Analisis Hasil Efisiensi Selanjutnya setelah dilakukan analisis speedup, berikut ini pada Gambar 29 disajikan grafik efisiensi dari hasil percobaan implementasi MPI. Jika Gambar 29 dibandingkan dengan Gambar 17, maka jelas sangat terlihat berbeda. Pada Gambar 17
Gambar 30 Grafik efisiensi hasil percobaan hybrid untuk setiap ukuran matriks dengan 2 thread.
Gambar 31 Grafik efisiensi hasil percobaan untuk setiap implementasi dengan ukuran matriks 2548 x 2548 . Seharusnya semakin tinggi ukuran matriks, semakin tinggi pula efisiensinya. Namun jika dilihat dari waktu komputasi, memang terdapat 17
anomali seperti dijelaskan pada Gambar 25, sehingga efisiensi tertinggi ada pada ukuran matriks 4884. Grafik efisiensi dari implementasi hybrid lebih lengkapnya disajikan pada Lampiran 3. Secara keseluruhan efisiensi yang diperoleh implementasi MPI dan hybrid, nilai tertinggi diperoleh oleh implementasi MPI. Hal ini dikarenakan speedup yang diperoleh tidak sesuai seperti yang diharapkan. Efisiensi adalah nilai speedup dibagi dengan jumlah processor. Pada hakikatnya total seluruh processor yang digunakan untuk implementasi hybrid adalah jumlah node dikali jumlah thread p x t . Semakin besar kombinasi yang digunakan, semakin besar pembagi speedup untuk menghasilkan nilai efisiensi, sehingga nilai efisiensi semakin kecil. Seharusnya bila diimbangi dengan peningkatan nilai speedup, maka nilai efisiensi akan stabil, namun tidak demikian, sehingga nilai efisiensi semakin kecil. Analisis Cost Pada hasil percobaan implementasi MPI, nilai cost terbesar ada pada ukuran matriks 10001. Grafiknya cost implementasi MPI disajikan pada Gambar 32.
Gambar 32 Grafik cost hasil percobaan implementasi MPI.
Gambar 33 Grafik cost hasil percobaan untuk setiap implementasi dengan ukuran matriks 2548 x 2548 .
Pada hasil percobaan hybrid, nilai cost terbesar diperoleh pada implementasi hybrid 3 thread pada setiap ukuran matriks dan pada setiap jumlah node yang digunakan. Hal ini memang wajar adanya karena waktu eksekusi yang diperoleh pada hybrid 3 thread tidak lebih cepat dari pada hybrid 2 thread dan hybrid 4 thread. Berdasarkan Gambar 33, dengan mengabaikan nilai cost pada hybrid 3 thread, dapat diketahui bahwa semakin besar kombinasi node dan thread, semakin besar nilai cost yang dihasilkan. Grafik cost untuk implementasi hybrid dengan kombinasi node dan thread lainnya disajikan pada Lampiran 4. Berdasarkan Persamaan 19 dan Persamaan 26, seharusnya nilai cost untuk setiap jumlah node yang digunakan dengan ukuran matriks tetap, idealnya nilainya hampir tetap atau meningkat namun kecil, tetapi tidak demikian dengan nilai cost hasil percobaan. Hal ini terjadi karena tingkat penurunan waktu eksekusi seiring dengan semakin besar jumlah node yang digunakan yang sangat dipengaruhi oleh waktu distribusi matriks. Analisis Total Parallel Overhead
Gambar 34 Grafik overhead hasil percobaan implementasi MPI.
Gambar 35 Grafik overhead hasil percobaan untuk setiap implementasi dengan ukuran matriks 2548 x 2548 .
18
Pada Gambar 34 dan Gambar 35 disajikan grafik overhead untuk implementasi MPI dan hybrid. Dari Gambar 34 dapat diketahui bahwa untuk implementasi MPI, nilai overhead pada semua matriks semakin besar seiring bertambahnya jumlah node dan nilai overhead tertinggi ada pada ukuran matriks 10001. Sedangkan pada Gambar 35 dapat diketahui bahwa nilai overhead semakin tinggi seiring dengan semakin tingginya kombinasi jumlah node dan thread yang digunakan dengan pengecualian pada hybrid 3 thread. Berdasarkan hasil perhitungan Persamaan 20 dan Persamaan 27, seharusnya nilai overhead memang mengalami kenaikan, namun tidak sebesar seperti yang terlihat pada Gambar 34 dan Gambar 35. Hal ini sesuai dengan yang terjadi pada nilai cost, karena memang nilai cost dan overhead saling berkaitan. Grafik overhead implementasi hybrid lebih lengkapnya disajikan pada Lampiran 5. KESIMPULAN DAN SARAN Kesimpulan Dari hasil pembahasan dapat disimpulkan bahwa: 1. Waktu eksekusi metode CG untuk semua implementasi semakin meningkat seiring dengan semakin besarnya ukuran matriks yang digunakan. Sebagai contoh: •
Implementasi sekuensial secara berturutturut untuk ukuran matriks 1000, 2548, dan 4884 dibutuhkan waktu sebesar 4.47, 28.94 dan 42.84 detik.
•
Implementasi MPI dengan 4 node secara berturut-turut untuk ukuran matriks 1000, 2548, dan 4884 dibutuhkan waktu sebesar 2.52, 12.57, dan 42.84 detik.
•
Implementasi hybrid 2 thread dengan 4 node secara berturut-turut untuk ukuran matriks 1000, 2548, dan 4884 dibutuhkan waktu sebesar 2.12, 9.87 dan 32.44 detik.
2. Waktu eksekusi metode CG pada implementasi MPI menurun dibandingkan dengan waktu eksekusi implementasi sekuensial. Waktu implementasi MPI juga semakin menurun seiring dengan semakin besar jumlah node yang digunakan. Sebagai contoh untuk ukuran matriks 2548, secara berturut-turut pada implementasi sekuensial, MPI dengan 1, 2, 3, 4 node dibutuhkan
waktu 28.94,28.44,17.79,14.40,12.57 detik. 3. Waktu eksekusi metode CG pada implementasi hybrid menurun dibandingkan dengan waktu eksekusi implementasi MPI. Waktu eksekusi implementasi hybrid juga semakin menurun seiring dengan semakin besarnya kombinasi node dan thread yang digunakan. Sebagai contoh: •
Untuk ukuran matriks 2548, secara berturut-turut pada implementasi MPI dengan 2 node, hybrid 1 thread, 2 thread dengan 2 node dibutuhkan waktu 17.79, 19.07, 12.61.
•
Untuk ukuran matriks 4884, secara berturut-turut pada implementasi MPI dengan 4 node, MPI dengan 5 node, hybrid 2 thread 4 node, hybrid 2 thread 5 node dibutuhkan waktu 29.37, 24.32, 18.95, 16.01.
4. Pengaruh bertambahnya jumlah node dan jumlah thread yang digunakan terhadap penurunan waktu eksekusi pada implementasi CG MPI dan CG hybrid secara keseluruhan semakin berkurang. 5. Nilai speedup tertinggi didapatkan pada implementasi hybrid 2 thread, karena sesuai dengan jumlah core processor pada komputer yang digunakan. Nilai speedup semakin bertambah seiring dengan bertambahnya jumlah node dan thread yang digunakan, namun nilai speedup yang diperoleh baik pada implementasi MPI maupun hybrid dapat dikatakan jauh dari nilai ideal yaitu sebesar p . 6. Nilai efisiensi tertinggi didapatkan pada implementasi MPI. Nilai efisiensi semakin menurun seiring dengan bertambahnya jumlah node dan thread yang digunakan, namun masih jauh berbeda dari nilai efisiensi yang didapat dari hasil perhitungan yaitu antara 0.9 - 1. 7. Nilai cost tertinggi didapatkan pada implementasi hybrid 3 thread. Nilai cost yang didapat semakin besar seiring dengan bertambahnya jumlah node dan thread yang digunakan. Seharusnya nilai cost yang diperoleh berdasarkan hasil perhitungan nilainya cenderung tetap pada setiap jumlah node dan jumlah thread. Hal ini disebabkan oleh waktu eksekusi yang tidak sesuai sebagaimana mestinya berdasarkan hasil perhitungan kompleksitas. 19
8. Karena nilai cost semakin besar, maka nilai overhead juga semakin besar seiring bertambahnya jumlah node dan thread yang digunakan.
El-Rewini, Hesham., Mostafa. A. 2005. Advance Computer Architecture and Parallel Processing. New Jersey: John Wiley & Sons, Inc Publication.
9. Jika dibandingkan dengan penelitian yang dilakukan oleh Hoefler et al. (2007), maka pada penelitian ini peningkatan waktu eksekusi tertinggi ada pada penggunaan hybrid 2 thread. Nilai peningkatan tertinggi adalah sebesar 34% pada penggunaan 2 node dan terendah sebesar 9% pada penggunaan 8 node.
Foster, Ian. 1995. Designing and Building Parallel Programs : Concepts and Tools for Parallel Software Engineering. AddisonWesley Pub Co.
10. Secara keseluruhan implementasi model hybrid pada metode CG menghasilkan waktu eksekusi yang lebih cepat dibandingkan dengan implementasi MPI murni. Namun bisa dikatakan baik jika jumlah thread yang digunakan pada setiap node sama dengan banyaknya jumlah core processor yang tersedia pada tiap node. Saran Berikut ini adalah beberapa saran untuk penelitian lebih lanjut: 1. Percobaan pada penelitian ini dilakukan pada jaringan dengan kecepatan 100 Mbps, pada penelitian selanjutnya diharapkan dapat menggunakan jaringan dengan kecepatan yang lebih tinggi lagi, seperti gigabit ethernet, atau fiber optic.
Grama A, A.L Gupta, G. Karypis, V. Kumar. 2003. Introduction to Parallel Computing, Second Edition. England: Addison-Wesley Publishing Company. Hoefler, Torsten et al. 2007. Optimizing a Conjugate Gradient Solver with NonBlocking Collective Operations. Bloomington: Indiana University. Schewchuk, J.R.. 1994. An Introduction to the Conjugate Gradient Method Without the Agonizing Pain. Pittsburgh: School of Computer Science Carnegie Mellon University. Smith, L.A. 2000. Mixed Mode MPI / OpenMP Programming. Edinburgh: Edinburgh Parallel Computing Center.
2. Pada penelitian berikutnya diharapkan algoritme CG tidak dibatasi pada jumlah iterasi, tetapi oleh akurasi solusi SPL yang ingin diperoleh. 3. Penelitian berikutnya bisa menambahkan Preconditioned pada metode CG untuk mempercepat diperolehnya solusi SPL, sehingga iterasi CG yang diperlukan berkurang. DAFTAR PUSTAKA Barney, Blaise. 2009. Introduction to Paralel Computing, Lawrence Livermore National Laboratory. Chapman, Barbara, G. Jost, R.V.D Pas. 2003. Source Book of Parallel Computing. Massachusetts: The MIT Press. Dongara, Jack et al. 2003. Source Book of Parallel Computing. San Francisco: Morgan Kaufmann Publishers.
20
LAMPIRAN
Lampiran 1 Grafik waktu eksekusi implementasi MPI dan hybrid pada untuk setiap kombinasi
Lampiran 2 Grafik speedup implementasi MPI dan hybrid pada untuk setiap kombinasi
Lampiran 3 Grafik efisiensi implementasi MPI dan hybrid pada untuk setiap kombinasi
Lampiran 4 Grafik cost implementasi MPI dan hybrid pada untuk setiap kombinasi
Lampiran 5 Grafik overhead implementasi MPI dan hybrid pada untuk setiap kombinasi
