Sparsity Encoding

The Compressed Sparse Row (CSR) format is a general-purpose, row-major representation ideal for sparse matrix-vector multiplication (SpMV). It uses three arrays:

• values: Stores all non-zero values.
• col_indices: Stores the column index for each corresponding value.
• row_ptr: Stores the start and end indices in values/col_indices for each row.

Example: A 3x3 matrix with non-zeros at (0,0)=5, (1,2)=8, (2,1)=3.

• values = [5, 8, 3]
• col_indices = [0, 2, 1]
• row_ptr = [0, 1, 2, 3]

CSR provides efficient row traversal but poor random access and column-wise operations. It is widely supported in frameworks like SciPy (scipy.sparse.csr_matrix) and optimized BLAS libraries.

The Compressed Sparse Column (CSC) format is the column-major analog to CSR, optimized for column-wise operations and SpMV when the vector is accessed by column. Its three arrays are:

• values: Stores all non-zero values.
• row_indices: Stores the row index for each value.
• col_ptr: Stores the start and end indices for each column.

CSC is the transpose representation of CSR. It is the preferred format for factorization algorithms (like Cholesky) and is equally prevalent in scientific computing libraries. The choice between CSR and CSC often depends on the dominant data access pattern in the target algorithm to ensure contiguous memory access.

The Coordinate Format (COO) is the simplest sparse encoding, storing a list of tuples for each non-zero element. It uses three arrays of equal length:

• values: The non-zero values.
• row_indices: The row coordinates.
• col_indices: The column coordinates.

Use Case: COO is highly flexible and easy to construct, making it ideal for incremental matrix assembly (e.g., during graph construction or finite element analysis). However, it is inefficient for computation due to unstructured access. It is often used as an intermediate format before being converted to CSR or CSC for efficient computation. Frameworks like PyTorch support COO tensors (torch.sparse_coo_tensor).

The Block Compressed Sparse Row (BSR) format extends CSR by storing dense sub-blocks of non-zero values instead of scalars. It is defined by a block size (R, C) and uses arrays similar to CSR:

• block_values: A 3D array of dense blocks.
• block_col_indices: Column index for each block.
• block_row_ptr: Row pointer array.

Hardware Advantage: BSR exploits spatial locality and enables the use of vectorized/SIMD instructions (like ARM NEON) or tensor cores by operating on small, dense blocks. It is highly effective for matrices with inherent block structure, such as those from certain PDE discretizations. The format reduces metadata overhead and improves cache line utilization compared to scalar CSR.

The ELLPACK (ELL) format is designed for vector architectures and GPUs where regular, aligned memory access is crucial. It stores non-zeros in two dense 2D arrays:

• values: A num_rows x max_nonzeros_per_row matrix. Rows with fewer non-zeros are padded.
• col_indices: Corresponding column indices matrix.

Performance Trade-off: ELL provides perfectly coalesced memory access on GPUs, leading to high bandwidth utilization for SpMV. However, its memory efficiency suffers if the number of non-zeros per row varies significantly (high padding overhead). It is often used in hybrid formats like ELL-COO or ELL-R, where a separate structure (like COO) handles the remaining irregular elements.

For high-order sparse tensors, the Compressed Sparse Fiber (CSF) format is a generalization of CSR. It represents a tensor as a tree where each level corresponds to a mode (dimension).

Structure:

• The root stores pointers into the first mode's indices.
• Subsequent levels store indices and pointers until the leaf level, which stores the non-zero values.

Application: CSF is essential for hardware-aware design of tensor operations (e.g., sparse tensor contractions) in domains like quantum chemistry and graph analytics. It minimizes metadata storage for high-dimensional data and can be optimized for specific access patterns (e.g., mode-1 vs. mode-2 traversal). Research compilers like Tensor Compiler (taco) use CSF-like formats to generate efficient sparse tensor algebra code.

The Compressed Sparse Row (CSR) format is a standard encoding for 2D sparse matrices. It uses three arrays:

• values: Stores only the non-zero elements.
• col_indices: Stores the column index for each non-zero value.
• row_ptr: Stores the cumulative count of non-zero elements up to each row, enabling efficient row-wise access.

This format is optimal for operations like sparse matrix-vector multiplication (SpMV), a core kernel in scientific computing and graph neural networks, as it minimizes memory footprint and enables efficient cache utilization during row traversal.

Compressed Sparse Column (CSC) is the column-major counterpart to CSR. It uses analogous arrays:

• values: Non-zero elements.
• row_indices: Row index for each value.
• col_ptr: Cumulative non-zero counts per column.

CSC is the preferred format for column-wise operations, such as certain linear algebra solvers. Its efficiency is critical in hardware-aware design, as the choice between CSR and CSC can significantly impact performance on modern CPUs and GPUs due to memory access patterns and cache line alignment.

Blocked sparsity patterns, such as Block CSR (BCSR), group non-zero elements into small, dense blocks (e.g., 4x4). Instead of storing individual element indices, it stores block indices and a dense block of values.

Key advantages include:

• Reduced Metadata Overhead: Fewer indices to store.
• Improved Hardware Utilization: Enables the use of SIMD (Single Instruction, Multiple Data) instructions and Tensor Cores by operating on small, dense blocks.
• Better Cache Locality: Accessing a block of contiguous data is more efficient than scattered elements. This is essential for achieving high throughput on accelerators like GPUs and NPUs.

