🔢 mathematics

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

本文提出了一种名为 PackSELL 的新型稀疏矩阵格式，通过结合列索引的差分编码与单字存储方案，在支持灵活精度表示的同时显著降低内存开销，从而在 GPU 上实现了比现有 SELL 格式更高效的稀疏矩阵向量乘法（SpMV）及线性求解器性能。

原作者： Kengo Suzuki, Takeshi Iwashita

发布于 2026-04-16

📖 1 分钟阅读🧠 深度阅读

CC BY 4.0

原作者： Kengo Suzuki, Takeshi Iwashita

原始论文采用 CC BY 4.0 许可（http://creativecommons.org/licenses/by/4.0/）。 ✨ 这是对下方论文的AI生成解释。它不是由作者撰写或认可的。如需技术准确性，请参阅原始论文。阅读完整免责声明

这是一篇关于如何让超级计算机“跑得更快、更省电”的学术论文。为了让你轻松理解，我们可以把这篇论文的核心内容想象成**“如何更高效地整理和运送一仓库的货物”**。

1. 背景：仓库里的混乱与瓶颈

想象一下，你有一个巨大的仓库（GPU 显卡），里面堆满了各种各样的货物（稀疏矩阵数据）。你的任务是把这些货物按照特定的规则，从 A 点运到 B 点（这叫“稀疏矩阵 - 向量乘法”，简称 SpMV）。

老问题：以前，仓库管理员（现有的算法）为了搬运方便，总是把货物按固定的大箱子（标准数据格式，如 FP32、FP64）打包。但是，很多货物其实很小，或者形状很怪。硬塞进大箱子里，不仅浪费空间（内存占用大），而且搬运工（内存带宽）每次都要搬很多没用的空气，导致速度上不去。
新趋势：现在的计算机越来越快，但搬运货物的速度（内存带宽）跟不上。所以，现在的核心任务不是让手更快，而是减少每次搬运的货物量，或者把货物打包得更紧凑。

2. 主角登场：PackSELL（智能打包法）

这篇论文提出了一种新的打包方法，叫 PackSELL。它就像是一个超级聪明的打包机器人。

它的两个独门绝技：

绝技一：只记“变化量”（Delta Encoding）

传统做法：假设货架上有货物在第 1 号位、第 5 号位、第 6 号位。传统方法会记录："1 号、5 号、6 号”。
PackSELL 做法：它发现货物是紧挨着的。于是它只记录："1 号，然后往右跳 4 格，再往右跳 1 格"。
比喻：就像你记电话号码，以前记"13800138000"，现在记"138 开头，后面全是 0"。只记“变化”，大大节省了记笔记的空间。

绝技二：把“位置”和“货物”塞进同一个口袋（Delta-Value Packing）

传统做法：位置记在一个本子上，货物放在另一个盒子里。搬运工要跑两趟，或者一次拿两个东西，很麻烦。
PackSELL 做法：它把“跳了几格”（位置变化）和“货物是什么”（数值）直接塞进同一个口袋里。
比喻：以前是“左手拿地图，右手拿包裹”。现在，它把地图画在包裹的包装纸上。一次伸手，既拿到了地图，也拿到了包裹。

3. 核心创新：灵活的“口袋”设计（精度无关）

这是这篇论文最酷的地方。

以前的限制：以前的打包方法规定，每个口袋必须正好能装下标准的“大苹果”（标准浮点数，如 FP32）。如果货物是“小苹果”（FP16）或者“奇形怪状的石头”（非标准格式），要么装不下，要么浪费空间。
PackSELL 的突破：它的口袋是可调节的！
- 你可以把口袋切分：左边留一点点给“位置变化”，右边留一大块给“货物”。
- 或者反过来：左边留一大块给“位置变化”，右边留一点点给“货物”。
- 比喻：就像是一个乐高积木式的收纳盒。如果你运的是大箱子，你就多留点空间给箱子；如果你运的是小珠子，你就多留点空间给位置信息。甚至，你可以发明一种全新的“货物包装法”（非 IEEE 标准格式），只要你能把“位置”和“货物”塞进这个 32 位的口袋里就行。

4. 实际效果：快如闪电

作者把这套方法在超级计算机（NVIDIA A100 GPU）上进行了测试：

