본문 바로가기
  • Home

GPU-based Parallel Ant Colony System for Traveling Salesman Problem

  • Journal of The Korea Society of Computer and Information
  • Abbr : JKSCI
  • 2022, 27(2), pp.1-8
  • DOI : 10.9708/jksci.2022.27.02.001
  • Publisher : The Korean Society Of Computer And Information
  • Research Area : Engineering > Computer Science
  • Received : January 26, 2022
  • Accepted : February 13, 2022
  • Published : February 28, 2022

Yunseok Rhee 1

1한국외국어대학교

Accredited

ABSTRACT

In this paper, we design and implement a GPU-based parallel algorithm to effectively solve the traveling salesman problem through an ant color system. The repetition process of generating hundreds or thousands of tours simultaneously in TSP utilizes GPU's task-level parallelism, and the update process of pheromone trails data actively exploits data parallelism by 32x32 thread blocks. In particular, through simultaneous memory access of multiple threads, the coalesced accesses on continuous memory addresses and concurrent accesses on shared memory are supported. This experiment used 127 to 1002 city data provided by TSPLIB, and compared the performance of sequential and parallel algorithms by using Intel Core i9-9900K CPU and Nvidia Titan RTX system. Performance improvement by GPU parallelization shows speedup of about 10.13 to 11.37 times.

Citation status

* References for papers published after 2022 are currently being built.

This paper was written with support from the National Research Foundation of Korea.