极客工场

Appearance

共 5,114 字预计阅读约 17 分钟

稀疏矩阵存储格式：COO、CSR、ELL、Hybrid 与块稀疏，SpMV 的容量与带宽账 ​

更新时间：2026-09-25。上一篇 AI 加速器架构：脉动阵列 讲的是稠密矩阵乘如何在 PE 网格里复用数据；本篇转向它的反面——矩阵里绝大多数元素是 0 时，该怎么存、怎么算。这个问题横跨三个看似不相干的领域：科学计算的有限元矩阵、互联网的图邻接矩阵、剪枝后的神经网络权重，矩阵形态各异，账本却是同一本：SpMV（Sparse Matrix-Vector Multiply，稀疏矩阵向量乘）y = Ax。零不存、零不算，听起来简单，真正决定性能的是「非零元素的位置用什么方式记录」。与本篇配套的算法侧讨论见 结构化稀疏与剪枝。

本文要回答的问题 ​

  • 一个百万阶的稀疏矩阵为什么稠密存储根本放不下？省下来的除了容量还有什么？
  • COO、CSR、CSC 各自用哪几个数组描述同一个矩阵？为什么 CSR 是最通用的事实标准？
  • ELL 格式为什么在 GPU 上向量化效果好？行长度参差不齐时它怎样退化，Hybrid ELL+COO 又如何补救？
  • block sparse（块稀疏）为什么成为 AI 权重压缩的主流形态？它和非结构化稀疏差在哪里？
  • SpMV 的负载不均衡从哪来？典型 GPU SpMV 能跑出多少有效算力、吃掉多少带宽？

一、稠密存储为什么不行：容量与带宽两笔账 ​

先给一个有体感的例子。社交网络的邻接矩阵是 N×N 的方阵，N 为用户数；每个用户平均关注几百人，意味着每行只有几百个非零元素（non-zero，记为 nnz）。N = 100 万时，稠密存储 double 精度需要 8 × 10¹² 字节，也就是约 8 TB——而真实非零元素按平均每行 10 个算只有 1000 万个，数据本身不到 80 MB。差距是十万倍。有限元离散得到的刚度矩阵同理：网格节点上百万、每点只与周围十几个节点耦合；自然语言处理里的高维词共现矩阵、剪枝后的网络权重，密度（nnz 除以总元素数）普遍在 1% 到 0.01% 之间。

容量是第一笔账，带宽是第二笔，而且第二笔更致命。SpMV 对每个非零元素做一次乘加：y[i] += A[i][j] · x[j]，2 个 FLOP。稠密实现时，矩阵里每一个 0 都要从内存读进来、判断、跳过，算术强度被海量的零稀释到近乎为零。即使硬件带宽无限，把 8 TB 数据扫一遍只为了算 80 MB 的有效数据，本身就是荒谬的。稀疏存储的核心思想因此只有一句话：只存非零值，但必须同时携带「它在矩阵里的位置」这一索引信息。所有格式之争，争的都是这份索引信息的编码方式——用三个数组还是两个数组、按行组织还是按列组织、定长还是变长。

给一个贯穿全篇的 5×5 小矩阵，8 个非零元素，记为 a~h：

  • 第 0 行：a 在列 0、b 在列 2
  • 第 1 行：c 在列 1
  • 第 2 行：d 在列 0、e 在列 3、f 在列 4
  • 第 3 行：g 在列 2
  • 第 4 行：h 在列 4

后面各节都用它展示数组布局。先记住一笔经济账：每个非零元素的存储成本 = 数值本身（double 8 字节 / float 4 字节）+ 索引开销。索引设计得越省，每个 nnz 的单价越低；但越省的索引往往对矩阵规则性要求越高。格式选择本质是在「通用性」和「每 nnz 单价」之间下注。

把这笔账算到具体数字上。仍以 N=100 万、nnz=1000 万为例：稠密 double 约 8 TB；COO 用 double + 两个 int32 索引，每个非零元 16 字节，共约 160 MB；CSR 用 double + int32 列号，外加 400 万字节的行指针，共约 124 MB——相对稠密存储缩小了约六万七千倍，一张普通显卡的显存就能装下。换成 AI 常用的 float16 权重，数值部分减半，CSR 单价降到 6 字节。而如果用 16×16 块稀疏，索引几乎归零，理论占用逼近 20 MB 的纯数值下限。还要注意一个反直觉点：当矩阵小到能被缓存容纳时，稠密格式偶尔反而更快——没有索引解码、访存完全连续，单位非零元的计算效率最高。稀疏化不是免费午餐，它用索引开销和不规则访问换取容量，密度高过某个临界点（经验上常在 10%~20% 以上）之后，稠密存储重新成为更优解。

