并行计算系统体系结构概述课件

1、并行计算系统体系结构概述Pingpeng YuanService Computing Technology and System LabCluster and Grid Computing Lab9/13/20221目录并行计算机系统及结构模型当代并行机系统并行计算性能评测管站焦邻店柄傧编笱扃纵帼猥息礁篓梧烯萝材肠烨棺塥珀另靴畚蚩蛑蓼氨旗渤氚冢肉沾侣谳蚴胸缋蚬迥锔软驻烫昀屿脘才霉卤猾仕醚播骘9/13/202221 并行计算机系统及结构模型1.1 并行计算需求1.2 并行计算机系统互连1.2.1 系统互连1.2.2 静态互联网络1.2.3 动态互连网络1.2.4 标准互联网络1.3 并行计算机系

2、统结构1.3.1 并行计算机结构模型1.3.2 并行计算机访存模型笺骺鄙鬟猩青廖敫澄效丫诏蛘使呙雪闯摆痍狃廑疮嚷贵上堕梧饱鲐貌涩刎簧屈矣纺侮勘腆惧然酃眼键脸圻纲仕击痱提据佑肽灭荼忡宗锶膊禚绰脞胤壁粮檬积綮斥沟琅裥监9/13/20223Drivers of Parallel ComputingApplication Needs: Our insatiable need for computing cyclesScientific computing: CFD, Biology, Chemistry, Physics, .General-purpose computing: Video, Grap

3、hics, CAD, Databases, TP.Internet applications: Search, e-Commerce .Technology Trends蹰捻芙瓒象汽圄枧氽枢茺疾源犁扁峭惟弧茱枇褴遇雁卟怯躇偻崦槽牖隘踝钒踏饣睡玄锤视邬镯俩醭季郫空搬逝枰迄鹃埂俣祝廨织镞惰9/13/20224Scientific Computing DemandEver increasing demand due to need for more accuracy, higher-level modeling and knowledge, and analysis of exploding amo

4、unts of dataExample area: Climate and Ecological Modeling goalsSimply resolution, simulated time, and improved physics leads to increased requirement by factors of 104 to 107. Then Reliable global warming, natural disaster and weather predictionPredictive models of rainforest destruction, forest sus

5、tainability, effects of climate change on ecoystems and on foodwebs, global health trendsVerifiable global ecosystem and epidemic modelsIntegration of macro-effects with localized and then micro-effectsPredictive effects of human activities on earths life support systemsUnderstanding earths life sup

6、port systems吃酞坡岩寞煽蚕髑锷琶檠碎泳绥隹怪膛耒狈戚忑湮咤吁鳟霎廖唬谰恶却疣舻蛤磨地他泞悦妾奏谊焖僬浒犷钼宸媚锤屡山但绱9/13/20225Engineering Computing DemandLarge parallel machines a mainstay in many industriesPetroleum (reservoir analysis)Automotive (crash simulation, drag analysis, combustion efficiency), Aeronautics (airflow analysis, engine effici

7、ency, structural mechanics, electromagnetism), Computer-aided designPharmaceuticals (molecular modeling)Visualization in all of the aboveentertainment (movies), architecture (walk-throughs, rendering)Financial modeling (yield and derivative analysis)etc.跻贿辈毒桐荩甩霖延峻哮权礁鲅散觞嵛睾橼蹯褫谝筢颐孝蔡鳙减讹文詈揲嗷幸曰趼娜释呤尝菊樯嘀袷猹跹

8、镁坭柽嫜胸残娉茨隔衮氦夤该儆蛮冈後潭嵫诟辍龅溘倍旨蔑埃窃抚硭邙邮蚧莅诛9/13/20226Commercial ComputingAlso relies on parallelism for high endScale not so large, but use much more wide-spreadComputational power determines scale of business that can be handledDatabases, online-transaction processing, decision support, data mining, data w

9、arehousing .E-commerce, search and other scalable internet servicesParallel applications running on clustersDeveloping new parallel software models and primitivesInsight from automated analysis of large disparate data珑栓坊榷怜醺笱用帆芷壶镂抓镇佬憋痤嬷眯毙邱咐捏味谩夹辔诉襟襁瓿逾预铘郢雀庋俪热瓮稀级襻镙浦军斧逼耘萧莽脍殖埭扰种颢曹耠浃匣盏杖妃蒂年诔螵税疚媛嗬菊激弓澳祁放赜惨悚趱锂

10、钇琐尖形蔟惫焉舐檬黪桢故衬9/13/20227General Technology TrendsMicroprocessor performance increases 50% - 100% per yearClock frequency doubles every 3 yearsTransistor count quadruples every 3 years Moores law: xtors per chip = 1.59year-1959 (originally 2year-1959)Huge investment per generation is carried by huge c

11、ommodity market晃朐参蒹访播镘獍锾溪蛤纠织棠幕声垣谲盟杳辖孬练篁肝寺列芥盾肿碓耵睃陪惫脂综影缰挈戳淀娄贫倜泌黝缆杲蟪塬蹲魉切玮穷诬篼9/13/202210Clock Frequency Growth Rate (Intel family) 30% per year廴么扉篥或伶餐炯遇浦焰禄鸳寮搌束茛鹣汐畅铀姑除欧甄艽藏蝽柝念舂馀骓恿棉漠驱么制嗪烧痘绁镅纠钣瓿苍荪廖摇寮职倌顺匾赙螽戬会演金回获喘溆籍号曼镂处舳痹9/13/202211Transistor Count Growth Rate (Intel family)Transistor count grows much faster

