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

第6章并行计算机的同步与通信计算机系统结构胡越明计算机系Agenda6.1并行计算机系统的通信6.2Cache与存储器数据一致性6.3并行计算机的同步6.4并行计算机程序设计6.1并行计算机系统的通信并行计算机对程序的要求代码的可重入并行线程之间的竞态现象线程之间对共享变量的不同的读-写和写-写访问顺序导致不同的程序执行结果源自线程间的数据相关性并行计算机的通信方式共享存储器互连网络的消息传递共享存储器通信共享变量最简单的通信方式没有同步功能信号（signal）一个二进制变量可以表示条件、状态、锁和其它同步信息不能传递数据内容信箱固定格式的通信结构通常包含一个标志位在发送方和接收方之间起到同步的作用寻址和管理比较简单，不够灵活消息具有灵活格式的通信单位共享存储器通信线程同步给线程执行顺序施加约束的机制控制线程执行的相对顺序建立在互斥机制的基础上互斥机制使得一次只有一个线程对共享变量进行访问以保证每个线程对于共享变量访问的完整性常见的互斥机制锁信号量临界区共享存储器通信锁一种互斥变量一次只能被一个线程获得信号量通过PV操作在线程间传递同步信息原子操作P操作将一个变量减1减后的变量小于0时线程被阻塞V操作将一个变量加1加后的变量大于或等于0时释放一个线程共享存储器通信临界区短小的、不能被中断的程序段进入的线程数量是有限制的通常只允许一个线程进入临界区可以采用锁机制来实现锁两个基本的原子操作Acquire原子地等待锁的状态变成打开的状态将打开的锁状态变成关闭的状态这时该线程获得了锁Release原子地将锁的状态从关闭状态变成打开的状态这时线程释放了锁锁的类型互斥量用PV操作上锁和解锁有阻塞可以加上时间属性递归锁可以递归地获得的锁用于递归程序读写锁多读单写锁限制写操作只能由一个线程执行用于对共享变量的读写操作自旋锁非阻塞的锁用于多处理机系统和多核系统阻塞型锁机制的问题优先级的颠倒priorityinversion当一个低优先级的线程占用了一个锁之后，需要同一个锁的高优先级线程就只能等待。护航Convoying当一个线程拥有一个锁而被切换出去时其他的线程如果需要同一个锁的话都不能运行下去其他线程都围着拥有锁的线程团团转死锁Deadlock锁的拥有和依赖关系形成一个环死锁及其解决死锁的原因对资源（锁）的访问是独占的线程在已经持有一个资源时继续请求其他资源所有线程都不放弃已经持有的资源线程对资源的请求形成一个环解决方法复制需要独占访问的资源按照一定的顺序获取资源有序嵌套无法获取其他资源时放弃已持有的资源调用构件时避免使用锁信号硬件信号一种黏滞性的逻辑电平一旦被设置就一直保持不变直到被清除如访存完成、cache失效、时钟信号可以表示为一个寄存器变量对于信号变量的读操作清除这个信号软件信号表示为共享变量如进程中止信号互连网络的消息传递通信方式消息结点间通信的基本逻辑单位消息头目标结点号、源结点号、消息类型和消息长度等消息体通信数据数据消息长度消息类型消息体消息头序号目标结点号校验和消息尾互连网络的消息传递通信方式数据包数据传输的物理单位寻径信息序号数据内容校验位协议号时间戳•存储转发•store-and-forward•电路交换•circuitswitching•虚拟切换•virtualcut-through•虫孔寻径•wormhole互连网络的消息传递通信方式存储转发store-and-forward问题：延迟大，缓存多转发部件互连网络的消息传递通信方式电路交换circuitswitching问题：冲突多，利用率低互连网络的消息传递通信方式虚拟切换virtualcut-through问题：缓存多flits互连网络的消息传递通信方式虫孔寻径wormhole问题：死锁和活锁互连网络的消息传递通信方式虫孔寻径与存储转发的比较时间时间结点序列结点序列图10-4多机系统数据通信方式的例子(b)虫孔寻径(a)存储转发N4N4N3N3N2N2N1N1互连网络的消息传递通信方式衡量指标通信带宽单位时间能够传输的数据量取决于处理器的通信处理吞吐率、存储器的吞吐率和互连网络的传输带宽通信延迟发送的时间开销信号传输时间传输持续时间接收方的时间开销通信延迟隐藏能力通信时间与计算时间或者其他通信时间的重叠程度例6-21个计算任务在单个核的计算机上运行的启动时间为1秒，运算时间为10秒，数据结果汇总的时间为1秒。如果将该计算任务放在多核处理器的计算机上运行，将运算部分分解成多个线程并行执行。（1）假如任务的启动和数据汇总操作不能并行执行，运算部分可以进行任意的任务分解，任务之间的通信量可以忽略，也不考虑任务分解后存储系统对性能的影响。问在处理器核的数量分别为2、4、8、16时的任务执行时间和加速比。（2）上述情况下，假如每两个处理器核之间的通信时间为0.1秒，每对处理器核的通信串行进行，问在核的数量分别为2、4、8、16时的任务执行时间和加速比。解：（1）任务在单个核的计算机上运行时间为12秒；在双核计算机上的运行时间为1+10/2+1=7秒，加速比为12/7=1.71；在4核计算机上的运行时间为1+10/4+1=4.5秒，加速比为12/4.5=2.67；在8核计算机上的运行时间为1+10/8+1=3.25秒，加速比为12/3.25=3.69；在16核计算机上的运行时间为1+10/16+1=2.63秒，加速比为12/2.63=4.56。解：（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，运行时间为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，即比单核计算机的计算时间更长。解00.511.522.533.544.55单核2核4核8核16核无通信开销有通信开销加速比单核2核4核8核16核无通信开销11.712.673.694.56有通信开销11.692.351.980.82习题66.2Cache与存储器数据一致性共享存储器多处理机系统的问题访存冲突与数据一致性数据多个副本之间的相同性数据一致性的实现软件方法编译分析避免cache共享数据总线监测各cache设置监测部件MESI协议目录表法全映射有限目录链式目录SCI总线监测所有cache不断监测总线上的每一个地址总线使得写操作变成串行的Cache失效时需要确定数据块的位置writeinvalidateprotocolinvalidatesothercopiesonawrite.writeupdateorwritebroadcastprotocolupdateallthecachedcopiesofadataitemwhenitiswrittencpu1cpu2cache1cache2Mainmemory总线监测写无效方式多次写操作时只需一次invalidate对于整个cache数据块进行写更新方式对于数据块中的个别字进行读操作的命中率高所有写操作通过总线写入所以相关的其他cache中写操作的开销较大总线监测每个处理器的cache中设置一个监测部件监测总线上的写操作根据监测的情况改变本地cache块的状态无效、修改、独占、共享监测条件主存中有一个单元被其他处理器所修改而这个单元在本地cache中也有一个副本对于写更新方法拥有数据最新版本的cache需向其他cache提供数据块内容阻止其他处理器从共享存储器的读操作MESI协议RH:读命中RMS:读失效，共享RME:读失效，独占WH:写命中WM:写失效SHR:读时检测命中SHW:写时检测命中或旨在修改的读浊行复制回来无效事务旨在修改的读填充cache行独占修改RHSHRSHWSHW(burst)RHWHWMWHWHSHRSHWRMERMSSHWRHSHR共享无效例6-3设单总线连接的两个CPU中采用MESI协议进行一致性操作，初始时某cache块都在无效状态，然后两个CPU对该存储块分别进行如下操作：CPUA读，CPUB读，CPUA写，CPUB读，CPUB写试写出每次访问后两个块的状态变化情况。事件状态A状态B说明初始无效无效（I）数据未装入CPUA读独占无效（I）读操作cache失效，装入CPUB读共享共享（S）读操作cache失效，装入后共享CPUA写修改无效（I）写操作命中CPUB读共享共享（S）读操作失效，装入CPUB写无效修改（M）写操作命中例6-4在一个共享L2cache的双核处理器芯片中，两个L1cache通过片内总线与L2cache连接，并采用MESI协议保持一致性。假设L1cache各有4个块，采用全相联地址映像和LRU替换策略，每个块的初始状态都是无效的。在以下读访问块地址序列下，试画出两个L1cache中块的分配情况，并标出每个块的状态。A核：1，0，6，7，8，0，1B核：0，2，7，8，9，2，0解A核L1cache000611060710202装入07897880797828071082装入装入装入装入装入装入替换替换命中命中替换替换B核L1cacheB核块地址02789201067801E1IIIIIIEESIISEIIESEISEEI7ESES2SESE装入6操作操作SSESE2ESS6SSESEESS9SSESEESS78A核块地址目录表法全映射每个快表目录项包含N个指示位段N为系统中处理器的个数指示位段构成一个位向量0表示相应的处理器cache没有该块1表示有该块有限目录每个快表目录项包含固定数量的指示位段指示位段的位数与处理器数量无关链式目录例6-5设4个CPU的并行计算机中采用全映射的目录表法进行一致性操作，初始时某cache块都在无效状态，然后4个CPU对该存储块分别进行如下操作：CPU0读，CPU1读，CPU2读，CPU1替换，CPU0写试写出每次访问后该块的有效指示位段的变化情况，假设一致性操作采用写无效策略。事件指示状态位段初始0000CPU0读0001CPU1读0011CPU2读0111CPU1替换0101CPU0写0001例6-6在一个由2个CPU构成的并行计算机中采用全映射的目录表法进行一致性操作。假设各CPU的cache都只有4个块，采用全相联地址映像和LRU替换策略，每个块的初始状态都是无效的。在以下读访问块地址序列下，试画出两个L1cache中块的分配情况，并标出每个块的指示状态位段。CPUA：1，0，6，7，8，0，1CPUB：0，2，7，8，9，2，0解CPUAcache000611060702027装入079788079788071082装入装入装入装入装入装入替换替换命中命中替换替换CPUBcacheCPUB块地址027892010678010110000000000001001110000111000000111010011101000701110111211101110装入6操作操作1101011110210111161101011110101111911110101101011111882CPUA块地址目录表法链式目录将目录分布到各个cache每个cache的块表中只需存放一个cache指针单链或双链SCICPUdCPUcCPUb