算法导论第 3 版之多线程算法-开头部分（带图版）

转自：http://blog.csdn.net/hoping/archive/2010/02/25/5326354.aspx

本书中的主要算法都是顺序算法 ，适合于运行在每次只能执行一条指令的单处理器计算机上。在本章中，我们要把算法模型转向并行算法 ，它们可以运行在能够同时执行多条指令的多处理器计算机中。我们将着重探索优雅的动态多线程算法模型，该模型既有助于算法的设计和分析，同时也易于进行高效的实现。

 

       并行计算机（就是具有多个处理单元的计算机）已经变得越来越常见，其在价格和性能方面差距甚大。相对比较便宜的有片上多处理器桌面电脑和笔记本电脑，其中包含着一个多核集成芯片，容纳着多个处理“核”，每个核都是功能齐全的处理器，可以访问一个公共内存。价格和性能都处于中间的是由多个独立计算机（通常都只是些 PC 级的电脑）组成的集群，通过专用的网络连接在一起。价格最高的是超级计算机，它们常常采用定制的架构和网络以提供最高的性能（每秒执行的指令数）。

 

       多处理器计算机已经以各种形态存在数十年了。计算社团早在计算机科学形成的初期就选定采用随机存取的机器模型来进行串行计算，但是对于并行计算来说，却没有一个公认的模型。这主要是因为供应商无法在并行计算机的架构模型上达成一致。比如，有些并行计算机采用共享内存 ，其中每个处理器都可以直接访问内存的任何位置。而有些并行计算机则使用分布式内存 ，每个处理器的内存都是私有的，要想去访问其他处理器的内存，必须得向其他处理器发送显式的消息。不过，随着多核技术的出现，新的笔记本和桌面电脑目前都成为共享内存的并行计算机，趋势似乎倒向了共享内存多处理这边。虽然一切还是得由时间来证明，不过我们在章中仍将采用共享内存的方法。

 

       对于片上多处理器和其他共享内存并行计算机来说，使用静态线程 是一种常见的编程方法，该方法是一种共享内存“虚拟处理器”或者线程的软件抽象。每个线程维持着自己的程序计数器，可以独立地执行代码。操作系统把线程加载到一个处理器上让其运行，并在其他线程需要运行时将其换下。操作系统允许程序员创建和销毁线程，不过这些操作的开销较大。因此，对于大多数应用来说，在计算期间线程是持久存在的，这也是为何称它们为“静态”的原因。

 

       遗憾的是，在共享内存并行计算机上直接使用静态线程编程非常的困难且易于出错。原因之一是，为了使每个线程所承担的负载大致相当，就需要动态地在线程间分配工作，而这是一项极其复杂的任务。除了那些最简单的应用之外，程序员都得使用复杂的通信协议来实现调度器以对工作进行均衡。这种状况导致了并发平台 的出现，并发平台就是一个用来协调、调度、管理并行计算资源的软件平台。有些并发平台被构建成运行时库，有些则提供了具有编译器和运行时支持的全功能的并行语言。

 

动态多线程编程

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

 

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

 

       动态多线程模型具有如下几个重要优点：

l         它是串行编程模型的简单扩展。只需在伪码中增加 3 个“并发”关键字： parallel ， spawn 以及 sync ，就可以描述多线程算法。此外，如果从多线程伪码中去掉这些关键字，就可以得到针对相同问题的串行伪代码，我们称之为“串行化”一个多线程算法。

l         它提供了一种理论上清晰的、基于“ work （工作总量）”和“ span （跨度）”这两个概念量化 parallelism （并行度）的方法。

l         许多多线程算法所涉及的嵌套并行可以从分治范型自然得出。此外，正如串行分治算法可以容易地通过递归关系进行分析一样，多线程算法也是如此。

l         该模型符合并行计算实践的演化方向。越来越多的并发平台开始支持动态多线程技术的不同变种，包括 Cilk [51, 118], Cilk++ [72], OpenMP [60], Task Parallel Library [230], and Threading Building Blocks [292] 。

 

       在 27.1 小节中，我们会介绍动态多线程模型，以及有关 work 、 span 以及 parallelism 的度量方法，我们会使用该度量去分析多线程算法。在 27.2 小节中，我们将研究如何使用多线程来进行矩阵相乘，在 27.3 小节中，我们将处理一个更为困难的问题：归并排序的多线程算法

 

送上图片：