28.37 희소 텐서(Sparse Tensor)의 저장 형식과 연산 최적화

1. 희소 텐서의 정의와 도입 동기

희소 텐서(Sparse Tensor)는 전체 원소 가운데 절대다수가 0이고, 0이 아닌 원소가 상대적으로 매우 적은 텐서를 일컫는다. 형식적으로 $d$ 차 텐서 $\mathcal{A} \in \mathbb{R}^{n_1 \times n_2 \times \cdots \times n_d}$ 의 0이 아닌 원소의 수를 $\mathrm{nnz}(\mathcal{A})$ 라 표기하면, 희소 텐서는 $\mathrm{nnz}(\mathcal{A}) \ll \prod_{k=1}^{d} n_k$ 를 만족하는 텐서로 정의된다. 이러한 희소성은 추천 시스템의 사용자-항목 행렬, 자연어 처리에서의 단어-문서 행렬, 그래프 인접 행렬, 그래프 신경망에서의 메시지 전달 행렬, 점군(Point Cloud) 자료, 3차원 격자 위의 점유 맵 등에서 자연스럽게 등장한다.

희소 텐서를 일반적인 조밀(Dense) 형식으로 저장하면 0인 원소의 수에 비례한 메모리 낭비가 발생하며, 또한 0과 곱해지거나 0이 더해지는 무의미한 산술 연산이 대량으로 수행된다. 따라서 0이 아닌 원소만을 명시적으로 저장하고, 그 위치 정보를 함께 부호화하는 특수한 자료 구조와, 그 자료 구조 위에서 직접 동작하는 전용 알고리즘이 필요하다.

2. 희소 행렬의 표준 저장 형식

희소 텐서의 일반론은 희소 행렬, 즉 2차 희소 텐서에 대한 고전적 자료 구조로부터 출발한다. 가장 널리 사용되는 형식은 다음과 같다.

2.1 좌표 형식(COO)

좌표 형식(Coordinate Format, COO)은 0이 아닌 각 원소에 대하여 그 행 인덱스, 열 인덱스, 값을 세 개의 1차원 배열에 저장하는 형식이다. 형식적으로 $\mathrm{nnz}(\mathcal{A})$ 개의 원소를 표현하기 위해 길이 $\mathrm{nnz}(\mathcal{A})$ 의 행 인덱스 배열, 동일한 길이의 열 인덱스 배열, 동일한 길이의 값 배열이 필요하다. COO 형식은 원소 단위의 삽입과 삭제가 단순하다는 장점이 있으며, 임의 차수의 텐서로 자연스럽게 일반화된다는 점에서 다차원 희소 텐서의 기본 표현으로 채택되는 경우가 많다.

2.2 압축 행 저장(CSR)

압축 희소 행(Compressed Sparse Row, CSR) 형식은 행렬 곱셈과 같은 행 단위 접근에 최적화된 형식이다. 세 개의 배열이 사용된다. 첫째는 0이 아닌 원소의 값을 행 우선 순서로 저장한 값 배열이며, 둘째는 각 값의 열 인덱스를 저장한 열 인덱스 배열이고, 셋째는 행 포인터(Row Pointer) 배열로, $i$ 번째 원소가 $i$ 번째 행의 첫 번째 0이 아닌 원소가 값 배열의 어느 위치에서 시작되는지를 나타낸다. 행 포인터 배열의 길이는 $m + 1$ 이며, $m$ 은 행렬의 행 수이다.

CSR 형식은 한 행에 속한 0이 아닌 원소들이 메모리 상에서 연속적으로 저장되므로, 행 단위 순회와 캐시 친화적 접근에 매우 유리하다. 이러한 특성 때문에 희소 행렬-벡터 곱셈(Sparse Matrix-Vector Multiplication, SpMV)과 희소 행렬-조밀 행렬 곱셈(Sparse Matrix-Matrix Multiplication, SpMM)의 표준 형식으로 채택된다.

2.3 압축 열 저장(CSC)

압축 희소 열(Compressed Sparse Column, CSC) 형식은 CSR과 대칭적으로, 0이 아닌 원소를 열 우선 순서로 저장하고 열 포인터를 사용한다. 열 단위 접근, 전치 행렬에 대한 연산, 일부 직접 해법(Direct Solver)에서 유리하다.

2.4 블록 압축 행 저장(BSR)

