第6章并行计算机的同步与通信.ppt

《第6章并行计算机的同步与通信.ppt》由会员分享，可在线阅读，更多相关《第6章并行计算机的同步与通信.ppt（120页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第第6章章 并行计算机的同步与通并行计算机的同步与通信信计算机系统结构胡越明计算机系Agendan6.1并行计算机系统的通信n6.2Cache与存储器数据一致性n6.3并行计算机的同步n6.4并行计算机程序设计6.1 并行计算机系统的通信并行计算机系统的通信n并行计算机对程序的要求q代码的可重入q并行线程之间的竞态现象n线程之间对共享变量的不同的读-写和写-写访问顺序导致不同的程序执行结果n源自线程间的数据相关性n并行计算机的通信方式q共享存储器q互连网络的消息传递共享存储器通信n共享变量共享变量q最简单的通信方式q没有同步功能n信号信号（signal）q一个二进制变量q可以表示条件、状态、锁

2、和其它同步信息q不能传递数据内容n信箱信箱q固定格式的通信结构q通常包含一个标志位n在发送方和接收方之间起到同步的作用q寻址和管理比较简单，不够灵活n消息消息q具有灵活格式的通信单位共享存储器通信n线程同步q给线程执行顺序施加约束的机制q控制线程执行的相对顺序q建立在互斥机制的基础上n互斥机制q使得一次只有一个线程对共享变量进行访问q以保证每个线程对于共享变量访问的完整性n常见的互斥机制q锁q信号量q临界区共享存储器通信n锁q一种互斥变量q一次只能被一个线程获得n信号量q通过PV操作在线程间传递同步信息n原子操作qP操作将一个变量减1n减后的变量小于0时线程被阻塞qV操作将一个变量加1n加后的

3、变量大于或等于0时释放一个线程共享存储器通信n临界区q短小的、不能被中断的程序段q进入的线程数量是有限制的q通常只允许一个线程进入临界区q可以采用锁机制来实现锁n两个基本的原子操作qAcquiren原子地等待锁的状态变成打开的状态n将打开的锁状态变成关闭的状态q这时该线程获得了锁qReleasen原子地将锁的状态从关闭状态变成打开的状态q这时线程释放了锁锁的类型n互斥量q用PV操作上锁和解锁q有阻塞q可以加上时间属性n递归锁q可以递归地获得的锁q用于递归程序n读写锁q多读单写锁n限制写操作只能由一个线程执行q用于对共享变量的读写操作n自旋锁q非阻塞的锁q用于多处理机系统和多核系统阻塞型锁机制的

4、问题n优先级的颠倒优先级的颠倒priorityinversionq当一个低优先级的线程占用了一个锁之后，需要同一个锁的高优先级线程就只能等待。n护航护航Convoyingq当一个线程拥有一个锁而被切换出去时其他的线程如果需要同一个锁的话都不能运行下去q其他线程都围着拥有锁的线程团团转n死锁死锁Deadlockq锁的拥有和依赖关系形成一个环死锁及其解决n死锁的原因q对资源（锁）的访问是独占的q线程在已经持有一个资源时继续请求其他资源q所有线程都不放弃已经持有的资源q线程对资源的请求形成一个环n解决方法q复制需要独占访问的资源q按照一定的顺序获取资源n有序嵌套q无法获取其他资源时放弃已持有的资源q

5、调用构件时避免使用锁信号n硬件信号q一种黏滞性的逻辑电平n一旦被设置就一直保持不变n直到被清除q如访存完成、cache失效、时钟信号q可以表示为一个寄存器变量n对于信号变量的读操作清除这个信号n软件信号q表示为共享变量q如进程中止信号互连网络的消息传递通信方式 n消息q结点间通信的基本逻辑单位q消息头n目标结点号、源结点号、消息类型和消息长度等q消息体n通信数据互连网络的消息传递通信方式n数据包数据包q数据传输的物理单位n寻径信息n序号n数据内容n校验位n协议号n时间戳存储转发store-and-forward电路交换circuitswitching虚拟切换virtualcut-through

