并行计算机系统

1、第九章 并行计算机系统的程序设计第一节 并行计算机系统的数据通信第二节 Cache与存储器的数据一致性第三节 多处理机的同步第四节 并行程序设计模型1第一节 并行计算机系统的数据通信数据包寻径信息序号数据内容校验位协议号时间戳存储转发store-and-forward电路交换circuit switching虚拟切换virtual cut-through虫孔寻径wormhole2MPIMessage passing interface 用于多处理器系统和集群系统进程通过调用库函数进行消息收发通信支持异构计算标准的消息传递函数库点到点通信函数群集通信函数不是一种语言消息传递机制点对点通信群集通信

2、3MPI的点对点通信机制发送操作模型标准的同步或缓存的（取决于实现）缓存的把发送缓存复制到缓存后返回同步的缓存被接收方读取后返回就绪的在接收方就绪时启动发送（启动发送后即返回）发送/接收操作模型阻塞的等到消息复制到缓存后返回非阻塞的启动发送/接收后即返回4MPI点对点通信函数例子MPI_INIT启动MPI计算MPI_FINALIZE结束MPI计算MPI_COMM_SIZE确定进程数MPI_COMM_RANK确定自己的进程号MPI_SEND标准地发送一条消息MPI_BSEND发送一条缓存的消息MPI_SSEND发送一条同步的消息MPI_RESEND发送一条就绪的消息MPI_ISEND标准地发送一

3、条非阻塞消息MPI_IBSEND发送一条缓存的非阻塞消息MPI_ISSEND发送一条同步的非阻塞消息MPI_RESEND发送一条就绪的非阻塞消息MPI_RECV标准地接收一条消息MPI_IRECV非阻塞地接收一条消息MPI_BCAST广播一条消息MPI_WAIT等待发送/接收完成MPI_TEST测试发送/接收是否完成5MPI的聚合通信机制同步方式同步发送和阻塞接收所有进程都完成调用时返回（屏障同步）特异方式 distinguished一对多通信散播广播多对一通信归约求最大值、最小值、总和、乘积等收集6MPI群集通信函数例子MPI_Bcast一对多广播同样的消息MPI_Gather多对一收集各个

4、进程的消息MPI_Allgather全局收集MPI_Scatter一对多散播不同的消息MPI_Alltoall每个进程给所有其他进程发送一个消息每个进程从所有其他进程接收一个消息MPI_Reduce多对一归约MPI_Reduce_scatter归约并散播MPI_Barrier屏障同步7第一节 并行计算机系统的数据通信1. 存储转发store-and-forward问题：延迟大，缓存多8第一节 并行计算机系统的数据通信2. 电路交换circuit switching问题：冲突多，利用率低9第一节 并行计算机系统的数据通信3. 虚拟切换virtual cut-through问题：缓存多flits1

5、0第一节 并行计算机系统的数据通信4. 虫孔寻径wormhole问题：死锁和活锁11第一节 并行计算机系统的数据通信虫孔寻径与存储转发的比较12例9-1设多处理器计算机中两个结点之间的距离为10，一个处理器发出的消息包含100个片段（flit），假设每个时钟周期可以在连路上传递一个片段，问在存储转发和虫孔寻径两种方式下消息的传递最快分别需要花费多少时间？解：存储转发方式，消息传递时间为10*100=1000个时钟周期虫孔寻径方式，消息的第一个片段在网络上的传递时间为10个时钟周期，后99个片段增加99个时钟周期，共109个时钟周期。13第二节 Cache与存储器的数据一致性共享存储器多处理机系

