求解器数据结构：稀疏矩阵、场布局、Cache、NUMA 与 Ghost 数据 / Solver Data Structures for Sparse Matrices, Fields, NUMA, and Ghost Data

📅 创建时间：2026-07-23
🏷️ 标签：#稀疏矩阵 #数据布局 #Cache #NUMA #GPU #MPI
📚 前置知识：[[03-cfd-solver-design]] [[/02-systems-and-performance/03-parallel-computing/04-memory-hierarchy]]
📚 相关知识：[[../marine-cae/11-discrete-systems-and-matrices]] [[/02-systems-and-performance/02-computer-architecture-and-hardware/01-computer-architecture-basics]]

1. 为什么数据结构决定性能

工业求解器的大部分时间不是在计算复杂函数，而是在移动数据：

从内存读取稀疏索引和系数；
根据单元或 Face 邻接间接读取状态；
向共享节点或 Cell 写入贡献；
在 NUMA 节点、GPU 和 MPI Rank 间搬运边界数据；
将大量结果写入文件。

同一个数学算法可以因为数据布局不同产生数倍性能差异。选择数据结构时要同时考虑：

text

构造成本
更新成本
算子吞吐
内存容量
并行冲突
硬件适配
结果可维护性

2. 稀疏矩阵的基本成本

SpMV：

text

y_i = Σ_j A_ij x_j

每个非零元通常需要读取：

数值 A_ij；
列索引 j；
向量 x_j；
最终写入 y_i。

浮点运算只有乘和加，因此算术强度低，常受内存带宽限制。理论 FLOPS 高并不代表 SpMV 快。

3. COO

text

row = [0, 0, 1, 2]
col = [0, 2, 1, 0]
val = [a, b, c, d]

适合：

并行生成局部贡献；
不提前知道非零结构；
GPU 上先生成再排序归并；
文件交换或调试。

不适合直接高效 SpMV，因为行信息重复且需要排序或原子累加。有限元并行组装常用 COO 作为中间格式，而不是最终求解格式。

4. CSR

text

rowPtr = [0, 2, 3, 4]
colIdx = [0, 2, 1, 0]
values = [a, b, c, d]

优点：

按行连续遍历；
SpMV 和多数 CPU/GPU 库支持成熟；
内存紧凑；
行边界天然适合并行。

局限：

动态插入昂贵；
x 的访问由 colIdx 决定，局部性不稳定；
小行和长行混合会造成 GPU Warp 负载不均；
多分量物理没有显式利用块结构。

因此通常先固定稀疏模式，再只更新 values。

5. CSC、BSR 与对称存储

CSC

按列压缩，适合列访问、转置操作和部分直接法内部结构。行组装和普通 SpMV 不如 CSR 自然。

BSR

把非零元按固定小块存储。三维位移问题常有 3×3 节点块：

text

每个节点对连接
→ 一个 3×3 刚度块

优点：

一个块共享一次列索引；
提高连续访问和 SIMD 机会；
适合块 Jacobi、块 ILU；
Coupled CFD 也可利用变量块。

局限是块内零元素会浪费空间，混合自由度或约束处理会破坏规则块。

对称存储

只保存三角部分可减小内存，但并行 SpMV 需要向两个 y 位置写入，可能增加冲突。现代并行硬件上，完整存储有时反而更快，应测量而不是只看容量。

6. ELL 与 SELL-C-σ

ELL 把每行补齐到相同长度，适合规则矩阵和 GPU 合并访问，但长短行差异大会浪费空间。

SELL-C-σ：

将行按长度在局部窗口内排序；
每 C 行组成 Slice；
Slice 内补齐；
让 SIMD Lane 或 GPU 线程规则访问。

它在非结构网格 SpMV 中可能优于 CSR，但重排行会影响向量编号、输出映射和其他算子。必须评估整体流程。

7. Matrix-Free

Matrix-Free 不显式存储 A，而是直接计算：

text

y = A(x)

有限元中可按单元：

text

收集局部 x
→ 计算局部算子作用
→ 散射到全局 y

优势：

大幅减少矩阵内存；
用额外计算换取更少数据移动；
高阶有限元中算术强度高；
几何与基函数可利用张量积。

困难：

高质量预条件器更难；
散射写冲突仍存在；
边界、约束和复杂材料增加实现难度；
调试不能直接查看矩阵。

Matrix-Free 不是“不使用线性代数”，而是改变 Operator 的表示。