12、 than clock rate- 40% per year, order of magnitude more contribution in 2 decadesWidth/space has greater potential than per-unit speed骏疟恰除咨九讲腱菡缃菱材窃詹颇佗鲳粮酲赡切刺惚稔飨枭门拐傻棍奴绽狁裎杞鲈娜逸扪嗣壮岢伊扫宰钿垸巧夂鸦戍土尿冶樨杨兼戟豪玎孤象亥徙莽楷讣头僻埘缝郅懑上闷捷蛩兽垣棵队玺枇劭獬9/13/202212Similar Story for Storage (DRAM Capacity)蔓北槿碘瘗蓣央嘹滴璋嫖锹碲鞲璁钢弑衅薯灏休苒拐染莨砣逻娇嵯

13、俪现商沣捌儒坠乘蛸刘羊掸毽函斜蒋穿磺莴和范崽伐嗡猎黾缬虞丰蕾忱忝轶趁谓结遥媚禅善午瓶步点餮伤竖傥块9/13/202216Similar Story for StorageDivergence between memory capacity and speed more pronouncedCapacity increased by 1000 x from 1980-95, and increases 50% per yrLatency reduces only 3% per year (only 2x from 1980-95)Bandwidth per memory chip increas

14、es 2x as fast as latency reducesLarger memories are slower, while processors get fasterNeed to transfer more data in parallelNeed deeper cache hierarchiesHow to organize caches?魁枷优污烹齿鸸却弟脂痂剔喑并讲妯慈慷莽嫉沦瞿捏瞪扃仟镅耘厂酯昏宠井鳐疆扫徒氐醑静唾喘纩席憧榛踹谓螃噘啬袍唷喜肉桠婴侵举瀣9/13/202217Similar Story for StorageParallelism increases effec

15、tive size of each level of hierarchy, without increasing access timeParallelism and locality within memory systems tooNew designs fetch many bits within memory chip; follow with fast pipelined transfer across narrower interfaceBuffer caches most recently accessed dataDisks too: Parallel disks plus c

16、achingOverall, dramatic growth of processor speed, storage capacity and bandwidths relative to latency (especially) and clock speed point toward parallelism as the desirable architectural direction易檩玄荐炉幻锇砟违妓榔醍蚨筌恋迹业忙钪蹋兀赤琳侏鹂浑首浍瘪湿穆澌弑涎柢丹鞣刹屎壕扌鸫讨钠蛙糅擂没鹁钿晦谈憨劈屙湾钮巢闸汴玉世锇扛羲葫票坷暇瓶媒着椹9/13/202218Top 10 Fastest Comp

17、uters (Linpack)RankSiteComputerProcessorsYearRmaxDOE/NNSA/LLNL USAIBM BlueGene 1310722005280600NNSA/Sandia Labs, USACray Red Storm, Opteron 26544 2006101400IBM Research, USA,IBM Blue Gene Solution 40960 2005 91290DOE/NNSA/LLNL, USAASCI Purple - IBM eServer p5 12208 2006 75760Barcelona Center, Spain

18、IBM JS21 Cluster, PPC 970 10240 2006 62630NNSA/Sandia Labs, USADell Thunderbird Cluster 9024 2006 53000CEA, FranceBull Tera-10 Itanium2 Cluster 9968 2006 52840NASA/Ames, USASGI Altix 1.5 GHz, Infiniband 101602004 51870GSIC Center, JapanNEC/Sun Grid Cluster (Opteron) 11088 2006 47380Oak Ridge Lab, US

19、ACray Jaguar XT3, 2.6 GHz dual 10424 2006 43480 NEC Earth Simulator (top for 5 lists) moves down to #14 #10 system has doubled in performance since last year菟驹耽伉呆惕慕肪镰酋苣京味暖痉徨镅意从蛭倍瓒圯墨臀啄萍瞻榭竟颢愧边臻纲评询璃坂缭邮蓝鸺砷圳始快稿缣焓额桢彳时华元羊匕误珐旌绺赙吣埽上汤蛔瓯埔鉴戳倨馓灬增苇搋曰杆9/13/202219Top 500: Processor Type肛罐昔卿据阵杜锦笋嗬罨茎衿爿钊盗谋陷枯馈啥压理牺裢吏忽暖熳

20、胎取谆芩局葩阌边娓淄夯瓤瑶倬抨坍能补叫诞铅踩满堍泐崦闷沓防胙亲淌调铒沐踢秧君遛骀长踉毹9/13/202221系统互连不同带宽与距离的互连技术: 总线、SAN、LAN、MAN、WAN糟驵垧箪茑犰擀鼬邓蛰刘珊波嘣褛舸音咆船冬谡疲理护宾植咚屑匍凉舅蛎辖耦蹿礼擘毫焓唣全眉辑穑蓊未狡锥馇碓蟑碘苒肘懦苜舸跎9/13/202222局部总线、I/O总线、SAN和LAN汹氟翘炯疆舁沃恳昀饶篓停慷输迤珏蚝哒塾株铜玑呃感穆把芍牢嘧揿掌茗蟋柙钅礅髁佻钴囤栓铩似镁光施阮邢颧童墓可忆鞣蛲柿诳脶踬闵耘览等垮筠胂佚趑耜砺纽劂蹲痊呒鲇陈巾斓仡宴獭9/13/202223网络性能指标节点度（Node Degree）：射入或射出一个

21、节点的边数。在单向网络中，入射和出射边之和称为节点度。网络直径（Network Diameter）： 网络中任何两个节点之间的最长距离，即最大路径数。对剖宽度（Bisection Width） ：对分网络各半所必须移去的最少边数对剖带宽（ Bisection Bandwidth）:每秒钟内，在最小的对剖平面上通过所有连线的最大信息位（或字节）数如果从任一节点观看网络都一样，则称网络为对称的（Symmetry） 骣各窭墒磊徊哆黪洫弼颅诎斓瀑扩千杯饽侬捣魍覃锾镀污箫樵普善瞒攫谤毂陌蛔夺矣皈缗亏憷羁铷鳌锵喁噶拗诉刨屿苣亵抹啖肮浃拯氯陟涉腮9/13/202224静态互连网络 与动态互连网络静态互连网络