6、虫孔寻径wormhole互连网络的消息传递通信方式存储转发store-and-forwardn问题：延迟大，缓存多互连网络的消息传递通信方式电路交换circuitswitching问题：冲突多，利用率低互连网络的消息传递通信方式虚拟切换virtualcut-through问题：缓存多flits互连网络的消息传递通信方式虫孔寻径wormhole问题：死锁和活锁互连网络的消息传递通信方式n虫孔寻径与存储转发的比较互连网络的消息传递通信方式衡量指标n通信带宽通信带宽q单位时间能够传输的数据量q取决于处理器的通信处理吞吐率、存储器的吞吐率和互连网络的传输带宽n通信延迟通信延迟q发送的时间开销q信号传输

7、时间q传输持续时间q接收方的时间开销n通信延迟隐藏能力通信延迟隐藏能力q通信时间与计算时间或者其他通信时间的重叠程度例例6-2 n1个计算任务在单个核的计算机上运行的启动时间为1秒，运算时间为10秒，数据结果汇总的时间为1秒。如果将该计算任务放在多核处理器的计算机上运行，将运算部分分解成多个线程并行执行。n（1）假如任务的启动和数据汇总操作不能并行执行，运算部分可以进行任意的任务分解，任务之间的通信量可以忽略，也不考虑任务分解后存储系统对性能的影响。问在处理器核的数量分别为2、4、8、16时的任务执行时间和加速比。n（2）上述情况下，假如每两个处理器核之间的通信时间为0.1秒，每对处理器核的通

8、信串行进行，问在核的数量分别为2、4、8、16时的任务执行时间和加速比。解：（1）任务在单个核的计算机上运行时间为12秒；n在双核计算机上的运行时间为1+10/2+1=7秒，加速比为12/7=1.71；n在4核计算机上的运行时间为1+10/4+1=4.5秒，加速比为12/4.5=2.67；n在8核计算机上的运行时间为1+10/8+1=3.25秒，加速比为12/3.25=3.69；n在16核计算机上的运行时间为1+10/16+1=2.63秒，加速比为12/2.63=4.56。解：（2）n任务在单个核的计算机上没有通信时间，运行时间为12秒；n在双核计算机上的通信时间为10.1，运行时间为1+10

9、/2+1+0.1=7.1秒，加速比为12/7.1=1.69；n在4核计算机上的通信时间为60.1=0.6，运行时间为1+10/4+1+0.6=5.1秒，加速比为12/5.1=2.35；n在8核计算机上的通信时间为280.1=2.8，运行时间为1+10/8+1+2.8=6.05秒，加速比为12/6.05=1.98；n在16核计算机上的通信时间为1200.1=12，运行时间为1+10/16+1+12=14.63秒，加速比为12/14.63=0.82，即比单核计算机的计算时间更长。解加速比单核2核4核8核16核无通信开销11.712.673.694.56有通信开销11.692.351.980.82习

10、题n66.2 Cache与存储器数据一致性与存储器数据一致性 n共享存储器多处理机系统的问题q访存冲突与数据一致性q数据多个副本之间的相同性数据一致性的实现n软件方法q编译分析q避免cache共享数据n总线监测q各cache设置监测部件nMESI协议n目录表法q全映射q有限目录q链式目录nSCI总线监测n所有cache不断监测总线上的每一个地址q总线使得写操作变成串行的qCache失效时需要确定数据块的位置nwriteinvalidateprotocolqinvalidatesothercopiesonawrite.nwriteupdateorwritebroadcastprotocolqup

11、dateallthecachedcopiesofadataitemwhenitiswrittencpu1cpu2cache1cache2Mainmemory总线监测n写无效方式q多次写操作时只需一次invalidateq对于整个cache数据块进行n写更新方式q对于数据块中的个别字进行q读操作的命中率高q所有写操作通过总线写入所以相关的其他cache中n写操作的开销较大总线监测n每个处理器的cache中设置一个监测部件q监测总线上的写操作q根据监测的情况改变本地cache块的状态n无效、修改、独占、共享n监测条件q主存中有一个单元被其他处理器所修改q而这个单元在本地cache中也有一个副本n对

