高等计算机系统结构ppt课件

1、高等计算机系统构造清华大学计算机科学与技术系高性能计算研讨所郑纬民 教授2007年9月计算机科学与技术系研讨生课程高等计算机系统构造第一章 高等计算机的中心技术并行处置第二章 加速比性能模型与可扩展性分析第三章 互连与通讯第四章 划分与调度第五章 并行存储器系统第六章 Cache Coherence第七章 Memory Consistency第八章 指令级并行处置第九章 微处置器设计与实现方法第十章 网格计算高等计算机系统构造第十一章 DSM第十二章 传感器网络第十三章 对等计算第十四章 海量网络存储器第十五章 多核CPU技术第十六章 可信计算系统第十七章 虚拟化技术第十八章 基于集群的海量数

2、据处置第二章 加速比性能模型与可扩展性分析2.1 加速比性能分析2.1.1 普通概念2.1.2 加速比2.1.3 三种加速比性能模型2.2 可扩展性分析2.1 加速比性能模型2.1.1 普通概念1.处置机时间积处置机数目与处置时间的乘积用以度量这些处置机运转时的资源利用率。假设一程序在P台处置机上运转的时间为Tp，那么此P台处置机在Tp时间间隔内完成的任务最大数量为Tp * P。可将处置机实践任务曲线对时间的积分看成是这些处置机完成的有效任务量。效率为有效任务量与最大任务量之比。2.并行度Degree Of ParallelismDOP并行度DOP是在一定时间间隔内执行一个程序所用的处置机的数

3、目。3.并行性分布图 执行一个给定的程序时DOP对时间的分布图。DOP与对应时间的间隔之积即为处置机要完成的任务或任务负载。 以下图所示为一个并行性分布图。DOPt1tt2并行性分布图2.1.2 加速比1. 绝对加速比将最好的串行算法与并行算法相比较. 定义一与详细机器有关将最好的串行算法在一台上的运转时间与并行算法在N台运转的时间相比。 定义二与详细机器无关将最好的串行算法在最快的顺序机上的执行时间与并行算法在并行机上的运转时间相比。T(N)TSbest2.相对加速比同一并行算法在单节点上运转时间与在多个一样节点构成的处置机系统上的运转时间之比。这种定义偏重于描画算法和并行计算机本身的可扩展

