Accelerating computer algorithm by using GPU

Abstract

Travelling Salesman Problem (TSP) is one of the significant problems in computer science which tries to find the shortest path for a salesman who needs to visit a set of cities and it involves in many computing problems such as networks, genome analysis, logistic etc. Using parallel executing paradigms, especially GPUs, is appealing in order to reduce the problem-solving time of TSP. One of the main issues in GPUs is to have limited GPU memory which would not be enough for the entire data. Therefore, transferring data from host device would reduce the performance in execution time. In this study, we present a methodology for compressing data to represent cities in the TSP so that we include more cities in GPU memory. We implement our methodology in Iterated Local Search (ILS) algorithm with 2-opt and show that our implementation presents 29% performance improvement compared to the state-of-the-art GPU implementation.

Gezgin Satıcı Problemi (TSP), bir dizi şehri ziyaret etmesi gereken bir satıcı için en kısa yolu bulmaya çalışan bilgisayar bilimlerinin önemli problemlerinden biridir ve ağlar, genom analizi, lojistik vb. gibi birçok hesaplama probleminde yer almaktadır. TSP'nin problem çözme süresini azaltmak için paralel yürütme paradigmalarını, özellikle GPU'ları kullanmak caziptir. GPU'lardaki ana sorunlardan biri, tüm veriler için yeterli olmayacak sınırlı GPU belleğine sahip olmaktır. Bu nedenle, verilerin ana cihazdan aktarılması, yürütme süresindeki performansı düşürecektir. Bu çalışmada, TSP'deki şehirleri temsil etmek için verileri sıkıştırmak için bir metodoloji sunuyoruz, böylece GPU belleğine daha fazla şehir dahil ediyoruz. Metodolojimizi 2-opt ile Yinelemeli Yerel Arama (ILS) algoritmasında uyguluyoruz ve uygulamamızın son teknoloji GPU uygulamasına kıyasla %29 performans artışı sunduğunu gösteriyoruz.