PERANCANGAN PERANGKAT LUNAK SIMULASI KOMPUTASI DNA BERBASIS CUDA DAN PENGUJIAN KINERJANYA DALAM PEMECAHAN TRAVELLING SALESMAN PROBLEM

SUPRADI SITEPU, Teguh Bharata Adji, S.T., M.T., M.Eng., Ph.D.

2015 | Tesis | S2 Teknik Elektro

Komputasi DNA merupakan salah satu solusi komputasi alternatif yang memiliki banyak kelebihan. Namun, komputasi ini hanya dapat dilakukan di dalam laboratorium bioinformatik dengan banyak keterbatasan. Oleh sebab itu, dibutuhkan sebuah cara untuk memanfaatkan kelebihan komputasi ini sekaligus mengeliminasi kekurangannya. Salah satu solusinya adalah dengan membuat program simulasi. Sayangnya, program simulasi yang sudah dibuat pada penelitian sebelumnya dianggap kurang memuaskan. Waktu eksekusi yang dibutuhkan dianggap terlalu lama untuk mencari solusi TSP (travelling salesman problem) dari sebuah graf sederhana. Untuk itu, penelitian kali ini mencoba menggunakan paralelisasi CUDA sebagai sarana mendongkrak kecepatan kinerja. Program simulasi yang telah dibuat ini kemudian diuji akurasi serta waktu eksekusinya dengan mencoba menyelesaikan TSP dalam skala kecil. Hasil pengujiannya kemudian dibandingkan dengan hasil pengujian program terdahulu yang dikembangkan tanpa paralelisasi CUDA. Dari hasil pembandingan, tampak bahwa kinerja program simulasi dengan paralelisasi CUDA lebih baik dibandingkan program terdahulu yang dikembangkan secara serial. Semakin besar ukuran graf yang diuji, semakin signifikan keunggulan performa dari program simulasi yang diparalelkan dengan CUDA. Setelah penelitian ini, struktur paralelisasi yang dibuat diharapkan dapat dimanfaatkan lebih jauh bagi penelitian-penelitian ke depannya. Kata kunci: Komputasi DNA, Travelling Salesman Problem, CUDA

DNA computation is one out of many alternative computation method available which provides many advantages. However, there are a number of problem that make this computation infeasible. Thus, a method to utilize its advantageous aspect while eliminating the problems is needed in the future. An effort to find the solution is attempted by creating a simulation program, which has been accomplished by earlier research. However, the former DNA computation application didn’t meet the satisfactory criteria on its performance. Its execution time is deemed as inefficient for it needed a substantial amount of time only to find TSP solution from a simple graph. Thus, this research was carried on to paralelize the former program, by using CUDA, in order to increase its performance. The developed application is then used to solve a Travelling Salesman Problem from some simple graphs. The result is then compared with the former application’s solution, which was developed using serial computation without any CUDA involvement, for the exact same problem. The result of comparation shows that the later application’s performance outperform the earliers. The more number of vertex in testing graph, the more significant the increasing performance in execution time by the developed application. The paralelized structure from this research is hoped to be carried on and used further to another experiment. Keywords: DNA computation, Traveling Salesman Problem, CUDA

Kata Kunci : Komputasi DNA, Travelling Salesman Problem, CUDA; DNA computation, Traveling Salesman Problem, CUDA