4、性。)()1(NTTS 线性加速比：中间开销小，通讯少，弱耦合计算超线性加速比：当运用需求大内存时能够出现病态加速比：加速比递减，能够是计算量太小2.1.3 三种加速比性能模型1.固定负载加速比性能模型Amdahl定律在许多实时运用领域，计算负载的大小常固定。在并行机中，此负载可分布至多台并行执行，获得的加速比称为fixed-load speedup。一个问题的负载可表示如下：W = Ws + Wp其中，Ws代表问题中不可并行化的串行部分负载， Wp表示可并行化的部分负载。 那么n个节点情况下，加速比可以表示如下：nWpWsWpWsSn/设串行因子为串行部分所占的比例。即WpWsWpWpWsW

5、s1或nWpWsnWpWpWsWsWpWsWpWsSn/)1(1/代入即得Amdahllaw：不论采用多少处置机，可望到达的最好加速比：1/)1(1limnSnn效率En可以表示为：)1(1111/)1(1nnnnnSnEn处置机数目n越大，效率En越低。Amdahl定律通知我们：系统中某一部件由于采用某种更快的执行方式后整个系统性能的提高与这种执行方式的运用频率或占总执行时间的比例有关。任务的时间采用改进措施后执行某行某任务的时间没有采用改进措施前执性能没有采用改进措施前的采用改进措施后的性能加速比加速比的两个决议要素：1.计算机执行某个义务的总时间中可被改良部分的时间所占的百分比，即可被改

6、良部分占用时间/改良前整个义务的执行时间，记为Fe，它总小于1。2.改良部分采用改良措施后比没有采用改良措施前性能提高的倍数，即改良前改良部分执行时间/改良后改良部分执行时间，记为Se。SeFeFeS)1(1例1：假设将某系统的某一部件的处置速度加快到10倍，但该部件的原处置时间仅为整个运转时间的40%，那么整个系统的性能提高了多少？解：Fe = 0.4，Se = 10，56.1104.0)4.01(1 S例2：采用哪种实现技术来求浮点数平方根FPSQR的操作对系统的性能影响较大。假设FPSQR操作占整个测试程序执行时间的20%。一种实现方法是采用FPSQR硬件，使FPSQR操作的速度加快到1

7、0倍。另一种方法是使一切浮点数据指令的速度加快，使FP指令的速度加快到2倍，还假设FP指令占整个执行时间的50%。请比较这两种设计方案。解：Fe_FPSQR = 0.2，Se_FPSQR = 10， Fe_FP = 0.5，Se_FP = 2，22.1102.0)2.01(1FPSQRS33.125.0)5.01(1FPSAmdahllaw又称为固定规模加速比模型，问题规模不随处置机变化而变化。固定问题规模，看用并行技术能到达的最短时间是多少。在固定规模加速比模型下，负载和执行时间随系统中处置机数目n变化的情况如以下图：WsWpWsWpWsWpWsWpWorkloadN1234Executio

8、n TimeNTsTp1TsTp2TsTp3TsTp4固定负载执行时间随N添加而减少固定负载加速比模型下的负载和执行时间情况当处置器数目n=1024，加速比Sn随变化的情况如下：102311024)11024(110241024S得出曲线如以下图：00.010.020.030.040.050.060.070.080.090.102004006008001000120091Sn102448312410可以比较不同的对加速比带来的不同影响：100101102103104100101102103104 =0Snn =0.01 =0.1 =0.9=0时得到理想加速比，当值添加时，加速比性能急剧下降。结

9、论：加速比曲线随的上升急剧下降，缘由是存在顺序部分Ws，无法用添加系统的处置机数目来处理。这一性质在过去二十年间给人们呵斥了对并行处置非常悲观的印象。影响：两种意见： 1.劝阻制造商消费大规模并行计算机。 2.研讨并行编译器，以降低的值，从而提高系统的性能。规定负载加速比模型的能够运用范围： 对时间要求严厉的运用问题。2.固定时间加速比性能模型Gustafsun定律有许多运用领域强调精度而不时运转时间。1988年，Gustafsun提出了固定时间加速比模型。当机器的规模扩展时，解题的规模也随着扩展，从而得到更加准确的解，而使运转时间坚持不变。比如：有限元方法做构造分析，流体动力学做天气预告解P

10、DE(偏微分方程组)就需求提高精度。粗格要求的计算量较少，而细格的计算量多，得到的准确度也较高。天气预告模拟求解四维PDE，假设使每个实践方向X，Y，Z的格点间隔减少10倍，并以同一幅度添加时间步，那么可以说格点添加了104倍，因此任务负载也至少增大了10000倍。模型提出的背景：固定负载模型有缺陷：由于Amdahllaw中，取决于问题及并行编译器的效率，无法描画系统固有的特性。加速比的公式：) 1()1 ()1 (/ nnnWpWsnWpWsnWpWsWpWsSn其中，Wp=nWp和Ws+Wp=Ws+Wp/n作为固定时间的条件。 Ws+Wp/n表示在扩展负载后在添加处置机台数的情况下的平均负

11、载执行时间，它该当和负载没有扩展情况下的平均负载执行时间Ws+Wp相等。即有Ws+Wp=Ws+Wp/n。同时，负载的串行部分并没有改动，即有Ws=Ws。在固定时间加速比模型下，负载和执行时间随系统中处置机数目n变化的情况如以下图：WsWpWsWpWsWpWsWpWorkloadN1234Execution TimeNTsTp1TsTp2TsTp3TsTp4并行负载不断添加执行时间固定固定时间加速比模型下的负载和执行时间情况00.010.020.030.040.050.060.070.080.090.180085090095010001050110010231024)1(1024nnS增大问题规

12、模的方法使一切处置机坚持忙碌形状，在问题扩展到与可用的计算才干匹配时，程序中的顺序部分就不再是瓶颈了。当处置器数目n=1024，加速比Sn随变化的情况如下：Sn1024101410049939833.受限于存储器的加速比模型1993年，由Sun和Ni提出。大型科学计算和工程设计需求较大的存储空间，许多运用问题是存储器受限，而不是CPU受限或者I/O受限。比如：在分布存储系统中常遇到，总存储容量随节点数线性添加，许多节点集合起来解一个大题。根本思想：要在存储空间有限条件下解尽能够大的问题，这同样需求扩展任务负载，才干提供较高的加速比、较高的精度和较好的资源利用率。加速比可以表示如下：nWpnGW

13、sWpnGWsnWWWWSpspsn/)()(/*sWWsWs其中：在单个处置机上顺序执行的任务负载与问题的规模或系统的规模无关，即：而G(n)反映的是存储容量添加n倍时并行任务负载添加的倍数。nnnSSS*讨论：1.G(n) = 1，即为固定负载的情况；2.G(n) = n，即存储器添加n倍，负载也添加n倍，为固定时间的情形；3.G(n) n，计算负载的添加情况比存储器添加快，会有较高的加速比。比较三种加速比，对于一样的处置机数量，有：在受限于存储器的加速比模型下，负载和执行时间随系统中处置机数目n变化的情况如以下图：WsWpWsWpWsWpWsWpWorkloadN1234Executio

14、n TimeNTsTp1TsTp2TsTp3TsTp4规模扩展的任务负载执行时间稍有添加受限于存储器的加速比模型下的负载和执行时间情况例：n维矩阵乘法：A * B = C，其中A、B、C都是n*n的方阵。为得到C的每一个元素需求进展n次乘法、n次加法，所以总的计算量为：n+n)*n2 = 2n3。需求的存储量为3n2两个源矩阵，一个结果矩阵。假设n台计算机组成多计算机系统，那么存储容量扩展n倍，那么矩阵的维数原来为n)也可以添加了，设为N倍，那么加速比为多少？ 解：存储容量变为：nM = n* 3n2 = 3n3，而N维需求的存储量为3N2，计算量变为2N3，那么有：5.12333nNNnps

15、pspspsWnWWnWnWnWWnWS5.0*/5.135.433*2222)(nnnnNWWnG原来扩大后01002003004005006007008009001000010020030040050060070080090010004.并行计算的运用模型随机器规模的增大，任务负载增长的方式如以下图：任务负载问题规模n指数线性亚线性常数上图中：采用受限于存储器的加速比模型中给出的公式，曲线对应的G(n) = n1.5曲线对应的G(n) = n曲线对应的G(n) = 0.5n曲线对应的G(n) = 1那么有加速比公式:nWpnGWsWpnGWsSn/)()(*给定一个程序，

16、假设Ws/Wp = 0.4，那么效率为：nSEn*0100200300400500600700800900100001相应的处置器数目效率曲线如以下图：效率n指数线性亚线性常数结论：1.假设任务负载问题规模坚持不变，那么效率E随机器规模的增大而迅速下降，其缘由是开销h比机器规模添加得快，为了使效率坚持在一定的程度上，我们可以按比例增大机器规模和问题规模。2.假设任务负载按指数增长方式，效率要坚持恒定或坚持良好的加速比，必需使问题规模猛增才行，这样就会超越存储器或I/O限制，而问题规模只允许在计算机存储器可用的限制以内增长。并行计算机的运用模

17、型如以下图：通讯界限 存储器界限受限于存储器模型任务负载问题规模机器规模固定负载模型固定时间模型第二章 加速比性能模型与可扩展性分析2.1 加速比性能分析2.2 可扩展性分析2.2.1 可扩展性2.2.2 可扩展性分析2.2 可扩展性分析2.2.1 可扩展性1.可扩展性与可编程性添加可扩展性添加可编程性分布存储的音讯传送型多计算机共享存储型多处置机理想并行计算机2.可扩展性目的机器规模n时钟频率f问题规模sCPU时间TI/O需求d存储容量m通讯开销h计算机价钱c程序设计开销p3.可扩展性的直观定义对恣意数量n的处置机和恣意规模s的问题，假设一切算法的系统效率 E = 1， 那么系统是可扩展的。

18、4.规模可扩展性系统性能随处置机数量线性增长，包括：处置速度和效率存储速度和容量互连带宽和时延I/O速度和容量软件开销规模可扩展性与空间部分性、时间部分性以及部件瓶颈都有关系。例子：Cray Y-MP：16台处置机范围可伸缩CM-2：8K-64K台处置机范围可伸缩CM-5：1024-16K台处置机范围可伸缩KSR-1： 8-1088台处置机范围可伸缩5.换代时间可扩展性对系统各部分改换成新技术后，性能随之易扩展，要求算法、S/W均能兼容运转。6.问题可扩展性问题规模扩展时，系统仍能很好的运转，或说问题规模扩展到很大时，系统能在给定粒度下高效运转。2.2.2 可扩展性1.恒等效率概念Isoeff

19、iciency恒等效率定义为一个并行算法在并行计算机上实现时，为坚持效率E固定所需的任务负载与机器规模n的相对关系。设:W = Ws为任务负载， h = h s，n为通讯开销，它随s、n添加而增大。其中，s为问题规模，n为机器规模。那么效率可以表示为：),()()(nshsWsWE 问题的关键在于Ws与hs，n之间的相对增长速度。机器规模一定，开销h的增长比任务负载W要慢。因此，对一定规模的机器来说，效率会随问题规模增大而提高。所以，假假设任务负载W随机器规模适当添加，那么就有希望坚持效率不变。 对于知的算法来说，为了坚持恒定的效率，任务负载W能够需求对n以多项式或指数规律增长。不同的算法能够

20、需求不同的任务负载增长速率以便在n添加时坚持效率不致下降。 普通并行算法的恒定效率函数是n的多项式函数，即它们为Onk，k 1。n的幂越小，并行系统的可扩展性越大系统包括算法和构造的组合。2.恒等效率函数并行程序执行时间 Tp = (T1+T0)/p，其中，T1为总任务负载串行执行时间，T0为多节点总通讯延时，p为节点数。那么，加速比为：pTTS1而T1 = W tc，W为以操作次数计算的总任务负载，tc为每个操作的平均执行时间。10011111TTTTTpTTpSEp的函数）与工作负载是节点数可得为常数为定值W()1(1)1(1)1(1100000pTKTWEEtETEEtWEEtWTWtT

21、Ecccc如前面所述，任务负载W与开销h均可以表示成n与s的函数，所以，效率也可以表示如下：)(/),(11sWnshE为了使E坚持不变，任务负载Ws应该与开销h(s,n)成比例增长，由此可以得出以下条件：),()(1),(1)(nshCnfCEEnshEEsWE为：表示，则恒等效率函数为常数，用假设任务负载W(s)与fE(n)一样快的增长，那么知算法构造组合就能使效率坚持恒定。这个结论和前面的结论是一致的。此时， W(s)与fE(n)是一样的，只需求出了W(s)的数量级，就可知道fE(n)了。为了得到恒等效率，只需使W(s)与h(s,n)同一个数量级就可以了。例1：矩阵乘法的W(s) = Os3其中s为维数，还设hs，n= Onlogn+s2n0.5。求fE(n) 。 解：)()()()()()()log()()log()()()(5.1323323nOsOnOsOnsOsOnnOsOnsnnOsOshsW或者即要满足W与h同数量级的条件，需求在两式中选出大的：)()()()(5 . 15 . 13nOnfnOsOE例2：W(s) = Os3，hs，n= Onlog