计算机系统结构 陈智勇 第8章 并行算法

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

8.1.1并行算法的定义和分类1.并行算法的定义算法是指解题方法的精确描述，是一组有穷的规则，它们规定了解决某一特定类型问题的一系列运算。并行算法(parallelalgorithm)是指一些可同时执行的诸进程的集合，这些进程相互作用和协调动作从而达到给定问题的求解。2.并行算法的分类并行机的出现来源于实际应用程序中存在内在并行度这一基本事实，因此，应用程序中是否存在可挖掘并行度是并行计算机应用的关键，而并行算法作为应用程序开发的基础，自然在并行计算机应用中具有举足轻重的地位。并行算法根据运算基本对象的不同可分为数值并行算法和非数值并行算法。数值计算是指基于代数关系运算的一类诸如矩阵运算、多项式求值、求解线性方程组等数字计算问题。主要为数值计算方法而设计的并行算法称为数值并行算法(numericalparallelalgorithm)。非数值计算是指基于比较关系运算的一类诸如排序、选择、搜索、匹配等符号处理问题。主要为符号运算而设计的并行算法称为非数值并行算法(non-numericalparallelalgorithm)。如神经网络算法、遗传算法等。根据并行进程间相互执行顺序关系的不同可分为同步并行算法、异步并行算法和独立并行算法。同步并行算法(synchronizedparallelalgorithm)是指算法的诸进程间由于运算执行顺序而必须相互等待的并行算法。如通常的向量算法、SIMD算法及MIMD并行机上进程间需要相互等待通信结果的算法等。异步并行算法(asynchronizedparallelalgorithm)是指算法的诸进程间执行相对独立，不需要相互等待的一种算法。通常对消息传递MIMD并行机进行设计，其主要特征是在计算的整个过程中均不需要等待，而是根据最新消息决定进程的继续或终止。独立并行算法(independentparallelalgorithm)是指算法的诸进程间执行完全独立，计算的整个过程不需要任何通信的并行算法。例如气象预报应用中通常需要同时计算多个模型，以保证预报的实时性。根据各处理机承担的计算任务粒度的不同，可分为细粒度并行算法、中粒度并行算法和粗粒度并行算法。细粒度并行算法(finegrainparallelalgorithm)通常指基于向量和循环级并行的算法。中粒度并行算法(middlegrainparallelalgorithm)通常指基于较大的循环级并行，且并行的好处足以弥补并行来的额外开销的算法。粗粒度并行算法(coarsegrainparallelalgorithm)通常指基于子任务级并行的算法，例如通常的基于区域分解的并行算法，它们是当前并行算法设计的主流。8.1.2进程中的同构性如前所述，并行算法是对一些可同时执行的诸进程之间相互关系的描述，因此，我们这里先讨论进程中的同构性，再来介绍并行算法的表达方法。进程中的同构性是指在执行并行程序时，并行机中各处理机执行的进程相似到何种程度。图8.1描述了程序执行时进程中的同构性。图8.1进程中的同构性在多程序多数据流(MPMD)程序中的分进程是异构的，因为多个进程可以执行不同的程序代码；在单程序多数据流(SPMD)程序中的分进程是同构的，因为多个进程在不同的数据范畴内执行相同的程序代码，但不需在指令级达到同步；在单指令多数据流(SIMD)程序中的分进程是同构的，并且要求所有分进程必须在同一时间执行相同的指令。也就是说，SIMD程序是SPMD程序的一个特例。MPMD和SPMD程序在执行时，由于各分进程在同一时间执行的是不同的指令，同时产生多个数据流，因此这两者均属于MIMD类型的程序。8.1.3并行算法的表达描述一个算法，可以使用自然语言进行物理描述，也可用某种编程语言进行形式化描述。语言的选用，应避免二义性，且力图直观、易懂而不苛求严格的语法格式。像描述串行算法所选用的语言一样，类Algol、Pidgin-Algol、类Pascal、类C等语言均可选用。在这些语言中，允许使用的任何数据类型都可引进。在描述并行算法时，所有描述串行算法的语句及过程调用等均可使用，如数组、集合、记录等等。根据进程中的同构性不同，对并行算法的表达采用了不同的并行语句。1.par语句当算法的若干个进程要并行执行时，可使用par语句进行描述。其格式如下：parbeginS1；S2；…；Sn；parendpar语句主要用来描述MPMD的功能并行性，其中S1，S2，…，Sn是分进程，它们可含不同代码。当par语句执行时，它的n个分进程S1，S2，…，Sn就开始同时执行。它们的执行是互相独立的而且以不同的速率进行。当所有n个分进程终止时，par语句也就终止。2.parfor语句当par语句中的所有分进程共享相同的程序代码时，可使用parfor语句进行描述。其格式如下：parfor(i=1；i<=n；i++)/类C语言/{process(i)；}或parfori:=1tondo/类Pascal语言/beginprocess(i)；end；parfor语句用来描述SPMD的数据并行性，其中process(i)表示某一个进程。尽管所有的进程都执行相同的程序代码，但各进程所需的参数是不相同的。3.forall语句当parfor语句中的所有分进程被分派到指定的处理机上并行执行时，可使用forall语句进行描述。其格式如下：forall(i=1；i<=k；i++)/类C语言/{process(i)；}或forallPiwhere0≤i≤kdo/类Pascal语言/process(i)；endfor；8.1.4并行算法中的同步与通信1.同步同步是在时间上强迫使各进程在某一点必须相互等待。在并行算法的各进程异步执行过程中，为了确保各处理机的正确工作顺序以及对共享可写数据的正确访问（互斥访问），程序员需在算法的适当点设置同步点。下面以MIMD-SD多处理器系统中n个数的求和为例，说明如何用同步语句lock和unlock来确保对共享可写数据的互斥访问。假定系统中有p个处理器P0，P1，…，Pp-1，输入数组A=(a0，a1，…，an-1)存放在共享存储器中，全局变量用于存放结果，局部变量L包含各处理机计算的部分和。lock和unlock语句实现临界区操作，锁语句是个原子性操作。在for循环中各进程异步地执行各语句，并结束在“endfor”。算法8.1共享存储器多处理器上的求和算法n-1i=0输入：A=(a0，a1，……，an-1)，处理器数p输出：S=∑aibeginS=0；forallPiwhere0≤i≤p-1doL=0；forj=itonsteppdoL=L+aj；endfor；lock(S)；S=S+L；unlock(S)；endfor；end；2.通信通信是在空间上对各并发执行的进程施行数据交换，通信可使用通信原语来表达。在共享存储器的多处理机中，可使用globalread(X,Y)和globalwrite(U,V)来交换数据，前者将全局存储器中数据X读入局部变量Y中，后者将局部数据U写入共享存储变量V中；在分布存储器的多计算机中，可使用send(X,i)和receive(Y,j)来交换数据，前者是处理机发送数据X给Pi，后者是处理机从Pj接收数据Y。下面以MIMD-DM多计算机系统中矩阵向量乘法为例说明。假定分布式连接拓扑为环，矩阵A和向量X划分成p块，A=(A1,…,Ap)和X=(x1,…,xp)，其中Ai的大小为n×r，xi的大小为r。假定有p≤n台处理机，r=n/p为一整数。为了计算y=AX，先由处理机i计算zi=Aixi(1≤i≤p),再累加求和z1+…+zp。如果Pi开始在其局存中保存B=Ai和w=xi(1≤i≤p)，则各处理机可局部计算乘积Bwi；然后采用在环中顺时针循环部分和的方法将这些向量累加起来；最终输出向量保存在P1中。对于每个处理器都执行如下算法：算法8.2分布式存储器多计算机上矩阵向量乘算法输入：处理器数p，第i个大小为n×r的子矩阵B=A(1:n,(i-1)r+1:ir)，其中r=n/p；第i个大小为r的子向量w=x((i-1)r+1:ir)。输出：Pi计算y=A1x1+…+Aixi，并向右传送此结果；算法结束时，P1保存乘积AX。beginComputez=Bw；ifi=1thenyi=0elsereceive(y,left)endif；y=y+z；send(y,right)；ifi=1thenreceive(y,left)endif；end；8.2同步技术同步是个丰富的概念，且是个活跃的研究课题，跨越了许多计算机领域。在多门课程中，例如计算机系统结构、数据库、操作系统、并行处理以及编程语言都涉及到同步。在学习同步概念时，以下4个方面必须弄清楚：(1)用户面临的同步问题，如互斥、原子性、生产者和消费者问题、哲学家就餐问题及路障同步等。(2)用户用来解决同步问题的语言结构。这种结构可以是新语言构造、库函数或编译制导等形式。在目前共享存储器编程环境中，流行的结构是锁、信号量（若只有两个状态就是锁）、事件、临界区和路障等。这些构造称为高级构造。(3)在多处理机体系结构中可用的同步原语，例如Decrement/Increment、Test-and-Set、Compare-and-Swap、Fetch-and-Add等，它们常常由系统硬件直接提供，因此称为低级构造。(4)用低级同步构造实现高级同步构造的算法。在目前的许多系统中，锁仍是最基本的构造，以它为基础可构筑其它构造。一般而言，同步操作可分为三类：原子性、控制同步和数据同步。详细的层次结构如图8.2所示。当前的多处理机编程模型都支持路障、互斥、信号量和锁，以及生产者和消费者同步，但它们不能很好地支持原子性和“我找到了”同步。所有在共享存储器的机器（PVP、SMP、DSM等）中的同步通常使用锁原语实现，而在分布存储器的机器（MPP和机群）中的同步使用消息传递原语实现。图8.2各种同步类型8.2.1原子性原子性(atomicity)是指一个进程需要以单原子操作方式加以执行。一个原子操作是指有如下特性的一种操作。(1)不可分：从程序员的观点看，原子操作作为单一、不可分的一步来执行，一旦开始便不可在中间加以中断，即其它进程无法见到其中间状态，仅仅原子操作最后的结果对其它进程是可见的。如果由于某种原因使原子操作中途放弃，那么必须消除已执行部分操作的影响，卷回到原子操作的初始状态。(2)有限：一旦启动原子操作，它将在有限时间内执行完。(3)可顺序化：不可分性质的推论是可顺序化。意思是说当几个原子操作并行执行时，最后的结果就如同这些操作按某种任意的一次序一个接一个地执行所得到的结果一样。如以下代码所示：parfor(i=1；i<=n；i++){atomic{x=x+1；y=y-1；}}此例中，尽管x=x+1；y=y-1；是串行操作的，atomic将以上两条语句强制捆绑在一起，使其同时输出，达到同步。关键字atomic表示n个进程中的每一个必须以原子操作方式执行两条赋值语句。由并行系统强制原子性方式完成隐式同步。8.2.2控制同步执行控制同步(controlsynchronization)操作的进程将处于等待状态，直到程序的执行到达某种控制状态。控制同步有路障、“我找到了”(eureka)和互斥(multualexclusive)等三种。路障同步是为了保证一组进程全都到达某一控制点后再继续执行。“我找到了”同步则与路障同步完全相反，当某个进程到达某一控制点时，立即异步通知其它所有进程，而勿需处于等待状态。互斥是通过各进程互斥地执行临界段的内容，来保证对共享数据读写的正确性，从而实现同步的技术。下面我们主要介绍路障同步和互斥。1.路障同步路障同步是通过设置路障来达到同步的，如以下代码所示：parfor(i=1；i<=n；i++){Pi；barrier；Qi；}代码中有n个进程。执行Pi的第i个进程后跟一个barrier(路障同步)，在其之后是Qi。当执行完Pi并到达barrier语句时，它必须处于等待状态，直到所有其它进程也到达了它们各自的路障时，才开始并行执行Qi。2.互斥在实现互斥操作时，各处理机处理的相同代码段具有原子性且各处理机只能串行执行这一代码段。一个互斥操作是指有如下特性的一种操作。(1)互斥：每个时刻，仅允许一个进程执行临界段。(2)保证前进：如果多个进程试图进入临界区执行它们的临界段程序，那么至少有一个进程最后获得成功。换句话说，程序不会出现死锁或活锁。(3)无饥饿：企图执行临界段的进程最后应该获得成功，它不会由于其它进程的协同作用而处于饥饿状态。如以下代码所示：parfor(i=1；i<=n；i++)/有n个进程/{/每个进程执行一个parfor迭代/whileCONDITION

{independentcomputation，noncriticalsection/独立计算，非临界区/critical/互斥代码进入点/{criticalsection}/退出互斥代码段/independentcomputation，noncriticalsection}}临界段(criticalsection)是应以互斥方式执行的代码段。CONDITION是可以被临界区修改的逻辑表达式，关键字critical指明了临界区(criticalregion)。应注意临界区是互斥的，因为每次只允许一个进程执行临界段的内容。与此相反，只要原子性是强制的，多个进程就可执行它们自己的原子区。但两者的时间复杂度是相同的，均为O(n)，其中n为进程的个数。8.2.3数据同步执行一个数据同步(datasynchronization)操作的进程将处于等待状态，直到程序执行到达某种数据状态。数据同步的例子包括信号量和锁(semaphore&lock)、生产者和消费者(producer&consumer)、池和队列(pool&queue)等。在大多数当今的系统中，都用数据同步来实现原子性。如以下代码所示：parfor(i=1；i<=n；i++){lock(S)；x=x+1；y=y-1；unlock(S)；}其中锁同步依赖于信号量S中的数据状态。控制同步只依赖于程序的控制状态，它不受程序数据状态的影响。数据同步使用时非常灵活，但控制同步通常要比数据同步更容易理解。8.2.4高级同步结构当前，共享存储器的多处理机系统的并行编程环境提供了4类同步原语：事件、路障、锁/信号量和临界区。事件操作用来实现生产者-消费者同步，路障用在路障同步中，锁和临界区主要用来实现互斥方式的原子性。我们这里只介绍信号量和锁。1.信号量和锁信号量S是一个非负整数变量，仅由两个原子操作P(S)和V(S)处理。P(S)操作用来延时一个进程，直到S变为大于0，然后S减1。V(S)操作简单地将S加1。二元信号量S(也就是S或为真或为假)也叫做锁。对锁信号量S的操作P(S)和V(S)常分别写为lock(S)和unlock(S)。锁的一般用途是通过互斥将临界区转变为原子操作，例如：在银行交易中，我们用单个锁S。进程在能够做任何取款、存款、转帐交易之前，必须通过执行lock(S)操作首先获得锁S，在完成交易之后，通过执行unlock(S)释放锁。一个进程已获得锁但还没有释放，就说该进程正持有锁。转帐交易可用下面代码实现：lock(S)；/进入代码/if(balance[X]>100)/临界区/{balance[X]=balance[X]-100；balance[Z]=balance[Z]+100；}unlock(S)；/退出代码/2.锁的副作用锁的优点是它已有大多数多处理器支持它，并且已研究得相当深入。锁是一种非常灵活的机制，几乎能实现任何同步。然而互斥锁技术用于实现原子性操作时具有某些严重的缺点，从而导致如下一些问题：(1)非结构性：锁不是一种结构化的结构，容易用错它，如果lock/unlock语句漏掉或冗余，则编译器不能查出它。(2)重叠说明：锁不是用户所真正想要的，它只是达到原子性操作的一种方法。锁损害了程序的可移植性，且使代码难于理解。(3)状态相关：锁引入了信号量S及使用条件原子操作lock(S)，一个进程能否穿过lock(S)依赖于信号量S的值，一般而言，像这样与状态有关的数据是难于理解的。(4)顺序执行：对于有些事务处理操作，即使可并行访问，但由于使用锁互斥，它们只能一次执行一个，同样这种顺序执行也不是用户想要的。如在上例的代码段中，若X向Z转帐的同时，Y也要求向W转帐。(5)锁开销：顺序执行lock(S)和unlock(S)也存在着附加的开销，而且当n个进程每个都执行lock(S)操作时，它们中至多一个能成功，其余的均必须重复访问S而再试。(6)优先权倒置：当一个高优先权进程所需的锁被低优先权进程抢先持有时，高优先权进程并不能向前执行，因为它被锁阻塞等待。(7)传递阻塞：当一个保持锁的进程因缺页或超时被中断时，其它的进程因等待锁不能前进。(8)死锁：假定两个进程P与Q，欲进行X与Y操作，当进程P已为X保持了一把锁并想为Y申请一把锁，而进程Q已为Y保持了一把锁并想为X申请一把锁时，此时没有任何进程在其得到锁之前释放一把锁，结果谁也得不到要求的锁。使用二相锁协议的代码段如下：lock(S[X])；/对帐户X(的信号量)加锁/if(balance[X]>100){balance[X]=balance[X]-100；lock(S[Y])；/对帐户Y(的信号量)加锁/balance[Y]=balance[Y]+100；unlock(S[Y])；/使用帐户Y结束/}unlock(S[X])；/使用帐户X结束/这段代码限制了并发性，因为当一个进程已完成处理帐户X，并且正在处理帐户Y时，帐户X仍然封锁。因此，尽管帐户X不再需要该进程作任何处理，其它进程也不能使用它。此代码段最严重的问题是死锁的可能性，假设进程P从帐户X中转帐100美元到帐户Y中，另一进程Q从帐户Y中转帐50美元到X中，因为P和Q是并行执行的，将形成争持不下的情形：P持有帐户X的锁，并试图获取帐户Y的锁；Q持有帐户Y的锁，并试图获取帐户X的锁。根据二相锁协议，进程在获得它需求的所有锁之前，不释放任何锁。因此，P和Q都不能得到它们要求的锁。在P等待执行lock(S[Y])和Q等待执行lock(S[X])时，它们就进入了死锁状态。3.临界区保证临界段互斥的结构化构造是临界区，它的语法类似如下：critical_regionresource{S1；S2；…；Sn；/临界段/}其中resource表示一组共享变量，共享相同resource的临界区必须互斥执行，这种需求由系统(编译器和运行支持系统)实现。而且，临界区结构原先是为操作系统应用提出来的。当它用于并行编程时，作了两个修改：第一，resource部分并非真正有用，因此可以抛弃。用在真正多处理机系统中的临界区结构具有下面语法：critical_region等效的锁机制代码{lock(S)；S1；S2；…Sn；S1；S2；…Sn；}unlock(S)；第二，如上所述，多处理机系统中的临界区是一定意义上的锁的结构化方法。系统将自动声明和初始化一个隐含的信号量S，并生成正确的lock/unlock语句。临界区是结构化的和状态独立的，因此更容易使用。使用临界区的交易可串行化且无死锁，其描述量少，对体系结构依赖弱。临界区意味着代码段将互斥执行，不意味着必须使用锁机制。8.2.5低级同步原语许多多处理机的硬件保证了对基本变量进行单个读或写操作的原子性。另外，大多数多处理机硬件提供了一些原子性指令，每条指令实现对基本变量的一个读、修改、写操作。共同使用这些指令可实现更大粒度的原子操作，下面我们讨论4种低级结构，并按复杂性增大的顺序，指出如何使用它们实现锁机制。1.Test-and-Set(测试和设置)Test-and-Set指令用Test-and-Set(S,temp)表示，它是一个原子操作，它读取共享变量S的值存入本地变量temp中，然后设置S为true。Test-and-Set的主要用途是实现锁，例如：while(S)do；Test-and-Set(S,temp)；while(temp)doTest-and-Set(S,temp)；/完成lock(S)操作/ifbalance[X]>100then/临界段/beginbalance[X]:=balance[X]-100；balance[Z]:=balance[Z]+100；end；S:=False；/完成unlock(S)操作/每次执行Test-and-Set(S,temp)都需要写共享变量S，这将导致繁重的存储器存取传输。lock(S)的上述实现办法使用了Test-and-Set操作。第一个while循环在本地高速缓存中重复检查共享变量S的拷贝。进程只有当检测到锁S被其它进程释放(处于开锁)时，才离开第一个while循环。在所有进程并行执行第一条Test-and-Set语句时，根据原子性操作的可顺序化特性，只有一个进程的temp值被置为False，从而获得锁，其它进程的temp值均为True。在执行第二个while循环时，只有获得锁的进程才能跳过此循环，执行临界段的内容，执行完成后，将共享变量S的值置为False，从而释放锁。其它所有进程在循环执行第二条Test-and-Set语句(等待锁)，直到锁被释放时，又有一个新的进程获得锁并执行临界段的内容，如此循环，直到所有进程都执行完临界段的内容。2.Decrement和Increment(减1和增1)实现Decrement和Increment指令的具体方法是每条指令在执行期间“拥有”一个指定的存储单元。当指定的存储单元正在被读访问时，其它任何指令都不能访问它，直到修改过的内容重新写入该单元为止。即Decrement和Increment指令具有读/修改/写的不可中断性质。在具有不可中断的Decrement和Increment指令的计算机系统中，用Decrement和Increment指令来实现同步，要比用Test-and-Set指令来实现同步所需要的指令要少。因为Test-and-Set指令返回的信息只有一位，而Decrement和Increment指令返回一个存储单元的全部内容。因为返回的信息多，所以实现同步所需的指令数少。用Test-and-Set指令实现的信号灯只允许一个进程通过，在信号灯被解锁之前，禁止其它进程访问。这种信号灯只适宜于控制一个长度为1的缓冲区。扩充的信号灯允许M个进程同时通过。如果已经有M个进程正在长度为M的共享缓冲区活动，那么在信号灯被解锁之前，以后的进程被禁止通过。如此每解锁一次允许一个进程通过该信号灯。有一种使用Decrement和Increment指令实现这种扩充信号灯的简单方法，开始时给该信号灯赋一个初值M，然后每个请求进程对信号灯进行减1操作。如果在Decrement(减1)操作之后，发现信号灯是一个非负的数，则该进程可以访问该缓冲区；如果信号灯是一个负数，则该进程被阻止访问，被阻止访问的进程随后立即对信号灯执行Increment(增1)操作，以表示该进程没有对缓冲区操作。如同我们早先讨论的Test-and-Set指令一样，被阻塞的进程可以入队或不断测试信号灯。一台处理机在完成对缓冲区的访问之后，对信号灯执行Increment(增1)操作，以表示有空间可供其它进程使用。这种简单的同步实现方法有时会出现一种称之为活锁的错误。所谓活锁，是指系统进入一种状态，一方面缓冲区中有可用空间，另一方面有用工作无法进入缓冲区。如下例：whileDecrement(semaphore)<0do/有活锁现象的同步/Increment(semaphore)；{临界程序区}Increment(semaphore)；这里的临界程序区与互斥临界区不一样，互斥临界区在任何时刻只允许一个进程执行临界区的内容，而这里的临界程序区允许最多M个进程同时执行临界程序区的内容。下面我们来分析上面程序进入活锁状态的原因。我们假设在信号灯为零时有大量处理机同时对该信号灯申请Decrement(减1)操作，那么信号灯值将变为-∞，它还能变为正数吗？如果每台被阻塞的处理机先执行Increment(增1)操作，然后返回去重新测试信号灯并执行Decrement(减1)操作，这整个过程是不可中断的，然后才把信号灯传送给下一台处理机，那么信号灯值将从-∞变为-∞+1，然后又回到-∞。如果这时有M台处理机同时从缓冲区退出，它们将信号灯值增加到-∞+M，但这仍是一个负数，所以不允许处理访问缓冲区。这时就出现有用的工作因为事件发生的顺序不合理而被阻塞的现象。如果改变事件的顺序，就可以使信号灯非负，进而使有用的工作只要缓冲区有空间就能开始执行。下面的程序中采用了一种能消去前面程序中活锁现象的机制。它是在信号灯执行Decrement(减1)操作之前测试信号灯。Loop:whilesemaphore<0do；/无活锁现象的同步/ifDecrement(semaphore)<0thenbeginIncrement(semaphore)；gotoLoop；end；{程序临界区}Increment(semaphore)；最坏的情况是大量的处理机发现信号灯为非负时，对信号灯进行Decrement(减1)操作而使它变为-∞。这时若有其它处理机执行while语句，将处于循环等待状态。当大量处理机执行完Increment(加1)操作并使信号灯重新变为非负时，至少有一个进程可以在该值再次变为负数之前获准通过。因此有用的工作可以继续执行，不会出现活锁现象。3.Compare-and-Swap(比较和交换)Compare-and-Swap指令用Compare-and-Swap(S,Old,New,Flag)表示，是一个原子操作。它比较共享变量S和本地变量Old中的值，如果两变量值相等，本地变量New的值存入S中，并且本地标志Flag设置为True，表示S已被修改。如果两变量不等，则S的值存入变量Old中，并且Flag设置为False。Compare-and-Swap可能的应用通过下面银行存钱交易代码演示如下：Old:=balance[X]；/读共享变量/repeatNew:=Old+100；/修改/Compare-and-Swap(balance[X],Old,New,Flag)；/写/untilFlag=True；作为对比，通过锁实现的相同存钱交易代码如下：lock(S)；balance[X]:=balance[X]+100；/读、修改、写/unlock(S)；锁实现方法使整个读、修改、写序列是互斥的。但是，Compare-and-Swap实现方法允许多个进程并发读和修改，只是写作为互斥操作完成。因此，使用Compare-and-Swap的优点是临界段的长度可减小到仅为一条指令。Compare-and-Swap也有几个缺点：首先，它是一种低级结构，难于使用；第二，尽管可以使用，但很难用于存取多于一个共享变量的交易处理；第三，在某些特殊情况下，该指令无法感知共享变量的历史变化情况，如下面的ABA问题。关于Compare-and-Swap(S,Old,New,Flag)指令隐含的假设是：当Old=S时，S还没有被修改过。但这个假设并不是始终成立的。例如，假设进程P在帐户balance[X]中读一个A美元值，然后进程Q存100美元到帐户balance[X]中，改变余额为B=A+100。接着，进程R从帐户balance[X]中取走100美元，修改余额后又变为A。这样，当以后进程P执行一个Compare-and-Swap操作时，它将发现帐户balance[X]中的值为A美元，由此得出结论，认为该帐户一直未被修改过，很显然这是错误的。此处的ABA问题并不影响简单存钱交易代码执行的正确性。但是，在其它情况下，特别是在共享变量为一个指针时，它可能导致不正确的结果。Compare-and-Swap指令的最有意义的应用是不需要加锁和解锁操作即可实现入队和出队。因为队列指针是共享变量，所以典型的入队/出队程序在修改队列指针前要加锁，但这种方法限制了操作的并行性。下面我们以队列为例，来介绍使用Compare-and-Swap指令并发地完成数据入队列的过程和出队列的过程。图8.3显示了队列的数据结构并说明了未使用比较与交换指令时并行完成数据入队的情况。图8.3(a)显示的是一个单链表队列，头指针Head指向队列的第一结点，即待出队数据所在的结点，尾指针Tail指向队列的最后一个结点，若有新的数据要入队就插入到尾指针所指向结点的后面。假设链表中结点的类型定义如下：nodepointer=^node；node=recorddata:real；next:nodepointer；end；将一个数据项插入队列只要执行下面三条语句就可实现，即把指针p所指向的结点插入到队列的队尾。p^.next:=nil；Tail^.next:=p；Tail:=p；由于Tail为共享变量，因此在执行上述三条语句的后两条语句时不可中断，否则在多个进程并行执行入队操作时，将会产生错误。下面我们来分析错误的原因。图8.3队列的插入操作当程序正确执行时，执行一个插入操作后的新队列如图8.3(b)所示。如果进程1要把数据x插入队列，进程2要把数据y插入队列，两个进程并行执行，其中Tail为共享的指针变量，p为局部(本地)指针变量，两者类型如前所述。假设进程1先执行第二条语句读取Tail的当前值，接着进程2执行第二条语句也读取Tail的当前值。若进程1和进程2仍按这个顺序执行第三条语句对Tail值进行修改，那么进程1执行的结点插入操作将无效，如图8.3(c)所示。反过来，若进程2在进程1之前先执行第三条语句，那么队列将在刚插入的这两个结点之间断开，如图8.3(d)所示。为避免上述错误，传统的编程方法总是在执行第二条语句前加锁，执行完第三条语句后再解锁，但这样使得对共享指针变量Tail的读、修改、写过程均是互斥的，限制了程序的并行性，用比较与交换指令可较好地解决这个问题。一个基于比较与交换指令实现入队(ENQUEUE)操作的程序如下：p^.next:=nil；/把插入队尾的数据项初始化/Old:=Tail；/读共享指针变量Tail到局部指针变量Old/Loop:Compare-and-Swap(Tail,Old,p,Flag)；ifFlag=FalsethengotoLoop；/比较与交换指令执行失败时返回Loop/Old^.next:=p；在执行上述程序时，所有进程首先将各自插入队尾的数据项初始化，然后读共享指针变量Tail的值存入局部指针变量Old中，再并行执行原子性指令Compare-and-Swap，将当前共享指针变量Tail的值与局部指针变量Old的值进行比较。若相等，即队尾指针未发生变化，则插入指针p所指向的新结点，并将Flag值置为True；若不相等，即在此进程执行入队操作前已有其它进程执行了入队操作，修改了队尾指针，则重新读取共享变量Tail的值赋给局部指针变量Old，并将Flag值置为False，重新执行比较与交换指令，直到结点入队操作成功为止。所有进程并行执行最后一条语句，完成对局部变量Old^.next的赋值操作。前述程序能实现并发的入队操作，但该程序没有考虑空表情况。如果入队(ENQUEUE)操作和出队(DEQUEUE)操作并发执行，此程序也有可能出错，下面我们要分析这种出错的原因。如果这个程序刚好在Compare-and-Swap指令执行之前被中断，接着有两个进程分别执行DEQUEUE操作和ENQUEUE操作。一个DEQUEUE操作可能已把Old所指向的结点从队列中移走，紧跟着一个ENQUEUE操作执行一个比较与交换指令又把移走的数据项存入队列。这时Tail的值仍为原先的值，即与Old的值相同。于是，出现了两个进程同时用不同的指针修改了Tail^.next的情况。出错的原因是Compare-and-Swap指令并不具备能感知Tail变化历史的功能，所以一看到Tail=Old就认为Tail从上次读出以来一直未被修改过，而这一结论有时是不正确的。为了提高程序的可靠性，采用了一种扩充的双比较与交换指令，使它能同时处理两个变量。这两个变量必须相邻存放，以便通过一次读和写操作就能同时完成这两个变量的存取。改进后的程序如下：p^.next:=nil；/把插入队尾的数据项初始化/Old&Old_Count:=Tail&Count；/把双变量Tail和Count值读到Old和Old_Count/Loop:New_Count:=Old_Count+1；DoubleCompare-and-Swap(Tail&Count,Old&Old_Count,p&New_Count,Flag)；ifFlag=FalsethengotoLoop；Old^.next:=p；变量Tail和Count相邻存放。Tail/Count对的当前值读到Old和Old_Count。仅在双比较与交换(DoubleCompare-and-Swap)指令执行之前，把Old_Count的内容加1后传送到New_Count。DoubleCompare-and-Swap指令验证Tail/Count未被修改后，用p/New_Count的内容修改Tail/Count的值。因为DoubleCompare-and-Swap指令执行成功后，既修改Tail值又修改Count值，所以如果发现Tail和Count值被修改过，那么就表示其它队列操作已经发生过或正在执行。这将强行使DoubleCompare-and-Swap指令失败，转到Loop执行，阻止错误的修改操作。只有当Tail和Count都没有修改过时才能进行修改操作。