6、统的问题访存冲突与数据一致性数据多个副本之间的相同性14数据的一致性类型串行一致性弱化一致性处理机一致性松散一致性15数据一致性串行一致性sequential consistency处理机P对于存储单元X的写操作之后进行的读操作，其间如果没有其它处理机对X进行写访问，则总是返回由P写入的数值。在一个处理机P1对于单元X进行写操作之后，另一处理机P2对于单元X的读操作只要两者足够分离并且没有其它对于X的写操作发生，就能够返回P1写入的数值。对于同一单元的写操作是顺序进行的，即两个处理机对于相同单元进行的写操作的顺序从任何处理机看都相同。如果数值1和2依次写入一个位置，处理机不可能先读得2，再读得

7、1。16数据一致性弱化一致性weak consistency程序通过同步操作强调一致性，使得在这些同步点上数据保持一致，而不要求数据随时都是一致的。处理机一致性processor consistency每个处理机发出的写操作被其它处理机看到的都保持原顺序，但两个不同处理机的写操作顺序可被其他处理机以不同的顺序看到。松散一致性release consistency采用acquire-release同步操作使得数据保持一致，从而减少对硬件一致性处理的要求。17数据一致性的实现软件方法编译分析避免cache共享数据总线监测各cache设置监测部件MESI协议目录表法全映射有限目录链式目录SCI18总

8、线监测所有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读操作的命中率高cpu1cpu2cache1cache2Mainmemory19MESI协议20数据一致性的实现目录表法链式

9、目录SCIscalable coherence interface IEEE 1596-199221数据一致性对cache性能的影响影响cache性能的因素单个处理器cache失效的数据传输数据通信引起的传输导致invalidations和后继cache失效一致性失效处理机数量Cache容量块大小22数据一致性对cache性能的影响一致性失效真共享失效true sharing misses 由cache一致性操作的通信引起对共享数据的第一个写操作引起invalidation伪共享失效false sharing misses 由每个cache块只有一个有效位引起一个块中其他数据的写操作引起cac

10、he块读操作的失效Cache块是共享的，但是数据字并没有共享23数据一致性对cache性能的影响一致性失效的例子假定数据字x1和x2在同一个数据块中数据块在 P1和P2之间共享假定以下事件序列24第三节 多处理机的同步多线程并行程序设计面临的挑战同步给线程执行顺序施加约束的强化机制影响程序的正确性和性能可能导致死锁通信线程间的数据传递负载平衡线程之间执行时间的平衡可伸缩性线程数量增加的挑战25Issues in MIMD multiprocessors architectures多线程程序运行中的问题Data racesUncertainty of data access orderSynch

11、ronizationCost of data access orderThread stallsForgetting unlock of mutexDead locksUnlimited processor stallFalse sharingSlowdown processors26并行程序设计面临的挑战数据竞争数据相关性险象以下两个if语句的表达式可能都为真吗？27数据竞争之二28数据竞争之三if (list-next = NULL) insert(list-next, node1)if (list-next = NULL) insert(list-next, node2)node2nod

12、e129数据竞争的解决变量局部化将变量改为线程局部的如将全局和分解为部分和用临界区控制共享变量的访问通过锁、信号量等实现每个共享数据用一把锁互斥机制30同步机制临界区critical section访问共享数据的程序段在某段时间内仅允许一定数目的线程访问的一段代码大多数情况下一次只有一个线程能够进入同一个临界区可采用互斥机制实现31同步机制共享存储器型多处理机信号量PV操作互斥机制锁条件变量屏障栅栏消息传递型多处理机消息的发送和接收32信号量通过PV操作在线程间传递同步信息P操作将一个变量减1减后的变量小于0时线程被阻塞V操作将一个变量加1加后的变量大于或等于0时释放一个线程变量初始化为0或1

13、互斥量MutexPV操作都是原子的不可中断的操作用于保护共享的资源生产者-消费者问题33锁两个基本的原子操作Acquire原子地等待锁的状态变成打开的状态将打开的锁状态变成关闭的状态这时该线程获得了锁Release原子地将锁的状态从关闭状态变成打开的状态这时线程释放了锁34锁的类型互斥量用PV操作上锁和解锁有阻塞可以加上时间属性递归锁可以递归地获得的锁用于递归程序读写锁多读单写锁限制写操作只能由一个线程执行 用于对共享变量的读写操作自旋锁非阻塞的锁用于多处理机系统和多核系统35阻塞型锁机制的问题 优先级的颠倒priority inversion当一个低优先级的线程占用了一个锁之后，需要同一个锁

