CSR 格式基础

定义与定位

CSR 格式（Compressed Sparse Row，压缩稀疏行存储）是一种用于存储稀疏矩阵的压缩数据结构。它将矩阵按“行”进行组织，只保存非零元素及其对应的列位置，从而减少对空洞（零元素）的显式存储开销。与密集存储相比，CSR 在内存占用上更紧凑，并能在需要按行遍历、进行行相关计算的场景中提供较好的效率。

在工程实践中，CSR 往往被视为通用的基础稀疏表示之一：一方面结构清晰，便于实现与调试；另一方面适配了多数数值库中成熟的稀疏算子接口。

适用场景：稀疏矩阵与稀疏计算

CSR 主要适用于稀疏矩阵的算子实现，例如：

  • 数值计算中的线性代数运算（如迭代求解中的矩阵-向量乘）。
  • 图算法中的邻接/关联表示（当图以稀疏邻接关系描述时，矩阵按行存储相当自然）。
  • 科学计算中的离散算子（如有限差分/有限元产生的稀疏线性系统）。
  • 深度学习或张量计算中稀疏算子的实现（在满足稀疏结构较稳定或需要显式稀疏表示时）。

当矩阵的行结构较清晰，且计算模式以“按行推进”为主时，CSR 的优势更容易体现。

与其他稀疏格式的关系（COO/CSC/ELL等）

稀疏格式的差异通常体现在“压缩方向”与“访问形态”上。与 CSR 的关系可概括为：

  • COO（Coordinate list，坐标列表）：按（行、列）逐项记录非零元素，构建简单但存储与遍历开销往往更大；CSR 则把相同的行聚拢，更利于行遍历。
  • CSC（Compressed Sparse Column，压缩稀疏列存储）：与 CSR 对称，按列压缩；若主要计算以列访问为主，CSC 可能更合适。
  • ELL（ELLPACK）：为便于向量化，将每行的元素数对齐到固定长度；当稀疏度分布较均匀时，ELL 往往更适合，但在高度不均匀时可能浪费。
  • 其他变体（如分块稀疏、切片稀疏等）：通常针对特定结构（局部块、规则模式）优化访存或计算效率。

理解这些格式的对比，有助于在不同数据分布与算子需求下选择最合适的表示方式。

数据结构组成

row_ptr 行指针数组

row_ptr 是 CSR 的行边界索引数组，用于标识每一行在 col_ind 和 values 中的起止位置。若矩阵有 \(m\) 行，则 row_ptr 通常长度为 \(m+1\)。

常见约定下：

  • 第 \(i\) 行的非零元素位于 col_ind 和 values 的区间 \([\,row\_ptr[i],\; row\_ptr[i+1)\,)\)。
  • row_ptr[i] 与 row_ptr[i+1] 的差值对应该行非零元素的数量。

通过 row_ptr，程序无需扫描全体非零条目即可定位到某一行的有效数据范围。

col_ind 列下标数组

col_ind 数组与 values 一一对应，存储每个非零元素所在的列编号。其长度等于非零元素总数 \(nnz\)。

在区间 \([row\_ptr[i], row\_ptr[i+1])\) 内，col_ind 的元素依次给出了第 \(i\) 行中各非零元素的列位置。

values 非零元素数组

values 保存非零元素的数值部分，同样与 col_ind 一一对应，长度为 \(nnz\)。在数值计算中，values 的顺序与 col_ind 的列位置保持一致是关键条件。

如果某行中存在重复列的条目（例如构建阶段尚未合并），values 的处理策略（求和或覆盖）会影响最终矩阵含义；因此在构建策略中通常会讨论去重或聚合。

索引约定与长度关系

CSR 的索引约定需明确两个方面：行索引与列索引的取值范围，以及数组长度之间的关系。

常见关系如下：

  • row_ptr 长度：\(m+1\)（m 为行数）。
  • col_ind 和 values 长度：均为 \(nnz\)。
  • 对任意行 \(i\)：\(0 \le col\_ind[k] < n\)（n 为列数），其中 \(k \in [row\_ptr[i], row\_ptr[i+1])\)。
  • row_ptr 单调性：通常要求 row_ptr 非递减，且 row_ptr[0] 为 0，row_ptr[m] 为 nnz。

这些约束决定了 CSR 结构能否正确还原矩阵并支持安全的边界访问。

构建 CSR

从 COO 转换为 CSR

