AKSELERASI GLOBAL PAIRWISE ALIGNMENT DENGAN SKEMA PARTISI BLOCKED COLUMN-WISE PADA SISTEM MEMORI TERDISTRIBUSI MAULANA RIZAL IBRAHIM

AKSELERASI GLOBAL PAIRWISE ALIGNMENT DENGAN SKEMA PARTISI BLOCKED COLUMN-WISE PADA SISTEM MEMORI TERDISTRIBUSI

MAULANA RIZAL IBRAHIM

DEPARTEMEN ILMU KOMPUTER FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM INSTITUT PERTANIAN BOGOR BOGOR 2015

PERNYATAAN MENGENAI SKRIPSI DAN SUMBER INFORMASI SERTA PELIMPAHAN HAK CIPTA Dengan ini saya menyatakan bahwa skripsi berjudul Akselerasi Global Pairwise Alignment dengan Skema Partisi Blocked Column-wise pada Sistem Memori Terdistribusi adalah benar karya saya dengan arahan dari komisi pembimbing dan belum diajukan dalam bentuk apa pun kepada perguruan tinggi mana pun. Sumber informasi yang berasal atau dikutip dari karya yang diterbitkan maupun tidak diterbitkan dari penulis lain telah disebutkan dalam teks dan dicantumkan dalam Daftar Pustaka di bagian akhir skripsi ini. Dengan ini saya melimpahkan hak cipta dari karya tulis saya kepada Institut Pertanian Bogor. Bogor, Agustus 2015 Maulana Rizal Ibrahim NIM G64110101

ABSTRAK MAULANA RIZAL IBRAHIM. Akselerasi Global Pairwise Alignment dengan Skema Partisi Blocked Column-wise pada Sistem Memori Terdistribusi. Dibimbing oleh WISNU ANANTA KUSUMA. Algoritme global pairwise alignment (GPA) yang digunakan untuk menyejajarkan sepasang sekuens DNA perlu diparalelisasi untuk mempersingkat waktu eksekusi. Skema partisi berpengaruh terhadap kinerja algoritme GPA paralel mengingat algoritme ini mengadopsi metode pemrograman dinamis. Penelitian ini mempercepat algoritme GPA menggunakan skema partisi blocked column-wise pada sistem memori terdistribusi. Pararelisasi algoritme GPA dilakukan dengan model pemrograman message-passing menggunakan standar message passing interface (MPI). Parameter panjang sekuens yang digunakan bervariasi dari 1000 bp sampai paling panjang 30 000 bp. Hasil yang diperoleh menunjukkan speedup menggunakan 2, 3, dan 4 buah PC berturut-turut adalah 1.79, 2.58, dan 3.37 untuk panjang sekuens 30 000 bp. Sedangkan efisiensi menggunakan jumlah PC dan panjang sekuens yang sama berturut-turut mencapai 89.32%, 85.97%, dan 84.19%. Algoritme GPA paralel yang dikembangkan menunjukkan skalabilitas. Kata kunci: message-passing, memori terdistribusi, pairwise alignment, skema partisi

ABSTRACT MAULANA RIZAL IBRAHIM. Acceleration of Global Pairwise Alignment using Blocked Column-wise Partition Scheme in Distributed Memory System. Supervised by WISNU ANANTA KUSUMA. The algorithm of global pairwise alignment (GPA) which is used to align a pair of DNA sequences need to be processed in parallel to shorten the execution time. Partitioning scheme affects the performance of GPA in parallel as the algorithm adopts the dynamic programming method. This study accelerates GPA algorithm using blocked column-wise partition scheme on distributed memory systems. The parallelism of GPA algorithm performed by message-passing programming model using the message passing interface (MPI) standard. Sequence’s length parameter varies from 1000 bp to a maximum length of 30 000 bp. The results showed speedup using 2, 3 and 4 PCs respectively, are 1.79, 2.58 and 3.37 with a sequence’s length of 30 000 bp. While the efficiency with the same amount of PCs and sequence’s length respectively, reached 89.32%, 85.97% and 84.19%. The algorithm of GPA in parallel shows scalability. Keywords: distributed memory, message-passing, pairwise alignment, partition scheme

AKSELERASI GLOBAL PAIRWISE ALIGNMENT DENGAN SKEMA PARTISI BLOCKED COLUMN-WISE PADA SISTEM MEMORI TERDISTRIBUSI

MAULANA RIZAL IBRAHIM

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 2015

Penguji: 1 Ahmad Ridha, SKom MS 2 Auriza Rahmad Akbar, SKomp MKom

Judul Skripsi : Akselerasi Global Pairwise Alignment dengan Skema Partisi Blocked Column-wise pada Sistem Memori Terdistribusi Nama : Maulana Rizal Ibrahim NIM : G64110101

Disetujui oleh

DrEng Wisnu Ananta Kusuma, ST MT Pembimbing

Diketahui oleh

Dr Ir Agus Buono, MSi MKom Ketua Departemen

Tanggal Lulus:

PRAKATA Puji dan syukur penulis panjatkan kepada Allah subhanahu wa ta’ala atas segala karunia-Nya sehingga karya ilmiah ini berhasil diselesaikan. Penelitian yang dilaksanakan sejak bulan Maret 2015 ini berjudul Akselerasi Global Pairwise Alignment dengan Skema Partisi Blocked Column-wise pada Sistem Memori Terdistribusi. Terima kasih penulis ucapkan kepada pihak-pihak yang telah berperan dalam penyelesaian tugas akhir ini, antara lain: 1 Ibu dan ayah penulis, Lina Herlina dan Wihatmoko Waskitoaji, yang selalu memberikan kasih sayang, dukungan, dan doa kepada penulis. Terima kasih juga untuk keluarga penulis atas semua dukungan yang diberikan. 2 Bapak Wisnu Ananta Kusuma selaku dosen pembimbing yang telah memberi arahan dan saran dalam penyelesaian tugas akhir ini. 3 Bapak Ahmad Ridha dan Bapak Auriza Rahmad Akbar selaku dosen penguji yang telah memberi masukan untuk penyelesaian tugas akhir ini. 4 Bapak Imam Cartealy dari BPPT yang telah memberi sebagian ilmunya terkait bioinformatika dan Bapak Djatmiko yang telah mempersilakan penulis menggunakan fasilitas cluster Laboratorium Analisis Data untuk penyelesaian tugas akhir ini. 5 Seluruh dosen Departemen Ilmu Komputer atas ilmu yang telah diberikan kepada penulis. 6 Pak Rizki, Pak Irvan, Pak Ridwan, dan pegawai Departemen Ilmu Komputer lainnya yang telah memberi bantuan kepada penulis, terutama bantuan mengenai urusan administrasi di departemen. 7 Teman-teman S1 Ilmu Komputer, IKMT IPB, Brigade G14, dan BEM FMIPA IPB yang telah mendukung penulis dan memberi banyak pelajaran hidup bagi penulis. Terima kasih kepada Udin, Dwi, Laras, Niken, Whina, Anas, Aries, Rudi, Ihda, Nida, Furqon, Dadi, Dedi, Ahas, Iin, Atikah, Rani, Faza, dan temanteman lain yang tidak dapat penulis sebutkan satu persatu. Semoga karya ilmiah ini bermanfaat.

