IMPLEMENTASI METODE ITERATIF PARALEL IMPLISIT MULTISTEP RUNGE-KUTTA PADA SISTEM PARALEL MPI-LINUX Alhadi Bustamam* Heru Suhartanto** , T. Basaruddin **
ABSTRAK IMPLEMENTASI METODE ITERATIF PARALEL IMPLISIT MULTISTEP RUNGEKUTTA PADA SISTEM PARALEL MPI-LINUX. Dunia ilmu pengetahuan dan teknologi membutuhkan perangkat lunak solver untuk menghitung solusi dari suatu pemodelan matematis atas fenomena fisik yang terjadi di alam. Kebutuhan tersebut sangat tergantung pada kinerja solver tersebut untuk dapat bekerja secara tepat, akurat dan murah dalam biaya komputasi dan setup sistemnya. Ketiga hal ini sulit untuk dipenuhi sekaligus karena semua hal tersebut sangat erat hubungannya dengan metode, algoritma dan sistem/lingkungan di mana program tersebut dijalankan. Ketiga hal ini menjadi semakin sulit dipenuhi jika persoalan yang harus diselesaikan menjadi kompleks dan mahal. Pengembangan metode, algoritma dan lingkungan komputasi paralel bertujuan untuk membuka peluang cara penyelesaian terhadap persoalan yang relatif sulit, kompleks dan mahal; meningkatkan kemampuan penyelesaian persoalan tersebut secara numerik menjadi lebih cepat daripada di lingkungan komputasi sekuensial, atau menyelesaikan persoalan yang ditinjau dari sisi ukuran dan batasan waktunya (dan/atau akurasinya) tidak bisa diselesaikan mengunakan lingkungan komputasi sekuensial. Pada makalah ini akan dibahas implementasi dari metode iteratif paralel implisit multistep Runge-Kutta (iPIMRK) tipe Radau secara SPMD pada lingkungan komputasi paralel MPI-LINUX di Laboratorium HPCCSUI Fakultas Ilmu Komputer UI Depok untuk menyelesaikan sistem persamaan diferensial biasa berupa persoalan-persoalan yang stiff . Kata kunci: SPMD, sistem persamaan diferensial biasa, persoalan stiff, metode iteratif paralel implisit multistep Runge-Kutta, sistem paralel MPI-LINUX.
ABSTRACT IMPLEMENTATION OF RUNGE-KUTTA MULTISTEPS IMPLICIT PARALLEL ITERATIVE METHOD ON MPI-LINUX PARALLEL SYSTEM. Scientific code users usually demand fast, accurate and cheap solver. However, this is difficult to fulfill as the requirement is closely related to the methods, algorithm and the environment in which the codes run. Such demands will be more difficult when the problem to be solved become more complex and expensive. With the introduction of parallel computing environments with increasing power, the works on solving of various expensive and difficult phenomena are becoming more widely open and new challenges are appearing. By the invention of such powerful environments it is hoped to solve the numerical problem faster than in the sequential computing environment, to solve insolvable problem with size and time constraints and/or accuracy constraints which were not able be solved in the sequential environment. In this paper, we will discuss the implementation of parallel iterated metode base on variabel stepsize implicit multistep Runge-Kutta of Radau type by using SPMD approach on MPI-Linux parallel system of HPCCSUI Depok Laboratory for stiff problems.
*
Jurusan Matematika FMIPA-UI Fakultas Ilmu Komputer UI
**
PENDAHULUAN Perkembangan teknologi komputasi paralel awalnya dikembangkan dari sisi perangkat keras yaitu berupa mesin superkomputer yang terdiri atas beberapa prosesor yang bekerja secara simultan dan menggunakan memori bersama dan memori lokal dengan ukuran yang sangat besar yang membutuhkan rancangan dan teknologi pengontrolan yang sangat rumit serta biaya yang sangat tinggi, akibatnya jumlah mesin superkomputer yang ada sangat terbatas, dan penelitian ke arah algoritma paralel menjadi mahal dan jarang dilakukan. Awal tahun 90-an muncul terobosan baru untuk mengembangkan teknologi komputasi paralel dari sisi perangkat lunak yang memungkinkan komputasi paralel secara virtual pada jaringan PC-workstation (clustering), berupa teknologi pertukaran pesan antara mesin seperti: P4, PVM (parallel virtual machine), LINDA dan MPI (message passing interface). Selanjutnya pertengahan tahun 90-an muncul suatu konsorsium yang mencoba membuat standarisasi untuk teknologi perangkat lunak pertukaran pesan yaitu MPI, lihat yang kemudian telah berhasil membuat standarisasi MPI-1 menggunakan bahasa pemrograman standar bahasa-C dan Fortran-77, kemudian dilanjutkan tahun 1995 dengan standarisasi MPI-2 yang meliputi bahasa pemrograman standar C, C++, Fortran-77 dan Fortran-90, serta MATLAB pada tahun 2001, lihat MPI[6], Fernandez[3]. Dalam perkembangannya, MPI telah diimplementasikan oleh beberapa pihak pengembang (vendor) dan institusi tertentu dalam teknologi komputasi paralel sehingga muncul beberapa versi MPI seperti: LAM-MPI, MPICH, Beowulf dll., yang dapat dijalankan pada berbagai mesin berbasis Unix atau Linux serta mesin superkomputer; terakhir saat ini sudah ada versi MPI untuk PC-clustering berbasis jaringan Windows/NT serta pembuatan toolbox MPI untuk pemrograman di MATLAB. Hampir semua versi dari perangkat lunak MPI tersebut dan juga bahasa pemrograman C dan Fortran-77 tersebut dapat di-download secara gratis dari internet, sedangkan bahasa pemrograman C++ dan Fortran-90 sampai saat ini masih dalam bentuk produk berlisensi sehingga belum bisa di dapatkan secara gratis.
SISTEM PARALEL MPI-LINUX Arsitektur Jaringan Sistem Paralel MPI-Linux Sistem Parallel MPI-Linux terdiri atas jaringan PC-workstation berbasis Linux yang dirancang menjadi mesin paralel maya menggunakan perangkat lunak MPI. Proses parale lisasi pada program dilakukan melalui eksekusi program secara paralel pada beberapa prosesor yang dilakukan melalui daemon MPI, diikuti dengan proses komunikasi dan pertukaran pesan antara modul - modul program dari prosesor satu
dengan prosesor lainnya. Untuk melakukan proses sinkronisasi data, digunakan informasi dari empat variabel dasar MPI yaitu: context, tag, source rank, destination rank, yang juga berguna untuk memetakan sinkronisasi data secara abstrak di lapisan (layer) MPI dengan lapisan jaringan Linux, lihat MPI Forum[6], Pacheco[7], Gropp[5]. Sebagai catatan bahwa: untuk proses simulasi paralel, masing-masing prosesor dapat juga disimulasikan sebagai proses-proses yang berbeda pada satu prosesor. Penggunaan teknologi pertukaran pesan, saat ini telah menjadi paradigma baru dalam pengembangan komputer paralel, khususnya pada Scalable Parallel Computers (SPCs) dengan memori terdistribusi dan pada Network of Workstations (NOWs) lihat Skillicorn[8], Geist[4]. Secara umum bentuk topologi NOWs Lab HPCCSUI yang digunakan untuk penelitian ini dapat dilihat pada gambar 1.
Nitrogen
Helium
Hidrogen
Oxygen (Server)
Switch Hub
Ek (in
ste L i n rnal k ne t)
ter
Gambar 1. NOWs dari sistem paralel MPI-Linux Sistem paralel MPI-Linux tediri atas 4 buah PC-workstation (Oxygen, Hidrogen, Helium, Nitrogen) yang salah satunya (Oxygen) berfungsi sebagai server, ditambah satu buah switch hub dengan topologi jaringannya berbentuk star dua arah dengan spesifikasi teknisnya adalah sebagai berikut: prosesor : Intel Pentium III450 Mhz., memori: DIMM Visipro 512 MB, Cache 512 Kbyte, kartu jaringan: 2 buah, sistem operasi: Linux Mandrake 8.0, sistem MPI: LAM-MPI versi 6.5.4, bahasa pemrograman: GNU-Fortran 77. Masing-masing workstation menggunakan dua buah kartu network interface card (NIC) di mana kartu pertama berguna untuk mengatur konfigurasi dari jaringan NOWs dan pengaturan networks file system (NFS), sedangkan kartu kedua digunakan untuk komunikasi data dan pertukaran pesan oleh MPI. Dengan penggunaan dua kartu ini diharapkan proses komunikasi data berjalan dengan baik. Dari konfigurasi sistem komputer yang digunakan, secara umum terlihat bahwa sistem bersifat homogen. Hal ini didasarkan pada karakteristik perangkat lunak
MPI yang lebih cocok berjalan pada sistem yang homogen, dibandingan dengan PVM yang dapat berjalan dengan baik pada sistem yang heterogen, lihat Geist [4], Gropp [5]. Hubungan aplikasi program FORTRAN, Daemon MPI, sistem operasi Linux dan Jaringan antara prosesor dapat dilihat pada Gambar 2.
Program FORTRAN Daemon MPI InitMPI/Pack/Send
Recv
Program FORTRAN context, tag, source rank, dest.
Sistem Operasi Linux Jaringan (TCP/IP) Prosesor#0
Daemon MPI Recv/Unpack/Eval
Send Sistem Operasi Linux
NIC-2 NIC-1
Jaringan (TCP/IP) Prosesor#lain
Gambar 2. Lapisan aplikasi pada sistem paralel MPI-Linux
Perangkat Lunak MPI MPI memiliki kemampuan untuk mengimplementasikan bentuk-bentuk program paralel standar seperti Multiple Instructions Multiple Data (MIMD); atau Multiple Programs Multiple Data (MPMD) dan bentuk Single Instructions Multiple Data (SIMD) atau Single Instructions Multiple Data (SPMD). Beberapa operasi utama yang bisa dilakukan oleh MPI standar (standar MPI-1 dan standar MPI-2) yaitu: Komunikasi langsung antara satu proses dengan proses lainnya (point to point), melakukan operasi-operasi bersama (collective), pengelompokan beberapa proses dalam suatu grup tertentu, pendefinisian lingkungan dan domain komunikasi, pembentukan topologi dari proses-proses tertentu, manajemen dari lingkungan komunikasi dan permintaan data. Dalam penelitian ini digunakan perangkat lunak MPI yang dikembangkan pertama kali oleh Ohio Supercomputer Center, Ohio State University kemudian diteruskan oleh Laboratory for Scientific Computing (LSC), University of Notre Dame yang dipimpin oleh Dr. Andrew Lumsdaine yaitu Local Area Multicomputer (LAM)-MPI (versi 6.5.4) pada NOWs Linux Mandrake (versi 8.0).
Arsitektur LAM-MPI LAM berjalan pada masing-masing komputer sebagai sebuah single-daemon (server) membentuk struktur yang unik sebagai sebuah nano kernel dengan beberapa proses pengendali vitual yang dapat dikontrol. Nano kernel menyediakan fasilitas pertukaran pesan dan berbagai servis tertentu yang dibutuhkan proses lokal. Beberapa dari proses in-daemon membentuk sebuah sub-sistem komunikasi jaringan yang berguna untuk melakukan pengiriman pesan dari dan kepada LAM daemon lain pada mesin yang lain. Sub-sistem komunikasi jaringan ini dilengkapi dengan beberapa fitur tambahan seperti: pemaketan data, buffering dan sinkronisasi. Beberapa proses indaemon yang lain berguna untuk kemampuan remote data misalnya: eksekusi program dan pengaksesan file secara paralel. Yang cukup menarik adalah nano kernel tidak memiliki koneksi langsung ke sub-sistem dan sub-sistem tidak memiliki koneksi langsug ke server, sehingga user dapat mengaturnya sendiri dari dalam/dari luar servis sesuai kebutuhan. Dilihat dari sisi rekayasa perangkat lunak, LAM bersifat transparan terhadap user ataupun administrator sistem. Administrator sistem dapat melakukan pengelompokan ulang (de-cluster) daemon menjadi sebuah daemon yang mengandung hanya nano kernel dan beberapa proses klien tertentu dari user tertentu sehingga sangat mendukung prinsip modularitas program dan memudahkan debugging program secara individu. LAM dapat juga dijala nkan secara berasingan pada scalable multicomputer dan menggabungkan mereka sebagai host jaringan melalui sebuah program yang sama/seragam. Secara umum lapisan-lapisan aplikasi pada LAM-MPI dapat dilihat pada gambar 3.
commands, applications, GUI’s MPI : client/server networks messages local messages, local management
Gambar 3. Lapisan aplikasi pada LAM-MPI Dari sisi debugging, fitur paling penting adalah LAM dapat dikontrol secara manual dan langsung (hand-on control) pada sistem multikomputer. Sedikit sekali yang tidak bisa kita lihat atau kita ubah dari sistem, program dapat diletakkan di mana saja, dapat dieksekusi dari mana saja, dihentikan sementara (stopped), dijalankan kembali(resumed), dihentikan permanen (killed), dan pesan dapat diamati di mana saja
dan kapan saja sepanjang waktu. Karena sinkronisasi antara sebuah proses dan sebuah pesan dapat ditampilkan dengan mudah maka hasil mismacthes akibat bugs pada dapat dengan mudah ditemukan. Beberapa Perintah Dasar LAM pada Sistem Paralel MPI-Linux •
Membuat konfigurasi sistem multikomputer Sebuah sistem multikomputer dinyatakan secara sederhana berupa daftar dari nama mesin komputer yang terlibat, dalam sebuah file hosts (misalnya: file lamhosts, lihat gambar 4). LAM menggunakan file hosts tersebut untuk melakukan verifikasi pengaksesan sistem, mengkonfigurasi sistem, mengaktifkan dan mematikan sistem MPI. oxygen.prj.cs.ui.ac.id helium.prj.cs.ui.ac.id hidrogen.prj.cs.ui.ac.id nitrogen.prj.cs.ui.ac.id
Gambar 4. File konfigurasi sistem multikomputer: lamhosts •
Mengaktifkan dan mematikan sistem paralel LAM-MPI Untuk mengaktifkan sistem paralel LAM-MPI dengan file hosts-nya lamhosts digunakan perintah berikut ini: lamboot –v lamhosts Untuk mematikan sistem paralel LAM-MPI yang sedang aktif tersebut digunakan perintah berikut ini: wipe –v lamhosts {Keterangan: –v digunakan agar MPI menampilkan informasi-informasi tertentu tentang perintah/program yang sedang dijalankan}
•
Mengkompilasi sebuah progam paralel pada sistem LAM-MPI Untuk melakukan kompilasi program FORTRAN digunakan perintah mpif77 untuk FORTAN 77 dan mpif90 untuk FORTRAN 90/95. mpif77 –o
-lmpi mpif90 –o -lmpi
Untuk melakukan kompilasi program aplikasi yang melibatkan banyak file biasanya digunakan perintah make dengan konfigurasi aplikasi dibuat dalam sebuah file terpisah makefile. •
Menjalan sebuah aplikasi paralel pada sistem LAM-MPI Sebuah aplikasi program paralel berbentuk SPMD dapat dijalankan dengan cara sederhana melalui perintah mpirun, sedangkan bentuk MPMD harus melalui konfigurasi yang lebih komplek pada sebuah file terpisah yang disebut dengan skema aplikasi. Sebagai contoh, untuk menjalankan aplikasi SPMD pada beberapa prosesor (#prosesor) (dimulai dari prosesor 0) digunakan perintah berikut ini: mpirun n<0-#prosesor-1> –v Contoh: mpirun n0-2 –v vmrk.out (Artinya: program vmrk.out dijalankan secara paralel SPMD pada prosesor 0, 1, dan 2) Untuk simulasi paralel, program SPMD juga dapat dijalankan pada beberapa proses berbeda (#proses) dalam satu komputer/prosesor dengan cara: mpirun –c <#proses-1> –v Contoh: mpirun –c 3 –v vmrk.out (artinya: program vmrk.out disimulasikan berjalan secara paralel SPMD pada 3 proses di prosesor tempat perintah mpirun dieksekusi)
Implementasi SPMD Metode iPIMRK pada Sistem Paralel MPI-Linux Implementasi program untuk metode iteratif paralel implisit MRK (iPIMRK) pada sistem paralel MPI_Linux merupakan implementasi ulang dari modul-modul FORTRAN 90 (F90) dari Suhartanto[1,2] yang dijalankan di mesin SGI_ORIGIN 2000, menggunakan MPI-FORTRAN 77 (MPIF77) agar bisa dijalankan di sistem paralel MPI-Linux yang ada di Lab HPCCSUI Fakultas Ilmu Komputer UI. Seperti telah dijelaskan pada [1,2], metode iPIMRK untuk persoalan yang kaku didefinisikan secara iteratif terhadap Yn( j ) sebanyak L kali sebagai berikut:
Yn( j ) = ( A ⊗ I m ) y ( n ) + hn ([ B − W ] ⊗ I m ) F (Yn( j −1) ) + hn (W ⊗ I m ) F (Yn( j ) ), y n +1 = (e Ts ⊗ I m ) F (Yn( L ) )
j = 1,..., L
(1)
dalam hal ini, Yn( 0 ) adalah nilai aproksimasi awalan untuk Yn , matrik W adalah matrik pemecah (spliting matrix) terhadap matrik B, yang terdiri atas nilai-nilai eigen nonnegatif sebarang dari matrik B. Pemilihan nilai matrik W ini dilakukan sedemikian hingga agar proses iterasi untuk masing-masing Y n ,i , i = 1,..., s dapat dilakukan secara paralel, misalnya dengan menggunakan W=D (matrik diagonal) disebut metode iteratif paralel implisit diagonal MRK (iPDIMRK) atau menggunakan W=T (matrik triangular) disebut metode iteratif paralel implisit triangular (iPTIMRK). Bentuk matrik W yang digunakan untuk implementasi metode (1) pada pembahasan ini adalah matrik segitiga bawah T yang didapat dari dekomposisi Crout terhadap matrik B. Implementasi Algoritma iteratif paralel implisit MRK (1) dapat disederhanakan dengan memecah persamaan (1) dengan cara mengambil nilai
Z = Yn j − ( A ⊗ I m ) y ( n )
dan
G(Yn( j −1 ) ) = h([ B − W ] ⊗ I m ) F (Yn
( j −1)
) , di mana
( j −1)
perhitungan F (Yn ) dan faktorisasi matrik B menjadi matrik W dapat dilakukan secara paralel pada sejumlah s-stages prosesor (paralel_stages dan paralel_factors) sehingga bentuk
Yn( j ) = ( A ⊗ I m ) y ( n ) + hn ([ B − W ] ⊗ I m ) F (Yn( j −1) ) + hn (W ⊗ I m ) F (Yn( j ) ),
j = 1,..., L
dapat diselesaikan menggunakan skema iterasi modifikasi Newton menjadi
(I sm − W ⊗ I m ) ∆Z = −[ Z ( k −1) − G(Yn( j −1) ) − h(W ⊗ I m ) F ( Z ( k −1) + ( A ⊗ I m ) y n )], k=1,..,#niner disebut iterasi dalam (inner iteration) di mana solusi ∆Z juga bisa dihitung secara paralel (paralel_solves) dan pada setiap akhir iterasi dalam dilakukan update data Z k = Z (k-1) + ∆Z . Setelah iterasi dalam selesai maka nilai Yn dihitung sebagai Yn
( j)
( j)
dapat
= Z ( niner) + ( A ⊗ I m ) y ( n ) , dan nilai y (n +j 1) yang baru didapat
y (n +j )1 = (e Ts ⊗ I m )Yn( j ) disebut iterasi luar (outer iteration). Untuk lebih jelasnya algoritma lengkapnya dapat dilihat pada gambar 5 berikut ini:
Misalkan Z = Yn j − ( A ⊗ I m ) y (n ) Iterasi lengkapnya dapat ditulis sbb : for j = 1,..., L
← OUTER iteration ( j −1) n
compute G (Y
) = h([ B − W ] ⊗ I m ) F (Yn
for k = 1,..., niner
( j −1)
)
← INNER iteration
(I sm − W ⊗ I m ) ∆Z = −[ Z ( k −1) − G (Y n( j −1) ) − h (W ⊗ I m ) F ( Z ( k −1) + ( A ⊗ I m ) y n )] Z k = Z (k-1) + ∆ Z end for Yn
( j)
= Z ( niner) + ( A ⊗ I m ) y ( n )
yn( +j )1 = (e Ts ⊗ I m )Yn( j ) = O (h q + j ) end for Gambar 5. Algoritma Umum Metode iPIMRK Berdasarkan pembahasan pada [1,2], misalkan ada sebanyak s-stages prosesor maka perhitungan F (Yn
( j −1)
) dapat dilakukan secara paralel, dan dari cara pemilihan
matrik W maka perhitungan nilai Yi ( j ) , i = 1,.., s juga dapat berlangsung secara terpisah/paralel dan penyelesaian sistem linier ( ∆Z ) pada iterasi Newton di masingmasing stages juga dapat berlangsung secara paralel sehingga pada metode iPIMRK ini terdapat tiga proses paralel yaitu: proses evaluasi fungsi derivatif F (Yi ( j ) ) , proses faktorisasi dari matrik-matrik iterasi (W ) dan proses penyelesaian sistem linier pada masing-masing tahapan ( ∆Z ) .
Strategi Pengontrolan Proses Paralelisasi Implementasi paralelisasi di dalam sistem paralel MPI-Linux dilakukan dengan menggunakan teknik SPMD di mana program yang sama (misalnya, vmrk.out) akan dijalankan di semua stages prosesor dengan menggunakan perintah berikut ini: mpirun n0-(jumlah stages-1) ./vmrk.out
Satu prosesor (prosesor-0: oxygen) bertugas membagi data, melakukan komputasi lokal dan mengumpulkan hasil komputasi dari prosesor lainnya (prosesor 1,2,3: hidrogen, helium, nitrogen), sedangkan prosesor lainnya bertugas melakukan komputasi lokal sesuai dengan data dan informasi proses yang harus dikerjakan (task_info & comp_info), berdasarkan pesanan dari prosesor-0, lihat gambar 6. Kontrol Utama Task_Info & data global Prosesor #0
Prosesor #1
Proses Parallel Stages
Proses Parallel Factors
. . ..
..
Prosesor #(s-1)
Proses Parallel Solves
Kontrol Sekunder Comp_Info & data lokal Gambar 6. Diagram Kontrol Proses Paralelisasi Metode iPIMRK
•
Strategi Pengontrolan Utama
Pengontrol Utama berada pada modul driver (DR_SVMRK, DR_CUSP, DR_SBRUSS, DR_SDENSE) yang berfungsi untuk mengontrol diaktifkan atau tidak diaktifkannya proses paralel tertentu (Parallel_Stages, Parallel_Factors, Parallel_Solves) berdasarkan dipanggil atau tidak dipanggilnya proses paralel tersebut oleh modul integrator SVMRK. Pengontrolan tersebut dilakukan melalui pengiriman informasi task_info dan data global oleh prosesor#0 kepada masing-masing prosesor lain yang tersedia (prosesor#1,.., prosesor#stages-1), selanjutnya masing-masing prosesor ini akan mengaktifkan proses paralel yang bersesuaian dengan task_info tersebut dan siap untuk menerima data dari prosesor#0 dan melakukan komputasi lokal secara paralel. Informasi task_info juga digunakan untuk menentukan apakah proses iterasi segera dimulai (“SVMRK_Starting”), proses iterasi diteruskan (“SVMRK_Continue”), atau proses iterasi telah selesai (“SVMRK_Finished”).
Pada akhir integrasi untuk menghentikan kegiatan MPI di semua prosesor maka program harus ditutup dengan pemanggilan MPI_FINALIZED. Implementasi Pengontrolan Utama dapat dilihat pada Gambar 7. Pengontrol Utama: Modul DR_SVMRK init MPI If numberOfprocessor >= stages then Parallel_flag In modul=TRUE SVMRK: #Prosesor-0 {if needed} Call MPI_Parallel_Stages if (Parallel_flag) then {if needed} Call MPI_Parallel_Factors 100 Send task info: ‘init’ to others {if needed} Call MPI_Parallel_Solves Init SVMRK & Problems Send initdata to others Send task info: ‘SVMRK_Starting’ to others Call modul SVMRK If other_PROBLEMS then Send task info: ‘SVMRK_Continue’ to others Goto 100 else Send task info: ‘SVMRK_finished’ to others endif endif Finalized MPI #Prosesor-others (1,2,..,s-1) receive taskinfo if (task info=’init’) receive initdata from prosesor#0 if (Parallel_flag.and.numberOfprocessors>=stages) then receive taskinfo if taskinfo = ‘SVMRK_Starting’ or ‘SVMRK_Continue’ then Parallel_flag =.TRUE. do while (Parallel_flag.and.processorRank<stages) Receive compinfo if (COMP_INFO=’SVMRK_Finished’then Parallel_flag =.FALSE. {Keluar, proses paralel} else if (compinfo=’compute_stages’) then call ParallelSTAGES else if (compinfo=’compute_factors’) then call ParallelFACTORS else if (compinfo=’comopute_factors’) then call ParallelSOLVES endif enddo endif endif
Gambar 7. Implementasi Pengontrolan Utama
•
Strategi Pengontrolan Sekunder
Pengontrol Sekunder berada pada masing-masing modul paralel (STAGES, FACTORS, dan SOLVES), berfungsi untuk mengatur pengiriman data lokal oleh prosesor#0 kesemua prosesor lain, pelaksanaan komputasi lokal secara paralel di semua prosesor (termasuk prosesor#0), dan pengumpulan kembali hasil akhir komputasi oleh prosesor#0 untuk dikirimkan kepada modul SVMRK. Setiap kali modul paralel tertentu akan memulai komputasi maka Pengontrol Sekunder terlebih dahulu memberi konfirmasi atau laporan berupa pengiriman informasi Comp_Info kepada Pengontrol Utama. Informasi Comp_info ini oleh Pengontrol Utama berguna untuk menentukan proses paralel mana yang akan diaktifkan oleh prosesor#selain-0. Setiap kali proses paralel diaktifkan di prosesor#selain-0 maka semua prosesor tersebut siap menerima data lokal dari prosesor-0 dan melakukan komputasi lokal secara paralel. Proses pengiriman dan penerimaan data dari prosesor-0 ke prosesor lainya (atau sebaliknya ) dapat dilakukan selama tanda Comp_Info proses paralel untuk modul yang bersangkutan pada masing-masing prosesor masih aktif. Implementasi dari Pengontrolan Sekunder dapat dilihat pada gambar 8. Pengontrol Sekunder: Modul Parallel Stages #Prosesor-0 Send compinfo: ‘compute stages’ {to others} Send data {to others} Compute local stages Recive data {from others} Send result to SVMRK Pengontrol Sekunder: Modul Parallel Factors #Prosesor-0 Send compinfo: ‘compute factors’ {to others} Send data {to others} Compute local fac_imaj, factorize Recive data {from others} Send result to SVMRK Pengontrol Sekunder: Modul Parallel Solves #Prosesor-0 Send compinfo: ‘compute solves’ {to others} Send data {to others} Compute local do_solve Recive data {from others} Send result to SVMRK
#Prosesor-others (1,2,..,s-1) receive compinfo if (compute info =’compute_stages’) then receive data {from prosesor-0} compute local stages send data {to prosesor-0} endif
#Prosesor-others (1,2,..,s-1) receive compute info if (compinfo =’compute factors’) then receive data {from prosesor-0} compute local fact_imaj,factorize send data {to prosesor-0} endif #Prosesor-others (1,2,..,s-1) receive compute info if (compinfo =’compute_solves’) then receive data {from prosesor-0} compute local do_solves send data {to prosesor-0} endif
Gambar 8. Implementasi Pengontrolan Sekunder
Dengan adanya strategi pengontrolan utama dan strategi pengontrolan sekunder diharapkan prinsip keseimbangan beban kerja (load balancing) bisa dipelihara dan keoptimalan hasil kerja komputasi (throughput) dapat diperoleh dengan baik.
HASIL PERCOBAAN Untuk percobaan dari implementasi metode iPIMRK pada sistem paralel MPILinux, digunakan metode iPIMRK dengan r=3 dan s=3, prediktor=P3 dan Atol=1.d09 untuk menyelesaikan problem dense dengan N=20, 30, 40, 50, 100, 150, 200, dan 250, yang didefinisikan sebagai berikut: (lihat Suhartanto [1,2]). i
y2j ∑ j =1
−
y′i = (QY)i + e
,i =1,...,m, Y ∈Rm ,Y(0) = e, x ∈[0,1]
di mana, Q = Q1T DQ1 , dan Q1 merupakan kolom - kolom ortonormal dari sebuah matrik random M. Problem dense tersebut bisa dikontrol menjadi persoalan nonstiff atau stiff dengan cara menetapkan nilai α = 1 / m 2 (nonstiff) atau membatasi nilai eigen dari D dalam daerah jangkauan antara 1.0 sampai dengan 10.0 (stiff). Berikut ini ditampilkan hasil percobaan untuk persoalan stiff untuk variasi N=20,30,40,50,100,150,200,250 menggunakan metode iPIMRK33 (r=3,s=3) prediktor P3 dan ATOL=1.d-9, sebagai berikut ini: Tabel 1. Hasil percobaan untuk persoalan dense yang stiff, dengan ATOL=1.d-9, Metode M33 dan Prediktor P3 fixed steps
variabel steps
N
seq-t
par -t
Prec digit
Speed - Effisi up ensi
seq-t
par -t
precdigit
Speed -up
Effisi ensi
20
0.05999994
0.17000008
4.78
0.35
12
0.090000153
0.13999987
7.28
0.64
21
30
0.12999988
0.14000011
5.07
40
0.26000023
0.32000017
4.97
0.93
31
0.160000086
0.13999987
7.01
1.14
38
0.81
27
0.330000162
0.37000036
7.89
0.89
30
50
0.44999981
0.37999988
4.89
1.18
39
0.53000021
0.42000008
7.81
1.26
42
100
2.42000103
1.64999843
5.02
1.47
49
3.24999905
2.17999983
8.04
1.49
50
150
7.06999969
4.58999777
5.19
1.54
51
7.93999672
5.31000042
7.75
1.50
50
200
15.4199982
9.37999535
4.84
1.64
55
20.0400047
11.5100079
8.25
1.74
58
250
54.1800003
28.9799995
5.47
1.87
62
118.040115
60.649971
7.72
1.95
65
Time Vs N (Atol=1.D-09) seqfixedCoeff s
Fixed coeffs
1.00 0.00
varCoeffs
parvarCoeffs
N
N
Efficiency vs N 70.00 60.00 50.00 40.00 30.00 20.00 10.00 0.00
Precision Digit Vs N (Atol=1.D-09) 10 fixedCoeffs
pd
5
fixedCoef fs
varCoeffs
20
30
40
50 100 150 200 250
40 10 0 20 0
0 20
Efficiency
2.00
N
Gambar 9.
40 10 0 20 0
seqvarCoeffs
3.00
20
40 10 0 20 0
parfixedCoeff s
Speedup vs N (atol=1.D-9) Speedup
150 100 50 0 20
Time (seconds)
Berdasarkan hasil percobaan pada Tabel 1 kita peroleh grafik untuk evaluasi ukuran-ukuran kinerja sebagai berikut:
varCoeffs
N
Hasil percobaan iPIMRK33 Prediktor P3 untuk problem dense dengan variasi N dan ATOL=1.d-09
Dan berdasarkan Gambar 9 dapat dilakukan evaluasi kinerja sebagai berikut ini: A. Hasil Waktu Eksekusi dari Metode iPIMRK33 Secara umum metode iPIMRK33 dengan variable coefficients (VC) membutuhkan waktu komputasi yang lebih lama daripada metode iPIMRK dengan fixed coefficients (FC), hal ini bisa dibenarkan karena pada metode VC perlu proses perhitungan ulang dari koefisien-koefisien pada setiap langkah integrasi. Pada kedua metode VC dan FC terlihat bahwa untuk nilai N yang kecil (20,30,40) waktu komputasi serial lebih cepat dari waktu komputasi paralel, tetapi untuk N yang makin
besar (N>= 50) waktu komputasi paralel mulai mendahului waktu komputasi sekuensial (mulai terjadi Speedup) dan mulai N> 200 lonjakan perbedaan waktu komputasi serial dan paralel mulai terlihat sangat tajam, lonjakan paling tajam khususnya pada metode dengan VC. B. Hasil Speed-up dari Metode iPIMRK33 Berdasarkan perilaku waktu eksekusi, maka secara umum Speedup mulai diperoleh untuk N>=50 dan terus meningkat mendekati linier untuk N yang lebih besar, baik untuk metode VC ataupun FC, di mana Speedup dari metode VC selalu lebih tinggi dari Speedup yang diperoleh oleh metode FC. C. Hasil Efisiensi dari Metode iPIMRK33 Kenaikan efisiensi yang medekati linier mulai dari N>40 pada kedua metode VC dan FC, tetapi secara umum metode VC memiliki efisiensi yang lebih baik dari metode FC. D. Hasil Presisi Digit dari Metode iPIMRK33 Presisi digit dari metode VC selalu lebih baik dari pada metode FC dengan perbedaan yang sangat signifikan (hampir 1,75 kali lipat), dari grafik juga terlihat bahwa besarnya nilai presisi digit tidak tergantung pada nilai N.
Times(detik)
Time Vs Precdigit N=250 metode M33, predictor P3
seq-t-fc
150.00
par-t-fc
100.00 50.00 0.00 0.00
seq-t-vc 2.00
4.00
6.00
8.00
10.00
par-t-vc
Precision Digit
Gambar 10. Hasil waktu eksekusi vs. presisi digit percobaan iPIMRK33 variable coefficients untuk problem dense dengan N=250. Selanjutnya berdasarkan Gambar 10, sebagai evaluasi tambahan dengan cara membandingkan antara presisi digit yang diperoleh dengan waktu eksekusi yang
dibutuhkan (khususnya pada N=250), lihat Gambar 3.14, menunjukkan kinerja yang lebih baik metode VC dari sisi presisi digit, tetapi memiliki kelemahan dari sisi waktu eksekusinya yang lebih lama dari metode FC, namun demikian walaupun dari sisi waktu eksekusi metode FC lebih unggul tetapi dengan melihat perbedaan presisi digit yang sangat signifikan maka dapat dikatakan metode VC tetap lebih baik dari metode FC.
KESIMPULAN Implementasi metode iteratif paralel implisit MRK, dapat dilakukan pada sistem paralel MPI-Linux pada NOWs berbasis Linux Mandrake 8.0, teknologi pertukaran pesan LAM-MPI 6.5.4 dan bahasa pemrograman FORTRAN77 dengan menggunakan implementasi SPMD yang dijalankan pada sejumlah stages prosesor. Dalam implementasi tersebut terdapat tiga proses utama yang dilakukan secara paralel yaitu: Parallel Stages, Parallel Factors dan Parallel Solves, yang kesemua proses paralel tersebut dijalankan pada sejumlah stages prosesor menggunakan dua lapis strategi komunikasi dan pengontrolan data yaitu: Pengontrolan Utama (untuk mengontrol komunikasi data global antar prosesor) dan Pengontrolan Sekunder (untuk mengontrol komunikasi dan komputasi data lokal masing-masing proses paralel pada semua prosesor). Kedua strategi pengontrolan utama dan pengontrolan sekunder ini diharapkan akan menjaga keseimbangan beban kerja (load balancing) dan keoptimalan hasil kerja komputasi (throughput). Hasil percobaan sementara memperlihatkan bahwa peningkatan kecepatan metode paralel dibandingkan metode sekuensial baru terjadi untuk dimensi persoalan yang cukup besar (misalnya, untuk persoalan dense pada waktu N>=50), dan kenaikan yang sangat significant terjadi pada waktu N>=200. Metode iPIMRK33 dengan variable coefficients (VC) memberikan hasil yang lebih baik dari metode iPIMRK33 fixed coefficients(FC) ditinjau dari sisi presisi digit yang diperoleh, speedup dan efisiensi yang dihasilkan, tetapi dari sisi waktu eksekusinya FC lebih baik dari VC. Namun demikian karena perbedaan presisi digit yang dihasilkan sangat signifikan (hampir 1 ¾ kali lipat), maka secara umum kinerja metode VC lebih baik dari metode FC.
DAFTAR PUSTAKA 1. BURRAGE, K., and SUHARTANTO, H., Parallel Iterated Method Based on Variable-step Multistep Runge-Kutta of Radau Type for Stiff Problems, Submitted to Adv. Comput. Math. (1997) 2. BURRAGE, K., and SUHARTANTO, H., Parallel iterated method based on multistep Runge-Kutta of Radau type for stiff problems, Adv. Comput. Math., 7, (1997) 59-77 3. FERNANDEZ, JAVIER B., Massage Passing under MATLAB, Dept, of Computer Technology and Architecture, Univ. of Granada, Spain, (2001) 4. GEIST, A., BEGUELIN, A., DONGARRA, J., JIANG, W., MANCHEK, R., SENDERAM, V., PVM:Parallel Virtual Machine; A Users’ guide and tutorial for Networked Parallel Computing, MIT Press, Cambrigde, England, (1994) 5. GROPP, W., LUSK, E. and SKJELLUM, Using MPI: Portable Programming with Massage Passing Interface, MIT Press, (1995) 6. Massage Passing Interface Forum, MPI: A massage passing interface standar, Int. Journal of Supercomputer, special issue on MPI 8 (3/4), (1994) 159-416 7. PACHECO, P. S., Parallel Programming with MPI, Morgan Kaufmann Publ. Co. (1997) 8. SKILLICORN, D. and TALIA, D., Models and Languages for Parallel Computation, ACM Computing Survey, 30 (2), (1998) 123-169
HOME
KOMPUTASI DALAM SAINS DAN TEKNOLOGI NUKLIR XIII
