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