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

1、第第8 8章章 并行算法并行算法 第第8章章 并行算法并行算法 8.1 并行算法的基础知识并行算法的基础知识 8.2 同步技术同步技术 8.3 程序并行性的分析程序并行性的分析 8.4 并行编程概述并行编程概述 8.5 并行编程模型并行编程模型 习题习题8 第第8 8章章 并行算法并行算法 8.1 并行算法的基础知识并行算法的基础知识 8.1.1 并行算法的定义和分类 1. 并行算法的定义 算法是指解题方法的精确描述，是一组有穷的规则，它们规定了解决某一特定类型问题的一系列运算。 并行算法(parallel algorithm)是指一些可同时执行的诸进程的集合，这些进程相互作用和协调动作从而达

2、到给定问题的求解。第第8 8章章 并行算法并行算法 2. 并行算法的分类 并行机的出现来源于实际应用程序中存在内在并行度这一基本事实，因此，应用程序中是否存在可挖掘并行度是并行计算机应用的关键，而并行算法作为应用程序开发的基础，自然在并行计算机应用中具有举足轻重的地位。 并行算法根据运算基本对象的不同可分为数值并行算法和非数值并行算法。第第8 8章章 并行算法并行算法 数值计算是指基于代数关系运算的一类诸如矩阵运算、多项式求值、求解线性方程组等数字计算问题。主要为数值计算方法而设计的并行算法称为数值并行算法(numerical parallel algorithm)。 非数值计算是指基于比较关

3、系运算的一类诸如排序、选择、搜索、匹配等符号处理问题。主要为符号运算而设计的并行算法称为非数值并行算法(non-numerical parallel algorithm)。如神经网络算法、遗传算法等。第第8 8章章 并行算法并行算法 根据并行进程间相互执行顺序关系的不同可分为同步并行算法、异步并行算法和独立并行算法。 同步并行算法(synchronized parallel algorithm)是指算法的诸进程间由于运算执行顺序而必须相互等待的并行算法。如通常的向量算法、SIMD算法及MIMD并行机上进程间需要相互等待通信结果的算法等。第第8 8章章 并行算法并行算法 异步并行算法(async

4、hronized parallel algorithm)是指算法的诸进程间执行相对独立，不需要相互等待的一种算法。通常对消息传递MIMD并行机进行设计，其主要特征是在计算的整个过程中均不需要等待，而是根据最新消息决定进程的继续或终止。 独立并行算法(independent parallel algorithm)是指算法的诸进程间执行完全独立，计算的整个过程不需要任何通信的并行算法。例如气象预报应用中通常需要同时计算多个模型，以保证预报的实时性。第第8 8章章 并行算法并行算法 根据各处理机承担的计算任务粒度的不同，可分为细粒度并行算法、中粒度并行算法和粗粒度并行算法。 细粒度并行算法(fine

5、 grain parallel algorithm)通常指基于向量和循环级并行的算法。 中粒度并行算法(middle grain parallel algorithm)通常指基于较大的循环级并行，且并行的好处足以弥补并行来的额外开销的算法。 粗粒度并行算法(coarse grain parallel algorithm)通常指基于子任务级并行的算法，例如通常的基于区域分解的并行算法，它们是当前并行算法设计的主流。第第8 8章章 并行算法并行算法 8.1.2 进程中的同构性 如前所述，并行算法是对一些可同时执行的诸进程之间相互关系的描述，因此，我们这里先讨论进程中的同构性，再来介绍并行算法的表达

6、方法。 进程中的同构性是指在执行并行程序时，并行机中各处理机执行的进程相似到何种程度。图8.1描述了程序执行时进程中的同构性。第第8 8章章 并行算法并行算法 多处理机 程序 多数据流 执行级 MPMD 相同指令 相同程序 SIMD SPMD 图8.1 进程中的同构性第第8 8章章 并行算法并行算法 在多程序多数据流(MPMD)程序中的分进程是异构的，因为多个进程可以执行不同的程序代码；在单程序多数据流(SPMD)程序中的分进程是同构的，因为多个进程在不同的数据范畴内执行相同的程序代码，但不需在指令级达到同步；在单指令多数据流(SIMD)程序中的分进程是同构的，并且要求所有分进程必须在同一时间

7、执行相同的指令。也就是说，SIMD程序是SPMD程序的一个特例。MPMD和SPMD程序在执行时，由于各分进程在同一时间执行的是不同的指令，同时产生多个数据流，因此这两者均属于MIMD类型的程序。第第8 8章章 并行算法并行算法 8.1.3 并行算法的表达 描述一个算法，可以使用自然语言进行物理描述，也可用某种编程语言进行形式化描述。语言的选用，应避免二义性，且力图直观、易懂而不苛求严格的语法格式。像描述串行算法所选用的语言一样，类Algol、Pidgin-Algol、类Pascal、类C等语言均可选用。在这些语言中，允许使用的任何数据类型都可引进。 在描述并行算法时，所有描述串行算法的语句及过