二、COO：三个等长数组，最好构造的坐标格式 ​

COO（Coordinate Format，坐标格式）最直白：每个非零元素用一个三元组 (row, col, value) 描述，落地为三个等长数组，按任意顺序排列即可。上例的 COO 表示为：

  • row = [0, 0, 1, 2, 2, 2, 3, 4]
  • col = [0, 2, 1, 0, 3, 4, 2, 4]
  • val = [a, b, c, d, e, f, g, h]
chip-design/expert/sparse-matrix-formats.md D2 示意图

COO 的优点全在「构造」上。逐行读文件、流式产生三元组直接 append，不需要预知每行有多少非零元，也不需要排序；从磁盘加载、网络传输、框架间交换数据，COO 都是最常见的中转格式。缺点同样明显：row 数组重复存储行号，上例中行号 2 出现了三次，索引开销最大；更麻烦的是 SpMV 时多个三元组可能贡献给同一个 y[i]，并行累加需要原子操作或分段归约，写冲突让 GPU 实现很吃亏（原子操作的争用模式与直方图统计同源，可对照 直方图与原子操作 理解）。因此工程上 COO 几乎不直接承担高性能计算，它的角色是「加载与构造格式」：进来是 COO，预处理转成 CSR/ELL 再算。

三、CSR：行指针取代行数组，最通用的事实标准 ​

CSR（Compressed Sparse Row，压缩稀疏行）把重复的行号压缩掉：三个数组变为行指针、列索引、数值。上例：

  • row_ptr = [0, 2, 3, 6, 7, 8]
  • col = [0, 2, 1, 0, 3, 4, 2, 4]
  • val = [a, b, c, d, e, f, g, h]

读法是：第 i 行的非零元位于 col/val 数组的 [row_ptr[i], row_ptr[i+1]) 区间。第 0 行有 2 个、第 1 行有 1 个、第 2 行有 3 个，行长度由相邻两个指针的差值给出。row_ptr 只需要 N+1 个整数而非 nnz 个，对 N 远小于 nnz 的常见矩阵是决定性的节省。

顺带说清 COO 到 CSR 的转换，这是实际工程里最常见的预处理路径：先按行号对三元组计数（一次直方图扫描得到每行 nnz），对计数做前缀和就得到 row_ptr，再把 col/val 搬运到对应区间。整个过程 O(nnz)，可并行，库函数一次调用完成；所以「数据以 COO 加载、内部转 CSR 计算」几乎是稀疏系统的标准流水线。

CSR 的访问模式天然适配 SpMV 的行结构：一个线程（或线程块）认领一行，从行指针一次定位，顺序扫该行的列号和数值，累加在自己的寄存器里，最后只写一次 y[i]——全程没有写冲突。按行切片做多核分发、按行做预条件、求行范数、矩阵转置之外的绝大多数稀疏运算，CSR 都能高效支持，这是它成为 cuSPARSE、MKL、Eigen 等库默认格式的原因。代价有两个：构造需要先知道每行的非零元数量（实践上常两遍扫描或由 COO 排序转换）；列方向访问（左乘、求 Aᵀx）变得低效，那是 CSC 的主场。CSC（Compressed Sparse Column）是 CSR 的列向镜像：col_ptr + row_idx + val，适合按列消费的算法，如单纯形法、某些图分析和列式存储的数据库内核。同构的思想在稀疏张量领域推广为 CSF（Compressed Sparse Fiber），思路一脉相承。

四、ELL：定长每行，为向量化而生 ​

ELL（ELLPACK）格式赌的是「每行非零元数量差不多」。设全矩阵最大行长度为 K，用两个 N×K 的定长数组分别存列号和数值，不足 K 的行用填充位补齐。上例 K=3：

  • col（按行）：[0,2,]、[1,,]、[0,3,4]、[2,,]、[4,,*]
  • val（按行）：[a,b,]、[c,,]、[d,e,f]、[g,,]、[h,,*]
