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

《并行计算机的同步与通信课件》由会员分享，可在线阅读，更多相关《并行计算机的同步与通信课件（120页珍藏版）》请在装配图网上搜索。

1、单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第6章 并行计算机的同步与通信,计算机系统结构,胡越明,计算机系,第6章 并行计算机的同步与通信计算机系统结构,Agenda,6.1 并行计算机系统的通信,6.2 Cache与存储器数据一致性,6.3 并行计算机的同步,6.4 并行计算机程序设计,Agenda6.1 并行计算机系统的通信,6.1 并行计算机系统的通信,并行计算机对程序的要求,代码的可重入,并行线程之间的竞态现象,线程之间对共享变量的不同的读-写和写-写访问顺序导致不同的程序执行结果,源自线程间的数据相关性,并行计算机的通信方式,共享存储器,

2、互连网络的消息传递,6.1 并行计算机系统的通信并行计算机对程序的要求,共享存储器通信,共享变量,最简单的通信方式,没有同步功能,信号,（signal）,一个二进制变量,可以表示条件、状态、锁和其它同步信息,不能传递数据内容,信箱,固定格式的通信结构,通常包含一个标志位,在发送方和接收方之间起到同步的作用,寻址和管理比较简单，不够灵活,消息,具有灵活格式的通信单位,共享存储器通信共享变量,共享存储器通信,线程同步,给线程执行顺序施加约束的机制,控制线程执行的相对顺序,建立在互斥机制的基础上,互斥机制,使得一次只有一个线程对共享变量进行访问,以保证每个线程对于共享变量访问的完整性,常见的互斥机制

3、,锁,信号量,临界区,共享存储器通信线程同步,共享存储器通信,锁,一种互斥变量,一次只能被一个线程获得,信号量,通过PV操作在线程间传递同步信息,原子操作,P操作将一个变量减1,减后的变量小于0时线程被阻塞,V操作将一个变量加1,加后的变量大于或等于0时释放一个线程,共享存储器通信锁,共享存储器通信,临界区,短小的、不能被中断的程序段,进入的线程数量是有限制的,通常只允许一个线程进入临界区,可以采用锁机制来实现,共享存储器通信临界区,锁,两个基本的原子操作,Acquire,原子地等待锁的状态变成打开的状态,将打开的锁状态变成关闭的状态,这时该线程获得了锁,Release,原子地将锁的状态从关闭

4、状态变成打开的状态,这时线程释放了锁,锁两个基本的原子操作,锁的类型,互斥量,用PV操作上锁和解锁,有阻塞,可以加上时间属性,递归锁,可以递归地获得的锁,用于递归程序,读写锁,多读单写锁,限制写操作只能由一个线程执行,用于对共享变量的读写操作,自旋锁,非阻塞的锁,用于多处理机系统和多核系统,锁的类型互斥量,阻塞型锁机制的问题,优先级的颠倒,priority inversion,当一个低优先级的线程占用了一个锁之后，需要同一个锁的高优先级线程就只能等待。,护航,Convoying,当一个线程拥有一个锁而被切换出去时其他的线程如果需要同一个锁的话都不能运行下去,其他线程都围着拥有锁的线程团团转,死

5、锁,Deadlock,锁的拥有和依赖关系形成一个环,阻塞型锁机制的问题优先级的颠倒priority invers,死锁及其解决,死锁的原因,对资源（锁）的访问是独占的,线程在已经持有一个资源时继续请求其他资源,所有线程都不放弃已经持有的资源,线程对资源的请求形成一个环,解决方法,复制需要独占访问的资源,按照一定的顺序获取资源,有序嵌套,无法获取其他资源时放弃已持有的资源,调用构件时避免使用锁,死锁及其解决死锁的原因,信号,硬件信号,一种黏滞性的逻辑电平,一旦被设置就一直保持不变,直到被清除,如访存完成、cache失效、时钟信号,可以表示为一个寄存器变量,对于信号变量的读操作清除这个信号,软件信

