희소 행렬-벡터 곱셈의 메모리 근접 병렬 처리를 위한 동적 분할 방법

Abstract

메모리 근접 처리 (Near-Memory Processing, NMP)는 가벼운 프로세싱 유닛을 메모리 근처에 배치하여 DRAM과 CPU 간의 데이터 전송량을 줄여 메모리 집약적인 연산의 속도를 높이기 위해 연구되어 왔다. 메모리 집약적인 커널의 대표적인 연산 중 하나인 희소 행렬-벡터 곱셈 (Sparse Matrix-Vector Multiplication, SpMV)은 그래프 분석, 과학 계산, 기계 학습 등 다양한 응용 분야에서 사용된다. 이전 연구들에선 SpMV를 가속하기 위해 희소 행렬과 벡터를 일정 크기로 분할하여 각 메모리 랭크에 저장하고 연결된 각 NMP 코어로 연산하는 병렬 메모리 근접 처리를 도입해왔다. 그러나 행렬의 다양한 분포로 인해 행렬을 정해진 개수로 분할하고 랭크에 분배하는 정적 분할은 각 NMP 코어에 불균등하게 데이터를 할당하는 부하 불균형을 일으킨다. 이를 해결하기 위해 희소행렬의 분포에 따라 추가 분할을 생성하고 각 랭크에 균등하게 분배하는 유동적인 분할 방법이 효과적일 수 있다. 본 논문은 희소 행렬에서 0이 아닌 값들의 분포를 분석하여 이를 세 가지 유형 (균등 분포, 비균등 분포 및 편향된 분포)으로 분류하고 각 분포에 따라 행렬을 분할하는 동적 분할 알고리즘 (Dynamic partitioning algorithm, DPA)을 제안한다. 우리가 제안하는 DPA는 정적 분할 방식과 비교하여 부하 불균형을 최대 73%정도 완화시키며, 정적 분할 방식을 사용하는 NMP 아키텍처에 대한 평균 속도 향상이 1.37배 (최대 1.84배) 달성하였다.|Near-memory processing (NMP), which places lightweight processing units near the DRAM memory, has been actively studied to speed up the execution of memory-intensive applications by reducing the amount of data traffic between the DRAM and the CPU. Sparse matrix-vector multiplication (SpMV) is a representative memory-bound kernel used in various applications such as graph analytics, scientific computing, and machine learning. There are prior works to accelerate SpMV by NMP employing a fixed partitioning scheme that hides random access of SpMV using a parallel NMP core. However, due to the various distributions of the matrix, the fixed partitioning of prior works causes a load imbalance in which a sparse matrix is unevenly allocated to processing units for NMP. To resolve this, dynamic partitioning methods to distribute matrices and vectors to the NMP processing units can be effective. In this paper, we propose a dynamic partitioning algorithm (DPA) that analyzes the distribution of non-zero elements in a sparse matrix to classify it into three types (even distribution, skewed distribution, and power-law distribution) and partitions the matrix according to each distribution. Our proposed distribution scheme alleviates load imbalance by up to 73% when compared to static distribution schemes, and such improvement achieves an average speed-up 1.37× (up to 1.84×) over the NMP architecture with static distribution schemes.