chip-design/expert/sparse-matrix-formats.md D2 示意图

ELL 的存储里没有行指针，第 i 行的起点就是 i×K，地址计算退化为乘法；更关键的是向量化：GPU 上让一个线程固定处理一行、所有线程在第 t 拍统一访问第 t 个槽位，warp 内访存地址连续、无分支，完美贴合 SIMT 的合并访问要求。规则网格导出的有限元矩阵（每行都是固定的模板邻居数）上，ELL 的 SpMV 常比 CSR 快一倍上下。

但 K 由最长的行决定，填充率是它的阿喀琉斯之踵。上例已经能看出：8 个有效值占 15 个槽位，近一半是填充。真实图矩阵遵循幂律分布，绝大多数行只有几个非零元、极少数枢纽行有成千上万，ELL 会把这些矩阵填出天文数字的废槽，不仅浪费容量，所有线程还要陪着最长行空转 K 拍。

Hybrid（ELL+COO）是 Bell 与 Garland 在 2008 年给出的经典解法：取一个阈值 K（典型取行长度分布的某个分位），每行前 K 个非零元进 ELL 主体，超长行多出来的尾部非零元全部进 COO 溢出区。绝大多数矩阵元素享受 ELL 的规整向量访问，只有占比很小的枢纽行走 COO 路径、用原子操作累加，整体带宽利用率显著优于纯 CSR 或纯 ELL。这一策略长期是 cuSPARSE 稀疏库的默认内核之一，也是理解「规则部分专用化、不规则部分兜底」这类混合设计的范本。

五、Block sparse：把块当成原子单位的 AI 权重格式 ​

前述格式都以单个标量非零元为单位。块稀疏（block sparse）换了个粒度：把矩阵划分为 B×B 的小块，整块要么全零、要么稠密，索引只需记录非零块的位置，块内元素不再带任何索引。比如 16×16 的块，一个块索引（4 字节）覆盖 256 个 float 值，索引均摊到每个权重上只有 0.0156 字节，几乎可以忽略。

这种设计对 AI 场景特别契合。其一，剪枝若按块进行（整块权重一起置零），压缩后的矩阵天然是块稀疏，结构化的零分布让稠密 GEMM 内核只跳过整块、不破坏张量核心（Tensor Core）要求的规整形状；其二，现代大模型注意力计算按块组织（flash attention 之类的 tile 调度），块稀疏注意力可以直接在块掩码上跳过整块计算。实现层面，块稀疏通常存成 BCSR（block CSR）：行指针指向每个非零块、列号记录块坐标、值数组按 B×B 稠密小块连续排列。一次块 SpMV 的内层循环就是一个小稠密矩阵乘向量，可以用 SIMD 或张量指令整块吞吐，分支和地址计算的频率降到原来的 1/B²。块大小的选择遵循与 tile 相同的折中：块越大索引越省、内核越规整，但剪枝时被迫置零的有效权重也越多，模型精度损失越大；4×4 到 32×32 是常见区间，且块边长要对齐硬件矩阵指令的最小形状。

非结构化稀疏（零的位置任意）虽然压缩率上限更高，但每个非零元都要带索引、计算需要动态路由，在 脉动阵列 和张量核心上实际兑现的加速常大打折扣——这正是工业界普遍倒向 2:4 结构化稀疏和块稀疏的根本原因，算法侧的取舍详见 结构化稀疏与剪枝。

六、格式总览、负载不均衡与 GPU SpMV 实测量级 ​

格式核心数组优点缺点典型场景
COOrow / col / val最好构造，可无序追加，加载友好索引最贵，并行累加有写冲突文件加载、数据交换、溢出兜底
CSRrow_ptr / col / val行访问快、无写冲突、最通用构造需知行长，列访问慢CPU/GPU SpMV 事实标准、预条件
CSCcol_ptr / row / val列向访问高效行向访问慢单纯形、列式算法、Aᵀx
ELLN×K 定长 col/val无行指针，SIMD/SIMT 向量化极好行长不均时填充爆炸规则模板矩阵、有限元
Hybrid ELL+COOELL 主体 + COO 尾部兼顾规整访问与长尾覆盖阈值需调，实现复杂GPU 图矩阵 SpMV
block sparse块坐标 + 稠密块数据索引均摊极低，保规整计算要求零呈块状分布AI 权重、块稀疏注意力

