High-throughput Ant Colony Optimization on graphics processing units

José M. Cecilia, Antonio Llanes, José L. Abellán, Juan Gómez-Luna, Li Wen Chang, Wen Mei W. Hwu

Research output: Contribution to journalArticle

Abstract

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.

Original languageEnglish (US)
Pages (from-to)261-274
Number of pages14
JournalJournal of Parallel and Distributed Computing
Volume113
DOIs
StatePublished - Mar 2018

    Fingerprint

Keywords

  • ACO
  • Agnostic vectorization
  • Atomic operations
  • GPUs
  • TSP

ASJC Scopus subject areas

  • Software
  • Theoretical Computer Science
  • Hardware and Architecture
  • Computer Networks and Communications
  • Artificial Intelligence

Cite this