12、于写更新方法q拥有数据最新版本的cache需向其他cache提供数据块内容q阻止其他处理器从共享存储器的读操作MESI协议例例6-3 n设单总线连接的两个CPU中采用MESI协议进行一致性操作，初始时某cache块都在无效状态，然后两个CPU对该存储块分别进行如下操作：nCPUA读，CPUB读，CPUA写，CPUB读，CPUB写n试写出每次访问后两个块的状态变化情况。事件状态A状态B说明初始无效无效（I）数据未装入CPU A读独占无效（I）读操作cache失效，装入CPU B读共享共享（S）读操作cache失效，装入后共享CPU A写修改无效（I）写操作命中CPU B读共享共享（S）读操作失效

13、，装入CPU B写无效修改（M）写操作命中例例6-4 n在一个共享L2cache的双核处理器芯片中，两个L1cache通过片内总线与L2cache连接，并采用MESI协议保持一致性。假设L1cache各有4个块，采用全相联地址映像和LRU替换策略，每个块的初始状态都是无效的。在以下读访问块地址序列下，试画出两个L1cache中块的分配情况，并标出每个块的状态。nA核：1，0，6，7，8，0，1nB核：0，2，7，8，9，2，0解目录表法n全映射q每个快表目录项包含N个指示位段nN为系统中处理器的个数q指示位段构成一个位向量n0表示相应的处理器cache没有该块n1表示有该块n有限目录q每个快表

14、目录项包含固定数量的指示位段q指示位段的位数与处理器数量无关n链式目录例例6-5 n设4个CPU的并行计算机中采用全映射的目录表法进行一致性操作，初始时某cache块都在无效状态，然后4个CPU对该存储块分别进行如下操作：nCPU0读，CPU1读，CPU2读，CPU1替换，CPU0写n试写出每次访问后该块的有效指示位段的变化情况，假设一致性操作采用写无效策略。事件指示状态位段初始0000CPU 0读0001CPU 1读0011CPU 2读0111CPU 1替换0101CPU 0写0001例例6-6 n在一个由2个CPU构成的并行计算机中采用全映射的目录表法进行一致性操作。假设各CPU的cach

15、e都只有4个块，采用全相联地址映像和LRU替换策略，每个块的初始状态都是无效的。在以下读访问块地址序列下，试画出两个L1cache中块的分配情况，并标出每个块的指示状态位段。nCPUA：1，0，6，7，8，0，1nCPUB：0，2，7，8，9，2，0解目录表法n链式目录q将目录分布到各个cacheq每个cache的块表中只需存放一个cache指针q单链或双链qSCI数据一致性对cache性能的影响n影响cache性能的因素q单个处理器cache失效的数据传输q数据通信引起的传输n导致invalidations和后继cache失效n一致性失效处理机数量Cache容量块大小数据一致性对cache性

16、能的影响一致性失效n真共享失效真共享失效true sharing misses q由cache一致性操作的通信引起q对共享数据的第一个写操作引起invalidationn伪共享失效伪共享失效false sharing misses q由每个cache块只有一个有效位引起q一个块中其他数据的写操作引起cache块读操作的失效qCache块是共享的，但是数据字并没有共享数据一致性对cache性能的影响n一致性失效的例子q假定数据字x1和x2在同一个数据块中n数据块在P1和P2之间共享q假定以下事件序列存储器数据的一致性时间一致性（consistency）q一个写操作写入共享存储器中的数值什么时候能

17、够被读到n串行一致性n弱化一致性n处理机一致性n松散一致性存储器数据的一致性串行一致性串行一致性sequentialconsistencyn处理机P对于存储单元X的写操作之后进行的读操作，其间如果没有其它处理机对X进行写访问，则总是返回由P写入的数值。n在一个处理机P1对于单元X进行写操作之后，另一处理机P2对于单元X的读操作只要两者足够分离并且没有其它对于X的写操作发生，就能够返回P1写入的数值。n对于同一单元的写操作是顺序进行的，即两个处理机对于相同单元进行的写操作的顺序从任何处理机看都相同。如果数值1和2依次写入一个位置，处理机不可能先读得2，再读得1。存储器数据的一致性n弱化一致性弱化

