Komputasi Paralel Pairwise Alignment Metode Blocked Antidiagonal Menggunakan OpenMP

Abstract

Skema partisi data yang baik dalam pemrograman paralel dapat membantu mempersingkat waktu komputasi algoritme. Pemrograman dinamis dalam bidang bioinformatik dapat memanfaatkan pemrograman paralel, pairwise alignment sebagai contoh. Beberapa skema partisi data yang diuji menghasilkan efisiensi yang bervariasi. Skema blocked antidiagonal digunakan dengan menggabungkan blok dalam skema antidiagonal. Algoritme paralel dengan OpenMP diimplementasikan dalam blok antidiagonal diharapkan dapat mempersingkat waktu komputasi. Setiap blok antidiagonal diberikan sebuah thread dalam proses komputasi paralel. Sebuah blok diharapkan dapat memanfaatkan fungsi cache internal CPU. Dari hasil pengujian, didapatkan ukuran blok yang lebih besar akan mempercepat waktu komputasi pada ukuran data DNA yang juga lebih panjang. Sementara, pada ukuran DNA yang pendek tidak akan mempengaruhi waktu komputasi secara signifikan. Ukuran blok terbaik yang didapat pada CPU yang digunakan adalah 128×128, yang menghasilkan speedup 3.10 kali lipat dengan efisiensi 75%.