COO 以坐标对（行、列、值）形式存储非零元素。将 COO 转为 CSR 的常见流程：

  1. 统计每一行非零元素数量，得到每行的计数。
  2. 对计数做前缀和，构建 row_ptr，使其形成每行的段起止位置。
  3. 根据每个 COO 条目的行编号，将其放入 CSR 对应行的空位区间，并填写 col_ind 与 values。
  4. 若 COO 中存在同一行同一列的重复条目，需要在插入后或插入前进行合并策略（常见是求和）。

该转换依赖排序或散列定位；当 COO 中条目较多时，转换的性能主要由排序开销与内存访问模式决定。

从密集矩阵生成 CSR（筛除零元素）

从密集矩阵构建 CSR 通常遵循：

  1. 遍历密集矩阵的所有元素，但仅对非零元素进行记录。
  2. 对每一行统计非零个数，填充 row_ptr。
  3. 将非零元素的列下标写入 col_ind，将数值写入 values。

其核心是“筛除零元素”，因此密集矩阵中零元素占比越高，CSR 相对收益越明显。若矩阵尺寸较大，构建阶段可能受制于遍历成本与零判定开销。

行内元素排序与去重策略

CSR 的功能正确性与性能在一定程度上与行内条目的组织有关。常见策略包括：

  • 排序：对每一行的 col_ind 按列编号升序排序。这通常有利于在某些算子中进行二元归并、快速查找或更稳定的访存模式。
  • 去重：当同一行出现相同列的多个条目时，需要合并。常用做法是对行内条目按列排序后，检测相邻列相同的条目并对 values 聚合（如求和）。
  • 稳定性：在需要可复现实验结果时，合并与排序的确定性很重要；否则浮点数求和顺序不同可能引入微小误差。

这些策略并不总是必须，但在涉及矩阵乘、求解器或精度敏感场景时更常被采用。

构建复杂度与性能考量

构建 CSR 的复杂度通常由以下因素主导：

  • 输入规模：m、n 与 nnz 的数量级。
  • 预处理成本：如 COO 转换中的排序或分桶。
  • 额外操作：去重聚合需要额外遍历或排序。
  • 内存分配与写入：row_ptr 的长度较小，但 col_ind/values 的写入通常是主开销；预先分配容量可减少扩容成本。

工程上常见做法是先统计再一次性分配，避免在插入过程中频繁触发内存重分配，从而提升构建吞吐。

CSR 的基本操作

行遍历与快速定位

CSR 对行遍历非常友好。要遍历第 \(i\) 行，只需：

  • 取起止指针：start = row_ptr[i]，end = row_ptr[i+1]。
  • 在区间 [start, end) 内依次读取 col_ind[k] 与 values[k]。

这种定位方式把“寻找该行非零条目”的时间从扫描全体 nnz 降到与该行非零数成正比。

稀疏矩阵-向量乘（SpMV）

SpMV（Sparse Matrix-Vector multiplication）是 CSR 中最常见的操作之一。直观上，对每一行 \(i\)：

  • 计算 \(y[i] = \sum_{k=row\_ptr[i]}^{row\_ptr[i+1)-1} values[k] \cdot x[col\_ind[k]]\)。

CSR 使得每行的求和范围明确，适合并行化：不同线程可以处理不同的行区间。然而访存仍可能较不规则，因为 x 向量的访问索引由 col_ind 决定，列分布越随机，缓存命中往往越难。

稀疏矩阵-稀疏矩阵（SpGEMM）的直观思路

SpGEMM 指稀疏矩阵乘法，其难点常在于结果的非零结构需要动态生成。用 CSR 思路进行直观描述：

  • 对于结果矩阵的某一行，通常需要累积来自被乘矩阵行/列的贡献。
  • 实现上常采用“临时存储 + 累加 + 再整理”的流程：先根据运算规则收集候选列，再对相同列进行合并，最后把结果写回 CSR 结构。

由于非零模式通常不预知，SpGEMM 往往比 SpMV 更昂贵，且对构建策略（如何管理临时哈希表、如何控制中间膨胀）更敏感。

取子矩阵/行切片的实现要点

取子矩阵或行切片常见于分块算法、局部更新或采样。若要取第 \(r\) 到 \(r+t-1\) 行的切片：

  • 新的 row_ptr 由原 row_ptr 的对应段截取后再整体平移（使起点为 0）。
  • col_ind 与 values 需要将原区间 [row_ptr[r], row_ptr[r+t]) 的元素拷贝到新结构。
  • 若列范围也需要裁剪，则还需对 col_ind 做过滤与重映射。

实现时应保持边界一致：新行的非零数与新 row_ptr 的差值完全对应，避免越界与错位。

