并行计算机系统.ppt

第九章 并行计算机系统的程序设计,第一节 并行计算机系统的数据通信第二节 Cache与存储器的数据一致性第三节 多处理机的同步第四节 并行程序设计模型,第一节 并行计算机系统的数据通信,数据包寻径信息序号数据内容校验位协议号时间戳,存储转发store-and-forward电路交换circuit switching虚拟切换virtual cut-through虫孔寻径wormhole,MPI,Message passing interface 用于多处理器系统和集群系统进程通过调用库函数进行消息收发通信支持异构计算标准的消息传递函数库点到点通信函数群集通信函数不是一种语言消息传递机制点对点通信群集通信,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等待发送/接收完成MPI_TEST测试发送/接收是否完成,MPI的聚合通信机制,同步方式同步发送和阻塞接收所有进程都完成调用时返回（屏障同步）特异方式 distinguished一对多通信散播广播多对一通信归约求最大值、最小值、总和、乘积等收集,MPI群集通信函数例子,MPI_Bcast一对多广播同样的消息MPI_Gather多对一收集各个进程的消息MPI_Allgather全局收集MPI_Scatter一对多散播不同的消息MPI_Alltoall每个进程给所有其他进程发送一个消息每个进程从所有其他进程接收一个消息MPI_Reduce多对一归约MPI_Reduce_scatter归约并散播MPI_Barrier屏障同步,第一节 并行计算机系统的数据通信,1.存储转发store-and-forward问题：延迟大，缓存多,第一节 并行计算机系统的数据通信,2.电路交换circuit switching问题：冲突多，利用率低,第一节 并行计算机系统的数据通信,3.虚拟切换virtual cut-through问题：缓存多,flits,第一节 并行计算机系统的数据通信,4.虫孔寻径wormhole问题：死锁和活锁,第一节 并行计算机系统的数据通信,虫孔寻径与存储转发的比较,例9-1,设多处理器计算机中两个结点之间的距离为10，一个处理器发出的消息包含100个片段（flit），假设每个时钟周期可以在连路上传递一个片段，问在存储转发和虫孔寻径两种方式下消息的传递最快分别需要花费多少时间？,解：存储转发方式，消息传递时间为10*100=1000个时钟周期虫孔寻径方式，消息的第一个片段在网络上的传递时间为10个时钟周期，后99个片段增加99个时钟周期，共109个时钟周期。,第二节 Cache与存储器的数据一致性,共享存储器多处理机系统的问题访存冲突与数据一致性数据多个副本之间的相同性,数据的一致性类型,串行一致性弱化一致性处理机一致性松散一致性,数据一致性,串行一致性sequential consistency处理机P对于存储单元X的写操作之后进行的读操作，其间如果没有其它处理机对X进行写访问，则总是返回由P写入的数值。在一个处理机P1对于单元X进行写操作之后，另一处理机P2对于单元X的读操作只要两者足够分离并且没有其它对于X的写操作发生，就能够返回P1写入的数值。对于同一单元的写操作是顺序进行的，即两个处理机对于相同单元进行的写操作的顺序从任何处理机看都相同。如果数值1和2依次写入一个位置，处理机不可能先读得2，再读得1。,数据一致性,弱化一致性weak consistency程序通过同步操作强调一致性，使得在这些同步点上数据保持一致，而不要求数据随时都是一致的。处理机一致性processor consistency每个处理机发出的写操作被其它处理机看到的都保持原顺序，但两个不同处理机的写操作顺序可被其他处理机以不同的顺序看到。松散一致性release consistency采用acquire-release同步操作使得数据保持一致，从而减少对硬件一致性处理的要求。,数据一致性的实现,软件方法编译分析避免cache共享数据总线监测各cache设置监测部件MESI协议目录表法全映射有限目录链式目录SCI,总线监测,所有cache不断监测总线上的每一个地址总线使得写操作变成串行的Cache 失效时需要确定数据块的位置write invalidate protocol invalidates other copies on a write.多次写操作时只需一次invalidatewrite update or write broadcast protocolupdate all the cached copies of a data item when it is written读操作的命中率高,cpu1,cpu2,cache1,cache2,Mainmemory,MESI协议,数据一致性的实现,目录表法链式目录SCI,scalable coherence interface IEEE 1596-1992,数据一致性对cache性能的影响,影响cache性能的因素单个处理器cache失效的数据传输数据通信引起的传输导致invalidations和后继cache失效一致性失效处理机数量Cache容量块大小,数据一致性对cache性能的影响,一致性失效真共享失效true sharing misses 由cache一致性操作的通信引起对共享数据的第一个写操作引起invalidation伪共享失效false sharing misses 由每个cache块只有一个有效位引起一个块中其他数据的写操作引起cache块读操作的失效Cache块是共享的，但是数据字并没有共享,数据一致性对cache性能的影响,一致性失效的例子假定数据字x1和x2在同一个数据块中数据块在 P1和P2之间共享假定以下事件序列,第三节 多处理机的同步,多线程并行程序设计面临的挑战同步给线程执行顺序施加约束的强化机制影响程序的正确性和性能可能导致死锁通信线程间的数据传递负载平衡线程之间执行时间的平衡可伸缩性线程数量增加的挑战,Issues in MIMD multiprocessors architectures,多线程程序运行中的问题Data racesUncertainty of data access orderSynchronizationCost of data access orderThread stallsForgetting unlock of mutexDead locksUnlimited processor stallFalse sharingSlowdown processors,并行程序设计面临的挑战,数据竞争数据相关性险象以下两个if语句的表达式可能都为真吗？,数据竞争之二,数据竞争之三,if(list-next=NULL)insert(list-next,node1),if(list-next=NULL)insert(list-next,node2),node2,node1,数据竞争的解决,变量局部化将变量改为线程局部的如将全局和分解为部分和用临界区控制共享变量的访问通过锁、信号量等实现每个共享数据用一把锁互斥机制,同步机制,临界区critical section访问共享数据的程序段在某段时间内仅允许一定数目的线程访问的一段代码大多数情况下一次只有一个线程能够进入同一个临界区可采用互斥机制实现,同步机制,共享存储器型多处理机信号量PV操作互斥机制锁条件变量屏障栅栏消息传递型多处理机消息的发送和接收,信号量,通过PV操作在线程间传递同步信息P操作将一个变量减1减后的变量小于0时线程被阻塞V操作将一个变量加1加后的变量大于或等于0时释放一个线程变量初始化为0或1互斥量MutexPV操作都是原子的不可中断的操作用于保护共享的资源生产者-消费者问题,锁,两个基本的原子操作Acquire原子地等待锁的状态变成打开的状态将打开的锁状态变成关闭的状态这时该线程获得了锁Release原子地将锁的状态从关闭状态变成打开的状态这时线程释放了锁,锁的类型,互斥量用PV操作上锁和解锁有阻塞可以加上时间属性递归锁可以递归地获得的锁用于递归程序读写锁多读单写锁限制写操作只能由一个线程执行 用于对共享变量的读写操作自旋锁非阻塞的锁用于多处理机系统和多核系统,阻塞型锁机制的问题,优先级的颠倒priority inversion当一个低优先级的线程占用了一个锁之后，需要同一个锁的高优先级线程就只能等待。护航Convoying当一个线程拥有一个锁而被切换出去时其他的线程如果需要同一个锁的话都不能运行下去其他线程都围着拥有锁的线程团团转死锁Deadlock锁的拥有和依赖关系形成一个环,死锁及其解决,死锁的原因对资源（锁）的访问是独占的线程在已经持有一个资源时继续请求其他资源所有线程都不放弃已经持有的资源线程对资源的请求形成一个环解决方法复制需要独占访问的资源 按照一定的顺序获取资源有序嵌套无法获取其他资源时放弃已持有的资源 调用构件时避免使用锁,条件变量,基于信号量机制但操作不涉及存储的数值等待的线程被阻塞条件满足时才被唤醒而不是循环等待满足条件时唤醒其他协作的线程三种操作等待发信号广播,栅栏与屏障,栅栏fence通过指令实现保证存储器操作的一致性保证所有在栅栏之前的访存操作完成在此之前停下所有在栅栏之后的访存操作屏障barrier线程执行的协调机制通过同步机制实现运行的线程必须等待所有的线程都运行到指定同步点然后各线程才继续下一步的运行需要对到达的线程进行原子的计数操作,同步操作中的硬件原语,原子交换atomic exchange实现锁测试并设置test-and-set实现锁读取并加1fetch-and-increment实现屏障读取并更新test-and-update实现PV操作,原子交换,将一个寄存器的数值与一个存储器中的数值进行交换难以在并行机中实现it requires both a memory read and a write in a single,uninterruptible instructionhardware cannot allow any other operations between the read and the write without deadlock,A,B,原子交换,解决方案用两条指令实现链接装载load linked条件存储store conditional返回一个数值表示其存储操作是否成功两条指令按顺序执行如果链接装载指令指定的存储单元在对应的条件存储指令执行之间被改变，则存储指令执行时失败。如果处理机在这两条指令之间进行了上下文交换，则该条件存储指令也将失败。,派生原语,1.原子交换 exch R4,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,宏指令,macroinstruction,R3,B,R4,R2,派生原语,2.读取并加1：try:ll R2,0(R1);load linkedaddi R2,R2,#1;incrementsc R2,0(R1);store conditionalbeqz R2,try;branch store fails,R2,B,R2,+1,派生原语,3.转锁spin lock处理机用循环方法试图得到的锁没有cache一致性机制时li R2,#1;load immediatelockit:exch R2,0(R1);atomic exchangebnez R2,lockit;already locked?有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,1,L,派生原语,采用链接装载/条件存储实现转锁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 failes,1,B,R2,派生原语,屏障同步barrier强制所有的线程等待直到所有的线程都到达屏障时释放所有的线程用一个计数器对到达的线程计数(Gather阶段)用一个信号释放所有的线程(release 阶段)用两个自旋锁实现一个用于保护计数器一个用于锁住线程,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*/,派生原语,问题屏障可能循环使用从屏障离开的线程可能再次进入屏障一个线程可能在另一个线程离开屏障之前又进入屏障代码的bug,release,派生原语,解决方案对离开的线程计数不允许线程在其他线程都离开上一个屏障之前又进入屏障从而又初始化屏障传感反相屏障sense-reversing使用线程局部变量初始化为1交替地等待1和0,release,派生原语,屏障同步的实现传感反相屏障local_sense=!local_sense;/*toggle local_sense*/lock(counterlock);/*ensure update atomic*/count=count+1;/*count arrivals*/if(count=total)/*all arrived*/count=0;/*reset counter*/release=local_sense;/*release processes*/unlock(counterlock);/*unlock*/spin(release=local_sense);/*wait for signal*/,第一个到达屏障的线程并不改变release的值,同步操作的性能问题,Contention for the lock(2i+1)=n2+2n锁变量访问的串行化大大增加完成同步操作的时间解决方案增量资源或分解资源如散列表的分割指数退避exponential backoff访问等待时间以指数增加防止活锁队列锁锁变量释放时通知下一个线程组合树树中每个结点组合k个线程的同步将对一个变量的竞争按树形结构分散,同步操作的性能问题,指数等待,同步操作的性能问题,组合树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*/int local_sense;/*private per processor*/int release;/*global release flag*/,同步操作的性能问题,组合树/*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 mynode*/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(mynode);,第四节 并行程序设计模型,并行化程序设计方法向量化开发数据并行性多线程化开发线程级并行性线程优化技术线程险象检测技术并行化程序设计的必要性并行机的普及,向量化与包装字,16x bytes,8x words,4x dwords,2x qwords,1x dqword,2x doubles,MMX*,SSE,SSE2SSE3,向量化与包装字,标量运算,128-bit Registers,A0,B0,C0,+,+,+,+,A1,B1,C1,not used,not used,not used,not used,not used,not used,not used,not used,not used,for(i=0;i=MAX;i+)ci=ai+bi;,向量化与包装字,向量化运算,128-bit Registers,A3,A2,B3,B2,C3,C2,+,+,A1,A0,B1,B0,C1,C0,+,+,for(i=0;i=MAX;i+)ci=ai+bi;,基于编译的向量化处理器相关,向量化,可向量化的情况大部分可计数内循环不可向量化的情况函数调用条件转移嵌套循环中的外循环混合数据类型不同封装格式数组下标非均匀跨步不可计数循环循环变量上界不是常数表达式包含不可向量化的运算如超越函数,多线程化,可重入性共享变量的保护访问顺序保护互斥保护临界区的保护线程安全性无死锁无数据竞争,多线程化,例1编译器通常会将循环不变的读操作移到循环之外，这样读操作就只会进行一次，而不是每次迭代都执行一次。在多线程的情况下，这样做会产生什么问题？,for(i=0;i100;i+0)int x;x=GlobalX；.,int x=GlobalX；for(i=0;i100;i+0).,多线程化,例2指令调度时通常可以将一条load指令提到它前面的的一条与之不相关的store指令之前执行，在多线程的情况下，这样做会产生什么问题？,多线程化,线程化的优点创建速度较进程快资源利用率高便于数据共享线程化的缺点增加程序设计的复杂性程序调试较难数据竞争、同步、死锁,多线程并行程序设计方法,任务划分将一个任务划分成多个并行子任务使得处理器负载平衡数据划分将数据对象划分成多个并行子集提高访存的效率以及cache的命中率 数据流划分根据数据处理的过程划分一个子任务的输出是另一个子任务的输入划分的目标负载平衡降低调度开销、通信开销和同步开销,任务与线程,任务task应用级的计算单位单任务线程为每个任务动态创建和终止创建和终止开销问题大量线程时的开销线程池预先创建的固定数量的线程与处理器数量匹配可完成多个任务应用程序中动态任务分配和调度线程中任意时刻只能运行一个纤程,多线程并行程序设计方法,任务划分的例子按颜色划分按区域划分,多线程并行程序设计方法,线程（数据流）划分的例子建筑工程砌墙、锯木、砌瓦、水电、粉刷存在相关性人力资源利用率问题,多线程并行程序设计方法,数据划分的例子批考卷流水并行负载平衡问题,多线程的执行环境,逻辑处理器操作系统看到的处理器资源硬件线程支持多线程的处理器核中的一个CU多核单线程处理器中的一个核一个单核单线程的处理器芯片,多线程的执行,硬件多线程每个线程运行在不同逻辑处理器上优先级相同硬件的通信开销真正的并行执行软件多线程运行在同一个逻辑处理器上OS动态改变优先级共享本地存储器通信开销小互斥容易解决,多线程与多处理器的映像,操作系统实现动态线程调度算法无法考虑应用的特征应用程序实现需要由应用程序员优化调试通过线程映像屏蔽向量位向量进程映像屏蔽向量的子集需要动态获知逻辑处理器的数量需要区分不同的硬件环境超线程、多核、多芯片,多线程并行程序设计中的问题,负载平衡挑战：线程执行时间的不确定性通过动态线程调度解决线程的开销创建、删除、同步、通信适度的并行并行颗粒度死锁Cache ping-pong,多线程并行程序设计方法,将独立的循环程序变成多线程并行执行的线程可能改变相对执行的进度或顺序要求不存在循环带来的相关性将独立的程序段变成多线程变串行为并行纤程（fiber）执行一个任务创建开销小应用层可控,Win32线程API,CreateThreadMyThreadStartCloseHandleWaitForSingleObjectWaitForMultipleObjectsCreateMutexReleaseMutexInitializeCriticalSectionDeleteCriticalSectionEnterCriticalSectionLeaveCriticalSectionCreateSemaphoreReleaseSemaphore,Win32线程API,ConvertThreadToFiber GetFiberData CreateFiber fiberProc SwitchToFiber DeleteFiber GetCurrentFiber,Example,#include#include const int numThreads=4;DWORD WINAPI helloFunc(LPVOID arg)printf(“Hello Threadn”);return 0;main()HANDLE hThreadnumThreads;for(int i=0;i numThreads;i+)hThreadi=CreateThread(NULL,0,helloFunc,NULL,0,NULL);WaitForMultipleObjects(numThreads,hThread,TRUE,INFINITE);,OpenMP,编写可移植的多线程应用程序的API提供与平台无关的并行编程机制编译指令 pragma编译指示符 directive函数调用环境变量循环程序多线程化支持多线程间的同步和局部数据变量采用fork-join的执行模式程序员不需要对线程的创建和删除进行编程程序员不需要对同步操作进行详细编程适用于共享存储器的并行计算机,#pragma omp parallel for for(i=0;iMAX;i+)Ai=c*Ai+Bi;,线程,fork-join的执行模式,主线程 分裂出一组线程并行性逐渐增加串行程序中嵌入并行性,Parallel Regions,Master Thread,OpenMP的编译指令,parallelforprivatesinglemasterreductionschedulesectionifbarrieratomicreductionchunk-size,#pragma omp construct clause clause,#pragma omp parallel block,Parallel 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 reduction,sum=0;for(i=0;i 100;i+)sum+=arrayi;/this variable 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();#pragma omp section phase3();,Serial,Parallel,OpenMP的线程调度算法,静态将循环程序的各个迭代划分成相等大小的迭代束或者近似相等大小的迭代束每个迭代束包含大致相等的迭代数量动态使用内部的工作队列将迭代束分配给各个线程线程空闲时从工作队列中获取下一个迭代束运行时迭代束的大小先比较大然后逐渐缩小在开始时减少调度时间，然后考虑负载平衡指导性的使用环境变量以指定三种调度方式中的哪一个用于调度,Parallel for schedule,Float x1000,y1000;#pragma omp parallel for schedule(dynamic,8)for(k=0;k1000;k+)xk=cos(a)*xk+sin(a)*yk,并行程序的性能优化,并行程序的优化分析程序的调用关系分析程序的关键调用路径分析程序中的热点执行时间最长的函数分析线程负载平衡分析关键路径,关键路径,多线程程序包含多个执行流执行流在同步点相关关键路径是最长的执行流,Acquire L,Threads 2&3 Done,Acquire L,Wait for Threads 2&3,Release L,Acquire lock L,Wait for L,Release L,Wait for L,Thread 2 terminates,Thread 3 terminates,Thread 1 terminates,线程的状态,巡航Cruise线程的运行不受干扰开销Overhead线程操作开销阻塞Blocking线程等待外部事件影响Impact线程阻碍了其他线程的执行,线程状态分析的例子,沿着关键路径分析线程的状态,Categorization shown for a system configuration with 2 processors,线程并行化状况,空闲Idle没有线程串行Serial单个线程偏少Under-subscribed线程数少于核数并行Parallel线程数等于核数偏多Oversubscribed线程数多于核数,线程并行状况分析例子,VTune,Intel的性能分析工具支持代码优化采样收集系统性能数据显示性能数据的时序图显示函数调用图采用统计方法发现程序中的热点嵌入的其他工具Thread checker Thread profiler,Thread checker,线程化软件的调试工具通过分析手段发现bug数据相关性分析快速定位bug对线程的共享数据进行分析检测数据竞争和线程死锁,Thread profiler,发现多线程的性能问题负载不平衡同步开销关键路径分析,Thread profiler的视图,关键路径视图Critical Path ViewShows breakdown of the critical path轮廓视图Profile ViewShows the breakdown of selected critical paths显示并行程度、线程和对象时间轴视图Timeline View显示线程行为和关键路径的转换源代码视图Source View显示源程序代码,