18、一致性weakconsistencyq程序通过同步操作强调一致性，使得在这些同步点上数据保持一致，而不要求数据随时都是一致的。n处理机一致性处理机一致性processorconsistencyq每个处理机发出的写操作被其它处理机看到的都保持原顺序，但两个不同处理机的写操作顺序可被其他处理机以不同的顺序看到。n松散一致性松散一致性releaseconsistencyq采用acquire-release同步操作使得数据保持一致，从而减少对硬件一致性处理的要求。SCInscalablecoherenceinterfaceqIEEE1596-1992n支持链式目录表法q双向链表n采用双向链路n采用虚拟

19、切换传输方式n支持大规模并行系统q不要求消息按顺序提交q使用64位固定长度地址的分布式存储器的寻址方案n高16位用于寻找结点n低48位地址指定结点内的存储器地址n采用16位差分ECL信号链路q信号时钟250MHzq链路的数据传输带宽为1GB/s习题n11n12n13n146.3 并行计算机的同步并行计算机的同步 n同步机制q并行系统中保持各并行程序正确运行的控制机制q建立在通信机制的基础上q需要采用的硬件提供的机制来实现n硬件原语硬件原语n原子交换atomicexchangeq实现锁n测试并设置test-and-setq实现锁n读取并加1fetch-and-incrementq实现屏障n读取并

20、更新test-and-updateq实现PV操作原子交换原子交换n将一个寄存器的数值与一个存储器中的数值进行交换n难以在并行机中实现n要求存储器读写操作在一条不可中断的指令中完成n硬件不能在读写操作之间响应中断AB原子交换原子交换n解决方案q用两条指令实现n链接装载loadlinkedn条件存储storeconditionalq返回一个数值q表示其存储操作是否成功n两条指令按顺序执行q如果链接装载指令指定的存储单元在对应的条件存储指令执行之间被改变，则存储指令执行时失败。q如果处理机在这两条指令之间进行了上下文交换，则该条件存储指令也将失败。原子交换原子交换原子交换的实现exchR4,0(R1

21、)try:mov R3,R4;move exchange value from R4 to R3ll R2,0(R1);load linkedsc R3,0(R1);store conditionalbeqz R3,try;branch store failesmov R4,R2;put load value in R4宏指令macroinstructionR3BR4R2读取并加1try:ll R2,0(R1);load linkedaddi R2,R2,#1;incrementsc R2,0(R1);store conditionalbeqz R2,try;branch store fail

22、sR2BR2+1派生原语转锁spinlock处理机用循环方法试图得到的锁n没有没有cache一致性机制时一致性机制时li R2,#1;load immediatelockit:exch R2,0(R1);atomic exchangebnez R2,lockit;already locked?n有有cache一致性一致性机制时机制时lockit:lw R2,0(R1);load of lockbnez R2,lockit;not available-spinli R2,#1;load locked valueexch R2,0(R1);swapbnez R2,lockit;branch if

23、lock wasnt 0派生原语采用链接装载/条件存储实现转锁lockit:ll R2,0(R1);load linkedbnez R2,lockit;not available-spinli R2,#1;locked valuesc R2,0(R1);storebeqz R2,lockit;branch if store failes1BR2派生原语n屏障同步barrierq强制所有的线程等待n直到所有的线程都到达屏障时释放所有的线程n用一个计数器对到达的线程计数(Gather阶段)n用一个信号释放所有的线程(release 阶段)q用两个自旋锁实现n一个用于保护计数器n一个用于锁住线程re