14、的高优先级线程就只能等待。护航Convoying当一个线程拥有一个锁而被切换出去时其他的线程如果需要同一个锁的话都不能运行下去其他线程都围着拥有锁的线程团团转死锁Deadlock锁的拥有和依赖关系形成一个环36死锁及其解决死锁的原因对资源（锁）的访问是独占的线程在已经持有一个资源时继续请求其他资源所有线程都不放弃已经持有的资源线程对资源的请求形成一个环解决方法复制需要独占访问的资源 按照一定的顺序获取资源有序嵌套无法获取其他资源时放弃已持有的资源 调用构件时避免使用锁37条件变量基于信号量机制但操作不涉及存储的数值等待的线程被阻塞条件满足时才被唤醒而不是循环等待满足条件时唤醒其他协作的线程三种

15、操作等待发信号广播38栅栏与屏障栅栏fence通过指令实现保证存储器操作的一致性保证所有在栅栏之前的访存操作完成在此之前停下所有在栅栏之后的访存操作屏障barrier线程执行的协调机制通过同步机制实现运行的线程必须等待所有的线程都运行到指定同步点然后各线程才继续下一步的运行需要对到达的线程进行原子的计数操作39同步操作中的硬件原语原子交换atomic exchange实现锁测试并设置test-and-set实现锁读取并加1fetch-and-increment实现屏障读取并更新test-and-update实现PV操作40原子交换将一个寄存器的数值与一个存储器中的数值进行交换难以在并行机中实现

16、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 deadlockAB41原子交换解决方案用两条指令实现链接装载load linked条件存储store conditional返回一个数值表示其存储操作是否成功两条指令按顺序执行如果链接装载指令指定的存储单元在对应的条件存储指令执行之间被改变，则存储指令执行时失败。如果

17、处理机在这两条指令之间进行了上下文交换，则该条件存储指令也将失败。42派生原语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宏指令macroinstructionR3BR4R243派生原语2. 读取并加1：try: ll R2,0(R1);load linkedaddi R2,R2,

18、#1;incrementsc R2,0(R1);store conditionalbeqz R2,try;branch store failsR2BR2+144派生原语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

19、;load locked valueexch R2,0(R1);swapbnez R2,lockit;branch if lock wasnt 01L45派生原语采用链接装载/条件存储实现转锁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 failes1BR246派生原语屏障同步barrier强制所有的线程等待直到所有的线程都到达屏障时释放所有的线程用一个计数器对到达的线程计数

20、(Gather阶段)用一个信号释放所有的线程 (release 阶段)用两个自旋锁实现一个用于保护计数器一个用于锁住线程release47派生原语屏障同步的实现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

21、; /* reset counter */ release=1;/* release processes */else /* more to come */ spin(release=1);/* wait for arrivals */48派生原语问题屏障可能循环使用从屏障离开的线程可能再次进入屏障一个线程可能在另一个线程离开屏障之前又进入屏障代码的bugrelease49派生原语解决方案对离开的线程计数不允许线程在其他线程都离开上一个屏障之前又进入屏障从而又初始化屏障传感反相屏障sense-reversing使用线程局部变量初始化为1交替地等待1和0release50派生原语屏障同步的实现传

22、感反相屏障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_sens

23、e); /*wait for signal*/第一个到达屏障的线程并不改变release的值51同步操作的性能问题Contention for the lock(2i+1) = n2+2n锁变量访问的串行化大大增加完成同步操作的时间解决方案增量资源或分解资源如散列表的分割指数退避exponential backoff访问等待时间以指数增加防止活锁队列锁锁变量释放时通知下一个线程组合树树中每个结点组合k个线程的同步将对一个变量的竞争按树形结构分散52同步操作的性能问题指数等待53同步操作的性能问题组合树struct node /* a node in the combining tree */

