ANALISIS KINERJA ALGORITME GENETIKA PARALEL UNTUK TRAVELING SALESMAN PROBLEM MENGGUNAKAN MULTI-GPU YANG HETEROGEN

SAID MUHAMMAD RAMADHAN, Dr.techn. Ahmad Ashari, M.Kom

2020 | Skripsi | S1 ELEKTRONIKA DAN INSTRUMENTASI

Algoritme genetika (GA) adalah suati algoritme metaheuristik yang terinspirasi dari prinsip genetika dan seleksi alam seperti perkawinan silang, seleksi, dan mutasi yang telah banyak digunakan untuk menyelesaikan masalah kombinasional salah satunya adalah traveling salesman problem (TSP). GA dapat menghasilkan solusi yang baik untuk permasalahan TSP namun waktu eksekusinya lebih lama dibandingkan dengan algoritme lainya. Untuk itu dibutuhkan suatu metode untuk mempercepat waktu eksekusi tersebut, salah satunya adalah melakukan paralelisasi dengan menggunakan GPU. Dalam penelitian ini, dilakukan paralelisasi algoritme GA untuk permasalahan TSP pada satu unit GPU (single-GPU) serta dua unit GPU yang berbeda (multi-GPU heterogen) menggunkan API OpenCL. Paralelisasi dilakukan dengan membuat GPU bekerja secara paralel untuk menghasilkan sekaligus menghitung nilai fitness populasi. Hasil penelitan menunjukkan bahwa algoritme paralel multi-GPU dapat menghasilkan peningkatan waktu eksekusi (speed up) hingga 14,98 kali terhadap algoritme serial dan peningkatan hingga 1,59 kali terhadap algoritme paralel single-GPU dengan sedikit penurunan pada akurasinya.

Genetic algorithm (GA) is a metaheuristic algorithm inspired by the principles of genetics and natural selection such as cross-breeding, selection, and mutation which have been widely used to solve combinational problems, one of which is the traveling salesman problem (TSP). GA can produce a good solution for TSP problems but the execution time is longer than other algorithms. For that we need a method to speed up the execution time, one of which is to do parallelization using the GPU. In this study, the GA algorithm was parallelized for TSP problems on one GPU unit (single-GPU) as well as two different GPU units (heterogeneous multi-GPU) using the OpenCL API. Parallelization is done by making the GPU work in parallel to produce and calculate the population fitness value. The results show that multi-GPU parallel algorithms can result in up to 14.98 times increase in execution time (speed up) for serial algorithms and up to 1.59 times for single-GPU parallel algorithms with a slight decrease in accuracy.

Kata Kunci : komputasi paralel, GPU, multi-GPU, multi-GPU heterogen, algoritme genetika, TSP