Bogor, Agustus 2015 Maulana Rizal Ibrahim

DAFTAR ISI DAFTAR GAMBAR

vi

DAFTAR LAMPIRAN

vi

PENDAHULUAN

1

Latar Belakang

1

Perumusan Masalah

1

Tujuan Penelitian

2

Manfaat Penelitian

2

Ruang Lingkup Penelitian

2

METODE

2

Tahapan Penelitian

2

Implementasi Global Pairwise Alignment Sekuensial

3

Implementasi GPA Paralel dengan Skema Partisi Blocked Column-wise

3

Analisis Hasil

5

Perbandingan dengan Penelitian Sebelumnya

5

Bahan

5

Alat

5

HASIL DAN PEMBAHASAN Implementasi Global Pairwise Alignment Sekuensial

5 5

Implementasi Global Pairwise Alignment Paralel dengan Skema Partisi Blocked Column-wise

6

Verifikasi Kebenaran Algoritme GPA Paralel

9

Memori Penyimpanan Matriks

10

Analisis Hasil

11

Perbandingan dengan Penelitian Sebelumnya

12

KESIMPULAN DAN SARAN

13

Kesimpulan

13

Saran

14

DAFTAR PUSTAKA

14

DAFTAR GAMBAR 1 2 3 4 5 6 7 8 9 10 11 12 13

Tahapan penelitian Bagan alir algoritme GPA Ilustrasi skema partisi blocked column-wise Hasil penjajaran ClustalW2 dan algoritme GPA Inisialisasi matriks Fm,n GPA paralel Inisialisasi matriks Fm,n GPA sekuensial Proses pengiriman nilai -5 dari P0 ke P1 Pengisian sel matriks Fm,n Perbandingan hasil algoritme GPA sekuensial (kiri) dan paralel dua prosesor (kanan) Grafik waktu eksekusi program penjajaran sekuens.  1 PC,  2 PC,  3 PC,  4 PC. Grafik speedup komputasi paralel algoritme GPA.  2 PC,  3 PC,  4 PC. Grafik efisiensi komputasi paralel algoritme GPA.  2 PC,  3 PC,  4 PC. Grafik efisiensi GPA pada sistem memori bersama dan sistem memori terdistribusi.  distributed memory,  shared memory.

2 3 4 6 8 8 9 9 10 11 11 12 13

DAFTAR LAMPIRAN 1 Hasil run program GPA sekuensial dan paralel dengan 2 sampai 4 PC untuk panjang sekuens 1.000 bp sampai 30.000 bp 15 2 Hasil run program GPA paralel pada sistem memori terdistribusi dan sistem memori bersama dengan panjang sekuens 1.000 bp sampai 16.000 bp 19

PENDAHULUAN Latar Belakang Algoritme global pairwise alignment (GPA) merupakan salah satu algoritme fundamental dalam disiplin ilmu bionformatika. Algoritme GPA digunakan untuk menyejajarkan sepasang sekuens DNA, RNA, maupun protein. Hasil penjajaran digunakan untuk menentukan kemiripan antara kedua sekuens. Nilai kemiripan yang tinggi antarkedua sekuens berimplikasi secara signifikan kepada kemiripan fungsional atau struktural antar-organisme (Mount 2001). Namun demikian, ukuran sekuens dari data biologis sangat besar sehingga menyejajarkan sekuens hanya oleh satu prosesor akan memakan waktu sangat lama. Algoritme ini juga memiliki kompleksitas O(mn), dengan m adalah panjang sekuens pertama dan n adalah panjang sekuens kedua (Shebab et al. 2012). Oleh karena kompleksitas tersebut, dibutuhkan metode yang dapat memangkas waktu komputasi namun tetap memiliki hasil akurat. Komputasi paralel menjadi solusi metode untuk mempercepat waktu komputasi algoritme GPA. Komputasi paralel adalah sebuah metode untuk melakukan langkah-langkah secara bersamaan dari program komputer menggunakan dua atau lebih prosesor. Paralelisasi algoritme GPA sudah dilakukan, seperti pada FDASA oleh Shebab et al. (2012) dan pada CudaSW oleh Liu et al. (2013) yang menggunakan skema partisi data tertentu. Skema partisi data menjadi sangat berpengaruh pada kinerja GPA paralel, karena algoritme GPA mengadopsi metode pemrograman dinamis (Hsien-Yu et al. 2004). Penelitian sebelumnya telah membandingkan skema partisi data algoritme GPA pada sistem memori bersama. Skema partisi yang dibandingkan antara lain skema row-wise, blocked column-wise, anti-diagonal, dan blocked column-wise dengan perbaikan. Hasilnya adalah skema partisi blocked column-wise dengan perbaikan menjadi skema partisi dengan nilai efisiensi terbaik (Akbar et al. 2015). Sistem memori bersama memungkinkan prosesor untuk saling berbagi-pakai memori yang sama. Namun, program paralel pada sistem memori ini hanya bisa dijalankan oleh batas jumlah core yang ada pada sistem. Sistem memori terdistribusi dapat menjadi salah satu solusi alternatif untuk permasalahan tersebut. Penelitian ini akan mengakselerasi algoritme GPA dengan skema partisi data blocked column-wise pada sistem memori terdistribusi. Berbeda dengan sistem memori bersama, sistem memori terdistribusi membagi interkoneksi untuk beberapa prosesor yang terhubung, masing-masing prosesor memiliki memori privat. Arsitektur memori seperti ini memungkinkan penambahan jumlah prosesor untuk menjalankan program paralel sewaktu-waktu. Paralelisasi algoritme GPA pada sistem memori terdistribusi menggunakan standar message passing interface (MPI). Perumusan Masalah Berdasarkan latar belakang di atas dapat dirumuskan masalah penelitian ini adalah bagaimana mengakselerasi algoritme GPA dengan skema partisi data blocked column-wise menggunakan standar komputasi paralel MPI.

