Ant Colony System은 계산 복잡도가 높은 조합 문제의 근사 최적해(near optimal solution)를 구하는 메타휴리스틱 기법이다. ACS가 갖는 막대한 계산량으로 인해 알고리즘의 효과적인 병렬화가 요구된다. 본 논문에서는 GPU가 제공하는 데이터 병렬성을 최대한 활용한 알고리즘을 제안하고, 이를 Traveling Salesman Problem에 적용하여 그 성능을 분석하였다. 특히 데이터 병렬성을 높이기 위해 병렬 쓰레드의 수와 쓰레드 블록의 수를 최대화하고, 이들의 연속 메모리 동시 접근 효과를 충분히 활용하였다. 또한 효과적인 TSP 해결을 위해 노드 간 거리를 이용한 근접성을 활용해 최적해를 탐색하는 과정을 제안한다. 본 실험은 Nvidia Titan RTX GPU와 Intel i9-9900K를 사용하여 구현하고 공개된 주요 TSPLIB 데이터를 대상으로 실험을 통해 성능 개선 효과를 확인했다.

*본 초록은 AI를 통해 원문을 번역한 내용입니다. 정확한 내용은 하기 원문에서 확인해주세요.