8、程调用等均可使用，如数组、集合、记录等等。根据进程中的同构性不同，对并行算法的表达采用了不同的并行语句。第第8 8章章 并行算法并行算法 1. par语句 当算法的若干个进程要并行执行时，可使用par语句进行描述。其格式如下： parbegin S1；S2；Sn； parend par语句主要用来描述MPMD的功能并行性，其中S1，S2，Sn是分进程，它们可含不同代码。当par语句执行时，它的n个分进程S1，S2，Sn就开始同时执行。它们的执行是互相独立的而且以不同的速率进行。当所有n个分进程终止时，par语句也就终止。第第8 8章章 并行算法并行算法 2. parfor语句 当par语句中的

9、所有分进程共享相同的程序代码时，可使用parfor语句进行描述。其格式如下： parfor(i=1；i=n；i+) /类C语言/ process(i)； 或第第8 8章章 并行算法并行算法 parfor i:=1 to n do /类Pascal语言/ begin process(i)； end； parfor语句用来描述SPMD的数据并行性，其中process(i)表示某一个进程。尽管所有的进程都执行相同的程序代码，但各进程所需的参数是不相同的。第第8 8章章 并行算法并行算法 3. forall语句 当parfor语句中的所有分进程被分派到指定的处理机上并行执行时，可使用forall语句进

10、行描述。其格式如下： 第第8 8章章 并行算法并行算法 forall(i=1；i=k；i+) /类C语言/ process(i)； 或 for all Pi where 0ik do /类Pascal语言/ process(i)； end for；第第8 8章章 并行算法并行算法 8.1.4 并行算法中的同步与通信 1. 同步 同步是在时间上强迫使各进程在某一点必须相互等待。在并行算法的各进程异步执行过程中，为了确保各处理机的正确工作顺序以及对共享可写数据的正确访问（互斥访问），程序员需在算法的适当点设置同步点。下面以MIMD-SD多处理器系统中n个数的求和为例，说明如何用同步语句lock和u

11、nlock来确保对共享可写数据的互斥访问。 第第8 8章章 并行算法并行算法 假定系统中有p个处理器P0，P1，Pp-1，输入数组A=(a0，a1，an-1)存放在共享存储器中，全局变量用于存放结果，局部变量L包含各处理机计算的部分和。lock和unlock语句实现临界区操作，锁语句是个原子性操作。在for循环中各进程异步地执行各语句，并结束在“end for”。第第8 8章章 并行算法并行算法 算法算法8.1 共享存储器多处理器上的求和算法n-1i=0 输入：A=(a0，a1，an-1)，处理器数p 输出：S=ai begin S=0； for all Pi where 0ip-1 do L

12、=0；第第8 8章章 并行算法并行算法 for j=i to n step p do L=L+aj； end for； lock(S)； S=S+L； unlock(S)； end for； end；第第8 8章章 并行算法并行算法 2. 通信 通信是在空间上对各并发执行的进程施行数据交换，通信可使用通信原语来表达。在共享存储器的多处理机中，可使用global read(X,Y)和global write(U,V)来交换数据，前者将全局存储器中数据X读入局部变量Y中，后者将局部数据U写入共享存储变量V中；在分布存储器的多计算机中，可使用send(X,i)和receive(Y,j)来交换数据，前

13、者是处理机发送数据X给Pi，后者是处理机从Pj接收数据Y。 第第8 8章章 并行算法并行算法 下面以MIMD-DM多计算机系统中矩阵向量乘法为例说明。假定分布式连接拓扑为环，矩阵A和向量X划分成p块，A=(A1,Ap)和X=(x1,xp)，其中Ai的大小为nr，xi的大小为r。假定有pn台处理机，r=n/p为一整数。为了计算y=AX，先由处理机i计算zi=Aixi(1ip),再累加求和z1+zp。如果Pi开始在其局存中保存B=Ai和w=xi(1ip)，则各处理机可局部计算乘积Bwi；然后采用在环中顺时针循环部分和的方法将这些向量累加起来；最终输出向量保存在P1中。对于每个处理器都执行如下算法：

14、第第8 8章章 并行算法并行算法 算法算法8.2 分布式存储器多计算机上矩阵向量乘算法 输入：处理器数p，第i个大小为nr的子矩阵 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。第第8 8章章 并行算法并行算法 begin Compute z=Bw； if i=1 then yi=0 else receive(y,left) endif； y=y+z； send(y,right)； if i=1 then receive(y,left) e

15、ndif； end；第第8 8章章 并行算法并行算法 8.2 同步技术同步技术 同步是个丰富的概念，且是个活跃的研究课题，跨越了许多计算机领域。在多门课程中，例如计算机系统结构、数据库、操作系统、并行处理以及编程语言都涉及到同步。在学习同步概念时，以下4个方面必须弄清楚：第第8 8章章 并行算法并行算法 (1)用户面临的同步问题，如互斥、原子性、生产者和消费者问题、哲学家就餐问题及路障同步等。 (2)用户用来解决同步问题的语言结构。这种结构可以是新语言构造、库函数或编译制导等形式。在目前共享存储器编程环境中，流行的结构是锁、信号量（若只有两个状态就是锁）、事件、临界区和路障等。这些构造称为高级