24、lease派生原语屏障同步的实现lock(counterlock);/*ensure update atomic */if(count=0)release=0;/*first arrival reset release*/count=count+1;/*count arrivals */unlock(counterlock);/*release lock*/if(count=total)/*all arrived */count=0;/*reset counter*/release=1;/*release processes*/else/*more to come*/spin(release=

25、1);/*wait for arrivals*/派生原语n问题q屏障可能循环使用q从屏障离开的线程可能再次进入屏障q一个线程可能在另一个线程离开屏障之前又进入屏障n代码的bugrelease派生原语n解决方案q对离开的线程计数n不允许线程在其他线程都离开上一个屏障之前又进入屏障q从而又初始化屏障q传感反相屏障sense-reversingn使用线程局部变量q初始化为1q交替地等待1和0release派生原语n屏障同步的实现q传感反相屏障local_sense=!local_sense;/*togglelocal_sense*/lock(counterlock);/*ensureupdateat

26、omic*/count=count+1;/*countarrivals*/if(count=total)/*allarrived*/count=0;/*resetcounter*/release=local_sense;/*releaseprocesses*/unlock(counterlock);/*unlock*/spin(release=local_sense);/*waitforsignal*/第一个到达屏障的线程并不改变release的值同步操作的性能问题nContentionforthelockq(2i+1)=n2+2nn锁变量访问的串行化q大大增加完成同步操作的时间n解决方案q增

27、量资源n或分解资源n如散列表的分割q指数退避exponentialbackoffn访问等待时间以指数增加n防止活锁q队列锁n锁变量释放时通知下一个线程q组合树n树中每个结点组合k个线程的同步n将对一个变量的竞争按树形结构分散同步操作的性能问题n指数等待同步操作的性能问题n组合树struct node/*anodeinthecombiningtree*/int counterlock;/*lockforthisnode*/int count;/*counterforthisnode*/int parent;/*parentinthetree=0.P-1exceptforroot*/;struct

28、 nodetree0.P1;/*thetreeofnodes*/int local_sense;/*privateperprocessor*/int release;/*globalreleaseflag*/同步操作的性能问题n组合树/*functiontoimplementbarrier*/barrier(intmynode,intlocal_sense)lock(treemynode.counterlock);/*protectcount*/treemynode.count=treemynode.count+1;/*incrementcount*/if(treemynode.count=k

29、)/*allarrivedatmynode*/if(treemynode.parent=0)barrier(treemynode.parent);/*recursivecall*/elserelease=local_sense;treemynode.count=0;/*resetforthenexttime*/unlock(treemynode.counterlock);/*unlock*/spin(release=local_sense);/*wait*/;/*codeexecutedbyaprocessortojoinbarrier*/local_sense=!local_sense;ba

30、rrier(mynode);事务存储器 n同步机制的硬件解决方案q非互锁的机制q使得系统能够并行地执行原子操作n事务q锁的作用范围q每个事务由一个线程推测性地执行而不请求锁q没有遇到冲突时提交n否则事务将放弃（abort）n进行卷回（rollback）并重新开始q事务没有成功提交之前不会对其它线程产生作用事务存储器n事务q由线程中的一组指令构成q串行性n从其他线程看来不会有不同的执行顺序q原子性n整体提交或者整体放弃n提交之前对其它线程看不到n同步与多线程 多线程的程序的问题n数据竞争q由各线程对共享数据读-写访问和写-写访问顺序的不确定性引起n同步q同步机制会带来的开销n线程停顿q一个锁未解

31、开使等待这个锁的线程停顿n死锁q线程的无限期的停顿现象n伪共享q线程之间的非真正的数据共享而引起的相关性多线程的程序的问题n数据竞争q数据相关性险象q以下两个if语句的表达式可能都为真吗？多线程的程序的问题线程1线程2原始代码t=x;x=t+1;u=x;x=u+2;并行情况1t=x;/xis0 x=t+1;/xis1u=x;x=u+2;/xis2并行情况2t=x;x=t+1;/xis1u=x/xis0 x=u+2/xis2并行情况3t=x;/xis0 x=t+1;/xis1u=x;x=u+2;/xis3数据竞争之二多线程的程序的问题n数据竞争之三nif(list-next=NULL)ninse