2 Tujuan Penelitian Tujuan dari penelitian ini adalah mengembangkan algoritme GPA paralel dengan skema partisi data blocked column-wise pada sistem memori terdistribusi dan menganalisis hasil kinerjanya. Penelitian ini juga membandingkan kinerja algoritme GPA paralel pada sistem memori terdistribusi dengan sistem memori bersama yang sudah dilakukan pada penelitian sebelumnya. Manfaat Penelitian Penelitian ini diharapkan dapat menghasilkan algoritme GPA paralel finegrained paralellism dengan kinerja tinggi sehigga dapat mengakselerasi kinerja algoritme GPA dan memangkas waktu komputasi penjajaran sekuens. Ruang Lingkup Penelitian 1

2 3 4 5

Ruang lingkup pada penelitian ini ialah: Paralelisasi dengan model pemrograman message-passing yang mengasumsikan setiap komputer sebagai prosesor dengan memori lokalnya masing-masing (Quinn 2003). Pengujian kinerja pada proses pengisian matriks kemiripan. Menggunakan standar MPI dan bahasa pemrograman C. Pengujian kinerja menggunakan 4 unit komputer dengan spesifikasi hardware yang sama. Menggunakan data sekuens maksimal panjang 30 000 base pair (bp) yang dibangkitkan secara acak.

METODE Tahapan Penelitian Tahapan-tahapan yang dilakukan pada penelitian ini dapat dilihat pada Gambar 1.

Gambar 1 Tahapan penelitian

3 Implementasi Global Pairwise Alignment Sekuensial Impelementasi algoritme GPA menggunakan modifikasi algoritme penjajaran Needleman-Wunsch. Langkah pertama dalam algoritme ini adalah membuat matriks yang disebut matriks kemiripan. Satu sekuens (dengan panjang m) ditulis secara vertikal pada bagian kiri dari matriks dan setiap residu pada sekuens ini melabeli satu baris. Sekuens lainnya (dengan panjang n) ditulis pada bagian atas matriks dan setiap residu pada sekuens ini melabeli satu kolom (Gautham 2006) sehingga terbentuk matriks kemiripan Fm,n dengan m × n elemen. Skor penjajaran diatur sebagai berikut, jika residu pada kedua sekuens sama maka diberikan skor satu, jika berbeda maka skor dikurangi satu. Gap penalty bergantung pada besarnya masing-masing jarak yang diinisialisasi sebagai skor pada baris dan kolom ke-0 secara menurun, yaitu nilai gap penalty dikalikan jaraknya dari titik awal F(0,0).

Gambar 2 Bagan alir algoritme GPA Gambar 2 menunjukkan prosedur aktivitas dari algoritme GPA sekuensial. Untuk mempercepat waktu komputasi algoritme GPA diparalelisasi pada bagian kode untuk pengisian matriks kemiripan. Hanya bagian inisialisasi yang tidak diparalelisasi. Kebenaran algoritme GPA diverifikasi dengan menyejajarkan 2 sekuens DNA SYG_YEAST dan SYG_SCHPO. Kemudian kedua sekuens juga disejajarkan dengan program ClustalW 2.1 pada pengaturan standar dan hasilnya dibandingkan dengan algoritme GPA sekuensial. Implementasi GPA Paralel dengan Skema Partisi Blocked Column-wise GPA paralel diimplementasi dengan standar MPI pada sistem memori terdistribusi. Implementasi MPI menggunakan pustaka MPICH. Implementasi GPA paralel didesain mengikuti foster’s methodology yang memiliki empat tahap, yaitu: partitioning, communication, agglomeration, dan mapping (Quinn 2003). 1 Partitioning Tahapan ini membagi komputasi dan data menjadi potongan-potongan kecil (pieces) atau tugas-tugas (tasks). Pada tahapan ini, sekuens kedua dengan panjang

4 n, yang setiap residunya melabeli satu kolom, dibagi oleh banyaknya jumlah prosesor yang digunakan. Hasil pembagian akan menurunkan jumlah kolom yang harus dikomputasi oleh satu prosesor. 2 Communication Tahapan ini menentukan pola komunikasi antar-tugas yang sudah dibagi menjadi bagian-bagian yang lebih kecil. Komunikasi pada pengembangan algoritme GPA paralel menggunakan MPI_Send dan MPI_Recv yang merupakan blocking communication. Hal ini membuat setiap pola pengiriman dan penerimaan data akan diblok sampai proses selesai atau sampai buffer data yang sudah diinisialisasi selesai diterima. Komunikasi melibatkan prosesor i dengan prosesor sebelumnya (i-1) dan prosesor setelahnya (i+1). Ketika prosesor selesai melakukan komputasi sampai bagian kolom terakhir, prosesor akan mengirimkan nilai tersebut ke prosesor setelahnya. Nilai tersebut diterima sebagai nilai bagian kolom pertama oleh prosesor setelahnya. 3 Agglomeration Tahap ini menggabungkan tugas-tugas untuk mengatur pemberian beban kerja kepada prosesor. Pada skema partisi data blocked column-wise setiap prosesor mendapatkan bagian data untuk dikomputasi sebanyak n/p dikali m, dengan m dan n adalah panjang sekuens pertama dan kedua, sedangkan p adalah banyaknya prosesor yang digunakan. 4 Mapping Tahap ini menentukan pembagian tugas yang sudah digabungkan pada tahap agglomeration untuk diproses oleh prosesornya. Mapping pada pengembangan algoritme GPA paralel dengan skema partisi blocked column-wise menentukan prosesor ke-i mendapat bagian blok kolom ⌊(i.n/t)+1⌋ hingga kolom ⌊(i+1)n/t⌋. Dengan n adalah panjang kolom atau panjang sekuens kedua dan t adalah jumlah prosesor yang digunakan. Gambar 3 menunjukkan skema partisi data blocked column-wise menggunakan tiga prosesor.

