ANALISIS KINERJA ALGORITME PARALEL ANT COLONY OPTIMIZATION (ACO) UNTUK TRAVELLING SALESMAN PROBLEM (TSP) PADA MULTI-GPU

RIFKI NURDIYANTO, Dr.techn. Ahmad Ashari, M.Kom.

2019 | Skripsi | S1 ELEKTRONIKA DAN INSTRUMENTASI

Ant Colony Optimization (ACO) adalah suatu algoritme pencarian berbasis populasi yang telah banyak digunakan untuk menyelesaikan berbagai permasalahan kombinatorial, salah satunya adalah travelling salesman problem (TSP). ACO dapat menghasilkan solusi yang paling baik pada permasalahan TSP namun waktu eksekusinya lebih lama dibandingkan dengan algoritme lainnya. Untuk itu dibutuhkan suatu metode untuk mempercepat waktu eksekusi tersebut, salah satunya adalah melakukan paralelisasi dengan menggunakan GPU. GPU memiliki ratusan core didalamnya yang dapat dimanfaatkan untuk melakukan paralelisasi dengan cara membagi beban komputasi ke ratusan core tersebut. Hal tersebut membuat GPU memiliki potensi yang sangat besar untuk dijadikan sebagai perangkat komputasi paralel dibandingkan dengan CPU yang hanya memiliki beberapa core saja. Dalam penelitian ini, dilakukan paralelisasi algoritme ACO untuk permasalahan TSP pada satu unit GPU (single-GPU) serta pada dua unit GPU (multi-GPU). Hasil penelitian menunjukkan bahwa algoritme paralel dapat menghasilkan peningkatan waktu eksekusi (speed up) hingga 9,4151 ± 0,002 kali terhadap algoritme serial. Paralelisasi algoritme ACO pada multi-GPU juga menghasilkan peningkatan kecepatan waktu eksekusi yang lebih tinggi dibandingkan dengan paralelisasi pada single-GPU dengan speed-up algoritme paralel multi-GPU terhadap single-GPU hingga 1,59432 ± 0,0013 kali.

Ant Colony Optimization (ACO) is a population-based search algorithm that has been widely used to solve various combinatorial problems, one of them is the traveling salesman problem (TSP). ACO can produce the best solution to the TSP but the execution time is longer compared to other algorithms. Therefor a method is needed to speed up the execution time, one of the method is to do parallelization using GPU. GPU has hundreds of cores in it that can be used to do parallelization by dividing the computing load to its hundreds of cores. This makes the GPU has a huge potential to be used as a parallel computing device compared to CPU that only has a few cores. In this study, ACO was parallelized for TSP on one GPU unit (single-GPU) as well as on two GPU units (multi-GPUs). The results showed that parallelization ACO using GPU can produce a speed up in execution time up to 9,4151 ± 0,002 times of serial algorithms. Parallelization of the ACO algorithm on multi-GPUs also results in a speed up of execution time that is higher than parallelization on single-GPU with speed up multi-GPUs parallel algorithms against single-GPU up to 1,59432 ± 0,0013 times.

Kata Kunci : komputasi paralel, ant colony optimization, tsp, GPU, multi-GPU