并行计算同步计算

《并行计算同步计算》由会员分享，可在线阅读，更多相关《并行计算同步计算（62页珍藏版）》请在金锄头文库上搜索。

1、第六章第六章 同步计算同步计算Synchronous ComputationsSynchronous Computations 同步计算分为全同步和部分同步同步计算分为全同步和部分同步 全同步全同步 (full synchronination)(full synchronination)：所有的进程在一些：所有的进程在一些 规则的执行点上的同步。规则的执行点上的同步。 部分同步部分同步(partial synchronization)(partial synchronization)或局部同步或局部同步 (local synchronization) (local synchronizatio

2、n) ：在逻辑上相邻的一组进：在逻辑上相邻的一组进 程参与的同步。程参与的同步。 同步计算是指那些带有全同步或大量部分同步同步计算是指那些带有全同步或大量部分同步 的计算。的计算。主要内容主要内容1 1全同步及相关技术问题全同步及相关技术问题2 2同步计算同步计算3 3同步迭代程序实例同步迭代程序实例一、全同步一、全同步及相关技术问题及相关技术问题 在消息传递并行计算中，常用的全同在消息传递并行计算中，常用的全同 步的实现方法有：步的实现方法有：1.1.障碍、路障障碍、路障(barrier)(barrier)2.2.计数器实现计数器实现3.3.树实现树实现1 1、障碍（路障）同步、障碍（路障）

3、同步(barrier synchronization)(barrier synchronization)：在在 并行系统中，使一组进程取得同步的一种方法。并行系统中，使一组进程取得同步的一种方法。 它在参与障碍同步的每个进程的程序中彼此必须它在参与障碍同步的每个进程的程序中彼此必须 等待的位置设置一个障碍点，当某进程执行到障等待的位置设置一个障碍点，当某进程执行到障 碍点时暂停，等待所有进程都执行到这个障碍点碍点时暂停，等待所有进程都执行到这个障碍点 上，它们才能继续运行。上，它们才能继续运行。 通常需要同步的进程的程序中有多个障碍点，以同通常需要同步的进程的程序中有多个障碍点，以同 步它们彼

4、此的操作。步它们彼此的操作。 障碍同步可应用于：障碍同步可应用于： 共享存储器系统共享存储器系统 分布存储的消息传递系统分布存储的消息传递系统 进程不在同一时刻到达障碍点的情况进程不在同一时刻到达障碍点的情况进程进程时间P0P1P2Pn-1活 动等 待障碍 在消息传递系统中，障碍同步通常是由库例程（函在消息传递系统中，障碍同步通常是由库例程（函 数）提供的。数）提供的。 MPI MPI 的障碍同步例程：的障碍同步例程：barrier(comm)barrier(comm) 阻塞所有的调用者，直到通信体阻塞所有的调用者，直到通信体 (comm)(comm)中所有中所有 的成员都调用了该例程后的成员

5、都调用了该例程后, ,各进程中的各进程中的 barrier barrier 调调 用才可返回。用才可返回。 PVM PVM 库也有类似的例程：库也有类似的例程：pvm_barrier( )pvm_barrier( ) 障碍同步例程的实现取决于并行系统的体系结构。障碍同步例程的实现取决于并行系统的体系结构。: : : barrier( ); : : : : barrier( ); : : : : : : : barrier( ); : :进程P0Pp-1P1各进程处于等待状态， 直到所有的进程都到达 barrier调用点为止。2 2、集中式计数器实现、集中式计数器实现 ：用一个计数器对到达路障的

6、进：用一个计数器对到达路障的进 程数目计数。程数目计数。 计数器的初值为计数器的初值为 0 0； 每个调用路障的进程将计数器增每个调用路障的进程将计数器增 1 1，并检查计数器是否已，并检查计数器是否已 到达路障同步进程总数到达路障同步进程总数 n n；若未到达；若未到达 n n 值，则使进程转入值，则使进程转入“ “ 挂起挂起” ” 状态；否则释放该进程及所有其它等待进程。状态；否则释放该进程及所有其它等待进程。: : : barrier( ); : : : : barrier( ); : : : : : : : barrier( ); : :计数器 计数器路障分为两个阶段：计数器路障分为两

7、个阶段：进入路障阶段进入路障阶段离开路障阶段离开路障阶段 如果系统没有路障例程，通常由主进程维护如果系统没有路障例程，通常由主进程维护 路障计数器：路障计数器：当从进程到达路障时，主进程对来自从进程的消当从进程到达路障时，主进程对来自从进程的消 息计数；息计数；在离开路障阶段中，主进程释放各个从进程。在离开路障阶段中，主进程释放各个从进程。/*count slaves as they reach barrier*/*count slaves as they reach barrier*/for (i = 0; i = 0; i- -) for (i = log(n) -1; i = 0; i-

8、 -) if (myid % 2 if (myid % 2i i = 0) = 0) if (myid % 2 if (myid % 2i+1i+1 = 0) send(P= 0) send(Pmyid+2myid+2i i); );else recv(P else recv(Pmyid-2myid-2i i); );局部同步局部同步 全同步要求所有的进程同步，但实际问题中常有些全同步要求所有的进程同步，但实际问题中常有些 局部同步的情况。局部同步的情况。 对于局部同步的情况，我们只需在要求同步的进程对于局部同步的情况，我们只需在要求同步的进程 之间实现即可。之间实现即可。 例如：在进程例如：