Gambar 3 Ilustrasi skema partisi blocked column-wise Kebenaran algoritme GPA paralel diverifikasi dengan membandingkan keluarannya dengan keluaran algoritme GPA sekuensial (Lamport 1979). Keluaran

5 yang dibandingkan adalah keluaran skor akhir penjajaran dan pengisian matriks kemiripan. Analisis Hasil Waktu eksekusi diambil sebanyak sepuluh kali ulangan untuk setiap panjang sekuens. Setelah itu, nilai rataannya diambil sebagai waktu eksekusi akhir. Hasil komputasi GPA sekuensial akan dibandingkan dengan hasil komputasi paralel dengan menganalisis waktu eksekusi, speedup, dan efisiensi. Perbandingan dengan Penelitian Sebelumnya Perbandingan dilakukan dengan menjalankan program GPA paralel pada sistem memori bersama dan memori terdistrbusi. Program GPA paralel dijalankan pada hardware dengan spesifikasi yang sama. Sistem memori bersama menggunakan 4 core prosesor, sedangkan sistem memori terdistribusi menggunakan 4 PC. Panjang data sekuens yang digunakan dimulai dari 1000 bp sampai 16000 bp. Perbandingan dilakukan dengan melihat efisiensi kedua sistem memori. Bahan Bahan penelitian menggunakan dua sekuens DNA untuk verifikasi kebenaran algoritme GPA. Dua sekuens DNA tersebut adalah GlyRS1 Saccharomyces cereviseae (SYG_YEAST) dan GlyRS Schizosaccharomyces pombe (SYG_SCHPO). Alat Penelitian ini dilakukan dengan menggunakan empat buah komputer dengan spesifikasi CPU Intel Core i3-3220 @ 3.30 GHz dengan 4 core CPU dan RAM 8 GB.

HASIL DAN PEMBAHASAN Implementasi Global Pairwise Alignment Sekuensial Pada pengisian matriks kemiripan algoritme GPA, skor untuk setiap sel didapatkan dari skor tertinggi di antara 3 kemungkinan arah penjajaran: diagonal, atas, dan kiri. Skor diagonal dihitung dengan bantuan prosedur SIMILARITY: jika kedua residu DNA sama maka skor ditambahkan dengan skor MATCH, jika berbeda maka skor dikurangi dengan skor MISMATCH. Skor atas dan kiri dihitung dengan mengurangkannya dengan skor penalti GAP. Setiap gap memiliki skor yang sama tanpa mempedulikan posisinya. Pemilihan nilai skor MATCH dan penalti GAP mengikuti nilai standar pada program ClustalW (DDBJ 2015). Berikut adalah pseudocode algoritme GPA yang dikembangkan.

6 MATCH = +1 MISMATCH = -1 GAP = -3 SIMILARITY(a, b) 1 if a == b 2 return MATCH 3 else 4 return MISMATCH PAIRWISE-ALIGN(X, Y) 5 m = X.length 6 n = Y.length 7 let C[0.. m, 0.. n] be a new table 8 9 //inisialisasi matriks 10 for i = 0 to m 11 Ci,0 = i * GAP 12 for j = 0 to n 13 C0,j = j * GAP 14 15 for i = 1 to m 16 for j = 1 to n 17 diag = Ci-1,j-1 + SIMILARITY(Xi,Yj) 18 Ci,j = MAX up = Ci-1,j + GAP 19 left = Ci,j-1 + GAP 20 return C

Verifikasi algoritme GPA dilakukan dengan menggunakan tool ClustalW2 pada pengaturan standar. Gambar 4 menunjukkan hasil penjajaran ClustalW2 dan algoritme GPA. Secara umum, algoritme GPA telah berhasil menyejajarkan 2 sekuens. ClustalW2 menghasilkan penjajaran dengan gap yang lebih rapat.

Gambar 4 Hasil penjajaran ClustalW2 dan algoritme GPA Hasil tersebut memverifikasi bahwa algoritme GPA sekuensial adalah benar. Selanjutnya algoritme GPA tersebut akan diparalelisasi. Implementasi Global Pairwise Alignment Paralel dengan Skema Partisi Blocked Column-wise Pembagian blok kolom untuk masing-masing prosesor dilakukan secara manual. Berikut adalah potongan awal pseudocode untuk pembagian kolom matriks kemiripan kepada masing-masing prosesor.

7 1 2 3 4

int jfirst, jlast rank = MPI_Comm_rank size = MPI_Comm_size jfirst = rank * n/size + 1

Setiap prosesor akan menghitung berdasarkan baris dari kolom pertamanya (jfirst) sampai kolom terakhirnya (jlast). Ketika perhitungan tiap prosesor sudah mencapai batas kolom terakhirnya (jlast), maka prosesor akan mengirimkan nilai Ci,jlast kepada prosesor berikutnya menggunakan prosedur MPI_Send. Semua prosesor melakukan proses pengiriman kecuali prosesor terakhir. Kemudian setiap prosesor menerima nilai yang dikirimkan prosesor sebelumnya dan menyimpannya sebagai Ci,jfirst-1. Setiap prosesor melakukan proses penerimaan kecuali prosesor pertama. Berikut adalah pseudocode untuk skema pengiriman dan penerimaan nilai di dalam matriks yang dilakukan secara blocked column-wise. 5 6 7 8 9 10 11 12 13 14

for i = 1 to m if (rank != 0) //not first processor MPI_Recv(C[i][jfirst-1], rank-1) for j = jfirst to jlast diag = Ci-1,j-1 + SIMILARITY(Xi,Yj) Ci,j = MAX up = Ci-1,j + GAP left = Ci,j-1 + GAP if (rank != size-1) //not last processor MPI_Send(C[i][jlast], rank+1) return C

Langkah demi langkah pengisian matriks dan komunikasi yang dilakukan oleh prosesor pada GPA paralel adalah sebagai berikut. Inisialisasi matriks Sebagai contoh, sekuens ATGAGT ingin disejajarkan dengan sekuens ATGAC menggunakan 2 prosesor (P0 dan P1). Pertama, matriks kemiripan Fm,n dari kedua sekuens tersebut diinisialisasi. Pada tahap ini inisialisasi dilakukan oleh setiap prosesor yang digunakan dengan pseudocode berikut. 1