24、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 */54同步操作的性能问题组合树/* function to i

25、mplement 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 */ elsereleas

26、e = 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);55第四节 并行程序设计模型并行化程序设计方法向量化开发数据并行性多线程化开发线程级并行性线程优化技术线程险象

27、检测技术并行化程序设计的必要性并行机的普及56向量化与包装字16x bytes8x words4x dwords2x qwords1x dqword2x doublesMMX*SSESSE2SSE357向量化与包装字标量运算128-bit RegistersA0B0C0+A1B1C1not usednot usednot usednot usednot usednot usednot usednot usednot usedfor (i=0;i=MAX;i+) ci=ai+bi;58向量化与包装字向量化运算128-bit RegistersA3A2B3B2C3C2+A1A0B1B0C1C0+f

28、or (i=0;i=MAX;i+) ci=ai+bi;59基于编译的向量化处理器相关描述UseMac*Linux*Windows*Generate instructions and optimize for Intel Pentium 4 compatible processors including MMX, SSE and SSE2. WDoes not apply-xW/QxWGenerate instructions and optimize for Intel processors with SSE3 capability including Core Duo. These proc

29、essors support SSE3 as well as MMX,SSE and SSE2. PVector-ization occurs by default-xP,-axP/QxP/QaxP60向量化可向量化的情况大部分可计数内循环不可向量化的情况函数调用条件转移嵌套循环中的外循环混合数据类型不同封装格式数组下标非均匀跨步不可计数循环循环变量上界不是常数表达式包含不可向量化的运算如超越函数61多线程化可重入性共享变量的保护访问顺序保护互斥保护临界区的保护线程安全性无死锁无数据竞争62多线程化例1编译器通常会将循环不变的读操作移到循环之外，这样读操作就只会进行一次，而不是每次迭代都执行一

30、次。在多线程的情况下，这样做会产生什么问题？for (i=0; i100; i+0) int x; x = GlobalX； . . . int x = GlobalX；for (i=0; i100; i+0) . . . 63多线程化例2指令调度时通常可以将一条load指令提到它前面的的一条与之不相关的store指令之前执行，在多线程的情况下，这样做会产生什么问题？64多线程化线程化的优点创建速度较进程快资源利用率高便于数据共享线程化的缺点增加程序设计的复杂性程序调试较难数据竞争、同步、死锁65多线程并行程序设计方法任务划分将一个任务划分成多个并行子任务使得处理器负载平衡数据划分将数据对象划

31、分成多个并行子集提高访存的效率以及cache的命中率 数据流划分根据数据处理的过程划分一个子任务的输出是另一个子任务的输入划分的目标负载平衡降低调度开销、通信开销和同步开销66任务与线程任务task应用级的计算单位单任务线程为每个任务动态创建和终止创建和终止开销问题大量线程时的开销线程池预先创建的固定数量的线程与处理器数量匹配可完成多个任务应用程序中动态任务分配和调度线程中任意时刻只能运行一个纤程 6711122333333333344445555555555555536679838338891107611多线程并行程序设计方法任务划分的例子按颜色划分按区域划分68多线程并行程序设计方法线程（

32、数据流）划分的例子建筑工程砌墙、锯木、砌瓦、水电、粉刷存在相关性人力资源利用率问题69多线程并行程序设计方法数据划分的例子批考卷流水并行负载平衡问题70多线程的执行环境逻辑处理器操作系统看到的处理器资源硬件线程支持多线程的处理器核中的一个CU多核单线程处理器中的一个核一个单核单线程的处理器芯片71多线程的执行硬件多线程每个线程运行在不同逻辑处理器上优先级相同硬件的通信开销真正的并行执行软件多线程运行在同一个逻辑处理器上OS动态改变优先级共享本地存储器通信开销小互斥容易解决72多线程与多处理器的映像操作系统实现动态线程调度算法无法考虑应用的特征应用程序实现需要由应用程序员优化调试通过线程映像屏蔽