블록 압축 희소 행(Block Sparse Row, BSR) 형식은 행렬을 작은 정방형 블록으로 분할한 뒤, 0이 아닌 블록만을 CSR과 유사한 방식으로 저장하는 형식이다. 한 블록 안에는 일반적인 조밀한 부분 행렬이 저장되며, 블록 단위의 산술 연산에 BLAS 수준의 최적화된 커널을 활용할 수 있다는 장점이 있다. 신경망 가중치 행렬에 구조적 희소성(Structured Sparsity)을 도입한 압축 모형에서 자주 사용된다.

2.5 대각 형식과 ELL 형식

대각 형식(DIA)은 대각선 방향으로 0이 아닌 원소가 집중되어 있는 행렬에 적합하며, ELL 형식은 각 행이 거의 동일한 수의 0이 아닌 원소를 가지는 경우에 유리한 형식이다. 두 형식 모두 GPU 상에서 SpMV 연산의 메모리 접근 패턴을 정규화하기 위한 기법으로 사용되었으며, 후자는 ELLPACK 패키지에서 유래하였다.

3. 다차원 희소 텐서의 표현

행렬이 아닌 일반적인 $d$ 차 희소 텐서는 두 가지 방향으로 일반화된다.

3.1 COO 형식의 확장

가장 단순한 일반화는 COO 형식의 직접적 확장이다. 0이 아닌 각 원소에 대해 $d$ 개의 인덱스 배열과 한 개의 값 배열을 저장한다. PyTorch의 torch.sparse_coo_tensor와 TensorFlow의 tf.SparseTensor가 이 형식에 기반한다. COO 형식은 차수에 무관하게 일관되게 정의되며, 임의의 텐서 연산을 수학적으로 명료하게 기술할 수 있는 장점이 있다.

3.2 모드 단위 압축 형식

CSR과 CSC를 다차원으로 확장한 형식은 보다 정교하다. 압축 희소 광역(Compressed Sparse Fiber, CSF) 형식은 $d$ 차 텐서의 차원을 일정한 순서로 정렬한 뒤, 가장 외부 차원부터 안쪽으로 들어가면서 0이 아닌 광섬유(Fiber)들의 트리 구조를 형성하는 방식이다. 이는 텐서 분해, 텐서 축약, 확장된 다차원 SpMM과 같은 연산에서 캐시 효율성과 압축률을 동시에 향상시키는 표준 형식 가운데 하나로, 스마이드(S. Smith) 등의 2015년 논문 “SPLATT: Efficient and Parallel Sparse Tensor-Matrix Multiplication“에서 분석되었다.

3.3 하이브리드 형식

실제 응용에서는 단일한 형식이 모든 연산에 최적이지 않으므로, 같은 텐서를 여러 형식으로 동시에 보유하거나, 부분 영역별로 서로 다른 형식을 적용하는 하이브리드 표현이 사용되기도 한다.

4. 희소 텐서 연산의 최적화 원리

4.1 무의미한 연산의 제거

희소 텐서 연산의 가장 기본적인 최적화 원리는, 0과 관련된 산술 연산을 명시적으로 제거하는 것이다. 즉, 0이 아닌 원소만을 순회하면서 그 원소가 결과에 기여하는 항만을 계산한다. 예를 들어 행렬-벡터 곱셈 $\mathbf{y} = A \mathbf{x}$ 에서 행렬 $A$ 가 CSR 형식으로 저장되어 있다면, 다음과 같이 연산할 수 있다.

$y_i = \sum_{k = \mathrm{rowptr}[i]}^{\mathrm{rowptr}[i+1]-1} \mathrm{val}[k] \cdot x_{\mathrm{colidx}[k]}$

여기서 합산은 0이 아닌 원소만을 따라 수행되며, 연산량은 행렬의 크기가 아니라 $\mathrm{nnz}(A)$ 에 비례한다. 따라서 희소 행렬-벡터 곱셈의 시간 복잡도는 $\mathcal{O}(\mathrm{nnz}(A))$ 이며, 동일한 형상의 조밀 행렬에 대한 $\mathcal{O}(mn)$ 에 비해 결정적인 이득을 얻는다.

4.2 메모리 접근 패턴과 캐시 활용

희소 연산의 실제 성능을 결정하는 핵심 요인은 산술 연산량이 아니라, 불규칙한 메모리 접근 패턴에 의한 캐시 효율성 저하이다. 예를 들어 위 SpMV 식에서 입력 벡터 $\mathbf{x}$ 의 접근 패턴은 $\mathrm{colidx}[k]$ 에 의해 결정되므로, 일반적으로 메모리 상에서 연속적이지 않다. 따라서 캐시 미스(Cache Miss)가 빈번하게 발생하며, 이론적 산술 처리량에 비해 실제 성능이 크게 떨어지는 현상이 관찰된다.