1 2 3 4 5

for j = 0 to n/size C[0][j+1] = (j + jfirst) * GAP if(rank == 0) //first processor for i = 1 to m C[i][0] = i * GAP

Dengan menggunakan pseudocode tersebut didapatkan inisialisasi matriks seperti pada Gambar 5.

8

Gambar 5 Inisialisasi matriks Fm,n GPA paralel Inisialisasi matriks GPA sekuensial tidak membagi matriks menjadi beberapa bagian, berbeda dengan inisialisasi matriks GPA paralel yang ditunjukkan Gambar 5. Setelah diinisialisasi, pengisian matriks GPA sekuensial dimulai dari sel 1 kolom 1 sampai sel terakhir kolom terakhir oleh hanya 1 prosesor seperti pada Gambar 6.

Gambar 6 Inisialisasi matriks Fm,n GPA sekuensial 2 Pengisian tiap nilai sel matriks Nilai sel matriks diisi menggunakan Persamaan (1) di bawah ini:

Ci,j = MAX

diag = Ci-1,j-1 + SIMILARITY(Xi,Yj) up = Ci-1,j + GAP left = Ci,j-1 + GAP

(1)

Seperti yang sudah dijelaskan sebelumnya pada prosedur SIMILARITY, jika residu DNA kedua sekuens sama, maka nilai SIMILARITY sama dengan MATCH (+1). Sebaliknya, jika berbeda, maka nilai SIMILARITY sama dengan MISMATCH (-1). Nilai GAP diatur di awal sama dengan -3. Hasil pengisian sel kolom 1 baris 1 matriks Fm,n adalah sebagai berikut: C1,1

C1,1

= MAX [C1-1,1-1 + S(A,A), C1-1,1 + GAP, C1,1-1 + GAP] = MAX [C0,0 + MATCH, C0,1 + (-3), C1,0 + (-3)] = MAX [0 + 1, (-3) - 3, (-3) - 3] = MAX [1, -6, -6] =1

Apabila proses pengisian dilanjutkan dari baris pertama, maka ketika P0 mencapai bagian kolom terakhirnya (dicatat pada variabel jlast), nilai pada Ci,jlast akan dikirimkan kepada prosesor setelahnya, yaitu P1. Proses komunikasi pengiriman dan penerimaan kedua prosesor menggunakan MPI_Send dan

9 MPI_Recv yang bersifat blocking communication, yang artinya P1 tidak akan memulai prosesnya sebelum buffer pada prosedur MPI_Recv terisi. Dalam hal ini, P1 baru akan memulai prosesnya apabila sudah menerima nilai dari P0.

Gambar 7 Proses pengiriman nilai -5 dari P0 ke P1 Gambar 7 menunjukkan P1 dapat memulai proses pengisian matriks setelah menerima nilai -5 sebagai Ci,jlast-1. Apabila proses diteruskan, P0 akan mengirimkan nilai Ci,jlast dan diterima oleh P1 sebagai Ci,jlast-1 untuk setiap iterasi i sampai m.

Gambar 8 Pengisian sel matriks Fm,n Gambar 8 menunjukkan proses pengisian sel matriks GPA paralel menggunakan 2 prosesor. Sesuai dengan pseudocode, P0 sebagai prosesor pertama hanya melakukan prosedur MPI_Send, sedangkan P1 sebagai prosesor terakhir (karena hanya menggunakan 2 prosesor) hanya melakukan prosedur MPI_Recv. Verifikasi Kebenaran Algoritme GPA Paralel Verifikasi kebenaran algoritme paralel penting karena implementasi program paralel dengan MPI yang kurang cermat akan menyebabkan keluaran yang tidak konsisten. Keluaran yang dibandingkan adalah skor akhir penjajaran dan pengisian matriks kemiripan. Gambar 9 menunjukkan perbandingan hasil pengisian matriks kemiripan pada GPA sekuensial dan GPA paralel menggunakan 2 prosesor. Skor akhir penjajaran GPA paralel sudah sama dengan GPA sekuensial. Baris dan kolom ke-0 adalah inisialisasi gap penalty yang dilakukan oleh setiap prosesor. Pada GPA sekuensial matriks kemiripan diisi hanya oleh satu prosesor, sedangkan pada GPA paralel pengisian matriks dibagi ke 2 prosesor (bisa lebih) dengan baik. Dapat dilihat bahwa nilai jlast prosesor 0 (kolom yang diarsir sebelah atas) dikirimkan menggunakan prosedur MPI_Send sebagai nilai jlast-1 prosesor selanjutnya (kolom yang diarsir sebelah bawah), dalam kasus ini prosesor 1. Apabila hasil

10 pengisian matriks dari prosesor ke-0 dan ke-1 digabungkan, hasilnya akan sama persis dengan matriks GPA sekuensial. Hal ini menunjukkan verifikasi kebenaran algoritme GPA paralel yang sudah 100% sesuai dengan algoritme GPA sekuensial.

Gambar 9 Perbandingan hasil algoritme GPA sekuensial (kiri) dan paralel dua prosesor (kanan) Memori Penyimpanan Matriks Pada sistem memori bersama, GPA paralel yang dijalankan memungkinkan untuk melakukan pengisian pada satu matriks yang sama. Sedangkan GPA paralel pada sistem memori terdistribusi mengharuskan setiap komputer yang terhubung membuat matriks pada memorinya sendiri. Untuk itu perlu diperhatikan ukuran matriks pada masing-masing komputer. Pada kondisi idealnya, ukuran matriks GPA paralel seharusnya sama dengan ukuran matriks yang digunakan pada GPA sekuensial. Apabila ukuran matriks GPA sekuensial sebesar m × n , maka setiap komputer yang terhubung pada cluster membuat matriks dengan ukuran n(m/size), dengan size adalah jumlah komputer yang digunakan untuk menjalankan GPA paralel. Namun, pada prakteknya hal ini tidak dicapai karena dibutuhkan memori untuk menyimpan nilai yang dikirimkan oleh prosesor sebelumnya sebagai nilai jlast-1 untuk memulai proses pengisian matriks seperti yang terlihat pada Gambar 7. Oleh karena itu, matriks yang dibuat oleh masing-masing komputer berukuran n(m/size + 1) sehingga total ukuran matriks yang dibuat adalah n(m + size). Ukuran ini merupakan yang paling efisien dalam penggunaan memori penyimpanan matriks GPA paralel pada sistem memori terdistribusi.

