🔢 mathematics

PackSELL: A Sparse Matrix Format for Precision-Agnostic High-Performance SpMV

The paper introduces PackSELL, a novel sparse matrix format that utilizes delta encoding and a compact packing scheme to support precision-agnostic data representations on GPUs, achieving significant speedups in SpMV and sparse linear solvers compared to existing methods like cuSPARSE.

Original authors: Kengo Suzuki, Takeshi Iwashita

Published 2026-04-16

📖 4 min read🧠 Deep dive

CC BY 4.0

Original authors: Kengo Suzuki, Takeshi Iwashita

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are a librarian trying to organize a massive, chaotic library where most of the shelves are empty. Your goal is to find specific books (data) and hand them to a very fast robot (the GPU) to do some heavy lifting (math calculations).

The problem is that the library is so big that the robot spends more time walking to the shelves (moving data) than actually reading the books (doing math). This is the "memory bottleneck" that slows down modern supercomputers.

This paper introduces a new way to organize the library called PackSELL. Here is how it works, explained simply:

1. The Old Way: The "Empty Shelf" Problem

Traditionally, libraries (sparse matrix formats) organize books by rows. If a row has 5 books, but the next row has 50, the system often forces them to look the same size to keep things tidy. This means filling the empty spots with "dummy books" (padding).

The Analogy: Imagine you are packing a suitcase. If you have a small shirt and a giant coat, and you force them into the same-sized box, you end up wasting a lot of space on air. The robot has to carry all that empty air, which slows it down.

2. The New Idea: "Delta Packing" (The Zipper Trick)

The authors, Kengo Suzuki and Takeshi Iwashita, realized that in these math libraries, the "book locations" (column indices) are usually close to each other. Instead of writing down the full address for every single book, you can just write down how far you moved from the last book.

The Analogy: Instead of writing "The book is at aisle 100, shelf 5," you just write "Move 3 steps right." This is called Delta Encoding. It turns a long address into a tiny number.

3. The Magic Trick: "Packing"

Here is where PackSELL gets clever. Usually, you store the "address" and the "book content" in separate boxes. But PackSELL glues them together into a single, custom-sized box.

The Analogy: Imagine you are a chef. Instead of carrying a separate tray for spices and a separate tray for ingredients, you mix the exact pinch of spice inside the ingredient bowl.
The Benefit: This allows the computer to carry less weight. It also lets the chef decide exactly how much space to give the spice vs. the ingredient.
- Need high precision? Give the ingredient more space.
- Need speed? Give the spice less space.
- Crucially: You aren't stuck with standard "box sizes" (like standard computer numbers). You can make custom boxes that fit your specific recipe perfectly.

4. Why This Matters: The "Precision-Agnostic" Superpower

Most computer systems are rigid. They only understand standard sizes (like 32-bit or 64-bit numbers). If you try to use a weird, custom size, the system breaks or slows down.

PackSELL is like a universal adapter. It can handle:

Standard sizes: The usual numbers computers use.
Tiny sizes: Half-precision numbers (FP16) that are super fast but less accurate.
Weird sizes: Custom formats that don't exist in standard textbooks, designed specifically for the problem at hand.

5. The Results: Speeding Up the Robot

The researchers tested this on a super-fast computer (NVIDIA A100 GPU).

The Win: When they used PackSELL with "half-precision" numbers, the robot worked 1.63 times faster than the current best standard method.
The Magic Win: Even better, they found a "sweet spot" where they used a custom format that was as accurate as the slow, heavy standard method, but as fast as the quick, light method.
Real World Impact: They used this to solve complex physics problems (like simulating airflow or electricity). The new method solved these problems 2.09 times faster than the old standard way.

Summary

Think of PackSELL as a smart, custom-fit suitcase for data.

It stops you from carrying empty air (reduces memory waste).
It lets you zip the address and the content together (delta-value packing).
It lets you choose exactly how big your suitcase needs to be, regardless of whether you are packing a feather or a brick (supports any data format).

By making the data lighter and more flexible, the computer's "robot" spends less time walking and more time working, leading to massive speedups in scientific research.

1. Problem Statement

Sparse Matrix-Vector Multiplication (SpMV) is a fundamental kernel in scientific computing, particularly for solving sparse linear systems using Krylov subspace methods. As hardware advances, the gap between memory bandwidth and computational performance has widened, making SpMV a memory-bound operation.

The Bottleneck: Reducing data movement is critical. While mixed-precision techniques (using FP16, BF16, or custom formats) can reduce memory footprint, existing high-performance SpMV kernels (like those in NVIDIA cuSPARSE) are tightly coupled to classical IEEE 754 formats (FP32, FP64) and byte-aligned memory access.
The Limitation: Current sparse formats (CSR, SELL, etc.) treat data representation and index encoding separately. They implicitly assume data types aligned to hardware boundaries (multiples of bytes), making it difficult to efficiently utilize non-IEEE formats or custom bit-widths (e.g., 16-bit integers or custom floating-point formats) without incurring padding or alignment overhead.
The Goal: Develop a sparse matrix format that supports precision-agnostic data representations (including non-IEEE formats) while minimizing memory footprint and maximizing GPU throughput.

2. Methodology: The PackSELL Format

The authors propose PackSELL, a novel sparse matrix format built upon the Sliced ELLPACK (SELL) format. It introduces two core innovations to compress data and enable flexible bit allocation:

A. Delta Encoding for Column Indices