8. AoS、SoA 与 AoSoA

以应力六分量为例。

AoS

cpp

struct Stress {
    double xx, yy, zz, xy, yz, zx;
};
std::vector<Stress> stress;

适合一次处理一个点的全部分量，业务表达自然。但只读取 xx 时会把其他分量一起带入 Cache。

SoA

cpp

struct StressFields {
    std::vector<double> xx, yy, zz;
    std::vector<double> xy, yz, zx;
};

适合对大量点执行同一分量操作，容易 SIMD 和 GPU 合并访存。

AoSoA

按 SIMD 宽度或 GPU Tile 分块：

text

block 0: xx[0..7], yy[0..7], ...
block 1: xx[8..15], yy[8..15], ...

兼顾局部对象和向量化，但接口和尾部处理更复杂。

选择必须根据最常见的访问模式，不应因为 SoA 常见就把所有对象机械拆开。

9. 网格与邻接布局

非结构网格的热点往往是：

text

for face:
    owner = owner[face]
    neighbour = neighbour[face]
    read field[owner], field[neighbour]

owner/neighbour 对 field 的读取可能跨越很远。改善方法：

按空间、分区或图顺序重编号 Cell；
将内部面和边界面分开；
按边界类型、材料或单元类型分组；
将内部区域和 Halo 区域分开，便于通信重叠；
为 GPU 按行长、单元类型或工作量分桶。

重排会影响多个算子。必须用端到端数据验证，而不是只看一个循环。

10. Cache 和分块

时间局部性

刚读取的数据尽快再次使用。例如在一个 Cell Block 内同时完成多个相关变量更新。

空间局部性

连续读取相邻元素。SoA、连续索引和重编号都有帮助。

分块

将工作集限制在 Cache 可容纳范围：

text

大网格
→ 分成 Cell/Element Block
→ 对一个 Block 完成多个阶段
→ 再处理下一个 Block

但过度融合会增加寄存器压力、复杂依赖和代码维护成本。阶段之间存在全局同步时也不能任意融合。

11. SIMD 与数据对齐

编译器向量化需要：

循环边界清晰；
指针别名可分析；
数据连续且对齐；
分支可消除或转换为 Mask；
迭代间无真实依赖。

单元类型混合时，可以先按类型分组，再调用专用 Kernel。短小固定矩阵运算可用模板展开，但需要控制代码尺寸。

“使用了 AVX 指令”不等于达到高性能，还要检查向量化比例、Lane 利用率和内存带宽。

不同线程更新不同变量，但这些变量位于同一 Cache Line，会引发一致性抖动：

text

thread 0 writes counter[0]
thread 1 writes counter[1]
两个 counter 位于同一条 Cache Line

解决方法：

Padding 或 Cache Line 对齐；
线程私有统计，结束后归约；
减少高频共享写；
按数据块划分所有权。

有限元组装中的共享节点冲突比普通 False Sharing 更严重，因为可能是真实的同一地址写竞争。

13. NUMA

双路或多路 CPU 上，访问本地内存快于远端内存。

First Touch

物理页通常分配到第一次写入它的 NUMA 节点。若主线程串行初始化全部大数组，之后并行线程可能大量远端访问。

合理流程：

text

线程绑定到目标 NUMA 节点
→ 各线程并行初始化自己将处理的数据
→ 计算期间保持线程和数据亲和性

MPI + OpenMP 混合模式常让每个 Rank 对应一个 NUMA 节点，再在节点内使用线程。

14. GPU 内存和数据常驻

主要层次：

寄存器；
Shared Memory；
L1/L2 Cache；
HBM/GDDR 全局显存；
主机内存。

工业求解器应尽量让主迭代所需的 Field、矩阵和预条件数据驻留 GPU。每次迭代上传矩阵、下载结果会抵消 Kernel 加速。

Pinned Memory 有利于异步传输，但过量使用会影响系统。Unified Memory 简化开发，却可能因缺页迁移产生不可预测停顿，需要用工具验证。

15. MPI 所有权与 Ghost 数据

每个 Rank 通常区分：

text

Owned Entity    本 Rank 负责更新并保存权威值
Ghost Entity    邻居拥有，本 Rank 保存只读或临时副本
Shared Entity   需要明确归约或一致性规则

Halo Buffer 应：

预先建立发送/接收索引；
复用缓冲区；
合并多个小消息；
根据阶段只交换必要字段；
区分内部和边界工作；
避免每步重新构造通信计划。

