4、稀疏矩阵存储格式概览：COO、CSR、CSC、ELL、BSR等格式的优缺点对比

TinyML 模型在部署到微控制器（MCU）、端侧 NPU 或 DSP 时，权重矩阵和激活值矩阵往往呈现出极高的稀疏性（通常由剪枝产生，稀疏度可达 70%~95%）。如果仍然使用稠密矩阵的存储与计算方式，不仅浪费宝贵的 Flash 和 SRAM，还会产生大量无效的乘加运算。稀疏矩阵存储格式的选择，直接决定了推理引擎的访存带宽、索引开销、并行效率以及算子内核的复杂度。本章将系统对比 COO、CSR、CSC、ELL、BSR 五种主流格式的存储结构、优缺点与适用场景，帮助你在实际 TinyML 工程中做出合理的格式选型。

稀疏矩阵存储格式选型决策框架 原始稀疏矩阵 非零元 + 行列索引 COO CSR / CSC ELL BSR 选型关键维度 稀疏度 / 硬件架构 / 算子类型 / 内存对齐 MCU (Cortex-M) CSR / BSR 优先，Flash 紧凑 端侧 NPU / DSP ELL / BSR 利于 SIMD 向量化 FPGA 定制加速器 COO 便于硬件调度，但索引开销大 核心权衡：索引内存开销 vs 计算并行度 vs 格式转换成本 没有绝对最优格式，只有针对特定硬件与稀疏模式的“最合适”格式

上图给出了格式选型的整体决策框架。实际工程中，我们需要根据目标硬件的存储层次、算子的计算模式（如矩阵-向量乘、矩阵-矩阵乘、卷积 im2col 后的 GEMM）以及稀疏度分布特征来综合判断。下面逐一剖析各格式的细节。

4.1 COO（Coordinate List）格式：最直观的稀疏表达

核心原理

COO 格式使用三个等长数组分别存储非零元的行索引、列索引和数值。假设矩阵有 nnz 个非零元，则三个数组长度均为 nnz。对于矩阵中的每个非零元 A[i][j] = v，在 COO 中记录为 row[k]=i, col[k]=j, val[k]=v。这种格式不要求索引有序，构建时只需扫描原矩阵即可。

判断方法 / 操作流程

在 TinyML 中，COO 通常作为中间格式使用。例如，训练后剪枝导出的稀疏权重，首先以 COO 形式导出，再转换为其他格式。判断是否直接使用 COO 的标准：

  • 矩阵规模较小（如全连接层权重 256×256），且 nnz 小于 1000 时，COO 的索引开销尚可接受。
  • 需要频繁增量修改稀疏结构（如在线学习场景），COO 的插入/删除操作最方便。
  • 硬件支持 gather 操作（如某些 DSP 的 DMA 引擎），可直接消费 COO 数据。

案例拆解：1×1 卷积核的 COO 表达

假设一个 3×3 的稀疏矩阵，非零元位置为 (0,2)=5, (1,0)=3, (2,1)=7。COO 存储为：

row = [0, 1, 2]
col = [2, 0, 1]
val = [5, 3, 7]

在 Cortex-M4 上，若使用 CMSIS-NN 的稀疏推理函数，COO 需要额外计算每个非零元的目标输出位置，导致循环内多一次乘法和加法。实测 8 位量化下，COO 的索引读取开销占整体访存带宽的 40% 以上，因此仅适合极稀疏（>95%）且非零元分布均匀的场景。

常见误区与总结

风险提示：COO 的索引数组是 int16 或 int32 类型，在 8 位 MCU 上会显著增加 Flash 占用。例如 1000 个非零元，索引需要 4KB（int16）或 8KB（int32），而数值本身仅 1KB（int8）。切勿在内存受限设备上直接使用 COO 作为最终推理格式。

COO 的优点是构建简单、格式通用；缺点是索引冗余大、无法直接支持行优先的连续内存访问。它更适合作为转换枢纽，而非最终存储格式。

4.2 CSR（Compressed Sparse Row）与 CSC（Compressed Sparse Column）

核心原理

CSR 将行索引压缩：使用三个数组 values（非零元值）、col_indices（列索引）、row_ptr（每行起始偏移）。row_ptr 长度为 rows+1，其中 row_ptr[i] 表示第 i 行的第一个非零元在 values 中的位置，row_ptr[i+1]-row_ptr[i] 即为第 i 行的非零元个数。CSC 是 CSR 的转置版本，压缩列索引。

