算法导论第三版新增27章中文版(9)

计算机科学与技术

把多线程计算（由一个代表多线程程序的处理器执行的运行时指令集）看做是一个有向无环图 G= （ V, E ）是很有帮助的，我们称其为计算 dag （ directed acyclic graph ） 。图 27.2

中给出了一个示例，其中的计算 dag 来自计算 P-FIB(4) 。从概念层面来讲， V 中的顶点都是指令， E 中边则表示指令间的依赖关系， (u,v ) ∈ E 表示指令 u 必须在指令 v 之前执行。为了方便起见，如果一条指令链中不包含任何并行控制语句（没有 spawn 、 sync 以及被 spawn 例程中 return ——显式的 return 语句或者过程执行完后的隐式 return ），我们就把它们组成一组，形成一个 strand ，每个 strand 都表示一条或者多条指令。涉及并行控制的指令不包括在 strand 中，但是会出现在 dag 结构中。例如，如果一个 strand 有两个后继，那么其中之一必须得被 spawn 出来，如果一个 strand 有多个前驱，就表示前驱因为一条 sync 语句被合并在一起。因此，一般来说， V 形成了 strand 集合，而有向边集合 E 则表示由并行控制产生的 strand 间的依赖关系。如果 G 中有一个从 strand u 到 strand v 的有向路径，那么我们就说这两个 strands 是（逻辑上）串行的。否则就称其为（逻辑上）并行的。