11 Analisis Hasil Analisis waktu eksekusi Waktu eksekusi terbagi menjadi waktu eksekusi sekuensial dan waktu eksekusi paralel. Waktu eksekusi sekuensial adalah lamanya waktu berlangsung antara awal dan akhir dari proses eksekusi program sekuensial. Waktu eksekusi paralel adalah lamanya waktu berlangsung dari komputasi paralel dimulai sampai momen ketika elemen terakhir yang diproses selesai dieksekusi (Grama et al. 2003). 10

Waktu (s)

8 6 4 2 0 1000

2000

5000

10000

20000

25000

30000

Panjang sekuens

Gambar 10 Grafik waktu eksekusi program penjajaran sekuens.  1 PC,  2 PC,  3 PC,  4 PC. Gambar 10 menunjukkan perbedaan waktu eksekusi terlihat untuk panjang sekuens 10 000 bp sampai 30 000 bp. Waktu eksekusi paralel lebih cepat dari waktu eksekusi sekuensial dan penambahan jumlah PC meningkatkan kecepatannya. Hal ini menunjukkan skalabilitas program GPA paralel yang dikembangkan. Analisis speedup Speedup mencatat keuntungan relatif dari menyelesaikan masalah secara paralel. Nilai speedup (S) didapatkan dari hasil bagi antara waktu eksekusi sekuensial (Ts) dengan waktu eksekusi paralel (Tp) (Grama et al. 2003). 4

Speedup

3

2 1 0 1000

2000

5000

10000

20000

25000

30000

Panjang sekuens

Gambar 11 Grafik speedup komputasi paralel algoritme GPA.  2 PC,  3 PC,  4 PC.

12

Gambar 11 menunjukkan peningkatan speedup pada panjang sekuens 1000 bp sampai 10 000 bp. Speedup untuk masing-masing skenario penggunaan PC cenderung konstan pada panjang sekuens 20 000 bp sampai 30 000 bp. Speedup dengan 2 PC mencapai rasio 1.78, sementara speedup dengan 3 PC dan 4 PC masing-masing mencapai rasio 2.57 dan 3.37. Hal ini menunjukkan bahwa penambahan jumlah PC untuk menjalankan program paralel akan meningkatkan speedup pada algoritme GPA. Analisis efisiensi Efisiensi adalah nilai hitungan perbandingan speedup dengan penggunaan sumber daya yang ada, dalam hal ini banyaknya PC. Nilai efisiensi (E) didapatkan dari hasil bagi antara speedup (S) dengan jumlah PC (p) yang digunakan. Dalam sistem paralel ideal, nilai S sama dengan p sehingga nilai efisiensi sama dengan satu. Namun pada prakteknya, nilai S selalu kurang dari p sehingga nilai efisiensi berkisar antara 0 dan 1 (Grama et al. 2003). Hasil perhitungan nilai efisiensi dapat dilihat pada Gambar 12. 100%

Efisiensi

80% 60% 40% 20% 0% 1000

2000

5000

10000

20000

25000

30000

Panjang sekuens

Gambar 12 Grafik efisiensi komputasi paralel algoritme GPA.  2 PC,  3 PC,  4 PC. Gambar 12 menunjukkan efisiensi komputasi paralel algoritme GPA menggunakan 2 PC sampai 4 PC. Efiensi terus meningkat sampai pada panjang sekuens 10 000 bp. Masing-masing skenario penggunaan PC mencapai efisiensi konstan pada panjang sekuens 20 000 bp sampai 30 000 bp. Efisiensi konstan menunjukkan bahwa kinerja program paralel scalable dengan ukuran data. Efiensi dengan 2 PC mencapai 95.62% pada panjang sekuens 30 000 bp. Untuk panjang sekuens yang sama, efisiensi 3 PC dan 4 PC masing-masing mencapai 92.38% dan 89.81%. Hasil lengkap dari run program GPA sekuensial dan paralel tertera pada Lampiran 1. Perbandingan dengan Penelitian Sebelumnya Perbandingan dilakukan dengan menjalankan program GPA paralel pada sistem memori bersama dan pada sistem memori terdistribusi menggunakan spesifikasi hardware yang sama. Pada sistem memori bersama program GPA

13 paralel dijalankan oleh 4 core prosesor, sementara pada sistem memori terdistribusi program GPA paralel dijalankan oleh 4 PC. Jumlah panjang sekuens yang digunakan juga sama, yaitu dari 1000 bp sampai 16 000 bp. Hasil perbandingan ditunjukkan pada Gambar 13. 100%

Efisiensi

80% 60% 40% 20% 0% 1000

2000

4000

8000

16000

Panjang sekuens

Gambar 13 Grafik efisiensi GPA pada sistem memori bersama dan sistem memori terdistribusi.  distributed memory,  shared memory. Berdasarkan Gambar 13, efisiensi kedua sistem memori terus meningkat mulai dari panjang sekuens 1000 bp sampai 16 000 bp. Efisiensi sistem memori terdistribusi sedikit di bawah efisiensi sistem memori bersama, yaitu 83.66% dibanding 89.73%. Namun, penerapan GPA paralel pada sistem memori terdistribusi terbukti scalable. Hal ini berarti speedup yang lebih tinggi dapat dicapai dengan menambah jumlah PC yang menjalankan program GPA paralel. Hasil lengkap perbandingan GPA paralel pada sistem memori bersama dan sistem memori terdistribusi tertera pada Lampiran 2.

