并行计算机的同步与通信课件.ppt

1、第第6章章 并行计算机的同步与并行计算机的同步与通信通信计算机系统结构胡越明计算机系Agendan6.1 并行计算机系统的通信 n6.2 Cache与存储器数据一致性 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操

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

5、取其他资源时放弃已持有的资源 q调用构件时避免使用锁信号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时间戳 存储转发 s

6、tore-and-forward 电路交换 circuit switching 虚拟切换 virtual cut-through 虫孔寻径 wormhole互连网络的消息传递通信方式存储转发store-and-forwardn问题：延迟大，缓存多转发部件互连网络的消息传递通信方式电路交换circuit switching问题：冲突多，利用率低互连网络的消息传递通信方式虚拟切换virtual cut-through问题：缓存多flits互连网络的消息传递通信方式虫孔寻径wormhole问题：死锁和活锁互连网络的消息传递通信方式n虫孔寻径与存储转发的比较互连网络的消息传递通信方式衡量指标n通信带宽

7、通信带宽q单位时间能够传输的数据量q取决于处理器的通信处理吞吐率、存储器的吞吐率和互连网络的传输带宽n通信延迟通信延迟q发送的时间开销q信号传输时间q传输持续时间q接收方的时间开销 n通信延迟隐藏能力通信延迟隐藏能力q通信时间与计算时间或者其他通信时间的重叠程度 例例6-2 n1个计算任务在单个核的计算机上运行的启动时间为1秒，运算时间为10秒，数据结果汇总的时间为1秒。如果将该计算任务放在多核处理器的计算机上运行，将运算部分分解成多个线程并行执行。n（1）假如任务的启动和数据汇总操作不能并行执行，运算部分可以进行任意的任务分解，任务之间的通信量可以忽略，也不考虑任务分解后存储系统对性能的影响

8、。问在处理器核的数量分别为2、4、8、16时的任务执行时间和加速比。n（2）上述情况下，假如每两个处理器核之间的通信时间为0.1秒，每对处理器核的通信串行进行，问在核的数量分别为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秒，加速比为

9、12/2.63=4.56。解：（2）n任务在单个核的计算机上没有通信时间，运行时间为12秒；n在双核计算机上的通信时间为10.1，运行时间为1+10/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，即

10、比单核计算机的计算时间更长。解加速比单核2核4核8核16核无通信开销11.712.673.694.56有通信开销11.692.351.980.82习题n66.2 Cache与存储器数据一致性与存储器数据一致性 n共享存储器多处理机系统的问题q访存冲突与数据一致性q数据多个副本之间的相同性数据一致性的实现n软件方法q编译分析q避免cache共享数据n总线监测q各cache设置监测部件nMESI协议n目录表法q全映射q有限目录q链式目录nSCI总线监测n所有cache不断监测总线上的每一个地址q总线使得写操作变成串行的qCache 失效时需要确定数据块的位置nwrite invalidate pr

11、otocol qinvalidates other copies on a write.nwrite update or write broadcast protocolqupdate all the cached copies of a data item when it is writtencpu1cpu2cache1cache2Mainmemory总线监测n写无效方式q多次写操作时只需一次invalidateq对于整个cache数据块进行 n写更新方式q对于数据块中的个别字进行 q读操作的命中率高q所有写操作通过总线写入所以相关的其他cache中n写操作的开销较大总线监测n每个处理器的c

12、ache中设置一个监测部件q监测总线上的写操作 q根据监测的情况改变本地cache块的状态n无效、修改、独占、共享n监测条件q主存中有一个单元被其他处理器所修改q而这个单元在本地cache中也有一个副本n对于写更新方法q拥有数据最新版本的cache需向其他cache提供数据块内容q阻止其他处理器从共享存储器的读操作MESI协议RH:读命中RMS:读失效，共享RME:读失效，独占WH:写命中WM:写失效SHR:读时检测命中SHW:写时检测命中或旨在修改的读 浊行复制回来 无效事务 旨在修改的读 填充 cache 行独占修改RHSHRSHWSHW(burst)RHWHWMWHWHSHRSHWRME

13、RMSSHWRHSHR共享无效例例6-3 n设单总线连接的两个CPU中采用MESI协议进行一致性操作，初始时某cache块都在无效状态，然后两个CPU对该存储块分别进行如下操作：nCPU A读，CPU B读，CPU A写，CPU B读，CPU B写n试写出每次访问后两个块的状态变化情况。事件状态A状态B说明初始无效无效（I）数据未装入CPU A读独占无效（I）读操作cache失效，装入CPU B读共享共享（S）读操作cache失效，装入后共享CPU A写修改无效（I）写操作命中CPU B读共享共享（S）读操作失效，装入CPU B写无效修改（M）写操作命中例例6-4 n在一个共享L2 cache