例8.1分别用Compare-and-Swap指令和DoubleCompare-and-Swap指令来实现DEQUEUE（出队）操作。解：把一个数据项从队列的头部移走只要执行下面三条语句就可实现：p:=Head；Head:=p^.next；p^.next:=nil；用Compare-and-Swap指令实现DEQUEUE（出队）操作的程序如下：Old:=Head；Loop:Compare-and-Swap(Head,Old,Old^.next,Flag)；ifFlag=FalsethengotoLoop；p:=Old；p^.next:=nil；用DoubleCompare-and-Swap指令DEQUEUE（出队）操作的程序如下：Old&Old_Count:=Head&Count；Loop:DoubleCompare-and-Swap(Head&Count,Old&Old_Count,Old^.next&Count,Flag)；ifFlag=FalsethengotoLoop；p:=Old；p^.next:=nil；4.Fetch-and-Add(取和加)上面讨论的各种技术(锁、临界区、测试和设置、比较和交换)都是顺序地实现原子性。当n个事务执行时，每次只能执行一个。即使用无锁方案如Compare-and-Swap，也是这样，因为尽管n个进程能并行执行n个事务，但只有一个事务能够成功提交，其它n-1个进程必须重试。所以，执行n个事务需O(n)时间。一条Fetch-and-Add指令的执行结果，记为Result:=Fetch-and-Add(S,V)，是一个原子操作，它返回共享变量S的值到本地变量Result中。然后，在S中加上局部变量V的值。Fetch-and-Add指令，意味着允许多个事务真正地并行执行。用Fetch-and-Add编写帐户存款交易代码只用1条指令：Fetch&Add(balance[X]，100)；该代码不仅更简单，而且比以前代码速度更快。使用一种称为组合(combining)的技术，n个处理器在O(log2n)时间内同时执行n个Fetch-and-Add指令(访问相同共享变量)是可能的。有关组合技术的内容已在第五章作了较为详细的介绍。用Fetch-and-Add指令实现ENQUEUE(入队)操作的最佳方法是以计数器为基础。这种实现方法的基本思想是使用一个计数器Tail，执行入队操作时，计数器Tail增1。Tail的值是一个偏移量，用来表示下一个项的插入位置。下面是用Fetch-and-Add指令实现入队操作的简单但不完全的程序：ProcedureEnqueue(item，Queue)；beginPlace:=Fetch-and-Add(Tail，1)；Queue[Place]:=item；endofEnqueue；Fetch-and-Add指令使Tail增1，同时返回增1以前的Tail的值。该返回值是偏移量用来表示插入点的位置。如果N台处理机同时执行取和加指令，Tail接收到的是增量的和，而返回给每一台处理机的是不同的位置值。这样，每台处理机在队列中有不同的插入位置。这是用Fetch-and-Add指令实现入队操作的最基本思想。但是，完整的实现因为需要考虑各种不同的条件而变得非常复杂。这些条件包括：(1)队列应该是循环的，这样当Tail值超过Queue向量的长度时，把Tail值置为0；(2)队列中活动项总数不能超过Queue向量的长度；(3)Dequeue操作允许把多个项从队列中并行地移出；(4)不允许对一个空队进行Dequeue操作；(5)Enqueue和Dequeue操作都必须避免出现活锁。8.3程序并行性的分析几个任务能否并行执行，除了算法外，很大程度上还取决于程序的结构形式。程序中各种类型的数据相关和控制相关都是限制程序并行性的重要因素。数据相关和控制相关既可存在于指令之间，也可存在于程序段之间。8.3.1数据相关数据相关(datadependence)是指邻近的指令之间出现了要求对同一数据地址(寄存器、存储单元地址或文件)进行读写操作而发生的关联，它用来说明语句之间的有序关系。常见的四种数据相关如下：(1)先写后读相关：如果从语句S1到语句S2存在执行通路，即S1执行完后，一定可以执行S2，而且如果S1至少有一个输出(赋值变量)可供S2用作输入(用作操作数)，则称语句S2与语句S1存在先写后读相关。(2)先读后写相关：如果在程序次序中语句S2紧接语句S1，而且如果S2的输出与S1的输入重叠，则语句S2与语句S1存在先读后写相关。(3)写-写相关：如果在程序次序中语句S2紧接语句S1，而且两条语句能产生(写)同一输出变量，则它们就是输出相关。(4)I/O相关：读和写都是I/O语句。存在I/O相关不是因为涉及同一变量，而是因为两条I/O语句引用同一文件。