이를 완화하기 위한 표준적 기법으로는 그래프 분할 및 재정렬을 통해 인접한 0이 아닌 원소들을 메모리 상에서 가깝게 배치하는 RCM(Reverse Cuthill-McKee) 재정렬, 행렬을 작은 블록 단위로 분해하여 캐시 안에 적합한 부분만을 한 번에 처리하는 캐시 블로킹(Cache Blocking), 동일한 0이 아닌 패턴을 공유하는 행들을 묶어 처리하는 벡터화 기법 등이 있다.

4.3 GPU에서의 희소 연산

GPU 환경에서는 결합 메모리 접근과 워프 단위 균등성이 성능을 좌우하므로, CSR과 같은 단순한 형식은 행마다 0이 아닌 원소의 수가 크게 다를 때 워프 발산(Warp Divergence)을 유발한다. 이러한 문제를 완화하기 위하여 NVIDIA cuSPARSE와 같은 라이브러리는 CSR, CSC, BSR, COO, BlockedELL 등의 다양한 형식을 지원하며, 각 형식에 최적화된 SpMV 및 SpMM 커널을 제공한다. 또한 머크리(D. Merrill)와 가랜드(M. Garland)의 2016년 논문 “Merge-Based Parallel Sparse Matrix-Vector Multiplication“은 부하 불균형을 알고리즘적으로 해소하는 병합 기반 SpMV를 제안하여, 임의 분포의 희소 행렬에 대해서도 일관된 GPU 성능을 달성하였다.

5. 자동 미분과 희소 텐서

희소 텐서를 딥러닝 학습과 결합할 때 발생하는 본질적 어려움은, 일반적인 전향-후향 자동 미분이 후행 단계에서 조밀한 보조량(Adjoint)을 산출할 수 있다는 점이다. 즉, 입력이 희소하더라도 경사도가 조밀해질 가능성이 있으며, 이는 메모리 폭발을 초래할 수 있다. 이를 방지하기 위해 프레임워크는 경사도의 희소성을 보존하는 특수한 연산(예: PyTorch의 torch.sparse.mm, TensorFlow의 tf.sparse.sparse_dense_matmul)을 별도로 정의하며, 임베딩 행렬 갱신과 같이 인덱스에 의해 제한된 부분만이 갱신되는 경우에는 희소 경사도(Sparse Gradient) 표현을 명시적으로 사용한다.

6. 신경망 가중치의 희소화

희소 텐서의 또 다른 중요한 응용은, 학습이 끝난 신경망의 가중치를 사후적으로 희소화함으로써 모델을 압축하고 추론 속도를 향상시키는 가지치기(Pruning) 기법이다. 한(S. Han) 등의 2016년 논문 “Deep Compression: Compressing Deep Neural Networks with Pruning, Trained Quantization and Huffman Coding“은 가지치기, 양자화, 허프만 부호화의 결합을 통해 가중치 텐서의 저장 비용을 수십 배 압축할 수 있음을 보였다. 그러나 비구조적 희소성(Unstructured Sparsity)은 메모리는 절약하지만 일반적인 GPU 산술 처리량을 곧바로 향상시키기 어렵기 때문에, NVIDIA의 암페어(Ampere) 세대에서 도입된 2:4 구조적 희소성(2:4 Structured Sparsity)과 같이 하드웨어가 직접 지원할 수 있는 형식이 제안되었다. 2:4 구조는 4개 원소 단위의 모든 그룹에서 정확히 2개의 원소만을 0이 아니도록 강제하며, 이러한 정규화된 희소성은 텐서 코어의 처리량을 약 2배 향상시킨다.

7. 결론

희소 텐서는 단순한 자료 구조의 변형이 아니라, 메모리와 연산 자원을 절약하기 위한 표현, 그리고 그 표현 위에서 동작하는 알고리즘 전체를 포괄하는 학문적 영역이다. COO, CSR, CSC, BSR, CSF 등 다양한 저장 형식은 각각 서로 다른 접근 패턴과 연산 유형에 대해 최적화되어 있으며, 최적화의 핵심은 무의미한 산술 연산의 제거뿐 아니라 불규칙한 메모리 접근의 정규화에 있다. 딥러닝의 맥락에서 희소 텐서는 추천 시스템, 그래프 신경망, 점군 처리, 모델 압축 등 다양한 응용에서 핵심적 역할을 수행하며, 그 자료 구조와 알고리즘은 일반적인 조밀 텐서와 동등하게 중요한 위상을 차지한다.