搜索
多线程算法（完整版）——算法导论第3版新增第27章ThomasH.Cormen,CharlesE.Leiserson,RonaldL.Rivest,CliffordStein邓辉译原文：本书中的主要算法都是顺序算法，适合于运行在每次只能执行一条指令的单处理器计算机上。在本章中，我们要把算法模型转向并行算法，它们可以运行在能够同时执行多条指令的多处理器计算机中。我们将着重探索优雅的动态多线程算法模型，该模型既有助于算法的设计和分析，同时也易于进行高效的实现。并行计算机（就是具有多个处理单元的计算机）已经变得越来越常见，其在价格和性能方面差距甚大。相对比较便宜的有片上多处理器桌面电脑和笔记本电脑，其中包含着一个多核集成芯片，容纳着多个处理“核”，每个核都是功能齐全的处理器，可以访问一个公共内存。价格和性能都处于中间的是由多个独立计算机（通常都只是些PC级的电脑）组成的集群，通过专用的网络连接在一起。价格最高的是超级计算机，它们常常采用定制的架构和网络以提供最高的性能（每秒执行的指令数）。多处理器计算机已经以各种形态存在数十年了。计算社团早在计算机科学形成的初期就选定采用随机存取的机器模型来进行串行计算，但是对于并行计算来说，却没有一个公认的模型。这主要是因为供应商无法在并行计算机的架构模型上达成一致。比如，有些并行计算机采用共享内存，其中每个处理器都可以直接访问内存的任何位置。而有些并行计算机则使用分布式内存，每个处理器的内存都是私有的，要想去访问其他处理器的内存，必须得向其他处理器发送显式的消息。不过，随着多核技术的出现，新的笔记本和桌面电脑目前都成为共享内存的并行计算机，趋势似乎倒向了共享内存多处理这边。虽然一切还是得由时间来证明，不过我们在章中仍将采用共享内存的方法。对于片上多处理器和其他共享内存并行计算机来说，使用静态线程是一种常见的编程方法，该方法是一种共享内存“虚拟处理器”或者线程的软件抽象。每个线程维持着自己的程序计数器，可以独立地执行代码。操作系统把线程加载到一个处理器上让其运行，并在其他线程需要运行时将其换下。操作系统允许程序员创建和销毁线程，不过这些操作的开销较大。因此，对于大多数应用来说，在计算期间线程是持久存在的，这也是为何称它们为“静态”的原因。遗憾的是，在共享内存并行计算机上直接使用静态线程编程非常的困难且易于出错。原因之一是，为了使每个线程所承担的负载大致相当，就需要动态地在线程间分配工作，而这是一项极其复杂的任务。除了那些最简单的应用之外，程序员都得使用复杂的通信协议来实现调度器以对工作进行均衡。这种状况导致了并发平台的出现，并发平台就是一个用来协调、调度、管理并行计算资源的软件平台。有些并发平台被构建成运行时库，有些则提供了具有编译器和运行时支持的全功能的并行语言。动态多线程编程动态多线程是一种重要的并发平台，也是本章中要采用的模型。使用动态多线程平台，程序员可以无需关心通信协议、负载均衡以及其他静态线程编程中的复杂问题，只要明确应用中的并行性即可。该并发平台中有一个调度器，用来自动均衡计算的负载，因此大大地简化了程序员的工作。动态多线程环境所具有的功能目前还在不断的演化之中，不过基本上都包含有两个功能：嵌套并行以及并行循环。嵌套并行就是可以去“spawn”一个子例程，并且使得调用者和子例程能够同时执行。并行循环和普通的for循环相似，只是循环中的迭代可以并发地执行。这两个功能是我们将要在本章中研究的动态多线程模型的基础。该模型的一个关键特征为，程序员只需要指明计算中的逻辑并行性，底层并发平台中的线程会自动调度和均衡计算。我们将研究基于这种模型所编写的多线程算法，以及底层并发平台能够高效进行计算调度的原理。动态多线程模型具有如下几个重要优点：它是串行编程模型的简单扩展。只需在伪码中增加3个“并发”关键字：parallel，spawn以及sync，就可以描述多线程算法。此外，如果从多线程伪码中去掉这些关键字，就可以得到针对相同问题的串行伪代码，我们称之为“串行化”一个多线程算法。它提供了一种理论上清晰的、基于“work（工作总量）”和“span（跨度）”这两个概念量化parallelism（并行度）的方法。许多多线程算法所涉及的嵌套并行可以从分治范型自然得出。此外，正如串行分治算法可以容易地通过递归关系进行分析一样，多线程算法也是如此。该模型符合并行计算实践的演化方向。越来越多的并发平台开始支持动态多线程技术的不同变种，包括Cilk[51,118],Cilk++[72],OpenMP[60],TaskParallelLibrary[230],andThreadingBuildingBlocks[292]。在27.1小节中，我们会介绍动态多线程模型，以及有关work、span以及parallelism的度量方法，我们会使用该度量去分析多线程算法。在27.2小节中，我们将研究如何使用多线程来进行矩阵相乘，在27.3小节中，我们将处理一个更为困难的问题：归并排序的多线程算法27.1动态多线程技术基础我们将以递归地计算Fibonacci数为例来开始对于动态多线程技术的探索历程。先来回忆一下3.22小节中给出的Fibonacci数的递归定义：F0=0,F1=1,Fi=Fi-1+Fi-2fori≥2.下面是一个简单的用于计算第n个Fibonacci数的递归串行算法：FIB(n)1ifn≤12returnn3elsex=FIB(n-1)4y=FIB(n-2)5returnx+y如果要计算很大的Fibonacci数，是不能使用该算法的，因为其中有大量的重复计算。图27.1展示了在计算F6时所创建的递归过程实例树。其中，对于对于FIB(6)的调用会递归地调用FIB(5)和FIB(4)。而对FIB(5)的调用又会去调用FIB(4)。这两个FIB(4)实例返回的结果完全相同（F4=3）。由于FIB并没有去记住这些结果，因此对于FIB(4)的第二次调用重复了第一次调用的工作。我们用T(n)表示FIB(n)的运行时间。由于FIB(n)包含了两个递归调用和其他一些常数时间的工作，因此得到如下递归方程：T(n)=T(n-1)+T(n-2)+Θ(1)我们可以采用替换方法得到该方程的解：T(n)=Θ(Fn)。作为归纳假设，我们假设T(n)≤aFn-b，其中a1，b0且都为常数。通过替换，我们得到：T(n)≤（aFn-1-b）+(aFn-2-b）+Θ(1)=a(Fn-1+Fn-2）-2b+Θ(1)=aFn-b–(b-Θ(1))≤aFn-b如果我们在选择b时让其大到足以支配Θ(1)中的常量。那么我们接着可以把a选得大到足以满足初始条件。其分析边界为：T(n)=Θ(Φn),(27.1)其中，Φ=(1+sqrt(5))/2是黄金分割率，由等式(3.25)得出。由于Fn随n成指数级增长，因此在计算Fibonacci数时，该过程非常低效。（问题31-3中给出了快得多的方法）。虽然上面的FIB过程对计算Fibonacci数来说是一种糟糕的方法，但是在说明多线程算法分析中的关键概念方面，它却是一个好例子。在FIB(n)中，第3行、第4行对FIB(n-1)和FIB(n-2)的两个递归调用彼此之间相互独立：它们可以按照任意顺序被调用，相互之间也不会有任何影响。因此，这两个递归调用是可以并行运行的。我们在伪代码中增加了并发关键字spawn和sync来指示并行属性。下面是采用动态多线程技术重写的FIB过程：P-FIB(n)1ifn≤12returnn3elsex=spawnP-FIB(n-1)4y=P-FIB(n-2)5sync6returnx+y请注意，如果我们从P-FIB中删除掉并发关键字spawn和sync，剩下的代码和FIB完全一样（除了开始和两处递归调用处的过程名字被更改之外）。我们把多线程算法的串行化定义为：删除了多线程关键字spawn、sync以及parallel（并行循环中会用到）后所得到的串行算法。事实上，我们的多线程伪代码具有一个不错的属性——其串行化版本就是解决相同问题的常用串行伪代码。在过程调用前面加上spawn关键字时，就意味着嵌套并行，如第3行中所示。spawn的语义和普通的过程调用不同，执行spawn的过程实例（parent）可以和被spawn出来的子例程（child）并行执行，而不像串行执行中那样去等待child执行完成。在本例中，当child在计算P-FIB(n-1)时，parent可以并行地去计算第4行中的P-FIB(n-2)。由于P-FIB过程是递归的，因此这两个对其自身进行调用的子例程就创建了嵌套的并行性，对其children来说同样如此，于是就产生了一个潜在的巨大子计算树，每个子计算都并行执行。不过，关键字spawn并不是一定要求过程必须和其child并发执行，只是表示可以并发执行。并发关键字表达了计算中的逻辑并行性，表明了计算中的哪些部分可以并行的运行。哪些子计算实际上是并发运行的是由调度器在运行时决定的，在计算进行中，调度器把子计算分配给可用的处理器。稍后，我们会讨论调度器的原理。一个过程，仅当其执行了sync语句时（如第5行），才能够安全地使用由其spawn的children例程的返回值。关键字sync表示过程必须等待，直到其所spawn的children全部完成计算，才能够继续sync后面的语句。在P-FIB过程中，必须要在return语句（第6行）前增加sync语句，从而避免出现在x还没有被计算前就进行x+y操作的异常情况。除了sync语句所提供的显式同步之外，每个过程都会在其返回前隐式地执行一条sync语句，这样可以保证在其终止前，其所有的children都已经终止。多线程执行模型把多线程计算（由一个代表多线程程序的处理器执行的运行时指令集）看做是一个有向无环图G=（V,E）是很有帮助的，我们称其为计算dag（directedacyclicgraph）。图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中有一个从strandu到strandv的有向路径，那么我们就说这两个strands是（逻辑上）串行的。否则就称其为（逻辑上）并行的。我们可以把一个多线程计算表示为由内嵌于一棵过程实例树中的strands组成的有向无环图。比如，图27.1中展示了P-FIB(6)的过程实例树，其中没有显示strands细节。图27.2放大了该树中的一个片段，展现了构成每个过程的strands。所有连接strands的有向边要么运行于一个过程之中，要么沿着过程树中的无向边运行。我们可以把计算dag的边进行分类，以表示出不同strands间依赖关系的种类。在图27.2中，沿水平方向连接strandu和其同一个过程实例中的后继u’的边被称为continuationedage（继续边）（u，u’）。当stranduspawn了strandv时，dag中就包含了另一个spawnedge(u,v)，在图中显示为指向下的边。表示正常过程调用的calle