[논문]GPU-based Parallel Ant Colony System for Traveling Salesman Problem

Rhee, Yunseok

doi:10.9708/jksci.2022.27.02.001

GPU-based Parallel Ant Colony System for Traveling Salesman Problem 원문보기

韓國컴퓨터情報學會論文誌 = Journal of the Korea Society of Computer and Information, v.27 no.2, 2022년, pp.1 - 8

Rhee, Yunseok (Division of Computer Engineering, Hankuk University of Foreign Studies)

초록
AI-Helper

본 논문에서는 개미 집단 시스템(ant colony system)을 통한 순회 외판원 문제(traveling salesman problem)를 효과적으로 해결하기 위해 GPU 기반 병렬 알고리즘을 설계 구현하였다. TSP에서 동시에 수백 또는 수천의 탐색 여정(tour)을 생성하는 반복 과정을 GPU의 작업 병렬성을 활용하여 처리성능을 개선하고, 페로몬 자취 데이터의 업데이트 과정은 32x32의 쓰레드 블럭을 사용하여 데이터 병렬성을 적극 활용하였다. 특히 다중 쓰레드의 메모리 동시 접근을 통해 연속 메모리공간의 병합 접근 효과와 공유 메모리의 동시 접근을 지원하였다. 본 실험은 TSPLIB에서 제공되는 127개부터 1002개에 이르는 도시 데이터를 사용하였고, Intel Core i9-9900K CPU와 Nvidia Titan RTX 시스템을 사용하여 순차 알고리즘과 병렬 알고리즘의 성능을 비교하였다. GPU 병렬화에 의한 성능 향상은 약 10.13~11.37배의 성능 개선 효과를 보였다.

Abstract ▼ AI-Helper

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.

주제어

표/그림 (9)

그림 Fig. 1. ACS algorithm flow for solving TSP
그림 Fig. 2. Stochastic selection for next visiting city
그림 Fig. 3. Coalesced memory access in CUDA
그림 Fig. 4. Bank conflict-free array example
그림 Fig. 5. selection process example for a next visiting city
그림 Fig. 6. Computation results with iterations
그림 Fig. 7. Results trend with the number of ants
표 Table 1. System Specification for Experiments
표 Table 2. Parallelization Performance [ms]

AI 본문요약
AI-Helper

가설 설정

Step 3은 페로몬의 양을 전체적으로 업데이트하는 단계이다. ACS에서는 이미 경로 상에 배출된 페로몬은 시간이 지남에 따라 증발하여 그 양이 다음과 같이 점차 약화된다고가정한다. 이때 는 실험에 의해 결정된 증발율 상수이다.
한편, 개미가 지나간 경로에는 페로몬이 증가되는데 그 양의 개미가 이동한 거리에 반비례한다고 가정한다. 따라서, 페로몬의 양이 업데이트되는 식은 다음과 같이 결정된다.

제안 방법

그럼에도, 여전히 TSP 문제 자체는 물론 ACS가 갖는 막대한 계산량으로 인해 이의 효과적인 병렬화는 필수적이다. 본 논문에서는 GPU가 제공하는 데이터 병렬성을 최대한 활용한 알고리즘을 설계하고, 이를 Nvidia GPU 상에서 구현하고 실험하였다.
본 논문에서는 Nvidia에서 제공하는 CUDA(compute unified device architecture) 프레임워크를 사용해 병렬프로그램을 개발했다. CUDA는 다수의 쓰레드들의 집합인쓰레드 블록(thread block)의 개념을 지원하는데, 한 블럭은 한 개의 SM에 배치되고, 한 개의 쓰레드는 그 안에서 하나의 코어(core)에서 실행된다.
따라서 GPU가 제공하는 메모리 계층 구조를 활용하여 자주 사용되는 전역 메모리 데이터를 공유 메모리에 복사하여 캐싱(caching) 효과를 적극 활용하고, 2장에서 설명한 전역 메모리의 병합 접근과 공유 메모리의 뱅크 충돌(bank conflict)을 줄임으로써 알고리즘의 수행 속도를 높이는 방법이다. 본 연구에서 제안하는 알고리즘은 여정 초기화(tour initialization), 방문적합도 계산(visit fitness calculation), 여정 구성(tour construction), 여정 정리(wrap-up tour), 페로몬 업데이트(pheromone update)의 5개 커널로 구성되고, 이 커널들을 일정 횟수 동안 반복 실행함으로써 TSP의 최단 경로를 계속 업데이트한다.
본 절에서는 GPU 기반 병렬 알고리즘의 성능을 살펴보기 위해 우선 본래 ACS 알고리즘의 CPU 버전에 대한 성능을 살펴보고, 개미의 수에 따른 실행 시간과 구해진 해답의 품질을 살펴본다. 그리고, GPU 실행 시간에서 각 부분이 차지하는 실행 시간의 비율을 분석한다.