32、rt(list-next,node1)nif(list-next=NULL)ninsert(list-next,node2)node2node1数据竞争的解决n变量局部化q将变量改为线程局部的q如将全局和分解为部分和n用临界区控制共享变量的访问q通过锁、信号量等实现q每个共享数据用一把锁n互斥机制同步与多线程n并行线程与临界区criticalsectionq访问共享数据的程序段q在某段时间内仅允许一定数目的线程访问的一段代码q大多数情况下一次只有一个线程能够进入同一个临界区q可采用互斥机制实现同步与多线程n并行线程与屏障习题n16n18n20n21n226.5 并行计算机程序的软件支持并行计算

33、机程序的软件支持 并行程序的概念n任务划分任务划分q将一个任务划分成多个并行子任务q使得处理器负载平衡n数据划分数据划分q将数据对象划分成多个并行子集q提高访存的效率以及cache的命中率n数据流划分数据流划分q根据数据处理的过程划分q一个子任务的输出是另一个子任务的输入u划分的目标l负载平衡l降低调度开销、通信开销和同步开销并行程序的概念n任务taskq应用级的计算单位n单任务线程q为每个任务动态创建和终止q创建和终止开销问题q大量线程时的开销n线程池q预先创建的固定数量的线程n与处理器数量匹配q可完成多个任务n应用程序中动态任务分配和调度n线程中任意时刻只能运行一个纤程并行程序的概念n线程

34、化的优点q创建速度较进程快q资源利用率高q便于数据共享n线程化的缺点q增加程序设计的复杂性q程序调试较难n数据竞争、同步、死锁多线程的执行n硬件多线程硬件多线程q每个线程运行在不同逻辑处理器上q优先级相同q硬件的通信开销q真正的并行执行n软件多线程软件多线程q运行在同一个逻辑处理器上qOS动态改变优先级q共享本地存储器n通信开销小n互斥容易解决共享存储器系统程序设计例子共享存储器系统程序设计例子8个处理机，单总线连接sumPn=0;for(i=8000*Pn;i8000*(Pn+1);i=i+1)sumPn=sumPn+Ai;/*sum the assigned areas */half=8;

35、/*8 processors in single-bus MIMD */do synch();/*wait for completion of partial sums */half=half/2;/*dividing line on two sums */if(Pn1);/*exit with final sum in sum0 */其中synch()函数是一个屏障同步函数。分布消息传递型系统程序例子分布消息传递型系统程序例子n假设64个处理机，各处理机具有不同的地址空间。nsum=0;nfor(i=0;i=half&Pnlimit)send(Pn%half,sum);n if(Pn1);/

36、*exit with final sum */任务划分n对数据进行划分q使得不同的子任务对不同的数据子集进行处理n对计算过程中的步骤进行q使得每个线程具有不同的程序代码n任务分解的一般方法q根据数据运算流程图进行例例6-8 n对于数组运算E=A*(B+C*D);n其中，A、B、C和D都是具有n个元素的数组，试画出其数据流程图，指出两种子任务划分方式。解n横向划分n纵向划分实现并行程序设计的方法 n库函数库函数q在串行程序的标准库的基础上增加支持并行操作的函数q如MPI的消息传递库和POSIX的Pthread多线程库q容易实现（不需要改变编译程序）q程序中的并行性没有经过编译程序的检查、分析、优

37、化n新的语言构造新的语言构造q程序设计语言中增加新的构造语句q如Fortran90中增加了向量运算语句q编译程序可以进行并行性检查和优化q增加了编译程序的复杂性。n编译指导编译指导q在原有的语言中增加表达并行运算的编译指导语句q并行编译程序跟据指导语句将代码转换成在并行代码q如OpenMPq介于上述两种方法之间线程操作函数n线程的创建和消除q分叉和汇集（fork-join）机制n线程的启动和终止n线程同步机制的建立和删除n线程通信机制的建立和删除q如MPI多线程并行程序设计方法n将独立的循环程序变成多线程q并行执行的线程可能改变相对执行的进度或顺序q要求不存在循环带来的相关性n将独立的程序段变