14、的双核处理器芯片中，两个L1 cache通过片内总线与L2 cache连接，并采用MESI协议保持一致性。假设L1 cache各有4个块，采用全相联地址映像和LRU替换策略，每个块的初始状态都是无效的。在以下读访问块地址序列下，试画出两个L1 cache中块的分配情况，并标出每个块的状态。nA核：1，0，6，7，8，0，1nB核：0，2，7，8，9，2，0解A 核 L1 cache 0 0 0 6 1 1 0 6 0 7 1 0 2 0 2 装入 0 7 8 9 7 8 8 0 7 9 7 8 2 8 0 7 1 0 8 2 装入 装入 装入 装入 装入 装入 替换 替换 命中 命中 替换 替

15、换 B 核 L1 cache B 核块地址 0 2 7 8 9 2 0 1 0 6 7 8 0 1 E 1 I I I I I I E E S I I S E I I E S E I S E E I 7 E S E S 2 S E S E 装入 6 操作 操作 S S E S E 2 E S S 6 S S E S E E S S 9 S S E S E E S S 7 8 A 核块地址 目录表法n全映射q每个快表目录项包含N个指示位段nN为系统中处理器的个数 q指示位段构成一个位向量n0表示相应的处理器cache没有该块n1表示有该块 n有限目录q每个快表目录项包含固定数量的指示位段q指示位

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

17、地址映像和LRU替换策略，每个块的初始状态都是无效的。在以下读访问块地址序列下，试画出两个L1 cache中块的分配情况，并标出每个块的指示状态位段。nCPU A：1，0，6，7，8，0，1nCPU B：0，2，7，8，9，2，0解CPU A cache 0 0 0 6 1 1 0 6 0 7 0 2 0 2 7 装入 0 7 9 7 8 8 0 7 9 7 8 8 0 7 1 0 8 2 装入 装入 装入 装入 装入 装入 替换 替换 命中 命中 替换 替换 CPU B cache CPU B 块地址 0 2 7 8 9 2 0 1 0 6 7 8 0 1 01 1 00 00 00 00

18、00 00 10 01 11 00 00 11 10 00 00 01 11 01 00 11 10 10 00 7 01 11 01 11 2 11 10 11 10 装入 6 操作 操作 11 01 01 11 10 2 10 11 11 6 11 01 01 11 10 10 11 11 9 11 11 01 01 10 10 11 11 1 8 8 2 CPU A 块地址 目录表法n链式目录q将目录分布到各个cache q每个cache的块表中只需存放一个cache指针 q单链或双链qSCICPUdCPUcCPUb控制图 10-5 链式目录表的例子存储器非一致数据块一致数据块cache

19、中间项头项尾项中间项CPUa数据一致性对cache性能的影响n影响cache性能的因素q单个处理器cache失效的数据传输q数据通信引起的传输n导致invalidations和后继cache失效n一致性失效处理机数量Cache容量块大小数据一致性对cache性能的影响一致性失效n真共享失效真共享失效true sharing misses q由cache一致性操作的通信引起q对共享数据的第一个写操作引起invalidationn伪共享失效伪共享失效false sharing misses q由每个cache块只有一个有效位引起q一个块中其他数据的写操作引起cache块读操作的失效qCache块是

20、共享的，但是数据字并没有共享数据一致性对cache性能的影响n一致性失效的例子q假定数据字x1和x2在同一个数据块中n数据块在 P1和P2之间共享q假定以下事件序列存储器数据的一致性时间一致性（consistency）q一个写操作写入共享存储器中的数值什么时候能够被读到 n串行一致性n弱化一致性n处理机一致性n松散一致性存储器数据的一致性串行一致性串行一致性sequential consistencyn处理机P对于存储单元X的写操作之后进行的读操作，其间如果没有其它处理机对X进行写访问，则总是返回由P写入的数值。n在一个处理机P1对于单元X进行写操作之后，另一处理机P2对于单元X的读操作只要两

21、者足够分离并且没有其它对于X的写操作发生，就能够返回P1写入的数值。n对于同一单元的写操作是顺序进行的，即两个处理机对于相同单元进行的写操作的顺序从任何处理机看都相同。如果数值1和2依次写入一个位置，处理机不可能先读得2，再读得1。存储器数据的一致性n弱化一致性弱化一致性weak consistencyq程序通过同步操作强调一致性，使得在这些同步点上数据保持一致，而不要求数据随时都是一致的。n处理机一致性处理机一致性processor consistencyq每个处理机发出的写操作被其它处理机看到的都保持原顺序，但两个不同处理机的写操作顺序可被其他处理机以不同的顺序看到。n松散一致性松散一致性