대상 데이터

개미의 수, 즉 병렬처리 쓰레드의 수에 따른 반복실행 결과와 그 품질을 좀더 살펴보기 위해 적당한 데이터 크기를 갖는 ali535 데이터를 대상으로 개미의 수를 260, 535, 1050개로 각각 변화시키며 실험을 수행하였다.

데이터처리

현재 실험에서는 반복 횟수를 30회로 한정하고, 개미의 수는 도시의 수와 동일하게 생성한 상태에서 각 횟수마다 계산된 최단경로(best-path-so-far)를 살펴보았다. data 에 따라 약간의 차이는 있었지만 그림 6에 보이는 바와 같이 대개 10회 내외에서 결과가 수렴하는 것으로 나타났고, bier127의 경우에는 1회의 결과가 최종 결과로 연결되었다.

성능/효과

공개된 주요 TSP 데이터를 대상으로 실험한 결과, 단일 CPU에서 동작하는 알고리즘에 비해 GPU 병렬 알고리즘은 약 10.13~11.37배의 성능 개선 효과를 보였다. 다만, bier127와 같이 비교적 작은 규모의 데이터에 대해 4.
ACS는 메타 휴리스틱을 사용해 TSP와 같이 계산 복잡도가 높은 문제의 근사 최적해(near optimal solution)를널리 활용되며, 특히 지속적으로 네트워크의 상태가 변화하는 동적인 TSP 환경에 ACS가 매우 효과적이어서 다양한 응용분야의 적용이 기대된다. 그럼에도, 여전히 TSP 문제 자체는 물론 ACS가 갖는 막대한 계산량으로 인해 이의 효과적인 병렬화는 필수적이다. 본 논문에서는 GPU가 제공하는 데이터 병렬성을 최대한 활용한 알고리즘을 설계하고, 이를 Nvidia GPU 상에서 구현하고 실험하였다.
37배의 성능 개선 효과를 보였다. 다만, bier127와 같이 비교적 작은 규모의 데이터에 대해 4.82 배의 비교적 낮은 성능향상을 보인 것은 여정 생성 과정에서 다음 방문 도시를 선정하는 순차적 과정이 차지하는 비중이 상대적으로 높았던 것으로 보인다.
특히 개미의 수(병렬처리 성능) 가 일정 수준 이상으로 제공되어야 고품질의 결과를 보장받을 수 있다는 점은 CPU 기반으로 ACS를 구현하는 것이 성능 면에서 한계에 다다랐음을 보여준다. 더욱이 수백 또는 수천 개의 데이터에 대해 ACS 알고리즘을 수행할 때, CPU에서 개미의 수를 그 수준으로 생성, 활용한다는 것은 그 수 만큼의 반복 연산을 일으켜 결국 GPU 기반 병렬 알고리즘과 성능 차이는 더욱 크게 벌어질 것으로 예상된다.
실험을 통해 일정한 품질(최적값 대비 일정 오차 이내) 의 결과를 얻기 위해 ACS 알고리즘은 적어도 데이터 크기에 상응하는 개미와 일정 횟수 이상의 반복 계산이 절대적임을 확인했다. 특히 개미의 수(병렬처리 성능)가 일정 수준 이상으로 제공되어야 고품질의 결과를 보장받을 수 있다는 점은 CPU 기반으로 ACS를 구현하는 것이 성능 면에서 한계에 다다랐음을 보여준다.
위의 결과를 볼 때, 일정한 품질(최적값 대비 일정 오차 이내)의 결과를 얻기 위해 ACS 알고리즘은 적어도 데이터 크기에 상응하는 개미와 일정 횟수 이상의 반복 계산이 절대적임을 확인할 수 있다. 특히 개미의 수(병렬처리 성능) 가 일정 수준 이상으로 제공되어야 고품질의 결과를 보장받을 수 있다는 점은 CPU 기반으로 ACS를 구현하는 것이 성능 면에서 한계에 다다랐음을 보여준다.
특히 대규모 TSP 맵 데이터에서 다음 방문 도시의 확률적 선택 적합도를 계산하거나 개미들의 움직임에 따른 페로몬의 자취를 업데이트하는 과정은 GPU의 데이터 병렬구조에 아주 적합한 계산과정으로 성능 개선에 주요한 부분이었다. 다만, 개미들이 매번 다음 여정을 생성하는 과정은 순차적 확률 과정의 연속으로 병렬화에 한계가 있었다.