38、成多线程q变串行为并行q纤程（fiber）n执行一个任务n创建开销小n应用层可控Win32线程APInCreateThreadnMyThreadStartnCloseHandlenWaitForSingleObjectnWaitForMultipleObjectsnCreateMutexnReleaseMutexnInitializeCriticalSectionnDeleteCriticalSectionnEnterCriticalSectionnLeaveCriticalSectionnCreateSemaphorenReleaseSemaphoreWin32线程APInConvertTh

39、readToFibernGetFiberDatanCreateFibernfiberProcnSwitchToFibernDeleteFibernGetCurrentFiber例n#include n#include nconst int numThreads=4;nDWORD WINAPI helloFunc(LPVOID arg)n printf(“Hello Threadn”);n return 0;nmain()n HANDLE hThreadnumThreads;n for(int i=0;i numThreads;i+)n hThreadi=n CreateThread(NULL,

40、0,helloFunc,NULL,0,NULL);n WaitForMultipleObjects(numThreads,hThread,nTRUE,INFINITE);nOpenMP n编写可移植的多线程应用程序的APIq提供与平台无关的并行编程机制n编译指令pragman编译指示符directiven函数调用n环境变量q循环程序多线程化n支持多线程间的同步和局部数据变量n采用fork-join的执行模式n程序员不需要对线程的创建和删除进行编程n程序员不需要对同步操作进行详细编程q适用于共享存储器的并行计算机qwww.openmp.org#pragma omp parallel for fo

41、r(i=0;iMAX;i+)Ai=c*Ai+Bi;线程fork-join的执行模式n主线程主线程 q分裂出一组线程n并行性逐渐增加并行性逐渐增加q串行程序中嵌入并行性Parallel RegionsMaster ThreadOpenMP的编译指令nparallelqforqprivateqsingleqmasterqreductionqscheduleqsectionqifnbarriernatomicnreductionqchunk-size#pragmaompconstruct clause clause#pragma omp parallelThread1Thread2Thread3#p

42、ragma omp parallel blockParallel for#pragmaompparallelforfor(i=0;inumPixels;i+)pGrayScalBitmapi=(unsignedBYTE)(pRGBBitmapi.red*0.299+pRGBBitmapi.green*0.587+pRGBBitmapi.blue*0.114);Parallel for reductionsum=0;for(i=0;i100;i+)sum+=arrayi;/thisvariableneedstobesharedtogenerate/thecorrectresults,butpri

43、vatetoavoid/raceconditionsfromparallelexecutionsum=0;#pragmaompparallelforreduction(+:sum)for(i=0;i100;i+)sum+=arrayi;Parallel section#pragmaompparallelsections#pragmaompsectionphase1();#pragmaompsectionphase2();#pragmaompsectionphase3();SerialParallelOpenMP的线程调度算法n静态q将循环程序的各个迭代划分成相等大小的迭代束n或者近似相等大小的

44、迭代束q每个迭代束包含大致相等的迭代数量n动态q使用内部的工作队列n将迭代束分配给各个线程q线程空闲时从工作队列中获取下一个迭代束n运行时q迭代束的大小先比较大然后逐渐缩小n在开始时减少调度时间，然后考虑负载平衡n指导性的q使用环境变量以指定三种调度方式中的哪一个用于调度Parallel for scheduleFloatx1000,y1000;#pragmaompparallelforschedule(dynamic,8)for(k=0;k1000;k+)xk=cos(a)*xk+sin(a)*yk例例6-9 n假设如图6-11所示的线程模式在一个4核的处理器芯片上运行，子任务1到子任务6的

