High-throughput Ant Colony Optimization on graphics processing units

Nowadays, computer researchers can face ever-complex scientific problems by using a hardware and software co-design. One successful approach is exploring novel massively-parallel Natural-inspired algorithms, such as the Ant Colony Optimization (ACO) algorithm, through the exploitation of high-throughput accelerators such as GPUs, which are designed to provide high levels of parallelism and low Energy per instruction (EP) cost through heavy vectorization. In this paper, we demonstrate how to take advantage of contemporary hardware-based CUDA vectorization to optimize the ACO algorithm when applied to the Traveling Salesman Problem (TSP). Several parallel designs are proposed and analyzed on two different CUDA architectures. Our results reveal that our vectorization approaches can obtain good performance on these architectures. Moreover, atomic operations are under study showing good benefits on latest generations of CUDA architectures. This work lays the groundwork for future developments of ACO algorithm on high-performance platforms.