Efficient Dynamic Graph Processing Based on GPU Accelerated Scheduling and Operation Reduction

최근 대용량 동적 그래프를 효율적으로 처리하기 위해 GPU를 활용하는 연구가 활발히 진행되고 있으며, 동적 그래프 처리 시 같은 데이터가 반복적으로 전송되고 처리되는 문제가 발생하고 있다. 본 논문에서는 메모리가 제한된 GPU 환경에서 대규모 동적 그래프를 효율적으로 처리하기 위한 동적 스케줄링 방법과 연산 축소 방법을 제안한다. 동적 스케줄링 방법은 동적 그래프를 분할하여 각 파티션을 활성 정점과 예비 활성 정점을 고려한 스케줄링 방식으로 GPU에 배치함으로써 처리 성능을 극대화한다. 또한, 그래프의 변화 양상을 반영하기 위해 스냅샷을 활용한다. 연산 축소 방법은 스냅샷을 통해 동적 그래프에서 중복된 간선 및 정점의 변경을 감지하여 불필요한 연산을 줄임으로써 GPU의 연산량과 데이터 전송 비용을 최소화하는 기법이다. 이를 통해 동일한 간선이나 정점에 대한 중복 연산을 방지하여 성능을 향상시킨다. 다양한 성능 평가 결과 기존 정적 그래프 처리 기법 대비 평균 280%, 기존 동적 그래프 처리 기법 대비 평균 108%의 성능 향상을 확인하였다.