22、release consistencyq采用acquire-release同步操作使得数据保持一致，从而减少对硬件一致性处理的要求。SCInscalable coherence interface qIEEE 1596-1992n支持链式目录表法q双向链表 n采用双向链路 n采用虚拟切换传输方式 n支持大规模并行系统 q不要求消息按顺序提交 q使用64位固定长度地址的分布式存储器的寻址方案 n高16位用于寻找结点n低48位地址指定结点内的存储器地址 n采用16位差分ECL信号链路 q信号时钟250MHzq链路的数据传输带宽为1GB/s 本地处理器 请求器 响应器 输入 请求 响应 请求 缓存

23、分片 选择 输出 输入 输出 接收队列 传输队列 编码 插入 响应 存储等待 旁路 FIFO 习题n11n12n13n146.3 并行计算机的同步并行计算机的同步 n同步机制q并行系统中保持各并行程序正确运行的控制机制q建立在通信机制的基础上 q需要采用的硬件提供的机制来实现 n硬件原语硬件原语n原子交换atomic exchangeq实现锁n测试并设置test-and-setq实现锁n读取并加1fetch-and-incrementq实现屏障n读取并更新test-and-updateq实现PV操作原子交换原子交换n将一个寄存器的数值与一个存储器中的数值进行交换n难以在并行机中实现n要求存储器

24、读写操作在一条不可中断的指令中完成n硬件不能在读写操作之间响应中断AB原子交换原子交换n解决方案q用两条指令实现n链接装载load linkedn条件存储store conditionalq返回一个数值q表示其存储操作是否成功n两条指令按顺序执行q如果链接装载指令指定的存储单元在对应的条件存储指令执行之间被改变，则存储指令执行时失败。q如果处理机在这两条指令之间进行了上下文交换，则该条件存储指令也将失败。原子交换原子交换原子交换的实现 exch R4,0(R1)try:mov R3,R4;move exchange value from R4 to R3ll R2,0(R1);load lin

25、kedsc 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 failsR2BR2+1派生原语转锁spin lock处理机用循环方法试图得到的锁n没有没有cache一致性机制时一致性机制时li R2,#1;

26、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 lock wasnt 0派生原语采用链接装载/条件存储实现转锁lockit:ll R2,0(R1);load linkedbnez R

27、2,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一个用于锁住线程release派生原语屏障同步的实现lock(counterlock);/*ensure update atomic */if(count

28、=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=1);/*wait for arrivals*/派生原语n问题q屏障可能循环使用q从屏障离开的线程可能再次进入屏障q一个线程可能在另一

29、个线程离开屏障之前又进入屏障n代码的bugrelease派生原语n解决方案q对离开的线程计数n不允许线程在其他线程都离开上一个屏障之前又进入屏障q从而又初始化屏障q传感反相屏障sense-reversingn使用线程局部变量q初始化为1q交替地等待1和0release派生原语n屏障同步的实现q传感反相屏障local_sense=!local_sense;/*toggle local_sense*/lock(counterlock);/*ensure update atomic*/count=count+1;/*count arrivals*/if(count=total)/*all arriv

30、ed*/count=0;/*reset counter*/release=local_sense;/*release processes*/unlock(counterlock);/*unlock*/spin(release=local_sense);/*wait for signal*/第一个到达屏障的线程并不改变release的值同步操作的性能问题nContention for the lockq(2i+1)=n2+2nn锁变量访问的串行化q大大增加完成同步操作的时间n解决方案q增量资源n或分解资源n如散列表的分割q指数退避exponential backoffn访问等待时间以指数增加n防

31、止活锁q队列锁n锁变量释放时通知下一个线程q组合树n树中每个结点组合k个线程的同步n将对一个变量的竞争按树形结构分散同步操作的性能问题n指数等待同步操作的性能问题n组合树struct node /*a node in the combining tree*/int counterlock;/*lock for this node*/int count;/*counter for this node*/int parent;/*parent in the tree=0.P-1 except for root*/;struct node tree 0.P1;/*the tree of nodes*

32、/int local_sense;/*private per processor*/int release;/*global release flag*/同步操作的性能问题n组合树/*function to implement barrier*/barrier(int mynode,int local_sense)lock(treemynode.counterlock);/*protect count*/treemynode.count=treemynode.count+1;/*increment count*/if(treemynode.count=k)/*all arrived at my

33、node*/if(treemynode.parent=0)barrier(treemynode.parent);/*recursive call*/elserelease=local_sense;treemynode.count=0;/*reset for the next time*/unlock(treemynode.counterlock);/*unlock*/spin(release=local_sense);/*wait*/;/*code executed by a processor to join barrier*/local_sense=!local_sense;barrier

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

