Analisis Penyelesaian Traveling Salesman Problem Dengan Metode Brute Force Menggunakan Graphic Processing Unit

Abstrak

Komputasi paralel sangat dibutuhkan dalam masalah komputasi yang memiliki kompleksitas tinggi sehingga dapat dikerjakan dalam waktu yang cepat. Komputasi paralel membutuhkan hardware yang memiliki kinerja tinggi dan software yang memadai untuk mengeksekusi algoritma secara parallel. Salah satu pendekatan komputasi paralel adalah Graphic Processing Unit (GPU) Computing, dimana dalam sebuah GPU terdapat banyak thread yang mampu ditugaskan secara paralel. Brute Force adalah teknik pemecahan masalah yang sangat umum dan dapat digunakan untuk menyelesaikan masalah komputasi untuk menemukan jalur terbaik. Brute Force bekerja dengan meng-enumerasi semua kandidat kemungkinan yang ada, sehingga menghasilkan solusi yang terbaik. Pada penelitian ini akan diimpelementasikan Brute Force dengan teknik Exhaustive Search pada GPU, dan menganalisis jumlah threadProcess pada setiap thread dan pengaruh block dan thread pada GPU. Setelah dilakukan penelitian dan uji statistik, didapatkan bahwa Perubahan threadProcess yang semakin besar akan mengakibatkan persentase penurunan waktu semakin besar dan juga semakin banyak threadProcess maka kecepatan komputasi GPU akan menuju satu titik, karena kecepatan komputasi pada device GPU telah mencapai titik maksimal. Pada percobaan yang dilakukan, GPU akan mengungguli kinerja CPU ketika jumlah maxCity>10. Kemudian terdapat perbedaan waktu yang signifikan antara threadProcess 1 dan threadProcess 2 sebesar 41.35%, hal ini disebabkan karena device GPU tersebut tidak dipakai secara maksimal. Untuk presentase penurunan waktu terbesar ketika menggunakan metode parallel adalah ketika user mampu menemukan kombinasi thread dan block yang pas, karena penambahan jumlah thread dan block tidak selalu menjamin penurunan kecepatan waktu pencarian, dimana waktu pencarian akan mencapai titik konvergen.

Kata kunci : TSP, Brute Force, GPU, CUDA.