16、构造。第第8 8章章 并行算法并行算法 (3)在多处理机体系结构中可用的同步原语，例如Decrement/Increment、Test-and-Set、Compare-and-Swap、Fetch-and-Add等，它们常常由系统硬件直接提供，因此称为低级构造。 (4)用低级同步构造实现高级同步构造的算法。在目前的许多系统中，锁仍是最基本的构造，以它为基础可构筑其它构造。第第8 8章章 并行算法并行算法 一般而言，同步操作可分为三类：原子性、控制同步和数据同步。详细的层次结构如图8.2所示。当前的多处理机编程模型都支持路障、互斥、信号量和锁，以及生产者和消费者同步，但它们不能很好地支持原子性和

17、“我找到了”同步。所有在共享存储器的机器（PVP、SMP、DSM等）中的同步通常使用锁原语实现，而在分布存储器的机器（MPP和机群）中的同步使用消息传递原语实现。第第8 8章章 并行算法并行算法 同步 原子性 控制同步 数据同步 路障 “我找到了” 互斥 信号量和锁 生产者和消费者 池，队列 图8.2 各种同步类型第第8 8章章 并行算法并行算法 8.2.1 原子性 原子性(atomicity)是指一个进程需要以单原子操作方式加以执行。一个原子操作是指有如下特性的一种操作。 (1)不可分：从程序员的观点看，原子操作作为单一、不可分的一步来执行，一旦开始便不可在中间加以中断，即其它进程无法见到其

18、中间状态，仅仅原子操作最后的结果对其它进程是可见的。如果由于某种原因使原子操作中途放弃，那么必须消除已执行部分操作的影响，卷回到原子操作的初始状态。第第8 8章章 并行算法并行算法 (2)有限：一旦启动原子操作，它将在有限时间内执行完。 (3)可顺序化：不可分性质的推论是可顺序化。意思是说当几个原子操作并行执行时，最后的结果就如同这些操作按某种任意的一次序一个接一个地执行所得到的结果一样。如以下代码所示： parfor(i=1；i=n；i+) atomic x=x+1；y=y-1； 第第8 8章章 并行算法并行算法 此例中，尽管x=x+1；y=y-1；是串行操作的，atomic将以上两条语句强

19、制捆绑在一起，使其同时输出，达到同步。 关键字atomic表示n个进程中的每一个必须以原子操作方式执行两条赋值语句。由并行系统强制原子性方式完成隐式同步。第第8 8章章 并行算法并行算法 8.2.2 控制同步 执行控制同步(control synchronization)操作的进程将处于等待状态，直到程序的执行到达某种控制状态。控制同步有路障、“我找到了”(eureka)和互斥(multual exclusive)等三种。路障同步是为了保证一组进程全都到达某一控制点后再继续执行。“我找到了”同步则与路障同步完全相反，当某个进程到达某一控制点时，立即异步通知其它所有进程，而勿需处于等待状态。互斥

20、是通过各进程互斥地执行临界段的内容，来保证对共享数据读写的正确性，从而实现同步的技术。下面我们主要介绍路障同步和互斥。第第8 8章章 并行算法并行算法 1. 路障同步 路障同步是通过设置路障来达到同步的，如以下代码所示： parfor(i=1；i=n；i+) Pi； barrier； Qi； 第第8 8章章 并行算法并行算法 代码中有n个进程。执行Pi的第i个进程后跟一个barrier(路障同步)，在其之后是Qi。当执行完Pi并到达barrier语句时，它必须处于等待状态，直到所有其它进程也到达了它们各自的路障时，才开始并行执行Qi。第第8 8章章 并行算法并行算法 2. 互斥 在实现互斥操作

21、时，各处理机处理的相同代码段具有原子性且各处理机只能串行执行这一代码段。一个互斥操作是指有如下特性的一种操作。 (1)互斥：每个时刻，仅允许一个进程执行临界段。 (2)保证前进：如果多个进程试图进入临界区执行它们的临界段程序，那么至少有一个进程最后获得成功。换句话说，程序不会出现死锁或活锁。 (3)无饥饿：企图执行临界段的进程最后应该获得成功，它不会由于其它进程的协同作用而处于饥饿状态。如以下代码所示：第第8 8章章 并行算法并行算法 parfor(i=1；i=n；i+) /有n个进程/ /每个进程执行一个parfor迭代/ while CONDITION independent comput

22、ation，noncritical section /独立计算，非临界区/ critical /互斥代码进入点/ 第第8 8章章 并行算法并行算法 critical section /退出互斥代码段/ independent computation，noncritical section 第第8 8章章 并行算法并行算法 临界段(critical section)是应以互斥方式执行的代码段。CONDITION是可以被临界区修改的逻辑表达式，关键字critical指明了临界区(critical region)。 应注意临界区是互斥的，因为每次只允许一个进程执行临界段的内容。与此相反，只要原子性是

