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

第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问题 死锁和活锁 互连网络的消息传递通信方式 虫孔寻径与存储转发的比较 互连网络的消息传递通信方式 衡量指标通信带宽单位时间能够传输的数据量取决于处理器的通信处理吞吐率 存储器的吞吐率和互连网络的传输带宽通信延迟发送的时间开销信号传输时间传输持续时间接收方的时间开销通信延迟隐藏能力通信时间与计算时间或者其他通信时间的重叠程度 例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 即比单核计算机的计算时间更长 解 习题 6 6 2Cache与存储器数据一致性 共享存储器多处理机系统的问题访存冲突与数据一致性数据多个副本之间的相同性 数据一致性的实现 软件方法编译分析避免cache共享数据总线监测各cache设置监测部件MESI协议目录表法全映射有限目录链式目录SCI 总线监测 所有cache不断监测总线上的每一个地址总线使得写操作变成串行的Cache失效时需要确定数据块的位置writeinvalidateprotocolinvalidatesothercopiesonawrite writeupdateorwritebroadcastprotocolupdateallthecachedcopiesofadataitemwhenitiswritten cpu1 cpu2 cache1 cache2 Mainmemory 总线监测 写无效方式多次写操作时只需一次invalidate对于整个cache数据块进行写更新方式对于数据块中的个别字进行读操作的命中率高所有写操作通过总线写入所以相关的其他cache中写操作的开销较大 总线监测 每个处理器的cache中设置一个监测部件监测总线上的写操作根据监测的情况改变本地cache块的状态无效 修改 独占 共享监测条件主存中有一个单元被其他处理器所修改而这个单元在本地cache中也有一个副本对于写更新方法拥有数据最新版本的cache需向其他cache提供数据块内容阻止其他处理器从共享存储器的读操作 MESI协议 例6 3 设单总线连接的两个CPU中采用MESI协议进行一致性操作 初始时某cache块都在无效状态 然后两个CPU对该存储块分别进行如下操作 CPUA读 CPUB读 CPUA写 CPUB读 CPUB写试写出每次访问后两个块的状态变化情况 例6 4 在一个共享L2cache的双核处理器芯片中 两个L1cache通过片内总线与L2cache连接 并采用MESI协议保持一致性 假设L1cache各有4个块 采用全相联地址映像和LRU替换策略 每个块的初始状态都是无效的 在以下读访问块地址序列下 试画出两个L1cache中块的分配情况 并标出每个块的状态 A核 1 0 6 7 8 0 1B核 0 2 7 8 9 2 0 解 目录表法 全映射每个快表目录项包含N个指示位段N为系统中处理器的个数指示位段构成一个位向量0表示相应的处理器cache没有该块1表示有该块有限目录每个快表目录项包含固定数量的指示位段指示位段的位数与处理器数量无关链式目录 例6 5 设4个CPU的并行计算机中采用全映射的目录表法进行一致性操作 初始时某cache块都在无效状态 然后4个CPU对该存储块分别进行如下操作 CPU0读 CPU1读 CPU2读 CPU1替换 CPU0写试写出每次访问后该块的有效指示位段的变化情况 假设一致性操作采用写无效策略 例6 6 在一个由2个CPU构成的并行计算机中采用全映射的目录表法进行一致性操作 假设各CPU的cache都只有4个块 采用全相联地址映像和LRU替换策略 每个块的初始状态都是无效的 在以下读访问块地址序列下 试画出两个L1cache中块的分配情况 并标出每个块的指示状态位段 CPUA 1 0 6 7 8 0 1CPUB 0 2 7 8 9 2 0 解 目录表法 链式目录将目录分布到各个cache每个cache的块表中只需存放一个cache指针单链或双链SCI 数据一致性对cache性能的影响 影响cache性能的因素单个处理器cache失效的数据传输数据通信引起的传输导致invalidations和后继cache失效一致性失效处理机数量Cache容量块大小 数据一致性对cache性能的影响 一致性失效真共享失效truesharingmisses由cache一致性操作的通信引起对共享数据的第一个写操作引起invalidation伪共享失效falsesharingmisses由每个cache块只有一个有效位引起一个块中其他数据的写操作引起cache块读操作的失效Cache块是共享的 但是数据字并没有共享 数据一致性对cache性能的影响 一致性失效的例子假定数据字x1和x2在同一个数据块中数据块在P1和P2之间共享假定以下事件序列 存储器数据的一致性 时间一致性 consistency 一个写操作写入共享存储器中的数值什么时候能够被读到串行一致性弱化一致性处理机一致性松散一致性 存储器数据的一致性 串行一致性sequentialconsistency处理机P对于存储单元X的写操作之后进行的读操作 其间如果没有其它处理机对X进行写访问 则总是返回由P写入的数值 在一个处理机P1对于单元X进行写操作之后 另一处理机P2对于单元X的读操作只要两者足够分离并且没有其它对于X的写操作发生 就能够返回P1写入的数值 对于同一单元的写操作是顺序进行的 即两个处理机对于相同单元进行的写操作的顺序从任何处理机看都相同 如果数值1和2依次写入一个位置 处理机不可能先读得2 再读得1 存储器数据的一致性 弱化一致性weakconsistency程序通过同步操作强调一致性 使得在这些同步点上数据保持一致 而不要求数据随时都是一致的 处理机一致性processorconsistency每个处理机发出的写操作被其它处理机看到的都保持原顺序 但两个不同处理机的写操作顺序可被其他处理机以不同的顺序看到 松散一致性releaseconsistency采用acquire release同步操作使得数据保持一致 从而减少对硬件一致性处理的要求 SCI scalablecoherenceinterfaceIEEE1596 1992支持链式目录表法双向链表采用双向链路采用虚拟切换传输方式支持大规模并行系统不要求消息按顺序提交使用64位固定长度地址的分布式存储器的寻址方案高16位用于寻找结点低48位地址指定结点内的存储器地址采用16位差分ECL信号链路信号时钟250MHz链路的数据传输带宽为1GB s 习题 11121314 6 3并行计算机的同步 同步机制并行系统中保持各并行程序正确运行的控制机制建立在通信机制的基础上需要采用的硬件提供的机制来实现硬件原语 硬件原语 原子交换atomicexchange实现锁测试并设置test and set实现锁读取并加1fetch and increment实现屏障读取并更新test and update实现PV操作 原子交换 将一个寄存器的数值与一个存储器中的数值进行交换难以在并行机中实现要求存储器读写操作在一条不可中断的指令中完成硬件不能在读写操作之间响应中断 A B 原子交换 解决方案用两条指令实现链接装载loadlinked条件存储storeconditional返回一个数值表示其存储操作是否成功两条指令按顺序执行如果链接装载指令指定的存储单元在对应的条件存储指令执行之间被改变 则存储指令执行时失败 如果处理机在这两条指令之间进行了上下文交换 则该条件存储指令也将失败 原子交换 原子交换的实现exchR4 0 R1 try movR3 R4 moveexchangevaluefromR4toR3llR2 0 R1 loadlinkedscR3 0 R1 storeconditionalbeqzR3 try branchstorefailesmovR4 R2 putloadvalueinR4 宏指令 macroinstruction R3 B R4 R2 读取并加1 try llR2 0 R1 loadlinkedaddiR2 R2 1 incrementscR2 0 R1 storeconditionalbeqzR2 try branchstorefails R2 B R2 1 派生原语 转锁spinlock处理机用循环方法试图得到的锁没有cache一致性机制时liR2 1 loadimmediatelockit exchR2 0 R1 atomicexchangebnezR2 lockit alreadylocked 有cache一致性机制时lockit lwR2 0 R1 loadoflockbnezR2 lockit notavailable spinliR2 1 loadlockedvalueexchR2 0 R1 swapbnezR2 lockit branchiflockwasn t0 派生原语 采用链接装载 条件存储实现转锁lockit llR2 0 R1 loadlinkedbnezR2 lockit notavailable spinliR2 1 lockedvaluescR2 0 R1 storebeqzR2 lockit branchifstorefailes 1 B R2 派生原语 屏障同步barrier强制所有的线程等待直到所有的线程都到达屏障时释放所有的线程用一个计数器对到达的线程计数 Gather阶段 用一个信号释放所有的线程 release阶段 用两个自旋锁实现一个用于保护计数器一个用于锁住线程 release 派生原语 屏障同步的实现lock counterlock ensureupdateatomic if count 0 release 0 firstarrivalresetrelease count count 1 countarrivals unlock counterlock releaselock if count total allarrived count 0 resetcounter release 1 releaseprocesses else moretocome spin release 1 waitforarrivals 派生原语 问题屏障可能循环使用从屏障离开的线程可能再次进入屏障一个线程可能在另一个线程离开屏障之前又进入屏障代码的bug release 派生原语 解决方案对离开的线程计数不允许线程在其他线程都离开上一个屏障之前又进入屏障从而又初始化屏障传感反相屏障sense reversing使用线程局部变量初始化为1交替地等待1和0 release 派生原语 屏障同步的实现传感反相屏障local sense local sense togglelocal sense lock counterlock ensureupdateatomic count count 1 countarrivals if count total allarrived count 0 resetcounter release local sense releaseprocesses unlock counterlock unlock spin release local sense waitforsignal 第一个到达屏障的线程并不改变release的值 同步操作的性能问题 Contentionforthelock 2i 1 n2 2n锁变量访问的串行化大大增加完成同步操作的时间解决方案增量资源或分解资源如散列表的分割指数退避exponentialbackoff访问等待时间以指数增加防止活锁队列锁锁变量释放时通知下一个线程组合树树中每个结点组合k个线程的同步将对一个变量的竞争按树形结构分散 同步操作的性能问题 指数等待 同步操作的性能问题 组合树structnode anodeinthecombiningtree intcounterlock lockforthisnode intcount counterforthisnode intparent parentinthetree 0 P 1exceptforroot structnodetree 0 P 1 thetreeofnodes intlocal sense privateperprocessor intrelease globalreleaseflag 同步操作的性能问题 组合树 functiontoimplementbarrier barrier intmynode intlocal sense lock tree mynode counterlock protectcount tree mynode count tree mynode count 1 incrementcount if tree mynode count k allarrivedatmynode if tree mynode parent 0 barrier tree mynode parent recursivecall else release local sense tree mynode count 0 resetforthenexttime unlock tree mynode counterlock unlock spin release local sense wait codeexecutedbyaprocessortojoinbarrier local sense local sense barrier mynode 事务存储器 同步机制的硬件解决方案非互锁的机制使得系统能够并行地执行原子操作事务锁的作用范围每个事务由一个线程推测性地执行而不请求锁没有遇到冲突时提交否则事务将放弃 abort 进行卷回 rollback 并重新开始事务没有成功提交之前不会对其它线程产生作用 事务存储器 事务由线程中的一组指令构成串行性从其他线程看来不会有不同的执行顺序原子性整体提交或者整体放弃提交之前对其它线程看不到 同步与多线程 多线程的程序的问题数据竞争由各线程对共享数据读 写访问和写 写访问顺序的不确定性引起同步同步机制会带来的开销线程停顿一个锁未解开使等待这个锁的线程停顿死锁线程的无限期的停顿现象伪共享线程之间的非真正的数据共享而引起的相关性 多线程的程序的问题 数据竞争数据相关性险象以下两个if语句的表达式可能都为真吗 多线程的程序的问题 数据竞争之二 多线程的程序的问题 数据竞争之三 if list next NULL insert list next node1 if list next NULL insert list next node2 node2 node1 数据竞争的解决 变量局部化将变量改为线程局部的如将全局和分解为部分和用临界区控制共享变量的访问通过锁 信号量等实现每个共享数据用一把锁互斥机制 同步与多线程 并行线程与临界区criticalsection访问共享数据的程序段在某段时间内仅允许一定数目的线程访问的一段代码大多数情况下一次只有一个线程能够进入同一个临界区可采用互斥机制实现 同步与多线程 并行线程与屏障 习题 1618202122 6 5并行计算机程序的软件支持 并行程序的概念任务划分将一个任务划分成多个并行子任务使得处理器负载平衡数据划分将数据对象划分成多个并行子集提高访存的效率以及cache的命中率数据流划分根据数据处理的过程划分一个子任务的输出是另一个子任务的输入划分的目标负载平衡降低调度开销 通信开销和同步开销 并行程序的概念 任务task应用级的计算单位单任务线程为每个任务动态创建和终止创建和终止开销问题大量线程时的开销线程池预先创建的固定数量的线程与处理器数量匹配可完成多个任务应用程序中动态任务分配和调度线程中任意时刻只能运行一个纤程 并行程序的概念 线程化的优点创建速度较进程快资源利用率高便于数据共享线程化的缺点增加程序设计的复杂性程序调试较难数据竞争 同步 死锁 多线程的执行 硬件多线程每个线程运行在不同逻辑处理器上优先级相同硬件的通信开销真正的并行执行软件多线程运行在同一个逻辑处理器上OS动态改变优先级共享本地存储器通信开销小互斥容易解决 共享存储器系统程序设计例子 8个处理机 单总线连接sum Pn 0 for i 8000 Pn i1 exitwithfinalsuminsum 0 其中synch 函数是一个屏障同步函数 分布消息传递型系统程序例子 假设64个处理机 各处理机具有不同的地址空间 sum 0 for i 0 i half exitwithfinalsum 任务划分 对数据进行划分使得不同的子任务对不同的数据子集进行处理对计算过程中的步骤进行使得每个线程具有不同的程序代码任务分解的一般方法根据数据运算流程图进行 例6 8 对于数组运算E A B C D 其中 A B C和D都是具有n个元素的数组 试画出其数据流程图 指出两种子任务划分方式 解 横向划分纵向划分 实现并行程序设计的方法 库函数在串行程序的标准库的基础上增加支持并行操作的函数如MPI的消息传递库和POSIX的Pthread多线程库容易实现 不需要改变编译程序 程序中的并行性没有经过编译程序的检查 分析 优化新的语言构造程序设计语言中增加新的构造语句如Fortran90中增加了向量运算语句编译程序可以进行并行性检查和优化增加了编译程序的复杂性 编译指导在原有的语言中增加表达并行运算的编译指导语句并行编译程序跟据指导语句将代码转换成在并行代码如OpenMP介于上述两种方法之间 线程操作函数 线程的创建和消除分叉和汇集 fork join 机制线程的启动和终止线程同步机制的建立和删除线程通信机制的建立和删除如MPI 多线程并行程序设计方法 将独立的循环程序变成多线程并行执行的线程可能改变相对执行的进度或顺序要求不存在循环带来的相关性将独立的程序段变成多线程变串行为并行纤程 fiber 执行一个任务创建开销小应用层可控 Win32线程API CreateThreadMyThreadStartCloseHandleWaitForSingleObjectWaitForMultipleObjectsCreateMutexReleaseMutexInitializeCriticalSectionDeleteCriticalSectionEnterCriticalSectionLeaveCriticalSectionCreateSemaphoreReleaseSemaphore Win32线程API ConvertThreadToFiberGetFiberDataCreateFiberfiberProcSwitchToFiberDeleteFiberGetCurrentFiber 例 include includeconstintnumThreads 4 DWORDWINAPIhelloFunc LPVOIDarg printf HelloThread n return0 main HANDLEhThread numThreads for inti 0 i numThreads i hThread i CreateThread NULL 0 helloFunc NULL 0 NULL WaitForMultipleObjects numThreads hThread TRUE INFINITE OpenMP 编写可移植的多线程应用程序的API提供与平台无关的并行编程机制编译指令pragma编译指示符directive函数调用环境变量循环程序多线程化支持多线程间的同步和局部数据变量采用fork join的执行模式程序员不需要对线程的创建和删除进行编程程序员不需要对同步操作进行详细编程适用于共享存储器的并行计算机www openmp org pragmaompparallelforfor i 0 i MAX i A i c A i B i 线程 fork join的执行模式 主线程分裂出一组线程并行性逐渐增加串行程序中嵌入并行性 ParallelRegions MasterThread OpenMP的编译指令 parallelforprivatesinglemasterreductionschedulesectionifbarrieratomicreductionchunk size pragmaompconstruct clause clause pragmaompparallel block Parallelfor pragmaompparallelforfor i 0 i numPixels i pGrayScalBitmap i unsignedBYTE pRGBBitmap i red 0 299 pRGBBitmap i green 0 587 pRGBBitmap i blue 0 114 Parallelforreduction sum 0 for i 0 i 100 i sum array i thisvariableneedstobesharedtogenerate thecorrectresults butprivatetoavoid raceconditionsfromparallelexecution sum 0 pragmaompparallelforreduction sum for i 0 i 100 i sum array i Parallelsection pragmaompparallelsections pragmaompsectionphase1 pragmaompsectionphase2 pragmaompsectionphase3 Serial Parallel OpenMP的线程调度算法 静态将循环程序的各个迭代划分成相等大小的迭代束或者近似相等大小的迭代束每个迭代束包含大致相等的迭代数量动态使用内部的工作队列将迭代束分配给各个线程线程空闲时从工作队列中获取下一个迭代束运行时迭代束的大小先比较大然后逐渐缩小在开始时减少调度时间 然后考虑负载平衡指导性的使用环境变量以指定三种调度方式中的哪一个用于调度 Parallelforschedule Floatx 1000 y 1000 pragmaompparallelforschedule dynamic 8 for k 0 k 1000 k x k cos a x k sin a y k 例6 9 假设如图6 11所示的线程模式在一个4核的处理器芯片上运行 子任务1到子任务6的执行时间分别为1到6个单位 试画出4个线程的时空图并分析系统的加速比 解 执行时间 1 2 3 4 5 6 21个单位加速比 21 12 1 75 并行程序的性能优化 并行程序的优化线程调度分析程序的调用关系分析程序的关键调用路径分析程序中的热点执行时间最长的函数分析线程负载平衡分析关键路径 例6 10 对于例6 9的情况 假设在一个双核的处理器上运行 试画出4个线程的时空图并分析系统的加速比 假设 1 采用动态调度 子任务按编号顺序进入队列进行调度 2 子任务采用运行时调度 解 1 总的执行时间 15个单位加速比 21 15 1 40 解 2 总的执行时间 14个单位加速比 21 14 1 50 习题 293132 MPI Messagepassinginterface用于多处理器系统和集群系统进程通过调用库函数进行消息收发通信支持异构计算标准的消息传递函数库点到点通信函数群集通信函数不是一种语言消息传递机制点对点通信群集通信 MPI的点对点通信机制 发送操作模型标准的同步或缓存的 取决于实现 缓存的把发送缓存复制到缓存后返回同步的缓存被接收方读取后返回就绪的在接收方就绪时启动发送 启动发送后即返回 发送 接收操作模型阻塞的等到消息复制到缓存后返回非阻塞的启动发送 接收后即返回 MPI点对点通信函数例子 MPI INIT启动MPI计算MPI FINALIZE结束MPI计算MPI COMM SIZE确定进程数MPI COMM RANK确定自己的进程号MPI SEND标准地发送一条消息MPI BSEND发送一条缓存的消息MPI SSEND发送一条同步的消息MPI RESEND发送一条就绪的消息 MPI ISEND标准地发送一条非阻塞消息MPI IBSEND发送一条缓存的非阻塞消息MPI ISSEND发送一条同步的非阻塞消息MPI RESEND发送一条就绪的非阻塞消息MPI RECV标准地接收一条消息MPI IRECV非阻塞地接收一条消息MPI BCAST广播一条消息MPI WAIT