| dc.description.abstract | Penjajaran urutan biologi seperti basa nukleotida merupakan tahapan penting dalam analisis genomik, antara lain untuk analisis filogenetik, identifikasi mutasi serta penentuan biomarker. Dalam disertasi ini, fokus penelitian terletak pada aspek komputasi algoritmik, sedangkan data biologis digunakan sebagai studi kasus untuk mengevaluasi kinerja pendekatan yang diusulkan. Salah satu algoritma penjajaran global yang sudah banyak digunakan adalah algoritma Needleman-Wunsch (NW). Namun demikian, algoritma ini memiliki kompleksitas ruang dan waktu sebesar O(nm) atau O(n^2), sehingga menjadi kendala serius ketika diterapkan pada data genom berukuran besar. Pemanfaatan Graphics Processing Unit (GPU) membuka peluang untuk mempercepat eksekusi algoritma NW melalui komputasi paralel, meskipun keterbatasan kapasitas memori GPU tetap menjadi tantangan utama dalam pengolahan matriks dynamic programming berskala besar.
Penelitian ini bertujuan untuk mengoptimalkan komputasi algoritma Needleman-Wunsch melalui pemanfaatan GPU dan strategi tiling guna meningkatkan kinerja dan skalabilitas. Strategi tiling digunakan untuk membagi matriks pemrograman dinamis menjadi submatriks yang lebih kecil dan terkelola, sehingga memungkinkan distribusi komputasi ke unit-unit pemroses paralel secara lebih efisien. Pendekatan ini dirancang dengan tetap mempertahankan ketergantungan data antarelemen matriks, sehingga aspek correctness hasil penjajaran tetap terjaga dan identik dengan implementasi NW serial.
Metode penelitian dilaksanakan melalui beberapa tahapan, meliputi studi literatur, perumusan masalah, pengusulan model komputasi, implementasi algoritma, serta evaluasi performa. Pada tahap awal, algoritma NW diimplementasikan secara serial dan dieksekusi pada Central Processing Unit (CPU) sebagai baseline. Tahap selanjutnya adalah pengembangan versi paralel pada satu unit GPU untuk verifikasi correctness serta pengukuran percepatan komputasi tanpa strategi tiling. Tahap berikutnya difokuskan pada pengembangan algoritma paralel dengan strategi tiling yang dijalankan pada sistem multi-GPU, sebagai pendekatan untuk mengatasi keterbatasan kapasitas memori GPU sekaligus meningkatkan skalabilitas komputasi. Eksperimen dilakukan menggunakan data biomarker penyakit kanker payudara serta Saccharomyces cerevisiae dengan variasi panjang urutan, sehingga menghasilkan matriks dynamic programming dengan jumlah elemen ratusan juta sel. Pada konfigurasi terbesar, matriks yang diproses memiliki lebih dari 400 juta elemen, yang merepresentasikan skenario komputasi berskala besar dan menantang dari sisi kebutuhan memori serta waktu eksekusi.
Evaluasi kinerja dilakukan menggunakan beberapa metrik, meliputi waktu eksekusi kernel GPU, waktu pencetakan matriks, total waktu eksekusi, percepatan (speedup), throughput, biaya komputasi, serta skalabilitas terhadap variasi panjang data genom. Hasil eksperimen menunjukkan bahwa pendekatan paralel berbasis GPU mampu memberikan percepatan yang signifikan dibandingkan eksekusi serial pada CPU. Implementasi NW pada satu GPU menghasilkan percepatan hingga 14,8 kali, dengan titik break-even pada panjang urutan sekitar 117 nukleotida, sehingga efektif untuk pemrosesan data berukuran menengah. Selanjutnya, penerapan strategi tiling pada sistem GPU ganda mampu meningkatkan skalabilitas komputasi secara substansial, dengan cakupan pemrosesan matriks hingga 419 juta sel dan percepatan maksimum mencapai 68 kali dibandingkan CPU.
Kontribusi utama atau novelty penelitian ini terletak pada perancangan skema tiling berbasis dependensi diagonal untuk Needleman-Wunsch pada multi-GPU yang memungkinkan komputasi matriks besar melebihi kapasitas satu GPU, dengan pengurangan kebutuhan memori global melalui pertukaran data batas antarsubmatriks. Hasil evaluasi menunjukkan bahwa peningkatan jumlah GPU dapat memperluas kapasitas pengolahan data urutan tanpa mengorbankan aspek correctness hasil penjajaran.
Secara keseluruhan, penelitian ini menunjukkan bahwa komputasi paralel berbasis GPU, khususnya melalui strategi tiling pada sistem multi-GPU, mampu meningkatkan performa dan skalabilitas algoritma Needleman-Wunsch untuk penjajaran urutan genom berskala besar. Tantangan yang masih terbuka meliputi overhead komunikasi antar-GPU serta sinkronisasi antara host dan device yang berpotensi menurunkan efisiensi pada dataset berukuran sangat besar. Oleh karena itu, penelitian lanjutan diarahkan pada pengembangan mekanisme resource-aware scheduling yang lebih adaptif, optimisasi manajemen memori antar-GPU, serta perancangan model prediksi kinerja untuk berbagai konfigurasi perangkat keras. Dengan demikian, disertasi ini diharapkan dapat memberikan kontribusi terhadap pengembangan akselerasi algoritmik berbasis GPU yang lebih efisien, skalabel, dan aplikatif dalam bidang bioinformatika. | |