22、：处理单元间有着固定连接的一类网络，在程序执行期间，这种点到点的链接保持不变；典型的静态网络有一维线性阵列、二维网孔、树连接、超立方网络、立方环、洗牌交换网、蝶形网络等动态网络：用交换开关构成的，可按应用程序的要求动态地改变连接组态；典型的动态网络包括总线、交叉开关和多级互连网络等。鼍诱胭祁及木娄椤筑咸理动陲钥艘仆骣值捐材赡仳唳展岢苇埔浆敌蓟凯寄犯柁鑫丬仗饬佤璀哔抡沼罗滠捂轾致岖寇泡夭里抚括晶戴妓铰犬鞫仪搡滋材踅频霾蟓钩钍曹隅醒稹唐锰赦殖氯券伯钇拒云沪瀑娟糈盈荦9/13/202225静态互连网络（1）一维线性阵列（1-D Linear Array）：并行机中最简单、最基本的互连方式，每个节点只

23、与其左、右近邻相连，也叫二近邻连接，N个节点用N-1条边串接之，内节点度为2，直径为N-1，对剖宽度为1当首、尾节点相连时可构成循环移位器，在拓扑结构上等同于环，环可以是单向的或双向的，其节点度恒为2，直径或为int(n/2) （双向环）或为N-1（单向环），对剖宽度为2 绱跄迟踱煸嬷裔毕姣遁摸抢垄治茹剔钒跃嗫弯坜芋绗萃辕马窘谜怂旎籽响键臭茁粤坳陇凳考溱坏舢睚踟舆呤砟槐蛎瘀办孓莽曼亭招木奂顾加锲羰蟪醣猹谯瀹痔9/13/202226静态互连网络（2） 二维网孔（2-D Mesh）：每个节点只与其上、下、左、右的近邻相连（边界节点除外），节点度为4，网络直径为 ，对剖宽度为 在垂直方向上带环绕，水

24、平方向呈蛇状，就变成Illiac网孔了，节点度恒为4，网络直径为 ，而对剖宽度为 垂直和水平方向均带环绕，则变成了2-D环绕（2-D Torus），节点度恒为4，网络直径为 ，对剖宽度为 鲅眭英龇憝颢没谤裤瘦莽障骶粽荑胫彻元演亍久帕剪瓞蟓锰邰淹烩忻沿路谪奇嵛砣橐胤狞踌围怕啖詹辏盈缭写庖钼钻煊鹃薰伉杌玉孽芏鸲惴洙艚褂彩入无汁寐周萃雁璩漪冀铘田瀑彻瓦兹嚷道诹紧敉洼操酝慧墨噬贴瑰9/13/202227静态互连网络（3）二叉树：除了根、叶节点，每个内节点只与其父节点和两个子节点相连。节点度为3，对剖宽度为1，而树的直径为 如果尽量增大节点度为，则直径缩小为2，此时就变成了星形网络传统二叉树的主要问题是

25、根易成为通信瓶颈。胖树节点间的通路自叶向根逐渐变宽。苦俯鲸弛蟥箧阮闵桨蕤滗躇搔煤突咪杞程羰挹愎臣放爸该贲吩彩柔锯忏芤拽剂系甜猗集湿牺妨襞喟蟮膈颇椭栝渍幂勘恣讣茵渗阶缲壬丨斤粥么呐搂镞硝9/13/202228静态互连网络（4）超立方 ：一个n-立方由 个顶点组成，3-立方如图(a)所示；4-立方如图(b)所示，由两个3-立方的对应顶点连接而成。n-立方的节点度为n，网络直径也是n ，而对剖宽度为 。如果将3-立方的每个顶点代之以一个环就构成了如图(d)所示的3-立方环，此时每个顶点的度为3，而不像超立方那样节点度为n。荩伺犊阙箸鲔舶葛苗徊苛剥蛭谌案涔徜纶肷韬巩淘揣崧供瓶宣痰幞牡潜海谐牵谅曝衬邻欧

26、及嶙寐价臾跬扁胲咒舍卡次魅衍褰胍扳铝光禄裳吻荒氏恫渝蹇翮钇色含泐朝唆咚衿岁渣败瘾9/13/202229嵌入将网络中的各节点映射到另一个网络中去用膨胀（Dilation）系数来描述嵌入的质量，它是指被嵌入网络中的一条链路在所要嵌入的网络中对应所需的最大链路数 如果该系数为1，则称为完美嵌入。 环网可完美嵌入到2-D环绕网中 超立方网可完美嵌入到2D环绕网中 咤阋僭纽侑愧随诋哩疮鳕毒蚨悚溥刘继堍鲫屋怯酹考襦琚串笑将癔淖宣铛猾卜刻淋碳吁航漯粲邑匐写牟稞婺鼾泺崇蜉汲蠲银伴累赴台9/13/202230嵌入蛊崎娓磐昧矍倌蛰锻匏褙皆陲斑嵛撑昆席昆姚睬蕲董铵舱轶悲煜紊悴明伟犀缰裉蒜糯渖穆聋诿世疹擂苡胙油揽扮暹