23、强制的，多个进程就可执行它们自己的原子区。但两者的时间复杂度是相同的，均为O(n)，其中n为进程的个数。第第8 8章章 并行算法并行算法 8.2.3 数据同步 执行一个数据同步(data synchronization)操作的进程将处于等待状态，直到程序执行到达某种数据状态。数据同步的例子包括信号量和锁(semaphore&lock)、生产者和消费者(producer&consumer)、池和队列(pool&queue)等。在大多数当今的系统中，都用数据同步来实现原子性。如以下代码所示：第第8 8章章 并行算法并行算法 parfor(i=1；i100) /临界区/ ba

24、lanceX=balanceX-100； balanceZ=balanceZ+100； unlock(S)； /退出代码/第第8 8章章 并行算法并行算法 2. 锁的副作用 锁的优点是它已有大多数多处理器支持它，并且已研究得相当深入。锁是一种非常灵活的机制，几乎能实现任何同步。然而互斥锁技术用于实现原子性操作时具有某些严重的缺点，从而导致如下一些问题： (1)非结构性：锁不是一种结构化的结构，容易用错它，如果lock/unlock语句漏掉或冗余，则编译器不能查出它。第第8 8章章 并行算法并行算法 (2)重叠说明：锁不是用户所真正想要的，它只是达到原子性操作的一种方法。锁损害了程序的可移植性，

25、且使代码难于理解。 (3)状态相关：锁引入了信号量S及使用条件原子操作lock(S)，一个进程能否穿过lock(S)依赖于信号量S的值，一般而言，像这样与状态有关的数据是难于理解的。第第8 8章章 并行算法并行算法 (4)顺序执行：对于有些事务处理操作，即使可并行访问，但由于使用锁互斥，它们只能一次执行一个，同样这种顺序执行也不是用户想要的。如在上例的代码段中，若X向Z转帐的同时，Y也要求向W转帐。 (5)锁开销：顺序执行lock(S)和unlock(S)也存在着附加的开销，而且当n个进程每个都执行lock(S)操作时，它们中至多一个能成功，其余的均必须重复访问S而再试。第第8 8章章 并行算

26、法并行算法 (6)优先权倒置：当一个高优先权进程所需的锁被低优先权进程抢先持有时，高优先权进程并不能向前执行，因为它被锁阻塞等待。 (7)传递阻塞：当一个保持锁的进程因缺页或超时被中断时，其它的进程因等待锁不能前进。 (8)死锁：假定两个进程P与Q，欲进行X与Y操作，当进程P已为X保持了一把锁并想为Y申请一把锁，而进程Q已为Y保持了一把锁并想为X申请一把锁时，此时没有任何进程在其得到锁之前释放一把锁，结果谁也得不到要求的锁。使用二相锁协议的代码段如下：第第8 8章章 并行算法并行算法 lock(SX)； /对帐户X(的信号量)加锁/ if (balanceX100) balanceX=bala

27、nceX-100； lock(SY)； /对帐户Y(的信号量)加锁/ balanceY=balanceY+100； unlock(SY)； /使用帐户Y结束/ unlock(SX)； /使用帐户X结束/第第8 8章章 并行算法并行算法 这段代码限制了并发性，因为当一个进程已完成处理帐户X，并且正在处理帐户Y时，帐户X仍然封锁。因此，尽管帐户X不再需要该进程作任何处理，其它进程也不能使用它。 此代码段最严重的问题是死锁的可能性，假设进程P从帐户X中转帐100美元到帐户Y中，另一进程Q从帐户Y中转帐50美元到X中，因为P和Q是并行执行的，将形成争持不下的情形：P持有帐户X的锁，并试图获取帐户Y的锁

28、； 第第8 8章章 并行算法并行算法 Q持有帐户Y的锁，并试图获取帐户X的锁。根据二相锁协议，进程在获得它需求的所有锁之前，不释放任何锁。因此，P和Q都不能得到它们要求的锁。在P等待执行lock(SY)和Q等待执行lock(SX)时，它们就进入了死锁状态。第第8 8章章 并行算法并行算法 3. 临界区 保证临界段互斥的结构化构造是临界区，它的语法类似如下： critical_region resource S1；S2；Sn； /临界段/ 第第8 8章章 并行算法并行算法 其中resource表示一组共享变量，共享相同resource的临界区必须互斥执行，这种需求由系统(编译器和运行支持系统)实

29、现。而且，临界区结构原先是为操作系统应用提出来的。当它用于并行编程时，作了两个修改：第一，resource部分并非真正有用，因此可以抛弃。用在真正多处理机系统中的临界区结构具有下面语法： critical_region 等效的锁机制代码 lock(S)； S1；S2；Sn； S1；S2；Sn； unlock(S)；第第8 8章章 并行算法并行算法 第二，如上所述，多处理机系统中的临界区是一定意义上的锁的结构化方法。系统将自动声明和初始化一个隐含的信号量S，并生成正确的lock/unlock语句。 临界区是结构化的和状态独立的，因此更容易使用。使用临界区的交易可串行化且无死锁，其描述量少，对体系

