GPU에서의 희소행렬 곱셈(spGEMM)(1)

컴퓨터좀 만져본 사람중 행렬 곱셈 코드를 안짜본 사람은 없다.
나도 이제 깨우치는 중이지만 상당히 많은 데이터가 행렬의 형태를 띄고, 많은 문제들이 수학적으로 모델링 될 때 행렬곱셈 연산이 포함되기 때문에 행렬 곱셈은 컴퓨터공학도에게는 꽤 중요한 연산중 하나다.

희소행렬

최근 데이터가 커지고 네트워크가 희소해지면서 희소행렬에 대한 연산이 중요해지고 있는데 희소행렬은 일반적인 행렬과 달리 2D array의 형태로 저장되지 않는다.
이유는 메모리 효율성 때문이다. 행렬이 N x N 이라면 2D array의 형태로 저장하기 위해선 N²의 메모리공간이 필요하다.

Space complexity for 2D array : \(O(N^{2})\)

따라서 스케일이 크고 희소한 행렬은 크게 두가지 포맷을 이용한다.

COO format
각각의 원소는 (row, col, value)로 표현된다. 위 행렬을 coo 포맷으로 저장하면 다음과 같다.

typedef struct _coo {
    int row;
    int col;
    double val;
}coo;

typedef struct _spmat{
    coo* elem;
}spmat;

int main(){
    spmat A;
    A.elem = (double*)malloc(sizeof(double)*4);
    A.elem[0].row = 1; A.elem[0].col = 0; A.elem[0].val = 5;
    A.elem[1].row = 1; A.elem[1].col = 1; A.elem[1].val = 8;
    A.elem[2].row = 2; A.elem[2].col = 2; A.elem[2].val = 3;
    A.elem[3].row = 3; A.elem[3].col = 1; A.elem[3].val = 6;
    return 0;
}

희소행렬을 COO format으로 저장한다면 행렬원소의 개수가 E일 경우 필요한 메모리 공간은 대략 3E이다.

Space complexity for COO : \(O(3E)\)

COO 포맷은 굉장히 직관적이고 어느정도의 메모리 효율성을 보장하지만 실제 연산에서는 자주 이용되지 않는다. 이유는 각 행이나 열에 direct access 할 수가 없기 때문이다.
실제 연산에서는 CSR(Compressed Sparse Row), CSC(Compressed Sparse Column) 포맷을 이용한다.
Compressed sparse format 는 3개의 array(ptr, idx , val)로 이루어져 있다.
CSR 포맷을 예로 들어보면

ptr array는 각 행의 첫 원소의 위치를 저장하고
idx array는 각 원소의 col을 저장하고
val array는 각 원소의 value를 저장한다.

COO 포맷과 다른 것은 ptr array 뿐이다.

#define ROW_MAJOR 0
#define COL_MAJOR 1
typedef struct _cs {
    int number_of_rows;
    int number_of_cols;
    int number_of_elems;
    int order;
    int* ptr;
    int* idx;
    double* val;
}cs;

typedef struct _spmat{
    coo* elem;
    cs csr;
    cs csc;
}spmat;

int main(){
    spmat A;
    // CSR representation
    A.csr.order = ROW_MAJOR;
    A.csr.number_of_rows = 4;   
    A.csr.number_of_cols = 4;
    A.csr.number_of_elems = 4;
    A.csr.ptr = (int*)malloc(sizeof(int)*(number_of_rows+1));
    A.csr.idx = (int*)malloc(sizeof(int)*(number_of_elems));
    A.csr.val = (double*)malloc(sizeof(double)*(number_of_elems));
    
    A.csr.ptr[0] = 0; // ptr[0] is always zero
    A.csr.ptr[1] = 0; // because there's no nonzero element in row 0
    A.csr.ptr[2] = 2; // two nonzero elements in row 1
    A.csr.ptr[3] = 3; // one nonzero elements in row 2
    A.csr.ptr[4] = 4; // one nonzero elements in row 3
    
    A.csr.idx[0] = 0;
    A.csr.idx[1] = 1;
    A.csr.idx[2] = 2;
    A.csr.idx[3] = 1;

    A.csr.val[0] = 5;
    A.csr.val[1] = 8;
    A.csr.val[2] = 3;
    A.csr.val[3] = 6
    return 0;
}

만약 위 행렬에서 row 1 에 대한 탐색을 하고싶다면 A.csr.ptr[1]을 참조하고 A.csr.ptr[2]-A.csr.ptr[1] 개의 원소를 탐색하면 된다 CSC 포맷은 CSR 포맷과 구조는 같지만 column-major order로 저장되고 ptr는 각 열의 첫번째 원소의 위치, idx array는 행 값을 저장한다.
희소행렬을 CSR/CSC format으로 저장한다면 행렬원소의 개수가 E, 행렬의 크기가 NxN일 경우 필요한 메모리 공간은 N+2E이다.

Space complexity for CSC,CSR : \(O(N+2E)\)

희소행렬 데이터 소스 : https://sparse.tamu.edu/