후속연구

ACS는 메타 휴리스틱을 사용해 TSP와 같이 계산 복잡도가 높은 문제의 근사 최적해(near optimal solution)를널리 활용되며, 특히 지속적으로 네트워크의 상태가 변화하는 동적인 TSP 환경에 ACS가 매우 효과적이어서 다양한 응용분야의 적용이 기대된다. 그럼에도, 여전히 TSP 문제 자체는 물론 ACS가 갖는 막대한 계산량으로 인해 이의 효과적인 병렬화는 필수적이다.
특히 대규모 TSP 맵 데이터에서 다음 방문 도시의 확률적 선택 적합도를 계산하거나 개미들의 움직임에 따른 페로몬의 자취를 업데이트하는 과정은 GPU의 데이터 병렬구조에 아주 적합한 계산과정으로 성능 개선에 주요한 부분이었다. 다만, 개미들이 매번 다음 여정을 생성하는 과정은 순차적 확률 과정의 연속으로 병렬화에 한계가 있었다. 따라서, 향후 연구에서는 이 부분의 알고리즘 속성을 세분화하고 더 적극적으로 병렬화 방법을 적용할 필요가 있다.
다만, 개미들이 매번 다음 여정을 생성하는 과정은 순차적 확률 과정의 연속으로 병렬화에 한계가 있었다. 따라서, 향후 연구에서는 이 부분의 알고리즘 속성을 세분화하고 더 적극적으로 병렬화 방법을 적용할 필요가 있다.
위의 결과를 볼 때, 일정한 품질(최적값 대비 일정 오차 이내)의 결과를 얻기 위해 ACS 알고리즘은 적어도 데이터 크기에 상응하는 개미와 일정 횟수 이상의 반복 계산이 절대적임을 확인할 수 있다. 특히 개미의 수(병렬처리 성능) 가 일정 수준 이상으로 제공되어야 고품질의 결과를 보장받을 수 있다는 점은 CPU 기반으로 ACS를 구현하는 것이 성능 면에서 한계에 다다랐음을 보여준다. 더욱이 수백 또는 수천 개의 데이터에 대해 ACS 알고리즘을 수행할 때, CPU에서 개미의 수를 그 수준으로 생성, 활용한다는 것은 그 수 만큼의 반복 연산을 일으켜 결국 GPU 기반 병렬 알고리즘과 성능 차이는 더욱 크게 벌어질 것으로 예상된다.

참고문헌 (16)

T.H. Cormen, C.E. Leiserson, R.L. Rivest, and C. Stein, "Introduction to Algorithms", 2nd ed., The MIT Press, 2001.
M. Dorigo, V. Maniezzo, and A. Colorni, "The ant system: Optimization by a colony of cooperating agents", IEEE Transactions on Systems, Man, and Cybernetics-Part B 26, pp. 29-41, Feb. 1996.

상세보기
Junqi Yu, Ruolin Li, Zengxi Feng, Anjun Zhao, Zirui Yu, Ziyan Ye, Junfeng Wang, "A Novel Parallel Ant Colony Optimization Algorithm for Warehouse Path Planning", Journal of Control Science and Engineering, Hindawi, pp. 1687-5249, vol. 2020, Aug. 2020.
J. Kanda, A. D. Carvalho, E. Hruschka, "Meta-learning to select the best meta-heuristic for the Traveling Salesman Problem: A comparison of meta-features", Neurocomputing, Vol. 205(C), pp. 393-406. Sep. 2016.

상세보기
X. Chen, Y. Zhou, Z. Tang, "A hybrid algorithm combining glowworm swarm optimization and complete 2-opt algorithm for spherical traveling salesman problems", Applied Soft Computing, Vol. 58, pp. 104-114, Apr. 2017.

