1. 稀疏计算导论与性能瓶颈定位

稀疏计算并不是一种“特殊算法”，而是对一类数据形态的统称：当矩阵、图结构或张量中绝大多数元素为零（或可视为无效）时，只对非零元素及其索引进行计算与存储，从而避免大量无意义的乘加与访存。它广泛出现在科学计算（稀疏矩阵向量乘 SpMV）、图计算（PageRank、BFS、连通分量）、稀疏神经网络（剪枝后的权重、Embedding 查表）以及推荐系统等场景中。理解稀疏计算的第一步，是认识到它的性能瓶颈与稠密计算截然不同——稠密计算是“算力受限”，而稀疏计算往往是“访存受限 + 控制流不规则”。

从三个真实场景看稀疏性从何而来

以 SpMV 为例，设矩阵 A 为 n×n、非零元个数为 nnz，向量为 x，计算 y = A·x。稠密实现需要 n² 次乘加，而稀疏实现只需 nnz 次乘加，当 nnz/n² 很小（例如 0.1%～1%）时，理论计算量下降两到三个数量级。但代价是：每个非零元都要额外携带列索引，且访问 x 的位置由索引决定，无法像稠密那样顺序流式读取。图计算中，邻接表天然稀疏，一次 BFS 扩展只访问当前层顶点的邻居，访问模式随图结构剧烈变化。稀疏神经网络中，剪枝后权重矩阵的非零分布往往呈块状或随机状，Embedding 查表则是典型的“按索引随机取行”。

这三个场景的共同点是：有效计算量小，但访存地址不可预测。这正是稀疏计算性能分析的核心出发点。

三大核心挑战

不规则访存。稀疏格式通常用“值数组 + 索引数组”表示，例如 CSR 格式中，行指针 row_ptr、列索引 col_idx、非零值 val 三个数组配合完成一次 SpMV。计算 y[i] = Σ val[k]·x[col_idx[k]] 时，x 的访问地址由 col_idx[k] 决定，属于间接寻址（gather）。这类访问难以被硬件预取器识别，缓存命中率低，且每次访问都可能触发一次新的缓存行加载。若一个缓存行 64 字节、每元素 4 字节，理想情况下一次加载可服务 16 个连续元素，但随机索引下可能只用到 1 个，有效带宽利用率大幅下降。

负载不均衡。稀疏矩阵各行非零元数量差异很大，若按行并行分配给线程，非零元多的行会成为“长尾”，导致部分线程早早空闲、部分线程仍在计算。图计算中顶点度数分布常呈幂律，少数高度顶点主导了工作量，并行扩展时同样出现严重倾斜。负载不均衡直接表现为并行加速比随线程数增加而饱和甚至下降。

低计算密度。计算密度指每字节访存所对应的浮点运算次数。稠密矩阵乘的密度可达 O(n)，而 SpMV 每次非零元只做 1 次乘加，却要读取 val、col_idx 以及间接访问 x，计算密度通常远低于 1 FLOP/Byte。这意味着即使算力充足，性能也被内存带宽和延迟卡住，属于典型的 memory-bound 问题。

建立整体问题框架：先定位，再优化

面对一个稀疏计算内核，优化的第一步不是急着换格式或加线程，而是判断它到底卡在哪一类瓶颈上。一个实用的定位方法是做“三看”：看计算密度、看访存效率、看并行效率。

计算密度可以用一个简单估算：统计内核每处理一个非零元所执行的浮点运算次数，再除以该非零元平均带来的访存字节数。以 CSR-SpMV 为例，每个非零元需要读 val（4 或 8 字节）、读 col_idx（4 字节）、间接读 x（4 或 8 字节，且可能未命中缓存）、写 y（累加，通常驻留寄存器或缓存）。若按 4 字节单精度估算，每非零元至少 12 字节访存、2 次浮点运算，密度约 0.17 FLOP/Byte，远低于现代 CPU 的 10+ FLOP/Byte 和 GPU 的更高比值，因此几乎必然 memory-bound。这个估算不需要跑性能计数器，就能在写代码前给出方向性判断。

访存效率则要看缓存命中与有效带宽。可以用一个教学示例来体会：假设矩阵规模 100 万×100 万、nnz = 500 万（平均每行 5 个非零元），col_idx 随机分布。若 L2 缓存为 1MB、x 向量为 4MB，则 x 无法全部驻留，间接访问的命中率会明显下降。此时把 x 分块、让一个线程块只处理列索引落在同一分块内的非零元，就能把随机访问局部化，这是“分块 + 重排”策略的由来。注意这些数字是用于说明量级关系的示例假设，实际值需以目标平台实测为准。

并行效率要看任务划分粒度。按行划分时，若某一行有 10 万个非零元而其余行平均只有 5 个，则一个线程承担了绝大部分工作。解决思路包括按非零元总数均分（而非按行数均分）、对超长行做行内拆分、或采用动态调度。判断是否均衡，可以观察各线程处理非零元数的最大值与平均值之比，比值接近 1 说明划分较均匀，明显大于 1 则存在长尾。

存储策略为何是稀疏优化的主战场

由于稀疏计算普遍 memory-bound，存储格式与数据布局的选择往往比指令级优化更能决定性能。CSR 适合按行遍历、行长度较均匀的矩阵；CSC 适合按列访问；COO 结构简单、便于构建和并行生成，但遍历时索引开销大；块稀疏（BSR）把非零元组织成固定小块，能提高索引复用和访存连续性，适合非零元呈块状聚集的剪枝网络。选择格式的本质，是在索引开销、访存连续性、构建灵活性三者之间做权衡。后续章节会逐一展开这些格式的实现细节与调优方法，本节只需建立“格式即策略”的意识。

综上，稀疏计算的性能问题可以归纳为一条主线：稀疏数据形态带来不规则访存与低计算密度，进而使内核受限于存储层次；行/顶点工作量差异又带来并行负载不均衡。优化的整体框架因此分为两层——存储层解决“数据怎么放、怎么取”，并行层解决“工作怎么分、怎么调度”。先把瓶颈定位清楚，再在这两层中选择匹配的手段，才能避免盲目优化。