并行计算4.ppt

并行计算并行计算结构结构算法算法编程编程主讲:雷向东中南大学 信息科学与工程学院Central South UniversitySchool of Information Science and Engineering 并行算法2 并行算法就是用多台处理机 联合求解问题的方法和步骤,其执行过程是将给定的问题首先分解成若干个尽量相互独立的子问 题,然后使用多台计算机同时求解它,从而最终求得原问题的解。并行算法是并行计算中非常重要的问题。并法研究应该确立一个“理论设计实现应用”的系统方法，形成一个完善的“架构算法编程”方法论，这样才能保证并行算法不断发展并变得更加实用。由于人们的思维能力以及思考问题的方法对并行不太习惯，且并行算法理论不成熟，所以总是出现了需求再来研究算法，不具有导向性，同时实现并行算法的并行程序性能较差，往往满足不了人们的需求。并行算法的研究历史可简单归纳为：上世纪70到80年代，并行算法研究处于高潮；到上世纪90年代跌入低谷；目前，又处于研究的热点阶段。第四章并行计算模型并行算法3并行算法的研究内容:(1)并行计算模型并行算法作为一门学科，首先研究的是并行计算模型。并行计算模型是算法设计者与体系结构研究者之间的一个桥梁，是并行算法设计和分析的基础。它屏蔽了并行机之间的差异，从并行机中抽取若干个能反映计算特性的可计算或可测量的参数，并按照模型所定义的计算行为构造成本函数，以此进行算法的复杂度分析。并行计算模型:第一代是共享存储模型，如SIMD-SM和MIMD-SM的一些计算模型，模型参数主要是CPU的单位计算时间，科学家可以忽略一些细节，集中精力设计算法。第二代是分布存储模型。在这个阶段，人们逐渐意识到对并行计算机性能带来影响的不仅仅是CPU，还有通信。因此如何把不同的通信性能抽象成模型参数，是这个阶段的研究重点。并行算法4并行计算模型:第三代是分布共享存储模型，也是我们目前研究所处的阶段。随着网络技术的发展，通信延迟固然还有影响，但对并行带来的影响不再像当年那样重要，注重计算系统的多层次存储特性的影响。(2)设计技术并行算法研究的第二部分是并行算法的设计技术。虽然并行算法研究还不是太成熟，但并行算法的设计依然是有章可循的，例如划分法、分治法、平衡树法、倍增法/指针跳跃法、流水线法破对称法等都是常用的设计并行算法的方法。另外人们还可以根据问题的特性来选择适合的设计方法。目前并行算法研究的新走向是：并行算法研究内容不断拓宽，并行计算被纳入研究范畴；与广大用户领域结合，注重应用，强调走到用户中去，为用户解决问题；重视新的、非常规计算模式，如神经计算、量子计算等，这些模式能够解决某类特定问题，有其自身的优越性。并行算法的分类5数值并行算法：(1)数值计算(矩阵运算、求解线性方程组等)(2)非数值并行算法：符号运算(排序、匹配、收索等)(3)同步并行算法：向量算法、SIMD、MIMD同步(4)异步并行算法：不需相互等待(5)独立并行算法：进程间完全独立(6)细粒度并行算法：基于向量和循环系级并行(7)中粒度并行算法：较大的循环级并行(8)大粒度并行算法：任务级并行（区域分解）6 并行算法的表达n描述语言n可以使用类Pascal等；n在描述语言中引入并行语句。n并行语句示例nPar-do语句 for i=1 to n par-do end fornfor all语句 for all Pi,where 0ik end for 7 并行算法的复杂性度量n串行算法的复杂性度量n最坏情况下的复杂度(Worst-CASE Complexity)n期望复杂度(Expected Complexity)n并行算法的几个复杂性度量指标n运行时间t(n):包含计算时间和通讯时间，分别用计算时间步和选路时间步作单位。n为问题实例的输入规模。n处理器数p(n)n并行算法成本c(n):c(n)=t(n)p(n)n总运算量W(n):并行算法求解问题时所完成的总的操作步数。8第四章并行算法的复杂性度量nBrent定理令W(n)是某并行算法A在运行时间T(n)内所执行的运算量，则A使用p台处理器可在t(n)=O(W(n)/p+T(n)时间内执行完毕。nW(n)和c(n)密切相关nP=O(W(n)/T(n)时，W(n)和c(n)两者是渐进一致的n对于任意的p，c(n)W(n)9 并行算法的同步同步是在时间上强使各执行进程在某一点必须互相等待；共享存储多处理器上求和算法，处理器数pBegin S=0；for all Pi where 0ip-1 do L=0；for j=i to n step p do L=L+aj end for end for lock(S)S=S+L unlock(S)end for End10 PRAM模型Control UnitInterconnection NetworkPLMPLMPLMPLMShared Memory由Fortune和Wyllie1978年提出，又称SIMD-SM模型。有一个集中的共享存储器和一个指令控制器，通过SM的R/W交换数据，隐式同步计算。结构图11 PRAM模型n分类(1)PRAM-CRCW并发读并发写nCPRAM-CRCW(Common PRAM-CRCW)：仅允许写入相同数据nPPRAM-CRCW(Priority PRAM-CRCW)：仅允许优先级最高的处理器写入nAPRAM-CRCW(Arbitrary PRAM-CRCW)：允许任意处理器自由写入(2)PRAM-CREW并发读互斥写(3)PRAM-EREW互斥读互斥写 n计算能力比较nPRAM-EREW是功能最弱的计算模型，而PRAM-CRCW则是最强的计算模型12 PRAM模型nPRAM模型优点：PRAM模型特别适合于并行算法的表达、分析和比较，使用简单，很多关于并行计算机的底层细节，比如处理器间通信、存储系统管理和进程同步都被隐含在模型中；易于设计算法和稍加修改便可以运行在不同的并行计算机系统上；根据需要，可以在PRAM模型中加入一些诸如同步和通信等需要考虑的内容。13 PRAM模型nPRAM模型的缺点：(1)模型中使用了一个全局共享存储器，且局存容量较小，不足以描述分布主存多处理机的性能瓶颈，而且共享单一存储器的假定，显然不适合于分布存储结构的MIMD机器；(2)PRAM模型是同步的，这就意味着所有的指令都按照锁步的方式操作，用户虽然感觉不到同步的存在，但同步的存在的确很耗费时间，而且不能反映现实中很多系统的异步性；(3)PRAM模型假设了每个处理器可在单位时间访问共享存储器的任一单元，因此要求处理机间通信无延迟、无限带宽和无开销，假定每个处理器均可以在单位时间内访问任何存储单元而略去了实际存在的，合理的细节，比如资源竞争和有限带宽，这是不现实的；14 PRAM模型nPRAM模型的缺点：(4)PRAM模型假设处理机有限或无限，对并行任务的增大无开销；(5)未能描述所线程技术和流水线预取技术，而这两种技术又是当今并行体系结构用的最普遍的技术。APRAM模型15 APRAM（Asynchronous Parallel Random Access Machine）指的是异步随机存取并行机器模型，显然，APRAM是一种MIMD模型。在有的文献上，APRAM也称作Phased PRAM（分相PRAM）。它由p个处理器组成，特点是每个处理器都有自己的局部存储器、局部时钟和局部程序，处理器之间的通信通过全局共享存储器进行。每个全局时钟，所以各处理器异步的独立执行各自的程序，处理器之间任何时间上的依赖关系（执行次序）需要明确的在各处理器的程序中加入同步障碍语句（Synchronization Barrier）来实现，一条指令可以在非确定（无界）但有限的时间内完成。APRAM模型16APRAM模型特点：APRAM模型最重要的特点是处理器均工作在异步模式下，即处理器有自己的控制器，局部存储器以及局部程序。处理器间的同步问题通过添加同步路障（Synchronization Barrier）来解决。这样，计算被分割成一些列的相（Phase），每一相类不允许两个处理器去访问同一存储单元。而局部程序的最后一条指令一定是同步指令。显然，同步路障的时间是由最后一个到达的处理器决定的，也就是说，先执行完局部程序的处理器必须等到执行的最慢的那个处理器来一起完成同步路障。17APRAM模型APRAM中的指令有四种类型：(1)全局读，将全局存储单元中的内容读到处理器得局部存储单元中；(2)局部操作，对局部存储器中的数据执行局部操作，操作的结果存放到局部存储器中；(3)全局写，将局部存储器单元中的内容写入全局存储单元中；(4)同步，同步是计算中的一个逻辑点，在该点各处理器均需要等待其他的处理器也到达该点后才能继续执行它们的局部程序。18 APRAM模型APRAM模型中的计算过程：APRAM模型中，计算由一系列用同步障碍语句分开的全局相（Global Phase）所组成。如下面的图。在全局相内，每个处理器异步的运行其局部的程序；每个局部程序中的最后一条指令是一条同步障碍指令，各处理器均可以异步的读取和写入全局存储器，但在同一个全局相中，不允许两个处理器访问同一单元。正是因为不同的处理器访问存储单元总是由同步障碍指令所分开，所以指令完成时间上的差异并不影响整个计算。19 APRAM模型APRAM模型计算过程20 APRAM模型n计算时间 令 为全局相内各处理器执行时间最长者，则APRAM上的计算时间为 n优缺点 易编程和分析算法的复杂度，但与现实相差较远，其上并行算法非常有限，也不适合MIMD-DM模型。BSP模型21 整体同步并行计算模型(Bulk Synchronous Parallel Computing Model，简称BSP模型)，又名大同步模型或BSP模型，由哈佛大学Viliant和牛津大学Bill McColl提出，其目的是像冯诺伊曼体系结构那样，为各种并行体系结构提供一个独立于具体体系结构的、具有可扩展并行性的理论模型，成为一个并行计算领域中软件和硬件之问的桥梁BSP模型不仅是一种并行体系结构模型，又是一种并行程序设计模型同时可以 精确地分析和预测并行程序性能BSP模型已被成功地运用到科学计算等数值计算领域。BSP模型22 BSP模型是个分布存储的MIMD计算模型，其特点是：(1)它将处理器和路由器分开，强调了计算任务和通信任务的分开，而路由器仅仅完成点到点的消息传递，不提供组合、复制和广播等功能，这样做既掩盖具体的互连网络拓扑，又简化了通信协议；(2)采用障碍同步的方式以硬件实现的全局同步是在可控的粗粒度级，从而提供了执行紧耦合同步式并行算法的有效方式，而程序员并无过分的负担；(3)为PRAM模型所设计的算法，都可以采用在每个BSP处理器上模拟一些PRAM处理器的方法来实现。理论分析证明，这种模拟在常数因子范围内是最佳的，只要并行宽松度（Parallel Slackness），即每个BSP处理器所能模拟的PRAM处理器的数目足够大。BSP模型23 BSP模型组成：BSP并行计算机由以下3部分组成：(1)一组带存储器的处理器集台；(2)以点对点发送消息的全局数据通信网络；(3)支持对所有处理器进行全局障碍同步机制。BSP模型的计算由一系列用全局同步分开的超步组成。每个超步顺序分为计算、通信及同步3个阶段。在计算阶段中每个处理器完成一些本地计算，在通信阶段中处理器之间通过网络接收和发送信息然后进入同步阶段，检测网络是否已传递完信息，只有当这些都完成时才进入下一超步。所有发送接收的信息只有进入下一超步时才有效。BSP模型24 BSP模型是“块”同步模型，是一种异步MIMD-DM模型，支持消息传递系统，块内异步并行，块间显式同步。计算过程由若干超级步组成，每个超级步计算模式为下图所示：BSP模型25 1.Processors指的是并行计算进程，它对应到集群中的多个结点，每个结点可以有多个Processor；2.LocalComputation就是单个Processor的计算，每个Processor都会切分一些结点作计算；3.Communication指的是Processor之间的通讯。计算往往需要做些递归或是使用全局变量，在BSP模型中，对结点的访问分布到了不同的Processor中，并且往往哪怕是关系紧密具有局部聚类特点的结点也未必会分布到同个Processor或同一个集群结点上，所有需要用到的数据都需要通过Processor之间的消息传递来实现同步；4.BarrierSynchronization又叫障碍同步或栅栏同步。每一次同步也是一个超步的完成和下一个超步的开始；5.Superstep超步，这是BSP的一次计算迭代。BSP模型26BSP模型中的基本参数：BSP并行计算机的性能可由4个参数来描述 (1)p=处理器数目；(2)l=全局同步的时间开销；(3)s=处理器计算速度；(4)g一每秒本地计算操作数日通信网络每秒传送字节数。参数g是对BSP并行计算能力的一个相当准确的量度这样，一台BSP并行计算机就由4个参数，g进行了刻画用几个简单的参数就能概括BSP计算机。这不仅便于在BSP模型下进行并行算法分析和设计，而且可以对BSP并行程序的性能作出预测。BSP模型27 BSP模型中的计算：在BSP模型中，计算由一系列用全局同步分开的周期为L的计算组成，这些计算称为超级步（SuperStep）。在各超级步中，每个处理器均执行局部计算，并通过选路器接受和发送消息；然后作一全局检查，以确定该超步是否已由所有的处理器完成；若是，则进行到下一超级步，否则下一个L周期被分配给未曾完成的超级步。BSP模型28 BSP模型中的成本分析：在BSP的一个超级计算步中，可以抽象出BSP的成本模型如下：一个超级计算步成本=其中，wi是进程i局部计算时间，hi是进程i发送或接收的最大通信包数，g是带宽的倒数（时间步/通信包），L是障碍同步时间。所以，在BSP计算中，如果用了s个超级步，则总的运行时间为：BSP模型29 BSP模型的性质和特点：BSP模型是个分布存储的MIMD计算模型，其特点是：(1)它将处理器和路由器分开，强调了计算任务和通信任务的分开，而路由器仅仅完成点到点的消息传递，不提供组合、复制和广播等功能，这样做既掩盖具体的互连网络拓扑，又简化了通信协议；(2)使用全局的路障同步。在传统的并行计算机中，点对点的、阻塞式的通信实际上完成了两个操作：通信和同步。在BSP计算机中，所有的通信操作都是非阻塞的，在进行本地计算时发出；通信操作在通信阶段完成在路障同步以后变为有效。BSP模型实际上是将通信和同步分离开，分别进行处理使并行程序结构更为清晰，而且，由于BSP模型中的通信操作都足非阻塞的，消除了由于通信而造成的死锁。采用障碍同步的方式以硬件实现的全局同步提供了执行紧耦合同步式并行算法的有效方式，程序员并无过分的负担。BSP模型30 BSP模型的性质和特点：(3)BSP计算机的运行方式以超步为单位类似于串行计算机，这样可以方便程序员进行并行程序的编写和调试从某种角度看，BSP并行模型可以看成是严格同步的并行计算模型(各处理机处理每一条指令都要保持同步，如按SIMD方式运行的并行计算机)和不进行同步的计算机群(各个处理机独立进行运算，彼此不发生联系)之间的一个折衷BSP模型31 BSP模型的性质和特点：（4）为PRAM模型所设计的算法，都可以采用在每个BSP处理器上模拟一些PRAM处理器的方法来实现。理论分析证明，这种模拟在常数因子范围内是最佳的，只要并行宽松度（Parallel Slackness），即每个BSP处理器所能模拟的PRAM处理器的数目足够大。在并发情况下，多个处理器同时访问分布式的存储器会引起一些问题，但使用散列方法可以使程序均匀的访问分布式存储器。BSP模型32 对BSP模型的评价 (1)在并行计算时，Valiant试图也为软件和硬件之间架起一座类似于冯o诺伊曼机的桥梁，它论证了BSP模型可以起到这样的作用，正是因为如此，BSP模型也常叫做桥模型；(2)一般而言，分布存储的MIMD模型的可编程性比较差，但在BSP模型中，如果计算和通信可以合适的平衡（例如g=1），则它在可编程方面呈现出主要的优点；(3)在BSP模型上，曾直接实现了一些重要的算法（如矩阵乘、并行前序运算、FFT和排序等），他们均避免了自动存储管理的额外开销；BSP模型33 对BSP模型的评价 (5)在BSP模型中，超级步的长度必须能够充分的适应任意的h-relation，这一点是人们最不喜欢的；(6)在BSP模型中，在超级步开始发送的消息，即使网络延迟时间比超级步的长度短，它也只能在下一个超级步才能使用；(7)BSP模型中的全局障碍同步假定是用特殊的硬件支持的，这在很多并行机中可能没有相应的硬件；(8)Valiant所提出的编程模拟环境，在算法模拟时的常数可能不是很小的，如果考虑到进程间的切换（可能不仅要设置寄存器，而且可能还有部分高速缓存），则这个常数可能很大。34 logP模型 根据技术发展的趋势，20世纪90年代末和未来的并行计算机发展的主流之一是MPP，它由成千个功能强大的处理器/存储器节点，通过具有有限带宽的和相当大的延迟的互连网络构成。建立并行计算模型应该充分考虑到这个情况，这样基于模型的并行算法才能在现有和将来的并行计算机上有效的运行。根据已有的编程经验，现有的共享存储、消息传递和数据并行等编程方式都很流行，但还没有一个公认的和占支配地位的编程方式，因此应该寻求一种与上面的编程方式无关的计算模型。而根据现有的理论模型，共享存储PRAM模型和互连网络的SIMD模型对开发并行算法还不够合适，因为它们既没有包含分布存储的情况，也没有考虑通信和同步等实际因素，从而也不能精确的反映运行在真实的并行计算机上的算法的行为。1993年D.Culer等人在分析了分布式存储计算机特点的基础上，提出了点对点通信的多计算机模型，它充分说明了互联网络的性能特性，而不涉及到具体的网络结构，也不假定算法一定要用现实的消息传递操作进行描述。35 logP模型logPlogP模型模型模型是一种分布存储的、点到点通信的多处理机模型，其中通信网络由4个主要参数来描述：（1）L(Latency)表示源处理机与目的处理机进行消息（一个或几个字）通信所需要的等待或延迟时间的上限，表示网络中消息的延迟。（2）o(overhead)表示处理机准备发送或接收每个消息的时间开销（包括操作系统核心开销和网络软件开销），在这段时间里处理不能执行其它操作。（3）g(gap)表示一台处理机连续两次发送或接收消息时的最小时间间隔，其倒数即微处理机的通信带宽。（4）P(Processor)处理机/存储器模块个数假定一个周期完成一次局部操作，并定义为一个时间单位，那么，L，o和g都可以表示成处理器周期的整数倍。36 logP模型LogP模型的特点(1)抓住了网络与处理机之间的性能瓶颈。g反映了通信带宽，单位时间内最多有L/g个消息能进行处理机间传送。(2)处理机之间异步工作，并通过处理机间的消息传送来完成同步。(3)对多线程技术有一定反映。每个物理处理机可以模拟多个虚拟处理机(VP)，当某个VP有访问请求时，计算不会终止，但VP的个数受限于通信带宽和上下文交换的开销。VP受限于网络容量，至多有L/g个VP。(4)消息延迟不确定，但延迟不大于L。消息经历的等待时间是不可预测的，但在没有阻塞的情况下，最大不超过L。(5)LogP模型鼓励编程人员采用一些好的策略，如作业分配，计算与通信重叠以及平衡的通信模式等。(6)可以预估算法的实际运行时间。37 logP模型LogP模型优点：捕捉了MPP的通讯瓶颈，隐藏了并行机的网络拓扑、路由、协议，可以应用到共享存储、消息传递、数据并行的编程模型中；但难以进行算法描述、设计和分析。LogP模型的不足之处：（1）对网络中的通信模式描述的不够深入。如重发消息可能占满带宽、中间路由器缓存饱和等未加描述。（2）LogP模型模型主要适用于消息传递算法设计，对于共享存储模式，则简单地认为远地读操作相当于两次消息传递，未考虑流水线预取技术、Cache引起的数据不一致性以及Cache命中率对计算的影响。（3）未考虑多线程技术的上下文开销。（4）LogP模型模型假设用点对点消息路由器进行通信，这增加了编程者考虑路由器上相关通信操作的负担。