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

计算机科学与技术

动态多线程 是一种重要的并发平台，也是本章中要采用的模型。使用动态多线程平台，程序员可以无需关心通信协议、负载均衡以及其他静态线程编程中的复杂问题，只要明确应用中的并行性即可。该并发平台中有一个调度器，用来自动均衡计算的负载，因此大大地简化了程序员的工作。动态多线程环境所具有的功能目前还在不断的演化之中，不过基本上都包含有两个功能：嵌套并行以及并行循环。嵌套并行就是可以去“ spawn ”一个子例程，并且使得调用者和子例程能够同时执行。并行循环和普通的 for 循环相似，只是循环中的迭代可以并发地执行。

这两个功能是我们将要在本章中研究的动态多线程模型的基础。该模型的一个关键特征为，程序员只需要指明计算中的逻辑并行性，底层并发平台中的线程会自动调度和均衡计算。我们将研究基于这种模型所编写的多线程算法，以及底层并发平台能够高效进行计算调度的原理。

动态多线程模型具有如下几个重要优点： 它是串行编程模型的简单扩展。只需在伪码中增加 3 个“并发”关键字： paral

lel ， spawn 以及 sync ，就可以描述多线程算法。此外，如果从多线程伪码中去掉这些关键字，就可以得到针对相同问题的串行伪代码，我们称之为“串行化”一个多线程算法。

它提供了一种理论上清晰的、基于“ work （工作总量）”和“ span （跨度）”

这两个概念量化 parallelism （并行度）的方法。

许多多线程算法所涉及的嵌套并行可以从分治范型自然得出。此外，正如串行分

治算法可以容易地通过递归关系进行分析一样，多线程算法也是如此。