After applying model pruning techniques to induce sparsity, specialized encoders are needed to exploit it. Structured pruning (removing entire channels, filters, or blocks) creates coarse-grained sparsity patterns that are highly amenable to efficient encoding.

Formats like 2:4 fine-grained sparsity (where 2 out of every 4 contiguous weights are zero) are natively supported by NVIDIA's Ampere architecture and newer GPUs. Encoding this pattern allows the hardware to skip zero multiplications entirely, doubling theoretical computational throughput for matrix operations. This directly translates to faster inference and lower power consumption.

For high-dimensional sparse data, generalized tensor formats are required.

• Coordinate Format (COO): Stores a list of (value, index_1, index_2, ...) tuples. Simple but can have high memory overhead for indices.
• Fiber-based Formats: Extend CSR/CSC concepts to N dimensions. For a 3D tensor, Compressed Sparse Fiber (CSF) or F-COO can be used.

These formats are critical for:

• Graph Neural Networks (GNNs): Representing adjacency matrices and performing sparse aggregations.
• Recommender Systems: Handling massive, sparse user-item interaction matrices.
• Scientific Data: Storing outputs from simulations where most states are empty.

Sparsity encoding is not just a storage format; it requires deep integration with the compiler stack and runtime. Systems like Apache TVM, TensorRT, and XLA perform graph-level optimizations that:

1. Fuse Operations: Combine a sparse matrix lookup with a subsequent dense operation into a single, optimized kernel.
2. Kernel Auto-Tuning: Select the best implementation (e.g., CSR vs. blocked) for the specific sparsity pattern and target hardware (CPU, GPU, NPU).
3. Schedule Optimization: Reorder loops and manage memory hierarchy to maximize data reuse from the encoded sparse structure. This integration is what unlocks the theoretical efficiency gains promised by sparsity.

Model pruning is the upstream technique that creates the sparsity later encoded for efficiency. It systematically removes redundant or less important parameters (weights, neurons, or filters) from a neural network. The goal is to reduce the model's size and computational footprint while preserving accuracy.

• Unstructured Pruning: Removes individual weights anywhere in the network, creating irregular sparsity patterns that require formats like CSR for efficient storage.
• Structured Pruning: Removes entire channels, filters, or layers, resulting in regular, hardware-friendly sparsity that is easier to accelerate without complex encoding.
• Pruning is typically iterative: train, prune less important weights, and fine-tune the remaining network.

Compressed Sparse Row is one of the most common sparsity encoding formats for 2D matrices. It efficiently represents a sparse matrix using three arrays:

• values: Stores all non-zero values, in row-major order.
• col_indices: Stores the column index for each corresponding non-zero value.
• row_ptr: Stores the index in values where each row begins; length is rows + 1.

Example: For a matrix with non-zeros at (0,0)=5 and (1,2)=3: values = [5, 3] col_indices = [0, 2] row_ptr = [0, 1, 2]

CSR minimizes storage for highly sparse matrices and enables efficient row-based operations like SpMM (Sparse Matrix-Matrix Multiplication).

SpMM is the fundamental computation kernel enabled by sparsity encoding. It performs the multiplication of a sparse matrix (encoded in CSR or similar format) with a dense matrix. The efficiency gains come from skipping multiplications with zero values.

• Key Challenge: Irregular memory access patterns due to sparse indices can underutilize hardware parallelism and cache. Optimized SpMM kernels are hardware-specific.
• Hardware Acceleration: Modern NPUs and GPUs include specialized instructions and execution units for sparse tensor operations, dramatically accelerating SpMM over dense equivalents.
• SpMM is critical in Transformer inference, where pruned attention or FFN weight matrices are sparse.

Block sparse format is an encoding scheme that trades some granularity for hardware efficiency. Instead of tracking individual non-zero values, it groups weights into small, dense blocks (e.g., 4x4). The sparsity pattern is then defined at the block level.

• Advantages:
  • More regular memory access patterns improve cache utilization and vectorization.
  • Easier to map to Tensor Core or SIMD units that operate on small, dense tiles.
  • Reduces metadata overhead compared to fully unstructured formats.
• Use Case: Often used in conjunction with structured pruning or when targeting hardware with specific block-level execution capabilities.

Modern Neural Processing Units include first-class hardware support for sparsity to maximize compute efficiency and reduce memory bandwidth. This goes beyond software encoding.

• Sparse Compute Units: Dedicated execution paths that skip multiplication when a weight or activation is zero, saving power and clock cycles.
• Weight Compression: On-chip decompression engines that read encoded sparse weights (e.g., CSR-like formats) from memory and expand them for computation.
• Sparse Dataflow: Architectures like systolic arrays can be designed to propagate zeros without performing useless operations.
• Examples include NVIDIA's Sparse Tensor Cores (Ampere+ GPUs) and dedicated features in Apple, Google, and Qualcomm NPUs.

Design Space Exploration is the systematic process of evaluating the trade-offs introduced by sparsity encoding within a hardware-aware design loop.

Engineers explore a multi-dimensional space:

• Pruning Ratio vs. Accuracy Drop
• Encoding Format (CSR, Blocked) vs. Hardware Throughput
• Sparsity Pattern (Unstructured, Structured) vs. Memory Bandwidth Saved

Tools like the Roofline Model are used to analyze if a sparsely encoded kernel is compute-bound or memory-bound on target hardware. The goal is to find a Pareto-optimal design where sparsity encoding provides maximal efficiency gains for an acceptable accuracy loss.