Instead of storing absolute column indices, PackSELL stores the difference (delta) between the current column index and the preceding non-zero element in the same row.

For a row $i$ , the column index $j$ of a non-zero element is encoded as $d_{i,j} = j - \max(S_{i,j})$ , where $S_{i,j}$ is the set of previous column indices.
This exploits the locality of non-zero elements, often resulting in small integers that require fewer bits than full 32-bit indices.

B. Delta–Value Packing

PackSELL packs the delta and the matrix value into a single $W$ -bit word (typically $W=32$ ).

Structure: A word consists of a $D$ -bit unsigned integer for the delta, $V$ bits for the value, and 1 flag bit ( $W = V + D + 1$ ).
Flag Mechanism:
- Flag = 1: The delta fits within $D$ bits. The value (using any $V$ -bit format, including non-IEEE) is stored in the upper $V$ bits, and the delta is shifted left by 1 bit.
- Flag = 0: The delta exceeds $D$ bits (overflow). All $W-1$ bits are used to store the large delta (shifted left). The matrix value is effectively zeroed out.
Handling Overflow (Dummy Elements): When a delta is too large for $D$ bits, PackSELL inserts a dummy element at the target column index. The dummy element carries the large delta (Flag=0), and the actual non-zero element follows with a delta of 0 (Flag=1). This allows $D$ to be kept very small (e.g., 1 bit) to maximize $V$ (value precision) without losing representability.
Flexibility: By adjusting the ratio of $D$ to $V$ , users can define custom data formats. For example, one can allocate 8 bits for an exponent and 22 bits for a mantissa (E8M22) or use standard FP16 (16 bits) with 15 bits for the delta.

C. Implementation Details

Alignment: PackSELL retains the SELL structure of slicing rows into blocks of size $C$ (e.g., 32) to ensure uniform workload and coalesced memory access.
Row Permutation: To minimize padding, rows are reordered within blocks of $\sigma$ rows (SELL-C- $\sigma$ ). PackSELL handles this implicitly using a permutation array.
Unpacking: The unpacking process is designed to be branch-free on GPUs, using bitwise operations to extract the flag, shift amounts, and values efficiently.

3. Key Contributions

Novel Format (PackSELL): A sparse matrix format that jointly compresses indices and values, enabling support for arbitrary bit-widths and non-IEEE floating-point formats.
Precision-Agnostic Design: The ability to trade off index precision ( $D$ ) for value precision ( $V$ ) dynamically, allowing the same kernel to run FP16, custom E8M formats, or even integer-based representations.
Performance Analysis: Comprehensive evaluation of PackSELL-based SpMV kernels and their integration into mixed-precision Krylov subspace methods (F3R and Inner-Outer CG).
Scenario Identification: Demonstration of a practical scenario where non-IEEE formats (specifically E8M variants) outperform standard FP16/FP32 approaches in terms of both speed and accuracy.

4. Experimental Results

Experiments were conducted on an NVIDIA A100 GPU using 435 matrices from the SuiteSparse collection.

A. Standalone SpMV Performance

FP16 Performance: For matrices with regular sparsity patterns (292 out of 435 matrices), PackSELL (configured with $D=15, V=16$ ) outperformed the NVIDIA cuSPARSE SELL kernel by up to 1.63×. It also outperformed cuCSR and DASP significantly.
Non-IEEE Formats: Using custom E8M formats (e.g., $D=1, V=21$ ), PackSELL achieved FP32-level accuracy (low backward error) while maintaining performance comparable to or exceeding FP16 cuSPARSE.
Memory Footprint: PackSELL reduced memory usage by up to ~25% compared to standard SELL for dense matrices, approaching the theoretical lower bound of 0.75 (32 bits total / 48 bits for standard 32-bit index + 16-bit value).

B. Krylov Subspace Methods (Solvers)

F3R Solver (FP16-enabled): Integrating PackSELL into the F3R solver (which uses FP16 SpMV in inner layers) resulted in a 1.32× speedup over the standard FP16-F3R implementation, with up to 2.64× speedup over full FP64 solvers.
Inner-Outer CG (IO-CG):
- Standard FP16-IO-CG often failed to converge or required excessive iterations due to precision loss.
- E8MY-IO-CG: By using PackSELL with a custom format (e.g., $D=10, V=14$ ), the solver achieved FP32-level accuracy while running faster than FP32 kernels.
- This approach achieved a 2.09× speedup over standard full-precision (FP64) PCG, approaching the theoretical ideal gain of 2.0×.

5. Significance and Impact

Breaking the Alignment Barrier: PackSELL decouples data representation from hardware alignment constraints, proving that non-byte-aligned and non-IEEE formats can be executed efficiently on GPUs.
Enabling Advanced Mixed-Precision: It provides a practical pathway for using custom floating-point formats in iterative solvers, solving the "accuracy vs. speed" trade-off that plagues standard FP16/BF16 approaches.
Future-Proofing: As hardware evolves with more specialized low-precision units, PackSELL offers a flexible framework to exploit these units without rewriting the entire sparse matrix infrastructure.
Practical Utility: The results demonstrate that for a significant subset of real-world matrices, PackSELL is not just a theoretical improvement but a practical tool for accelerating scientific simulations.

In conclusion, PackSELL represents a significant step forward in sparse linear algebra by unifying index compression and value packing, thereby unlocking high-performance computing potential for a wider variety of data representations.