计算机体系结构-第8章-并行算法课件

第8章并行算法8.1并行算法的基础知识8.2同步技术8.3程序并行性的分析8.4并行编程概述8.5并行编程模型第8章并行算法8.1并行算法的基础知识8.1并行算法的基础知识

8.1.1并行算法的定义和分类

1.并行算法的定义算法是指解题方法的精确描述，是一组有穷的规则，它们规定了解决某一特定类型问题的一系列运算。并行算法(parallelalgorithm)是指一些可同时执行的诸进程的集合，这些进程相互作用和协调动作从而达到给定问题的求解。8.1并行算法的基础知识8.1.1并行算法的2.并行算法的分类并行机的出现来源于实际应用程序中存在内在并行度这一基本事实，因此，应用程序中是否存在可挖掘并行度是并行计算机应用的关键，而并行算法作为应用程序开发的基础，自然在并行计算机应用中具有举足轻重的地位。并行算法根据运算基本对象的不同可分为数值并行算法和非数值并行算法。2.并行算法的分类

数值计算是指基于代数关系运算的一类诸如矩阵运算、多项式求值、求解线性方程组等数字计算问题。主要为数值计算方法而设计的并行算法称为数值并行算法(numericalparallelalgorithm)。非数值计算是指基于比较关系运算的一类诸如排序、选择、搜索、匹配等符号处理问题。主要为符号运算而设计的并行算法称为非数值并行算法(non-numericalparallelalgorithm)。如神经网络算法、遗传算法等。数值计算是指基于代数关系运算的一类诸

根据并行进程间相互执行顺序关系的不同可分为同步并行算法、异步并行算法和独立并行算法。同步并行算法(synchronizedparallelalgorithm)是指算法的诸进程间由于运算执行顺序而必须相互等待的并行算法。如通常的向量算法、SIMD算法及MIMD并行机上进程间需要相互等待通信结果的算法等。根据并行进程间相互执行顺序关系的不同

