GPU에서의 규칙적인 그래프 처리

Abstract

현실세계의 그래프의 크기가 점점 커짐에따라서, 큰 그래프를 처리하는 것은 점 점 어려워지고 있다. GPU는 높은 병렬성과 메모리 대여폭으로 이러한 그래프를 처리하는데 큰 도움이 된다. 하지만, GPU의 메모리 크기와 현실세계 그래프의 불 규칙적인 특성들은 GPU의 성능향상에 문제점을 야기한다. 이전 논문들은 GPU 의 warp lane 활용률을 높이는 등 GPU의 자원이용률을 향상시켜 이러한 문제를 해결하였지만, 여전히 이전 논문들은 기존 그래프 자료구조의 한계점으로 인해서 높은 메모리 사용률과 낮은 GPU 자원이용률을 야기하고 있다. 본 연구는 불규칙한 그래프를 규칙적인 그래프로 변환하여 GPU를 고려한 규칙 화된 그래프 처리를 제안한다. 첫번째로 각각의 vertex들이 유사한 수의 edge를 가지게 하기 위하여 하나의 vertex를 여러 vertex로 만드는 과정을 거친다. 두번째 로, 동일한 수의 edge를 가진 vertex끼리 그룹을 묶어 GPU에서 각 쓰레드가 동일한 양의 일을 수행할 수 있도록한다. 또한, 각 그룹은 동일한 수의 edge를 가지게 되기 때문에 offset 데이터를 요구하지 않는다. 본 연구는 4개의 응용프로그램을 평가하 였고 기존의 연구대비 약 3.80배 빠른 실행시간을 보여준다.

As the size of real-world graphs continues to grow, processing large-scale graphs becomes more challenging. GPUs are promising platform for the graph processing due to their massive parallelism with high-bandwidth memory. How- ever, a limited memory space of GPUs and irregular degree distribution in real- world graphs prevent GPUs from achieving high performance. Prior works have been done to improve resource utilization such as warp lane utilization, but they still suffer from an excessive amount of memory usage and resource underutiliza- tion due to existing graph representation that are not tailored for GPUs. This thesis proposes regularized graph processing (RGP) by transforming irregular graph representation into regular graph representation that are con- sidered for GPUs. First, to make each vertex to have similar number of edges, each vertex is split into multiple virtual vertices by considering the architectural properties of GPUs such as warp size. Second, by aggregating vertices with same number of edges, each thread meets an opportunity to perfectly process same amount of jobs. In addition, since RGP groups vertices with same number of edges, regularized graph processing (RGP) does not require offsets to access edge list, reducing memory space requirement. This thesis evaluates with four popular graph applications, and achieves 3.80× speedup compared to existing state-of-the-art techniques.