Sparse matrix is widely used in many important applications such as graph analysis, machine learning, and scientific simulations. Among the kernels using sparse matrix, generalized sparse matrix-sparse matrix multiplication (SpGEMM) is one of the key computational primitives and it is known to be inefficient on general-purpose processors such as CPUs and GPUs by showing resource under-utilization. SpGEMM’s importance and its inefficiency on general-purpose processors result in the advent of accelerators specialized for SpGEMM. Among several dataflows for matrix multiplication, this thesis focuses on the row-wise product and the column-wise product. This thesis found that these two dataflows can be exploited on the same accelerator design and these two dataflows require the different number of memory accesses for the same matrix multiplication. By selectively exploiting two dataflows based on the densities of input matrices, this thesis shows that appropriate dataflow can achieve up to 9.6x performance improvement of SpGEMM by reducing the required memory accesses compared to the inadequate dataflow.
희소 행렬은 그래프 처리, 머신 러닝, 그리고 과학적 시뮬레이션등 광범위하게 활용되고 있다. 희소 행렬을 활용하는 연산 중, 희소 행렬 곱셈은 핵심적인 연산으로, 범용 프로세서에서는 연산 자원을 제대로 활용하지 못하고 낮은 성능을 가진다. 희소 행렬 곱셈의 중요성과 범용 프로세서에서의 낮은 성능으로 인해, 희소 행렬 곱셈을 위한 가속기가 등장하고 있다. 본 학위 논문은, 행렬의 곱셈을 위한 여러 데이터 흐름 중에서 row-wise 곱셈과 column-wise 곱셈에 초점을 맞추어, 이 두 데이터 흐름의 곱셈이 같은 가속기 구조에서 활용될 수 있으며, 이 두 데이터 흐름은 같은 행렬의 곱셈 연산을 수행함에 있어서 다른 메모리 접근 수를 요구할 수 있다는 점을 발견하였다. 본 학위논문은 입력 행렬의 밀도를 고려하여, 선택적으로 더 적은 메모리 접근을 요구하는 적합한 데이터 흐름을 활용하면, 부적합한 데이터 흐름 대비, 최대 9.6배까지 희소 행렬 곱셈의 성능이 좋아짐을 확인하였다.
