A GPU-Based Complex Graph Query Processing System Based on Grid Partitioning for Trillion-Scale Graphs

Abstract

Graphs are continually growing in size, and processing complex queries, such as multi-hop pattern queries, on them is becoming increasingly important. Although GPUs have received significant attention recently, there is still a notable shortage of efficient GPU-based out-of-memory methods for handling these queries. Three key issues arise when processing multi-hop queries on large-scale graphs using GPUs: the need for an efficient graph format, effective scheduling of accesses to graph partitions on storage, and dynamic buffer management on both the host and GPUs. To address these issues, we first propose the High-density Graph Representation Format (HGF), a GPU-friendly and space-efficient graph storage format that enables scalable graph partitioning and efficient access patterns on both CPUs and GPUs. Based on HGF, we present GFlux, an efficient GPU-based out-of-memory multi-hop query processing framework. GFlux introduces GTask, a novel abstraction that represents the data access and dependency structure of complex multi-hop queries, allowing them to be executed efficiently and in parallel on GPUs. Additionally, we design a GPU-based multi-hop query execution mechanism and a dynamic buffer management strategy, both built on GTasks. Through extensive experiments, we have demonstrated that GFlux significantly improves both the speed and scalability compared to existing state-of-the-art methods.|그래프 데이터의 규모가 지속적으로 증가함에 따라, 멀티홉 (multi-hop) 패턴 질의와 같은 복잡한 질의를 효율적으로 처리하는 기술의 중요성이 커지고 있다. 최근 GPU 활용이 활발해졌지만, 이러한 질의를 위한 GPU 기반 out-of-memory 처리 방식은 여전히 부족하다. 대규모 그래프에서 멀티홉 질의를 GPU로 처리하려면, 효율적인 그래프 저장 형식, 저장장치 기반의 파티션 접근 스케줄링, 그리고 호스트와 GPU 간의 동적 버퍼 관리가 필수적이다. 이러한 문제를 해결하기 위해, GPU 친화적 (GPU-aware)이면서 공간 효율성을 갖춘 그래프 저장 형식인 High-density Graph Representation Format (HGF)를 제안하였다. HGF는 CPU와 GPU 모두에서 확장 가능한 그래프 파티셔닝과 효율적인 접근 패턴을 지원한다. 이를 기반으로, GPU 기반 out-of-memory 멀티홉 질의 처리 프레임워크인 GFlux를 제안하였다. GFlux는 복잡한 멀티홉 질의의 데이터 접근과 실행 의존성을 추상화하는 GTask 모델을 도입하고, 이를 활용하여 GPU 상에서 질의를 병렬적이고 효율적으로 처리한다. 또한, GTask 기반의 멀티홉 질의 실행 방식과 동적 버퍼 관리 기법을 함께 제안하여 전체 처리 성능을 향상시킨다. 다양한 실험을 통해, GFlux는 기존 state-of-the-art 기법들과 비교하여 처리 속도뿐만 아니라 확장성과 공간 효율성 측면에서도 우수한 성능을 입증하였다.