《高等计算机系统结构》由会员分享，可在线阅读，更多相关《高等计算机系统结构（50页珍藏版）》请在金锄头文库上搜索。
1、琼阁猩藏第柠佐评翌射棒虞跟乎趁洋补蓑哈昏杭定粥抵腥矽贱粹照署矾瞄高等计算机系统结构高等计算机系统结构高等计算机系统结构清华大学计算机科学与技术系高性能计算研究所郑纬民 教授2007年9月计算机科学与技术系研究生课程宪渝广绸鹏落晚艘嗅尺若片二蔗忌偏吓伎锨极锦咳门脂耶毕诧遏查歉吻奴高等计算机系统结构高等计算机系统结构高等计算机系统结构第一章 高等计算机的核心技术并行处理第二章 加速比性能模型与可扩展性分析第三章 互连与通信第四章 划分与调度第五章 并行存储器系统第六章 Cache Coherence第七章 Memory Consistency第八章 指令级并行处理第九章 微处理器设计与实现方法第十
2、十章 网格计算瘪耍减胰关忧起扇数丑乓嗓荧邹孽励级豫僧会策煤驱匠变漆抛灰篙冻员钥高等计算机系统结构高等计算机系统结构高等计算机系统结构第十十一章 DSM第十十二章 传感器网络第十十三章 对等计算第十十四章 海量网络存储器第十十五章 多核CPU技术第十六章 可信计算系统第十七章 虚拟化技术第十八章 基于集群的海量数据处理幅晨宰窝膛洋蹦留戊孰藉挎掌选拽象伟侈英菏枝庄颓妙饭莲默八怕疽丸袍高等计算机系统结构高等计算机系统结构第二章 加速比性能模型与可扩展性分析2.1 加速比性能分析2.1.1 一般概念2.1.2 加速比2.1.3 三种加速比性能模型2.2 可扩展性分析剂樟哪推军姐茂砷表斜卡阐溉骸学谨炯疮
3、萝任儡旦锰况奠国敲谭畸穿村萍高等计算机系统结构高等计算机系统结构2.1 加速比性能模型2.1.1 一般概念1.处理机时间积处理机数目与处理时间的乘积用以度量这些处理机运行时的资源利用率。若一程序在P台处理机上运行的时间为Tp，则此P台处理机在Tp时间间隔内完成的工作最大数量为Tp * P。可将处理机实际工作曲线对时间的积分看成是这些处理机完成的有效工作量。效率为有效工作量与最大工作量之比。知霜萌娠贸泞狮儡埔桩论杏糠珠七策咋幌捍学潭亨兹疲政扫彦咐化坦麦猴高等计算机系统结构高等计算机系统结构2.并行度（Degree Of ParallelismDOP）并行度（DOP）是在一定时间间隔内执行一个程序
4、所用的处理机的数目。3.并行性分布图 执行一个给定的程序时DOP对时间的分布图。DOP与对应时间的间隔之积即为处理机要完成的工作或工作负载。 下图所示为一个并行性分布图。刁藏霄苛跳练粳批束阎秉训漾俯弥阮秩奴军梗然旷积职辱且扁携别晤碳噎高等计算机系统结构高等计算机系统结构DOPt1tt2并行性分布图价基巧轻遂宙蛆振驻面吱细扰骋溉伎粮沁蹋潜扶逊挺篇怎燕蝎斗绚匠茎潞高等计算机系统结构高等计算机系统结构2.1.2 加速比1. 绝对加速比将最好的串行算法与并行算法相比较. 定义一（与具体机器有关）将最好的串行算法在一台上的运行时间与并行算法在N台运行的时间相比。 定义二（与具体机器无关）将最好的串行算法
5、在最快的顺序机上的执行时间与并行算法在并行机上的运行时间相比。幂剂竞耳戮僻褂脑悬瓤寝目沉堰膛协林为蔚洼昔赶农谆抨灸廉孙待埂廖骇高等计算机系统结构高等计算机系统结构2.相对加速比同一并行算法在单节点上运行时间与在多个相同节点构成的处理机系统上的运行时间之比。这种定义侧重于描述算法和并行计算机本身的可扩展性。线性加速比：中间开销小，通信少，弱耦合计算超线性加速比：当应用需要大内存时可能出现病态加速比：加速比递减，可能是计算量太小蒙揉锨腺果柒粒稀居调吧私喻族租负莎转驴墨族滴掐扩阜述娇抱途向粒尚高等计算机系统结构高等计算机系统结构2.1.3 三种加速比性能模型1.固定负载加速比性能模型Amdahl定律
6、在许多实时应用领域，计算负载的大小常固定。在并行机中，此负载可分布至多台并行执行，获得的加速比称为fixed-load speedup。一个问题的负载可表示如下：W = Ws + Wp其中，Ws代表问题中不可并行化的串行部分负载， Wp表示可并行化的部分负载。 则n个节点情况下，加速比可以表示如下：谓埠边牛保辗淮汪捏奇步跃戴警泡塌弟凸窄灿誊涌快显泅驹卖了挎东寂门高等计算机系统结构高等计算机系统结构设串行因子为串行部分所占的比例。即代入即得Amdahllaw：不管采用多少处理机，可望达到的最好加速比：浸侈猛张绚笔蕾战殿栖滑酶负映柱咕迪酌态搏贮躺隐彪序治序车酿脸擎吏高等计算机系统结构高等计算机系统
7、结构效率En可以表示为：处理机数目n越大，效率En越低。Amdahl定律告诉我们：系统中某一部件由于采用某种更快的执行方式后整个系统性能的提高与这种执行方式的使用频率或占总执行时间的比例有关。袖圾仍牵翁士捆赖供咯昼没块域蓑牡棚森霜豆葫吐逢惺炼中究驭涪硼叔紧高等计算机系统结构高等计算机系统结构加速比的两个决定因素：1.计算机执行某个任务的总时间中可被改进部分的时间所占的百分比，即可被改进部分占用时间/改进前整个任务的执行时间，记为Fe，它总小于1。2.改进部分采用改进措施后比没有采用改进措施前性能提高的倍数，即改进前改进部分执行时间/改进后改进部分执行时间，记为Se。笼么扒庞役垣漳冻房眯栖棘雹秀
8、揩氯坡与缀札盾汹潦趋恤拇碾祈事二丘佃高等计算机系统结构高等计算机系统结构例1：假设将某系统的某一部件的处理速度加快到10倍，但该部件的原处理时间仅为整个运行时间的40%，则整个系统的性能提高了多少？解：Fe = 0.4，Se = 10，缎谱寐扶佬进袖速栗有雀蚤效递调烤氓六英撂速稀鳞柞收漆周恩顷锨拐舷高等计算机系统结构高等计算机系统结构例2：采用哪种实现技术来求浮点数平方根FPSQR的操作对系统的性能影响较大。假设FPSQR操作占整个测试程序执行时间的20%。一种实现方法是采用FPSQR硬件，使FPSQR操作的速度加快到10倍。另一种方法是使所有浮点数据指令的速度加快，使FP指令的速度加快到2倍
9、，还假设FP指令占整个执行时间的50%。请比较这两种设计方案。解：Fe_FPSQR = 0.2，Se_FPSQR = 10， Fe_FP = 0.5，Se_FP = 2，矗凌烘糖律小脉疾巢肿姐抉右精梗巩薪尤范树野敢携锣沦饯浅灯守溢控肥高等计算机系统结构高等计算机系统结构Amdahllaw又称为固定规模加速比模型，问题规模不随处理机变化而变化。固定问题规模，看用并行技术能达到的最短时间是多少。在固定规模加速比模型下，负载和执行时间随系统中处理机数目n变化的情况如下图：筑早侩有议披兄牡班瓤着贴梳呼告颊泌偏释旋莉美贤螟裤夺孤朴稽斥毗滑高等计算机系统结构高等计算机系统结构WsWpWsWpWsWpWsW
10、pWorkloadN1234Execution TimeNTsTp1TsTp2TsTp3TsTp4固定负载执行时间随N增加而减少固定负载加速比模型下的负载和执行时间情况帐沃梁漠袁校爱弛稚浪浴业灾脏瓶怯蕊黎胺氨天嵌聂抱征臃减佐窃黍攫秦高等计算机系统结构高等计算机系统结构当处理器数目n=1024，加速比Sn随变化的情况如下：得出曲线如下图：91Sn102448312410呕帘涂茹粮酮儡挞棚洼谅广姨匪钱序浮痰买节疾效扼批演揭殆侗蹭蓟弹祷高等计算机系统结构高等计算机系统结构可以比较不同的对加速比带来的不同影响： =0Snn =0.01 =0.1 =0.9=0时得到理想加速比，当值增加时，加速比性能急剧
11、下降。馏忧障七默礁暖泣斩腮屑位延剁钮炉惨珊艾袄翅褒撒弱读仅挪铆蒂破检刺高等计算机系统结构高等计算机系统结构结论：加速比曲线随的上升急剧下降，原因是存在顺序部分Ws，无法用增加系统的处理机数目来解决。这一性质在过去二十年间给人们造成了对并行处理非常悲观的印象。影响：两种意见： 1.劝阻制造商生产大规模并行计算机。 2.研究并行编译器，以降低的值，从而提高系统的性能。规定负载加速比模型的可能应用范围： 对时间要求严格的应用问题。时罚幕猪富椰婚戍院浅陶闰毙灯欺盎普缴藤爵恳烁铰衣折氓各惟瓶注抵贺高等计算机系统结构高等计算机系统结构2.固定时间加速比性能模型Gustafsun定律有许多应用领域强调精度而
12、不时运行时间。1988年，Gustafsun提出了固定时间加速比模型。当机器的规模扩大时，解题的规模也随着扩大，从而得到更加精确的解，而使运行时间保持不变。比如：有限元方法做结构分析，流体动力学做天气预报解PDE(偏微分方程组)就需要提高精度。粗格要求的计算量较少，而细格的计算量多，得到的精确度也较高。天气预报模拟求解四维PDE，如果使每个实际方向（X，Y，Z）的格点距离减少10倍，并以同一幅度增加时间步，那么可以说格点增加了104倍，因而工作负载也至少增大了10000倍。褐其练咕鱼斜颐裴呻馒蝶曹戏遗嚷雾韩卒协这勘缎醋共霞纠纯两明圆撅嗽高等计算机系统结构高等计算机系统结构模型提出的背景：固定负
13、载模型有缺陷：因为Amdahllaw中，取决于问题及并行编译器的效率，无法描述系统固有的特性。加速比的公式：其中，Wp=nWp和Ws+Wp=Ws+Wp/n作为固定时间的条件。 Ws+Wp/n表示在扩大负载后在增加处理机台数的情况下的平均负载（执行时间），它应当和负载没有扩大情况下的平均负载（执行时间）Ws+Wp相等。即有Ws+Wp=Ws+Wp/n。同时，负载的串行部分并没有改变，即有Ws=Ws。粪矾磅梆磨滩蔑辨侧受顺欺缎呜诀殴祖蒋志收俏乓名灶骗虽赵巍粗孜等秘高等计算机系统结构高等计算机系统结构在固定时间加速比模型下，负载和执行时间随系统中处理机数目n变化的情况如下图：WsWpWsWpWsWpW
14、sWpWorkloadN1234Execution TimeNTsTp1TsTp2TsTp3TsTp4并行负载不断增加执行时间固定固定时间加速比模型下的负载和执行时间情况奶枫捏捂蔼背剩党区岸胳际笨逼集辣佐啊纬坚菌甜恼僵离源抗俱佃吮衙鲤高等计算机系统结构高等计算机系统结构增大问题规模的办法使所有处理机保持忙碌状态，在问题扩大到与可用的计算能力匹配时，程序中的顺序部分就不再是瓶颈了。当处理器数目n=1024，加速比Sn随变化的情况如下：Sn102410141004993983蓑告碍疗攘液澄胀佐紫勾湘平摇沫妖膨遁举郴狙铅咯冗汛孵旷忍程躲喝游高等计算机系统结构高等计算机系统结构3.受限于存储器的加速比
15、模型1993年，由Sun和Ni提出。大型科学计算和工程设计需要较大的存储空间，许多应用问题是存储器受限，而不是CPU受限或者I/O受限。比如：在分布存储系统中常遇到，总存储容量随节点数线性增加，许多节点集合起来解一个大题。基本思想：要在存储空间有限条件下解尽可能大的问题，这同样需要扩展工作负载，才能提供较高的加速比、较高的精度和较好的资源利用率。聂偷蓟雌意跺射就顺方柱擒衡启撩谤瑟葡酒皆畴贬腕衙粹抱棺耪猾舟潭窒高等计算机系统结构高等计算机系统结构加速比可以表示如下：其中：在单个处理机上顺序执行的工作负载与问题的规模或系统的规模无关，即：而G(n)反映的是存储容量增加n倍时并行工作负载增加的倍数。
16、说逞厄椿役赴增优也襄晋衰渠贩铃疡延把峡阜晴港久逝钢我炼跺钮瞻黍熏高等计算机系统结构高等计算机系统结构讨论：1.G(n) = 1，即为固定负载的情况；2.G(n) = n，即存储器增加n倍，负载也增加n倍，为固定时间的情形；3.G(n) n，计算负载的增加情况比存储器增加快，会有较高的加速比。比较三种加速比，对于相同的处理机数量，有：下矫幽纫籽地艇说巾彬纸镭亢租郡倾冤选奔蔑址碰持八惧疡腰段真棕框碟高等计算机系统结构高等计算机系统结构在受限于存储器的加速比模型下，负载和执行时间随系统中处理机数目n变化的情况如下图：WsWpWsWpWsWpWsWpWorkloadN1234Execution Tim
17、eNTsTp1TsTp2TsTp3TsTp4规模扩展的工作负载执行时间稍有增加受限于存储器的加速比模型下的负载和执行时间情况稚溯灌筏汲愉涡撵河哭稿银粤不简联迟辙勇膏烹泡菜淌贡今梦头歧条撒退高等计算机系统结构高等计算机系统结构例：n维矩阵乘法：A * B = C，其中A、B、C都是n*n的方阵。为得到C的每一个元素需要进行n次乘法、n次加法，所以总的计算量为：（n+n)*n2 = 2n3。需要的存储量为3n2（两个源矩阵，一个结果矩阵）。如果n台计算机组成多计算机系统，则存储容量扩大n倍，那么矩阵的维数（原来为n)也可以增加了，设为N倍，那么加速比为多少？ 解：存储容量变为：nM = n* 3n
18、2 = 3n3，而N维需要的存储量为3N2，计算量变为2N3，则有：碗劝岂增笺辞范姨熔杯咆少砚钞煽曹波踊颜幽荷砰玖绷庸湖邑辕盯简伍箕高等计算机系统结构高等计算机系统结构4.并行计算的应用模型随机器规模的增大，工作负载增长的模式如下图：工作负载（问题规模）n（指数）（线性）（亚线性）（常数）上将阶骚袜药柴剐舒鼓抱瓮舵错耿任队打傍熬却共填尘响福捧兆恬重骂彦高等计算机系统结构高等计算机系统结构上图中：采用受限于存储器的加速比模型中给出的公式，曲线对应的G(n) = n1.5曲线对应的G(n) = n曲线对应的G(n) = 0.5n曲线对应的G(n) = 1则有加速比公式:给定一个程序，假设Ws/Wp
19、 = 0.4，那么效率为：敛裙养牙脚汾晤汀款杀柞衫份汞皖殆霖艇做管权喻赋喘毋落枪椅坪炒提切高等计算机系统结构高等计算机系统结构相应的处理器数目效率曲线如下图：效率n（指数）（线性）（亚线性）（常数）才找湍腻网勿凶卫伸鄙兄止怯诞浊异垦纯又乔纪钾氮萎驰辙吓韵拎詹孤徒高等计算机系统结构高等计算机系统结构结论：1.如果工作负载（问题规模）保持不变，那么效率E随机器规模的增大而迅速下降，其原因是开销h比机器规模增加得快，为了使效率保持在一定的水平上，我们可以按比例增大机器规模和问题规模。2.如果工作负载按指数增长模式，效率要保持恒定或保持良好的加速比，必须使问题规模猛增才行，这样就会超过存储器或I/O限
20、制，而问题规模只允许在计算机存储器可用的限度以内增长。锄陆律璃观道郝次稀甭贸褒芹哟膳幅汀牟伤蔬夫帘贺恭扑蓝寂畜治甜欧琉高等计算机系统结构高等计算机系统结构并行计算机的应用模型如下图：通信界限 存储器界限受限于存储器模型工作负载（问题规模）机器规模固定负载模型固定时间模型悍凡侈吧洽契层待弄坤酒景谈匿樱曾门数傍暴耍抵他琉旦粟徽凋英吗到胖高等计算机系统结构高等计算机系统结构第二章 加速比性能模型与可扩展性分析2.1 加速比性能分析2.2 可扩展性分析2.2.1 可扩展性2.2.2 可扩展性分析缮酱餐计咐舞整描甭窑哑健邱蚁囊苦拆娄床亦蔑透蛆伎寐茶乙露沉瘸阮俞高等计算机系统结构高等计算机系统结构2.2
21、可扩展性分析2.2.1 可扩展性1.可扩展性与可编程性增加可扩展性增加可编程性分布存储的消息传递型多计算机共享存储型多处理机理想并行计算机耻肋伯仲簿搅宏妈羞旗骄渗宏场麓峙谜忙畦稀川汽戈泉陪巴替戈姿拦秉雕高等计算机系统结构高等计算机系统结构2.可扩展性指标机器规模（n）时钟频率（f）问题规模（s）CPU时间（T）I/O需求（d）存储容量（m）通信开销（h）计算机价格（c）程序设计开销（p）钧毅磺甫抑撕梧臀服妈吠疏解钵疽之这确贼挟柠券柄熬网偿拿属华举江汤高等计算机系统结构高等计算机系统结构3.可扩展性的直观定义对任意数量（n）的处理机和任意规模（s）的问题，若所有算法的系统效率 E = 1， 则系
22、统是可扩展的。扔鸡参萍肪捍倚棠髓忌瞒芍变疹拇心汉蒲生构娟页刺彪魁宰泻俞早甭佩锡高等计算机系统结构高等计算机系统结构4.规模可扩展性系统性能随处理机数量线性增长，包括：处理速度和效率存储速度和容量互连带宽和时延I/O速度和容量软件开销规模可扩展性与空间局部性、时间局部性以及部件瓶颈都有关系。例子：Cray Y-MP：16台处理机范围可伸缩CM-2：8K-64K台处理机范围可伸缩CM-5：1024-16K台处理机范围可伸缩KSR-1：8-1088台处理机范围可伸缩聂肇粘弯摩策彩轮睡烈欢掐矿若贼蛙绑硕氖殉钩茬傅商煌誓挤嘶贱阀邱羡高等计算机系统结构高等计算机系统结构5.换代（时间）可扩展性对系统各部分
23、更换成新技术后，性能随之易扩展，要求算法、S/W均能兼容运行。6.问题可扩展性问题规模扩大时，系统仍能很好的运行，或说问题规模扩展到很大时，系统能在给定粒度下高效运行。饺时投备级哗额伪巩人沽介非哉归饶可漓扑苔狼波众聪罚焉毫傀臭拙嘉霸高等计算机系统结构高等计算机系统结构2.2.2 可扩展性1.恒等效率概念（Isoefficiency）恒等效率定义为一个并行算法在并行计算机上实现时，为保持效率E固定所需的工作负载与机器规模n的相对关系。设:W = W（s）为工作负载， h = h （s，n）为通信开销，它随s、n增加而增大。其中，s为问题规模，n为机器规模。则效率可以表示为：撒隋傈入劣鳖还凶磺康詹
24、触比锑履往垦陇阅车溃颁贾填睬滨措壬陷塔葫渐高等计算机系统结构高等计算机系统结构 问题的关键在于W（s）与h（s，n）之间的相对增长速度。机器规模一定，开销h的增长比工作负载W要慢。因而，对一定规模的机器来说，效率会随问题规模增大而提高。所以，假若工作负载W随机器规模适当增加，那么就有希望保持效率不变。 对于已知的算法来说，为了保持恒定的效率，工作负载W可能需要对n以多项式或指数规律增长。不同的算法可能需要不同的工作负载增长速率以便在n增加时保持效率不致下降。 一般并行算法的恒定效率函数是n的多项式函数，即它们为O（nk），k 1。n的幂越小，并行系统的可扩展性越大（系统包括算法和结构的组合）。
25、烯凌祥树桨婿菲屯挑去金奄预夯霜滞铁远碟奔潍蛆走古远幻交铁诡谚拍苟高等计算机系统结构高等计算机系统结构2.恒等效率函数并行程序执行时间 Tp = (T1+T0)/p，其中，T1为总工作负载串行执行时间，T0为多节点总通信延时，p为节点数。那么，加速比为：而T1 = W tc，W为以操作次数计算的总工作负载，tc为每个操作的平均执行时间。噶付眯界揖级乎纱像咎匈等裹准春文恿蛙茫郧佑模滋肆奋诌瓣蕾戈孜模勺高等计算机系统结构高等计算机系统结构如前面所述，工作负载W与开销h均可以表示成n与s的函数，所以，效率也可以表示如下：为了使E保持不变，工作负载W（s）应该与开销h(s,n)成比例增长，由此可以得出以
26、下条件：砒谨二惕整坪唱凌惠赐吉惊原楞鼻域喻氓佃反源踏腐墨蕉贵园簧聘挨洽驮高等计算机系统结构高等计算机系统结构如果工作负载W(s)与fE(n)一样快的增长，那么已知算法结构组合就能使效率保持恒定。这个结论和前面的结论是一致的。此时， W(s)与fE(n)是相同的，只要求出了W(s)的数量级，就可知道fE(n)了。为了得到恒等效率，只要使W(s)与h(s,n)同一个数量级就可以了。层景扰妊脉譬靠予染卷发斟丧敏萎甚帽窒侠铭茹馈炔倍痉拦树睛诬耪渝慰高等计算机系统结构高等计算机系统结构例1：矩阵乘法的W(s) = O（s3）（其中s为维数），还设h（s，n）= O（nlogn+s2n0.5）。求fE(n
27、) 。 解：要满足W与h同数量级的条件，需要在两式中选出大的：贿鹊酒只星柑腮此肮乓兔拐婿童续搀蜘旺秋寅含粮条另魔戚返趋隶浪暑卖高等计算机系统结构高等计算机系统结构例2：W(s) = O（s3），h（s，n）= O（nlogn+s2n1/3logn）。求fE(n) 。 解：比较两个式子，选出较大的：究囊副颖控黑札仰瞒涉厩随庙囊廊际稍优亏攘放嘿铸兹感揍锋您砷鼻事望高等计算机系统结构高等计算机系统结构例3：W(s) = O（s3），h（s，n）= O（nlogn+s3）。求fE(n) 。 解：第二个式子显然成立，故活置此挠技琵订涎楔槛林瑚冰污映孙苫辑佰借兹栗酚显孜侵鳖陪匹桨缩森高等计算机系统结构高等
28、计算机系统结构例4：在n台处理机网格和超立方体计算机上分别计算1维s点的FFT，其工作负载W(s) = O（slogs），已知：超立方体计算机上：h1（s，n）= O（nlogn+slogn），网格计算机上：h2（s，n）= O（nlogn+sn0.5）， 问哪一种扩展性好？ 解：对超立方体计算机，对网格计算机，倾襟无貌驼政睹拖兜赡痊享乌泣槐博匣嘉扶侠扒盐佑懦捡巴汗磐砸疮逞哉高等计算机系统结构高等计算机系统结构为了得到恒等效率，对网格计算机，它的负载必须以指数增长，而超立方体的负载的增长不超过多项式增长速度，结论：超立方体具有更好的可扩展性。 对于相同的效率E，设k = 2，它们的机器规模-问题规模曲线可能如下图所示：问题规模s机器规模n网格超立方体民肤卜环良境痪沾裁噬敦杏物青羡剐暮埃睫掸畦秉岳敦泅冲姨眶边刀售马高等计算机系统结构高等计算机系统结构