30、结构依赖弱。临界区意味着代码段将互斥执行，不意味着必须使用锁机制。第第8 8章章 并行算法并行算法 8.2.5 低级同步原语 许多多处理机的硬件保证了对基本变量进行单个读或写操作的原子性。另外，大多数多处理机硬件提供了一些原子性指令，每条指令实现对基本变量的一个读、修改、写操作。共同使用这些指令可实现更大粒度的原子操作，下面我们讨论4种低级结构，并按复杂性增大的顺序，指出如何使用它们实现锁机制。第第8 8章章 并行算法并行算法 1. Test-and-Set(测试和设置) Test-and-Set指令用Test-and-Set(S,temp)表示，它是一个原子操作，它读取共享变量S的值存入本地

31、变量temp中，然后设置S为true。Test-and-Set的主要用途是实现锁，例如：第第8 8章章 并行算法并行算法 while(S) do ； Test-and-Set(S,temp)； while(temp) do Test-and-Set(S,temp)； /完成lock(S)操作 / if balanceX100 then /临界段/ begin balanceX:=balanceX-100； balanceZ:=balanceZ+100； end； S:=False； /完成unlock(S)操作/第第8 8章章 并行算法并行算法 每次执行Test-and-Set(S,temp)

32、都需要写共享变量S，这将导致繁重的存储器存取传输。lock(S)的上述实现办法使用了Test-and-Set操作。第一个while循环在本地高速缓存中重复检查共享变量S的拷贝。进程只有当检测到锁S被其它进程释放(处于开锁)时，才离开第一个while循环。第第8 8章章 并行算法并行算法 在所有进程并行执行第一条Test-and-Set语句时，根据原子性操作的可顺序化特性，只有一个进程的temp值被置为False，从而获得锁，其它进程的temp值均为True。在执行第二个while循环时，只有获得锁的进程才能跳过此循环，执行临界段的内容，执行完成后，将共享变量S的值置为False，从而释放锁。其

33、它所有进程在循环执行第二条Test-and-Set语句(等待锁)，直到锁被释放时，又有一个新的进程获得锁并执行临界段的内容，如此循环，直到所有进程都执行完临界段的内容。第第8 8章章 并行算法并行算法 2. Decrement和Increment(减1和增1) 实现Decrement和Increment指令的具体方法是每条指令在执行期间“拥有”一个指定的存储单元。当指定的存储单元正在被读访问时，其它任何指令都不能访问它，直到修改过的内容重新写入该单元为止。即Decrement和Increment指令具有读/修改/写的不可中断性质。第第8 8章章 并行算法并行算法 在具有不可中断的Decreme

34、nt和Increment指令的计算机系统中，用Decrement和Increment指令来实现同步，要比用Test-and-Set指令来实现同步所需要的指令要少。因为Test-and-Set指令返回的信息只有一位，而Decrement和Increment指令返回一个存储单元的全部内容。因为返回的信息多，所以实现同步所需的指令数少。第第8 8章章 并行算法并行算法 用Test-and-Set指令实现的信号灯只允许一个进程通过，在信号灯被解锁之前，禁止其它进程访问。这种信号灯只适宜于控制一个长度为1的缓冲区。扩充的信号灯允许M个进程同时通过。如果已经有M个进程正在长度为M的共享缓冲区活动，那么在信

35、号灯被解锁之前，以后的进程被禁止通过。如此每解锁一次允许一个进程通过该信号灯。第第8 8章章 并行算法并行算法 有一种使用Decrement和Increment指令实现这种扩充信号灯的简单方法，开始时给该信号灯赋一个初值M，然后每个请求进程对信号灯进行减1操作。如果在Decrement(减1)操作之后，发现信号灯是一个非负的数，则该进程可以访问该缓冲区；如果信号灯是一个负数，则该进程被阻止访问，被阻止访问的进程随后立即对信号灯执行Increment(增1)操作，以表示该进程没有对缓冲区操作。如同我们早先讨论的Test-and-Set指令一样，被阻塞的进程可以入队或不断测试信号灯。一台处理机在完

36、成对缓冲区的访问之后，对信号灯执行Increment(增1)操作，以表示有空间可供其它进程使用。第第8 8章章 并行算法并行算法 这种简单的同步实现方法有时会出现一种称之为活锁的错误。所谓活锁，是指系统进入一种状态，一方面缓冲区中有可用空间，另一方面有用工作无法进入缓冲区。如下例： while Decrement(semaphore)0 do /有活锁现象的同步/ Increment(semaphore)； 临界程序区 Increment(semaphore)；第第8 8章章 并行算法并行算法 这里的临界程序区与互斥临界区不一样，互斥临界区在任何时刻只允许一个进程执行临界区的内容，而这里的临界