速度提升：在处理那些货物分布比较均匀的仓库时，PackSELL 比目前业界最强的标准方法（NVIDIA 的 cuSPARSE）快了 1.63 倍。
精准度与速度的完美平衡：
- 通常，用“小盒子”（低精度，如 FP16）装东西，速度快但容易出错（货物压坏）。
- 用“大盒子”（高精度，如 FP32）装东西，准但慢。
- PackSELL 的魔法：通过灵活调整口袋大小，它竟然能用接近“小盒子”的速度，达到**“大盒子”的精准度**。
解决复杂问题：在解复杂的数学方程（线性方程组求解）时，使用 PackSELL 的方法，比传统方法快了 2 倍多。

5. 总结：这对我们意味着什么？

这就好比在快递行业：

以前：不管包裹大小，都塞进标准的大纸箱，浪费空间，运输慢。
现在：PackSELL 发明了一种智能压缩袋。它能根据包裹的大小和形状，自动调整压缩比例，把“地址”和“物品”完美融合。
结果：同样的卡车（内存带宽），现在能拉更多的货；或者拉同样的货，跑得更快、更省油。

一句话总结：
PackSELL 是一种超级灵活的打包技术，它通过把“位置信息”和“数据内容”压缩在一起，并允许自定义数据格式，让超级计算机在处理海量稀疏数据时，既快又准，还省内存。这为未来开发更高效的科学计算软件打开了新的大门。

1. 研究背景与问题 (Problem)

内存带宽瓶颈：随着 GPU 计算能力的提升，内存带宽与计算性能之间的差距日益扩大。对于受内存带宽限制的 SpMV 操作，减少数据移动（Data Movement）至关重要。
混合精度趋势：为了利用低精度算术单元（如 FP16），混合精度算法（如 Krylov 子空间方法）日益流行。然而，现有的高性能 SpMV 内核大多针对传统的 IEEE 754 格式（FP64, FP32）设计，且通常假设数据按字节对齐。
现有格式的局限性：
- 现有的压缩技术（如索引压缩、值压缩）通常将索引和数值分开处理，且受限于硬件友好的字节对齐要求。
- 这导致许多非字节对齐的自定义格式（如非 IEEE 浮点数、少比特整数）难以高效利用，限制了数据表示的灵活性和性能优化空间。
核心痛点：缺乏一种能够统一支持多种数据表示（包括非标准格式），同时通过压缩索引和数值来减少内存占用并提升 GPU 性能的稀疏矩阵格式。

2. 方法论 (Methodology)

作者提出了 PackSELL，一种基于切片 ELLPACK (SELL) 格式的改进方案。其核心创新在于联合设计数据表示、索引编码和内存布局。

2.1 核心机制

列索引的差分编码 (Delta Encoding)：
- 不再存储原始列索引，而是存储当前非零元素列索引与前一个非零元素列索引的差值（Delta）。
- 对于带状矩阵（常见于科学计算），这种差值通常很小，可以用较少的比特位表示。
- 引入了偏移量 $d_i$ 来处理每行的第一个非零元素。
差值 - 数值打包 (Delta-Value Packing)：
- 单字存储：将每个“差值（Delta）”和对应的“非零值（Value）”打包进一个 $W$ 位的字（Word，通常为 32 位）中。
- 位分配灵活性：字结构包含：
  - 标志位 (Flag)：1 位。
  - 差值位 (D bits)：存储差分索引。
  - 数值位 (V bits)：存储矩阵值。
  - 满足 $W = V + D + 1$ 。
- 动态调整：通过调整 $D$ 和 $V$ 的分配，可以灵活支持不同的数据格式（如 FP16、自定义浮点格式 E8MY、定点数等），甚至支持非 IEEE 754 格式。
溢出处理与虚拟元素：
- 如果差值过大导致 $D$ 位溢出，PackSELL 使用标志位为 0 的特殊编码，将 $W-1$ 位全部用于存储差值（此时不存储数值）。
- 为了保持结构一致性，会在稀疏矩阵中插入“虚拟元素”（Dummy Element），其差值为 0，标志位为 1，从而允许后续元素正常编码。
SELL 风格对齐：
- 保留了 SELL 的切片（Slice）结构，将连续 $C$ 行分为一组，组内填充使每行元素数相同，以平衡 GPU 线程负载。
- 支持行重排（Row Permutation，SELL-C- $\sigma$ ）以减少填充，并针对 PackSELL 的虚拟元素插入进行了优化。

