SpMM - 1 : Introduction

Sparse Matrix Multiplication 

Matrix multiplication은 우리가 흔히 아는 다음 그림과 같은 행렬곱을 의미한다.

 

Matrix multiplication. https://en.wikipedia.org/wiki/Matrix_multiplication

 

Matrix multiplication(MM) 연산은 기존의 선형대수 관련 문제 계산, 3D graphics 뿐만 아니라 딥러닝에서도 활발하게 사용되고 있는 중요한 연산이다. 특히 딥러닝에서 convolution layer나 fully connect layer 연산을 MM 연산으로 변환하여 계산하고 있으며, 매우 많은 성능상의 이점을 보이고 있다.

MM 연산은 operand인 행렬이 dense인지, sparse 인지에 따라 dense matrix multiplication 또는 sparse matrix multiplication으로 나뉜다. 

 

 

Dense vs. Sparse

Sparse matrix(희소행렬)는 행렬의 값 대부분이 0인 행렬을 의미하며, 그것의 반대되는 개념이 dense matrix(밀집행렬)이다[1]. 행렬의 값의 몇 퍼센트 이상이 0이 되어야 sparse matrix라는 구체적인 정의는 없다. M*N 크기 행렬에서 0인 행렬의 값의 개수가 a개일 때, 얼마나 sparse한지를 측정하는 척도로 sparsity가 제안되며 다음과 같다. 

 

 

Dense, sparse 행렬 모두, 우리가 일반적으로 사용하는 MM 연산을 통해 결과를 쉽게 얻을 수 있다. M*K 행렬과 K*N 행렬의 MM 연산을 할 시, 총 M*K*N번의 스칼라 곱셈 연산과 스칼라 덧셈 연산이 필요하다.

 

 

 

Sparse matrix multiplication이 필요한 이유

Sparse 행렬의 경우 많은 연산의 결과가 대부분이 0일 것이다. 만약 100*100 대각행렬끼리의 행렬곱 연산 시, 일반적으로 사용하는 MM 연산을 이용할 시 100*100*100번의 스칼라 곱셈 연산이 필요하다. 하지만 0이 아닌 값만을 얻기 위해서는 100번의 스칼라 곱셈만 하면 되므로 (대각성분끼리의 곱셈만 하면 됨) 100만번의 곱셈 연산이 100번의 곱셈 연산으로 줄어들 수 있다. 이처럼 sparse matrix의 경우 일반적인 MM 연산이 아닌 새로운 알고리즘을 통해 빠르게 연산할 수 있을 가능성이 있다.

 

대각행렬끼리의 matrix multiplication. 대각성분만 알면 된다.

 

또한 단순히 연산의 개수만 줄어드는 것이 아니라, 메모리 사용량 (memory footprint)도 줄일 수 있다. 100*100 대각행렬 2개의 행렬곱을 위해서는 총 100*100 + 100*100 + 100*100 개의 데이터를 저장해야 한다. 만약 100개의 대각성분만 저장한다면 100 + 100 + 100개의 데이터만 저장하여도 된다. 추후 나머지는 0이라는 정보를 알고 있기에 300개의 데이터만 있어도 행렬의 전체 모습을 복원할 수 있다.

 

 

 

 

Reference

1. https://en.wikipedia.org/wiki/Sparse_matrix