《高等计算机系统结构(第四讲)课件》由会员分享，可在线阅读，更多相关《高等计算机系统结构(第四讲)课件（70页珍藏版）》请在金锄头文库上搜索。
1、高等计算机系统结构,清华大学计算机科学与技术系高性能计算研究所 郑纬民 教授 2007年10月,计算机科学与技术系研究生课程,高等计算机系统结构,第一章 高等计算机的核心技术并行处理 第二章 加速比性能模型与可扩展性分析 第三章 互连与通信 第四章 划分与调度 第五章 并行存储器系统 第六章 Cache Coherence 第七章 Memory Consistency 第八章 指令级并行处理,第四章 划分与调度,4.1 粒度划分与组合 4.1.1 细粒度程序调度 4.1.2 粒度的组合 4.1.3 静态多处理机调度 4.2 负载平衡 4.3 程序流机制,4.1 粒度划分与组合,做并行程序设计时
2、要回答两个基本问题： （1）如何将程序划分成并行模块、子任务以获得最短执行时间。 （2）计算中的并发粒度为多大会比较理想。 这与问题以及机器都有关，需要在并行性与调度开销之间做折衷。,4.1.1 细粒度程序的调度 1.一个细粒度程序调度的例子 Var a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p, q Begin 1a:=1 2b:=2 3c:=3 4d:=4 5e:=5 6f:=6,7g:=a*b 8h:=c*d 9i:=d*e 10j:=e*f 11k:=d*f 12l:=j*k 13m:=4*l 14n:=3*m 15o:=n*i 16p:
3、=o*h 17q=p*g End,指令1，2，3，4，5，6是存储器访问（取数据）操作，每个结点用一个周期进行寻址，用六个周期从存储器取数。 指令7-17是CPU操作，每个需要两个周期完成。 程序图： 每个结点相当于程序中的计算单元 粒度用执行结点中全部操作所需要的基本时间来度量（处理机和存储器） 程序图中的结点表示如下图：,n，s,x，i,y，j,u，k,v，h,（n，s）=（结点名，粒度） （x，i）=（输入变量，延迟） （u，k）=（输出变量，延迟） 粒度是指程序段所含的计算量； 延迟主要指通信延迟，包括通道延迟和消息延迟。,例中的细粒度程序图如下：,1,1,2,1,3,1,4,1,5,
4、1,6,1,7,2,8,2,9,2,10,2,11,2,12,2,13,2,14,2,15,2,16,2,17,2,a,6,b,6,c,6,d,6,d,6,e,6,e,6,d,6,f,6,f,6,g,4,h,4,i,4,j,4,k,4,l,3,4,0,3,0,m,3,n,4,o,3,p,3,q,3,2台处理机的细粒度调度如下：,6,11,1,2,3,9,8,7,5,10,12,13,14,15,16,17,4,P1,P2,0,1,7,9,10,11,12,18,20,22,24,28,0,1,2,8,10,14,16,19,21,24,26,26,30,32,35,37,40,42,图中的阴影
5、部分为通信延迟,4.1.2粒度的组合 如果加大粒度有可能消除消除一些不必要的通信时延或降低总的调度开销，则将多个细粒度结点组合成粗粒度结点。 前面细粒度的程序图经过粒度组合可以得到粗粒度的程序图如下所示：,1,1,2,1,3,1,4,1,5,1,6,1,7,2,8,2,9,2,10,2,11,2,12,2,13,2,14,2,15,2,16,2,17,2,a,6,b,6,c,6,d,6,d,6,e,6,e,6,d,6,f,6,g,4,h,4,i,4,j,4,k,4,l,3,4,0,3,0,m,3,n,4,o,3,p,3,q,3,A,B,C,D,E,例中的粗粒度程序图如下：,A,8,B,4,C,
6、4,D,6,E,6,a,6,b,6,c,6,d,6,d,6,e,6,f,6,g,4,h,4,i,4,j,4,k,4,n,4,q,0,2台处理机的粗粒度调度如下：,A,C,D,P1,P2,0,8,14,22,28,32,38,图中的阴影部分为通信延迟 I表示处理机空闲,18,E,I,B,0,14,22,18,I,4.1.3静态多处理机调度 结点复制：为了消除空闲时间和进一步降低处理机间的通信延迟。 如下面的程序图所示的例子：,d,4,A,4,B,1,E,2,C,1,D,2,a,1,b,1,c,8,a,8,c,1,e,4,2台处理机的不用结点复制技术的调度方案如下：,d,4,A,4,B,1,E,2
7、,C,1,D,2,a,1,b,1,c,8,a,8,c,1,e,4,P1,P2,调度图如下：,A,B,I,P1,P2,0,4,5,7,13,21,23,图中的阴影部分为通信延迟 I表示处理机空闲,6,D,I,C,0,4,16,12,得到e,27,E,13,14,20,得到d,2台处理机的采用结点复制技术的调度方案如下：,d,4,A,4,B,1,E,2,C,1,D,2,a,1,b,1,c,1,a,1,c,1,e,4,P1,P2,A,4,C,1,a,1,调度图如下：,A,B,C,P1,P2,0,4,5,7,10,图中的阴影部分为通信延迟 I表示处理机空闲,6,D,A,C,0,4,9,5,得到e,14
8、,E,6,7,13,得到d,8,比较两种方案： 采用结点复制的技术后，调度方案所用的时间几乎短了50%，其原因是由于消除了两台处理机之间的延迟（a，8）和（c，8）。,粒度确定和调度优化过程：,第一步：构造细粒度的程序图,第二步：调度细粒度运算,第三步：进行粒度组合得到粗粒度,第四步：在组合图基础上产生并行调度方案,例1静态多处理机调度的程序分解,需要8次乘法（每次需要101个CPU周期），7次加法（每次需要8个CPU周期），以二叉树结构完成，如下。,Aik,Bkj,k=1,2,粒度=101,Aik Bkj,Ai1 B1j,Ai2 B2j,粒度=8,Gij= Ai1 B1j+ Ai2 B2j,
9、在20MHz下，M68000汇编代码如下（后面的数字是指令所用的周期数）： MoveWAxx,D115 MoveWBxx,D215 MPTYD1,D271 MoveLD2,PAR20 MoveLPAR1,D120 MoveLPAR2,D220 ADDLD1,D28 MoveLD2,PSUM20,通信延迟d的计算：,P1,存储器,DMA,DMA,P2,存储器,T1,T2,T3,T4,T5,串行链路,其中，T3是32位在20Mbps下的传输时间，折合成M68000的周期，T6是由于软件协议的延迟（假定用5条Move指令，共100个周期）。,细粒度的程序图如下：,A,B,C,D,E,F,G,H,d,
10、d,d,d,d,d,d,d,J,K,L,M,d,d,d,d,N,O,P,d,d,SUM,细粒度的顺序调度方案如下：,P1,A,B,0,202,101,C,D,404,303,E,F,606,505,G,H,808,707,J,K,L,M,N,O,P,816,824,832,840,848,856,864,808,共需864个周期。,细粒度的并行调度方案如下（8处理器）：,P1,A,B,0,313,101,C,D,321,=101,E,F,531,523,G,H,751,743,J,K,L,M,N,O,P,P2,P3,P4,P5,P6,P7,P8,I,I,I,I,I,I,图中的阴影部分为通信延迟
11、 I表示处理机空闲,=8,d=212,=8,d=212,=8,d=212,使用8个处理机进行并行调度，共需751个周期。 和顺序调度相比，获得的加速比为:,采用粒度组合减少通信开销：,A,B,C,D,E,F,G,H,d,d,d,d,d,d,d,d,J,K,L,M,d,d,d,d,N,O,P,d,d,SUM,V,W,X,Y,Z,通信延迟为：,各结点粒度为：,程序图中最大并行度已降为4，所以只需要用4台处理机执行此粗粒度程序即可。 上述调度方案只用了,第四章 划分与调度,4.1 粒度划分与组合 4.2 负载平衡 4.2.1 负载平衡及其分类 4.2.2 负载分配算法的构成 4.3 程序流机制,4.
12、2 负载平衡,4.2.1 负载平衡的定义及其分类 问题背景：并行计算机的进程数目超过了可用的处理机数。 负载的度量：CPU时间、通信时间、存储器用量、并发进程数等等。 什么是负载平衡（Load Balance）？,1.静态的负载平衡 针对应用程序中的各种信息（如各个任务的计算量大小、依赖关系和通信关系）以及并行系统本身的状况（如网络结构、各处理结点计算能力）对应用程序中的并行任务作出静态的分配决策，在运行该程序的过程中依照事先的分配方案将任务分配到相应结点。 问题是任务负载是动态产生的，很难准确预测。这种方法只用于理论推导而很难用于实际。,2.动态的负载平衡 在应用程序运行过程中实现负载平衡，
13、通过分析并行系统的实时负载信息，动态的将任务在多处理机之间进行分配和调整。,4.2.2 负载分配算法的构成 1. Transfer Policy（传送策略） 用来确定一个结点是否进行任务传送。 常用的是阈值（Threshold policy）。把结点分成忙碌和空闲两类，某个结点的负载低于阈值即为空闲，高于阈值为忙碌。如果阈值设置过低，负载量人为的很高；如果阈值设置过高，结点事实上已经支持过重的计算，但表面上仍显得空闲。 如结点上产生了一个新的任务，使负载超过了阈值，则可认定此结点为Sender，如负载低于阈值，则可认为此结点是可接收远程任务的Receiver。,2. Selection Pol
14、icy（选择策略） 在Transfer Policy确定Sender后，选择策略即去选哪一个任务进行传送。最简单的办法是选定最新使该结点成为可发送结点的那个任务。,3. Location Policy（定位策略） 用来确定传送任务应该传送给哪一个结点。一般所用的方法为Polling，可串行做或并行进行（multicast），可随机进行，即根据以前收集的信息随机进行或按照近邻方式进行。也可以广播方式进行。,4. Information Policy（信息收集策略） 负责确定何时应该从系统中的其它结点收集信息，从何处收集信息，以及收集什么信息。Demand-driven：在一个结点被确定为Send
15、er或Receiver后，即去收集其它结点的信息。,5.三种启动方式 （1）Sender-initiated：发送者启动，即忙碌结点启动负载平衡，适合于轻负载。过程如下： a. Sender广播Too-High消息，将Too-High的超时标志Timeout置位，开始收听Accept消息，直到超时结束。 b. Receiver接收Too-High消息，撤除Too-Low的超时标志Timeout，发送Accept消息给Too-High源结点，增加负载值并设置Awaiting Task Timeout。如超时后仍然没有收到任务，则将负载值减小。,c. 在收到Accept后，如结点仍然为Sender，则选定最合适的任务给响应结点。 d. 如Too-High超时已经结束，而Accept消息尚未收到，Sender表示原来假定的平均系统负载值太低（阈值），它可以广播Change Average消息给其它结点，增加平均负载值。,（2）Receiver-initiated：接收者启动，适合于重负载系统。 a. Receiver广播Too-Low消息，设置Too-Low Timeout，开始收听Too-High消息。 b. 假如收到Too-High消息，Receiver完成上述类似于S
