Many high-performance computing applications use sparse matrices with various operations and kernels. These applications use GPUs for parallel acceleration. However, these kernels suffer from memory I/O bottleneck, which makes it hard to utilize the total performance of GPU. It is possible to classify these memory-intensive kernels into these four categories: sparse matrix general multiplication (SpGEMM), vector-vector operations, sparse matrix-vector multiplication (SpMV), and sparse triangular matrix-vector solve (SpTRSV). Therefore, this dissertation proposes a SpGEMM accelerator architecture and a processing-in-memory (PIM) architecture for the others, which results in total hardware acceleration of sparse matrix applications.
Recent SpGEMM accelerator designs advocated outer product processing, which reads sequentially and minimizes the memory read traffic. However, this study first identifies the memory bloating problem of the outer product designs, which can cause availability problems. Therefore, this study revisits an alternative inner product approach and proposes a new accelerator design called InnerSP to overcome the memory bloating problem. This study shows that row-wise inner product algorithms have a locality and exploits with a modest on-chip cache. The row-wise inner product relies on the on-chip aggregation of intermediate products with the fixed-size on-chip hash table. To deal with the variance in the size of output rows, InnerSP proposes a pre-scanning technique for row splitting and merging.
For the rest of the kernels, this dissertation suggests a processing-in-memory architecture pSyncPIM to expand the compute capability of the commercial PIMs to support sparse matrix operations. These commercial PIM products execute all memory banks to access the same memory bank rows and operate simultaneously. However, these approaches could not be applied directly to sparse matrix kernels due to the uneven distribution of sparse matrices. In addition, the current DRAM interface does not allow the generation of memory commands inside the memory chip itself. Therefore, this dissertation proposes a partially synchronous execution technique that follows the lock-step manner execution of all memory banks. Still, it allows the execution of each bank to diverge in its status. On top of that, this dissertation proposes a mapping scheme of SpMV and SpTRSV kernels.
여러 고성능 컴퓨팅 분야의 애플리케이션들은 희소 행렬들을 다루며, 이러한 희소 행렬들을 다루는 다양한 연산들과 커널들을 사용한다. 이러한 애플리케이션들은 GPU에서 병렬 가속으로 처리를 하고 있으나, 대부분의 커널들이 GPU 연산보다는 메모리 입출력에서 병목 현상이 발생하여 GPU의 성능을 전부 활용하기 어려운 문제가 있다. 이러한 메모리 병목 커널은 크게 희소 행렬 간 곱셈, 벡터-벡터 연산, 희소 행렬-벡터 곱셈, 희소 삼각 행렬-벡터 풀이로 구분할 수 있다. 따라서 본 논문에서는 희소 행렬 간 곱셈 가속을 위한 InnerSP 가속기 아키텍처를, 그 외 나머지 세 종류의 연산에 대해서는 pSyncPIM 프로세싱-인-메모리 아키텍처를 제안하여, 희소 행렬 애플리케이션 전반에 대한 하드웨어 가속을 지원하고자 한다.
희소 행렬 간 곱셈을 위한 가속기 아키텍처는 많은 기존 연구들에서 벡터 외적 기반 알고리즘으로 접근하여, 입력 행렬을 연속적으로 읽으면서 횟수를 최소화하는 형태로 메모리 접근을 최적화하였다. 하지만 본 연구에서는 외적 알고리즘이 상당한 추가 메모리 소모를 불러일으켜, 가용성에 문제를 일으킬 수 있음을 보인다. 이러한 메모리 가용성 문제를 해결하기 위해, 행 단위 내적 알고리즘을 사용하는 InnerSP 가속기 아키텍처를 제안한다. 내적 알고리즘에서 어느 정도의 데이터 국소성이 있음을 보이고 이를 InnerSP 내부의 캐시로 활용한다. 알고리즘에서의 행 단위 누적을 위한 하기 위하여 해시 테이블을 도입하였으며, 다양한 출력 행렬의 행 길이에 대응하기 위하여 선-스캔 기법으로 다양한 길이의 행들을 자르고 붙이는 기법을 제안한다.
희소 행렬 간 곱셈을 제외한 나머지 메모리 병목 연산을 처리하기 위하여 pSyncPIM 프로세싱-인-메모리 아키텍처를 제안하여, 기존의 밀집 행렬과 벡터 간 연산만 지원하던 산업 현장의 프로세싱-인-메모리 제품의 기능을 확장하고자 한다. 프로세싱-인-메모리 제품들은 최대화된 대역폭을 위하여 모든 메모리 뱅크들이 같은 타이밍에 같은 행에 대하여 접근을 하고 연산을 수행하는 특징이 있다. 이러한 특징은 근본적으로 불균등한 작업 분배를 할 수 밖에 없는 희소 행렬 커널에 그대로 적용하기 어렵다. 또한 현재의 DRAM 인터페이스는 메모리 칩에서 컨트롤러의 명령 없이 자체적으로 메모리 명령을 생성해서 처리하는 방식을 지원하지 않는다. 따라서 본 연구에서는 모든 메모리 뱅크의 동기화된 실행 방식을 유지하면서 각 메모리 뱅크가 상황에 맞게 동적으로 실행 유무를 결정하는 부분 동기화 방식을 제안한다. 그리고 이러한 방식을 희소 행렬-벡터 커널과 희소 삼각 행렬-벡터 풀이 커널에 적용하는 방법을 제안하고자 한다.
