최근 그래프의 규모와 복잡성은 지속해서 증가하는 추세이다. 대규모 그래프는 계산 및 저장 공간 비용이 매우 높기 때문에 기존 CPU를 활용한 연구 기법을 그대로 활용하기엔 적합하지 않다. 이러한 이유로 GPU와 같은 고성능 컴퓨팅 자원을 활용한 처리 기법은 계산 비용 관점에서 중요한 연구 주제이며 이를 효과적으로 이용하기 위해서는 GPU의 구조적 특징을 고려한 효율적인 그래프 처리 기법이 필요하다. GPU는 CPU와 비교하여 뛰어난 계산 성능을 갖고 있으나 비교적 적은 메모리 공간을 갖고 있으므로 이를 효과적으로 이용하기 위해서는 그래프를 나누어 처리해야 한다. 본 논문은 GPU를 활용하여 효과적인 그래프 분할을 수행하기 위한 스트리밍 클러스터링 기반의 그래프 분할 방법을 제안한다. 제안하는 기법은 그래프를 GPU의 메모리에서 처리할 수 있는 수준으로 압축하여 전송하고 GPU는 그래프 분할에 필요한 정보를 구하여 호스트에 전달한다. 마지막으로 호스트에서는 해당 정보를 기반으로 그래프 분할한다. 결과적으로 제안하는 기법은 메모리 효율을 높이고 GPU의 장점을 최대화하여 효율적이고 정확한 그래프 분할을 수행한다. 다양한 다른 최신 기법과 실험을 통해 본 논문의 우수성을 입증한다. 실험 결과, 기존 기법이 처리할 수 없는 그래프를 GPU에서 처리했으며 전체적인 그래프 분할 품질이 우수함을 확인했다.
The increasing size and complexity of modern graphs are quickly surpassing the capabilities of traditional CPU-based methods, owing to their significant computational and storage demands. This situation necessitates high-performance computing solutions, such as GPUs. Although GPUs possess superior processing power, their limited memory capacity remains a challenge. To effectively utilize GPUs for graph processing, schemes that align with their architectural features are crucial. In this paper, we propose the efficient large-scale graph partitioning schemes for GPU environments. Our approach involves compressing the graph to a size manageable by GPU memory, which facilitates processing, and then transmitting the partitioning-relevant information back to the host system for final partitioning. This scheme enhances memory efficiency and leverages the computational advantages of GPUs, resulting in a more effective and precise graph partitioning process. The efficacy of our approach is further demonstrated through comparative experiments with other contemporary GPU-based research. The experimental results demonstrate that the graph, which was previously unprocessable by conventional schemes, has been successfully handled on a GPU, and an overall superior quality of graph partitioning has been observed.