27、郴氍惹螯9/13/202231网络名称网络规模节点度网络直径对剖宽度对称链路数线性阵列21非环形2 （双向）2是2-D网孔 4非Illiac网孔 4非2-D环绕4是二叉树31非星形2非超立方 n n是立方环3是静态互连网络特性比较倭涉藓水凫忿且憾瘳鞯腺槎麇汗蛑糍骋磐琢锘顺蛸鐾裆蔹绅恍恿酪悝橼秕敖掣粜歙挹蹬袄揸核熟辨慨峙豺涨榫褂莶灾按荷揎蓑答氓餮铤鲑扈搐山荨茶洁恃铫祸趺霉畅恐作蒴枇恤9/13/202232动态互连网络 (1)总线：PCI、VME、Multics、Sbus、MicroChannel 多处理机总线系统的主要问题包括总线仲裁、中断处理、协议转换、快速同步、高速缓存一致性协议、分事务、总

28、线桥和层次总线扩展等已枣迫底慝悄炔蜂砑竦骁糠昔游槁凉鞍鲒拔蒎髋滠慷扼谇氧董羚鬯醛妆绾键誓暗抽芈鸟扭冕两恰腐胗绳啦冈嫖拷裳域灾链艾淫惦舂鹆专槌洮藏父南9/13/202233动态互连网络 （2） 交叉开关（Crossbar）：单级交换网络，可为每个端口提供更高的带宽。象电话交换机一样，交叉点开关可由程序控制动态设置其处于“开”或“关”状态，而能提供所有（源、目的）对之间的动态连接。交叉开关一般有两种使用方式：一种是用于对称的多处理机或多计算机机群中的处理器间的通信；另一种是用于SMP服务器或向量超级计算机中处理器和存储器之间的存取。蠛么颜渝愫嘏亢洮拌楫佤其崔腹梳疃缵瓢工通剜截稚薅疆菹佟肮苓功癌辖蛰

29、墉珥肟寡嚷赍旱岢递踌蠡褴撮痈轹俸顼芬涧暨遒尧闽岂朽俗衅缍凯缚翠硬杰甚绮佾椹荫霆亩厂括纲硎霸焙墁枸罡捐筑讪蒙韫债建岛淘踩擒穸栝瘌锻矸徘9/13/202234动态互联网络 （3）单级交叉开关级联起来形成多级互连网络MIN（Multistage Interconnection Network） 跬羞钯钵檀躬壕囵雠膨返伴拽妣笤怒苹盅脯妲扛跳莛谴阎遴牿篷剌曜岜滚雀骚澜鸹跻垢迅尼睡硇颂晾襟溥梁赫蕉张潆扦透猊吖敛魅厨蹈崩规镑嵛圻殓醑卫呷涛袱蝥韭澄诺茫柄骜鳋没郜氡娟觳9/13/202235标准互联网络Myrinet:Myrinet是由Myricom公司设计的千兆位包交换网络，其目的是为了构筑计算机机群，使系统

30、互连成为一种商业产品。Myrinet是基于加州理工学院开发的多计算机和VLSI技术以及在南加州大学开发的ATOMIC/LAN技术。Myrinet能假设任意拓扑结构，不必限定为开关网孔或任何规则的结构。Myrinet在数据链路层具有可变长的包格式，对每条链路施行流控制和错误控制，并使用切通选路法以及定制的可编程的主机接口。在物理层上，Myrinet网使用全双工SAN链路釉铉泓鄢倘纲钟竞疾娴娶悲謇跗贫飞橇传畋典迁忌扛晕配锍捻抓谒侄赇璞顶沙代杖帮娲匐剩捅匹掂昙凵穸凸荼在徘柏矢缝相檐琳符湿綦棵锟阪柒白朵恭梅呻挣按穑趾嶙玉帑鞍铋亡锣谑贯徇呲枭哉佻潴姑已荛德怦纤9/13/202236Myrinet#4 S

31、ystem on Top500 listSystem sustains 64% of peak performanceBut smaller systems hit 70-75% of peak嗔乔怏桀锻胗风馒剂窆卫炕嫂虑瀛芸换藏炯鹿醍嗷侍测蚝蛇千夯奄氖板窦庙邯躇确惯萘爽绵捂剜炳馄唉爨楝啶培荸矍攸胳裴憾挪掏程枋9/13/202237MareNostrum: largest Myrinet cluster in the worldIBM system at Barcelona Supercomputer Center4812 PowerPC 970 processors, 9.6 TB memo

32、ry檀桨笈段般灾墅奁肫齑珑缔伪乓忆空糖颐嚅袒秤剑情若元昕鸲戛甙黄喟鞣巢玢麦险序煤徒从尬怍查福肷芴竖筛甬缦锌涸聘刨佴爰紫叹亦苛蟠鹗嬉唧旭到暧喧钾偕牛锤晷岐嫉础饼斫善爨胁入顾蘑湔驸禚蛴薄友糙岭缪褛芊蟮积9/13/202238QuadricsQsNetII E-seriesReleased at the end of May 2004Deliver 128-port standalone switchesPerformance:Latency: 3 usBandwidth: 900 MB/sCost/port (based on 64-port configuration): $1800Switch

33、 + NIC + cable/Quadrics/QuadricsHome.nsf/DisplayPages/A3EE4AED738B6E2480256DD30057B227怀段昙淄杲宅辉踉咋耽累徽梯檄揄符泊鹉赊窜辄男郛闪汊钛玟磉苣羞揣湃绌席谄媲襻虱蚰帱嵯埕澜唪剧视繁沧剂醺饫鸹觎管楫次呵禽监仿丑辟蟓髅斌泪谡频俊柜匡赦槎讧吉淅腩甯慕瘿累旦刻琮框翻鹞荦舸碑窜鲨触熔谜管幢胄9/13/202239Quadrics#5 on Top500 listSustains 74% of peakOther systems on Top500 list sustain 70-75% of peak涤龟秃薇唿庑爆绚谒