45、执行时间分别为1到6个单位。试画出4个线程的时空图并分析系统的加速比。解n执行时间=1+2+3+4+5+6=21个单位n加速比=21/12=1.75并行程序的性能优化n并行程序的优化q线程调度n分析程序的调用关系n分析程序的关键调用路径q分析程序中的热点n执行时间最长的函数q分析线程负载平衡q分析关键路径例例6-10 n对于例6-9的情况，假设在一个双核的处理器上运行，试画出4个线程的时空图并分析系统的加速比。假设：n（1）采用动态调度，子任务按编号顺序进入队列进行调度。n（2）子任务采用运行时调度。解：（1）n总的执行时间=15个单位n加速比=21/15=1.40解：（2）n总的执行时间=1

46、4个单位n加速比=21/14=1.50习题n29n31n32MPInMessagepassinginterfacen用于多处理器系统和集群系统q进程通过调用库函数进行消息收发通信q支持异构计算n标准的消息传递函数库q点到点通信函数q群集通信函数q不是一种语言n消息传递机制q点对点通信q群集通信MPI的点对点通信机制n发送操作模型发送操作模型q标准的标准的n同步或缓存的（取决于实现）q缓存的缓存的n把发送缓存复制到缓存后返回q同步的同步的n缓存被接收方读取后返回q就绪的就绪的n在接收方就绪时启动发送（启动发送后即返回）n发送发送/接收操作模型接收操作模型q阻塞的阻塞的n等到消息复制到缓存后返回q

47、非阻塞的非阻塞的n启动发送/接收后即返回MPI点对点通信函数例子nMPI_INITq启动MPI计算nMPI_FINALIZEq结束MPI计算nMPI_COMM_SIZEq确定进程数nMPI_COMM_RANKq确定自己的进程号nMPI_SENDq标准地发送一条消息nMPI_BSENDq发送一条缓存的消息nMPI_SSENDq发送一条同步的消息nMPI_RESENDq发送一条就绪的消息nMPI_ISENDq标准地发送一条非阻塞消息nMPI_IBSENDq发送一条缓存的非阻塞消息nMPI_ISSENDq发送一条同步的非阻塞消息nMPI_RESENDq发送一条就绪的非阻塞消息nMPI_RECVq标准

48、地接收一条消息nMPI_IRECVq非阻塞地接收一条消息nMPI_BCASTq广播一条消息nMPI_WAITq等待发送/接收完成nMPI_TESTq测试发送/接收是否完成MPI的聚合通信机制n同步方式同步方式q同步发送和阻塞接收q所有进程都完成调用时返回（屏障同步）n特异方式特异方式 distinguishedq一对多通信n散播n广播q多对一通信n归约q求最大值、最小值、总和、乘积等n收集MPI群集通信函数例子nMPI_Bcastq一对多广播同样的消息nMPI_Gatherq多对一收集各个进程的消息nMPI_Allgatherq全局收集nMPI_Scatterq一对多散播不同的消息nMPI_A

49、lltoallq每个进程给所有其他进程发送一个消息q每个进程从所有其他进程接收一个消息nMPI_Reduceq多对一归约nMPI_Reduce_scatterq归约并散播nMPI_Barrierq屏障同步例例6-11 n在一个双核的处理器芯片中运行了两个线程。线程A在开始运行2秒后向线程B发送数据，线程B在开始运行后的1秒后等待这个数据；线程B获得数据后运行3秒后向线程A发回结果，线程A在发送数据之后运行了2秒后开始等待线程B的结果。然后两个线程分别运行1秒后结束。忽略线程通信的时间开销，试画出线程运行状态时空图。解多线程与多处理器的映像n操作系统实现q动态线程调度算法q无法考虑应用的特征n应

50、用程序实现q需要由应用程序员优化调试q通过线程映像屏蔽向量n位向量n进程映像屏蔽向量的子集q需要动态获知逻辑处理器的数量q需要区分不同的硬件环境n超线程、多核、多芯片关键路径n多线程程序包含多个执行流q执行流在同步点相关n关键路径是最长的执行流Thread 1Thread 2Thread 3T0T1T2T3T4T5T6T7T8T9T10T11T12T13T14T15Acquire LThreads 2&3 DoneAcquire LWait for Threads 2&3Release LAcquire lock LWait for LRelease LWait for LThread 2 t