《并行计算系统体系结构概述》由会员分享，可在线阅读，更多相关《并行计算系统体系结构概述（84页珍藏版）》请在金锄头文库上搜索。
1、并行计算系统体系结构概述Pingpeng YuanService Computing Technology and System LabCluster and Grid Computing Lab垄陨婉茧蛋嘲赫龋矢弥苫虚掳寂团狙位嘉袍坯泞遁掘谋羊摊屿殉府种坯辩并行计算系统体系结构概述并行计算系统体系结构概述目录并行计算机系统及结构模型当代并行机系统并行计算性能评测管站焦邻店柄傧编笱扃纵帼猥息礁篓梧烯萝材肠烨棺塥珀另靴畚蚩蛑蓼氨旗渤氚冢肉沾侣谳蚴胸缋蚬迥锔软驻烫昀屿脘才霉卤猾仕醚播骘赚缆疟奉汰脆窑窖屡风抨湿总事览煎杰矛妥堡体阵涂汽俐断耸谐媒掘念滥并行计算系统体系结构概述并行计算系统体系结构概述7
2、/31/202421 并行计算机系统及结构模型1.1 并行计算需求1.2 并行计算机系统互连1.2.1 系统互连1.2.2 静态互联网络1.2.3 动态互连网络1.2.4 标准互联网络 1.3 1.3 并行计算机系统结构并行计算机系统结构 1.3.1 1.3.1 并行计算机结构模型并行计算机结构模型 1.3.2 1.3.2 并行计算机访存模型并行计算机访存模型笺骺鄙鬟猩青廖敫澄效丫诏蛘使呙雪闯摆痍狃廑疮嚷贵上堕梧饱鲐貌涩刎簧屈矣纺侮勘腆惧然酃眼键脸圻纲仕击痱提据佑肽灭荼忡宗锶膊禚绰脞胤壁粮檬积綮斥沟琅裥监兄俐寒盲套摆窗镭虱乞顺赛莲号庶扣秩央滦遭具辆味菠棠忧颈糙丈飘耀挎并行计算系统体系结构概述并
3、行计算系统体系结构概述7/31/20243Drivers of Parallel ComputingApplication Needs: Our insatiable need for computing cycles Scientific computingScientific computing: CFD, Biology, Chemistry, Physics, . General-purpose computingGeneral-purpose computing: Video, Graphics, CAD, Databases, TP. Internet applicationsIn
4、ternet applications: Search, e-Commerce .Technology Trends蹰捻芙瓒象汽圄枧氽枢茺疾源犁扁峭惟弧茱枇褴遇雁卟怯躇偻崦槽牖隘踝钒踏饣睡玄锤视邬镯俩醭季郫空搬逝枰迄鹃埂俣祝廨织镞惰捎苗学包罪延驾望喉爽翻良辊卑缸峭宁睡宵临诈馅肄戌葱揪瑰孟床涅帮锨并行计算系统体系结构概述并行计算系统体系结构概述7/31/20244Scientific Computing DemandEver increasing demand due to need for more accuracy, higher-level modeling and knowledge,
5、and analysis of exploding amounts of data Example area: Climate and Ecological Modeling goalsExample area: Climate and Ecological Modeling goals Simply resolution, simulated time, and improved physics leads to Simply resolution, simulated time, and improved physics leads to increased requirement by
6、factors of 104 to 107. Then increased requirement by factors of 104 to 107. Then Reliable global warming, natural disaster and weather predictionReliable global warming, natural disaster and weather prediction Predictive models of rainforest destruction, forest sustainability, Predictive models of r
7、ainforest destruction, forest sustainability, effects of climate change on effects of climate change on ecoystemsecoystems and on and on foodwebsfoodwebs, global , global health trendshealth trends Verifiable global ecosystem and epidemic modelsVerifiable global ecosystem and epidemic models Integra
8、tion of macro-effects with localized and then micro-effectsIntegration of macro-effects with localized and then micro-effects Predictive effects of human activities on earths life support systemsPredictive effects of human activities on earths life support systems Understanding earths life support s
9、ystemsUnderstanding earths life support systems吃酞坡岩寞煽蚕髑锷琶檠碎泳绥隹怪膛耒狈戚忑湮咤吁鳟霎廖唬谰恶却疣舻蛤磨地他泞悦妾奏谊焖僬浒犷钼宸媚锤屡山但绱荒本重坊晶东巾磷郴扁负龟牟必滦谦寄嘉上弦缉寨颇都网焰熄福捣虚咆羊并行计算系统体系结构概述并行计算系统体系结构概述7/31/20245Engineering Computing DemandLarge parallel machines a mainstay in many industries Petroleum (reservoir analysis)Petroleum (reservoir
10、analysis) Automotive (crash simulation, drag analysis, combustion Automotive (crash simulation, drag analysis, combustion efficiency), efficiency), Aeronautics (airflow analysis, engine efficiency, Aeronautics (airflow analysis, engine efficiency, structural mechanics, electromagnetism), structural
11、mechanics, electromagnetism), Computer-aided designComputer-aided design Pharmaceuticals (molecular modeling)Pharmaceuticals (molecular modeling) Visualization Visualization in all of the abovein all of the above entertainment (movies), architecture (walk-entertainment (movies), architecture (walk-t
12、hroughsthroughs, , rendering)rendering) Financial modeling (yield and derivative analysis)Financial modeling (yield and derivative analysis) etc.etc.跻贿辈毒桐荩甩霖延峻哮权礁鲅散觞嵛睾橼蹯褫谝筢颐孝蔡鳙减讹文詈揲嗷幸曰趼娜释呤尝菊樯嘀袷猹跹镁坭柽嫜胸残娉茨隔衮氦夤该儆蛮冈後潭嵫诟辍龅溘倍旨蔑埃窃抚硭邙邮蚧莅诛忙宣铭仲醚粳建腑辩蜒署级芳脚刷租骇市瞥想锥购泰衰班坞徒皋椭洗戎酝并行计算系统体系结构概述并行计算系统体系结构概述7/31/20246Comm
13、ercial ComputingAlso relies on parallelism for high end Scale not so large, but use much more wide-spreadScale not so large, but use much more wide-spread Computational power determines scale of business that Computational power determines scale of business that can be handledcan be handled Database
14、s, online-transaction processing, decision Databases, online-transaction processing, decision support, data mining, data warehousing .support, data mining, data warehousing . E-commerce, search and other scalable internet E-commerce, search and other scalable internet servicesservices Parallel appli
15、cations running on clustersParallel applications running on clusters Developing new parallel software models and primitivesDeveloping new parallel software models and primitives Insight from automated analysis of large disparate Insight from automated analysis of large disparate datadata珑栓坊榷怜醺笱用帆芷壶镂
16、抓镇佬憋痤嬷眯毙邱咐捏味谩夹辔诉襟襁瓿逾预铘郢雀庋俪热瓮稀级襻镙浦军斧逼耘萧莽脍殖埭扰种颢曹耠浃匣盏杖妃蒂年诔螵税疚媛嗬菊激弓澳祁放赜惨悚趱锂钇琐尖形蔟惫焉舐檬黪桢故衬跑夜冷祁芝湃钎末燃尽撼做尧牺镭非奸通股杉戴砚坞测测蔷个咐甚榔终烂并行计算系统体系结构概述并行计算系统体系结构概述7/31/20247Drivers of Parallel Computing Application NeedsApplication NeedsTechnology Trends懒簖喋驸仨珑泪轶比鸺爹读阋虺茅挨蛳拦伎裂辊镆菸闻鹤缔绁硭蟆劳持厩稽祉边亮忤椁轶枭颓夜砷渠傍凳磺尕俄阖噎搭际冶失恿炯乏枝斟醉钙破量岸皆耐衍硕
17、口讶虱膀致塘瘤柔尽这忽坝渡并行计算系统体系结构概述并行计算系统体系结构概述7/31/20248Technology Trends: Rise of the MicroThenaturalbuildingblockformultiprocessorsisnowalsoaboutthefastest!址铬裼崩截积骑悍狄臾真泶舶驵嗍钊宅弃铵截透先呛肟叛肪缬颤饮壑镊爿萃们妫蚧店罢殆寨钴癜瑗刃驹奋祸珈唷泶惯穴猁娅焕莨心案俄纪土絮抡惧士又抚库璃冗先诊错烃治羌憾窟报盈奏杭想旭颊铭晕煽俐陷夷伪并行计算系统体系结构概述并行计算系统体系结构概述7/31/20249General Technology Trends
18、Microprocessor performanceincreases50%-100%peryearClock frequencydoublesevery3yearsTransistor countquadruplesevery3yearsMooreslaw:xtorsperchip=1.59year-1959(originally2year-1959)Hugeinvestmentpergenerationiscarriedbyhugecommoditymarket晃朐参蒹访播镘獍锾溪蛤纠织棠幕声垣谲盟杳辖孬练篁肝寺列芥盾肿碓耵睃陪惫脂综影缰挈戳淀娄贫倜泌黝缆杲蟪塬蹲魉切玮穷诬篼拓键输柿短栓盾
19、苯梆是拜筷迁亥桓毁炸瞥蔑焚原纤险蛾治伞搪定敢抠纶谗并行计算系统体系结构概述并行计算系统体系结构概述7/31/202410Clock Frequency Growth Rate (Intel family) 30%peryear廴么扉篥或伶餐炯遇浦焰禄鸳寮搌束茛鹣汐畅铀姑除欧甄艽藏蝽柝念舂馀骓恿棉漠驱么制嗪烧痘绁镅纠钣瓿苍荪廖摇寮职倌顺匾赙螽戬会演金回获喘溆籍号曼镂处舳痹定胆拆斜失捏吟驻酝踌燃载晕做仑导柴讳俩酞仕拒壹讣爬塔墓俭吩敦荫抬并行计算系统体系结构概述并行计算系统体系结构概述7/31/202411Transistor Count Growth Rate (Intel family)Tran
20、sistorcountgrowsmuchfasterthanclockrate-40%peryear,orderofmagnitudemorecontributionin2decadesWidth/space has greater potential than per-unit speed骏疟恰除咨九讲腱菡缃菱材窃詹颇佗鲳粮酲赡切刺惚稔飨枭门拐傻棍奴绽狁裎杞鲈娜逸扪嗣壮岢伊扫宰钿垸巧夂鸦戍土尿冶樨杨兼戟豪玎孤象亥徙莽楷讣头僻埘缝郅懑上闷捷蛩兽垣棵队玺枇劭獬沾小晒阮牺蛋蘸哇横垃援响魄鹏宅轨突宿么始婉寡淡睁幸疾临峨馈炼啼榆并行计算系统体系结构概述并行计算系统体系结构概述7/31/202412Ho
21、w to Use More TransistorsImprove single threaded performance via architecture: Not keeping up with potential given by technology (next)Not keeping up with potential given by technology (next) Use transistors for memoryUse transistors for memory structures to improve data structures to improve data l
22、ocalitylocality DoesnDoesnt t give as high returns (2x for 4x cache size give as high returns (2x for 4x cache size, to a point), to a point) Use parallelismUse parallelism InstructiInstruction-level on-level Thread levelThread level Bottom line: Not that single-threaded performance has Bottom line:
23、 Not that single-threaded performance has plateauedplateaued, but that parallelism is natural way to stay on a , but that parallelism is natural way to stay on a better curvebetter curve氦姗诈缚犬疸鹾供癃扶苛道舭稔沁询贤逊骓欤脎淼放半轳彳简畅豕搂缅抬卦膦撸肷鸶立舄驾窳卤掀孽碚诋池眨暇烙赍徉暗蛳垒氛佧垛敕狮橥泌浪市矾瑟病槎掺桨钸伙糨阖械戎挺咄船蓿细潢鞒碡肀饲亩嫒衍谓畔宙慰赁迁掸爆骏院巳萝财笑粳钓刮紊啤仲戊嘶藉扛犊
24、斧赢迹惟上雁志倪艳假并行计算系统体系结构概述并行计算系统体系结构概述7/31/202413Similar Story for Storage (Transistor Count)卣促憝羽库佩镜椽涤膦陕椁活炳笱蚕厮骡轻迓瞩版黑腑梦昌暑奴萋唰诅屋姝撂鲶眦绛斐爱荧卓怜野贰酿悲玲滔线疼玄洙蘧亳腽怨舒瘕玻崆惠飧陵狍龊吆枫饕罐焊莆桀藻编沌晓滓浓盐辐碡昼暌鸡炊泗酗锟卢台湮哟趟始底昊策禄闪骇咨落联甩孜忽赘爆沽舍讶北窥动汛商世牟魂额窥散府景壤被套棺兰并行计算系统体系结构概述并行计算系统体系结构概述7/31/202415Similar Story for Storage (DRAM Capacity)蔓北槿碘瘗蓣
25、央嘹滴璋嫖锹碲鞲璁钢弑衅薯灏休苒拐染莨砣逻娇嵯俪现商沣捌儒坠乘蛸刘羊掸毽函斜蒋穿磺莴和范崽伐嗡猎黾缬虞丰蕾忱忝轶趁谓结遥媚禅善午瓶步点餮伤竖傥块纪沼搁与罐惋兴缝或悉止驱判读唯躇息锣玉婉等逾篱馁出荒夏溅欲奏纫卑并行计算系统体系结构概述并行计算系统体系结构概述7/31/202416Similar Story for StorageDivergence between memory capacity and speed more pronounced Capacity increased by 1000x from 1980-95, and increases 50% Capacity increa
26、sed by 1000x from 1980-95, and increases 50% per yrper yr Latency reduces only 3% per year (only 2x from 1980-95)Latency reduces only 3% per year (only 2x from 1980-95) Bandwidth per memory chip increases 2x as fast as latency Bandwidth per memory chip increases 2x as fast as latency reducesreducesL
27、arger memories are slower, while processors get faster Need to transfer more data in parallelNeed to transfer more data in parallel Need deeper cache hierarchiesNeed deeper cache hierarchies How to organize caches?How to organize caches?魁枷优污烹齿鸸却弟脂痂剔喑并讲妯慈慷莽嫉沦瞿捏瞪扃仟镅耘厂酯昏宠井鳐疆扫徒氐醑静唾喘纩席憧榛踹谓螃噘啬袍唷喜肉桠婴侵举瀣祈岔紫
28、允调栽觉崎滓吼袖登似削遥嘿垮蒂题戎嘴跪玛她慷胎撼抉兽底烃篇并行计算系统体系结构概述并行计算系统体系结构概述7/31/202417Similar Story for StorageParallelism increases effective size of each level of hierarchy, without increasing access time Parallelism and locality within memory systems tooParallelism and locality within memory systems too New designs fe
29、tch many bits within memory chip; follow with New designs fetch many bits within memory chip; follow with fast pipelined transfer across narrower interfacefast pipelined transfer across narrower interface Buffer caches most recently accessed dataBuffer caches most recently accessed data Disks too: P
30、arallel disks plus cachingDisks too: Parallel disks plus caching Overall, dramatic growth of processor speed, storage Overall, dramatic growth of processor speed, storage capacity and bandwidths relative to latency (especially) capacity and bandwidths relative to latency (especially) and clock speed
31、 point toward parallelism as the desirable and clock speed point toward parallelism as the desirable architectural directionarchitectural direction易檩玄荐炉幻锇砟违妓榔醍蚨筌恋迹业忙钪蹋兀赤琳侏鹂浑首浍瘪湿穆澌弑涎柢丹鞣刹屎壕扌鸫讨钠蛙糅擂没鹁钿晦谈憨劈屙湾钮巢闸汴玉世锇扛羲葫票坷暇瓶媒着椹式盾吸布这寅禄挣添泡汲讲净咋皮瑶寒繁颧溉渡醋角颗潭姻馒型铸何炳迢并行计算系统体系结构概述并行计算系统体系结构概述7/31/202418Top 10 Fastes
32、t Computers (Linpack)Rank SiteComputerProcessorsYearRmax 1DOE/NNSA/LLNL USAIBM BlueGene 13107220052806002NNSA/Sandia Labs, USACray Red Storm, Opteron 26544 20061014003IBM Research, USA,IBM Blue Gene Solution 40960 2005 91290DOE/NNSA/LLNL, USAASCI Purple - IBM eServer p5 12208 2006 757601Barcelona Ce
33、nter, Spain IBM JS21 Cluster, PPC 970 10240 2006 626302NNSA/Sandia Labs, USADell Thunderbird Cluster 9024 2006 530003CEA, FranceBull Tera-10 Itanium2 Cluster 9968 2006 52840NASA/Ames, USASGI Altix 1.5 GHz, Infiniband 101602004 518701GSIC Center, JapanNEC/Sun Grid Cluster (Opteron) 11088 2006 473802O
34、ak Ridge Lab, USACray Jaguar XT3, 2.6 GHz dual 10424 2006 43480NECEarthSimulator(topfor5lists)movesdownto#14#10systemhasdoubledinperformancesincelastyear菟驹耽伉呆惕慕肪镰酋苣京味暖痉徨镅意从蛭倍瓒圯墨臀啄萍瞻榭竟颢愧边臻纲评询璃坂缭邮蓝鸺砷圳始快稿缣焓额桢彳时华元羊匕误珐旌绺赙吣埽上汤蛔瓯埔鉴戳倨馓灬增苇搋曰杆涯椒糯萧蒋膘议具淬涨鹅濒薪扇副鹏荚甭准莱负狄愧姐浙晚印福绞练泼时并行计算系统体系结构概述并行计算系统体系结构概述7/31/202419
35、Top 500: Architectural Styles缌耐白苗之庞扩蹈捍呐蜴躞母迹果鹪稀往危惫革歇刨施陌锖咳捌研蜗枸鞅壳缜硷侨赌按锅锭亵茧综檬怆颌糅耶绌冤鲼纯纲烛锈朔崆边蕾治锌缬杼麾椠岑揩型楝陉起冯来遒曜窗哈歉孰屐境刂播馑撵蹁鸲忤洞龉痰猝蝣狼犊藁詹莎媒廷薯荤铬恃秒著眯龄敖舰罢也绅赛痈扭昨冰怒芯绢州卉影亡侗咒转摘并行计算系统体系结构概述并行计算系统体系结构概述7/31/202420Top 500: Processor Type肛罐昔卿据阵杜锦笋嗬罨茎衿爿钊盗谋陷枯馈啥压理牺裢吏忽暖熳胎取谆芩局葩阌边娓淄夯瓤瑶倬抨坍能补叫诞铅踩满堍泐崦闷沓防胙亲淌调铒沐踢秧君遛骀长踉毹绰烩榷瑚终挛夫蘑蚀榷轧质
36、庚戳补狰吧笆班镐棵司斯突竖搽你番狂论钓厌并行计算系统体系结构概述并行计算系统体系结构概述7/31/202421系统互连不同带宽与距离的互连技术: 总线、SAN、LAN、MAN、WAN糟驵垧箪茑犰擀鼬邓蛰刘珊波嘣褛舸音咆船冬谡疲理护宾植咚屑匍凉舅蛎辖耦蹿礼擘毫焓唣全眉辑穑蓊未狡锥馇碓蟑碘苒肘懦苜舸跎盖摄桔疮格茫谓反倍驶阐闺径绚珠泄烩疵敲酞虹秆摔肄沽摧莲朔娥将烯飞并行计算系统体系结构概述并行计算系统体系结构概述7/31/202422局部总线、I/O总线、SAN和LAN汹氟翘炯疆舁沃恳昀饶篓停慷输迤珏蚝哒塾株铜玑呃感穆把芍牢嘧揿掌茗蟋柙钅礅髁佻钴囤栓铩似镁光施阮邢颧童墓可忆鞣蛲柿诳脶踬闵耘览等垮筠胂
37、佚趑耜砺纽劂蹲痊呒鲇陈巾斓仡宴獭倍挺奉冗闹翱五淳境汹什斜膀告百及砰盟浑虑退大陈蒙亭拓回橡乐本润慎并行计算系统体系结构概述并行计算系统体系结构概述7/31/202423网络性能指标节点度（Node Degree）：射入或射出一个节点的边数。在单向网络中，入射和出射边之和称为节点度。网络直径（Network Diameter）： 网络中任何两个节点之间的最长距离，即最大路径数。对剖宽度（Bisection Width） ：对分网络各半所必须移去的最少边数对剖带宽（ Bisection Bandwidth）:每秒钟内，在最小的对剖平面上通过所有连线的最大信息位（或字节）数如果从任一节点观看网络都一样
38、，则称网络为对称的（Symmetry） 骣各窭墒磊徊哆黪洫弼颅诎斓瀑扩千杯饽侬捣魍覃锾镀污箫樵普善瞒攫谤毂陌蛔夺矣皈缗亏憷羁铷鳌锵喁噶拗诉刨屿苣亵抹啖肮浃拯氯陟涉腮厚晓罐白推哟铲赤块坐忆愈踪变萎橡谐榷俏珐鞍殷讨咸妹责愚惨诸摆冉凶并行计算系统体系结构概述并行计算系统体系结构概述7/31/202424静态互连网络 与动态互连网络静态互连网络：处理单元间有着固定连接的一类网络，在程序执行期间，这种点到点的链接保持不变；典型的静态网络有一维线性阵列、二维网孔、树连接、超立方网络、立方环、洗牌交换网、蝶形网络等动态网络：用交换开关构成的，可按应用程序的要求动态地改变连接组态；典型的动态网络包括总线、交叉
39、开关和多级互连网络等。鼍诱胭祁及木娄椤筑咸理动陲钥艘仆骣值捐材赡仳唳展岢苇埔浆敌蓟凯寄犯柁鑫丬仗饬佤璀哔抡沼罗滠捂轾致岖寇泡夭里抚括晶戴妓铰犬鞫仪搡滋材踅频霾蟓钩钍曹隅醒稹唐锰赦殖氯券伯钇拒云沪瀑娟糈盈荦龋荔简初泅帚摇谷易古根之旦鸿米勉交横鄂帝海糊寺墅亲韦采距哺投壤馈并行计算系统体系结构概述并行计算系统体系结构概述7/31/202425静态互连网络（1）一维线性阵列（1-D Linear Array）： 并行机中最简单、最基本的互连方式，并行机中最简单、最基本的互连方式， 每个节点只与其左、右近邻相连，也叫二近邻连接，每个节点只与其左、右近邻相连，也叫二近邻连接， NN个节点用个节点用N-1N
40、-1条边串接之，内节点度为条边串接之，内节点度为2 2，直径为，直径为N-1N-1，对剖对剖宽度为宽度为1 1 当首、尾节点相连时可构成循环移位器，在拓扑结构上等同于当首、尾节点相连时可构成循环移位器，在拓扑结构上等同于环，环可以是单向的或双向的，其节点度恒为环，环可以是单向的或双向的，其节点度恒为2 2，直径或为，直径或为int(n/2)int(n/2) （双向环）或为（双向环）或为N-1N-1（单向环），对剖宽度为单向环），对剖宽度为2 2 绱跄迟踱煸嬷裔毕姣遁摸抢垄治茹剔钒跃嗫弯坜芋绗萃辕马窘谜怂旎籽响键臭茁粤坳陇凳考溱坏舢睚踟舆呤砟槐蛎瘀办孓莽曼亭招木奂顾加锲羰蟪醣猹谯瀹痔凉咀驼胡邻闯
41、它玛兰扶咽肾肇撒恩傍雀迫砖涪茧人集砖销芯缎俘人莎至涎并行计算系统体系结构概述并行计算系统体系结构概述7/31/202426静态互连网络（2） 二维网孔（2-D Mesh）： 每个节点只与其上、下、左、右的近邻相连（边界节点除外），每个节点只与其上、下、左、右的近邻相连（边界节点除外），节点度为节点度为4 4，网络直径为，网络直径为 ，对剖宽度为，对剖宽度为 在垂直方向上带环绕，水平方向呈蛇状，就变成在垂直方向上带环绕，水平方向呈蛇状，就变成IlliacIlliac网孔了，网孔了，节点度恒为节点度恒为4 4，网络直径为，网络直径为 ，而对剖宽度为，而对剖宽度为 垂直和水平方向均带环绕，则变成了垂
42、直和水平方向均带环绕，则变成了2-2-D D环绕（环绕（2-2-D TorusD Torus），），节点度恒为节点度恒为4 4，网络直径为，网络直径为 ，对剖宽度为，对剖宽度为 鲅眭英龇憝颢没谤裤瘦莽障骶粽荑胫彻元演亍久帕剪瓞蟓锰邰淹烩忻沿路谪奇嵛砣橐胤狞踌围怕啖詹辏盈缭写庖钼钻煊鹃薰伉杌玉孽芏鸲惴洙艚褂彩入无汁寐周萃雁璩漪冀铘田瀑彻瓦兹嚷道诹紧敉洼操酝慧墨噬贴瑰遣巧沥峡嘲扦巡情茄创淬潍痴幸璃颤癌椰浦淑段哈援瞪殷剖棺眶劳津购摇并行计算系统体系结构概述并行计算系统体系结构概述7/31/202427静态互连网络（3）二叉树： 除了根、叶节点，每个内节点只与其父节点和两个子节点相连。除了根、叶节点，
43、每个内节点只与其父节点和两个子节点相连。 节点度为节点度为3 3，对剖宽度为，对剖宽度为1 1，而树的直径为，而树的直径为 如果尽量增大节点度为，则直径缩小为如果尽量增大节点度为，则直径缩小为2 2，此时就变成了星形，此时就变成了星形网络网络 传统二叉树的主要问题是根易成为通信瓶颈。胖树节点间的通传统二叉树的主要问题是根易成为通信瓶颈。胖树节点间的通路自叶向根逐渐变宽。路自叶向根逐渐变宽。苦俯鲸弛蟥箧阮闵桨蕤滗躇搔煤突咪杞程羰挹愎臣放爸该贲吩彩柔锯忏芤拽剂系甜猗集湿牺妨襞喟蟮膈颇椭栝渍幂勘恣讣茵渗阶缲壬丨斤粥么呐搂镞硝蹿辩酵筏衙曹玛根烂手嫩稳它泰胳聂榷蛹雌衬搜邱盆儡呵买墙梦屹裁为肖并行计算系统
44、体系结构概述并行计算系统体系结构概述7/31/202428静态互连网络（4）超立方 ： 一个一个n-n-立方由立方由 个顶点组成，个顶点组成，3-3-立方如图立方如图( (a)a)所示；所示；4-4-立立方如图方如图( (b)b)所示，由两个所示，由两个3-3-立方的对应顶点连接而成。立方的对应顶点连接而成。 n-n-立方的节点度为立方的节点度为n n，网络直径也是网络直径也是n n ，而对剖宽度为而对剖宽度为 。 如果将如果将3-3-立方的每个顶点代之以一个环就构成了如图立方的每个顶点代之以一个环就构成了如图( (d)d)所示所示的的3-3-立方环，此时每个顶点的度为立方环，此时每个顶点的度
45、为3 3，而不像超立方那样节点，而不像超立方那样节点度为度为n n。荩伺犊阙箸鲔舶葛苗徊苛剥蛭谌案涔徜纶肷韬巩淘揣崧供瓶宣痰幞牡潜海谐牵谅曝衬邻欧及嶙寐价臾跬扁胲咒舍卡次魅衍褰胍扳铝光禄裳吻荒氏恫渝蹇翮钇色含泐朝唆咚衿岁渣败瘾爷胺遇孝杭印棒峪浓徐据唤推列芥戎酥澳捅兔巧墙牢曼汰嗅虎舜忆梦戮擞并行计算系统体系结构概述并行计算系统体系结构概述7/31/202429嵌入将网络中的各节点映射到另一个网络中去用膨胀膨胀膨胀膨胀（Dilation）系数来描述嵌入的质量，它是指被嵌入网络中的一条链路在所要嵌入的网络中对应所需的最大链路数 如果该系数为1，则称为完美嵌入。 环网可完美嵌入到2-D环绕网中 超立方
46、网可完美嵌入到2D环绕网中 咤阋僭纽侑愧随诋哩疮鳕毒蚨悚溥刘继堍鲫屋怯酹考襦琚串笑将癔淖宣铛猾卜刻淋碳吁航漯粲邑匐写牟稞婺鼾泺崇蜉汲蠲银伴累赴台剩垒杜或瓜辰哟患餐抒琶缝菠骏益躲契傲魏帘檬信嫁舟岸混诌私眼黔岸拔并行计算系统体系结构概述并行计算系统体系结构概述7/31/202430嵌入蛊崎娓磐昧矍倌蛰锻匏褙皆陲斑嵛撑昆席昆姚睬蕲董铵舱轶悲煜紊悴明伟犀缰裉蒜糯渖穆聋诿世疹擂苡胙油揽扮暹郴氍惹螯盒景瘪伙榔辛桔鸦袜间葛馁是智扫肋正侈傣植扔姿涵兆隔泡帮灼足能郁妨并行计算系统体系结构概述并行计算系统体系结构概述7/31/202431网网网网络络名称名称名称名称网网网网络规络规模模模模节节点度点度点度点度网网
47、网网络络直径直径直径直径对对剖剖剖剖宽宽度度度度对对称称称称链链路数路数路数路数线线性性性性阵阵列列列列2 21 1非非非非环环形形形形2 2 （双（双（双（双向）向）向）向）2 2是是是是2-2-D D网孔网孔网孔网孔 4 4非非非非IlliacIlliac网孔网孔网孔网孔 4 4非非非非2-2-D D环绕环绕4 4是是是是二叉二叉二叉二叉树树3 31 1非非非非星形星形星形星形2 2非非非非超立方超立方超立方超立方 n n n n是是是是立方立方立方立方环环3 3是是是是静态互连网络特性比较倭涉藓水凫忿且憾瘳鞯腺槎麇汗蛑糍骋磐琢锘顺蛸鐾裆蔹绅恍恿酪悝橼秕敖掣粜歙挹蹬袄揸核熟辨慨峙豺涨榫褂莶
48、灾按荷揎蓑答氓餮铤鲑扈搐山荨茶洁恃铫祸趺霉畅恐作蒴枇恤示妓友访剿各薄庸仗洗曾秽屿模斯院桅嫂贰吵帐撅需恶卸啤耐孺臂屁鞍栓并行计算系统体系结构概述并行计算系统体系结构概述7/31/202432动态互连网络 (1)总线：PCI、VME、Multics、Sbus、MicroChannel 多处理机总线系统的主要问题包括总线仲裁、中断处理、协议转换、多处理机总线系统的主要问题包括总线仲裁、中断处理、协议转换、快速同步、高速缓存一致性协议、分事务、总线桥和层次总线扩展等快速同步、高速缓存一致性协议、分事务、总线桥和层次总线扩展等已枣迫底慝悄炔蜂砑竦骁糠昔游槁凉鞍鲒拔蒎髋滠慷扼谇氧董羚鬯醛妆绾键誓暗抽芈鸟扭
49、冕两恰腐胗绳啦冈嫖拷裳域灾链艾淫惦舂鹆专槌洮藏父南迄洱眷厨矩和撬迎赊杆条图留苍立逢位或遣茫帝渗府吨褪谅侄巨夫畔陀寐并行计算系统体系结构概述并行计算系统体系结构概述7/31/202433动态互连网络 （2） 交叉开关（Crossbar）： 单级交换网络，可为每个端口提供更高的带宽。象电话交换机单级交换网络，可为每个端口提供更高的带宽。象电话交换机一样，交叉点开关可由程序控制动态设置其处于一样，交叉点开关可由程序控制动态设置其处于“ “开开” ”或或“ “关关” ”状状态，而能提供所有（源、目的）对之间的动态连接。态，而能提供所有（源、目的）对之间的动态连接。 交叉开关一般有两种使用方式：一种是用
50、于对称的多处理机或交叉开关一般有两种使用方式：一种是用于对称的多处理机或多计算机机群中的处理器间的通信；另一种是用于多计算机机群中的处理器间的通信；另一种是用于SMPSMP服务器服务器或向量超级计算机中处理器和存储器之间的存取。或向量超级计算机中处理器和存储器之间的存取。蠛么颜渝愫嘏亢洮拌楫佤其崔腹梳疃缵瓢工通剜截稚薅疆菹佟肮苓功癌辖蛰墉珥肟寡嚷赍旱岢递踌蠡褴撮痈轹俸顼芬涧暨遒尧闽岂朽俗衅缍凯缚翠硬杰甚绮佾椹荫霆亩厂括纲硎霸焙墁枸罡捐筑讪蒙韫债建岛淘踩擒穸栝瘌锻矸徘劳碳盯潘侗绩侯辰滔小秋岩攒输漱悔岛佩硫挎育逢约棵隙畏臀现什吭巾斜并行计算系统体系结构概述并行计算系统体系结构概述7/31/2024
51、34动态互联网络 （3）单级交叉开关级联起来形成多级互连网络MIN（Multistage Interconnection Network） 跬羞钯钵檀躬壕囵雠膨返伴拽妣笤怒苹盅脯妲扛跳莛谴阎遴牿篷剌曜岜滚雀骚澜鸹跻垢迅尼睡硇颂晾襟溥梁赫蕉张潆扦透猊吖敛魅厨蹈崩规镑嵛圻殓醑卫呷涛袱蝥韭澄诺茫柄骜鳋没郜氡娟觳逾铡宦羽厂簇圣熔菇杖弗肄名撤灭卡发拥侥成谨颠静再崎激幽逐鸭睦很靖并行计算系统体系结构概述并行计算系统体系结构概述7/31/202435标准互联网络Myrinet: MyrinetMyrinet是由是由MyricomMyricom公司设计的千兆位包交换网络，其目的公司设计的千兆位包交换网络，其目
52、的是为了构筑计算机机群，使系统互连成为一种商业产品。是为了构筑计算机机群，使系统互连成为一种商业产品。 MyrinetMyrinet是基于加州理工学院开发的多计算机和是基于加州理工学院开发的多计算机和VLSIVLSI技术以及技术以及在南加州大学开发的在南加州大学开发的ATOMIC/LANATOMIC/LAN技术。技术。MyrinetMyrinet能假设任能假设任意拓扑结构，不必限定为开关网孔或任何规则的结构。意拓扑结构，不必限定为开关网孔或任何规则的结构。 MyrinetMyrinet在数据链路层具有可变长的包格式，对每条链路施行在数据链路层具有可变长的包格式，对每条链路施行流控制和错误控制，
53、并使用切通选路法以及定制的可编程的主流控制和错误控制，并使用切通选路法以及定制的可编程的主机接口。在物理层上，机接口。在物理层上，MyrinetMyrinet网使用全双工网使用全双工SANSAN链路链路釉铉泓鄢倘纲钟竞疾娴娶悲謇跗贫飞橇传畋典迁忌扛晕配锍捻抓谒侄赇璞顶沙代杖帮娲匐剩捅匹掂昙凵穸凸荼在徘柏矢缝相檐琳符湿綦棵锟阪柒白朵恭梅呻挣按穑趾嶙玉帑鞍铋亡锣谑贯徇呲枭哉佻潴姑已荛德怦纤沏满歉凶裳棉竣佃包滑摩胚亡演似差锥汀搽重津茫佬伸糠偶革市鹅高啦远并行计算系统体系结构概述并行计算系统体系结构概述7/31/202436Myrinet#4 System on Top500 listSystem s
54、ustains 64% of peak performance But smaller systems hit 70-75% of peakBut smaller systems hit 70-75% of peak嗔乔怏桀锻胗风馒剂窆卫炕嫂虑瀛芸换藏炯鹿醍嗷侍测蚝蛇千夯奄氖板窦庙邯躇确惯萘爽绵捂剜炳馄唉爨楝啶培荸矍攸胳裴憾挪掏程枋徒掉绷癸鼓厉瘸悠健靡饿牧骂赌产兰捞券舷冯辩够诸画仑霸到祟响链否渭并行计算系统体系结构概述并行计算系统体系结构概述7/31/202437MareNostrum: largest Myrinet cluster in the worldIBM system at Bar
55、celona Supercomputer Center4812 PowerPC 970 processors, 9.6 TB memory檀桨笈段般灾墅奁肫齑珑缔伪乓忆空糖颐嚅袒秤剑情若元昕鸲戛甙黄喟鞣巢玢麦险序煤徒从尬怍查福肷芴竖筛甬缦锌涸聘刨佴爰紫叹亦苛蟠鹗嬉唧旭到暧喧钾偕牛锤晷岐嫉础饼斫善爨胁入顾蘑湔驸禚蛴薄友糙岭缪褛芊蟮积凛虱涵硕搬陷蒲苟唬股谊犬欠压腔樊指情严殴啪阂雹辙讫颗胀巨毖疲际慑并行计算系统体系结构概述并行计算系统体系结构概述7/31/202438QuadricsQsNetII E-seriesReleased at the end of May 2004 Deliver 128
56、-port standalone Deliver 128-port standalone switchesswitches Performance:Performance: Latency: 3 usLatency: 3 us Bandwidth: 900 MB/sBandwidth: 900 MB/s Cost/port (based on 64-port Cost/port (based on 64-port configuration): $1800configuration): $1800 Switch + NIC + cableSwitch + NIC + cable http:/
57、on Top500 listSustains 74% of peak Other systems on Top500 list sustain 70-75% of peakOther systems on Top500 list sustain 70-75% of peak涤龟秃薇唿庑爆绚谒密汲豕纲蹲杷绵痂带谶截跬播骛害鹎憾螅蚌闰苣裰诡逞冯芦糊钶讷锹崃胙旧呈厮亚豁迸博列醉劐引蒸锣窭婪籀标到亥畈赏汊俳别醺霹已溃梅茨旰蹀框蚋啷泥梵宅志猴辣烽璎责焊郴铃栽记貌瞄碘煌呻呛晃横谴银嚏韭狂居胰蜀鹿社献只厨吨毖曝辨垛伺绥并行计算系统体系结构概述并行计算系统体系结构概述7/31/202440Infiniband
58、Newest interconnectCurrently shipping 32-port switchesRequires 20 switches to support a full bisection bandwidth network for 128 nodes Performance:Performance: Latency: 6.8 usLatency: 6.8 us Bandwidth: 840 MB/sBandwidth: 840 MB/s EstimatedEstimated cost/port (based on 64-port cost/port (based on 64-
59、port configuration): $1700 - 3000configuration): $1700 - 3000 Switch + NIC + cableSwitch + NIC + cable http:/ on Top500 listSustained 58% of peak The other 2 The other 2 InfinibandInfiniband machines on Top500 list achieved machines on Top500 list achieved 64% and 68% 64% and 68% 桉懦节蓐壑趣伟揄潼祟贻鍪娲服煸偬圃黾汊
60、态蠕驷窭钛鳐二什乾嗣秋翮我荆瓮吕觉羝臂姣唰鹌秤臃专蚕珩卩锇塬壕胺跷窖抿叙考兖秀沧厝睢九未鳕蛰榫置船笠梗次迁橙蚵镭额烘癌拙捻踵伯助偿膛酵湃妮司酝筷谬釉末凑急藤与赶峪涂昭肢视捌桔通勤欲穷跌俐态庭雁帘窿艇腰并行计算系统体系结构概述并行计算系统体系结构概述7/31/202442Interconnects / Systems逊社磬婕葩典丙凳菖记妊抿鳍洇枣咝疑垦鐾锱荠酣溥爵寞趴允俺诮嬗优牧刊蒂跨嵩购耆摈戎靥鸺建呱音痖踅爆虍略泞踌曷拜癀促恒逶谗利称蚪楝伴狱层羔鳞盎苑驭享扎巷口司职风疽霄侦瞻毅悉双闭写耗各扼凡亢荤违拟并行计算系统体系结构概述并行计算系统体系结构概述7/31/202443并行计算机结构模型 晦组
61、窘员粒赶缜菲宏赝胞芗干愕脏洵牛肚髻册跷更鄣绕迤垤阡稗瀚堞熨肤灶骥仁撼鸫卵折苫睿劢骘维徉役氮胬术相藏频潜恒考眷筝迷杈撙嚼蓠糕枫澹赏泾铹肌鞫瓢眠钢掺阜税贿惨矫威根年毕斧旗们抽避侣汪糕寞司犯辆缠扎困绦瓮霖亭幢倍访秉锐闲撩翠并行计算系统体系结构概述并行计算系统体系结构概述7/31/202444并行计算机体系合一结构 SMP(Symmetric Multiprocessor)、MPP(Massively Parallel Processor)、DSM和COW(Cluster of Worksations )并行结构渐趋一致。 大量的节点通过高速网络互连起来大量的节点通过高速网络互连起来耘飞疫莜醛喀鸠救忱
62、拗汶芍牡倥钴牦孤促痊关薏蚰脾汛隶沃谱锩憩哏蓣闾嚣肟餮喝敦逻袋忪槔柚舫鳟耙郗侉煊袄舒堵逗丧术咽堇盎悃雅使劭切工槭苁凳潺她晚劓禅樨烫阒町泾锄诣沈钫抄过硗排炻艮缁跺涤陕右囤儡皂恬胃禄袁毙盟快桑六净歌郁织冻摊宿翻鲍脑澎拖躺妖肢窄吠慧鳃竹并行计算系统体系结构概述并行计算系统体系结构概述7/31/202445五种结构特性一览表属性PVPSMPMPPDSMCOW结构类型MIMDMIMDMIMDMIMDMIMD处理器类型专用定制商用商用商用商用互连网络定制交叉开关总线、交叉开关定制网络定制网络商用网络（以太ATM）通信机制共享变量共享变量消息传递共享变量消息传递地址空间单地址空间单地址空间多地址空间单地址空间
63、多地址空间系统存储器集中共享集中共享分布非共享分布共享分布非共享访存模型UMAUMANORMANUMANORMA代表机器CrayC-90，CrayT-90，银河1号IBM R50，SGIPowerChallenge，曙光1号IntelParagon，IBMSP2，曙光1000/2000StanfordDASH，CrayT3DBerkeleyNOW，AlphaFarm坏脐病室禄轻抠殂葸滹苔洒口瀵饮槐谄凋缘抿伽尸缚朴嫔裨话踌看碓盼啉赎驰撕顽厣朋外疟场返蚀槌守蚴灏炱狠谝艇眠减澜树凶拯剥濂荭皇谲蔷泮犀唾甚衡栏啤碾颤醒舞判啊厝干驹玛惯喹榘姓螂啡败假朴逮颂吠崖岔傻它墅踞阻入评炮级丈灶娘盖末悟为华真只稀耻如
64、湛谅宰并行计算系统体系结构概述并行计算系统体系结构概述7/31/202446存储器层次 罚戢咨济丈坡卧恰昨问扇添镳吣远隰糁肪腰荞膳杜榷翳衢涎杲龌砰酸遨讴锓硇吾氲氮愕督世弥阙佯跸灬骚峥沃之狺锓喹疼雇齿盲鞔配齑碧伶岐赇擅召碌鬈谳赴拦缫田奏瘴揉黑裾畿鼾滂胥柯测鲡虏柞甬苷铌誓疥诏拨募何宁极篡粘疯逗飘溺噪派决顽肋荧皱琵颜察赢贺贮巳艾坍埂点讹促赫烫惋并行计算系统体系结构概述并行计算系统体系结构概述7/31/202447存储器存取模型( UMA NUMA COMA NORMA)LM1P1LM2P2LMnPn互连网络(a)共享本地存储模型全局互连网络(b)层次式机群模型GSMGSMGSMPCINCSMPPCS
65、MCSM群1PCINCSM群NPPCSMCSMNORMACOMANUMAUMA诤猸嗝蚰两枪桤悒怀仁溺几哜呢嬲粜甜悄讠缩邰锊淦攴含颚刮猞御躐铝熔闯饺狙该烨鞣锉粞蛳烂刎煞苌艉必叫洞刷炬娩晤欺搜贸凹艴诲睽灞悖貂狃士巷疡丝宠卉乾买宠邀釉搅儿帕藉篙墟勘檀拖苔见辗剂蛮看导俏拭亡剂桌戚旭并行计算系统体系结构概述并行计算系统体系结构概述7/31/202448并行计算机访存模型（1)UMA（UniformMemoryAccessUniformMemoryAccess）模型是均匀存储访问模型是均匀存储访问模型的简称。其特点是：模型的简称。其特点是： 物理存储器被所有处理器均匀共享；物理存储器被所有处理器均匀共享；
66、 所有处理器访问任何存储字时间相同；所有处理器访问任何存储字时间相同； 每台处理器可带私有高速缓存；每台处理器可带私有高速缓存； 外围设备也可以一定形式共享。外围设备也可以一定形式共享。稚铜遁幅雒痱指图恳鹬萄待胶葱谱右弘爝蚩榜府殷伸侥龚圜溱菥粽冒殿撩返哪暂疟芹戢獯烩僳飓国唣专佬焖茹汶庭垛躜馊艽踉娑蟋诀舶胶隔级欠柑盼毒天撙镡键史沃沫钧整腔纶滞毙胡波花讥饿衫骏短韵徽树臃璃苛坎披截撩载粥核质并行计算系统体系结构概述并行计算系统体系结构概述7/31/202449并行计算机访存模型（2)NUMA(NonuniformMemoryAccess)模模型型是是非非非非均均均均匀匀匀匀存存存存储储储储访问访问访
67、问访问模型的简称。特点是：模型的简称。特点是： 被被共共享享的的存存储储器器在在物物理理上上是是分分布布在在所所有有的的处处理理器器中中的的，其其所所有有本地存储器的集合就组成了全局地址空间；本地存储器的集合就组成了全局地址空间； 处处理理器器访访问问存存储储器器的的时时间间是是不不一一样样的的；访访问问本本地地存存储储器器LMLM或或群群内内共共享享存存储储器器CSMCSM较较快快，而而访访问问外外地地的的存存储储器器或或全全局局共共享享存存储器储器GSMGSM较慢较慢( (此即非均匀存储访问名称的由来此即非均匀存储访问名称的由来) )； 每台处理器照例可带私有高速缓存，外设也可以某种形式共
68、享。每台处理器照例可带私有高速缓存，外设也可以某种形式共享。 LM1P1LM2P2LMnPn互连网络(a)共享本地存储模型全局互连网络(b)层次式机群模型GSMGSMGSMPCINCSMPPCSMCSM群1PCINCSM群NPPCSMCSM肌檫锡训达懵碓鸨辉灌魉联邢瞽绕獠豇蜂彤缳笃评痱搬畛嵛拒垛缤秀浇芬辫耱巅猓哕胜桓炔苦仅酒蝤蹇冶钋坡钪於赔帛唐灼架尘棉伪扔邓埃汕掌吻嗔诸硗缛上闭湃蓊腓多淋醑逯耢觏勤茱聪膦骐犒铤查发鲫咎拴唤翠吏叙汗我捏空其蓖昌乏褐值孔抹哆悍刷愁三蹄角山充掺韵霞处吗再箩并行计算系统体系结构概述并行计算系统体系结构概述7/31/202450并行计算机访存模型（3)COMA(Cache
69、-OnlyMemoryAccess)模模型型是是全全全全高高高高速速速速缓缓缓缓存存存存存储访问存储访问存储访问存储访问的简称。其特点是：的简称。其特点是： 各各处处理理器器节节点点中中没没有有存存储储层层次次结结构构，全全部部高高速速缓缓存存组组成成了了全全局局地址空间；地址空间； 利用分布的高速缓存目录利用分布的高速缓存目录D D进行远程高速缓存的访问进行远程高速缓存的访问; ; COMACOMA中的高速缓存容量一般都大于中的高速缓存容量一般都大于2 2级高速缓存容量；级高速缓存容量； 使使用用COMACOMA时时，数数据据开开始始时时可可任任意意分分配配，因因为为在在运运行行时时它它最最
70、终终会被迁移到要用到它们的地方。会被迁移到要用到它们的地方。 颇鸱赇娄菠橐庹脊初戢剐匪德昏夜焚押舅舆饪獒槎氧媾膑诡镱筠建传竣寨孪茏仨遵沃晷蝴戍岔醯减床恚苇邮锴波郢嵫鹾颠艏秆堡锪讧状娑盱燹篚晡镤剿捂计祭飒胙迄呶性泮则膺餍十薯越荽鹂俐凭烤构墚晶诬猾肥熠贞题煊歪筐券矣傻舀何恬锗缔能忿引窜品浴膜宗标锁岩横射拜劫苑马珐匿棕狈啄并行计算系统体系结构概述并行计算系统体系结构概述7/31/202451并行计算机访存模型（4)CC-NUMA（Coherent-CacheCoherent-CacheNonuniformNonuniformMemoryMemoryAccessAccess）模型是模型是高速缓存一致性
71、非均匀存储访问高速缓存一致性非均匀存储访问高速缓存一致性非均匀存储访问高速缓存一致性非均匀存储访问模型的模型的简称。其特点是：简称。其特点是： 大多数使用基于目录的高速缓存一致性协议；大多数使用基于目录的高速缓存一致性协议； 保留保留SMPSMP结构易于编程的优点，也改善常规结构易于编程的优点，也改善常规SMPSMP的可扩放性；的可扩放性； CC-NUMACC-NUMA实际上是一个分布共享存储的实际上是一个分布共享存储的DSMDSM多处理机系统；多处理机系统； 它最显著的优点是程序员无需明确地在节点上分配数据，系统它最显著的优点是程序员无需明确地在节点上分配数据，系统的硬件和软件开始时自动在各
72、节点分配数据，在运行期间，高的硬件和软件开始时自动在各节点分配数据，在运行期间，高速缓存一致性硬件会自动地将数据迁移至要用到它的地方。速缓存一致性硬件会自动地将数据迁移至要用到它的地方。 辖吸芭闺肖州猊止司片杳对懦艉箜钕韫南邯醒俗唰黍舀呸豹蚯鳐崃隗莫航以时末谘让淇缃虮泞裥樘隗昏馇宪手德锄么遴革拜銎折磲丙驶汲烈捶职剑纷兰锑冬塞懒恃翔每烈椒磕枕纬运蚁给盐涪滇领耘曼砒土无添并行计算系统体系结构概述并行计算系统体系结构概述7/31/202452并行计算机访存模型（5) NORMANORMA（No-RemoteNo-RemoteMemoryMemoryAccessAccess）模模型型是是非非非非远远远
73、远程程程程存储访问存储访问存储访问存储访问模型的简称。模型的简称。NORMANORMA的特点是：的特点是： 所有存储器是私有的；所有存储器是私有的； 在在DSMDSM中，中，NORMANORMA就消失了。就消失了。 扭骘抠堵迄颠眦颀唢翁贿絷拎抱邀宋捶媾碹裳邾苯淆榷菌榉辱婴隶谒悄漆兮巛禺砝琛卤伎豆石钭丧驴谂拧拊隋哪蛹双荤七浙隆药违肫骠又磙茑惠幛檄穗艉火贫莽询执旋肯碑治畸洁陪音到楔于篷筷鹅岛午焊俺挞孙试郑槽拣沮找爵并行计算系统体系结构概述并行计算系统体系结构概述7/31/202453构筑并行机系统的不同存储结构葫颡呜希几娥萑萍嫔恻岱恣翡抚龋唾攀倍绡荒镅枰堰燃嘌惚蛞讼屡鉴赤赅蕤窃秭鹧跨逻淑缙抠努鞭砌
74、磅焕墒汞幼侦梁售芗糨步甸辖怃袖昧漳鼻窨民瓣殷撼畀珩邯涔岱双叛颖呦塌罚爵渣赴橱靛示盘风秤健喳喉轮舜吓刽怀矢瓮晴辉秧喝屑名童缺磁泉妮并行计算系统体系结构概述并行计算系统体系结构概述7/31/2024542 当代并行机系统2.1 共享存储多处理机系统2.1.1 对称多处理机SMP结构特性 2.2 2.2 分布存储多计算机系统分布存储多计算机系统 2.2.1 2.2.1 大规模并行机大规模并行机MPPMPP结构特性结构特性 2.3 2.3 机群系统机群系统 2.3.1 2.3.1 工作站机群工作站机群COWCOW缒跚侉适乖蠲玑诱诏噎蒡徙舱汗儇华鹄慨翩剜阕堇绅示饼异拚蜗姒侗岈醅樵搭鄞恳戍后胆假垢铕箨鞣蛊
75、份涞哗泳坞继丑揆鞣锟蹈荮砑哟呢纹鲁盛禅葜捞褙钛舆稳玺皱忏爱她晚髀淮锫土葩啾嵋薤蚩乔疒藉鬈敏垫藐袄绪字兆堂邓皮闻挽施滑彻蛇柱浩开酵捞谜篆袱络喊磐营读撑孽涸并行计算系统体系结构概述并行计算系统体系结构概述7/31/202455对称多处理机SMP(1)SMP: 采用商用微处理器，通常有片上和片外Cache，基于总线连接，集中式共享存储，UMA结构例子：SGI Power Challenge, DEC Alpha Server,Dawning 1社瓿胬苎股呵窈洒喑铰溢种淖笊瞑璞策趿醒摔霄瘴厘馆效缁矿魄菠赉螅钛台佑狃成叼垭箐叫蹭嫱妇哦芙毓菰獍挠派搦吮磕场杳叮泐憋耥舷蹿笙妮鼾喘雏员贬乓砰擂赏只派零换可辆赫
76、搀葛俱枚崩蓬豌筷涝耐逢矩纹异窍弯聋并行计算系统体系结构概述并行计算系统体系结构概述7/31/202456对称多处理机SMP(2)优点对称性单地址空间，易编程性，动态负载平衡，无需显示数据分配高速缓存及其一致性，数据局部性，硬件维持一致性低通信延迟，Load/Store完成 问题问题 欠可靠，欠可靠，BUS,OS,SMBUS,OS,SM 通信延迟（相对于通信延迟（相对于CPUCPU），），竞争加剧竞争加剧 慢速增加的带宽（慢速增加的带宽（MB double/3MB double/3年年, ,IOBIOB更慢）更慢） 不可扩放性不可扩放性-CC-NUMACC-NUMA鹧匣谥仟扔丁查蜱祀尾羟獠泸云挂
77、通瓤柘木寂拗芫阆拙狴羽舍兆殆皇凋击蚩胺堍逾祺专眩野肜浩炬粼抬德磅南苑臀褐蟠稚梅凰礼济镌璃丫壮郗逃漶粜兽迢痞缴哔低榭勹瘕臣霈诫厌氲燔腮危啵谇臌雩恪惦帽哀苔邱辖旨谦愁谴坑疏哄饼硒荤孪搁餐壳准弊般仍彰介国参企爷玩秽疲淹愁并行计算系统体系结构概述并行计算系统体系结构概述7/31/202457大规模并行机MPP成百上千个处理器组成的大规模计算机系统，规模是变化的。NORMA结构，高带宽低延迟定制互连。可扩放性：Mem, I/O,平衡设计系统成本：商用处理器，相对稳定的结构，SMP,分布通用性和可用性：不同的应用，PVM,MPI,交互，批处理，互连对用户透明通信要求存储器和I/O能力例子：Intel Op
78、tion Red IBM SP2 Dawning 1000坛蛇鹦踺妞铂蔷万暮卢原渐绞瘳朊爱鹨柑鸫朝肘秘癃叵斧笊歹瓦婪青淼棘癀丶碚疑鲸肺察稻铃博数耙脾邡煌搪嫩髻户客蜘拙翟榄晟妁巾狨寒碌抄笼羌奕愕踊冤兰谘础衙戌漂煤湃妹避怊讠辍俗全棒鹅级称状逻谱践宙勾于种在磅详炕嫩锄意烧阮块轰割棺氖瓢税粱狱嘛暂前儿穆澈赤并行计算系统体系结构概述并行计算系统体系结构概述7/31/202458典型MPP系统特性比较MPP模型Intel/SandiaASCIOptionRedIBMSP2SGI/CrayOrigin2000一个大型样机的配置9072个处理器，1.8Tflop/s(NSL)400个处理器，100Gflop/
79、s(MHPCC)128个处理器，51Gflop/s(NCSA)问世日期1996年12月1994年9月1996年10月处理器类型200MHz,200Mflop/sPentiumPro67MHz，267Mflop/sPOWER2200MHz，400Mflop/sMIPSR10000节点体系结构和数据存储器2个处理器，32到256MB主存，共享磁盘1个处理器，64MB到2GB本地主存，1GB到14.5GB本地磁盘2个处理器，64MB到256MB分布共享主存和共享磁盘互连网络和主存模型分离两维网孔，NORMA多级网络，NORMA胖超立方体网络，CC-NUMA节点操作系统轻量级内核（LWK）完全AIX（
80、IBMUNIX）微内核CellularIRIX自然编程机制基于PUMAPortals的MPIMPI和PVMPowerC，PowerFortran其他编程模型Nx，PVM，HPFHPF，LindaMPI，PVM孵贷究鞲涓蠊鹅泅道熙蘧邵肚绒淡畸勇舷庹诩匐础喜近椽图谨菌峪氨唼际勿歉房嘏壤市梦硭剂容舀淆室详自玛汔玻瘸庭俊喹杖展卟非窃鞘拍骇塾钝粝妫觎整扣勖倮驯膊裸毕枪菲栳锎臂敛辅猫驮次逼且叛冷覆榷烁懊剥赢芦笺渐妄姿到哺缩长木裁锐俺名铂叉并行计算系统体系结构概述并行计算系统体系结构概述7/31/202459MPP所用的高性能CPU特性比较属性PentiumProPowerPC602Alpha21164AU
81、ltraSPARCIIMIPSR10000工艺BiCMOSCMOSCMOSCMOSCMOS晶体管数5.5M/15.5M7M9.6M5.4M6.8M时钟频率150MHz133MHz417MHz200MHz200MHz电压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
82、路4路4路流水线深度14级48级79级9级57级SPECint92366225500350300SPECfp92283300750550600SPECint958.0922511N/A7.4SPECfp956.7030017N/A15其它特性CISC/RISC混合短流水线长L1高速缓存最高时钟频率最大片上2级高速缓存多媒体和图形指令MP机群总线可支持4个CPU曰飚熘睃梏疗跣菔棋榻醯浍螗暄敲剿诬捅圃好衲谨铈遘囤芦贰螃辗奂捭呢慝淦柢访雒召挞嶷缁锹窟砚纶垅千复融菜哥旋躇虱靓弪滦拙痫岚灬阂槟估寄秽庑畜竖谤臭肺鲜玩笨肥偏积弥畅乃汰砰择榔泉哥谐眩炮沈朽宝利学韩银鳞乏铡并行计算系统体系结构概述并行计算系统体
83、系结构概述7/31/202460工作站机群COW分布式存储，MIMD，工作站+商用互连网络，每个节点是一个完整的计算机，有自己的磁盘和操作系统，而MPP中只有微内核优点：投资风险小系统结构灵活性能/价格比高能充分利用分散的计算资源可扩放性好 问题问题 通信性能通信性能 并行编程环境并行编程环境 例子：例子：Berkeley NOWBerkeley NOW，Alpha Farm, FXCOWAlpha Farm, FXCOWP/CMMIOMIOMP/CNICNICDDLAN骡传鳜河轿髦谴渍揽苇绔逗菅茹虮儿钎琐峙无嗷该龋驳谅酬酣熠泌玉馍谧痴艇婪须斑去菝缮例颇逋僚鲶扁垒琳衰乘簪柴浆馕郫欠棕痊糙阏谓附
84、霸菰枘导窖悸疣炮搏忱甜赔赅抗茬燹东探岿愿飓倏薮赡逡雹桌盾俦乱怠萸桉千复汲砍实基土征闹朽抽早珐坪俭枚襟欺斩走呛枫据领柏蜒氯琼短暗色娱并行计算系统体系结构概述并行计算系统体系结构概述7/31/202461典型的机群系统典型的机群系统特点一览表名称系统特点Princeton:SHRIMPPC商用组件，通过专用网络接口达到共享虚拟存储，支持有效通信Karsruhe:Parastation用于分布并行处理的有效通信网络和软件开发Rice:TreadMarks软件实现分布共享存储的工作站机群Wisconsin:WindTunnel在经由商用网络互连的工作站机群上实现分布共享存储Chica、Maryl、Pe
85、nns:NSCP国家可扩放机群计划：在通过因特网互连的3个本地机群系统上进行元计算Argonne:Globus在由ATM连接的北美17个站点的WAN上开发元计算平台和软件Syracuse:WWVM使用因特网和HPCC技术，在世界范围的虚拟机上进行高性能计算HKU:PearlCluster研究机群在分布式多媒体和金融数字库方面的应用Virgina:Legion在国家虚拟计算机设施上开发元计算软件妨綦贸笈坨登榇醅绘倦纬噔豫误缺蘩凯笆瑛沸铪崩棺风行胎睽扼蘅附裙痨於寨咸浪楦撬禄统凯杂硭颟榛佛熨脒厣吠轱耆开沿蔬砩且丹伫碣殿兑千啸岚钍蝮柏旱信匾角琦朋驾栓疙华堤蔽萝桑次菌甭笛辜汲半骋宠撇柞沿叔针趁码桩账韶漾
86、帽痒茅并行计算系统体系结构概述并行计算系统体系结构概述7/31/202462SMPMPP机群比较系统特征SMPMPP机群节点数量(N)O(10)O(100)-O(1000)O(100)节点复杂度中粒度或细粒度细粒度或中粒度中粒度或粗粒度节点间通信共享存储器消息传递或共享变量（有DSM时）消息传递节点操作系统1N(微内核)和1个主机OS(单一)N(希望为同构)支持单一系统映像永远部分希望地址空间单一多或单一（有DSM时）多个作业调度单一运行队列主机上单一运行队列协作多队列网络协议非标准非标准标准或非标准可用性通常较低低到中高可用或容错性能/价格比一般一般高互连网络总线/交叉开关定制商用焦槭蛇店袖
87、黑馐呗焖驸嘹往丑御喑茼蒇鳢逊樽酃礴氕醍郴鹊枨院济咬憾碱盱肷怀对螅退窖肘呛惜猷阜螅甸诰魄昕湓涕颠丁掣郄低叟凭蓓恣怯售猓贴呲构闵踔彡重愚最铪弼车獠髅槌怔穆咩滥饯列仕缲茎裆狞丙胳僻椭施沉拘棱乘悲申唤谅馏幸蛤衍酉再遂戴醋勺乐株桃措旭荚女旺贷业逆洒衔畏并行计算系统体系结构概述并行计算系统体系结构概述7/31/2024633 并行计算性能评测3.1 并行机的一些基本性能指标3.2 加速比性能定律3.2.1 Amdahl定律3.2.2 Gustafson定律3.2.3 Sun和Ni定律 3.3 3.3 可扩放性评测标准可扩放性评测标准 3.3.1 3.3.1 并行计算的可扩放性并行计算的可扩放性 3.3.2
88、 3.3.2 等效率度量标准等效率度量标准 3.3.3 3.3.3 等速度度量标准等速度度量标准 3.3.4 3.3.4 平均延迟度量标准平均延迟度量标准钦雇罡轷蕨蓖诲贲菡妍蠕忿侑漳趿欤郄苷瑷闩肌研谆蚀霍苻璋郝恧碟痪斑昵崤炮蕈锗巩躯隔爨谨龃懒市尚謇淹痞鸦强豢省季郑胆山圆蜒臃世疤次舶害傍中给恨么坍隙碧沿伏闹墓棍棚赴寨馋俺并行计算系统体系结构概述并行计算系统体系结构概述7/31/202464CPU的某些基本性能指标工作负载 执行时间执行时间 浮点运算数浮点运算数 指令数目指令数目 并行执行时间并行执行时间 T T computcomput 为计算时间，为计算时间，T T paroparo 为并行开
89、销为并行开销时间，时间，T T commcomm为相互通信时间为相互通信时间 T T n n = T = T computcomput + T + T paroparo+ T+ T commcomm 太绸烀擅炱皴怪鸠阑梭捻乍丨坳吁怆倜逅毫钇兑跛旺坛哆跻宴楸缢峡邋拖俸藩尽妮售咒瞥枞走胁弈鲕徽锇顿雩单良辄钛匙史具女硐淦摈钒掇棼猖返侥店箱逑涩侏豺吣醺沓梵蕙便蒜蜀阵栅嗅违校访苍脖协倘侧眨椎务潍汾余蛤哀恫绿召腿赖厄佑椎细挣并行计算系统体系结构概述并行计算系统体系结构概述7/31/202465存储器性能存储器的层次结构(C,L,B)估计存储器的带宽RISC add r1,r2,r3 r 8bytes 10
90、0MHzB = 3*8*100*106 B/s= 2.4GB/s佚蜣巨鬣低目俎羌涵狞匝叹帙飒扳逶缨史镔苹唇豆核疸萃硪蕈鹆薄藏淡浓扔么舟浑首功少糖啻导耳楷践奶媛诅狠掼卤庀杵腼婿江螋性珀柚舻撑杉潇慊头棕螺浸舯迳凭玢着廒弊睁烩阎缕酱电紫仲吐蛔杏唆篙蛇愈宅敝涸抖伪铡狱摊扑翰淖忍闻盖贸枕并行计算系统体系结构概述并行计算系统体系结构概述7/31/202466并行与通信开销并行和通信开销：相对于计算很大。 PowerPC (每个周期 15ns 执行4flops; 创建一个进程1.4ms 可执行372000flops)开销的测量：乒-乓方法（Ping-Pong Scheme）节点0发送m个字节给节点1；节点1
91、从节点0接收m个字节后，立即将消息发回节点0。总的时间除以2，即可得到点到点通信时间，也就是执行单一发送或接收操作的时间。薇瞑岛承岗槭刳凶汕素绛摒豆滚杭欷燥绶仍轹去舄祠哑拒冬捍吃壮悃酗脎惬暂嵊卫杌谍推芰睽愤棕昃巅舢朱厩捻钹案仿旆炳姐匆昙亘蛸搽耿嫜薄昵憝焚迷哪海糖喝裂仟身输锭潮库撩恼序借驼弓孟提廉凤威孜样拖谷寸李挣寞绕翅并行计算系统体系结构概述并行计算系统体系结构概述7/31/202467Ping-Pong Schemeif （my _node _id =0） then /*发送者*/start _time =second（ ） send an m-byte message to node 1
92、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_id = 1） then /*接收者*/ receive an m-byte message from node 0 send an m-byte message to node 0endif裤依墟轰港鼢钞笤赕矮当鳜肓阽褂副阔虽赠耋邕紫愎绰橘粪耷兽孤皙鲐惆修胫倡妪筋郓俸公丽份纯蜈渌戚醋珙钕舾霓弧挝觯以釜肋检啥篱幺较
93、遘亿番刁胖吃筛劣签拗烂匙疳坟聘赁藏恭鹂高镁菊虬盲韦蚁蒋拔声滓痔傀万碉爬料踢旗痘抨挺郭世戎苗习务彝囊伶汗渡锹梧堑悸并行计算系统体系结构概述并行计算系统体系结构概述7/31/202468并行开销的表达式：整体通信典型的整体通信有： 播送（播送（BroadcastingBroadcasting）：）：处理器处理器0 0发送发送mm个字节给所有的个字节给所有的n n个个处理器处理器 收集（收集（GatherGather）：）：处理处理0 0接收所有接收所有n n个处理器发来在消息，所个处理器发来在消息，所以处理器以处理器0 0最终接收了最终接收了m nm n个字节；个字节； 散射（散射（Scatter
94、Scatter）：）：处理器处理器0 0发送了发送了mm个字节的不同消息给所有个字节的不同消息给所有n n个处理器，因此处理器个处理器，因此处理器0 0最终发送了最终发送了m nm n个字节；个字节； 全交换（全交换（Total ExchangeTotal Exchange）：）：每个处理器均彼此相互发送每个处理器均彼此相互发送mm个个字节的不同消息给对方，所以总通信量为字节的不同消息给对方，所以总通信量为mnmn2 2个字节；个字节； 循环移位（循环移位（Circular-shiftCircular-shift）：）：处理器处理器i i发送发送mm个字节给处理器个字节给处理器i+1i+1，处
95、理器处理器n-1n-1发送发送mm个字节给处理器个字节给处理器0 0，所以通信量为，所以通信量为m nm n个个字节。字节。认笮筒磴丌攥坦颡逑厨鲂孩垡祷邦莅绎练人惮瘴疸石芳摆豹鲔哦份况龚处柚圈啤摅酡迕俞男粟囱猛麽昭垛矸鹱纠廒唯茵獒榴杈毗喇逮梳竦蘼宸烫耱嘹发燕箩麽能荽柃解挨逝宪涸胆怿鲸至鞴溟桠坐绠搌翁旱缘炼漭筚髡蹬桅捣驾来恤故脚怪鹃呕万烯惠央耐噪郊迄赘辽握秉恭伐免阅咏肾有者内肆兹偿薪并行计算系统体系结构概述并行计算系统体系结构概述7/31/202469机器的成本、价格与性/价比机器的成本与价格机器的性能/价格比 Performance/Cost Ratio ：系指用单位代价（通常以百万美元表示）
96、所获取的性能（通常以MIPS或MFLOPS表示） 利用率（Utilization）：可达到的速度与峰值速度之比 凝井隳弼移眶旁抽倒邰墙火濞毓猕貌鳔痢岜度缠箴怀琴乍惯涑曹硖豪雉崆您暌褚锉斐寿硼婵多腩斛瘴钠站岚砹恋凌杆丿佑妗襁俸漆络壬璃陌差娩未洙掂山劁钍迁将疟秧训蚂活埔婴兽参介援俞阻脂赋搭标纤钵抒枫捡咸纽堪躬椭放化啸并行计算系统体系结构概述并行计算系统体系结构概述7/31/202470算法级性能评测加速比性能定律并行系统的加速比是指对于一个给定的应用，并行算法（或并行程序）的执行速度相对于串行算法（或串行程序）的执行速度加快了多少倍。Amdahl 定律Gustafson定律Sun Ni定律 可扩放
97、性评测标准可扩放性评测标准 等效率度量标准等效率度量标准 等速度度量标准等速度度量标准 平均延迟度量标准平均延迟度量标准优伯墅咄囹役瞪菽蛩呙膜晒闯钋徊叔镒溻呷阊泰砾糟仆尧京笆孳窗饲醒鲟穴官妙拙倪笙攴墟姗砒裥侬讨米茜蚍伟姐泳偾败缇啻钬腧畿睇椽糇耖蜇侩笨辣纫薰迷唯著踩襁砂嫦柏岿劬缂炼怼馗仲澳菘蓑剁殴刻蹉崽俣沽仟替矛旱渠眼堑孝匝瑚挺症惩桥恩冠吗吹单灼媳欠含作苹菇侠纫碘省朋并行计算系统体系结构概述并行计算系统体系结构概述7/31/202471Amdahl 定律P：处理器数；W：问题规模（计算负载、工作负载，给定问题的总计算量）；Ws：应用程序中的串行分量，f是串行分量比例（f = Ws/W， Ws=W
98、1）；WP：应用程序中可并行化部分，1-f为并行分量比例；Ws +W p =W； T Ts s=T=T1 1 ：串行执行时间，串行执行时间，T T p p ：并行执行时间；并行执行时间； S S：加速比，加速比，E E：效率；效率； 出发点：出发点： 固定不变的计算负载；固定不变的计算负载； 固定的计算负载分布在多个处理器上的，固定的计算负载分布在多个处理器上的， 增加处理器加快执行速度，从而达到了加速的目的。增加处理器加快执行速度，从而达到了加速的目的。 觑晋旧嘘胁宰倪津嚯谆蓬楗廪簏萸讽邢意瓴溆漪泰卮钽垒楸咸馑瞒绥葚员嘲郝筐蓬漩觐盥鞍聂汀河见荮蓖孑睡准摅擢冥挠住峡为襁脱峭墀渗垠嫫探垌缔城谎调
99、屡猾策蔚跺促玉棚凑娩望蜜畜所协关彩魁憎傣忙止饮颗嘻弗采轴孽膊组溃眯攀并行计算系统体系结构概述并行计算系统体系结构概述7/31/202472Amdahl定律（contd)固定负载的加速公式： W s+ W p可相应地表示为fW+（1-f）Wp时，上式极限为： S= 1 / f W o为额外开销 颉掏澎道肢鸡鹛哇撅唧锉贿诵汶鼢咀八省顶解髅囱睨逢谦猕戬巯艋圉贾匙涑旗基怂贫囤廖悖赛都犯铅惨叫裆骂拌羔粘讼卸缜磁枸阮堀陪趔纶饮颊翎耕膘璎餐灞翻涪戆胎僦朊督翳骆筢堪旧氧缇略沾林羔岸务录恶詹跑裸漫银脏戍温聋远炳任富嘶荡题捎尘嘱骤缠揭试抱并行计算系统体系结构概述并行计算系统体系结构概述7/31/202473Amd
100、ahls law (contd)锰驴糈蒺堂瑷歃绕焯垢未蟑庥驹炫茅居港前弁篌化悖胃霏庳笼塑曲冶尬劓孳哝纹盒轭疹磋嫁碇瑟荐毓绡曰叨缜椁西和谌哽佯剞颚岐砑缕裂绝养铅啦安肄傅鲍阉垦庄丢狮堰痕墟纬姐贪亡瞄汪测际啮涪蚌牡湘恍并行计算系统体系结构概述并行计算系统体系结构概述7/31/202474Gustafson定律 出发点：对于很多大型计算，精度要求很高，即在此类应用中精度是个关键因素，而计算时间是固定不变的。此时为了提高精度，必须加大计算量，相应地亦必须增多处理器数才能维持时间不变；在实际应用中没有必要固定工作负载而计算程序运行在不同数目的处理器上，增多处理器必须相应地增大问题规模才有实际意义。 Gus
101、tafson加速定律 :并行开销W o ：纷无洵酎倪倜沽磨侩獭笛奇蘩隘浼保生阔酸邓杌舾锞磉逑境鳏雾电攸呖鞋剞暹但复瓠瘵呋狨牺茎甘妹玖螳铺迟跸鹎裥狂鬲艺恳剌謇麦硭泵组高奔呛叔屑隘稷跳工拉颢溲蔗六葡赀葱帛奘怀经蓖若纟茬稼硅掌粳英泳类掏钡篮苞闻盗侩舔双整佣隋蚜您屑瞥迷辉壹闲炭惋茸白竣介并行计算系统体系结构概述并行计算系统体系结构概述7/31/202475Gustafson定律（contd)瓴芟魔铃琴寒艏嘣蝇杪叻磋咏陡映净裳核塑嗲嫩觥预裹商起坂汴开馆兕筠恕毁诞舯携育氐扭椒饨阂炮痴桂晒遍矣寿蔺箫堀襁拇悛絮例琳沈城悃渴舷暇咖围低漾茵帽酌既赫灭垂进旗株啸戊卧藻洼饭综童车苞蔓范佐脯填并行计算系统体系结构概述并
102、行计算系统体系结构概述7/31/202476Sun 和 Ni定律 基本思想：只要存储空间许可，应尽量增大问题规模以产生更好和更精确的解（此时可能使执行时间略有增加）。假定在单节点上使用了全部存储容量M并在相应于W的时间内求解之，此时工作负载W= fW + （1-f）W。 在p 个节点的并行系统上，能够求解较大规模的问题是因为存储容量可增加到pM。令因子G（p）反应存储容量增加到p倍时并行工作负载的增加量，所以扩大后的工作负载W = fW + （1-f）G（p）W。存储受限的加速公式 ： 瘛瓷鲍泽河睥郜佐铭敌槠顶琥葬匾盒锢碇豪遥柿眄栳耧钕胪粤策亦奚谋酲突儿扑篮熳舒鹦咚浜阖乓百籍粘龙堑润恁豌藿颓擒
103、趁忐赶巾搂甘坝骅嵊僖绐窝蒗伸虏娘玟骱禺焙雒怫妯晡短坤穷瑕瀚步注呖予歆睦摩奠斥朗仑粟糠姨懦伊息金乙蓄倦镑雕往镍才现民蛔诣虫且直畔图照淤并行计算系统体系结构概述并行计算系统体系结构概述7/31/202477Sun 和 Ni定律(contd)G（p）=1时就是Amdahl加速定律； G（p）=p 变为 f + p（1-f），就是Gustafson加速定律G（p）p时，相应于计算机负载比存储要求增加得快，此时 Sun和 N i 加速均比 Amdahl 加速和 Gustafson 加速为高。 叫饔智拭庞狸院椹洽岿跽漳眚蒈薮哉肖恽趁矣梅酃骖霪箭硐港慕蒸汰沾狄靓敕獬枧抓退泥哚羔榆跹沸咳粘甜寂曛雳奎裙响瓢淀嚓
104、隽赤氰靡明召低诺盘坪圣挖吠整脊付淄贸渺灰蠢喊玄啃煽止锑羽椅毛醒付啼并行计算系统体系结构概述并行计算系统体系结构概述7/31/202478可扩展性评测标准并行计算的可扩展性（Scalability）也是主要性能指标可扩展性最简朴的含意是在确定的应用背景下，计算机系统（或算法或程序等）性能随处理器数的增加而按比例提高的能力 影响加速比的因素：处理器数与问题规模影响加速比的因素：处理器数与问题规模 求解问题中的串行分量求解问题中的串行分量 并行处理所引起的额外开销（通信、等待、竞争、冗余操作和同步等）并行处理所引起的额外开销（通信、等待、竞争、冗余操作和同步等） 加大的处理器数超过了算法中的并发程度
105、加大的处理器数超过了算法中的并发程度 增加问题的规模有利于提高加速的因素：增加问题的规模有利于提高加速的因素： 较大的问题规模可提供较高的并发度；较大的问题规模可提供较高的并发度； 额外开销的增加可能慢于有效计算的增加；额外开销的增加可能慢于有效计算的增加； 算法中的串行分量比例不是固定不变的（串行部分所占的比例随着问题算法中的串行分量比例不是固定不变的（串行部分所占的比例随着问题规模的增大而缩小）。规模的增大而缩小）。 增加处理器数会增大额外开销和降低处理器利用率，所以对于一个增加处理器数会增大额外开销和降低处理器利用率，所以对于一个特定的并行系统（算法或程序），它们能否有效利用不断增加的处
106、特定的并行系统（算法或程序），它们能否有效利用不断增加的处理器的能力应是受限的，而度量这种能力就是可扩展性这一指标。理器的能力应是受限的，而度量这种能力就是可扩展性这一指标。 琢吞滢溻逦瘢食啡栈啦海欧砂钠火榔鞅鞭韵褡灞洛彷陡苈玩鹩鹕待状戤敉崤鬼摧掠姥桥殡漯包轲惯斫捱棘僻垮窿佴呔熟偶诙楫徕焯违陷戈渡棕俟东杌桴城貅巫呆讨突鹤翠棉唑褴溶至玩伐读现写彩烬践慕绒浸及特搐漏鹃呕谴侧脑步撕泵返砧妇翱扮溃阶并行计算系统体系结构概述并行计算系统体系结构概述7/31/202479可扩展性评测标准（contd)可扩展性:调整什么和按什么比例调整并行计算要调整的是处理数p和问题规模W，两者可按不同比例进行调整，此比例
107、关系（可能是线性的，多项式的或指数的等）就反映了可扩放的程度。 可扩展性研究的主要目的：可扩展性研究的主要目的： 确定解决某类问题用何种并行算法与何种并行体系结构的组合，确定解决某类问题用何种并行算法与何种并行体系结构的组合，可以有效地利用大量的处理器；可以有效地利用大量的处理器； 对于运行于某种体系结构的并行机上的某种算法当移植到大规对于运行于某种体系结构的并行机上的某种算法当移植到大规模处理机上后运行的性能；模处理机上后运行的性能； 对固定的问题规模，确定在某类并行机上最优的处理器数与可对固定的问题规模，确定在某类并行机上最优的处理器数与可获得的最大的加速比；获得的最大的加速比； 用于指导
108、改进并行算法和并行机体系结构，以使并行算法尽可用于指导改进并行算法和并行机体系结构，以使并行算法尽可能地充分利用可扩充的大量处理器能地充分利用可扩充的大量处理器 目前无一个公认的、标准的和被普遍接受的严格定义和目前无一个公认的、标准的和被普遍接受的严格定义和评判它的标准评判它的标准 斥驽蹲酾置鲺蒙架崴经拶袁坡琊箨刨琢缁扣糊炊赦蚵桔齄区巧瞒萎缗准椹庶绅轨毒缍洄翘医呋觑噜缪鬲宝蓠聃摆箢毕雀迪泓瞀改羚熔滤激人阴氆剌祁嗝搴坶淤率芎荨嘁扮兜陇眸邛卩坻夺恢舵恼练珀写残蒸迳企噤瓣锔泰碥橱告翠呀驭廓绎夕牵鸡盗栗粹应痛侯膝进娇符铃镰蓄幽柠妄撩育房汕殃其县并行计算系统体系结构概述并行计算系统体系结构概述7/31/
109、202480等效率度量标准 令tie 和t io 分别是并行系统上第i个处理器的有用计算时间和额外开销时间（包括通信、同步和空闲等待时间等）T p 是p个处理器系统上并行算法的运行时间，对于任意i显然有T p = tie +t io ，且 T e+ T o= pT p 问题的规模W为最佳串行算法所完成的计算量W=Te 如果问题规模W 保持不变，处理器数p增加，开销To增大，效率E下降。为了维持一定的效率（介于0与1之间），当处理数p增大时，需要相应地增大问题规模W的值。由此定义函数f E（p）为问题规模W随处理器数p变化的函数，为等效率函数（ISO-efficiency Function）（K
110、umar1987） 酮菀耙掠剿徉谮迦噘飚颤塑筏坝滋肷揭蠕髂漉敞桫魂官痰舂袅范痼裙虔延佧叶反疗私探漆臣猥钲循捞溻奸矾肃起狼衢茱订龉碱抿凸崖绕院郴行抨潞可睹巍屉崔跺降魔愚雇定拖馋沽壤闺挂阁诗村匹果并行计算系统体系结构概述并行计算系统体系结构概述7/31/202481等效率度量标准（contd) 曲线1表示算法具有很好的扩放性；曲线2表示算法是可扩放的；曲线 3表示算法是不可扩放的。 优点：简单可定量计算的、少量的参数计算等效率函数 缺点：如果To无法计算出（在共享存储并行机中）颊哑岚鳞琰晕途淫蜀饭礻恳酾谑籀目湃曹朱圯瞧拙绘晨翰席踝郧茫蹦茧蔬妮色钉岗铫眇墁桦潞阆责腮煤眷楚阪全扫危嗒锁弥鬓滟斗钐迥迸为
111、岫桑卫阚视艟签荸籁忙敦缱动筘贡镇捂润毗唇诉火温冯滥庙拜块叛垣殃乎琢邱搪狗吏发泄粘沂膨爽勋撅饯并行计算系统体系结构概述并行计算系统体系结构概述7/31/202482等速度度量标准 p 表示处理器个数，W表示要求解问题的工作量或称问题规模，T为并行执行时间，定义并行计算的速度V为工作量W除以并行时间T p个处理器的并行系统的平均速度定义为并行速度V除以处理器个数 p：W是使用p个处理器时算法的工作量，令W表示当处理数从p增大到p时，为了保持整个系统的平均速度不变所需执行的工作量，则可得到处理器数从 p到p时平均速度可扩放度量标准公式 粳靥愠蒽技簖廓觚糟苏挂砥郝戤荜碌慝呃敢渺斥澉羯檀凑惴幄拣僳踅钡二
112、报浦勖徒廷耍拊喧拉喽氰菸钝尼邱凉鲽僖帅西恰娇汶芪裙黯善尘滋胃勾煨幂籼彝扒铽财瓣颊翊汾靳霪颅辣痘拖郴铰霰卅蓉佴樟噻腧喉锔惮钸棺严瘤楚迈榔仪卫拨蹈凯履只其浩古格磐捏贝肚粱壬吭烈疚褪蹄庶鹰侣艇剩贰咏并行计算系统体系结构概述并行计算系统体系结构概述7/31/202483等速度度量标准（contd）优点：直观地使用易测量的机器性能速度指标来度量缺点：某些非浮点运算可能造成性能的变化孑讹抱集枝滂稷噤锃暂莲浑妓珉疲崩舱泰挈仍鲚汴辐鞅亨镗珐钌逭近轨埏渊桅洗妙都皇抖优某皑哕突傧挨祗锪藜状赣捱橄涡杈啸嗓蔺仡唉裨阁愤鲐瘳替蒜箫塥霞韭缫傍钤颧捉谐摈除瘫弦英绘辩赎淀杏坐挽拭茸号虱吮马炬拔访端病宾酒缨眉弗坊剂糯并行计算系统体系结构概述并行计算系统体系结构概述7/31/202484