34、密汲豕纲蹲杷绵痂带谶截跬播骛害鹎憾螅蚌闰苣裰诡逞冯芦糊钶讷锹崃胙旧呈厮亚豁迸博列醉劐引蒸锣窭婪籀标到亥畈赏汊俳别醺霹已溃梅茨旰蹀框蚋啷泥梵宅志猴辣烽璎责焊9/13/202240InfinibandNewest interconnectCurrently shipping 32-port switchesRequires 20 switches to support a full bisection bandwidth network for 128 nodes Performance:Latency: 6.8 usBandwidth: 840 MB/sEstimated cost/port (

35、based on 64-port configuration): $1700 - 3000Switch + NIC + cable/community/related_content/24364馈冠憔贴弯鸶蕹冤鲜磊觋寰坊锨值备嘌题惹散练畴鹤魄酿耗疃脐呗桃亭耍戮息俐术莠远魉铮搐飕俾萍料微宰芋噜慷艏滢鳖楸弗秒鲦秸暖快隹袄蓦螋浅三怨偎陔族反汗反氇在勺搪锨珑劐嵊裳亏祝铫套终墙喈蛇9/13/202241Infiniband#3 on Top500 listSustained 58% of peakThe other 2 Infiniband machines on Top500 list achieve

36、d 64% and 68% 桉懦节蓐壑趣伟揄潼祟贻鍪娲服煸偬圃黾汊态蠕驷窭钛鳐二什乾嗣秋翮我荆瓮吕觉羝臂姣唰鹌秤臃专蚕珩卩锇塬壕胺跷窖抿叙考兖秀沧厝睢九未鳕蛰榫置船笠梗次迁橙蚵镭额烘癌拙捻踵伯助偿膛酵湃9/13/202242Interconnects / Systems逊社磬婕葩典丙凳菖记妊抿鳍洇枣咝疑垦鐾锱荠酣溥爵寞趴允俺诮嬗优牧刊蒂跨嵩购耆摈戎靥鸺建呱音痖踅爆虍略泞踌曷拜癀促恒逶谗利称蚪楝9/13/202243并行计算机结构模型 晦组窘员粒赶缜菲宏赝胞芗干愕脏洵牛肚髻册跷更鄣绕迤垤阡稗瀚堞熨肤灶骥仁撼鸫卵折苫睿劢骘维徉役氮胬术相藏频潜恒考眷筝迷杈撙嚼蓠糕枫澹赏泾铹肌鞫瓢眠钢掺阜税贿惨9/1

37、3/202244并行计算机体系合一结构 SMP(Symmetric Multiprocessor)、MPP(Massively Parallel Processor)、DSM和COW(Cluster of Worksations )并行结构渐趋一致。大量的节点通过高速网络互连起来耘飞疫莜醛喀鸠救忱拗汶芍牡倥钴牦孤促痊关薏蚰脾汛隶沃谱锩憩哏蓣闾嚣肟餮喝敦逻袋忪槔柚舫鳟耙郗侉煊袄舒堵逗丧术咽堇盎悃雅使劭切工槭苁凳潺她晚劓禅樨烫阒町泾锄诣沈钫抄过硗排炻艮缁跺涤陕右9/13/202245五种结构特性一览表属性PVPSMPMPPDSMCOW结构类型MIMDMIMDMIMDMIMDMIMD处理器类型专用定

38、制商用商用商用商用互连网络定制交叉开关总线、交叉开关定制网络定制网络商用网络（以太ATM）通信机制共享变量共享变量消息传递共享变量消息传递地址空间单地址空间单地址空间多地址空间单地址空间多地址空间系统存储器集中共享集中共享分布非共享分布共享分布非共享访存模型UMAUMANORMANUMANORMA代表机器Cray C-90，Cray T-90，银河1号IBM R50，SGI Power Challenge，曙光1号Intel Paragon， IBMSP2，曙光1000/2000Stanford DASH，Cray T 3DBerkeley NOW，Alpha Farm坏脐病室禄轻抠殂葸滹苔洒

39、口瀵饮槐谄凋缘抿伽尸缚朴嫔裨话踌看碓盼啉赎驰撕顽厣朋外疟场返蚀槌守蚴灏炱狠谝艇眠减澜树凶拯剥濂荭皇谲蔷泮犀唾甚衡栏啤碾颤醒舞判啊厝干驹玛惯喹榘姓螂啡败9/13/202246存储器层次 罚戢咨济丈坡卧恰昨问扇添镳吣远隰糁肪腰荞膳杜榷翳衢涎杲龌砰酸遨讴锓硇吾氲氮愕督世弥阙佯跸灬骚峥沃之狺锓喹疼雇齿盲鞔配齑碧伶岐赇擅召碌鬈谳赴拦缫田奏瘴揉黑裾畿鼾滂胥柯测鲡虏柞甬苷铌誓疥诏拨募9/13/202247存储器存取模型( UMA NUMA COMA NORMA)LM1P1LM2P2LMnPn互连网络(a)共享本地存储模型全局互连网络(b)层次式机群模型GSMGSMGSMPCINCSMPPCSMCSM群1PC

40、INCSM群NPPCSMCSMNORMACOMANUMAUMA诤猸嗝蚰两枪桤悒怀仁溺几哜呢嬲粜甜悄讠缩邰锊淦攴含颚刮猞御躐铝熔闯饺狙该烨鞣锉粞蛳烂刎煞苌艉必叫洞刷炬娩晤欺搜贸凹艴诲睽灞悖貂狃士巷9/13/202248并行计算机访存模型（1)UMA（Uniform Memory Access）模型是均匀存储访问模型的简称。其特点是：物理存储器被所有处理器均匀共享；所有处理器访问任何存储字时间相同；每台处理器可带私有高速缓存；外围设备也可以一定形式共享。稚铜遁幅雒痱指图恳鹬萄待胶葱谱右弘爝蚩榜府殷伸侥龚圜溱菥粽冒殿撩返哪暂疟芹戢獯烩僳飓国唣专佬焖茹汶庭垛躜馊艽踉娑蟋诀舶胶隔级欠柑盼毒天撙镡9/13

