**Data Flow Graph
Data-Flow Graph（数据流图，DFG） 是一种用来表示“计算过程”的图结构。它只关心数据从哪里来、经过什么操作、到哪里去，而不关心“先执行哪条指令”这种控制顺序。
在 GenDP 论文中，DPMap 算法的输入就是 DP 目标函数的 DFG。
1. DFG 的基本定义
一个 DFG 通常包含两类元素：
| 元素 | 含义 | 例子 |
|---|---|---|
| 节点（Node） | 一个操作或计算 | 加法、乘法、取最大值、比较、查表 |
| 边（Edge） | 数据依赖关系 | 节点 A 的输出是节点 B 的输入 |
边是有方向的：
A ──► B
表示 B 需要 A 的结果作为输入。
所以 DFG 通常是一个有向无环图（DAG），因为数据不能循环依赖自己。
在论文中：
In the DFG, a node represents an operator, while an edge shows the dependency between operators.
也就是说：
- 节点 = 算子（operator）；
- 边 = 依赖（dependency）；
- 父节点 = 提供输入的操作；
- 子节点 = 接收输出的操作。
2. 一个简单例子
假设要计算：
c = (a + b) * (a - b)
对应的 DFG 是：
a ──┬──► Add ──┐
│ ├──► Mul ──► c
b ──┴──► Sub ──┘
节点：Add、Sub、Mul
边：a 和 b 分别流向 Add 和 Sub；Add 和 Sub 的输出流向 Mul。
从这个图可以直接看出：
Add和Sub可以并行执行；Mul必须等两者都完成；a和b被多个节点使用，可能需要复制或存寄存器。
这就是 DFG 的核心价值：把计算的并行性和依赖关系显式地画出来。
3. DFG 与 CFG 的区别
| 数据流图 DFG | 控制流图 CFG | |
|---|---|---|
| 关注点 | 数据依赖 | 执行顺序 |
| 节点 | 操作 | 基本块或指令 |
| 边 | 数据流向 | 控制跳转 |
| 顺序 | 由依赖决定，可并行 | 由程序计数器决定，串行 |
| 典型用途 | 编译器优化、硬件综合 | 程序分析、分支预测 |
DFG 不关心“第 1 条指令、第 2 条指令”，只关心“谁的数据给谁用”。
所以 DFG 天然适合并行执行和硬件映射。
4. DFG 的主要应用场景
4.1 编译器优化与指令调度
编译器把中间表示（如 SSA）转成 DFG，然后：
- 做公共子表达式消除；
- 做指令调度，把无依赖的指令并行发射；
- 做寄存器分配，判断哪些值需要存下来。
例如 LLVM、GCC 都大量使用 DFG 做优化。
4.2 硬件综合与 FPGA
在 High-Level Synthesis（HLS） 中：
- 把 C/C++ 或算法描述转成 DFG；
- 再把 DFG 映射到 FPGA 的 LUT、DSP、寄存器；
- 决定流水线级数、并行度、资源复用。
DFG 是硬件综合的核心中间表示。
4.3 数据流架构与加速器
很多加速器直接以 DFG 为执行模型：
- Systolic array：PE 之间按数据流传递；
- Dataflow accelerator：如 SoftBrain、TIA；
- GenDP 的 DPAx：DPMap 把 DFG 划分成子图，映射到 2 级 ALU 树。
在 GenDP 中，BSW、PairHMM、POA、Chain 的目标函数都先表示成 DFG，再由 DPMap 划分。
4.4 机器学习框架
TensorFlow、PyTorch、JAX 等框架内部都用计算图（computation graph），本质上就是 DFG：
- 节点 = 张量操作（矩阵乘、卷积、ReLU）；
- 边 = 张量依赖；
- 优化 = 图重写、算子融合、内存复用；
- 执行 = 按依赖调度到 CPU/GPU/TPU。
4.5 信号处理与 DSP
在音频、图像、通信领域：
- 滤波器、FFT、卷积等算法表示成 DFG；
- 映射到 DSP 芯片或 FPGA；
- 实现流水线和并行处理。
4.6 数据库与分布式计算
- Apache Spark 的 RDD 血统图（lineage graph）本质是 DFG；
- MapReduce 的 job graph 也是 DFG；
- 用于容错恢复、任务调度、依赖分析。
4.7 基因组学与动态规划加速
这正是 GenDP 的场景：
- 每个 DP kernel 的目标函数表示成 DFG；
- DPMap 把 DFG 划分成子图；
- 子图映射到 PE 内的 ALU 阵列；
- 最终生成 VLIW 计算指令。
例如 BSW 的 DFG 包含：
comp节点：计算匹配得分；add、sub节点：计算对角线、gap 候选；max节点：取最大值得到 H、E、F。
5. DFG 在 GenDP 中的具体作用
论文第 5 节说：
The DP objective function is represented as a data-flow graph (DFG). The DPMap algorithm generates compute instructions by mapping the DFG to compute units in the PE.
流程是：
DP 目标函数
↓ 表示
DFG
↓ DPMap 划分
多个子图
↓ 映射
2 级 ALU 树
↓ 生成
VLIW 计算指令
DPMap 的三步：
- Partitioning：分离乘法、4 输入节点，复制 comp 节点；
- Seeding：找双亲节点，和父节点打包；
- Refinement：剩余节点两两配对。
最终每个子图正好塞进一个 CU 的 2 级 ALU 树。
6. 一句话总结
Data-Flow Graph 是用“节点表示操作、边表示数据依赖”的图，用来描述计算过程。
它不关心控制顺序，只关心数据流向，因此非常适合并行调度、硬件综合、编译器优化、机器学习、数据流加速器和基因组 DP 加速。GenDP 正是把 BSW、PairHMM、POA、Chain 的目标函数表示成 DFG，再用 DPMap 映射到 PE 的 ALU 阵列上。