稀疏二进制矩阵乘法SpGEMM转换为分块形式是否有实际价值？

结论先行 #

分块稀疏矩阵乘法（SpGEMM）并非在所有场景下都能带来加速，你当前观测到块越小速度越慢，是你的实现方式和应用场景共同导致的。

为什么你的分块版本没有加速 #

• 额外开销盖过了分块收益：你现在的分块逻辑需要重复处理块间的OR合并操作（就是你---OR---注释段的代码），块越小，合并的次数越多，还要伴随多次标记位重置、结果数组重分配、行排序的额外开销，这些额外计算直接抵消了分块可能带来的收益。
• 没有利用到分块的核心优势：分块SpGEMM的设计初衷是优化访存局部性，让A的行块、B的列块能全部放进CPU缓存，减少随机访存的延迟。但你现在所有矩阵还是用全局CSR格式存储，计算每个块的时候依然要随机访问整个B矩阵的行数据，完全没有享受到缓存优化的收益。
• 标记数组的缓存优势被破坏：你当前用的稠密布尔标记数组xb大小为5e6字节（约5MB），刚好可以放进主流CPU的L2缓存，你做分块之后重复擦写xb，反而会把原本缓存中存储的B矩阵行数据挤出去，进一步拉高访存开销。

分块SpGEMM的适用场景 #

分块并非没有价值，它在以下场景下收益会非常明显：

• 矩阵规模极大：当矩阵维度超过1e8时，全局的稠密标记数组大小会超过CPU三级缓存容量，这时候分块可以把标记数组的大小降到和块维度一致，大幅降低访存开销。
• 并行计算场景：你现在做的是串行实现，分块的收益本来就不明显，要是做多核CPU并行、GPU加速的SpGEMM，分块是最基础的任务拆分手段，这时候收益才会体现。
• 极稀疏矩阵场景：如果参与计算的矩阵稀疏度极高，绝大多数块都是没有非零元的空块，分块可以提前跳过这些空块的计算，减少无效运算。

优化建议 #

• 先优化当前的串行版本：你当前每行计算结束后调用快速排序的开销占比很高，而D矩阵的行本身就是有序的，A*B生成的新元素如果提前做有序插入/合并，可以完全代替快排，能带来非常明显的提速。
• 调整分块的实现逻辑：不要用全局CSR格式存储分块，先把B矩阵按列分块转成CSC格式，每个块单独存储局部的索引，保证计算单个块的时候访问的B矩阵内存是连续的，才能享受到缓存收益。
• 匹配块大小和CPU缓存：分块的总数据量要适配你使用的CPU的三级缓存大小，不要用过小的块，建议从128x128、256x256这类尺寸开始测试，找到开销和缓存收益的平衡点。

内容的提问来源于stack exchange，提问作者pavlidic