Sparse Data Layout

The simplest sparse format, storing an explicit list of (row, column, value) tuples for each non-zero element.

• Structure: Three parallel arrays: rows, cols, data.
• Use Case: Ideal for incremental construction and modification of sparse matrices, as new non-zeros can be appended. Common as an intermediate format before conversion to more efficient layouts for computation.
• Drawback: High memory overhead for operations due to explicit storage of both row and column indices per element, leading to suboptimal cache locality during arithmetic.

The de facto standard for general-purpose SpMM (Sparse Matrix-Dense Matrix Multiplication) on CPUs and GPUs. It compresses row index information.

• Structure: Three arrays:
  • data: Stores non-zero values.
  • col_indices: Stores the column index for each value.
  • row_ptr: Stores the start and end index in data/col_indices for each row.
• Performance: Enables efficient row-wise traversal. Multiplying CSR by a dense matrix involves streaming the dense matrix rows, offering good spatial locality.
• Limitation: Inefficient for column-slice operations or transposed multiplication, which require random access within rows.

The column-major analogue to CSR, optimized for operations that access or traverse a matrix by columns.

• Structure: Three arrays:
  • data: Stores non-zero values.
  • row_indices: Stores the row index for each value.
  • col_ptr: Stores the start and end index for each column.
• Use Case: Essential for algorithms like sparse Cholesky factorization. Also optimal for multiplying the transpose of a sparse matrix (CSC) by a dense matrix, as it becomes a row-wise operation.
• Conversion: CSR and CSC are often transposes of each other; converting between them is a common preprocessing step.

Stores non-zero values in small, dense blocks (e.g., 4x4), trading some sparsity for vastly improved memory access regularity and utilization of SIMD/vector units.

• Principle: Instead of storing single values, stores small dense sub-matrices where at least one element in the block is non-zero.
• Advantage: Dramatically reduces index storage overhead and enables the use of dense, highly optimized micro-kernels (BLAS-like) on the blocks. Improves cache line utilization and prefetching.
• Application: Naturally fits neural network weight matrices where structured pruning (removing entire channels or blocks) creates coarse-grained sparsity patterns.

A hardware-aware format where sparsity is enforced at a fine-grained, regular pattern to match the data path of modern Sparse Tensor Cores (e.g., in NVIDIA Ampere+ GPUs).

• Pattern Rule: In every contiguous block of M weights (e.g., 4), exactly N (e.g., 2) must be non-zero. This creates a predictable, aligned sparsity pattern.
• Hardware Acceleration: The GPU's sparse tensor cores can skip reading the zero values, effectively doubling the theoretical FLOPs throughput for matrix operations. The sparsity is encoded compactly with a bitmask (e.g., 4 bits per block).
• Engineering Impact: Requires pruning algorithms specifically designed to satisfy the N:M constraint, balancing accuracy with the rigid format requirement.

A format designed for vector supercomputers, effective for matrices where the number of non-zeros per row is very regular.

• Structure: Two dense 2D arrays:
  • data: Holds non-zero values, padded per row.
  • col_indices: Holds corresponding column indices.
• Efficiency: When rows have similar non-zero counts, ELLPACK eliminates the indirect addressing of row_ptr in CSR, enabling efficient, coalesced memory accesses on GPUs. Each GPU thread can be assigned a row.
• Drawback: Severe performance degradation and memory waste if row lengths vary significantly, due to padding to the length of the longest row. Often used in hybrid formats like HYB (ELLPACK + COO).

The foundational data structure for storing tensors where most elements are zero. Instead of allocating memory for all values, it encodes only the non-zero values and their corresponding indices. The choice of format (e.g., CSR, COO, Blocked) is a critical design decision that determines memory footprint and computational efficiency for operations like SpMM and sparse convolution.

The fundamental computational kernel for sparse inference, calculating the product of a sparse matrix and a dense matrix. Performance is dominated by:

• Memory access patterns dictated by the sparse layout.
• Efficiency of gather-scatter operations to fetch non-contiguous data.
• Load imbalance across parallel threads due to irregular non-zero distribution. Optimized SpMM kernels are the workhorse of pruned model execution.

These pruning techniques create the sparsity that layouts must encode.

• Structured Pruning: Removes entire groups (e.g., filters, channels), creating regular, hardware-friendly sparsity patterns like N:M sparsity (e.g., 2:4).
• Unstructured Pruning: Removes individual weights, creating irregular, fine-grained sparsity that maximizes compression but requires sophisticated layouts and kernels to exploit. The pruning method dictates the optimal data layout.

Parallel computing primitives essential for sparse computation on vector architectures like GPUs.

• Gather: Reads a set of non-contiguous values (e.g., non-zero weights) into a contiguous register.
• Scatter: Writes a contiguous set of results to non-contiguous memory locations. The performance of these data-movement operations is often the bottleneck in sparse kernels, making layout choices critical for memory coalescing.

The observed performance difference between the theoretical speedup from reduced FLOPs and the actual speedup achieved on hardware. This gap is caused by overheads inherent to sparse execution:

• Sparse kernel overhead: Index decoding, pointer chasing, conditional branches.
• Inefficient memory access: Non-coalesced reads/writes due to layout.
• Load imbalance. A well-designed data layout directly addresses these overheads to minimize the gap.