例8.2并行程序中的数据相关性分析假设有如下并行程序段：parfor(i=1；i<=n；i++){A[i]=B[i]/10；A[i-1]=B[i]+C[i]；}解：在上述并行程序段的循环体部分，下标只出现了i和i-1，即下标的变化范围为2，因此，只需将上述并行循环展开2层，即可分析出2条语句在并行执行时可能会发生的数据相关性。假设i=1对应的指令序列在处理机P1上实现，i=2对应的指令序列在处理机P2上执行，如下所示：P1(i=1)P2(i=2)…

A[1]=B[1]/10；A[2]=B[2]/10；…A[0]=B[1]+C[1]；A[1]=B[2]+C[2]；…由上述加下划线的语句可以看出，两条语句都要求写同一输出变量A[1]，为保证程序运行的正确性，即在顺序程序中语句“A[1]=B[2]+C[2]；”应在语句“A[1]=B[1]/10；”之后执行，因此并行程序段中存在写写相关。值得注意的是，并不是循环体中两条语句的输出变量只要是数组A的分量，就一定发生写写相关，例如，将本例中的步长改为2，程序如下：parfor(i=1；i<=n；i=i+2){A[i]=B[i]/10；A[i-1]=B[i]+C[i]；}例8.3并行程序中的数据相关性分析假设有如下并行程序段：parfor(i=2；i<=n；i++)A[i]=A[i-2]/B[i]；解：在上述并行程序段的循环体部分只有一条语句，下标只出现了i和i-2，即下标的变化范围为3，因此，只需将上述并行循环展开3层，即可分析出此条语句在并行执行时可能会出现的数据相关性。假设i=2、3、4对应的指令分别在处理机P2、P3、P4上执行，如下所示：P2(i=2)P3(i=3)P4(i=4)…