示例与直观理解

一个小矩阵到 CSR 的转换示例

考虑一个 \(3 \times 4\) 的矩阵： \[ A= \begin{bmatrix} 1 &amp; 0 &amp; 2 &amp; 0\\ 0 &amp; 3 &amp; 0 &amp; 4\\ 5 &amp; 0 &amp; 0 &amp; 6 \end{bmatrix} \] 其非零元素按行依次出现：

  • 第 0 行：列 0 -> 1，列 2 -> 2
  • 第 1 行：列 1 -> 3，列 3 -> 4
  • 第 2 行：列 0 -> 5，列 3 -> 6

则可以构造：

  • row_ptr = [0, 2, 4, 6]
  • col_ind = [0, 2, 1, 3, 0, 3]
  • values = [1, 2, 3, 4, 5, 6]

这里 row_ptr[0]=0 表示第 0 行从第一个非零条目开始；row_ptr[1]=2 表示第 0 行结束于第 2 个条目前。

读懂三数组如何还原矩阵

给定 row_ptr、col_ind、values，可以还原矩阵的“非零分布与数值”：

  • 对 i=0：区间 [0,2) -> col_ind[0]=0, values[0]=1；col_ind[1]=2, values[1]=2。
  • 对 i=1：区间 [2,4) -> col_ind[2]=1, values[2]=3；col_ind[3]=3, values[3]=4。
  • 对 i=2：区间 [4,6) -> col_ind[4]=0, values[4]=5；col_ind[5]=3, values[5]=6。

其余未被列出的格点默认为零，从而得到原矩阵。

常见错误示例（行指针越界、索引错位）

构建 CSR 时常见问题包括：

  • 行指针越界：row_ptr[m] 不等于 nnz，或某行的 start/end 组合超出 col_ind/values 的实际长度，会导致读取错误。
  • 索引错位：col_ind 与 values 的写入顺序不同步，造成列下标与数值对应关系错乱，结果矩阵将完全偏离预期。
  • 去重缺失：若输入中存在同列重复条目却未合并，最终矩阵含义可能不符合预期的线性代数定义。
  • 列索引范围错误：col_ind 中出现等于 n 或小于 0 的列编号，会破坏合法性约束。

在调试阶段，核对 row_ptr 的单调性、检查 col_ind 的范围以及验证各行非零数与输入统计一致，通常能快速定位问题。

兼容性与工程实践

与数值库/并行框架的接口形式

多数数值计算库将 CSR 作为通用输入结构，接口通常包含：

  • 指针数组 row_ptr（可带类型约定：32 位或 64 位索引）。
  • 列下标数组 col_ind。
  • 数值数组 values（可为单精度、双精度或其他标量类型）。
  • 矩阵维度与可能的非零数 nnz。

并行框架常要求额外的元信息，例如行数分段、线程分配策略或是否需要对行内条目排序，以适配其算子实现。

存储精度：数值类型与内存布局

values 的数值精度会直接影响精度与性能：

  • 单精度（float）通常更省内存且带宽需求更低，但可能带来数值误差。
  • 双精度（double）通常精度更稳定，但存储与计算成本更高。
  • 对于特殊类型（如复数或自定义标量），接口需要对应的乘加与类型兼容规则。

内存布局方面，CSR 的三个数组通常是独立连续的线性存储，能减少结构体嵌套带来的额外开销，并便于向量化或批处理。

线程并行与负载均衡（按行粒度）

并行化 SpMV 等按行计算的任务时，常见做法是“每个线程处理一批行”。负载均衡的关键在于不同线程分配的行，其非零元素数量应尽量接近，因为计算量与行的 nnz 成正比。

当稀疏性高度不均匀时，仅按行均匀切分可能导致某些线程早完成而另一些线程仍在工作。工程上可采用按非零计数划分区间或动态调度策略，以降低尾部延迟。

缓存局部性与访存优化

CSR 的访存不规则主要来自 col_ind 对 x 的间接访问。优化方向包括：

  • 预处理：对每行按列排序，提升局部访问模式的可预测性（尽管不保证显著提升，但有时能改善缓存行为）。
  • 重排：在不改变矩阵语义的前提下进行行/列重编号，以改善局部性（例如图重排思想）。
  • 并行与批处理：将多个向量计算或多次 SpMV 合并在合适的数据布局下，减少重复加载。

这些手段通常需要结合具体硬件与数据分布评估收益。

变体与扩展

支持对角/块结构的改进思路

