Optimization of GPU-based Sparse Matrix Multiplication

Abstract

희소행렬 곱셈은 희소 네트워크 데이터를 분석하고 행렬을 기반으로 중요한 정보를 추출하는데 널리 사용된다. 행렬곱셈 연산이 데이터 병렬성을 갖고 있기 때문에 CUDA 및 OpenCL과 같은 데이터 병렬 프로그래밍 플랫폼을 이용해 GPU를 이용해 연산을 가속하려는 많은 시도가 있었다. cuSPARSE 및 CUSP를 포함한 여러 행렬곱셈 방식은 쓰레드 간 로드 밸런싱 문제와 병합 프로세스의 높은 메모리 경합으로 인해 GPU 리소스를 완전히 활용하지 못하는 경우가 많다. 이러한 과제를 해결하기 위해 본 논문에서는 Block Reorganizer라는 새로운 최적화 단계를 제안한다. Block Reorganizer는 GPU 내 연산장치에 할당되는 작업량을 조절하고 병합 프로세스에서 발생하는 메모리 트랜잭션량을 줄여 메모리 경합을 완하한다. 이를 위해 먼저 각 쓰레드 블록의 실제 작업량을 계산 후 블록의 특성에 따라 쓰레드 블록 최적화를 수행한다. 1) 작업량이 과적된 쓰레드 블록을 여러 개의 작은 쓰레드 블록으로 변환하기 위한 B-Splitting. 2) 여러개의 작은 쓰레드 블록을 하나의 블록으로 압축하는 B-Gathering. 병합 과정에서 B-Limitting을 수행하여 각 컴퓨팅 장치내 할당 가능한 쓰레드 블록의 수를 제한하여 전체 성능을 향상시킨다. 실험 결과, 제안 방안은 NVIDIA Tittan Xp GPU에서 기존 방안에 비해 평균 1.43배의 성능 향상을 보인다.