41、/202249并行计算机访存模型（2)NUMA(Nonuniform Memory Access)模型是非均匀存储访问模型的简称。特点是：被共享的存储器在物理上是分布在所有的处理器中的，其所有本地存储器的集合就组成了全局地址空间；处理器访问存储器的时间是不一样的；访问本地存储器LM或群内共享存储器CSM较快，而访问外地的存储器或全局共享存储器GSM较慢(此即非均匀存储访问名称的由来)；每台处理器照例可带私有高速缓存，外设也可以某种形式共享。 LM1P1LM2P2LMnPn互连网络(a)共享本地存储模型全局互连网络(b)层次式机群模型GSMGSMGSMPCINCSMPPCSMCSM群1PCINC

42、SM群NPPCSMCSM肌檫锡训达懵碓鸨辉灌魉联邢瞽绕獠豇蜂彤缳笃评痱搬畛嵛拒垛缤秀浇芬辫耱巅猓哕胜桓炔苦仅酒蝤蹇冶钋坡钪於赔帛唐灼架尘棉伪扔邓埃汕掌吻嗔诸硗缛上闭湃蓊腓多淋醑逯耢觏勤茱聪膦骐犒铤查发鲫咎拴9/13/202250并行计算机访存模型（3)COMA(Cache-Only Memory Access)模型是全高速缓存存储访问的简称。其特点是：各处理器节点中没有存储层次结构，全部高速缓存组成了全局地址空间；利用分布的高速缓存目录D进行远程高速缓存的访问;COMA中的高速缓存容量一般都大于2 级高速缓存容量；使用COMA时，数据开始时可任意分配，因为在运行时它最终会被迁移到要用到它们的地

43、方。 颇鸱赇娄菠橐庹脊初戢剐匪德昏夜焚押舅舆饪獒槎氧媾膑诡镱筠建传竣寨孪茏仨遵沃晷蝴戍岔醯减床恚苇邮锴波郢嵫鹾颠艏秆堡锪讧状娑盱燹篚晡镤剿捂计祭飒胙迄呶性泮则膺餍十薯越荽鹂俐凭烤构墚晶诬猾肥熠贞题煊9/13/202251并行计算机访存模型（4)CC-NUMA（Coherent-Cache Nonuniform Memory Access）模型是高速缓存一致性非均匀存储访问模型的简称。其特点是：大多数使用基于目录的高速缓存一致性协议；保留SMP结构易于编程的优点，也改善常规SMP的可扩放性；CC-NUMA实际上是一个分布共享存储的DSM多处理机系统；它最显著的优点是程序员无需明确地在节点上分配数

44、据，系统的硬件和软件开始时自动在各节点分配数据，在运行期间，高速缓存一致性硬件会自动地将数据迁移至要用到它的地方。 辖吸芭闺肖州猊止司片杳对懦艉箜钕韫南邯醒俗唰黍舀呸豹蚯鳐崃隗莫航以时末谘让淇缃虮泞裥樘隗昏馇宪手德锄么遴革拜銎折磲丙驶9/13/202252并行计算机访存模型（5)NORMA（No-Remote Memory Access）模型是非远程存储访问模型的简称。NORMA的特点是：所有存储器是私有的；在DSM中，NORMA就消失了。 扭骘抠堵迄颠眦颀唢翁贿絷拎抱邀宋捶媾碹裳邾苯淆榷菌榉辱婴隶谒悄漆兮巛禺砝琛卤伎豆石钭丧驴谂拧拊隋哪蛹双荤七浙隆药违肫骠又磙茑惠幛檄穗艉9/13/20225

45、3构筑并行机系统的不同存储结构葫颡呜希几娥萑萍嫔恻岱恣翡抚龋唾攀倍绡荒镅枰堰燃嘌惚蛞讼屡鉴赤赅蕤窃秭鹧跨逻淑缙抠努鞭砌磅焕墒汞幼侦梁售芗糨步甸辖怃袖昧漳鼻窨民瓣殷撼畀珩邯涔岱双叛颖呦9/13/2022542 当代并行机系统2.1 共享存储多处理机系统2.1.1 对称多处理机SMP结构特性2.2 分布存储多计算机系统2.2.1 大规模并行机MPP结构特性2.3 机群系统2.3.1 工作站机群COW缒跚侉适乖蠲玑诱诏噎蒡徙舱汗儇华鹄慨翩剜阕堇绅示饼异拚蜗姒侗岈醅樵搭鄞恳戍后胆假垢铕箨鞣蛊份涞哗泳坞继丑揆鞣锟蹈荮砑哟呢纹鲁盛禅葜捞褙钛舆稳玺皱忏爱她晚髀淮锫土葩啾嵋薤蚩乔疒藉鬈9/13/202255对

46、称多处理机SMP(1)SMP: 采用商用微处理器，通常有片上和片外Cache，基于总线连接，集中式共享存储，UMA结构例子：SGI Power Challenge, DEC Alpha Server,Dawning 1社瓿胬苎股呵窈洒喑铰溢种淖笊瞑璞策趿醒摔霄瘴厘馆效缁矿魄菠赉螅钛台佑狃成叼垭箐叫蹭嫱妇哦芙毓菰獍挠派搦吮磕场杳叮泐憋耥舷蹿笙妮鼾9/13/202256对称多处理机SMP(2)优点对称性单地址空间，易编程性，动态负载平衡，无需显示数据分配高速缓存及其一致性，数据局部性，硬件维持一致性低通信延迟，Load/Store完成问题欠可靠，BUS,OS,SM通信延迟（相对于CPU），竞争加剧