6、号,表示为共享变量,如进程中止信号,信号硬件信号,互连网络的消息传递通信方式,消息,结点间通信的基本逻辑单位,消息头,目标结点号、源结点号、消息类型和消息长度等,消息体,通信数据,互连网络的消息传递通信方式 消息,互连网络的消息传递通信方式,数据包,数据传输的物理单位,寻径信息,序号,数据内容,校验位,协议号,时间戳,存储转发,store-and-forward,电路交换,circuit switching,虚拟切换,virtual cut-through,虫孔寻径,wormhole,互连网络的消息传递通信方式数据包存储转发,互连网络的消息传递通信方式,存储转发,store-and-forwa

7、rd,问题：延迟大，缓存多,互连网络的消息传递通信方式存储转发store-and-for,互连网络的消息传递通信方式,电路交换,circuit switching,问题：冲突多，利用率低,互连网络的消息传递通信方式电路交换circuit switc,互连网络的消息传递通信方式,虚拟切换,virtual cut-through,问题：缓存多,flits,互连网络的消息传递通信方式虚拟切换virtual cut-t,互连网络的消息传递通信方式,虫孔寻径,wormhole,问题：死锁和活锁,互连网络的消息传递通信方式虫孔寻径wormhole,互连网络的消息传递通信方式,虫孔寻径与存储转发的比较,互连

8、网络的消息传递通信方式虫孔寻径与存储转发的比较,互连网络的消息传递通信方式,衡量指标,通信带宽,单位时间能够传输的数据量,取决于处理器的通信处理吞吐率、存储器的吞吐率和互连网络的传输带宽,通信延迟,发送的时间开销,信号传输时间,传输持续时间,接收方的时间开销,通信延迟隐藏能力,通信时间与计算时间或者其他通信时间的重叠程度,互连网络的消息传递通信方式衡量指标,例6-2,1个计算任务在单个核的计算机上运行的启动时间为1秒，运算时间为10秒，数据结果汇总的时间为1秒。如果将该计算任务放在多核处理器的计算机上运行，将运算部分分解成多个线程并行执行。,（1）假如任务的启动和数据汇总操作不能并行执行，运算

9、部分可以进行任意的任务分解，任务之间的通信量可以忽略，也不考虑任务分解后存储系统对性能的影响。问在处理器核的数量分别为2、4、8、16时的任务执行时间和加速比。,（2）上述情况下，假如每两个处理器核之间的通信时间为0.1秒，每对处理器核的通信串行进行，问在核的数量分别为2、4、8、16时的任务执行时间和加速比。,例6-2 1个计算任务在单个核的计算机上运行的启动时间为1秒,解,：（1）,任务在单个核的计算机上运行时间为12秒；,在双核计算机上的运行时间为1+10/2+1=7秒，加速比为12/7=1.71；,在4核计算机上的运行时间为1+10/4+1=4.5秒，加速比为12/4.5=2.67；,

10、在8核计算机上的运行时间为1+10/8+1=3.25秒，加速比为12/3.25=3.69；,在16核计算机上的运行时间为1+10/16+1=2.63秒，加速比为12/2.63=4.56。,解：（1）任务在单个核的计算机上运行时间为12秒；,解,：（2）,任务在单个核的计算机上没有通信时间，运行时间为12秒；,在双核计算机上的通信时间为1,0.1，运行时间为1+10/2+1+0.1=7.1秒，加速比为12/7.1=1.69；,在4核计算机上的通信时间为6,0.1=0.6，运行时间为1+10/4+1+0.6=5.1秒，加速比为12/5.1=2.35；,在8核计算机上的通信时间为28,0.1=2.8

11、，运行时间为1+10/8+1+2.8=6.05秒，加速比为12/6.05=1.98；,在16核计算机上的通信时间为120,0.1=12，运行时间为1+10/16+1+12=14.63秒，加速比为12/14.63=0.82，即比单核计算机的计算时间更长。,解：（2）任务在单个核的计算机上没有通信时间，运行时间为12,解,加速比,单核,2核,4核,8核,16核,无通信开销,1,1.71,2.67,3.69,4.56,有通信开销,1,1.69,2.35,1.98,0.82,解加速比单核2核4核8核16核无通信开销11.712.673,习题,6,习题6,6.2 Cache与存储器数据一致性,共享存储器

