그래프 채색 알고리즘의 GPGPU 상 구현 및 최적화 (Implementation of Graph Coloring Algorithms on GPGPUs and Its Optimization)

서지정보

· 발행기관 : 한국정보과학회
· 수록지 정보 : 정보과학회 컴퓨팅의 실제 논문지 / 28권 / 12호 / 594 ~ 614페이지
· 저자명 : 윤인섭, 안형찬

초록

본 논문에서는 그래프 채색 알고리즘의 GPGPU상 구현을 최적화하는 새로운 기법으로서, 입력에 따라 최적의 그래프 표현방식을 선택하는 휴리스틱을 제시한다. 기존에 Alabandi et al.이 GPGPU에 적합한 그래프 채색 알고리즘을 제시한 바 있으나, 단일한 자료 구조만을 사용한다는 제한으로 인해 GPGPU의 최대 성능을 이끌어 내는 것에는 한계가 있었다. 본 논문에서는 GPGPU에 알맞은 복수의 자료 구조를 채택하고, 이로써 개선된 성능을 실험적으로 측정하였다. 실험은 공개 리파지터리들의 그래프를 벤치마크로 사용해 RTX 2060과 GTX 1050Ti에서 수행하였다. 이 결과를 바탕으로, 입력 그래프의 차수 등을 토대로 적합한 그래프 표현방식을 자동으로 선택해주는 휴리스틱을 개발하였고, 이는 기존 대비 평균 8.01%(RTX 2060)～10.43%(GTX 1050Ti)의 수행 속도 개선 효과를 나타내었다. 끝으로, 휴리스틱의 효과가 저조한 경우에 대한 개별 분석을 수행하였다.

영어초록

In this paper, we propose a new heuristic that optimizes implementations of graph coloring algorithms on GPGPUs by selecting efficient graph representations depending on the input graphs. Previously, Alabandi et al. gave a graph coloring algorithm suitable for GPGPU implementation; however, limitations due to its monolithic use of a single data structure restricted using the full power of GPGPUs. We adopted multiple graph representations that work better with GPGPUs and experimentally measured the resulting performance improvements. These experiments were conducted on RTX 2060 and GTX 1050Ti using graphs from public repositories as the benchmark set. Based on the results, we devised a heuristic that considers the input graph's properties, such as its degree, to automatically select the most suitable graph representation. This led to an average improvement of 8.01% (RTX 2060) - 10.43% (GTX 1050Ti) in running time compared to the previous algorithm. Lastly, we investigated individual cases for which the heuristic showed little improvement.

참고자료

· 없음