KESIMPULAN DAN SARAN Kesimpulan Berdasarkan hasil penelitian, dapat disimpulkan bahwa tujuan penelitian ini telah tercapai. Komputasi GPA paralel dengan skema partisi blocked column-wise pada sistem memori terdistrisbui berhasil memangkas waktu eksekusi algoritme GPA sekuensial dengan baik. Speedup yang diperoleh dengan menggunakan 2, 3, dan 4 PC berturut-turut adalah 1.78, 2.57, dan 3.36 untuk panjang sekuens 30 000 bp. Efisiensi menggunakan jumlah PC dan panjang sekuens yang sama berturutturut adalah 89.32%, 85.97%, dan 84.19%. Kinerja GPA paralel juga scalable dengan ukuran data dan jumlah PC yang digunakan. Komputasi GPA paralel pada sistem memori terdistribusi memiliki efisiensi yang sedikit kurang dari efisiensi sistem memori bersama. Efisiensi menggunakan 4 PC mencapai 83.66%%, sedangkan pada sistem memori bersama dengan 4 core prosesor mencapai 89.73% untuk panjang sekuens 16 000 bp. Namun, speedup yang lebih tinggi dapat dicapai pada sistem memori terdistribusi dengan menambah jumlah PC yang menjalankan program GPA paralel.

14 Saran Saran untuk penelitian selanjutnya adalah untuk menambahkan fitur gap extension sehingga hasil penjajaran lebih optimal dan menambah jumlah PC untuk menjalankan program paralel. Selain itu, penelitian selanjutnya dapat pula membandingan kinerja antara komputer dengan spesifikasi kinerja tinggi dan cluster komputer dengan spesifikasi kinerja rumahan. Saran lainnya adalah untuk mengembangkan algoritme GPA paralel pada sistem hibrida shared-distributed memory.

DAFTAR PUSTAKA Akbar AR, Sukoco H, Kusuma WA. 2015. Comparison of data partitioning schema of parallel pairwise alignment on shared memory system. Telkomnika. 13(2): 694-702. doi: 10.12928/telkomnika.v13i2.1415. [DDBJ] DNA Data Bank of Japan. 2015. ClustalW help [internet]. [diperbaharui 2015 Apr 6]. Tersedia pada: http://www.ddbj.nig.ac.jp/search/help/ clustalwhelp-e.html Grama A, Gupta A, Karypis G, Kumar V. 2003. Introduction to Parallel Computing: Second Edition. Edinburgh (GB): Benjamin/Cumming. hlm 233275. Gautham N. 2006. Bionformatics Databases and Algorithms. Oxford (GB): Alpha Science International. hlm 69-80. Hsien-Yu L, Meng-Lai Y, Yi C. 2004. A parallel implementation of the SmithWaterman algorithm for massive sequences searching. Engineering in Medicine and Biology Society. 2(9):2817-2820. Lamport L. 1979. How to make a multiprocessor computer that correctly executes multiprocess programs. IEEE Transactions on Computers. 100(9):690-691. Liu Y, Wirawan A, Schmidt B. 2013. CUDASW++ 3.0: accelerating SmithWaterman protein database search by coupling CPU and GPU SIMD instructions. BMC Bioinformatics. 14(117): 1-10. Mount DW. 2001. Bioinformatics: Sequences and Genome Analysis. New York (US): Cold Spring Harbor Laboratory. hlm 11. Quinn MJ. 2003. Parallel Programming in C with MPI and OpenMP. New York (US): McGraw-Hill. hlm 94-95. Shebab SA, Keshk A, Mahgoub H. 2012. Fast dynamic algorithm for sequence alignment based on bionformatics. International Journal of Computer Applications. 37(7): 54-61.

15 Lampiran 1 Hasil run program GPA sekuensial dan paralel dengan 2 sampai 4 PC untuk panjang sekuens 1000 bp sampai 30 000 bp Panjang sekuens: 1000 bp Pengulangan

Sekuensial

1 2 3 4 5 6 7 8 9 10 Rataan Speedup Efisiensi (%)

0.0159 0.0117 0.0139 0.0169 0.0137 0.0125 0.0118 0.0120 0.0118 0.0118 0.0132

Paralel (procs) 2 3 4 0.0144 0.0144 0.0145 0.0130 0.0153 0.0150 0.0161 0.0137 0.0141 0.0116 0.0143 0.0146 0.0164 0.0144 0.0150 0.0153 0.0135 0.0143 0.0155 0.0129 0.0147 0.0162 0.0134 0.0143 0.0161 0.0140 0.0139 0.0161 0.0141 0.0143 0.0153 0.0138 0.0145 0.8629 0.9575 0.9118 43.1436 31.9173 22.7956

Panjang sekuens: 2000 bp Pengulangan

Sekuensial


0.0469 0.0469 0.0471 0.0470 0.0469 0.0470 0.0469 0.0469 0.0469 0.0470 0.0469

Paralel (procs) 2 3 4 0.0279 0.0272 0.0284 0.0313 0.0233 0.0243 0.0318 0.0229 0.0240 0.0335 0.0236 0.0224 0.0325 0.0299 0.0239 0.0319 0.0263 0.0285 0.0287 0.0241 0.0222 0.0333 0.0230 0.0264 0.0328 0.0231 0.0215 0.0312 0.0223 0.0216 0.0315 0.0246 0.0243 1.4909 1.9105 1.9306 74.5430 63.6823 48.2640

16 Lampiran 1 Lanjutan Panjang sekuens: 5000 bp Pengulangan

Sekuensial


0.2802 0.2802 0.2802 0.2803 0.2803 0.2801 0.2802 0.2802 0.2802 0.2801 0.2802

Paralel (procs) 2 3 4 0.1672 0.1213 0.0973 0.1672 0.1211 0.1015 0.1670 0.1229 0.0955 0.1670 0.1215 0.0973 0.1669 0.1231 0.0962 0.1662 0.1259 0.0997 0.1668 0.1230 0.0956 0.1669 0.1216 0.0962 0.1674 0.1210 0.0959 0.1669 0.1216 0.0968 0.1670 0.1223 0.0972 1.6783 2.2912 2.8829 83.9130 76.3731 72.0716


Sekuensial


1.0683 1.0682 1.0684 1.0681 1.0680 1.0684 1.0681 1.0680 1.0682 1.0680 1.0682

Paralel (procs) 2 3 4 0.6198 0.4436 0.3599 0.6201 0.4437 0.3475 0.6200 0.4438 0.3475 0.6202 0.4494 0.3469 0.6202 0.4434 0.3477 0.6188 0.4438 0.3471 0.6207 0.4436 0.3513 0.6198 0.4439 0.3474 0.6190 0.4441 0.3480 0.6192 0.4440 0.3474 0.6198 0.4443 0.3491 1.7235 2.4039 3.0600 86.1738 80.1304 76.5010


