희소 행렬 압축
IT 위키
희소 행렬 압축(sparse matrix compression)은 요소의 대부분이 0인 희소 행렬을 저장 및 계산할 때, 0이 아닌 원소만을 효율적으로 표현하여 메모리와 연산 효율을 높이는 기술이다.
개념 및 필요성
- 희소 행렬(sparse matrix)이란 행렬 원소 중 0이 아닌 값(nonzero)이 전체 원소 대비 매우 적은 비율을 차지하는 행렬이다.
- 밀집 행렬(dense matrix) 방식으로 저장하면 많은 0 값도 공간을 차지하므로 비효율적이다.
- 따라서 희소 행렬 압축은 0 값을 건너뛰고, 비(非)제로 값을 중심으로 저장하고 연산하는 방식이 필요하다.
- 이는 대형 그래프 인접 행렬, 기계 학습 특성 행렬, 과학/공학 응용의 선형 시스템 등에서 매우 중요하다.
대표 저장 방식
여러 방법이 존재하며, 각각 장단점이 있다:
- Coordinate (COO) 형식
- 행렬의 비제로 원소 각각에 대해 (행 인덱스, 열 인덱스, 값) 튜플을 저장
- 구현이 단순하고 직관적이며 추가/수정이 유연하다는 장점이 있다
- 하지만 행 또는 열 기반 연산에서는 비효율적일 수 있다
- Compressed Sparse Row (CSR, 압축 행 기준)
- 각 비제로 원소의 값을 담은 배열(Val)
- 각 비제로 원소의 열 인덱스를 담은 배열(ColIdx)
- 각 행의 시작 위치를 담은 배열(RowPtr)
- 행 방향 연산(예: 행벡터 곱셈)에 유리하다
- Compressed Sparse Column (CSC, 압축 열 기준)
- CSR의 전치된 방식으로, 열 중심 연산에 유리하다
- 각 비제로 원소의 값, 각 비제로 원소의 행 인덱스, 각 열의 시작 위치를 저장
- Block Sparse Row / Block Sparse Column (BSR / BSC)
- 행 또는 열을 블록 단위로 묶어 저장
- 블록 내에 0이 일부 포함될 수 있지만, 패턴이 구조화돼 있거나 블록 단위 연산이 유리한 경우 사용
- 기타 압축 기법 및 응용형 포맷
- 희소 텐서 압축 기법 (예: Compressed Sparse Fibers, CSF)
- 행렬 재배치(reordering) + 압축 기법 결합
- 손실 압축 기법 (예: 근사 압축 방식)
재배치 및 최적화 기법
저장 방식만큼이나 중요한 것은 재배치와 최적화 전략이다:
- 대역폭 최소화 재배치 (예: Cuthill–McKee 알고리즘)
- 대각선을 중심으로 비제로 원소가 모이게 행/열 순서를 재배치
- LU 분해나 가우스 소거 시 “fill-in(제로가 아닌 원소가 새로 생기는 현상)”을 줄이는 데 유리
- Reverse Cuthill-McKee 등 변형 기법 존재
- 최소 차수 알고리즘 (Minimum Degree Algorithm)
- 대각화, 분해 시 발생할 비제로 증가를 줄이기 위해 변수의 차수를 기준으로 순서를 선택하는 방식
- 하드웨어 가속 및 비트맵 기반 인덱싱 (예: SMASH)
- 지시자(pointer chasing) 연산을 줄이고 인덱싱 비용을 낮추는 구조와 하드웨어 협조 방식 제안됨
압축 효과 및 연산 비용
- 저장 공간 절감: 비제로 원소만 저장하므로 밀집 방식 대비 메모리 사용량을 크게 줄일 수 있다
- 계산 효율성: 0 요소를 건너 뛰므로 연산량 감소
- 단, 인덱스 배열 관리, 포인터 연산, 캐시 효율 저하 등의 오버헤드가 존재
- 압축 방식과 포맷에 따라 특정 연산(예: 행벡터 곱, 열벡터 곱, 전치 등)에 강점 또는 약점이 있음
최신 연구 동향 및 응용
- NeuKron: 희소 행렬을 재배치하고 순환 신경망을 사용해 상수 크기로 손실 압축하는 방법 제안됨
- LoSparse: 행렬을 저순위 근사 + 희소 근사 합으로 표현해 모델 압축 성능 개선 시도
같이 보기
참고 문헌
- Nazli Goharian 외, “Comparative Analysis of Sparse Matrix Algorithms”
- Konstantinos Kanellopoulos 등, “SMASH: Co‑designing Software Compression and Hardware‑Accelerated Indexing for Efficient Sparse Matrix Operations”
- Taehyung Kwon 등, “NeuKron: Constant‑Size Lossy Compression of Sparse Reorderable Matrices and Tensors”
- Yixiao Li 등, “LoSparse: Structured Compression of Large Language Models based on Low‑Rank and Sparse Approximation”