当稀疏矩阵呈现明显的结构（例如对角占比更高或存在块状非零），可以在 CSR 的基础上做扩展：

  • 对角增强：对角元素单独存储或提升其访问效率，减少对一般路径的依赖。
  • 块稀疏：把连续的列区间视为小块，减少索引开销并提高算子利用率。

这类改进通常以减少间接访问、提高数据复用为目标，但会增加实现复杂度。

加权或带掩码的 CSR 扩展

在某些模型中，并非所有非零条目都需要参与计算，或者非零条目带有额外权重/门控信息。扩展形式包括：

  • 带掩码：对某些条目启用/禁用，计算时根据掩码跳过。
  • 加权 CSR：额外存储与 values 对齐的权重或系数，使乘加过程包含额外因子。
  • 稀疏正则项相关结构：在优化或训练阶段需要对稀疏模式进行统计或约束时引入相关数据。

这种扩展的核心在于保持索引结构与条目对齐，同时控制额外存储对内存带宽的影响。

CSR5/向量化相关设计（概念性）

CSR5（概念上常被视为面向向量化与并行友好的 CSR 变体）通常围绕“降低分支与改善批量处理”展开。其设计思路一般包括：

  • 将非零条目按一定规则分组，使得向量化计算更容易。
  • 调整内部数据布局或引入更细粒度的分段，减少线程之间的差异。
  • 通过更规则的访问模式提升吞吐。

需要强调的是，不同实现对“CSR5”可能存在差异；理解其目标（向量化与吞吐提升）有助于把握其与标准 CSR 的关系。

评价与取舍

优势：空间与行访问特性

CSR 的主要优点在于：

  • 空间效率高：只存储非零元素与必要索引，显著降低与密集存储相比的内存需求。
  • 行访问效率好：定位与遍历某一行只需通过 row_ptr 获得连续区间。
  • 算子实现直观：SpMV 等按行累加操作结构清晰，便于优化与并行。

当计算以行遍历为主且稀疏度确实能带来明显压缩效果时，CSR 往往是可靠的默认选择。

局限：随机列访问与不规则性

CSR 的限制主要体现在：

  • 随机列访问：对 x（或矩阵乘中的中间向量）的访问由 col_ind 决定，可能造成缓存利用率下降。
  • 不规则计算：行内 nnz 差异大时，容易出现负载不均或分支开销。
  • 对某些访问模式不友好：若主要计算需要频繁按列组织数据，CSR 可能不如 CSC 或其他面向列的格式。

因此，性能表现往往与稀疏结构分布、硬件特性和算子类型强相关。

选型建议：何时用 CSR 而非其他格式

选择 CSR 通常遵循以下思路：

  • 如果算法以“按行扫描/累加”为核心，并且矩阵以稀疏形式自然表示，CSR 是合适的起点。
  • 如果稀疏度在行方向差异很大，可能需要评估其他格式或配套的重排/分块策略来改善负载与访存。
  • 若主要访问形态是按列，优先考虑 CSC 或相关格式可能更高效。
  • 若非零分布相对规则且可利用向量化对齐，ELL 等可能提供更高吞吐。

工程上常通过基准测试或根据结构特征做预估，再确定最终格式。

术语与相关概念

稀疏度、非零结构（sparsity pattern）

稀疏度通常指矩阵中零元素占比的程度；非零结构（sparsity pattern）则强调“非零出现在哪里”，即非零的行列位置分布，而不关心具体数值大小。

CSR 与 sparsity pattern 的关系在于：行指针与列下标共同刻画了结构分布；数值部分 values 则在结构之上提供权重。

指针数组的含义与边界条件

在 CSR 中，row_ptr 的含义不仅是“起止位置”，还隐含了结构合法性条件：

  • 每个 row_ptr[i] 应该对应第 i 行的段起点。
  • row_ptr 的单调性与最终值 row_ptr[m]=nnz 是边界正确性的关键。
  • start=end 的情况意味着该行没有非零元素，此时该行对应区间为空，需要确保程序能正确处理空区间。

理解边界条件是避免越界和错误还原的基础。

稀疏算子的通用评价指标

评价稀疏算子与稀疏格式时，常见指标包括：

  • 性能：如吞吐率、延迟、每次迭代的耗时。
  • 内存开销：包括索引与数值数组的总字节数，以及额外辅助结构。
  • 计算与访存平衡：访存瓶颈程度、缓存命中情况、带宽利用率等。
  • 数值稳定性与精度：若涉及浮点求和顺序或去重策略，需关注误差传播。

这些指标共同决定 CSR 在特定任务上的“好用程度”。