35、一个锁未解开使等待这个锁的线程停顿n死锁q线程的无限期的停顿现象n伪共享q线程之间的非真正的数据共享而引起的相关性多线程的程序的问题n数据竞争q数据相关性险象q以下两个if语句的表达式可能都为真吗？多线程的程序的问题线程1线程2原始代码t=x;x=t+1;u=x;x=u+2;并行情况1t=x;/x is 0 x=t+1;/x is 1u=x;x=u+2;/x is 2并行情况2t=x;x=t+1;/x is 1u=x /x is 0 x=u+2 /x is 2并行情况3t=x;/x is 0 x=t+1;/x is 1u=x;x=u+2;/x is 3数据竞争之二多线程的程序的问题n数据竞争之

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

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

38、配和调度n线程中任意时刻只能运行一个纤程 并行程序的概念n线程化的优点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;/*s

39、um the assigned areas */half=8;/*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&Pnlimi

40、t)send(Pn%half,sum);n if(Pn1);/*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容易实现（不需

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

42、相对执行的进度或顺序q要求不存在循环带来的相关性n将独立的程序段变成多线程q变串行为并行q纤程（fiber）n执行一个任务n创建开销小n应用层可控Win32线程APInCreateThreadnMyThreadStartnCloseHandlenWaitForSingleObjectnWaitForMultipleObjectsnCreateMutexnReleaseMutexnInitializeCriticalSectionnDeleteCriticalSectionnEnterCriticalSectionnLeaveCriticalSectionnCreateSemaphorenRel

43、easeSemaphoreWin32线程APInConvertThreadToFiber nGetFiberData nCreateFiber nfiberProc nSwitchToFiber n DeleteFiber nGetCurrentFiber 例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 numT

44、hreads;i+)n hThreadi=n CreateThread(NULL,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适用于共享存储器的并行计算

45、机qwww.openmp.org#pragma omp parallel for for(i=0;iMAX;i+)Ai=c*Ai+Bi;线程fork-join的执行模式n主线程主线程 q分裂出一组线程n并行性逐渐增加并行性逐渐增加q串行程序中嵌入并行性Parallel RegionsMaster ThreadOpenMP的编译指令nparallelqforqprivateqsingleqmasterqreductionqscheduleqsectionqifnbarriernatomicnreductionqchunk-size#pragma omp construct clause clau

46、se#pragma omp parallelThread1Thread2Thread3#pragma omp parallel blockParallel for#pragma omp parallel for for(i=0;inumPixels;i+)pGrayScalBitmapi=(unsigned BYTE)(pRGBBitmapi.red*0.299+pRGBBitmapi.green*0.587+pRGBBitmapi.blue*0.114);Parallel for reductionsum=0;for(i=0;i 100;i+)sum+=arrayi;/this variab

47、le needs to be shared to generate /the correct results,but private to avoid /race conditions from parallel executionsum=0;#pragma omp parallel for reduction(+:sum)for(i=0;i 100;i+)sum+=arrayi;Parallel section#pragma omp parallel sections#pragma omp section phase1();#pragma omp section phase2();#prag

48、ma omp section phase3();SerialParallelOpenMP的线程调度算法n静态q将循环程序的各个迭代划分成相等大小的迭代束n或者近似相等大小的迭代束q每个迭代束包含大致相等的迭代数量n动态q使用内部的工作队列n将迭代束分配给各个线程q线程空闲时从工作队列中获取下一个迭代束n运行时q迭代束的大小先比较大然后逐渐缩小n在开始时减少调度时间，然后考虑负载平衡n指导性的q使用环境变量以指定三种调度方式中的哪一个用于调度Parallel for scheduleFloat x1000,y1000;#pragma omp parallel for schedule(dynam

49、ic,8)for(k=0;k1000;k+)xk=cos(a)*xk+sin(a)*yk 例例6-9 n假设如图6-11所示的线程模式在一个4核的处理器芯片上运行，子任务1到子任务6的执行时间分别为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个线程的时空图并分析系统的加速比。假

50、设：n（1）采用动态调度，子任务按编号顺序进入队列进行调度。n（2）子任务采用运行时调度。解：（1）n总的执行时间=15个单位n加速比=21/15=1.40解：（2）n总的执行时间=14个单位n加速比=21/14=1.50习题n29n31n32MPInMessage passing interface n用于多处理器系统和集群系统q进程通过调用库函数进行消息收发通信q支持异构计算n标准的消息传递函数库q点到点通信函数q群集通信函数q不是一种语言n消息传递机制q点对点通信q群集通信MPI的点对点通信机制n发送操作模型发送操作模型q标准的标准的n同步或缓存的（取决于实现）q缓存的缓存的n把发送缓存