A[2]=A[0]/B[2]；A[3]=A[1]/B[3]；A[4]=A[2]/B[4]；…由上述加下划线的语句可以看出，两条语句都要求对同一变量A[2]进行读写操作，为保证程序运行的正确性，即在顺序程序中语句“A[4]=A[2]/B[4]；”应在语句“A[2]=A[0]/B[2]；”之后执行，因此并行程序段中存在先写后读相关。

例8.4并行程序中的数据相关性分析假设有如下并行程序段：parfor(i=1；i<=n；i++)A[i]=A[C[i]]；解：在此例中，由于C[i]的值未知，因此不能直接判断数据相关性。此例与例8.3非常相似，数组A的不同分量既出现在赋值号的左边，又出现在赋值号的右边。根据C[i]与i的关系，可得出如下结论：(1)当C[i]＜i时，此并行程序段存在先写后读相关；(2)当C[i]＞i时，此并行程序段存在先读后写相关。8.3.2控制相关控制相关(controldependence)指的是语句执行次序运行前不能确定的情况。影响程序执行次序的指令通常有无条件转移指令、条件转移指令、子程序调用与返回指令、中断调用与返回指令等。这里主要介绍由条件语句引起的控制相关。条件语句(如Fortran中的IF语句)直到运行时才能确定条件判断的结果。条件转移后所执行的不同分支可以导致、也可以消除指令间的数据相关，在完成一个循环的连续迭代操作之间也可能存在相关性。这里我们举一个无控制相关迭代的例子和一个有控制相关迭代的例子。下面循环的连续迭代是无控制相关的：DO10I=1，NA(I)=C(I)IF(A(I).LT.0)A(I)=010CONTINUE下面循环的连续迭代存在控制相关：DO10I=1，NIF(A(I-1).EQ.0)A(I)=010CONTINUE将循环展开后如下所示：I=1，IF(A(0).EQ.0)A(1)=0I=2，IF(A(1).EQ.0)A(2)=0从上面加有下划线的语句可以看出，语句“A(1).EQ.0”在判断之前可能会被修改，由于条件语句的存在，使得对于I从1到N，所有的条件语句不能并行执行。控制相关常使正在开发的并行性中止。为了开发更多的并行性，必须用编译技术克服控制相关。例8.5一个程序的内部循环如下：A[i,j]=A[i+1,j-1]；假设此条语句位于双重循环内，外部循环控制变量为i，内部的为j。设计一段循环控制程序，使之对变量j的操作集中，而对i的操作分布到相互独立的处理器上，从而可以并行处理。

