并行计算机系统并行计算机系统第一节 并行计算机系统的数据通信n数据包数据包q寻径信息q序号q数据内容q校验位q协议号q时间戳存储转发store-and-forward电路交换circuitswitching虚拟切换virtualcut-through虫孔寻径wormhole第一节 并行计算机系统的数据通信2. 电路交换circuitswitching问题：冲突多，利用率低第一节 并行计算机系统的数据通信3. 虚拟切换virtualcut-through问题：缓存多flits第一节 并行计算机系统的数据通信4. 虫孔寻径wormhole问题：死锁和活锁第一节 并行计算机系统的数据通信n虫孔寻径与存储转发的比较例例9-1n设多处理器计算机中两个结点之间的距离为10，一个处理器发出的消息包含100个片段（flit），假设每个时钟周期可以在连路上传递一个片段，问在存储转发和虫孔寻径两种方式下消息的传递最快分别需要花费多少时间？解：解：存储转发方式，消息传递时间为10*100=1000个时钟周期虫孔寻径方式，消息的第一个片段在网络上的传递时间为10个时钟周期，后99个片段增加99个时钟周期，共109个时钟周期。第二节 Cache与存储器的数据一致性n共享存储器多处理机系统的问题q访存冲突与数据一致性q数据多个副本之间的相同性数据的一致性类型n串行一致性n弱化一致性n处理机一致性n松散一致性数据一致性串行一致性串行一致性sequentialconsistencyn处理机P对于存储单元X的写操作之后进行的读操作，其间如果没有其它处理机对X进行写访问，则总是返回由P写入的数值。n在一个处理机P1对于单元X进行写操作之后，另一处理机P2对于单元X的读操作只要两者足够分离并且没有其它对于X的写操作发生，就能够返回P1写入的数值。n对于同一单元的写操作是顺序进行的，即两个处理机对于相同单元进行的写操作的顺序从任何处理机看都相同。如果数值1和2依次写入一个位置，处理机不可能先读得2，再读得1。数据一致性n弱化一致性弱化一致性weakconsistencyq程序通过同步操作强调一致性，使得在这些同步点上数据保持一致，而不要求数据随时都是一致的。n处理机一致性处理机一致性processorconsistencyq每个处理机发出的写操作被其它处理机看到的都保持原顺序，但两个不同处理机的写操作顺序可被其他处理机以不同的顺序看到。n松散一致性松散一致性releaseconsistencyq采用acquire-release同步操作使得数据保持一致，从而减少对硬件一致性处理的要求。数据一致性的实现n软件方法q编译分析q避免cache共享数据n总线监测q各cache设置监测部件nMESI协议n目录表法q全映射q有限目录q链式目录nSCI总线监测n所有cache不断监测总线上的每一个地址q总线使得写操作变成串行的qCache失效时需要确定数据块的位置nwriteinvalidateprotocolqinvalidatesothercopiesonawrite.q多次写操作时只需一次invalidatenwriteupdateorwritebroadcastprotocolqupdateallthecachedcopiesofadataitemwhenitiswrittenq读操作的命中率高cpu1cpu2cache1cache2MainmemoryMESI协议数据一致性的实现n目录表法q链式目录nSCIscalablecoherenceinterfaceIEEE1596-1992数据一致性对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块是共享的，但是数据字并没有共享数据一致性对cache性能的影响n一致性失效的例子q假定数据字x1和x2在同一个数据块中n数据块在P1和P2之间共享q假定以下事件序列第三节 多处理机的同步多线程并行程序设计面临的挑战n同步q给线程执行顺序施加约束的强化机制q影响程序的正确性和性能q可能导致死锁n通信q线程间的数据传递n负载平衡q线程之间执行时间的平衡n可伸缩性q线程数量增加的挑战Issues in MIMD multiprocessors architecturesn多线程程序运行中的问题nDataracesqUncertaintyofdataaccessordernSynchronizationqCostofdataaccessordernThreadstallsqForgettingunlockofmutexnDeadlocksqUnlimitedprocessorstallnFalsesharingqSlowdownprocessors并行程序设计面临的挑战n数据竞争q数据相关性险象q以下两个if语句的表达式可能都为真吗？数据竞争之二线程1线程2原始代码t=x;x=t+1;u=x;x=u+2;并行情况1t=x;/xis0x=t+1;/xis1u=x;x=u+2;/xis2并行情况2t=x;x=t+1;/xis1u=x/xis0x=u+2/xis2并行情况3t=x;/xis0x=t+1;/xis1u=x;x=u+2;/xis3数据竞争之三nif(list-next=NULL)ninsert(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共享存储器型多处理机q信号量nPV操作q互斥机制n锁n条件变量q屏障n栅栏n消息传递型多处理机q消息的发送和接收信号量n通过PV操作在线程间传递同步信息qP操作将一个变量减1n减后的变量小于0时线程被阻塞qV操作将一个变量加1n加后的变量大于或等于0时释放一个线程q变量初始化为0或1n互斥量MutexqPV操作都是原子的n不可中断的操作n用于保护共享的资源q生产者-消费者问题锁n两个基本的原子操作qAcquiren原子地等待锁的状态变成打开的状态n将打开的锁状态变成关闭的状态q这时该线程获得了锁qReleasen原子地将锁的状态从关闭状态变成打开的状态q这时线程释放了锁锁的类型n互斥量q用PV操作上锁和解锁q有阻塞q可以加上时间属性n递归锁q可以递归地获得的锁q用于递归程序n读写锁q多读单写锁n限制写操作只能由一个线程执行q用于对共享变量的读写操作n自旋锁q非阻塞的锁q用于多处理机系统和多核系统阻塞型锁机制的问题 n优先级的颠倒priorityinversionq当一个低优先级的线程占用了一个锁之后，需要同一个锁的高优先级线程就只能等待。n护航Convoyingq当一个线程拥有一个锁而被切换出去时其他的线程如果需要同一个锁的话都不能运行下去q其他线程都围着拥有锁的线程团团转n死锁Deadlockq锁的拥有和依赖关系形成一个环死锁及其解决n死锁的原因q对资源（锁）的访问是独占的q线程在已经持有一个资源时继续请求其他资源q所有线程都不放弃已经持有的资源q线程对资源的请求形成一个环n解决方法q复制需要独占访问的资源q按照一定的顺序获取资源n有序嵌套q无法获取其他资源时放弃已持有的资源q调用构件时避免使用锁条件变量n基于信号量机制q但操作不涉及存储的数值n等待的线程被阻塞q条件满足时才被唤醒q而不是循环等待q满足条件时唤醒其他协作的线程n三种操作q等待q发信号q广播栅栏与屏障n栅栏fenceq通过指令实现q保证存储器操作的一致性n保证所有在栅栏之前的访存操作完成n在此之前停下所有在栅栏之后的访存操作n屏障barrierq线程执行的协调机制q通过同步机制实现q运行的线程必须等待所有的线程都运行到指定同步点q然后各线程才继续下一步的运行q需要对到达的线程进行原子的计数操作同步操作中的硬件原语n原子交换atomicexchangeq实现锁n测试并设置test-and-setq实现锁n读取并加1fetch-and-incrementq实现屏障n读取并更新test-and-updateq实现PV操作原子交换原子交换n将一个寄存器的数值与一个存储器中的数值进行交换n难以在并行机中实现nitrequiresbothamemoryreadandawriteinasingle,uninterruptibleinstructionnhardwarecannotallowanyotheroperationsbetweenthereadandthewritewithoutdeadlockAB原子交换原子交换n解决方案q用两条指令实现n链接装载loadlinkedn条件存储storeconditionalq返回一个数值q表示其存储操作是否成功n两条指令按顺序执行q如果链接装载指令指定的存储单元在对应的条件存储指令执行之间被改变，则存储指令执行时失败。q如果处理机在这两条指令之间进行了上下文交换，则该条件存储指令也将失败。派生原语1.原子交换exchR4,0(R1)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派生原语2.读取并加1：try: ll R2,0(R1);load linkedaddi R2,R2,#1;incrementsc R2,0(R1);store conditionalbeqz R2,try;branch store failsR2BR2+1派生原语3.转锁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 lock wasnt 01L派生原语采用链接装载/条件存储实现转锁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一个用于锁住线程release派生原语屏障同步的实现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=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);/*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的值同步操作的性能问题nContentionforthelockq(2i+1)=n2+2nn锁变量访问的串行化q大大增加完成同步操作的时间n解决方案q增量资源n或分解资源n如散列表的分割q指数退避exponentialbackoffn访问等待时间以指数增加n防止活锁q队列锁n锁变量释放时通知下一个线程q组合树n树中每个结点组合k个线程的同步n将对一个变量的竞争按树形结构分散同步操作的性能问题n指数等待同步操作的性能问题n组合树structnode/*anodeinthecombiningtree*/intcounterlock;/*lockforthisnode*/intcount;/*counterforthisnode*/intparent;/*parentinthetree=0.P-1exceptforroot*/;structnodetree0.P1;/*thetreeofnodes*/intlocal_sense;/*privateperprocessor*/intrelease;/*globalreleaseflag*/同步操作的性能问题n组合树/*functiontoimplementbarrier*/barrier(intmynode,intlocal_sense)lock(treemynode.counterlock);/*protectcount*/treemynode.count=treemynode.count+1;/*incrementcount*/if(treemynode.count=k)/*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;barrier(mynode);第四节 并行程序设计模型n并行化程序设计方法q向量化n开发数据并行性q多线程化n开发线程级并行性n线程优化技术n线程险象检测技术n并行化程序设计的必要性q并行机的普及向量化与包装字16xbytes8xwords4xdwords2xqwords1xdqword2xdoublesMMX*SSESSE2SSE3向量化与包装字n标量运算128-bitRegistersA0B0C0+A1B1C1notusednotusednotusednotusednotusednotusednotusednotusednotusedfor (i=0;i=MAX;i+) ci=ai+bi;向量化与包装字n向量化运算128-bitRegistersA3A2B3B2C3C2+A1A0B1B0C1C0+for (i=0;i=MAX;i+) ci=ai+bi;基于编译的向量化处理器相关描述描述UseMac*Linux*Windows*GenerateinstructionsandoptimizeforIntelPentium4compatibleprocessorsincludingMMX,SSEandSSE2.WDoesnotapply-xW/QxWGenerateinstructionsandoptimizeforIntelprocessorswithSSE3capabilityincludingCoreDuo.TheseprocessorssupportSSE3aswellasMMX,SSEandSSE2.PVector-izationoccursbydefault-xP,-axP/QxP/QaxP向量化n可向量化的情况q大部分可计数内循环n不可向量化的情况q函数调用q条件转移q嵌套循环中的外循环q混合数据类型n不同封装格式q数组下标非均匀跨步q不可计数循环n循环变量上界不是常数表达式q包含不可向量化的运算n如超越函数多线程化n可重入性q共享变量的保护n访问顺序保护n互斥保护q临界区的保护n线程安全性q无死锁q无数据竞争多线程化n例1q编译器通常会将循环不变的读操作移到循环之外，这样读操作就只会进行一次，而不是每次迭代都执行一次。在多线程的情况下，这样做会产生什么问题？for(i=0;i100;i+0)intx;x=GlobalX；.intx=GlobalX；for(i=0;i100;i+0).多线程化n例2q指令调度时通常可以将一条load指令提到它前面的的一条与之不相关的store指令之前执行，在多线程的情况下，这样做会产生什么问题？多线程化n线程化的优点q创建速度较进程快q资源利用率高q便于数据共享n线程化的缺点q增加程序设计的复杂性q程序调试较难n数据竞争、同步、死锁多线程并行程序设计方法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线程中任意时刻只能运行一个纤程11122333333333344445555555555555536679838338891107611多线程并行程序设计方法n任务划分的例子q按颜色划分q按区域划分多线程并行程序设计方法n线程（数据流）划分的例子q建筑工程q砌墙、锯木、砌瓦、水电、粉刷q存在相关性q人力资源利用率问题多线程并行程序设计方法n数据划分的例子q批考卷n流水n并行q负载平衡问题多线程的执行环境n逻辑处理器n操作系统看到的处理器资源n硬件线程q支持多线程的处理器核中的一个CUq多核单线程处理器中的一个核q一个单核单线程的处理器芯片多线程的执行n硬件多线程q每个线程运行在不同逻辑处理器上q优先级相同q硬件的通信开销q真正的并行执行n软件多线程q运行在同一个逻辑处理器上qOS动态改变优先级q共享本地存储器n通信开销小n互斥容易解决多线程与多处理器的映像n操作系统实现q动态线程调度算法q无法考虑应用的特征n应用程序实现q需要由应用程序员优化调试q通过线程映像屏蔽向量n位向量n进程映像屏蔽向量的子集q需要动态获知逻辑处理器的数量q需要区分不同的硬件环境n超线程、多核、多芯片多线程并行程序设计中的问题n负载平衡q挑战：线程执行时间的不确定性n通过动态线程调度解决n线程的开销q创建、删除、同步、通信n适度的并行n并行颗粒度n死锁nCacheping-pong多线程并行程序设计方法n将独立的循环程序变成多线程q并行执行的线程可能改变相对执行的进度或顺序q要求不存在循环带来的相关性n将独立的程序段变成多线程q变串行为并行q纤程（fiber）n执行一个任务n创建开销小n应用层可控Win32线程APInCreateThreadnMyThreadStartnCloseHandlenWaitForSingleObjectnWaitForMultipleObjectsnCreateMutexnReleaseMutexnInitializeCriticalSectionnDeleteCriticalSectionnEnterCriticalSectionnLeaveCriticalSectionnCreateSemaphorenReleaseSemaphoreWin32线程APInConvertThreadToFibernGetFiberDatanCreateFibernfiberProcnSwitchToFibernDeleteFibernGetCurrentFiberExamplen#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, 0, helloFunc, NULL, 0, NULL );n WaitForMultipleObjects(numThreads, hThread,nTRUE, INFINITE);nOpenMPn编写可移植的多线程应用程序的APIq提供与平台无关的并行编程机制n编译指令pragman编译指示符directiven函数调用n环境变量q循环程序多线程化n支持多线程间的同步和局部数据变量n采用fork-join的执行模式n程序员不需要对线程的创建和删除进行编程n程序员不需要对同步操作进行详细编程q适用于共享存储器的并行计算机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#pragmaompconstruct clause clause#pragma omp parallelThread1Thread2Thread3#pragmaompparallelblockParallel 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,butprivatetoavoid/raceconditionsfromparallelexecutionsum=0;#pragmaompparallelforreduction(+:sum)for(i=0;i100;i+)sum+=arrayi;Parallel section#pragmaompparallelsections#pragmaompsectionphase1();#pragmaompsectionphase2();#pragmaompsectionphase3();SerialParallelOpenMP的线程调度算法n静态q将循环程序的各个迭代划分成相等大小的迭代束n或者近似相等大小的迭代束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并行程序的性能优化n并行程序的优化q分析程序的调用关系n分析程序的关键调用路径q分析程序中的热点n执行时间最长的函数q分析线程负载平衡q分析关键路径关键路径n多线程程序包含多个执行流q执行流在同步点相关n关键路径是最长的执行流Thread1Thread2Thread3T0T1T2T3T4T5T6T7T8T9T10T11T12T13T14T15AcquireLThreads2&3DoneAcquireLWaitforThreads2&3ReleaseLAcquirelockLWaitforLReleaseLWaitforLThread2terminatesThread3terminatesThread1terminates线程的状态n巡航Cruiseq线程的运行不受干扰n开销Overheadq线程操作开销n阻塞Blockingq线程等待外部事件n影响Impactq线程阻碍了其他线程的执行线程状态分析的例子n沿着关键路径分析线程的状态CruisetimeOverheadBlockingtimeImpacttimeCategorization shown for a system configuration with 2 processorsThreadInteraction015510TimeThread1Thread2Thread3T0T1T2T3T4T5T6T7T8T9T10T11T12T13T14T15AcquirelockLWaitforThreads2&3WaitforLReleaseLWaitforLReleaseLAcquireLAcquireLThreads2&3Done线程并行化状况n空闲Idleq没有线程n串行Serialq单个线程n偏少Under-subscribedq线程数少于核数n并行Parallelq线程数等于核数n偏多Oversubscribedq线程数多于核数线程并行状况分析例子Thread1Thread2Thread3T0T1T2T3T4T5T6T7T8T9T10T11T12T13T14T15AcquirelockLWaitforThreads2&3WaitforLReleaseLWaitforLReleaseLAcquireLAcquireLThreads2&3DoneIdleSerialParallelUnder-subscribedOver-subscribedConcurrencyLevel015510TimeVTunenIntel的性能分析工具q支持代码优化q采样收集系统性能数据q显示性能数据的时序图q显示函数调用图q采用统计方法发现程序中的热点n嵌入的其他工具qThreadcheckerqThreadprofilerThread checkern线程化软件的调试工具q通过分析手段发现bugn数据相关性分析q快速定位bugn对线程的共享数据进行分析q检测数据竞争和线程死锁nhttp:/www.intel.com/support/performancetools/sb/CS-009681.htmThread profilern发现多线程的性能问题q负载不平衡q同步开销q关键路径分析Thread profiler的视图n关键路径视图CriticalPathViewqShowsbreakdownofthecriticalpathn轮廓视图ProfileViewqShowsthebreakdownofselectedcriticalpathsq显示并行程度、线程和对象n时间轴视图TimelineViewq显示线程行为和关键路径的转换n源代码视图SourceViewq显示源程序代码结束语结束语谢谢大家聆听！谢谢大家聆听！97