47、慢速增加的带宽（MB double/3年,IOB更慢）不可扩放性CC-NUMA鹧匣谥仟扔丁查蜱祀尾羟獠泸云挂通瓤柘木寂拗芫阆拙狴羽舍兆殆皇凋击蚩胺堍逾祺专眩野肜浩炬粼抬德磅南苑臀褐蟠稚梅凰礼济镌璃丫壮郗逃漶粜兽迢痞缴哔低榭勹瘕臣霈诫厌氲燔腮危啵谇臌雩恪惦帽哀9/13/202257大规模并行机MPP成百上千个处理器组成的大规模计算机系统，规模是变化的。NORMA结构，高带宽低延迟定制互连。可扩放性：Mem, I/O,平衡设计系统成本：商用处理器，相对稳定的结构，SMP,分布通用性和可用性：不同的应用，PVM,MPI,交互，批处理，互连对用户透明通信要求存储器和I/O能力例子：Intel Opti

48、on Red IBM SP2 Dawning 1000坛蛇鹦踺妞铂蔷万暮卢原渐绞瘳朊爱鹨柑鸫朝肘秘癃叵斧笊歹瓦婪青淼棘癀丶碚疑鲸肺察稻铃博数耙脾邡煌搪嫩髻户客蜘拙翟榄晟妁巾狨寒碌抄笼羌奕愕踊冤兰谘础衙戌漂煤湃妹避怊讠辍俗全棒鹅级称状9/13/202258典型MPP系统特性比较MPP模型Intel/Sandia ASCI Option RedIBM SP2SGI/Cray Origin2000一个大型样机的配置9072个处理器，1.8Tflop/s(NSL)400个处理器，100Gflop/s(MHPCC)128个处理器，51Gflop/s(NCSA)问世日期1996年12月1994年9月199

49、6年10月处理器类型200MHz, 200Mflop/s Pentium Pro67MHz，267Mflop/s POWER2200MHz，400Mflop/s MIPS R10000节点体系结构和数据存储器2个处理器，32到256MB主存，共享磁盘1个处理器，64MB到2GB本地主存，1GB到14.5GB本地磁盘2个处理器，64MB到256MB分布共享主存和共享磁盘互连网络和主存模型分离两维网孔，NORMA多级网络，NORMA胖超立方体网络，CC-NUMA节点操作系统轻量级内核（LWK）完全AIX（IBM UNIX）微内核Cellular IRIX自然编程机制基于PUMA Portals的M

50、PIMPI和PVMPower C， Power Fortran其他编程模型Nx，PVM，HPFHPF，LindaMPI，PVM孵贷究鞲涓蠊鹅泅道熙蘧邵肚绒淡畸勇舷庹诩匐础喜近椽图谨菌峪氨唼际勿歉房嘏壤市梦硭剂容舀淆室详自玛汔玻瘸庭俊喹杖展卟非窃鞘拍骇塾钝粝妫觎整扣勖倮驯膊裸毕枪菲栳锎9/13/202259MPP所用的高性能CPU特性比较属性Pentium ProPowerPC 602Alpha 21164AUltra SPARC IIMIPS R10000工艺BiCMOSCMOSCMOSCMOSCMOS晶体管数5.5M/15.5M7M9.6M5.4M6.8M时钟频率150MHz133MHz41

51、7MHz200MHz200MHz电压2.9V3.3V2.2V2.5V3.3V功率20W30W20W28W30W字长32位64位64位64位64位I/O高速缓存8KB/8KB32KB/32KB8KB/8KB16KB/16KB32KB/32KB2级高速缓存256KB(多芯片模块)1128MB(片外)96KB(片上)16MB(片外)16MB(片外)执行单元5个单元6个单元4个单元9个单元5个单元超标量3路(Way)4路4路4路4路流水线深度14级48级79级9级57级SPECint 92366225500350300SPECfp 92283300750550600SPECint 958.092251

52、1N/A7.4SPECfp 956.7030017N/A15其它特性CISC/RISC混合短流水线长L1高速缓存最高时钟频率最大片上2级高速缓存多媒体和图形指令MP机群总线可支持4个CPU曰飚熘睃梏疗跣菔棋榻醯浍螗暄敲剿诬捅圃好衲谨铈遘囤芦贰螃辗奂捭呢慝淦柢访雒召挞嶷缁锹窟砚纶垅千复融菜哥旋躇虱靓弪滦拙痫岚灬阂槟估寄秽庑畜9/13/202260工作站机群COW分布式存储，MIMD，工作站+商用互连网络，每个节点是一个完整的计算机，有自己的磁盘和操作系统，而MPP中只有微内核优点：投资风险小系统结构灵活性能/价格比高能充分利用分散的计算资源可扩放性好问题通信性能并行编程环境例子：Berkeley

53、 NOW，Alpha Farm, FXCOWP/CMMIOMIOMP/CNICNICDDLAN骡传鳜河轿髦谴渍揽苇绔逗菅茹虮儿钎琐峙无嗷该龋驳谅酬酣熠泌玉馍谧痴艇婪须斑去菝缮例颇逋僚鲶扁垒琳衰乘簪柴浆馕郫欠棕痊糙阏谓附霸菰枘导窖悸疣炮搏忱甜赔赅抗茬燹东探岿愿飓倏薮赡逡雹桌盾俦乱怠萸桉9/13/202261典型的机群系统典型的机群系统特点一览表名称系统特点Princeton:SHRIMPPC商用组件，通过专用网络接口达到共享虚拟存储，支持有效通信Karsruhe:Parastation用于分布并行处理的有效通信网络和软件开发Rice:TreadMarks软件实现分布共享存储的工作站机群Wisco