Sekuensial


4.1459 4.1458 4.1462 4.1457 4.1456 4.1460 4.1460 4.1461 4.1459 4.1459 4.1459

Paralel (procs) 2 3 4 2.3318 1.6521 1.2348 2.3299 1.6083 1.2468 2.3307 1.6541 1.2402 2.3310 1.6083 1.2346 2.3297 1.6105 1.2636 2.3320 1.6075 1.2348 2.3310 1.6111 1.2338 2.3303 1.6076 1.2711 2.3316 1.6073 1.2364 2.3307 1.6075 1.2343 2.3309 1.6174 1.2430 1.7787 2.5633 3.3353 88.9352 85.4425 83.3823


Sekuensial


6.4052 6.4046 6.4049 6.4049 6.4050 6.4046 6.4045 6.4047 6.4047 6.4045 6.4048

Paralel (procs) 2 3 4 3.5789 2.4700 1.9063 3.5744 2.4703 1.9455 3.5747 2.4689 1.9469 3.5749 2.4701 1.9478 3.5758 2.4691 1.9468 3.5746 2.4703 1.9496 3.5749 2.4698 1.9472 3.5775 2.4697 1.9057 3.5740 2.4702 1.9050 3.5743 2.4705 1.9056 3.5754 2.4699 1.9306 1.7913 2.5931 3.3174 89.5668 86.4383 82.9357


Sekuensial


9.1124 9.1122 9.1111 9.1117 9.1113 9.1129 9.1118 9.1133 9.1125 9.1123 9.1122

Paralel (procs) 2 3 4 5.1005 3.5392 2.7006 5.1000 3.5375 2.7011 5.1009 3.4991 2.7001 5.1041 3.5375 2.7001 5.0990 3.5412 2.7486 5.1019 3.5384 2.6998 5.0991 3.5378 2.7018 5.1037 3.5619 2.7020 5.1003 3.5390 2.7019 5.1009 3.4985 2.7016 5.1010 3.5330 2.7058 1.7863 2.5792 3.3677 89.3168 85.9719 84.1923

19 Lampiran 2 Hasil run program GPA paralel pada sistem memori terdistribusi dan sistem memori bersama dengan panjang sekuens 1000 bp sampai 16 000 bp Panjang sekuens: 1000 bp Pengulangan Sekuensial 1 2 3 4 5 6 7 8 9 10 Rataan Speedup Efisiensi (%)

0.0159 0.0117 0.0139 0.0169 0.0137 0.0125 0.0118 0.0120 0.0118 0.0118 0.0132

Paralel 4 PC/Core Distributed memory Shared Memory 0.0139 0.0145 0.0130 0.0150 0.0131 0.0141 0.0130 0.0146 0.0133 0.0150 0.0145 0.0143 0.0149 0.0147 0.0132 0.0143 0.0133 0.0139 0.0147 0.0143 0.0145 0.0137 0.9118 0.9640 22.7956 24.1003

Panjang sekuens: 2000 bp Pengulangan Sekuensial 1 2 3 4 5 6 7 8 9 10 Rataan Speedup Efisiensi (%)

0.0469 0.0469 0.0471 0.0470 0.0469 0.0470 0.0469 0.0469 0.0469 0.0470 0.0469


20 Lampiran 2 Lanjutan Panjang sekuens: 4000 bp Pengulangan Sekuensial 1 2 3 4 5 6 7 8 9 10 Rataan Speedup Efisiensi (%)

0.1349 0.1349 0.1349 0.1349 0.1349 0.1350 0.1349 0.1348 0.1349 0.1349 0.1349


Panjang sekuens: 8000 bp Pengulangan Sekuensial 1 2 3 4 5 6 7 8 9 10 Rataan Speedup Efisiensi (%)

0.5385 0.5385 0.5384 0.5384 0.5384 0.5384 0.5384 0.5385 0.5385 0.5385 0.5385


21 Lampiran 2 Lanjutan Panjang sekuens: 16000 bp Pengulangan Sekuensial 1 2 3 4 5 6 7 8 9 10 Rataan Speedup Efisiensi (%)

2.1598 2.1600 2.1601 2.1601 2.1600 2.1601 2.1598 2.1602 2.1602 2.1604 2.1601


22

RIWAYAT HIDUP Penulis dilahirkan di Yokohama pada tanggal 20 Mei 1993. Penulis merupakan anak pertama dari empat bersaudara pasangan Wihatmoko Waskioaji dan Lina Herlina. Penulis mengenyam pendidikan dasar di SD Negeri Puspiptek Kota Tangerang Selatan (1999-2005). Penulis melanjutkan pendidikan menengah pertama di SMP Islam Nurul Fikri Boarding School Kabupaten Serang (20052008). Kemudian, penulis melanjutkan pendidikan menengah atas di SMA Negeri 2 Kota Tangerang Selatan (2008-2011). Penulis berkesempatan melanjutkan studi di Institut Pertanian Bogor melalui jalur Ujian Talenta Masuk IPB (UTM) di Departemen Ilmu Komputer, Fakultas Matematika dan Ilmu Pengetahuan Alam. Selama masa kuliah, penulis pernah menjadi asisten praktikum pada mata kuliah Penerapan Komputer (2012) dan Pengembangan Sistem Berorientasi Objek (2015). Penulis juga aktif di organisasi kemahasiswaan, yaitu Badan Eksekutif Mahasiswa Fakultas Matematika dan Ilmu Pengetahuan Alam (BEM FMIPA) Institut Pertanian Bogor pada tahun 2012 hingga 2014. Penulis sempat menjabat sebagai Ketua Umum BEM FMIPA pada masa bakti 2013-2014. Selain itu, penulis melaksanakan kegiatan Praktik Kerja Lapangan di Pusat Sosial Ekonomi dan Kebijakan Pertanian.

AKSELERASI GLOBAL PAIRWISE ALIGNMENT DENGAN SKEMA PARTISI BLOCKED COLUMN-WISE PADA SISTEM MEMORI TERDISTRIBUSI MAULANA RIZAL IBRAHIM

Recommend Documents