37、程序区允许最多M个进程同时执行临界程序区的内容。 下面我们来分析上面程序进入活锁状态的原因。我们假设在信号灯为零时有大量处理机同时对该信号灯申请Decrement(减1)操作，那么信号灯值将变为-，它还能变为正数吗？如果每台被阻塞的处理机先执行Increment(增1)操作，然后返回去重新测试信号灯并执行Decrement(减1)操作，这整个过程是不可中断的，然后才把信号灯传送给下一台处理机，那么信号灯值将从-变为-+1，然后又回到-。 第第8 8章章 并行算法并行算法 如果这时有 M台处理机同时从缓冲区退出，它们将信号灯值增加到-+M，但这仍是一个负数，所以不允许处理访问缓冲区。这时就出现有

38、用的工作因为事件发生的顺序不合理而被阻塞的现象。如果改变事件的顺序，就可以使信号灯非负，进而使有用的工作只要缓冲区有空间就能开始执行。 下面的程序中采用了一种能消去前面程序中活锁现象的机制。它是在信号灯执行Decrement(减1)操作之前测试信号灯。第第8 8章章 并行算法并行算法 Loop:while semaphore0 do ； /无活锁现象的同步/ if Decrement(semaphore)0 then begin Increment(semaphore)； go to Loop； end； 程序临界区 Increment(semaphore)；第第8 8章章 并行算法并行算法

39、最坏的情况是大量的处理机发现信号灯为非负时，对信号灯进行Decrement(减1)操作而使它变为-。这时若有其它处理机执行while语句，将处于循环等待状态。当大量处理机执行完Increment(加1)操作并使信号灯重新变为非负时，至少有一个进程可以在该值再次变为负数之前获准通过。因此有用的工作可以继续执行，不会出现活锁现象。第第8 8章章 并行算法并行算法 3. Compare-and-Swap(比较和交换) Compare-and-Swap指令用Compare-and-Swap(S,Old,New,Flag)表示，是一个原子操作。它比较共享变量S和本地变量Old中的值，如果两变量值相等，本

40、地变量New的值存入S中，并且本地标志Flag设置为True，表示S已被修改。如果两变量不等，则S的值存入变量Old中，并且Flag设置为False。Compare-and-Swap可能的应用通过下面银行存钱交易代码演示如下：第第8 8章章 并行算法并行算法 Old:=balanceX； /读共享变量/ repeat New:=Old+100； /修改/ Compare-and-Swap(balanceX,Old,New,Flag)； /写/ until Flag=True；第第8 8章章 并行算法并行算法 作为对比，通过锁实现的相同存钱交易代码如下： lock(S)； balanceX:=b

41、alanceX+100； /读、修改、写/ unlock(S)； 锁实现方法使整个读、修改、写序列是互斥的。但是，Compare-and-Swap实现方法允许多个进程并发读和修改，只是写作为互斥操作完成。因此，使用Compare-and-Swap的优点是临界段的长度可减小到仅为一条指令。第第8 8章章 并行算法并行算法 Compare-and-Swap也有几个缺点：首先，它是一种低级结构，难于使用；第二，尽管可以使用，但很难用于存取多于一个共享变量的交易处理；第三，在某些特殊情况下，该指令无法感知共享变量的历史变化情况，如下面的ABA问题。第第8 8章章 并行算法并行算法 关于Compare-

42、and-Swap(S,Old,New,Flag)指令隐含的假设是：当Old=S时，S还没有被修改过。但这个假设并不是始终成立的。例如，假设进程P在帐户balanceX中读一个A美元值，然后进程Q存100美元到帐户balanceX中，改变余额为B=A+100。接着，进程R从帐户balanceX中取走100美元，修改余额后又变为A。这样，当以后进程P执行一个Compare-and-Swap操作时，它将发现帐户balanceX中的值为A美元，由此得出结论，认为该帐户一直未被修改过，很显然这是错误的。此处的ABA问题并不影响简单存钱交易代码执行的正确性。但是，在其它情况下，特别是在共享变量为一个指针时

43、，它可能导致不正确的结果。第第8 8章章 并行算法并行算法 Compare-and-Swap指令的最有意义的应用是不需要加锁和解锁操作即可实现入队和出队。因为队列指针是共享变量，所以典型的入队/出队程序在修改队列指针前要加锁，但这种方法限制了操作的并行性。下面我们以队列为例，来介绍使用Compare-and-Swap指令并发地完成数据入队列的过程和出队列的过程。第第8 8章章 并行算法并行算法 图8.3显示了队列的数据结构并说明了未使用比较与交换指令时并行完成数据入队的情况。图8.3(a)显示的是一个单链表队列，头指针Head指向队列的第一结点，即待出队数据所在的结点，尾指针Tail指向队列的

44、最后一个结点，若有新的数据要入队就插入到尾指针所指向结点的后面。第第8 8章章 并行算法并行算法 假设链表中结点的类型定义如下： nodepointer=node； node=record data:real； next:nodepointer； end；第第8 8章章 并行算法并行算法 将一个数据项插入队列只要执行下面三条语句就可实现，即把指针p所指向的结点插入到队列的队尾。 p.next:=nil； Tail.next:=p； Tail:=p； 由于Tail为共享变量，因此在执行上述三条语句的后两条语句时不可中断，否则在多个进程并行执行入队操作时，将会产生错误。下面我们来分析错误的原因。第