结构组装还需要区分“Ghost 值同步”和“界面贡献累加”，两者方向和语义不同。

16. 临时内存与分配器

高频循环中反复 new/delete 会带来：

分配器锁；
Cache/TLB 扰动；
GPU 分配同步；
内存碎片。

常用处理：

Arena/Memory Pool；
每线程 Scratch Buffer；
按最大需求预分配；
时间步间复用向量；
明确所有权和生命周期；
用高水位统计而不是随意扩大缓存。

17. 选择速查

场景	优先考虑
通用 CPU SpMV	CSR
规则多自由度节点	BSR
GPU 行长较规则	ELL/SELL-C-σ
并行有限元组装中间结果	COO + 排序归并
高阶有限元、矩阵内存过大	Matrix-Free
逐分量批量计算	SoA
SIMD 固定宽度批处理	AoSoA
多路 CPU	First Touch + 绑核
MPI 网格	Owned/Ghost + 预生成 Halo Plan
GPU 主迭代	数据常驻 + 批处理/融合

18. 观察、解释与下一步

观察到什么	说明什么	下一步检查什么
SpMV 带宽高但性能不再增长	数据格式的字节成本可能已成上限	索引宽度、块结构和 Matrix-Free
向量化报告成功但收益很小	Gather/Mask 或内存带宽抵消了 SIMD	Lane 利用率、访问连续性和 Roofline
多 Socket 比单 Socket 慢	页放置和线程亲和性可能错误	First Touch、远端页和绑核
GPU Kernel 快但总流程慢	数据布局转换或主机往返占主导	Nsight 时间线和权威数据副本
Halo 字节异常大	Ghost 范围、字段集合或分区边界不合理	发送索引、必要字段和表面积/体积比

19. 设计检查

[ ] 稀疏结构是否跨迭代复用？
[ ] 索引使用 32 位还是 64 位，是否有明确规模边界？
[ ] 数据布局是否匹配最主要的访问模式？
[ ] 重编号是否同时评估求解、组装和通信？
[ ] 是否存在隐藏的 CPU/GPU 格式转换？
[ ] NUMA 页是否由实际计算线程初始化？
[ ] Halo 是否只交换必要字段？
[ ] 临时内存是否在高频路径复用？
[ ] 优化后是否比较总内存、总时间和正确性？

下一篇：[[05-cae-performance-analysis]]

求解器数据结构：稀疏矩阵、场布局、Cache、NUMA 与 Ghost 数据 / Solver Data Structures for Sparse Matrices, Fields, NUMA, and Ghost Data ​

1. 为什么数据结构决定性能 ​

2. 稀疏矩阵的基本成本 ​

3. COO ​

4. CSR ​

5. CSC、BSR 与对称存储 ​

CSC ​

BSR ​

对称存储 ​

6. ELL 与 SELL-C-σ ​

7. Matrix-Free ​

8. AoS、SoA 与 AoSoA ​

AoS ​

SoA ​

AoSoA ​

9. 网格与邻接布局 ​

10. Cache 和分块 ​

时间局部性 ​

空间局部性 ​

分块 ​

11. SIMD 与数据对齐 ​

12. False Sharing ​

13. NUMA ​

First Touch ​

14. GPU 内存和数据常驻 ​

15. MPI 所有权与 Ghost 数据 ​

16. 临时内存与分配器 ​

17. 选择速查 ​

18. 观察、解释与下一步 ​

19. 设计检查 ​

求解器数据结构：稀疏矩阵、场布局、Cache、NUMA 与 Ghost 数据 / Solver Data Structures for Sparse Matrices, Fields, NUMA, and Ghost Data

1. 为什么数据结构决定性能

2. 稀疏矩阵的基本成本

3. COO

4. CSR

5. CSC、BSR 与对称存储

CSC

BSR

对称存储

6. ELL 与 SELL-C-σ

7. Matrix-Free

8. AoS、SoA 与 AoSoA

AoS

SoA

AoSoA

9. 网格与邻接布局

10. Cache 和分块

时间局部性

空间局部性

分块

11. SIMD 与数据对齐

12. False Sharing

13. NUMA

First Touch

14. GPU 内存和数据常驻

15. MPI 所有权与 Ghost 数据

16. 临时内存与分配器

17. 选择速查

18. 观察、解释与下一步

19. 设计检查