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

计算机科学与技术

我们可以把一个多线程计算表示为由内嵌于一棵过程实例树中的 strands 组成的有向无环图。比如，图 27.1 中展示了 P-FIB(6) 的过程实例树，其中没有显示 strands 细节。图 27.2 放大了该树中的一个片段，展现了构成每个过程的 strands 。所有连接 strands 的有向边要么运行于一个过程之中，要么沿着过程树中的无向边运行。

我们可以把计算 dag 的边进行分类，以表示出不同 strands 间依赖关系的种类。在图 27.2 中，沿水平方向连接 strand u 和其同一个过程实例中的后继 u’ 的边被称为 continuation edage （继续边） （ u ， u’ ）。当 strand u spawn 了 strand v 时， dag 中就包含了另一个 spawn edge (u,v) ，在图中显示为指向下的边。表示正常过程调用的 call edge 也指向下。 Strand u spawn 了 strand v 和 u 调用 v 的差别在于： spawn 会产生一条从 u 到其同一过程中后继 u’ 的水平方向的 continuation edge ，意味着 u’ 可以和 v 同时执行，而调用不会产生出这样的边。当 strand u 返回到其调用过程，而 x 是该调用过程中紧跟着下一条 sync 语句的 strand 时，计算 dag 中就会包含 return edge (u,x) ，指向上方。计算从一个 initial strand 开始执行（图 27.2 中被标记为 P-FIB(4) 的过程中的黑色顶点），并以一个 final strand 结束（被标记为 P-FIB(4) 的过程中的白色顶点）。

我们将在理想并行计算机 上研究并行算法的执行，该理想并行计算机由一组处理器和一个顺序一致性 的共享内存组成。顺序一致性的意思是，虽然在实际上多个处理器可以同时对共享内存执行众多的存取操作，但是其产生的结果和在每一步中都只有来自一个处理器的一条指令被执行所产生的完全一样。也就是说，内存的行为就像是按照某个全局的线性顺序来执行指令，该全局顺序保证了每个处理器基于独立的顺序来发出自己的指令。对于动态多线程计算来说，计算是被并发平台自动调度到处理器上的，共享内存的工作方式看起来就像是多线