Dependence Graph

定义 Definition

dependence graph（依赖图/依存图）：一种用节点表示对象（如变量、语句、任务、模块），用有向边表示“谁依赖谁”的关系的图结构。常见于编译器优化、程序分析、并行计算、任务调度等领域。也常见写法：dependency graph（更口语、更常用的同义表达）。

发音 Pronunciation

/dɪˈpɛndəns ɡræf/

例句 Examples

We built a dependence graph to see which tasks must finish first.
我们构建了一个依赖图来查看哪些任务必须先完成。

The compiler uses a dependence graph of statements to determine which instructions can be safely reordered without changing the program’s meaning.
编译器使用语句的依赖图来判断哪些指令可以在不改变程序含义的前提下安全地重排。

词源 Etymology

dependence 来自拉丁语 dependere（“悬挂于……之上、依附于……”），引申为“依赖关系”；graph 来自希腊语 graphē（“书写/描画”），在数学与计算机科学中指“图（节点与边的结构）”。合在一起就是“把依赖关系用图结构画出来”。

相关词 Related Words

• Dependency
• Graph
• Directed Graph
• DAG
• Topological Sort
• Data Dependence
• Control Dependence
• Program Dependence Graph
• Dependency Analysis
• Scheduling

文学与经典作品 Literary Works

• Compilers: Principles, Techniques, and Tools（Aho, Sethi, Ullman 等，“龙书”）：讨论程序分析与优化时涉及依赖关系图/相关图模型。
• Advanced Compiler Design and Implementation（Steven Muchnick）：在优化与并行化相关章节中使用依赖图思想与术语。
• Optimizing Compilers for Modern Architectures（Randy Allen, Ken Kennedy）：以依赖分析与依赖图为基础讲解指令调度与并行优化。