判断方法 / 操作流程

选择 CSR 还是 CSC，取决于算子的访存模式：

  • 矩阵-向量乘（GEMV）：CSR 按行访问，适合权重矩阵左乘输入向量（y = Wx）。
  • 反向传播或梯度计算：CSC 按列访问，适合 y = W^T x 的转置乘。
  • 卷积 im2col 后的 GEMM：通常将输入 patch 组织为行主序，CSR 更自然。

在 TinyML 中，CSR 是最常用的格式，因为大多数推理框架（如 TensorFlow Lite Micro、CMSIS-NN）的稀疏算子原生支持 CSR。

案例拆解：CSR 在 MLP 推理中的内存收益

考虑一个 512×512 的全连接层，稀疏度 90%。稠密存储需要 512×512×1B = 256KB（int8）。CSR 存储：

values: 512×512×10% = 26,214 个 int8 → 26.2KB
col_indices: 26,214 个 int16 → 52.4KB
row_ptr: 513 个 int16 → 1KB
总占用 ≈ 79.6KB，节省 69%

在 STM32F746（1MB Flash）上，该层从稠密 256KB 降至 79.6KB，使得整个模型可以放入片内 Flash。推理时，CSR 的 GEMV 循环只需遍历非零元，计算量从 262K MACs 降至 26K MACs，加速约 10 倍（理想情况）。

常见误区与总结

经验提醒：CSR 的 row_ptr 使用 int16 还是 int32 需要权衡。当 nnz < 65536 时，int16 足够，可节省一半索引内存。但要注意对齐：某些 MCU 的 DMA 要求 4 字节对齐，int16 数组可能需要 padding。

CSR 的缺点是行内非零元不连续时，col_indices 的随机访问会导致 cache miss。对于高度稀疏且行内分布极不均匀的矩阵，CSR 的负载均衡较差。

4.3 ELL（ELLPACK）格式：面向 SIMD 的均匀化存储

核心原理

ELL 格式假设每行最多有 K 个非零元（K 取所有行非零元数的最大值）。使用两个 rows×K 的二维数组：data 存储非零元值，col_idx 存储对应的列索引。不足 K 的行用 0 填充。这种格式将稀疏矩阵“稠密化”为固定宽度的二维数组，便于向量化加载。

判断方法 / 操作流程

ELL 适用于以下条件：

  • 各行非零元数量差异不大（方差小），否则填充率低，浪费内存。
  • 目标硬件支持 SIMD（如 ARM NEON、RISC-V P 扩展），可一次性处理多行数据。
  • 矩阵宽度（列数）较大，且 K 值较小（如 K ≤ 8）。

操作流程：先统计每行非零元数，确定 K；然后按行填充 data 和 col_idx；最后将两个数组展平为一维数组以适配 DMA 传输。

案例拆解：3×4 矩阵的 ELL 填充

矩阵：

| 1 0 0 2 |
| 0 3 0 0 |
| 4 0 5 0 |

每行非零元数分别为 2、1、2，K=2。ELL 存储：

data   = [[1,2], [3,0], [4,5]]
col_idx= [[0,3], [1,0], [0,2]]

在带有 NEON 的 Cortex-A 系列（非 MCU）上，ELL 的 GEMV 可以按行向量化：每次处理 4 行，每行 K 个元素，使用 vld1q_s16 加载列索引，vmlaq_s16 乘加。相比 CSR 的标量循环，加速比可达 3~4 倍。但在 Cortex-M 系列（无 SIMD）上，ELL 的优势不明显，反而因填充浪费内存。

常见误区与总结

风险提示：ELL 的填充开销在稀疏度极高（>95%）且行间分布不均时非常严重。例如某卷积层 3×3 卷积核，每行非零元数从 1 到 9 不等，K=9 时填充率可能超过 50%，内存反而比 CSR 更大。

ELL 的核心价值在于消除索引间接跳转，使内存访问模式可预测。它适合规则稀疏（如带状矩阵、卷积核剪枝后保持固定非零模式）的场景。

4.4 BSR（Block Sparse Row）格式：块级压缩

核心原理

BSR 将矩阵划分为固定大小的块（如 4×4、8×8），仅存储包含非零元的块。每个块内部使用稠密存储，块间使用类似 CSR 的行指针和列索引。BSR 的索引粒度从单个元素提升到块，大幅减少索引数量。

判断方法 / 操作流程