9、在进程 P Pi i、P Pj j 和和 P Pk k 之间实现同步是利用彼此之间实现同步是利用彼此 间的接收间的接收/ /发送空消息完成的：发送空消息完成的： Pi Pj Pksend(Pi);send(Pk);recv(Pi);recv(Pk);recv(Pj);send(Pj);recv(Pj);send(Pj);死锁死锁 正如操作系统中的同步一样，并行系统中同步也会正如操作系统中的同步一样，并行系统中同步也会 出现死锁问题；出现死锁问题； 如果要通过接收如果要通过接收/ /发送消息实现两进程彼此的同步：发送消息实现两进程彼此的同步：Pi Pjsend(Pi); recv(Pi);sen

10、d(Pj); recv(Pj);可以看到：若两进程的send例程是同步或阻塞的，则两进程均会等待对方匹配的接收例程而造成死锁。常用的解决办法：两进程的发送和接收例程 的顺序做调整。Pi Pjsend(Pi); recv(Pi);recv(Pj); send(Pj);对流水线系统而言，我们可以利用下列办法 避免死锁的发生：对编号为奇数的进程先接收消息再发送消息；而 对编号为偶数的进程首先发送消息然后再接收消 息。 另外，对进程间双向数据传输可能造成的死锁问题，另外，对进程间双向数据传输可能造成的死锁问题， MPI MPI 及其它一些并行例程库中，提供了一个复合阻塞及其它一些并行例程库中，提供了一

11、个复合阻塞 例程例程sendrecv( )sendrecv( )；这个例程通过系统内部实现机制来；这个例程通过系统内部实现机制来 避免死锁的发生。避免死锁的发生。Pi Pj Pk send(Pi); send(Pk); recv(Pi); recv(Pk);recv(Pj); send(Pj);recv(Pj); send(Pj);上述情况可改写为：Pi Pj Pk sendrecv(Pi);sendrecv(Pk);sendrecv(Pj);sendrecv(Pj);二、同步计算二、同步计算 全同步计算典型的例子是全同步计算典型的例子是数据并行计算数据并行计算 数据并行数据并行 (SIMD)

12、 (SIMD) 计算计算-所有的进程同时对不同所有的进程同时对不同 的数据执行相同的操作。的数据执行相同的操作。 数据并行计算的优势：数据并行计算的优势： 容易编程；容易编程； 可以容易地扩展问题的规模；可以容易地扩展问题的规模； 可以数据并行方式解决许多数值问题和一些非可以数据并行方式解决许多数值问题和一些非 数值问题。数值问题。 同步计算的一个典型应用例子是同步计算的一个典型应用例子是同步迭代同步迭代数据并行计算数据并行计算 例例1 1：两个具有：两个具有n n个元素的数组进行相加：个元素的数组进行相加：A = B + C ;A = B + C ;相应的串行代码可写为：相应的串行代码可写为

13、：for ( i = 0; i = 2i = n-1; i = 2j j; i - -; i - -) )x i = x i + x i 2 x i = x i + x i 2 j j; ;4 43 38 82 29 91 10 05 56 63 34 47 711111010111110101 15 511119 94 47 7151517172222202012121515121214144 47 7151517172626272727273232343434344 47 715151717262627272727323238384141A0 A1 A2 A3 A4 A5 A6 A7 A8

14、 A9414138383232272727272626171715157 74 4 求前缀和的并行代码：求前缀和的并行代码：for ( j = 0; j = 2 if (i = 2 j j) x i = x i + x i 2) x i = x i + x i 2 j j ; ; 前缀求和的数据并行前缀求和的数据并行(SIMD)(SIMD)算法的时间复杂性为算法的时间复杂性为 O(log n)O(log n)。 由于每次循环中进行计算的处理机的个数不同，实由于每次循环中进行计算的处理机的个数不同，实 际上有些处理机处于空闲，从而使该并行算法的并际上有些处理机处于空闲，从而使该并行算法的并 行效

15、率降低。行效率降低。 该并行算法所用处理机的个数为该并行算法所用处理机的个数为 n-1n-1， 加速比加速比 = =最佳串行算法的执行时间 并行算法的执行时间l该并行算法的成本为：并行算法的执行时间处理机个数 = O(n log n)l并行效率为：加速比/处理机个数 = O(1/ log n)n -1 Log(n)= O同步迭代同步迭代 同步迭代计算是指所有的进程都完成当前迭代之后，同步迭代计算是指所有的进程都完成当前迭代之后， 才能够进行下一次迭代计算。这些进程在每一次迭代才能够进行下一次迭代计算。这些进程在每一次迭代 时同时启动。时同时启动。 for (j = 0; j | a| | ai, ji, j | ( i = 1, 2, , n)| ( i = 1, 2, , n) j=1,nj=1,nji ji 即即A A的每一行对角元素的绝对值都严格大于同行其的每一行对角元素的绝对值都严格大于同行其他元素绝对值之和，则称他元素绝对值之和，则称A A为严格对角占优矩阵。为严格对角占优矩阵。 定理定理1 1：如果：如果A A为严格对角占优矩阵，则用为严格对角占优