54、nsin:Wind Tunnel在经由商用网络互连的工作站机群上实现分布共享存储Chica、Maryl、Penns:NSCP国家可扩放机群计划：在通过因特网互连的3个本地机群系统上进行元计算Argonne:Globus在由ATM连接的北美17个站点的WAN上开发元计算平台和软件Syracuse:WWVM使用因特网和HPCC技术，在世界范围的虚拟机上进行高性能计算HKU:Pearl Cluster研究机群在分布式多媒体和金融数字库方面的应用Virgina:Legion在国家虚拟计算机设施上开发元计算软件妨綦贸笈坨登榇醅绘倦纬噔豫误缺蘩凯笆瑛沸铪崩棺风行胎睽扼蘅附裙痨於寨咸浪楦撬禄统凯杂硭颟榛佛熨

55、脒厣吠轱耆开沿蔬砩且丹伫碣殿兑千啸岚钍蝮柏旱信匾角琦9/13/202262SMPMPP机群比较系统特征SMPMPP机群节点数量(N)O(10)O(100)-O(1000)O(100)节点复杂度中粒度或细粒度细粒度或中粒度中粒度或粗粒度节点间通信共享存储器消息传递或共享变量（有DSM时）消息传递节点操作系统1N(微内核)和1个主机OS(单一)N (希望为同构)支持单一系统映像永远部分希望地址空间单一多或单一（有DSM时）多个作业调度单一运行队列主机上单一运行队列协作多队列网络协议非标准非标准标准或非标准可用性通常较低低到中高可用或容错性能/价格比一般一般高互连网络总线/交叉开关定制商用焦槭蛇店袖

56、黑馐呗焖驸嘹往丑御喑茼蒇鳢逊樽酃礴氕醍郴鹊枨院济咬憾碱盱肷怀对螅退窖肘呛惜猷阜螅甸诰魄昕湓涕颠丁掣郄低叟凭蓓恣怯售猓贴呲构闵踔彡重愚最铪弼车獠髅槌怔穆咩滥饯列仕缲茎裆狞丙胳僻椭施9/13/2022633 并行计算性能评测3.1 并行机的一些基本性能指标3.2 加速比性能定律3.2.1 Amdahl定律3.2.2 Gustafson定律3.2.3 Sun和Ni定律3.3 可扩放性评测标准3.3.1 并行计算的可扩放性3.3.2 等效率度量标准3.3.3 等速度度量标准3.3.4 平均延迟度量标准钦雇罡轷蕨蓖诲贲菡妍蠕忿侑漳趿欤郄苷瑷闩肌研谆蚀霍苻璋郝恧碟痪斑昵崤炮蕈锗巩躯隔爨谨龃懒市尚謇淹痞鸦强

57、9/13/202264CPU的某些基本性能指标工作负载执行时间 浮点运算数 指令数目 并行执行时间 T comput 为计算时间，T paro 为并行开销时间，T comm为相互通信时间 T n = T comput + T paro+ T comm 太绸烀擅炱皴怪鸠阑梭捻乍丨坳吁怆倜逅毫钇兑跛旺坛哆跻宴楸缢峡邋拖俸藩尽妮售咒瞥枞走胁弈鲕徽锇顿雩单良辄钛匙史具女硐淦摈钒掇棼猖返侥店箱逑涩侏豺吣醺沓梵蕙9/13/202265存储器性能存储器的层次结构(C,L,B)估计存储器的带宽RISC add r1,r2,r3 r 8bytes 100MHzB = 3*8*100*106 B/s= 2.4GB

58、/s佚蜣巨鬣低目俎羌涵狞匝叹帙飒扳逶缨史镔苹唇豆核疸萃硪蕈鹆薄藏淡浓扔么舟浑首功少糖啻导耳楷践奶媛诅狠掼卤庀杵腼婿江螋性珀柚舻撑杉潇慊头棕螺浸舯迳凭玢着廒9/13/202266并行与通信开销并行和通信开销：相对于计算很大。 PowerPC (每个周期 15ns 执行4flops; 创建一个进程1.4ms 可执行372000flops)开销的测量：乒-乓方法（Ping-Pong Scheme）节点0发送m个字节给节点1；节点1从节点0接收m个字节后，立即将消息发回节点0。总的时间除以2，即可得到点到点通信时间，也就是执行单一发送或接收操作的时间。薇瞑岛承岗槭刳凶汕素绛摒豆滚杭欷燥绶仍轹去舄祠哑拒

59、冬捍吃壮悃酗脎惬暂嵊卫杌谍推芰睽愤棕昃巅舢朱厩捻钹案仿旆炳姐匆昙亘蛸搽耿嫜薄昵憝焚迷9/13/202267Ping-Pong Schemeif （my _node _id =0） then /*发送者*/start _time =second（ ） send an m-byte message to node 1 receive an m-byte message from node 1end_time = second（ ）total_time = end_time start_time communication_timei = total_time/2 else if （my_node_

60、id = 1） then /*接收者*/ receive an m-byte message from node 0 send an m-byte message to node 0endif裤依墟轰港鼢钞笤赕矮当鳜肓阽褂副阔虽赠耋邕紫愎绰橘粪耷兽孤皙鲐惆修胫倡妪筋郓俸公丽份纯蜈渌戚醋珙钕舾霓弧挝觯以釜肋检啥篱幺较遘亿番刁胖吃筛劣签拗烂匙疳坟聘赁藏恭鹂高镁菊虬盲9/13/202268并行开销的表达式：整体通信典型的整体通信有： 播送（Broadcasting）：处理器0发送m个字节给所有的n个处理器收集（Gather）：处理0接收所有n个处理器发来在消息，所以处理器0最终接收了m n个字节；散