除了表中六种主流格式，工程中还能见到一些特化变体，了解它们有助于判断格式设计的边界。DIA（Diagonal）只记录非零对角线的偏移与数据，对带状矩阵（如三对角、五对角）比 CSR 更省，PDE 一维/二维离散中常见；SELL（SELL-C-sigma）按 C 行一组对 ELL 做切片、组内按行长排序，既保留向量化又压缩填充，是 CPU 端 SpMV 的高性能选择；CSR5、BCSR（块 CSR）则分别在向量化分段归约和块索引上做文章。它们的设计手法都能在前面的格式里找到原型：压缩重复索引、定长换向量、切块控填充。

负载不均衡是 SpMV 在并行硬件上的常驻敌人，根源是行长度分布。社交图、网页链接图的行长呈典型幂律：99% 的行长度不超过几十个非零元，而 1% 的枢纽行可能占掉总 nnz 的一半以上。CSR 按行静态分给线程时，分到枢纽行的线程要做几千次乘加，其余线程早已空转等待，warp 内还会因行长不同频繁分支，有效带宽在等待中流失。硬件层面的主流对策有三类：行切分（把超长行拆成多段分给多线程，段内用原子操作拼回）；按工作量装箱（把行打包成 nnz 总量相近的任务包再分发）；merge-based SpMV（把行指针与非零元两个序列想象成归并，线程认领等量的非零元工作量，彻底解耦行边界）。即使如此，不规则的 x[j] 访问（列号近乎随机）仍会带来缓存未命中，稀疏矩阵的性能对矩阵结构的依赖远大于对硬件峰值的依赖——同一个库、同一块卡，换一个矩阵性能相差数倍是常态。

最后给出实测量级，建立合理预期。每个非零元 SpMV 要读数值（8 字节）、列号（4 字节）和位置随机的 x[j]（约 8 字节，缓存命中可摊薄），合计约 12~20 字节换 2 个 FLOP，算术强度只有 0.1~0.17 FLOP/byte——它是教科书级的访存受限算子。一块 HBM 带宽约 900 GB/s 的数据中心 GPU，稠密双精度峰值近 10 TFLOPS，而 SpMV 实测有效算力通常只有十几到几十 GFLOPS，不足峰值的 1%；能跑到 HBM 带宽的六七成（约 150~600 GB/s，视矩阵规则度而定）就已属优秀内核。这组数字说明两件事：SpMV 优化的目标从来不是乘法器利用率，而是有效带宽和负载均衡；存储格式每省下一个索引字节，都直接折算成端到端时间。CPU 侧的图景相似但更复杂：标量 SpMV 受限于内存通道带宽，实测有效带宽常在每秒十几到几十 GB；只有规则矩阵配合 SELL 之类的向量格式，才可能逼近平台带宽上限。一个实用的排查顺序是：先算矩阵的行长度直方图判断是否规则（决定 CSR 还是 ELL/Hybrid），再用 roofline 核对实测带宽，带宽明显偏低时依次检查 x[j] 缓存命中、负载倾斜和原子争用——顺序反了很容易在内核微调上白费功夫。

这一篇在知识体系里的位置 ​

总结 ​

稀疏矩阵存储格式的本质是为「只存非零值」这件事设计索引：COO 用 row/col/val 三数组换取最好构造性、适合加载中转，CSR 用行指针把行号压缩掉、行访问无冲突而成为最通用标准，CSC 是其列向镜像；ELL 用定长行槽位换来完美的 SIMT 向量化，却在行长幂律分布时被填充拖垮，Hybrid ELL+COO 让规则部分走 ELL、超长尾部走 COO 兜底，成为 GPU 经典；block sparse 以块为索引单位把索引均摊到近乎为零，保住张量核心要求的规整性，是 AI 权重与块稀疏注意力的主流。SpMV 算术强度仅约 0.1 FLOP/byte，是纯粹的访存受限算子，GPU 实测有效算力常不足峰值的 1%，成败全在每 nnz 的存储单价、x[j] 访问局部性和行长不均带来的负载倾斜——选格式就是按矩阵的规则程度，在通用性、索引成本和向量化之间做交易。