12、多处理机系统的问题,访存冲突与数据一致性,数据多个副本之间的相同性,6.2 Cache与存储器数据一致性 共享存储器多处理机系统,数据一致性的实现,软件方法,编译分析,避免,cache,共享数据,总线监测,各,cache,设置监测部件,MESI,协议,目录表法,全映射,有限目录,链式目录,SCI,数据一致性的实现软件方法,总线监测,所有cache不断监测总线上的每一个地址,总线使得写操作变成串行的,Cache 失效时需要确定数据块的位置,write invalidate protocol,invalidates other copies on a write.,write update or

13、write broadcast protocol,update all the cached copies of a data item when it is written,cpu1,cpu2,cache1,cache2,Main,memory,总线监测所有cache不断监测总线上的每一个地址cpu1cp,总线监测,写无效方式,多次写操作时只需一次invalidate,对于整个cache数据块进行,写更新方式,对于数据块中的个别字进行,读操作的命中率高,所有写操作通过总线写入所以相关的其他cache中,写操作的开销较大,总线监测写无效方式,总线监测,每个处理器的cache中设置一个监测部件,

14、监测总线上的写操作,根据监测的情况改变本地cache块的状态,无效、修改、独占、共享,监测条件,主存中有一个单元被其他处理器所修改,而这个单元在本地cache中也有一个副本,对于写更新方法,拥有数据最新版本的cache需向其他cache提供数据块内容,阻止其他处理器从共享存储器的读操作,总线监测每个处理器的cache中设置一个监测部件,MESI,协议,MESI协议,例6-3,设单总线连接的两个CPU中采用MESI协议进行一致性操作，初始时某cache块都在无效状态，然后两个CPU对该存储块分别进行如下操作：,CPU A读，CPU B读，CPU A写，CPU B读，CPU B写,试写出每次访问后

15、两个块的状态变化情况。,事件,状态A,状态B,说明,初始,无效,无效（I）,数据未装入,CPU A读,独占,无效（I）,读操作cache失效，装入,CPU B读,共享,共享（S）,读操作cache失效，装入后共享,CPU A写,修改,无效（I）,写操作命中,CPU B读,共享,共享（S）,读操作失效，装入,CPU B写,无效,修改（M）,写操作命中,例6-3 设单总线连接的两个CPU中采用MESI协议进行一致,例6-4,在一个共享L2 cache的双核处理器芯片中，两个L1 cache通过片内总线与L2 cache连接，并采用MESI协议保持一致性。假设L1 cache各有4个块，采用全相联地

16、址映像和LRU替换策略，每个块的初始状态都是无效的。在以下读访问块地址序列下，试画出两个L1 cache中块的分配情况，并标出每个块的状态。,A核：1，0，6，7，8，0，1,B核：0，2，7，8，9，2，0,例6-4 在一个共享L2 cache的双核处理器芯片中，两个,解,解,目录表法,全映射,每个快表目录项包含,N,个指示位段,N,为系统中处理器的个数,指示位段构成一个位向量,0表示相应的处理器cache没有该块,1表示有该块,有限目录,每个快表目录项包含固定数量的指示位段,指示位段的位数与处理器数量无关,链式目录,目录表法全映射,例6-5,设4个CPU的并行计算机中采用全映射的目录表法进行一致性操作，初始时某cache块都在无效状态，然后4个CPU对该存储块分别进行如下操作：,CPU 0读，CPU 1读，CPU 2读，CPU 1替换，CPU 0写,试写出每次访问后该块的有效指示位段的变化情况，假设一致性操作采用写无效策略。,事件,指示状态位段,初始,0000,CPU 0读,0001,CPU 1读,0011,CPU 2读,0111,CPU 1替换,0101,CPU 0写,0001,