异步并行算法(asynchronizedparallelalgorithm)是指算法的诸进程间执行相对独立，不需要相互等待的一种算法。通常对消息传递MIMD并行机进行设计，其主要特征是在计算的整个过程中均不需要等待，而是根据最新消息决定进程的继续或终止。独立并行算法(independentparallelalgorithm)是指算法的诸进程间执行完全独立，计算的整个过程不需要任何通信的并行算法。例如气象预报应用中通常需要同时计算多个模型，以保证预报的实时性。异步并行算法(asynchroniz

根据各处理机承担的计算任务粒度的不同，可分为细粒度并行算法、中粒度并行算法和粗粒度并行算法。细粒度并行算法(finegrainparallelalgorithm)通常指基于向量和循环级并行的算法。中粒度并行算法(middlegrainparallelalgorithm)通常指基于较大的循环级并行，且并行的好处足以弥补并行带来的额外开销的算法。粗粒度并行算法(coarsegrainparallelalgorithm)通常指基于子任务级并行的算法，例如通常的基于区域分解的并行算法，它们是当前并行算法设计的主流。根据各处理机承担的计算任务粒度的不同8.1.2进程中的同构性如前所述，并行算法是对一些可同时执行的诸进程之间相互关系的描述，因此，我们这里先讨论进程中的同构性，再来介绍并行算法的表达方法。进程中的同构性是指在执行并行程序时，并行机中各处理机执行的进程相似到何种程度。图8.1描述了程序执行时进程中的同构性。8.1.2进程中的同构性图8.1进程中的同构性图8.1进程中的同构性

在多程序多数据流(MPMD)程序中的分进程是异构的，因为多个进程可以执行不同的程序代码；在单程序多数据流(SPMD)程序中的分进程是同构的，因为多个进程在不同的数据范畴内执行相同的程序代码，但不需在指令级达到同步；在单指令多数据流(SIMD)程序中的分进程是同构的，并且要求所有分进程必须在同一时间执行相同的指令。也就是说，SIMD程序是SPMD程序的一个特例。

MPMD和SPMD程序在执行时，由于各分进程在同一时间执行的是不同的指令，同时产生多个数据流，因此这两者均属于MIMD类型的程序。在多程序多数据流(MPMD)程序中的8.1.3并行算法的表达描述一个算法，可以使用自然语言进行物理描述，也可用某种编程语言进行形式化描述。语言的选用，应避免二义性，且力图直观、易懂而不苛求严格的语法格式。像描述串行算法所选用的语言一样，类Algol、Pidgin-Algol、类Pascal、类C等语言均可选用。在这些语言中，允许使用的任何数据类型都可引进。在描述并行算法时，所有描述串行算法的语句及过程调用等均可使用，如数组、集合、记录等等。根据进程中的同构性不同，对并行算法的表达采用了不同的并行语句。8.1.3并行算法的表达1.par语句当算法的若干个进程要并行执行时，可使用par语句进行描述。其格式如下：

parbeginS1；S2；…；Sn；parendpar语句主要用来描述MPMD的功能并行性，其中S1，S2，…，Sn是分进程，它们可含不同代码。当par语句执行时，它的n个分进程S1，S2，…，Sn就开始同时执行。它们的执行是互相独立的而且以不同的速率进行。当所有n个分进程终止时，par语句也就终止。1.par语句2.parfor语句当par语句中的所有分进程共享相同的程序代码时，可使用parfor语句进行描述。其格式如下：

parfor(i=1；i<=n；i++)/类C语言/{process(i)；

}

或2.parfor语句parfori:=1tondo/类Pascal语言/beginprocess(i)；

end；

parfor语句用来描述SPMD的数据并行性，其中process(i)表示某一个进程。尽管所有的进程都执行相同的程序代码，但各进程所需的参数是不相同的。parfori:=1to3.forall语句当parfor语句中的所有分进程被分派到指定的处理机上并行执行时，可使用forall语句进行描述。其格式如下：3.forall语句forall(i=1；i<=k；i++)/类C语言/{process(i)；

}

或

forallPiwhere0≤i≤kdo/类Pascal语言/process(i)；

endfor；forall(i=1；i<=k；i++)/类C语8.2同步技术

同步是个丰富的概念，且是个活跃的研究课题，跨越了许多计算机领域。在多门课程中，例如计算机系统结构、数据库、操作系统、并行处理以及编程语言都涉及到同步。在学习同步概念时，以下4个方面必须弄清楚：

(1)用户面临的同步问题，如互斥、原子性、生产者和消费者问题、哲学家就餐问题及路障同步等。8.2同步技术同步是个丰富的概念(2)用户用来解决同步问题的语言结构。这种结构可以是新语言构造、库函数或编译制导等形式。在目前共享存储器编程环境中，流行的结构是锁、信号量（若只有两个状态就是锁）、事件、临界区和路障等。这些构造称为高级构造。

(3)在多处理机体系结构中可用的同步原语，例如Decrement/Increment、Test-and-Set、Compare-and-Swap、Fetch-and-Add等，它们常常由系统硬件直接提供，因此称为低级构造。

(4)用低级同步构造实现高级同步构造的算法。在目前的许多系统中，锁仍是最基本的构造，以它为基础可构筑其它构造。(2)用户用来解决同步问题的语言

一般而言，同步操作可分为三类：原子性、控制同步和数据同步。详细的层次结构如图8.2所示。

当前的多处理机编程模型都支持路障、互斥、信号量和锁，以及生产者和消费者同步，但它们不能很好地支持原子性和“我找到了”同步。所有在共享存储器的机器（PVP、SMP、DSM等）中的同步通常使用锁原语实现，而在分布存储器的机器（MPP和机群）中的同步使用消息传递原语实现。一般而言，同步操作可分为三类：原子性图8.2各种同步类型图8.2各种同步类型8.2.1原子性原子性(atomicity)是指一个进程需要以单原子操作方式加以执行。一个原子操作是指有如下特性的一种操作。

(1)不可分：从程序员的观点看，原子操作作为单一、不可分的一步来执行，一旦开始便不可在中间加以中断，即其它进程无法见到其中间状态，仅仅原子操作最后的结果对其它进程是可见的。如果由于某种原因使原子操作中途放弃，那么必须消除已执行部分操作的影响，卷回到原子操作的初始状态。8.2.1原子性(2)有限：一旦启动原子操作，它将在有限时间内执行完。

(3)可顺序化：不可分性质的推论是可顺序化。意思是说当几个原子操作并行执行时，最后的结果就如同这些操作按某种任意的次序一个接一个地执行所得到的结果一样。如以下代码所示：parfor(i=1；i<=n；i++){atomic{x=x+1；y=y-1；}}(2)有限：一旦启动原子操作，它将在

此例中，尽管x=x+1；y=y-1；是串行操作的，atomic将以上两条语句强制捆绑在一起，使其同时输出，达到同步。关键字atomic表示n个进程中的每一个必须以原子操作方式执行两条赋值语句。由并行系统强制原子性方式完成隐式同步。此例中，尽管x=x+1；y=y-18.2.2控制同步执行控制同步(controlsynchronization)操作的进程将处于等待状态，直到程序的执行到达某种控制状态。控制同步有路障、“我找到了”(eureka)和互斥(multualexclusive)等三种。路障同步是为了保证一组进程全都到达某一控制点后再继续执行。“我找到了”同步则与路障同步完全相反，当某个进程到达某一控制点时，立即异步通知其它所有进程，而勿需处于等待状态。互斥是通过各进程互斥地执行临界段的内容，来保证对共享数据读写的正确性，从而实现同步的技术。下面我们主要介绍路障同步和互斥。8.2.2控制同步1.路障同步路障同步是通过设置路障来达到同步的，如以下代码所示：

parfor(i=1；i<=n；i++){Pi；

barrier；

Qi；

}

代码中有n个进程。执行Pi的第i个进程后跟一个barrier(路障同步)，在其之后是Qi。当执行完Pi并到达barrier语句时，它必须处于等待状态，直到所有其它进程也到达了它们各自的路障时，才开始并行执行Qi。1.路障同步2.互斥在实现互斥操作时，各处理机处理的相同代码段具有原子性且各处理机只能串行执行这一代码段。一个互斥操作是指有如下特性的一种操作。

(1)互斥：每个时刻，仅允许一个进程执行临界段。

(2)保证前进：如果多个进程试图进入临界区执行它们的临界段程序，那么至少有一个进程最后获得成功。换句话说，程序不会出现死锁或活锁。

(3)无饥饿：企图执行临界段的进程最后应该获得成功，它不会由于其它进程的协同作用而处于饥饿状态。如以下代码所示：2.互斥parfor(i=1；i<=n；i++)/有n个进程/{/每个进程执行一个parfor迭代/whileCONDITION

{independentcomputation，noncriticalsection/独立计算，非临界区/critical/互斥代码进入点/{criticalsection}/退出互斥代码段/independentcomputation，noncriticalsection}}parfor(i=1；i<=n；i++)

临界段(criticalsection)是应以互斥方式执行的代码段。CONDITION是可以被临界区修改的逻辑表达式，关键字critical指明了临界区(criticalregion)。应注意临界区是互斥的，因为每次只允许一个进程执行临界段的内容。与此相反，只要原子性是强制的，多个进程就可执行它们自己的原子区。但两者的时间复杂度是相同的，均为O(n)，其中n为进程的个数。临界段(criticalsecti8.2.3数据同步执行一个数据同步(datasynchronization)操作的进程将处于等待状态，直到程序执行到达某种数据状态。数据同步的例子包括信号量和锁(semaphore&lock)、生产者和消费者(producer&consumer)、池和队列(pool&queue)等。在大多数当今的系统中，都用数据同步来实现原子性。如以下代码所示：8.2.3数据同步parfor(i=1；i<=n；i++){lock(S)；x=x+1；y=y-1；unlock(S)；

}

其中锁同步依赖于信号量S中的数据状态。控制同步只依赖于程序的控制状态，它不受程序数据状态的影响。数据同步使用时非常灵活，但控制同步通常要比数据同步更容易理解。parfor(i=1；i<=n；i++)8.4并行编程概述8.4.1并行编程概况对于所希望的应用，很多现存的并行代码似乎是不存在的，即使有，也常不能用于用户的并行机上，因为并行代码原来都是为不同的并行结构(如SMP、MPP等)而写的。8.4并行编程概述8.4.1并行编程概况

并行编程的问题是：(1)并行算法范例至今尚不能被很好地理解和广泛地接受；

(2)并行编程是建立在不同的计算模型（PRAM模型、异步PRAM模型、BSP模型、logP模型、C3模型）上的，而它们没有谁能象冯·诺依曼模型那样被普遍的接受和认可；

(3)绝大部分被使用的并行编程语言都是Fortran和C的推广，它们都不能充分地表达不同并行结构的特点，既不成熟也不通用；

(4)并行编程工具依赖于具体的并行机结构和计算机的更迭，既不通用也不稳定，在某个平台上开发的并行程序，很难移植到别的或将来的并行机上。并行编程的问题是：(1)并行算法范例至

尽管并行编程问题很多，但也有不少进展：

(1)已经开发了很多并行算法，虽然它们大多基于理想的PRAM(ParallelRandom-AccessMachine)模型，但有些已被实际采用；

(2)少量的并行算法范例已出现，并且正逐渐被接受；

(3)编程类型渐趋汇聚于两类：用于PVP、SMP和DSM的共享变量的单地址空间模型和用于MPP和机群的消息传递的多地址空间模型，SIMD模型已退出主流，但对专用领域(如信号、图像处理，多媒体处理等)仍是有用的；

(4)并行编程模型渐趋汇聚于三类标准模型：数据并行(如HPF)，消息传递(如PVM和MPI)和共享变量(如ANSI和X3H5)。在表8.1中，将并行编程所获得的进展在五个方面与串行编程进行了比较。尽管并行编程问题很多，但也有不少进表8.1串行编程和并行编程比较一览表

串行编程并行编程应用领域科学和工程计算，数据处理，商务应用等算法范例分而治之，分枝限界，动态规划，回溯，贪心计算交互，异步迭代，分而治之，流水线，进程农庄，工作池编程模型冯·诺依曼隐式并行、数据并行、共享变量、消息传递编程语言Fortran，C，Cobol，4GLKAP，Fortran90，HPF，X3H5，PVM，MPI体系结构不同类型的单处理机共享内存（PVP，SMP，DSM）数据并行（SIMD）消息传递（MPP，Cluster）表8.1串行编程和并行编程比较一览表

串行编程并行编程应8.4.2并行编程方法现今编程模型主要有隐式并行、数据并行、消息传递和共享变量等四种。当在实际的并行机上根据它们设计并行程序时，绝大部分均是采用扩展Fortran和C语言的方法。

目前有三种扩展的方法：(1)库函数(librarysubroutines)法：除了串行语言所包含的库函数外，一组新的支持并行性和交互操作的库函数(如MPI消息传递库和POSIXPthreads多线程库)引入到并行编程中；

(2)新语言构造(newlanguageconstructs)法：采用某些新的语言构造来帮助并行编程以支持并行性和交互操作(如Fortran90中的聚集数组操作)；

(3)编译制导(compilerdirectives)法：编程语言保持不变，但是加进称之为编译制导(pragma)的格式注释。8.4.2并行编程方法

图8.4中用一段简单代码来说明这些方法。

所有3个并行程序均执行相同的如图8.4(a)所示的串行C代码的计算。

图8.4(b)使用库函数的方法实现之，其中两个循环由p个进程并行执行，两个库函数my_process_id()和number_of_processes()开拓并行性，barrier()函数确保第一个循环执行后所有进程被同步，这样第二个循环能使用第一个循环更新后的数组A的正确值；图8.4中用一段简单代码来说明这些图8.4三种并行化方法for(i=0；i<N；i++)A[i]=B[i]*B[i+1]；

for(i=0；i<N；i++)C[i]=A[i]+A[i+1]；图(a)顺序化代码段

id=my_process_id()；

p=number_of_processes()；

for(i=id；i<N；i=i+p)A[i]=B[i]*B[i+1]；

barrier()；/路障同步，解决先写后读的数据相关/for(i=id；i<N；i=i+p)C[i]=A[i]+A[i+1]；图(b)使用库函数的等效并行代码图8.4三种并行化方法for(i=0；i<

图8.4(c)展示了使用新语言构造执行并行操作，Fortran90数组赋值结构语句执行N个元素相乘，然后以一个赋值语句进行赋值，两个数组赋值之间无需显式同步，因为Fortran90语句是松散同步的，即在下一语句开始执行之前，一条赋值语句的所有操作均已完成；图8.4(d)展示了编译制导法实现并行操作，并行pragma指示下一语句应并行执行，SGI的pfor指使系统并行执行下一循环，同步pragma产生一个路障同步。图8.4(c)展示了使用新语言构造执行并行操作，Fo图8.4三种并行化方法my_process_id()，number_of_processes()，andbarrier()A(0：N-1)=B(0：N-1)*B(1：N)/采用蕴式同步/C(0：N-1)=A(0：N-1)+A(1：N)

图(c)使用数组操作Fortran90等效代码

#pragmaparallel/以#pragma开头的表示编译器命令/#pragmashared(A，B，C)#pragmalocal(i){图8.4三种并行化方法my_proces图8.4三种并行化方法#pragmapforiterate(i=0；N；1)/此命令表示以并行方式执行迭代操作/for(i=0；i<N；i++)A[i]=B[i]*B[i+1]；

#pragmasynchronize/产生一个路障同步/#pragmapforiterate(i=0；N；1)for(i=0；i<N；i++)C[i]=A[i]+A[i+1]；

}

图(d)SGIpowerC中使用pragma的等效代码图8.4三种并行化方法#pragma表8.2三种并行编程方法的优缺点方法优点缺点例子库函数易于实现，不需要新的编译器没有编译检查、分析和优化MPI、PVM、CrayCraft新语言构造允许编译检查、分析和优化难以实现，需要一个新的编译器Fortran90、CrayCraft编译制导是库函数和新语言构造两者优缺点的折衷，其显著优点是“普通串行程序+格式注释”，可在任何串行平台上编译HPF、CrayCraft表8.2三种并行编程方法的优缺点方法优点缺点例子库函数易

库函数是目前使用最广泛的方法。所有并行化和交互功能由附加到顺序C或Fortran中的一组程序实现。因此，原来的串行编译器也能够使用，不需要任何修改，编程者只要在原来的串行程序中加入对并行库函数的调用，就可以实现并行编程。然而，由于没有新的编译器的支持，用户就丧失了编译时间分析、错误检查和优化的机会。库函数是目前使用最广泛的方法。所有并8.4.3并行算法范例所谓并行算法范例(parallelalgorithmicparadigms)是指构造运行在并行机系统上的并行算法的方法，又称并行编程范例(parallelprogrammingparadigms)。

目前已出现了多种算法范例，在一个实际的并行程序中，这些范例常以各种方法组合使用。

在图8.5中给出了的五种常用的并行算法范例。

8.4.3并行算法范例图8.55种并行算法范例图8.55种并行算法范例

1.阶段并行(phaseparallel)

如图8.5(a)所示，一个并行程序由一些超步(supersteps)组成，每一个超步分为计算和交互两个阶段。在计算阶段，多个进程中的每一个完成一个独立计算C，处于同一计算阶段的所有进程并行执行。此后是交互阶段，在这一阶段，这些进程完成一个或多个同步交互操作，例如一个路障同步或一个锁定通信，然后再执行下一个超步。这种阶段并行也称之为松散同步并行，其优点是方便了调试和性能分析，其缺点是计算和交互过程不能重叠且很难维持负载平衡。1.阶段并行(phaseparallel)2.分而治之(divideandconquer)

如图8.5(b)所示，一个父进程将其工作负载分成若干个较小的负载并将它们分派给一些子进程，然后这些子进程并行地完成各自的计算，所产生的结果由父进程进行合并。这种分割和合并的过程很自然地导致递归，其缺点是很难达到负载平衡。

3.流水线(pipeline)

如图8.5(c)所示，由一些进程形成一条虚拟的流水线，连续的数据流进入此流水线，处于不同流水级上的进程以重叠的方式依次轮流地执行不同的操作来达到整体并行的效果。2.分而治之(dividean4.进程农庄(processfarm)

如图8.5(d)所示，一个主进程执行并行程序中基本的顺序部分并派生出一些从进程去执行并行的工作负载。当一个从进程完成其工作时便通知主进程，让其再分派一个新的工作负载给它。整个工作过程由主进程协调完成，其缺点是主进程很可能会成为系统瓶颈。4.进程农庄(processf5.工作池(workpool)

如图8.5(e)所示，工作池以全局数据结构方式实现，如一个无序集合、一个队列或是一个优先级队列。开始时，池中只有一件工作，任何空闲进程均可从该池中获取一件工作并加以执行，执行后可能产生会0个、1个或多个新工作并把它们放回池中，以供其它的空闲进程获取并执行。当工作池为空时，并行程序结束。此种范例容易实现负载平衡，因为工作负载是动态分配给空闲进程的。然而实现工作池能被多个进程有效访问并非易事，特别是在消息传递模型中。正因为如此，工作池算法范例常用于共享变量模型。5.工作池(workpool)8.5并行编程模型

并行编程模型(parallelprogrammingmodels)是一种程序抽象的集合，它给程序员提供了一幅计算机硬件/软件系统透明的简图，程序员利用这些模型就可以为多处理机、多计算机和工作站机群等设计并行程序。并行编程模型包括蕴式并行编程模型和显式并行编程模型。本节主要介绍蕴式并行编程模型和三种主要的显式并行编程模型(数据并行、共享变量和消息传递)。8.5并行编程模型并行编程模型(8.5.1蕴式并行性显式并行性(explicitparallelism)是指在源程序中由程序员使用专用语言构造、编译器命令或库函数调用对并行性加以显式说明。如果程序员不显式地说明并行性，而是让编译器和运行支持系统自动加以开发，这种并行性称之为蕴式并行性(implicitparallelism)。蕴式并行性的一个最流行方法是对顺序程序实行自动并行化。由编译器对顺序程序的源代码进行相关性分析，然后使用一组程序变换技术将顺序代码转换成自然并行Fortran代码。称这种编译器为并行化编译器或重构编译器。8.5.1蕴式并行性8.5.2显式并行模型由于显式并行性是在源程序中由程序员编程时显式说明的，因此并行编程模型通常指的就是这类显式并行编程模型。并行编程模型有：数据并行模型、消息传递模型、共享变量模型、面向对象模型、函数和逻辑模型等。这里我们重点介绍三种占统治地位的并行编程模型，即：数据并行模型、消息传递模型和共享变量模型。

8.5.2显式并行模型1.数据并行模型(data-parallelmodel)

数据并行表现在程序中，就是对循环中大量数据进行相同或不同的、互不影响的操作，可以带来大量并行操作的高度并行性。1.数据并行模型(data-pa

数据并行模型的实现有单指令多数据流(SIMD)和单程序多数据流(SPMD)两种模式。SIMD是一种逐条指令同步控制的、细粒度的并行模式，适合于SIMD类型的并行机，并且没有专门的编程语言支持，没有提供全局地址空间，而是建立在消息传递机制上。而SPMD模式适合于MIMD类型的分布式存储并行系统，由专门的并行编程语言支持，支持中粒度并行，反映在语句块和循环迭代一级的同步。基于SPMD数据并行编程，用户可以将整个系统看做是一个统一的全局地址空间，由编译器实现程序的从逻辑空间到物理空间的映射。例如，CrayT3D就支持消息传递(MPMD)和SPMD数据并行编程两种模式。数据并行模型的实现有单指令多数据流(SIM

数据并行模型有如下特征：

(1)单线程化(singlecontrolthreading)

从程序员的观点，一个数据并行程序只由一个进程执行，具有单一控制线程；就控制流而论，一个数据并行程序就像一个顺序程序一样。

(2)并行操作于聚合数据结构上数据并行程序的一个单步(语句)，可指定同时作用在不同数组元素或其它聚合数据结构上的多个操作。数据并行模型有如下特征：(3)松散同步(looselysynchronous)

在数据并行程序的每条语句之后，均有一个隐含的同步，相对于SIMD机器中每条指令之后的紧同步而言，这种语句级的同步是松散的。

(4)全局命名空间(globalnamingspace)

采用数据并行编程语言编程时，无论系统是否支持全局编址，用户看到的总是全局空间。用户程序空间到系统存储空间的映射由编译系统完成。在全局编址的系统中，远程存储器的访问被编译成远程存储单元的读/写操作。在无全局编址的系统中，被编译成消息传递函数调用。(3)松散同步(looselysy(5)隐式相互作用(implicitinteraction)

因为数据并行程序的每条语句之后都存在着一个隐含的路障，所以不需要显式同步，通信可由变量指派而隐含地完成。

(6)隐式数据分配(implicitdataallocation)

程序员在编程时不需要明确地指定数据如何分配，如何改进数据局部性和减少通信开销都将隐含地由编译器完成。(5)隐式相互作用(implicit根据积分公式：令函数f(x)=4/(1+x2)，则有：而f(x)的图像如图8.6所示。由于求π值的近似计算方法有很好的并行性，同时由于它用到了集合通信中的广播和归约操作，因此这里将较为详细地对它进行介绍。并行编程举例根据积分公式：令函数f(x)=4/(1+x2)，则有：而f图8.6求π近似值方法的示意图图8.6求π近似值方法的示意图

计算f(x)图像下面从0到1之间的面积即为π的值。而此面积可以用图8.6所示的5个小矩形面积的和来近似，矩形的高度取函数在矩形中间点的取值。当用更多的矩形来划分时，该近似值就越接近于真实的π值。设将0到1的区间划分为N个矩形，则近似公式如图8.7所示。图8.7求π的近似公式计算f(x)图像下面从0到1之间的面积即为

例8.6

计算π函数的数据并行程序举例下面的简单例子阐述了数据并行化的概念。该数据并行代码的功能是计算π的值。这里我们使用类似HPF的C记号来加以表示。例8.6计算π函数的数据并行程序举例main(){doublelocal[N]，tmp[N]，pi，w；

longi，j，t，N=1000000；

A:w=1.0/N；

B:forall(i=0；i<N；i++){P:local[i]=(i+0.5)*w；/由于采用单一控制线程，N个元素同时计算/Q:tmp[i]=4.0/(1.0+local[i]*local[i])；

}C:pi=sum(tmp)；/对所有的tmp元素归约求和/D:printf("piis%f\n"，pi*w)；

}main(){

该程序有四条语句A、B(它有二个子语句P和Q)、C和D。程序员可假设这四条语句以一个接一个的单进程方式执行。但这个语句可同时对多个数据项完成相同操作。语句A和D是一般的顺序语句。语句C完成对tmp数组所有N个元素的归约求和并将结果赋值给变量pi。语句P同时对N个右部表达式求值且更新局部数据的所有N个元素。在语句Q中执行任何操作之前，必须先完成语句P中局部数据的所有N个元素的更新。类似地，在语句C中进行归约操作之前，必须先完成语句Q中对所有tmp元素的赋值。该程序有四条语句A、B(它有二个子语2.消息传递模型(message-passingmodel)

在消息传递模型中，程序员必须通过显式地发送和接收消息来实现处理机间的数据交换。此时，每个并行进程均有自己独立的地址空间，相互之间的访问不能直接进行，必须通过显式消息传递来实现。因此，并行开销比较大，主要适合于粗粒度的并行计算。2.消息传递模型(messag

由于消息传递模型要求用户很好地分解问题，组织不同进程间的数据交换，并行计算粒度大，特别适合于大规模可扩展并行算法。并且，当前条件下，在分布式存储或分布共享存储MPP系统和NOWs上，当处理机台数较多时，只有消息传递才能充分发挥并行机的潜在性能。因此，消息传递是当前并行计算领域的一个重要的并行编程模型，被当前所有的分布式存储MPP、分布共享存储DSM、共享存储SMP和NOWs所支持。由于消息传递模型要求用户很好地分解

消息传递模型有如下特征：

(1)多线程化(multithreading)

消息传递程序由多个进程组成，其中每个进程有自己的控制线程且可执行不同代码。它支持功能并行(MPMD)和数据并行(SPMD)两者。

(2)异步并行性(asynchronousparallelism)

消息传递程序的进程异步执行，使用如路障和锁定通信那样的专用操作对进程加以同步。应注意的是细粒度MIMD不适合当今的消息传递系统。消息传递模型有如下特征：(3)分离的地址空间(separateaddressspace)

并行程序的进程驻留在不同的地址空间。一个进程中的数据变量对其它进程来讲是看不见的。因此一个进程不能读写另一个进程的变量。进程间的交互需通过执行专用的消息传递操作（或称消息传递原语）实现，例如调用MPI库函数实现消息传递操作。(3)分离的地址空间(separat(4)显式交互(explicitinteraction)

程序必须解决所有的交互问题，包括数据映射、通信、同步和聚集。工作负载的分配通常用拥有者计算法则来完成，即由拥有数据块的进程来完成相应计算。

(5)显式分配(explicitallocation)

工作负载和数据均需用户用显式方法分配给进程。为减少设计和编制代码复杂性，常通过使用单代码方法书写SPMD程序来实现应用问题的求解。(4)显式交互(expliciti

当前，最流行的网络并行计算消息传递库为PVM和MPI。其中，PVM是并行虚拟机器(ParallelVirtualMachine)的缩写，是基于消息传递的并行通信库，异构性和可移植性是其设计的主要目的。通过它，用户可以将一组由不同网络连接起来的、不同类型的、采用UNIX操作系统的计算机看做是一台虚拟的并行机，依靠整体的计算能力和存储能力来解决一些以前只能用超级并行机才能解决的大型应用问题。而MPI是消息传递接口(MessagePassingInterface)的缩写，是1994年推出的，目的在于将众多消息传递库标准化，以保证并行编程的可移植性。当前，最流行的网络并行计算消息传

例8.7

计算π函数的数据并行程序举例在下面的代码段中我们使用了具有MPI的C语言记号。

#defineN1000000main(){doublelocal，pi，w；

longi，taskid，numtask；例8.7计算π函数的数据并行程序举例A:w=1.0/N；

MPI_Init(&argc，&argv)；

MPI_Comm_rank(MPI_COMM_WORLD，&taskid)；

MPI_Comm_size(MPI_COMM_WORLD，&numtask)；

B:forall(i=taskid；i<N；i=i+numtask){P:local=(i+0.5)*w；

Q:local=4.0/(1.0+local*local)；

}A:w=1.0/N；C:MPI_Reduce(&local，&pi，1，MPI_Double，MPI_MAX，0，MPI_COMM_WORLD)；

D:if(taskid==0)printf("piis%f\n"，pi*w)；

MPI_Finalize()；

}C:MPI_Reduce(&local，&pi

一个通信子(Communicator)是一个进程组加上一个现场。进程组是进程的有限（指进程组有有限个进程n，其中n为组的大小）和定序（指某个进程在组中的排序）集。MPI_COMM_WORLD是系统默认的通信子，表示所有的进程。例8.7程序中出现的MPI原语的通用格式及含义如下：

MPI_Init(&argc，&argv)：MPI初始化。它是MPI的第一个调用，它完成MPI程序所有的初始化工作。所有MPI程序的第一条可执行语句都是这条语句。一个通信子(Communicator)是一MPI_Comm_rank(MPI_COMM_WORLD，&taskid)：此通信原语可得到进程在组中的排序，有了这一排序号，不同的进程就可以将自身和其它的进程区别开来，实现各进程的并行和协作。

MPI_Comm_size(MPI_COMM_WORLD，&numtask)：此通信原语可得到组的大小，即组内进程的个数，不同的进程通过这一调用得知在给定的通信域中一共有多少个进程在并行执行。MPI_Comm_rank(MPI_MPI_Reduce(SendAddress，RecvAddress，Count，Datatype，Op，Root，Comm)中的7个参数意思分别为：发送进程要发送的数据地址、接收进程要存入的数据地址、数据的个数、数据的类型、归约操作符、结果存入Root进程中的RecvAddress、通信子。通过此调用将多个进程的一个或多个数据归约到Root进程，完成指定的操作后，将结果存入到相应的地址。

MPI_Finalize()：MPI结束。它是MPI程序的最后一个调用，它结束MPI程序的运行，它是MPI程序的最后一条可执行语句，否则程序的运行结果是不可预知的。由于采用分离的地址空间（多地址空间），可使用相同变量名，如local，而采用数据并行时，写成local（i）；采用共享变量时，写成local，但同时用shared/local加以说明。MPI_Reduce(SendAdd3.共享变量模型(shared-variablemodel)

共享变量模型又称共享存储器模型，它与数据并行模型类似，因为它有单地址(全局命名)空间。它又与消息传递模型类似，因为它是多线程化和异步的。由于数据驻留在单一共享地址空间中，因此不需要对数据加以显式分配。工作负载的分配可以用显式也可用蕴式方法。通信需通过读、写共享变量蕴式地实现，但同步却必须是显式的。3.共享变量模型(shared

例8.8

计算π函数的数据并行程序举例这里用类似C语言记号说明共享变量并行编程模型的概念。

#defineN1000000main(){doublelocal，pi=0.0，w；

longi；

A:w=1.0/N；例8.8计算π函数的数据并行程序B:#pragmaparallel#pragmashared(pi，w)#pragmalocal(i，local){/同步必须是显式的/#pragmapforiterate(i=0；N；1)/以并行方式执行下一循环/for(i=0；i<N；i++){P:local=(i+0.5)*w；

Q:local=4.0/(1.0+local*local)；

}B:#pragmaparallelC:#pragmacritical/同步必须是显式的(临界区)/{pi=pi+local；

}D:printf("piis%f\n"，pi*w)；

}

综合前面介绍的三种主要的显式并行编程模型（数据并行、消息传递、共享变量），其主要特征比较如表8.3所示。C:#pragmacritical表8.3数据并行、消息传递和共享变量并行编程模型的主要特征特征数据并行消息传递共享变量控制流（线程化）单多多同步松散同步异步异步地址空间单多单交互隐式显式显式数据分配隐式或半显式显式隐式或半显式表8.3数据并行、消息传递和共享变量并行编程模型的主要特第8章并行算法8.1并行算法的基础知识8.2同步技术8.3程序并行性的分析8.4并行编程概述8.5并行编程模型第8章并行算法8.1并行算法的基础知识8.1并行算法的基础知识

8.1.1并行算法的定义和分类

1.并行算法的定义算法是指解题方法的精确描述，是一组有穷的规则，它们规定了解决某一特定类型问题的一系列运算。并行算法(parallelalgorithm)是指一些可同时执行的诸进程的集合，这些进程相互作用和协调动作从而达到给定问题的求解。8.1并行算法的基础知识8.1.1并行算法的2.并行算法的分类并行机的出现来源于实际应用程序中存在内在并行度这一基本事实，因此，应用程序中是否存在可挖掘并行度是并行计算机应用的关键，而并行算法作为应用程序开发的基础，自然在并行计算机应用中具有举足轻重的地位。并行算法根据运算基本对象的不同可分为数值并行算法和非数值并行算法。2.并行算法的分类

数值计算是指基于代数关系运算的一类诸如矩阵运算、多项式求值、求解线性方程组等数字计算问题。主要为数值计算方法而设计的并行算法称为数值并行算法(numericalparallelalgorithm)。非数值计算是指基于比较关系运算的一类诸如排序、选择、搜索、匹配等符号处理问题。主要为符号运算而设计的并行算法称为非数值并行算法(non-numericalparallelalgorithm)。如神经网络算法、遗传算法等。数值计算是指基于代数关系运算的一类诸

根据并行进程间相互执行顺序关系的不同可分为同步并行算法、异步并行算法和独立并行算法。同步并行算法(synchronizedparallelalgorithm)是指算法的诸进程间由于运算执行顺序而必须相互等待的并行算法。如通常的向量算法、SIMD算法及MIMD并行机上进程间需要相互等待通信结果的算法等。根据并行进程间相互执行顺序关系的不同

异步并行算法(asynchronizedparallelalgorithm)是指算法的诸进程间执行相对独立，不需要相互等待的一种算法。通常对消息传递MIMD并行机进行设计，其主要特征是在计算的整个过程中均不需要等待，而是根据最新消息决定进程的继续或终止。独立并行算法(independentparallelalgorithm)是指算法的诸进程间执行完全独立，计算的整个过程不需要任何通信的并行算法。例如气象预报应用中通常需要同时计算多个模型，以保证预报的实时性。异步并行算法(asynchroniz

根据各处理机承担的计算任务粒度的不同，可分为细粒度并行算法、中粒度并行算法和粗粒度并行算法。细粒度并行算法(finegrainparallelalgorithm)通常指基于向量和循环级并行的算法。中粒度并行算法(middlegrainparallelalgorithm)通常指基于较大的循环级并行，且并行的好处足以弥补并行带来的额外开销的算法。粗粒度并行算法(coarsegrainparallelalgorithm)通常指基于子任务级并行的算法，例如通常的基于区域分解的并行算法，它们是当前并行算法设计的主流。根据各处理机承担的计算任务粒度的不同8.1.2进程中的同构性如前所述，并行算法是对一些可同时执行的诸进程之间相互关系的描述，因此，我们这里先讨论进程中的同构性，再来介绍并行算法的表达方法。进程中的同构性是指在执行并行程序时，并行机中各处理机执行的进程相似到何种程度。图8.1描述了程序执行时进程中的同构性。8.1.2进程中的同构性图8.1进程中的同构性图8.1进程中的同构性

在多程序多数据流(MPMD)程序中的分进程是异构的，因为多个进程可以执行不同的程序代码；在单程序多数据流(SPMD)程序中的分进程是同构的，因为多个进程在不同的数据范畴内执行相同的程序代码，但不需在指令级达到同步；在单指令多数据流(SIMD)程序中的分进程是同构的，并且要求所有分进程必须在同一时间执行相同的指令。也就是说，SIMD程序是SPMD程序的一个特例。

MPMD和SPMD程序在执行时，由于各分进程在同一时间执行的是不同的指令，同时产生多个数据流，因此这两者均属于MIMD类型的程序。在多程序多数据流(MPMD)程序中的8.1.3并行算法的表达描述一个算法，可以使用自然语言进行物理描述，也可用某种编程语言进行形式化描述。语言的选用，应避免二义性，且力图直观、易懂而不苛求严格的语法格式。像描述串行算法所选用的语言一样，类Algol、Pidgin-Algol、类Pascal、类C等语言均可选用。在这些语言中，允许使用的任何数据类型都可引进。在描述并行算法时，所有描述串行算法的语句及过程调用等均可使用，如数组、集合、记录等等。根据进程中的同构性不同，对并行算法的表达采用了不同的并行语句。8.1.3并行算法的表达1.par语句当算法的若干个进程要并行执行时，可使用par语句进行描述。其格式如下：

parbeginS1；S2；…；Sn；parendpar语句主要用来描述MPMD的功能并行性，其中S1，S2，…，Sn是分进程，它们可含不同代码。当par语句执行时，它的n个分进程S1，S2，…，Sn就开始同时执行。它们的执行是互相独立的而且以不同的速率进行。当所有n个分进程终止时，par语句也就终止。1.par语句2.parfor语句当par语句中的所有分进程共享相同的程序代码时，可使用parfor语句进行描述。其格式如下：

parfor(i=1；i<=n；i++)/类C语言/{process(i)；

}

或2.parfor语句parfori:=1tondo/类Pascal语言/beginprocess(i)；

end；

parfor语句用来描述SPMD的数据并行性，其中process(i)表示某一个进程。尽管所有的进程都执行相同的程序代码，但各进程所需的参数是不相同的。parfori:=1to3.forall语句当parfor语句中的所有分进程被分派到指定的处理机上并行执行时，可使用forall语句进行描述。其格式如下：3.forall语句forall(i=1；i<=k；i++)/类C语言/{process(i)；

}

或

forallPiwhere0≤i≤kdo/类Pascal语言/process(i)；

endfor；forall(i=1；i<=k；i++)/类C语8.2同步技术

同步是个丰富的概念，且是个活跃的研究课题，跨越了许多计算机领域。在多门课程中，例如计算机系统结构、数据库、操作系统、并行处理以及编程语言都涉及到同步。在学习同步概念时，以下4个方面必须弄清楚：

(1)用户面临的同步问题，如互斥、原子性、生产者和消费者问题、哲学家就餐问题及路障同步等。8.2同步技术同步是个丰富的概念(2)用户用来解决同步问题的语言结构。这种结构可以是新语言构造、库函数或编译制导等形式。在目前共享存储器编程环境中，流行的结构是锁、信号量（若只有两个状态就是锁）、事件、临界区和路障等。这些构造称为高级构造。

(3)在多处理机体系结构中可用的同步原语，例如Decrement/Increment、Test-and-Set、Compare-and-Swap、Fetch-and-Add等，它们常常由系统硬件直接提供，因此称为低级构造。

(4)用低级同步构造实现高级同步构造的算法。在目前的许多系统中，锁仍是最基本的构造，以它为基础可构筑其它构造。(2)用户用来解决同步问题的语言

一般而言，同步操作可分为三类：原子性、控制同步和数据同步。详细的层次结构如图8.2所示。

当前的多处理机编程模型都支持路障、互斥、信号量和锁，以及生产者和消费者同步，但它们不能很好地支持原子性和“我找到了”同步。所有在共享存储器的机器（PVP、SMP、DSM等）中的同步通常使用锁原语实现，而在分布存储器的机器（MPP和机群）中的同步使用消息传递原语实现。一般而言，同步操作可分为三类：原子性图8.2各种同步类型图8.2各种同步类型8.2.1原子性原子性(atomicity)是指一个进程需要以单原子操作方式加以执行。一个原子操作是指有如下特性的一种操作。

(1)不可分：从程序员的观点看，原子操作作为单一、不可分的一步来执行，一旦开始便不可在中间加以中断，即其它进程无法见到其中间状态，仅仅原子操作最后的结果对其它进程是可见的。如果由于某种原因使原子操作中途放弃，那么必须消除已执行部分操作的影响，卷回到原子操作的初始状态。8.2.1原子性(2)有限：一旦启动原子操作，它将在有限时间内执行完。

(3)可顺序化：不可分性质的推论是可顺序化。意思是说当几个原子操作并行执行时，最后的结果就如同这些操作按某种任意的次序一个接一个地执行所得到的结果一样。如以下代码所示：parfor(i=1；i<=n；i++){atomic{x=x+1；y=y-1；}}(2)有限：一旦启动原子操作，它将在

此例中，尽管x=x+1；y=y-1；是串行操作的，atomic将以上两条语句强制捆绑在一起，使其同时输出，达到同步。关键字atomic表示n个进程中的每一个必须以原子操作方式执行两条赋值语句。由并行系统强制原子性方式完成隐式同步。此例中，尽管x=x+1；y=y-18.2.2控制同步执行控制同步(controlsynchronization)操作的进程将处于等待状态，直到程序的执行到达某种控制状态。控制同步有路障、“我找到了”(eureka)和互斥(multualexclusive)等三种。路障同步是为了保证一组进程全都到达某一控制点后再继续执行。“我找到了”同步则与路障同步完全相反，当某个进程到达某一控制点时，立即异步通知其它所有进程，而勿需处于等待状态。互斥是通过各进程互斥地执行临界段的内容，来保证对共享数据读写的正确性，从而实现同步的技术。下面我们主要介绍路障同步和互斥。8.2.2控制同步1.路障同步路障同步是通过设置路障来达到同步的，如以下代码所示：

parfor(i=1；i<=n；i++){Pi；

barrier；

Qi；

}

代码中有n个进程。执行Pi的第i个进程后跟一个barrier(路障同步)，在其之后是Qi。当执行