BSR 的适用条件：

  • 稀疏结构具有块状聚集性（如硬件剪枝按 block 进行，或结构化剪枝保留连续区域）。
  • 目标硬件支持块矩阵乘（如某些 NPU 的脉动阵列固定为 4×4 或 8×8）。
  • 需要减少索引内存占用：块越大，索引越少，但块内填充可能增加。

操作流程：确定块大小（通常为 4 或 8）；将矩阵划分为块；扫描块，记录非零块的行块索引、列块索引和块内稠密数据。

案例拆解：4×4 块 BSR 在卷积中的应用

假设一个 8×8 的权重矩阵，非零元集中在四个 4×4 块中（左上、右上、左下、右下各一个）。使用 4×4 块 BSR：

block_row_ptr = [0, 2, 4]  // 两个行块，每行 2 个非零块
block_col_idx = [0, 1, 0, 1]
block_data    = 4 个 4×4 稠密矩阵，每个 16 个 int8

总存储：4×16×1B（数据）+ 4×1B（列索引）+ 3×1B（行指针）≈ 71B。而 CSR 需要存储所有非零元（假设每个块内 16 个元素全非零，共 64 个非零元）：64B（值）+ 64×2B（列索引）+ 9×2B（行指针）≈ 210B。BSR 节省约 66% 内存。在支持块矩阵乘的 NPU 上，BSR 可直接映射到硬件指令，无需额外索引解析。

常见误区与总结

经验提醒：BSR 的块大小选择需权衡：块越大，索引节省越多，但块内零元填充也越多。建议对实际稀疏模式做统计分析，选择使“块内非零元密度 × 块数量”最大化的块大小。

BSR 的缺点是灵活性差：如果非零元分散且不构成块，填充率会急剧下降。它更适合结构化剪枝（如 N:M 剪枝、块剪枝）产出的模型。

4.5 格式对比与选型决策表

格式索引内存开销计算并行度构建复杂度适用硬件典型场景
COO高（2×nnz 索引）低（随机访问）最低通用格式转换、调试
CSR中（nnz + rows）中（行内连续）中MCU、CPU全连接层、GEMV
CSC中（nnz + cols）中（列内连续）中MCU、CPU转置乘、反向传播
ELL中高（rows×K）高（SIMD 友好）低DSP、NEON规则稀疏、卷积
BSR低（块级索引）高（块矩阵乘）高NPU、FPGA结构化剪枝、卷积

4.6 实战选型流程与综合建议

操作流程

  1. 统计稀疏模式：分析权重矩阵的行非零元分布、块聚集性、最大行非零元数。
  2. 确定硬件约束：检查目标 MCU/NPU 是否支持 SIMD、DMA 对齐要求、Flash 容量。
  3. 初步筛选：若稀疏度 > 90% 且行分布均匀 → CSR；若行分布不均但块状明显 → BSR；若硬件支持 SIMD 且 K 值小 → ELL。
  4. 原型验证：在真实硬件上运行 GEMV 基准，测量推理延迟和 Flash 占用。
  5. 格式转换：使用脚本将训练导出的 COO 转换为目标格式，注意字节序和对齐。

综合建议

工程经验：在绝大多数 TinyML 场景（Cortex-M 系列）中，CSR 是“最不坏”的选择——它平衡了内存效率、构建复杂度和算子实现难度。如果使用 CMSIS-NN，其稀疏函数原生支持 CSR 格式。只有在硬件明确支持块运算（如 ARM Ethos-U NPU）时，才优先考虑 BSR。ELL 在 MCU 上收益有限，除非你使用带有 SIMD 扩展的高端 MCU（如 Cortex-M55 的 MVE）。

常见误区总结

  • 误区一：认为 COO 最节省内存。实际上 COO 的索引开销最大，仅适合极稀疏且小规模矩阵。
  • 误区二：盲目追求 ELL 的 SIMD 加速，忽略了填充开销。在稀疏度 95% 以上时，ELL 的内存可能比稠密还大。
  • 误区三：忽略格式转换成本。在 MCU 上运行时，如果从 Flash 加载 CSR 数据后需要转换为其他格式，会消耗大量额外周期。应尽量直接使用 Flash 中存储的格式。
  • 误区四：不检查索引类型宽度。int32 索引在 8 位 MCU 上会拖慢访存速度，应使用 int16 或 int8（当 nnz < 256 时）。
← 上一章 📖 返回目录 下一章 →