상세보기
C. Groba, A. Sartal, "Solving the dynamic traveling salesman problem using a genetic algorithm with trajectory prediction: an application to fish aggregating devices," Computers & Operations Research, pp. 22-32, Apr. 2015.
Mavrovouniotis, M., Yang, S., Van, M., Li, C., Polycarpou, M., "Ant Colony Optimization Algorithms for Dynamic Optimization: A Case Study of the Dynamic Travelling Salesperson Problem", IEEE COMPUTATIONAL INTELLIGENCE MAGAZINE, 15(1), 52-63, Feb. 2020.

상세보기
M. Mavrovouniotis, F. M. Muller, and S. Yang, "Ant colony optimization with local search for dynamic traveling salesman problems," IEEE Trans. Cybern., vol. 47, no. 7, pp. 1743-1756, July 2017.

상세보기
M. Manfrin, M. Birattari, T. Stutzle, and M. Dorigo, "Parallel Ant Colony Optimization for the Traveling Salesman Problem", in Proc. of5th International Workshop on Ant Colony Optimization and Swarm Intelligence, Vol. LNCS 4150, Springer-Verlag, pp. 224-234, Sep. 2006.
P. Delisle, M. Krahecki, M. Gravel, and C. Gagne, "Parallel implementation of an ant colony optimization metaheuristic with OpenMP", in Proc. of the 3rd European Workshop on OpenMP, pp. 1-7, Jan. 2001.
Breno A. de Melo Menezes, Nina Herrmann, Herbert Kuchen & Fernando Buarque de Lima Neto, "High-Level Parallel Ant Colony Optimization with Algorithmic Skeletons", International Journal of Parallel Programming, vol. 49, pp. 776-801, Dec. 2021.

상세보기
A. Del'evacq, P. Delisle, M. Gravel, and M. Krahecki, "Parallel Ant Colony Optimization on Graphics Processing Units", Journal of Parallel and Distributed Computing, vol. 73, no. 1, pp 52-61, Jan. 2013.

상세보기
Menezes, B.A., Kuchen, H., Neto, and de Lima Neto, "Parallelization strategies for GPU-based ant colony optimization solving the traveling salesman problem", In Proc. of IEEE Congress on Evolutionary Computation, pp. 3094-3101, June 2019.
Yi Zhou, Fazhi He, Neng Hou, Yimin Qiu, "Parallel ant colony optimization on multi-core SIMD CPUs", Future Generation Computer Systems, vol. 79, part. 2, pp. 473-487, Feb. 2018,

상세보기
Stutzle Thomas. Ant colony optimization - http://iridia.ulb.ac.be/~mdorigo/ACO/aco-code/public-software.html. [accessed: Dec. 05, 2021]
TSPLIB, "Symmetric traveling salesman problem", http://elib.zib.de/pub/mp-testdata/tsp/tsplib/tsplib.html. [accessed: Nov. 22, 2021]

표제어: PCR

동의어: Packet Collision Rate

용어 설명 출처 목록 (6)

용어 설명: PCR은 세균 특이성이 있는 primer를 이용하여 적은 수의 세균이 있을지라도 쉽게 검출할 수 있는 유용한 방법이며, 이를 이용하여 구강 내 치면세균막이나 타액에서 직접 세균을 검출할 수 있게 되었다[8].

내보내기 구분	파일저장 인쇄 메일전송
구성항목	기본정보 상세정보 관리번호, 논문명, 저널/프로시딩명, 저자 , 발행년, 권, 호, 시작페이지, 끝페이지, 발행기관 관리번호, 논문명, 대등논문명, 저자 , 저널/프로시딩명, 발행기관, 발행년, 발행언어, 권, 호, 시작페이지, 끝페이지, ISBN, ISSN, 주제분야, 키워드, 초록(한글), 초록(영문), 저자(소속기관)
저장형식	Text(ASCII format) Excel format RefWorks Direct Export RIS format (for Reference Manager, ProCite, EndNote), Scholar's Aids, Mendeley
메일정보	받는사람 (필수) @ 보내는사람 (선택) @ 제목 내용 KISTI 검색결과 이메일 서비스
안내	총 건의 자료가 검색되었습니다. 다운받으실 자료의 인덱스를 입력하세요. (1-10,000) 검색결과의 순서대로 최대 10,000건 까지 다운로드가 가능합니다. 데이타가 많을 경우 속도가 느려질 수 있습니다.(최대 2~3분 소요) 다운로드 파일은 UTF-8 형태로 저장됩니다. 파일의 내용이 제대로 보이지 않을실 때는 웹브라우저 상단의 보기 -> 인코딩 -> 자동선택 여부를 확인하십시오. ~ Text(ASCII format) Excel format

연합인증