45、第8 8章章 并行算法并行算法 nil nil Head Tail data1 data2 data3 data4 nil (a)单链表的队列形式 data1 data2 data3 data4 (b)执行一个插入队列操作的过程 Head Tail nil x p data1 data2 data3 data4 (c)不用锁语句并行地执行两个插入队列操作的情况 1 Head Tail nil y p x p data1 data2 data3 data4 (d)不用锁语句并行地执行两个插入队列操作的情况 2 Head Tail nil y p x p 图8.3 队列的插入操作第第8 8章章 并

46、行算法并行算法 当程序正确执行时，执行一个插入操作后的新队列如图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)所示。第第8 8章章 并行算法并行算法 为避免上述

47、错误，传统的编程方法总是在执行第二条语句前加锁，执行完第三条语句后再解锁，但这样使得对共享指针变量Tail的读、修改、写过程均是互斥的，限制了程序的并行性，用比较与交换指令可较好地解决这个问题。一个基于比较与交换指令实现入队(ENQUEUE)操作的程序如下：第第8 8章章 并行算法并行算法 p.next:=nil； /把插入队尾的数据项初始化/ Old:=Tail； /读共享指针变量Tail到局部指针变量Old/Loop:Compare-and-Swap(Tail,Old,p,Flag)； if Flag=False then go to Loop； /比较与交换指令执行失败时返回Loop/

48、Old.next:=p；第第8 8章章 并行算法并行算法 在执行上述程序时，所有进程首先将各自插入队尾的数据项初始化，然后读共享指针变量Tail的值存入局部指针变量Old中，再并行执行原子性指令Compare-and-Swap，将当前共享指针变量Tail的值与局部指针变量Old的值进行比较。若相等，即队尾指针未发生变化，则插入指针p所指向的新结点，并将Flag值置为True；若不相等，即在此进程执行入队操作前已有其它进程执行了入队操作，修改了队尾指针，则重新读取共享变量Tail的值赋给局部指针变量Old，并将Flag值置为False，重新执行比较与交换指令，直到结点入队操作成功为止。所有进程并

49、行执行最后一条语句，完成对局部变量Old.next的赋值操作。第第8 8章章 并行算法并行算法 前述程序能实现并发的入队操作，但该程序没有考虑空表情况。如果入队(ENQUEUE)操作和出队(DEQUEUE)操作并发执行，此程序也有可能出错，下面我们要分 析这种出错的原因。 如果这个程序刚好在Compare-and-Swap指令执行之前被中断，接着有两个进程分别执行DEQUEUE操作和ENQUEUE操作。一个DEQUEUE操作可能已把Old所指向的结点从队列中移走，紧跟着一个ENQUEUE操作执行一个比较与交换指令又把移走的数据项存入队列。 第第8 8章章 并行算法并行算法 这时Tail的值仍为

50、原先的值，即与Old的值相同。于是，出现了两个进程同时用不同的指针修改了Tail.next的情况。出错的原因是Compare-and-Swap指令并不具备能感知Tail变化历史的功能，所以一看到Tail=Old就认为Tail从上次读出以来一直未被修改过，而这一结论有时是不正确的。第第8 8章章 并行算法并行算法 为了提高程序的可靠性，采用了一种扩充的双比较与交换指令，使它能同时处理两个变量。这两个变量必须相邻存放，以便通过一次读和写操作就能同时完成这两个变量的存取。改进后的程序如下：第第8 8章章 并行算法并行算法 p.next:=nil； /把插入队尾的数据项初始化/ Old&Old

51、_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)； if Flag=False then go to Loop； Old.next:=p；第第8 8章章 并行算法并行算法 变量Tail和Count相邻存放。Tail/Count对的当前值读到Old和Old_Count。仅在双比较与交换(Double Compare-and-S

52、wap)指令执行之前，把Old_Count的内容加1后传送到New_Count。Double Compare-and-Swap指令验证Tail/Count未被修改后，用p/New_Count的内容修改Tail/Count的值。第第8 8章章 并行算法并行算法 因为Double Compare-and-Swap指令执行成功后，既修改Tail值又修改Count值，所以如果发现Tail和Count值被修改过，那么就表示其它队列操作已经发生过或正在执行。这将强行使Double Compare-and-Swap指令失败，转到Loop执行，阻止错误的修改操作。只有当Tail和Count都没有修改过时才能进

53、行修改操作。第第8 8章章 并行算法并行算法 例例8.1 分别用Compare-and-Swap指令和Double Compare-and-Swap指令来实现DEQUEUE（出队）操作。 解：把一个数据项从队列的头部移走只要执行下面三条语句就可实现： p:=Head； Head:=p.next； p.next:=nil； 用Compare-and-Swap指令实现DEQUEUE（出队）操作的程序如下： Old:=Head；第第8 8章章 并行算法并行算法 Loop:Compare-and-Swap(Head,Old,Old.next,Flag)； if Flag=False then go t