33、向量位向量进程映像屏蔽向量的子集需要动态获知逻辑处理器的数量需要区分不同的硬件环境超线程、多核、多芯片73多线程并行程序设计中的问题负载平衡挑战：线程执行时间的不确定性通过动态线程调度解决线程的开销创建、删除、同步、通信适度的并行并行颗粒度死锁Cache ping-pong74多线程并行程序设计方法将独立的循环程序变成多线程并行执行的线程可能改变相对执行的进度或顺序要求不存在循环带来的相关性将独立的程序段变成多线程变串行为并行纤程（fiber）执行一个任务创建开销小应用层可控75Win32线程APICreateThreadMyThreadStartCloseHandleWaitForSingl

34、eObjectWaitForMultipleObjectsCreateMutexReleaseMutexInitializeCriticalSectionDeleteCriticalSectionEnterCriticalSectionLeaveCriticalSectionCreateSemaphoreReleaseSemaphore76Win32线程APIConvertThreadToFiber GetFiberData CreateFiber fiberProc SwitchToFiber DeleteFiber GetCurrentFiber 77Example#include #in

35、clude 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);78OpenMP编写可

36、移植的多线程应用程序的API提供与平台无关的并行编程机制编译指令 pragma编译指示符 directive函数调用环境变量循环程序多线程化支持多线程间的同步和局部数据变量采用fork-join的执行模式程序员不需要对线程的创建和删除进行编程程序员不需要对同步操作进行详细编程适用于共享存储器的并行计算机#pragma omp parallel for for (i=0;iMAX;i+) Ai= c*Ai + Bi;线程79fork-join的执行模式主线程 分裂出一组线程并行性逐渐增加串行程序中嵌入并行性Parallel RegionsMaster Thread80OpenMP的编译指令par

37、allelforprivatesinglemasterreductionschedulesectionifbarrieratomicreductionchunk-size#pragma omp construct clause clause#pragma omp parallelThread1Thread2Thread3#pragma omp parallel block81Parallel for#pragma omp parallel for for ( i=0; inumPixels; i+) pGrayScalBitmapi = (unsigned BYTE) ( pRGBBitmap

38、i.red * 0.299 + pRGBBitmapi.green*0.587 + pRGBBitmapi.blue*0.114); 82Parallel for reductionsum = 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 re

39、duction(+:sum)for (i=0; i 100; i+)sum += arrayi;83Parallel section#pragma omp parallel sections #pragma omp section phase1(); #pragma omp section phase2(); #pragma omp section phase3();SerialParallel84OpenMP的线程调度算法静态将循环程序的各个迭代划分成相等大小的迭代束或者近似相等大小的迭代束每个迭代束包含大致相等的迭代数量动态使用内部的工作队列将迭代束分配给各个线程线程空闲时从工作队列中获取

40、下一个迭代束运行时迭代束的大小先比较大然后逐渐缩小在开始时减少调度时间，然后考虑负载平衡指导性的使用环境变量以指定三种调度方式中的哪一个用于调度85Parallel for scheduleFloat x1000, y1000;#pragma omp parallel for schedule(dynamic, 8) for (k=0; k1000; k+) xk=cos(a)*xk + sin(a)*yk 86并行程序的性能优化并行程序的优化分析程序的调用关系分析程序的关键调用路径分析程序中的热点执行时间最长的函数分析线程负载平衡分析关键路径87关键路径多线程程序包含多个执行流执行流在同步点相关关键路径是最长的执行流Thread 1Thread 2Thread 3T0T1T2T3T4T5T6T7T8T9T10T11T12T13T14T15Acquire LTh