解：假定满足上述条件的双重循环如下:parfor(i=1；i<n；i++){for(j=1；j<n；j++){A[i,j]=A[i+1,j-1]；}}若直接使之对变量j的操作集中，而对i的操作分布到相互独立的处理器上，来完成并行处理，将会出现先读后写数据相关。将上述循环展开后如下：P1(i=1)P2(i=2)P3(i=3)…j=1A[1,1]=A[2,0]A[2,1]=A[3,0]A[3,1]=A[4,0]…j=2A[1,2]=A[2,1]A[2,2]=A[3,1]

A[3,2]=A[4,1]…j=3A[1,3]=A[2,2]

A[2,3]=A[3,2]A[3,3]=A[4,2]…j=4A[1,4]=A[2,3]…在上述加框语句、加下划线语句、斜体表示的语句对之间均出现了先读后写数据相关。因此，需对并行循环体中的顺序程序部分进行修改，修改后的循环控制程序如下：parfor(i=1；i<n；i++){for(j=1；j<n；j++){B[i,j]=A[i+1,j-1]；}barrier；for(j=1；j<n；j++){A[i,j]=B[i,j]；}}8.4并行编程概述8.4.1并行编程概况对于所希望的应用，很多现存的并行代码似乎是不存在的，即使有，也常不能用于用户的并行机上，因为并行代码原来都是为不同的并行结构(如SMP、MPP等)而写的。并行编程的问题是：(1)并行算法范例至今尚不能被很好地理解和广泛地接受；(2)并行编程是建立在不同的计算模型（PRAM模型、异步PRAM模型、BSP模型、logP模型、C3模型）上的，而它们没有谁能象冯·诺依曼模型那样被普遍的接受和认可；(3)绝大部分被使用的并行编程语言都是Fortran和C的推广，它们都不能充分地表达不同并行结构的特点，既不成熟也不通用；(4)并行编程工具依赖于具体的并行机结构和计算机代的更迭，既不通用也不稳定，在某个平台上开发的并行程序，很难移植到别的或将来的并行机上。尽管并行编程问题很多，但也有不少进展：(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）现在人们希望高性能的并行机应是具有单一系统映象的巨大的工作站，使得很多用户都能利用增强的处理能力和存储容量来运行多个串行作业，这就是所谓的串行程序并行系统SPPS(SerialProgramParallelSystem)。8.4.2并行编程方法现今编程模型主要有隐式并行、数据并行、消息传递和共享变量等四种。当在实际的并行机上根据它们设计并行程序时，绝大部分均是采用扩展Fortran和C语言的方法。目前有三种扩展的方法：(1)库函数(librarysubroutines)法：除了串行语言所包含的库函数外，一组新的支持并行性和交互操作的库函数(如MPI消息传递库和POSIXPthreads多线程库)引入到并行编程中；(2)新语言构造(newlanguageconstructs)法：采用某些新的语言构造来帮助并行编程以支持并行性和交互操作(如Fortran90中的聚集数组操作)；(3)编译制导(compilerdirectives)法：编程语言保持不变，但是加进称之为编译制导(pragma)的格式注释。图8.4中用一段简单代码来说明这些方法。所有3个并行程序均执行相同的如图8.4(a)所示的串行C代码的计算。图8.4(b)使用库函数的方法实现之，其中两个循环由p个进程并行执行，两个库函数my_process_id()和number_of_processes()开拓并行性，barrier()函数确保第一个循环执行后所有进程被同步，这样第二个循环能使用第一个循环更新后的数组A的正确值；图8.4(c)展示了使用新语言构造执行并行操作，Fortran90数组赋值结构语句执行N个元素相乘，然后以一个赋值语句进行赋值，两个数组赋值之间无需显式同步，因为Fortran90语句是松散同步的，即在下一语句开始执行之前，一条赋值语句的所有操作均已完成；图8.4(d)展示了编译制导法实现并行操作，并行pragma指示下一语句应并行执行，SGI的pfor指使系统并行执行下一循环，同步pragma产生一个路障同步。图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三种并行化方法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三种并行化方法#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.2三种并行编程方法的优缺点方法优点缺点例子库函数易于实现，不需要新的编译器没有编译检查、分析和优化MPI、PVM、CrayCraft新语言构造允许编译检查、分析和优化难以实现，需要一个新的编译器Fortran90、CrayCraft编译制导是库函数和新语言构造两者优缺点的折衷，其显著优点是“普通串行程序+格式注释”，可在任何串行平台上编译HPF、CrayCraft库函数是目前使用最广泛的方法。所有并行化和交互功能由附加到顺序C或Fortran中的一组程序实现。因此，原来的串行编译器也能够使用，不需要任何修改，编程者只要在原来的串行程序中加