54、o Loop； p:=Old； p.next:=nil； 用Double Compare-and-Swap指令DEQUEUE（出队）操作的程序如下： Old&Old_Count:=Head&Count；第第8 8章章 并行算法并行算法 L o o p : D o u b l e C o m p a r e - a n d -Swap(Head&Count,Old&Old_Count,Old.next&Count,Flag)； if Flag=False then go to Loop； p:=Old； p.next:=nil；第第8 8章章 并行算法并行

55、算法 4. Fetch-and-Add(取和加) 上面讨论的各种技术(锁、临界区、测试和设置、比较和交换)都是顺序地实现原子性。当n个事务执行时，每次只能执行一个。即使用无锁方案如Compare-and-Swap，也是这样，因为尽管n个进程能并行执行n个事务，但只有一个事务能够成功提交，其它n-1个进程必须重试。所以，执行n个事务需O(n)时间。第第8 8章章 并行算法并行算法 一条Fetch-and-Add指令的执行结果，记为Result:=Fetch-and-Add(S,V)，是一个原子操作，它返回共享变量S的值到本地变量Result中。然后，在S中加上局部变量V的值。Fetch-and-

56、Add指令，意味着允许多个事务真正地并行执行。用Fetch-and-Add编写帐户存款交易代码只用1条指令： Fetch&Add(balanceX，100)；第第8 8章章 并行算法并行算法 该代码不仅更简单，而且比以前代码速度更快。使用一种称为组合(combining)的技术，n个处理器在O(log2n)时间内同时执行n个Fetch-and-Add指令(访问相同共享变量)是可能的。有关组合技术的内容已在第五章作了较为详细的介绍。 用Fetch-and-Add指令实现ENQUEUE(入队)操作的最佳方法是以计数器为基础。这种实现方法的基本思想是使用一个计数器Tail，执行入队操作时，计

57、数器Tail增1。Tail的值是一个偏移量，用来表示下一个项的插入位置。下面是用Fetch-and-Add指令实现入队操作的简单但不完全的程序：第第8 8章章 并行算法并行算法 Procedure Enqueue(item，Queue)； begin Place:=Fetch-and-Add(Tail，1)； QueuePlace:=item； end of Enqueue；第第8 8章章 并行算法并行算法 Fetch-and-Add指令使Tail增1，同时返回增1以前的Tail的值。该返回值是偏移量用来表示插入点的位置。如果N台处理机同时执行取和加指令，Tail接收到的是增量的和，而返回给每

58、一台处理机的是不同的位置值。这样，每台处理机在队列中有不同的插入位置。 这是用Fetch-and-Add指令实现入队操作的最基本思想。但是，完整的实现因为需要考虑各种不同的条件而变得非常复杂。这些条件包括：第第8 8章章 并行算法并行算法 (1)队列应该是循环的，这样当Tail值超过Queue向量的长度时，把Tail值置为0； (2)队列中活动项总数不能超过Queue向量的长度； (3)Dequeue操作允许把多个项从队列中并行地移出； (4)不允许对一个空队进行Dequeue操作； (5)Enqueue和Dequeue操作都必须避免出现活锁。第第8 8章章 并行算法并行算法 8.3 程序并行

59、性的分析程序并行性的分析 几个任务能否并行执行，除了算法外，很大程度上还取决于程序的结构形式。程序中各种类型的数据相关和控制相关都是限制程序并行性的重要因素。数据相关和控制相关既可存在于指令之间，也可存在于程序段之间。第第8 8章章 并行算法并行算法 8.3.1 数据相关 数据相关(data dependence)是指邻近的指令之间出现了要求对同一数据地址(寄存器、存储单元地址或文件)进行读写操作而发生的关联，它用来说明语句之间的有序关系。常见的四种数据相关如下： (1)先写后读相关：如果从语句S1到语句S2存在执行通路，即S1执行完后，一定可以执行S2，而且如果S1至少有一个输出(赋值变量)

60、可供S2用作输入(用作操作数)，则称语句S2与语句S1存在先写后读相关。第第8 8章章 并行算法并行算法 (2)先读后写相关：如果在程序次序中语句S2紧接语句S1，而且如果S2的输出与S1的输入重叠，则语句S2与语句S1存在先读后写相关。 (3)写-写相关：如果在程序次序中语句S2紧接语句S1，而且两条语句能产生(写)同一输出变量，则它们就是输出相关。 (4)I/O相关：读和写都是I/O语句。存在I/O相关不是因为涉及同一变量，而是因为两条I/O语句引用同一文件。 第第8 8章章 并行算法并行算法 例例8.2 并行程序中的数据相关性分析 假设有如下并行程序段： parfor(i=1；i=n；i+) Ai=Bi/10； Ai-1=Bi+Ci； 第第8 8章章 并行算法并行算法 解：在上述并行程序