2.2 算法实现

运行时解压：在 SpMV 执行过程中，GPU 线程即时解压打包的数据（提取差值和数值），无需预先解压，保持了内存访问的高效性。
无分支解压：设计了基于位操作的无分支（Branch-free）解压逻辑，利用标志位动态调整移位宽度，最大化 GPU 并行效率。

3. 主要贡献 (Key Contributions)

新型稀疏矩阵格式 PackSELL：
- 首个能够统一支持多种数据表示（包括非字节对齐、非 IEEE 格式）的高性能 GPU SpMV 格式。
- 通过差值编码和打包技术，显著减少了内存占用和数据移动。
性能与精度的权衡分析：
- 证明了通过调整位分配，可以在保持 FP32 级别精度的同时，达到甚至超越 FP16 格式的性能。
混合精度求解器的应用验证：
- 将 PackSELL 集成到 Krylov 子空间方法（如 F3R 求解器和内 - 外共轭梯度法 IO-CG）中，展示了其在实际科学计算场景中的加速效果。
- 揭示了非 IEEE 格式在混合精度求解器中的潜在优势。

4. 实验结果 (Results)

实验在 NVIDIA A100 GPU 上进行，使用了 SuiteSparse 矩阵集合中的 435 个矩阵。

4.1 独立 SpMV 内核性能

FP16 场景：
- 在 292 个适合 SELL 格式的矩阵上，PackSELL (FP16) 比 NVIDIA cuSPARSE 的 SELL 内核快 1.63 倍。
- 相比 cuSPARSE 的 CSR 和 DASP 格式，最大加速比分别达到 3.01 倍和 5.09 倍。
- 对于非零元素密集且分布均匀的矩阵，PackSELL 通过减少内存占用（压缩率接近理论下限 0.75）实现了显著加速。
非 IEEE 格式场景：
- 使用自定义的 E8MY 格式（8 位指数，可变尾数），PackSELL 在 $D=12$ 时，性能优于 FP16 cuSELL，且反向误差（Backward Error）远低于 FP16，接近 FP32 水平。
- 证明了 PackSELL 能够根据矩阵特性灵活调整指数和尾数位数，解决 FP16 精度不足或 BF16 尾数过短的问题。

4.2 稀疏线性求解器性能

F3R 求解器 (FP16 启用)：
- 使用 PackSELL 的 F3R 求解器比标准 FP16-F3R 快 1.32 倍，比全精度 FP64-F3R 快 2.64 倍。
内 - 外共轭梯度法 (IO-CG)：
- 使用 PackSELL (E8MY 格式) 的 IO-CG 求解器，在保持 FP32 级别收敛精度的同时，比标准 FP64 PCG 求解器快 2.09 倍。
- 相比之下，直接使用 FP16 或 BF16 的 IO-CG 由于精度不足导致迭代次数增加，性能反而不如 FP32 版本。PackSELL 通过微调尾数长度，完美平衡了精度与性能。

5. 意义与结论 (Significance & Conclusion)

突破数据表示限制：PackSELL 打破了传统稀疏矩阵格式对字节对齐和标准 IEEE 格式的依赖，为利用自定义低精度格式（如非 IEEE 浮点、定点数）提供了高效的底层支持。
解决精度与性能的矛盾：在混合精度计算中，FP16 往往精度不足，而 FP32 内存开销大。PackSELL 允许用户“按需分配”比特位，在 FP16 的内存带宽下实现接近 FP32 的精度和性能。
推动混合精度算法发展：实验表明，PackSELL 使得在 Krylov 子空间方法中使用非标准格式成为可能，为未来设计更高效的混合精度求解器（如内 - 外迭代法）奠定了基础。
未来展望：虽然目前主要针对 SELL 适合的大规模规则矩阵，未来工作将探索将其扩展至 CSR 格式以处理不规则矩阵，并适配更多硬件平台。

总结：PackSELL 通过创新的“差值 - 数值打包”机制，成功将稀疏矩阵的索引压缩与数据表示灵活性相结合，在 GPU 上实现了超越现有库（cuSPARSE）的高性能 SpMV，并显著提升了混合精度求解器的整体效率。