并行計(jì)算中科大講義

并行計(jì)算中科大講義第1頁/共617頁國家高性能計(jì)算中心（合肥）22023/4/4并行計(jì)算——結(jié)構(gòu)?算法?編程第三篇并行數(shù)值算法第八章基本通信操作第九章稠密矩陣運(yùn)算第十章線性方程組的求解第十一章快速傅里葉變換第四篇并行程序設(shè)計(jì)第十二章并行程序設(shè)計(jì)基礎(chǔ)第十三章并行程序設(shè)計(jì)模型和共享存儲(chǔ)系統(tǒng)編程第十四章分布存儲(chǔ)系統(tǒng)并行編程第十五章并行程序設(shè)計(jì)環(huán)境與工具第2頁/共617頁國家高性能計(jì)算中心（合肥）32023/4/4第一章并行計(jì)算機(jī)系統(tǒng)及結(jié)構(gòu)模型1.1并行計(jì)算1.1.1并行計(jì)算與計(jì)算科學(xué)1.1.2當(dāng)代科學(xué)與工程問題的計(jì)算需求1.2并行計(jì)算機(jī)系統(tǒng)互連1.2.1系統(tǒng)互連1.2.2靜態(tài)互聯(lián)網(wǎng)絡(luò)1.2.3動(dòng)態(tài)互連網(wǎng)絡(luò)1.2.4標(biāo)準(zhǔn)互聯(lián)網(wǎng)絡(luò)1.3并行計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)1.3.1并行計(jì)算機(jī)結(jié)構(gòu)模型1.3.2并行計(jì)算機(jī)訪存模型第3頁/共617頁國家高性能計(jì)算中心（合肥）42023/4/4并行計(jì)算并行計(jì)算：并行機(jī)上所作的計(jì)算，又稱高性能計(jì)算或超級(jí)計(jì)算。計(jì)算科學(xué)：計(jì)算物理、計(jì)算化學(xué)、計(jì)算生物等科學(xué)與工程問題的需求：氣象預(yù)報(bào)、油藏模擬、核武器數(shù)值模擬、航天器設(shè)計(jì)、基因測(cè)序等。需求類型：計(jì)算密集、數(shù)據(jù)密集、網(wǎng)絡(luò)密集。美國HPCC計(jì)劃：重大挑戰(zhàn)性課題，3T性能美國Petaflops研究項(xiàng)目：Pflop/s。美國ASCI計(jì)劃：核武器數(shù)值模擬。第4頁/共617頁國家高性能計(jì)算中心（合肥）52023/4/4高性能計(jì)算機(jī)Intel（OptionRed)： 1Tflops,1997,PentiumProSGI(OptionBlueMountain): 3Tflops,1998,MIPS10000IBM(OptionWhite): 7Tflops,Top4,2001,Power3日本EarthSimulator: 35Tflops,Top1,2002,VPHewlett-PackardASCIQ： 7Tflops,Top2,3,2002,AlphaServer中國聯(lián)想： 1Tflops,Top43,2002

第5頁/共617頁國家高性能計(jì)算中心（合肥）62023/4/4系統(tǒng)互連不同帶寬與距離的互連技術(shù): 總線、SAN、LAN、MAN、WAN第6頁/共617頁國家高性能計(jì)算中心（合肥）72023/4/4局部總線、I/O總線、SAN和LAN第7頁/共617頁國家高性能計(jì)算中心（合肥）82023/4/4網(wǎng)絡(luò)性能指標(biāo)節(jié)點(diǎn)度（NodeDegree）：射入或射出一個(gè)節(jié)點(diǎn)的邊數(shù)。在單向網(wǎng)絡(luò)中，入射和出射邊之和稱為節(jié)點(diǎn)度。網(wǎng)絡(luò)直徑（NetworkDiameter）：網(wǎng)絡(luò)中任何兩個(gè)節(jié)點(diǎn)之間的最長距離，即最大路徑數(shù)。對(duì)剖寬度（BisectionWidth）：對(duì)分網(wǎng)絡(luò)各半所必須移去的最少邊數(shù)對(duì)剖帶寬（BisectionBandwidth）:每秒鐘內(nèi)，在最小的對(duì)剖平面上通過所有連線的最大信息位（或字節(jié)）數(shù)如果從任一節(jié)點(diǎn)觀看網(wǎng)絡(luò)都一樣，則稱網(wǎng)絡(luò)為對(duì)稱的（Symmetry）第8頁/共617頁國家高性能計(jì)算中心（合肥）92023/4/4靜態(tài)互連網(wǎng)絡(luò)與動(dòng)態(tài)互連網(wǎng)絡(luò)靜態(tài)互連網(wǎng)絡(luò)：處理單元間有著固定連接的一類網(wǎng)絡(luò)，在程序執(zhí)行期間，這種點(diǎn)到點(diǎn)的鏈接保持不變；典型的靜態(tài)網(wǎng)絡(luò)有一維線性陣列、二維網(wǎng)孔、樹連接、超立方網(wǎng)絡(luò)、立方環(huán)、洗牌交換網(wǎng)、蝶形網(wǎng)絡(luò)等動(dòng)態(tài)網(wǎng)絡(luò)：用交換開關(guān)構(gòu)成的，可按應(yīng)用程序的要求動(dòng)態(tài)地改變連接組態(tài)；典型的動(dòng)態(tài)網(wǎng)絡(luò)包括總線、交叉開關(guān)和多級(jí)互連網(wǎng)絡(luò)等。第9頁/共617頁國家高性能計(jì)算中心（合肥）102023/4/4靜態(tài)互連網(wǎng)絡(luò)（1）一維線性陣列（1-DLinearArray）：并行機(jī)中最簡(jiǎn)單、最基本的互連方式，每個(gè)節(jié)點(diǎn)只與其左、右近鄰相連，也叫二近鄰連接，N個(gè)節(jié)點(diǎn)用N-1條邊串接之，內(nèi)節(jié)點(diǎn)度為2，直徑為N-1，對(duì)剖寬度為1當(dāng)首、尾節(jié)點(diǎn)相連時(shí)可構(gòu)成循環(huán)移位器，在拓?fù)浣Y(jié)構(gòu)上等同于環(huán)，環(huán)可以是單向的或雙向的，其節(jié)點(diǎn)度恒為2，直徑或?yàn)椋p向環(huán)）或?yàn)镹-1（單向環(huán)），對(duì)剖寬度為2第10頁/共617頁國家高性能計(jì)算中心（合肥）112023/4/4靜態(tài)互連網(wǎng)絡(luò)（2）二維網(wǎng)孔（2-DMesh）：每個(gè)節(jié)點(diǎn)只與其上、下、左、右的近鄰相連（邊界節(jié)點(diǎn)除外），節(jié)點(diǎn)度為4，網(wǎng)絡(luò)直徑為，對(duì)剖寬度為在垂直方向上帶環(huán)繞，水平方向呈蛇狀，就變成Illiac網(wǎng)孔了，節(jié)點(diǎn)度恒為4，網(wǎng)絡(luò)直徑為，而對(duì)剖寬度為垂直和水平方向均帶環(huán)繞，則變成了2-D環(huán)繞（2-DTorus），節(jié)點(diǎn)度恒為4，網(wǎng)絡(luò)直徑為，對(duì)剖寬度為第11頁/共617頁國家高性能計(jì)算中心（合肥）122023/4/4靜態(tài)互連網(wǎng)絡(luò)（3）二叉樹：除了根、葉節(jié)點(diǎn)，每個(gè)內(nèi)節(jié)點(diǎn)只與其父節(jié)點(diǎn)和兩個(gè)子節(jié)點(diǎn)相連。節(jié)點(diǎn)度為3，對(duì)剖寬度為1，而樹的直徑為如果盡量增大節(jié)點(diǎn)度為，則直徑縮小為2，此時(shí)就變成了星形網(wǎng)絡(luò)，其對(duì)剖寬度為傳統(tǒng)二叉樹的主要問題是根易成為通信瓶頸。胖樹節(jié)點(diǎn)間的通路自葉向根逐漸變寬。第12頁/共617頁國家高性能計(jì)算中心（合肥）132023/4/4靜態(tài)互連網(wǎng)絡(luò)（4）超立方：一個(gè)n-立方由個(gè)頂點(diǎn)組成，3-立方如圖(a)所示；4-立方如圖(b)所示，由兩個(gè)3-立方的對(duì)應(yīng)頂點(diǎn)連接而成。n-立方的節(jié)點(diǎn)度為n，網(wǎng)絡(luò)直徑也是n，而對(duì)剖寬度為。如果將3-立方的每個(gè)頂點(diǎn)代之以一個(gè)環(huán)就構(gòu)成了如圖(d)所示的3-立方環(huán)，此時(shí)每個(gè)頂點(diǎn)的度為3，而不像超立方那樣節(jié)點(diǎn)度為n。第13頁/共617頁國家高性能計(jì)算中心（合肥）142023/4/4嵌入將網(wǎng)絡(luò)中的各節(jié)點(diǎn)映射到另一個(gè)網(wǎng)絡(luò)中去用膨脹（Dilation）系數(shù)來描述嵌入的質(zhì)量，它是指被嵌入網(wǎng)絡(luò)中的一條鏈路在所要嵌入的網(wǎng)絡(luò)中對(duì)應(yīng)所需的最大鏈路數(shù)如果該系數(shù)為1，則稱為完美嵌入。環(huán)網(wǎng)可完美嵌入到2-D環(huán)繞網(wǎng)中超立方網(wǎng)可完美嵌入到2－D環(huán)繞網(wǎng)中第14頁/共617頁國家高性能計(jì)算中心（合肥）152023/4/4嵌入第15頁/共617頁國家高性能計(jì)算中心（合肥）162023/4/4網(wǎng)絡(luò)名稱網(wǎng)絡(luò)規(guī)模節(jié)點(diǎn)度網(wǎng)絡(luò)直徑對(duì)剖寬度對(duì)稱鏈路數(shù)線性陣列21非環(huán)形2（雙向）2是2-D網(wǎng)孔

4非Illiac網(wǎng)孔

4非2-D環(huán)繞4是二叉樹31非星形2非超立方

nn是立方環(huán)3是靜態(tài)互連網(wǎng)絡(luò)特性比較第16頁/共617頁國家高性能計(jì)算中心（合肥）172023/4/4動(dòng)態(tài)互連網(wǎng)絡(luò)(1)總線：PCI、VME、Multics、Sbus、MicroChannel多處理機(jī)總線系統(tǒng)的主要問題包括總線仲裁、中斷處理、協(xié)議轉(zhuǎn)換、快速同步、高速緩存一致性協(xié)議、分事務(wù)、總線橋和層次總線擴(kuò)展等第17頁/共617頁國家高性能計(jì)算中心（合肥）182023/4/4動(dòng)態(tài)互連網(wǎng)絡(luò)（2）交叉開關(guān)（Crossbar）：?jiǎn)渭?jí)交換網(wǎng)絡(luò)，可為每個(gè)端口提供更高的帶寬。象電話交換機(jī)一樣，交叉點(diǎn)開關(guān)可由程序控制動(dòng)態(tài)設(shè)置其處于“開”或“關(guān)”狀態(tài)，而能提供所有（源、目的）對(duì)之間的動(dòng)態(tài)連接。交叉開關(guān)一般有兩種使用方式：一種是用于對(duì)稱的多處理機(jī)或多計(jì)算機(jī)機(jī)群中的處理器間的通信；另一種是用于SMP服務(wù)器或向量超級(jí)計(jì)算機(jī)中處理器和存儲(chǔ)器之間的存取。第18頁/共617頁國家高性能計(jì)算中心（合肥）192023/4/4動(dòng)態(tài)互聯(lián)網(wǎng)絡(luò)（3）單級(jí)交叉開關(guān)級(jí)聯(lián)起來形成多級(jí)互連網(wǎng)絡(luò)MIN（MultistageInterconnectionNetwork）第19頁/共617頁國家高性能計(jì)算中心（合肥）202023/4/4動(dòng)態(tài)互連網(wǎng)絡(luò)（4）交換開關(guān)模塊：

一個(gè)交換開關(guān)模塊有n個(gè)輸入和n個(gè)輸出，每個(gè)輸入可連接到任意輸出端口，但只允許一對(duì)一或一對(duì)多的映射，不允許多對(duì)一的映射，因?yàn)檫@將發(fā)生輸出沖突級(jí)間互連（InterstageConnection）：均勻洗牌、蝶網(wǎng)、多路均勻洗牌、交叉開關(guān)、立方連接n輸入的Ω網(wǎng)絡(luò)需要級(jí)開關(guān)，在Ilinois大學(xué)的Cedar[2]多處理機(jī)系統(tǒng)中采用了Ω網(wǎng)絡(luò)CrayY/MP多級(jí)網(wǎng)絡(luò)，該網(wǎng)絡(luò)用來支持8個(gè)向量處理器和256個(gè)存儲(chǔ)器模塊之間的數(shù)據(jù)傳輸。網(wǎng)絡(luò)能夠避免8個(gè)處理器同時(shí)進(jìn)行存儲(chǔ)器存取時(shí)的沖突。第20頁/共617頁國家高性能計(jì)算中心（合肥）212023/4/4動(dòng)態(tài)互連網(wǎng)絡(luò)比較n,節(jié)點(diǎn)規(guī)模w，數(shù)據(jù)寬度動(dòng)態(tài)互連網(wǎng)絡(luò)的復(fù)雜度和帶寬性能一覽表網(wǎng)絡(luò)特性總線系統(tǒng)多級(jí)互連網(wǎng)絡(luò)交叉開關(guān)硬件復(fù)雜度每個(gè)處理器帶寬

～報(bào)道的聚集帶寬SunFire服務(wù)器中的Gigaplane總線：2.67GB/sIBMSP2中的512節(jié)點(diǎn)的HPS：10.24GB/sDigital的千兆開關(guān)：3.4GB/s第21頁/共617頁國家高性能計(jì)算中心（合肥）222023/4/4標(biāo)準(zhǔn)互聯(lián)網(wǎng)絡(luò)（1）Myrinet:Myrinet是由Myricom公司設(shè)計(jì)的千兆位包交換網(wǎng)絡(luò)，其目的是為了構(gòu)筑計(jì)算機(jī)機(jī)群，使系統(tǒng)互連成為一種商業(yè)產(chǎn)品。Myrinet是基于加州理工學(xué)院開發(fā)的多計(jì)算機(jī)和VLSI技術(shù)以及在南加州大學(xué)開發(fā)的ATOMIC/LAN技術(shù)。Myrinet能假設(shè)任意拓?fù)浣Y(jié)構(gòu)，不必限定為開關(guān)網(wǎng)孔或任何規(guī)則的結(jié)構(gòu)。Myrinet在數(shù)據(jù)鏈路層具有可變長的包格式，對(duì)每條鏈路施行流控制和錯(cuò)誤控制，并使用切通選路法以及定制的可編程的主機(jī)接口。在物理層上，Myrinet網(wǎng)使用全雙工SAN鏈路，最長可達(dá)3米，峰值速率為（1.28＋1.28）Gbps（目前有2.56+2.56)Myrinet交換開關(guān):8,12,16端口Myrinet主機(jī)接口:32位的稱作LANai芯片的用戶定制的VLSI處理器，它帶有Myrinet接口、包接口、DMA引擎和快速靜態(tài)隨機(jī)存取存儲(chǔ)器SRAM。140oftheNovember2002TOP500useMyrinet,including15ofthetop100第22頁/共617頁國家高性能計(jì)算中心（合肥）232023/4/4Myrinet連接的LAN/Cluster第23頁/共617頁國家高性能計(jì)算中心（合肥）242023/4/4標(biāo)準(zhǔn)互連網(wǎng)絡(luò)（2)高性能并行接口（HiPPI）LosAlamos國家實(shí)驗(yàn)室于1987年提出的一個(gè)標(biāo)準(zhǔn)，其目的是試圖統(tǒng)一來自不同產(chǎn)商生產(chǎn)的所有大型機(jī)和超級(jí)計(jì)算機(jī)的接口。在大型機(jī)和超級(jí)計(jì)算機(jī)工業(yè)界，HiPPI作為短距離的系統(tǒng)到系統(tǒng)以及系統(tǒng)到外設(shè)連接的高速I/O通道。1993年，ANSIX3T9.3委員會(huì)認(rèn)可了HiPPI標(biāo)準(zhǔn)，它覆蓋了物理和數(shù)據(jù)鏈路層，但在這兩層之上的任何規(guī)定卻取決于用戶。HiPPI是個(gè)單工的點(diǎn)到點(diǎn)的數(shù)據(jù)傳輸接口，其速率可達(dá)800Mbps到1.6Gbps。開發(fā)成功了一種能提供潛在的6.4Gbps速率，比HiPPI快8倍且有很低時(shí)延的超級(jí)HiPPI技術(shù)，SGI公司和LosAlamos國家實(shí)驗(yàn)室都開發(fā)了用來構(gòu)筑速率高達(dá)25.6Gbps的HiPPI交換開關(guān)的HiPPI技術(shù)。HiPPI通道和HiPPI交換開關(guān)被用在SGIPowerChallenge服務(wù)器、IBM390主機(jī)、CrayY/MP、C90和T3D/T3E等系統(tǒng)

第24頁/共617頁國家高性能計(jì)算中心（合肥）252023/4/4使用HiPPI通道和開關(guān)構(gòu)筑的LAN主干網(wǎng)第25頁/共617頁國家高性能計(jì)算中心（合肥）262023/4/4標(biāo)準(zhǔn)互連網(wǎng)絡(luò)（3）光纖通道FC（FiberChannel）:通道和網(wǎng)絡(luò)標(biāo)準(zhǔn)的集成光纖通道既可以是共享介質(zhì)，也可以是一種交換技術(shù)光纖通道操作速度范圍可從100到133、200、400和800Mbps。FCSI廠商也正在推出未來具有更高速度（1、2或4Gbps）的光纖通道光纖通道的價(jià)值已被現(xiàn)在的某些千兆位局域網(wǎng)所證實(shí)，這些局域網(wǎng)就是基于光纖通道技術(shù)的連網(wǎng)拓?fù)浣Y(jié)構(gòu)的靈活性是光纖通道的主要財(cái)富，它支持點(diǎn)到點(diǎn)、仲裁環(huán)及交換光纖連接FDDI:光纖分布式數(shù)據(jù)接口FDDI（FiberDistributedDataInterface）FDDI采用雙向光纖令牌環(huán)可提供100-200Mbps數(shù)據(jù)傳輸速率FDDI具有互連大量設(shè)備的能力傳統(tǒng)的FDDI僅以異步方式操作第26頁/共617頁國家高性能計(jì)算中心（合肥）272023/4/4雙向FDDI環(huán)作為主干網(wǎng)第27頁/共617頁國家高性能計(jì)算中心（合肥）282023/4/4標(biāo)準(zhǔn)互聯(lián)網(wǎng)絡(luò)（4）ATM（AsynchronousTransferMode）:由成立于1991年的ATM論壇和ITU標(biāo)準(zhǔn)定義。ATM是一種獨(dú)立于介質(zhì)的消息傳輸協(xié)議，它將消息段變成更短的固定長度為53字節(jié)的報(bào)元進(jìn)行傳輸。這種技術(shù)是基于報(bào)元交換機(jī)制。ATM的目的是將實(shí)時(shí)和突發(fā)數(shù)據(jù)的傳輸合并成單一的網(wǎng)絡(luò)技術(shù)。ATM網(wǎng)絡(luò)支持從25到51、155和622Mbps不同的速率，其速率越低ATM交換器和使用的鏈路價(jià)格越低。第28頁/共617頁國家高性能計(jì)算中心（合肥）292023/4/4香港大學(xué)開發(fā)的Pearl機(jī)群第29頁/共617頁國家高性能計(jì)算中心（合肥）302023/4/4標(biāo)準(zhǔn)互連網(wǎng)絡(luò)（5）代別類型以太網(wǎng)10BaseT快速以太網(wǎng)100BaseT千兆位以太網(wǎng)1GB引入年代198219941997速度（帶寬）10Mb/s100Mb/s1Gb/s最大距離UTR（非屏蔽雙扭對(duì)）100m100m25－100mSTP（屏蔽雙扭對(duì)）同軸電纜500m100m25－100m多模光纖2Km412m（半雙工）2Km（全雙工）500m單模光纖25Km20Km3Km主要應(yīng)用領(lǐng)域文件共享，打印機(jī)共享COW計(jì)算，C/S結(jié)構(gòu)，大型數(shù)據(jù)庫存取等大型圖像文件，多媒體，因特網(wǎng)，內(nèi)部網(wǎng)，數(shù)據(jù)倉庫等第30頁/共617頁國家高性能計(jì)算中心（合肥）312023/4/4并行計(jì)算機(jī)結(jié)構(gòu)模型第31頁/共617頁國家高性能計(jì)算中心（合肥）322023/4/4并行計(jì)算機(jī)體系合一結(jié)構(gòu)

SMP、MPP、DSM和COW并行結(jié)構(gòu)漸趨一致。大量的節(jié)點(diǎn)通過高速網(wǎng)絡(luò)互連起來節(jié)點(diǎn)遵循Shell結(jié)構(gòu)：用專門定制的Shell電路將商用微處理器和節(jié)點(diǎn)的其它部分（包括板級(jí)Cache、局存、NIC和DISK）連接起來。優(yōu)點(diǎn)是CPU升級(jí)只需要更換Shell。第32頁/共617頁國家高性能計(jì)算中心（合肥）332023/4/4五種結(jié)構(gòu)特性一覽表屬性PVPSMPMPPDSMCOW結(jié)構(gòu)類型MIMDMIMDMIMDMIMDMIMD處理器類型專用定制商用商用商用商用互連網(wǎng)絡(luò)定制交叉開關(guān)總線、交叉開關(guān)定制網(wǎng)絡(luò)定制網(wǎng)絡(luò)商用網(wǎng)絡(luò)（以太ATM）通信機(jī)制共享變量共享變量消息傳遞共享變量消息傳遞地址空間單地址空間單地址空間多地址空間單地址空間多地址空間系統(tǒng)存儲(chǔ)器集中共享集中共享分布非共享分布共享分布非共享訪存模型UMAUMANORMANUMANORMA代表機(jī)器CrayC-90，CrayT-90，銀河1號(hào)IBMR50，SGIPowerChallenge，曙光1號(hào)IntelParagon，IBMSP2，曙光1000/2000StanfordDASH，CrayT3DBerkeleyNOW，AlphaFarm第33頁/共617頁國家高性能計(jì)算中心（合肥）342023/4/4并行計(jì)算機(jī)訪存模型（1)UMA（UniformMemoryAccess）模型是均勻存儲(chǔ)訪問模型的簡(jiǎn)稱。其特點(diǎn)是：物理存儲(chǔ)器被所有處理器均勻共享；所有處理器訪問任何存儲(chǔ)字取相同的時(shí)間；每臺(tái)處理器可帶私有高速緩存；外圍設(shè)備也可以一定形式共享。第34頁/共617頁國家高性能計(jì)算中心（合肥）352023/4/4并行計(jì)算機(jī)訪存模型（2)NUMA(NonuniformMemoryAccess)模型是非均勻存儲(chǔ)訪問模型的簡(jiǎn)稱。特點(diǎn)是：被共享的存儲(chǔ)器在物理上是分布在所有的處理器中的，其所有本地存儲(chǔ)器的集合就組成了全局地址空間；處理器訪問存儲(chǔ)器的時(shí)間是不一樣的；訪問本地存儲(chǔ)器LM或群內(nèi)共享存儲(chǔ)器CSM較快，而訪問外地的存儲(chǔ)器或全局共享存儲(chǔ)器GSM較慢(此即非均勻存儲(chǔ)訪問名稱的由來)；每臺(tái)處理器照例可帶私有高速緩存，外設(shè)也可以某種形式共享。

LM1P1LM2P2LMnPn互連網(wǎng)絡(luò)(a)共享本地存儲(chǔ)模型全局互連網(wǎng)絡(luò)(b)層次式機(jī)群模型GSMGSMGSM…………PCINCSMPPCSMCSM群1……PCINCSM群NPPCSMCSM……第35頁/共617頁國家高性能計(jì)算中心（合肥）362023/4/4并行計(jì)算機(jī)訪存模型（3)COMA(Cache-OnlyMemoryAccess)模型是全高速緩存存儲(chǔ)訪問的簡(jiǎn)稱。其特點(diǎn)是：各處理器節(jié)點(diǎn)中沒有存儲(chǔ)層次結(jié)構(gòu)，全部高速緩存組成了全局地址空間；利用分布的高速緩存目錄D進(jìn)行遠(yuǎn)程高速緩存的訪問;COMA中的高速緩存容量一般都大于2級(jí)高速緩存容量；使用COMA時(shí)，數(shù)據(jù)開始時(shí)可任意分配，因?yàn)樵谶\(yùn)行時(shí)它最終會(huì)被遷移到要用到它們的地方。

第36頁/共617頁國家高性能計(jì)算中心（合肥）372023/4/4并行計(jì)算機(jī)訪存模型（4)CC-NUMA（Coherent-CacheNonuniformMemoryAccess）模型是高速緩存一致性非均勻存儲(chǔ)訪問模型的簡(jiǎn)稱。其特點(diǎn)是：大多數(shù)使用基于目錄的高速緩存一致性協(xié)議；保留SMP結(jié)構(gòu)易于編程的優(yōu)點(diǎn)，也改善常規(guī)SMP的可擴(kuò)放性；CC-NUMA實(shí)際上是一個(gè)分布共享存儲(chǔ)的DSM多處理機(jī)系統(tǒng)；它最顯著的優(yōu)點(diǎn)是程序員無需明確地在節(jié)點(diǎn)上分配數(shù)據(jù)，系統(tǒng)的硬件和軟件開始時(shí)自動(dòng)在各節(jié)點(diǎn)分配數(shù)據(jù)，在運(yùn)行期間，高速緩存一致性硬件會(huì)自動(dòng)地將數(shù)據(jù)遷移至要用到它的地方。

第37頁/共617頁國家高性能計(jì)算中心（合肥）382023/4/4并行計(jì)算機(jī)訪存模型（5)NORMA（No-RemoteMemoryAccess）模型是非遠(yuǎn)程存儲(chǔ)訪問模型的簡(jiǎn)稱。NORMA的特點(diǎn)是：所有存儲(chǔ)器是私有的；絕大數(shù)NUMA都不支持遠(yuǎn)程存儲(chǔ)器的訪問；在DSM中，NORMA就消失了。

第38頁/共617頁國家高性能計(jì)算中心（合肥）392023/4/4構(gòu)筑并行機(jī)系統(tǒng)的不同存儲(chǔ)結(jié)構(gòu)第39頁/共617頁國家高性能計(jì)算中心（合肥）402023/4/4第二章當(dāng)代并行機(jī)系統(tǒng)2.1共享存儲(chǔ)多處理機(jī)系統(tǒng)2.1.1對(duì)稱多處理機(jī)SMP結(jié)構(gòu)特性2.2分布存儲(chǔ)多計(jì)算機(jī)系統(tǒng)2.2.1大規(guī)模并行機(jī)MPP結(jié)構(gòu)特性2.3機(jī)群系統(tǒng)2.3.1大規(guī)模并行處理系統(tǒng)MPP機(jī)群SP22.3.2工作站機(jī)群COW第40頁/共617頁國家高性能計(jì)算中心（合肥）412023/4/4對(duì)稱多處理機(jī)SMP(1)SMP:采用商用微處理器，通常有片上和片外Cache，基于總線連接，集中式共享存儲(chǔ)，UMA結(jié)構(gòu)例子：SGIPowerChallenge,DECAlphaServer,Dawning1第41頁/共617頁國家高性能計(jì)算中心（合肥）422023/4/4對(duì)稱多處理機(jī)SMP(2)優(yōu)點(diǎn)對(duì)稱性單地址空間，易編程性，動(dòng)態(tài)負(fù)載平衡，無需顯示數(shù)據(jù)分配高速緩存及其一致性，數(shù)據(jù)局部性，硬件維持一致性低通信延遲，Load/Store完成問題欠可靠，BUS,OS,SM通信延遲（相對(duì)于CPU），競(jìng)爭(zhēng)加劇慢速增加的帶寬（MBdouble/3年,IOB更慢）不可擴(kuò)放性---〉CC-NUMA第42頁/共617頁國家高性能計(jì)算中心（合肥）432023/4/4大規(guī)模并行機(jī)MPP成百上千個(gè)處理器組成的大規(guī)模計(jì)算機(jī)系統(tǒng)，規(guī)模是變化的。NORMA結(jié)構(gòu)，高帶寬低延遲定制互連?？蓴U(kuò)放性：Mem,I/O,平衡設(shè)計(jì)系統(tǒng)成本：商用處理器，相對(duì)穩(wěn)定的結(jié)構(gòu)，SMP,分布通用性和可用性：不同的應(yīng)用，PVM,MPI,交互，批處理，互連對(duì)用戶透明，單一系統(tǒng)映象，故障通信要求存儲(chǔ)器和I/O能力例子：IntelOptionRed

IBMSP2Dawning1000第43頁/共617頁國家高性能計(jì)算中心（合肥）442023/4/4典型MPP系統(tǒng)特性比較MPP模型Intel/SandiaASCIOptionRedIBMSP2SGI/CrayOrigin2000一個(gè)大型樣機(jī)的配置9072個(gè)處理器，1.8Tflop/s(NSL)400個(gè)處理器，100Gflop/s(MHPCC)128個(gè)處理器，51Gflop/s(NCSA)問世日期1996年12月1994年9月1996年10月處理器類型200MHz,200Mflop/sPentiumPro67MHz，267Mflop/sPOWER2200MHz，400Mflop/sMIPSR10000節(jié)點(diǎn)體系結(jié)構(gòu)和數(shù)據(jù)存儲(chǔ)器2個(gè)處理器，32到256MB主存，共享磁盤1個(gè)處理器，64MB到2GB本地主存，1GB到14.5GB本地磁盤2個(gè)處理器，64MB到256MB分布共享主存和共享磁盤互連網(wǎng)絡(luò)和主存模型分離兩維網(wǎng)孔，NORMA多級(jí)網(wǎng)絡(luò)，NORMA胖超立方體網(wǎng)絡(luò)，CC-NUMA節(jié)點(diǎn)操作系統(tǒng)輕量級(jí)內(nèi)核（LWK）完全AIX（IBMUNIX）微內(nèi)核CellularIRIX自然編程機(jī)制基于PUMAPortals的MPIMPI和PVMPowerC，PowerFortran其他編程模型Nx，PVM，HPFHPF，LindaMPI，PVM第44頁/共617頁國家高性能計(jì)算中心（合肥）452023/4/4MPP所用的高性能CPU特性比較屬性PentiumProPowerPC602Alpha21164AUltraSPARCIIMIPSR10000工藝BiCMOSCMOSCMOSCMOSCMOS晶體管數(shù)5.5M/15.5M7M9.6M5.4M6.8M時(shí)鐘頻率150MHz133MHz417MHz200MHz200MHz電壓2.9V3.3V2.2V2.5V3.3V功率20W30W20W28W30W字長32位64位64位64位64位I/O高速緩存8KB/8KB32KB/32KB8KB/8KB16KB/16KB32KB/32KB2級(jí)高速緩存256KB(多芯片模塊)1~128MB(片外)96KB(片上)16MB(片外)16MB(片外)執(zhí)行單元5個(gè)單元6個(gè)單元4個(gè)單元9個(gè)單元5個(gè)單元超標(biāo)量3路(Way)4路4路4路4路流水線深度14級(jí)4~8級(jí)7~9級(jí)9級(jí)5~7級(jí)SPECint92366225>500350300SPECfp92283300>750550600SPECint958.09225>11N/A7.4SPECfp956.70300>17N/A15其它特性CISC/RISC混合短流水線長L1高速緩存最高時(shí)鐘頻率最大片上2級(jí)高速緩存多媒體和圖形指令MP機(jī)群總線可支持4個(gè)CPU第45頁/共617頁國家高性能計(jì)算中心（合肥）462023/4/4機(jī)群型大規(guī)模并行機(jī)SP2設(shè)計(jì)策略：機(jī)群體系結(jié)構(gòu)標(biāo)準(zhǔn)環(huán)境標(biāo)準(zhǔn)編程模型系統(tǒng)可用性精選的單一系統(tǒng)映像系統(tǒng)結(jié)構(gòu)：高性能開關(guān)HPS多級(jí)Ω網(wǎng)絡(luò)寬節(jié)點(diǎn)、窄節(jié)點(diǎn)和窄節(jié)點(diǎn)2第46頁/共617頁國家高性能計(jì)算中心（合肥）472023/4/4工作站機(jī)群COW分布式存儲(chǔ)，MIMD，工作站+商用互連網(wǎng)絡(luò)，每個(gè)節(jié)點(diǎn)是一個(gè)完整的計(jì)算機(jī)，有自己的磁盤和操作系統(tǒng)，而MPP中只有微內(nèi)核優(yōu)點(diǎn)：投資風(fēng)險(xiǎn)小系統(tǒng)結(jié)構(gòu)靈活性能/價(jià)格比高能充分利用分散的計(jì)算資源可擴(kuò)放性好問題通信性能并行編程環(huán)境例子：BerkeleyNOW，AlphaFarm,FXCOWP/CMMIOMIOMP/CNICNICDDLAN第47頁/共617頁國家高性能計(jì)算中心（合肥）482023/4/4典型的機(jī)群系統(tǒng)典型的機(jī)群系統(tǒng)特點(diǎn)一覽表名稱系統(tǒng)特點(diǎn)Princeton:SHRIMPPC商用組件，通過專用網(wǎng)絡(luò)接口達(dá)到共享虛擬存儲(chǔ)，支持有效通信Karsruhe:Parastation用于分布并行處理的有效通信網(wǎng)絡(luò)和軟件開發(fā)Rice:TreadMarks軟件實(shí)現(xiàn)分布共享存儲(chǔ)的工作站機(jī)群Wisconsin:WindTunnel在經(jīng)由商用網(wǎng)絡(luò)互連的工作站機(jī)群上實(shí)現(xiàn)分布共享存儲(chǔ)Chica、Maryl、Penns:NSCP國家可擴(kuò)放機(jī)群計(jì)劃：在通過因特網(wǎng)互連的3個(gè)本地機(jī)群系統(tǒng)上進(jìn)行元計(jì)算Argonne:Globus在由ATM連接的北美17個(gè)站點(diǎn)的WAN上開發(fā)元計(jì)算平臺(tái)和軟件Syracuse:WWVM使用因特網(wǎng)和HPCC技術(shù)，在世界范圍的虛擬機(jī)上進(jìn)行高性能計(jì)算HKU:PearlCluster研究機(jī)群在分布式多媒體和金融數(shù)字庫方面的應(yīng)用Virgina:Legion在國家虛擬計(jì)算機(jī)設(shè)施上開發(fā)元計(jì)算軟件第48頁/共617頁國家高性能計(jì)算中心（合肥）492023/4/4SMP\MPP\機(jī)群比較系統(tǒng)特征SMPMPP機(jī)群節(jié)點(diǎn)數(shù)量(N)O(10)O(100)-O(1000)O(100)節(jié)點(diǎn)復(fù)雜度中粒度或細(xì)粒度細(xì)粒度或中粒度中粒度或粗粒度節(jié)點(diǎn)間通信

共享存儲(chǔ)器消息傳遞或共享變量（有DSM時(shí)）消息傳遞節(jié)點(diǎn)操作系統(tǒng)1N(微內(nèi)核)和1個(gè)主機(jī)OS(單一)N(希望為同構(gòu))支持單一系統(tǒng)映像永遠(yuǎn)部分希望地址空間單一多或單一（有DSM時(shí)）多個(gè)作業(yè)調(diào)度單一運(yùn)行隊(duì)列主機(jī)上單一運(yùn)行隊(duì)列協(xié)作多隊(duì)列網(wǎng)絡(luò)協(xié)議非標(biāo)準(zhǔn)非標(biāo)準(zhǔn)標(biāo)準(zhǔn)或非標(biāo)準(zhǔn)可用性通常較低低到中高可用或容錯(cuò)性能/價(jià)格比一般一般高互連網(wǎng)絡(luò)總線/交叉開關(guān)定制商用第49頁/共617頁國家高性能計(jì)算中心（合肥）502023/4/4第三章并行計(jì)算性能評(píng)測(cè)3.1并行機(jī)的一些基本性能指標(biāo)3.2加速比性能定律3.2.1Amdahl定律3.2.2Gustafson定律3.2.3Sun和Ni定律3.3可擴(kuò)放性評(píng)測(cè)標(biāo)準(zhǔn)3.3.1并行計(jì)算的可擴(kuò)放性3.3.2等效率度量標(biāo)準(zhǔn)3.3.3等速度度量標(biāo)準(zhǔn)3.3.4平均延遲度量標(biāo)準(zhǔn)第50頁/共617頁國家高性能計(jì)算中心（合肥）512023/4/4CPU的某些基本性能指標(biāo)工作負(fù)載執(zhí)行時(shí)間浮點(diǎn)運(yùn)算數(shù)指令數(shù)目并行執(zhí)行時(shí)間Tcomput

為計(jì)算時(shí)間，Tparo為并行開銷時(shí)間，Tcomm為相互通信時(shí)間

Tn=Tcomput+Tparo+Tcomm例：估計(jì)APRAM模型下執(zhí)行時(shí)間

第51頁/共617頁國家高性能計(jì)算中心（合肥）522023/4/4存儲(chǔ)器性能存儲(chǔ)器的層次結(jié)構(gòu)(C,L,B)估計(jì)存儲(chǔ)器的帶寬RISCaddr1,r2,r3r8bytes100MHzB=3*8*100*106B/s=2.4GB/s第52頁/共617頁國家高性能計(jì)算中心（合肥）532023/4/4并行與通信開銷并行和通信開銷：相對(duì)于計(jì)算很大。

PowerPC(每個(gè)周期15ns執(zhí)行4flops;

創(chuàng)建一個(gè)進(jìn)程1.4ms可執(zhí)行372000flops)開銷的測(cè)量：乒--乓方法（Ping-PongScheme）節(jié)點(diǎn)0發(fā)送m個(gè)字節(jié)給節(jié)點(diǎn)1；節(jié)點(diǎn)1從節(jié)點(diǎn)0接收m個(gè)字節(jié)后，立即將消息發(fā)回節(jié)點(diǎn)0?？偟臅r(shí)間除以2，即可得到點(diǎn)到點(diǎn)通信時(shí)間，也就是執(zhí)行單一發(fā)送或接收操作的時(shí)間?？梢话慊癁闊嵬炼狗ǎ℉ot-Potato），也稱為救火隊(duì)法（Fire-Brigade)0——1——2——

…

——-n-1——0

第53頁/共617頁國家高性能計(jì)算中心（合肥）542023/4/4Ping-PongSchemeif（my_node_id=0）then/*發(fā)送者*/

start_time=second（） sendanm-bytemessagetonode1 receiveanm-bytemessagefromnode1 end_time=second（） total_time=end_time–start_timecommunication_time[i]=total_time/2 elseif（my_node_id=1）then/*接收者*/

receiveanm-bytemessagefromnode0 sendanm-bytemessagetonode0 endif第54頁/共617頁國家高性能計(jì)算中心（合肥）552023/4/4并行開銷的表達(dá)式：點(diǎn)到點(diǎn)通信通信開銷

t(m)=t0+m/r∞通信啟動(dòng)時(shí)間t0漸近帶寬r∞

：傳送無限長的消息時(shí)的通信速率半峰值長度m1/2：達(dá)到一半漸近帶寬所要的消息長度特定性能π0：表示短消息帶寬

t0=m1/2/

r∞=1/π0第55頁/共617頁國家高性能計(jì)算中心（合肥）562023/4/4并行開銷的表達(dá)式：整體通信典型的整體通信有：播送（Broadcasting）：處理器0發(fā)送m個(gè)字節(jié)給所有的n個(gè)處理器收集（Gather）：處理0接收所有n個(gè)處理器發(fā)來在消息，所以處理器0最終接收了mn個(gè)字節(jié)；散射（Scatter）：處理器0發(fā)送了m個(gè)字節(jié)的不同消息給所有n個(gè)處理器，因此處理器0最終發(fā)送了mn個(gè)字節(jié)；全交換（TotalExchange）：每個(gè)處理器均彼此相互發(fā)送m個(gè)字節(jié)的不同消息給對(duì)方，所以總通信量為mn2個(gè)字節(jié)；循環(huán)移位（Circular-shift）：處理器i發(fā)送m個(gè)字節(jié)給處理器i+1，處理器n-1發(fā)送m個(gè)字節(jié)給處理器0，所以通信量為mn個(gè)字節(jié)。第56頁/共617頁國家高性能計(jì)算中心（合肥）572023/4/4機(jī)器的成本、價(jià)格與性/價(jià)比機(jī)器的成本與價(jià)格機(jī)器的性能/價(jià)格比Performance/CostRatio：系指用單位代價(jià)（通常以百萬美元表示）所獲取的性能（通常以MIPS或MFLOPS表示）利用率（Utilization）：可達(dá)到的速度與峰值速度之比第57頁/共617頁國家高性能計(jì)算中心（合肥）582023/4/4算法級(jí)性能評(píng)測(cè)加速比性能定律并行系統(tǒng)的加速比是指對(duì)于一個(gè)給定的應(yīng)用，并行算法（或并行程序）的執(zhí)行速度相對(duì)于串行算法（或串行程序）的執(zhí)行速度加快了多少倍。Amdahl定律Gustafson定律SunNi定律可擴(kuò)放性評(píng)測(cè)標(biāo)準(zhǔn)等效率度量標(biāo)準(zhǔn)等速度度量標(biāo)準(zhǔn)平均延遲度量標(biāo)準(zhǔn)第58頁/共617頁國家高性能計(jì)算中心（合肥）592023/4/4Amdahl定律P：處理器數(shù)；W：?jiǎn)栴}規(guī)模（計(jì)算負(fù)載、工作負(fù)載，給定問題的總計(jì)算量）；Ws：應(yīng)用程序中的串行分量，f是串行分量比例（f=Ws/W，Ws=W1）；WP：應(yīng)用程序中可并行化部分，1-f為并行分量比例；Ws+Wp=W；Ts=T1：串行執(zhí)行時(shí)間，Tp：并行執(zhí)行時(shí)間；S：加速比，E：效率；出發(fā)點(diǎn)：固定不變的計(jì)算負(fù)載；固定的計(jì)算負(fù)載分布在多個(gè)處理器上的，增加處理器加快執(zhí)行速度，從而達(dá)到了加速的目的。第59頁/共617頁國家高性能計(jì)算中心（合肥）602023/4/4Amdahl定律（cont‘d)固定負(fù)載的加速公式：

Ws+Wp可相應(yīng)地表示為f+（1-f）

p→∞時(shí)，上式極限為：S=1/fWo為額外開銷 第60頁/共617頁國家高性能計(jì)算中心（合肥）612023/4/4Amdahl’slaw(cont’d)第61頁/共617頁國家高性能計(jì)算中心（合肥）622023/4/4Gustafson定律出發(fā)點(diǎn)：對(duì)于很多大型計(jì)算，精度要求很高，即在此類應(yīng)用中精度是個(gè)關(guān)鍵因素，而計(jì)算時(shí)間是固定不變的。此時(shí)為了提高精度，必須加大計(jì)算量，相應(yīng)地亦必須增多處理器數(shù)才能維持時(shí)間不變；除非學(xué)術(shù)研究，在實(shí)際應(yīng)用中沒有必要固定工作負(fù)載而計(jì)算程序運(yùn)行在不同數(shù)目的處理器上，增多處理器必須相應(yīng)地增大問題規(guī)模才有實(shí)際意義。

Gustafson加速定律:并行開銷Wo：第62頁/共617頁國家高性能計(jì)算中心（合肥）632023/4/4Gustafson定律（cont‘d)第63頁/共617頁國家高性能計(jì)算中心（合肥）642023/4/4Sun和Ni定律基本思想：只要存儲(chǔ)空間許可，應(yīng)盡量增大問題規(guī)模以產(chǎn)生更好和更精確的解（此時(shí)可能使執(zhí)行時(shí)間略有增加）。假定在單節(jié)點(diǎn)上使用了全部存儲(chǔ)容量M并在相應(yīng)于W的時(shí)間內(nèi)求解之，此時(shí)工作負(fù)載W=fW+（1-f）W。在p個(gè)節(jié)點(diǎn)的并行系統(tǒng)上，能夠求解較大規(guī)模的問題是因?yàn)榇鎯?chǔ)容量可增加到pM。令因子G（p）反應(yīng)存儲(chǔ)容量增加到p倍時(shí)并行工作負(fù)載的增加量，所以擴(kuò)大后的工作負(fù)載W=fW+（1-f）G（p）W。存儲(chǔ)受限的加速公式：并行開銷Wo:第64頁/共617頁國家高性能計(jì)算中心（合肥）652023/4/4Sun和Ni定律(cont’d)G（p）=1時(shí)就是Amdahl加速定律；

G（p）=p變?yōu)閒+p（1-f），就是Gustafson加速定律G（p）>p時(shí)，相應(yīng)于計(jì)算機(jī)負(fù)載比存儲(chǔ)要求增加得快，此時(shí)Sun和Ni加速均比Amdahl加速和Gustafson加速為高。第65頁/共617頁國家高性能計(jì)算中心（合肥）662023/4/4加速比討論參考的加速經(jīng)驗(yàn)公式：p/logp≤S≤P線性加速比：很少通信開銷的矩陣相加、內(nèi)積運(yùn)算等p/logp的加速比：分治類的應(yīng)用問題通信密集類的應(yīng)用問題：S=1/C（p）超線性加速絕對(duì)加速：最佳并行算法與串行算法相對(duì)加速：同一算法在單機(jī)和并行機(jī)的運(yùn)行時(shí)間第66頁/共617頁國家高性能計(jì)算中心（合肥）672023/4/4可擴(kuò)放性評(píng)測(cè)標(biāo)準(zhǔn)并行計(jì)算的可擴(kuò)放性（Scalability）也是主要性能指標(biāo)可擴(kuò)放性最簡(jiǎn)樸的含意是在確定的應(yīng)用背景下，計(jì)算機(jī)系統(tǒng)（或算法或程序等）性能隨處理器數(shù)的增加而按比例提高的能力影響加速比的因素：處理器數(shù)與問題規(guī)模求解問題中的串行分量并行處理所引起的額外開銷（通信、等待、競(jìng)爭(zhēng)、冗余操作和同步等）加大的處理器數(shù)超過了算法中的并發(fā)程度增加問題的規(guī)模有利于提高加速的因素：較大的問題規(guī)?？商峁┹^高的并發(fā)度；額外開銷的增加可能慢于有效計(jì)算的增加；算法中的串行分量比例不是固定不變的（串行部分所占的比例隨著問題規(guī)模的增大而縮?。?。增加處理器數(shù)會(huì)增大額外開銷和降低處理器利用率，所以對(duì)于一個(gè)特定的并行系統(tǒng)（算法或程序），它們能否有效利用不斷增加的處理器的能力應(yīng)是受限的，而度量這種能力就是可擴(kuò)放性這一指標(biāo)。第67頁/共617頁國家高性能計(jì)算中心（合肥）682023/4/4可擴(kuò)放性評(píng)測(cè)標(biāo)準(zhǔn)（cont‘d)可擴(kuò)放性:調(diào)整什么和按什么比例調(diào)整并行計(jì)算要調(diào)整的是處理數(shù)p和問題規(guī)模W，兩者可按不同比例進(jìn)行調(diào)整，此比例關(guān)系（可能是線性的，多項(xiàng)式的或指數(shù)的等）就反映了可擴(kuò)放的程度。并行算法和體系結(jié)構(gòu)可擴(kuò)放性研究的主要目的：確定解決某類問題用何種并行算法與何種并行體系結(jié)構(gòu)的組合，可以有效地利用大量的處理器；對(duì)于運(yùn)行于某種體系結(jié)構(gòu)的并行機(jī)上的某種算法當(dāng)移植到大規(guī)模處理機(jī)上后運(yùn)行的性能；對(duì)固定的問題規(guī)模，確定在某類并行機(jī)上最優(yōu)的處理器數(shù)與可獲得的最大的加速比；用于指導(dǎo)改進(jìn)并行算法和并行機(jī)體系結(jié)構(gòu)，以使并行算法盡可能地充分利用可擴(kuò)充的大量處理器目前無一個(gè)公認(rèn)的、標(biāo)準(zhǔn)的和被普遍接受的嚴(yán)格定義和評(píng)判它的標(biāo)準(zhǔn)第68頁/共617頁國家高性能計(jì)算中心（合肥）692023/4/4等效率度量標(biāo)準(zhǔn)令tie

和tio

分別是并行系統(tǒng)上第i個(gè)處理器的有用計(jì)算時(shí)間和額外開銷時(shí)間（包括通信、同步和空閑等待時(shí)間等）Tp

是p個(gè)處理器系統(tǒng)上并行算法的運(yùn)行時(shí)間，對(duì)于任意i顯然有Tp=tie+tio，且Te+To=pTp問題的規(guī)模W為最佳串行算法所完成的計(jì)算量W=Te

如果問題規(guī)模W保持不變，處理器數(shù)p增加，開銷To增大，效率E下降。為了維持一定的效率（介于0與1之間），當(dāng)處理數(shù)p增大時(shí)，需要相應(yīng)地增大問題規(guī)模W的值。由此定義函數(shù)fE（p）為問題規(guī)模W隨處理器數(shù)p變化的函數(shù)，為等效率函數(shù)（ISO-efficiencyFunction）（Kumar1987）第69頁/共617頁國家高性能計(jì)算中心（合肥）702023/4/4等效率度量標(biāo)準(zhǔn)（cont‘d)曲線1表示算法具有很好的擴(kuò)放性；曲線2表示算法是可擴(kuò)放的；曲線3表示算法是不可擴(kuò)放的。優(yōu)點(diǎn)：簡(jiǎn)單可定量計(jì)算的、少量的參數(shù)計(jì)算等效率函數(shù)缺點(diǎn)：如果To無法計(jì)算出（在共享存儲(chǔ)并行機(jī)中）第70頁/共617頁國家高性能計(jì)算中心（合肥）712023/4/4等速度度量標(biāo)準(zhǔn)p表示處理器個(gè)數(shù)，W表示要求解問題的工作量或稱問題規(guī)模（在此可指浮點(diǎn)操作個(gè)數(shù)），T為并行執(zhí)行時(shí)間，定義并行計(jì)算的速度V為工作量W除以并行時(shí)間Tp個(gè)處理器的并行系統(tǒng)的平均速度定義為并行速度V除以處理器個(gè)數(shù)p：W是使用p個(gè)處理器時(shí)算法的工作量，令W’表示當(dāng)處理數(shù)從p增大到p’時(shí)，為了保持整個(gè)系統(tǒng)的平均速度不變所需執(zhí)行的工作量，則可得到處理器數(shù)從p到p’時(shí)平均速度可擴(kuò)放度量標(biāo)準(zhǔn)公式第71頁/共617頁國家高性能計(jì)算中心（合肥）722023/4/4等速度度量標(biāo)準(zhǔn)（cont’d）優(yōu)點(diǎn)：直觀地使用易測(cè)量的機(jī)器性能速度指標(biāo)來度量缺點(diǎn)：某些非浮點(diǎn)運(yùn)算可能造成性能的變化第72頁/共617頁國家高性能計(jì)算中心（合肥）732023/4/4平均延遲度量標(biāo)準(zhǔn)Ti為Pi的執(zhí)行時(shí)間，包括包括延遲Li，Pi的總延遲時(shí)間為“Li+啟動(dòng)時(shí)間+停止時(shí)間”。定義系統(tǒng)平均延遲時(shí)間為pTpara=To+Ts

在p個(gè)處理器上求解工作量為W問題的平均延遲在p’個(gè)處理器上求解工作量為W’問題的平均延遲當(dāng)處理器數(shù)由p變到p’，而推持并行執(zhí)行效率不變，則定義平均延遲可擴(kuò)放性度量標(biāo)準(zhǔn)為第73頁/共617頁國家高性能計(jì)算中心（合肥）742023/4/4平均延遲度量標(biāo)準(zhǔn)（Cont’d)優(yōu)點(diǎn)：平均延遲能在更低層次上衡量機(jī)器的性能缺點(diǎn)：需要特定的軟硬件才能獲得平均延遲第74頁/共617頁并行計(jì)算

中國科學(xué)技術(shù)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系國家高性能計(jì)算中心(合肥)2003年9月第75頁/共617頁第二篇并行算法的設(shè)計(jì)

第四章并行算法的設(shè)計(jì)基礎(chǔ)

第五章并行算法的一般設(shè)計(jì)方法

第六章并行算法的基本設(shè)計(jì)技術(shù)

第七章并行算法的一般設(shè)計(jì)過程

第76頁/共617頁第四章并行算法的設(shè)計(jì)基礎(chǔ)

4.1并行算法的基礎(chǔ)知識(shí)

4.2并行計(jì)算模型

第77頁/共617頁4.1并行算法的基礎(chǔ)知識(shí)

4.1.1

并行算法的定義和分類

4.1.2

并行算法的表達(dá)

4.1.3

并行算法的復(fù)雜性度量

4.1.4

并行算法中的同步和通訊第78頁/共617頁國家高性能計(jì)算中心（合肥）792023/4/4并行算法的定義和分類并行算法的定義算法并行算法：一些可同時(shí)執(zhí)行的諸進(jìn)程的集合，這些進(jìn)程互相作用和協(xié)調(diào)動(dòng)作從而達(dá)到給定問題的求解。并行算法的分類數(shù)值計(jì)算和非數(shù)值計(jì)算同步算法和異步算法分布算法確定算法和隨機(jī)算法第79頁/共617頁4.1并行算法的基礎(chǔ)知識(shí)

4.1.1

并行算法的定義和分類

4.1.2

并行算法的表達(dá)

4.1.3

并行算法的復(fù)雜性度量

4.1.4

并行算法中的同步和通訊第80頁/共617頁國家高性能計(jì)算中心（合肥）812023/4/4并行算法的表達(dá)描述語言可以使用類Algol、類Pascal等；在描述語言中引入并行語句。并行語句示例Par-do語句

fori=1tonpar-do

……endforforall語句

forallPi,where0≤i≤k

……endfor第81頁/共617頁4.1并行算法的基礎(chǔ)知識(shí)

4.1.1

并行算法的定義和分類

4.1.2

并行算法的表達(dá)

4.1.3

并行算法的復(fù)雜性度量

4.1.4

并行算法中的同步和通訊第82頁/共617頁國家高性能計(jì)算中心（合肥）832023/4/4并行算法的復(fù)雜性度量串行算法的復(fù)雜性度量最壞情況下的復(fù)雜度(Worst-CASEComplexity)期望復(fù)雜度(ExpectedComplexity)并行算法的幾個(gè)復(fù)雜性度量指標(biāo)運(yùn)行時(shí)間t(n):包含計(jì)算時(shí)間和通訊時(shí)間，分別用計(jì)算時(shí)間步和選路時(shí)間步作單位。n為問題實(shí)例的輸入規(guī)模。處理器數(shù)p(n)并行算法成本c(n):c(n)=t(n)p(n)總運(yùn)算量W(n):并行算法求解問題時(shí)所完成的總的操作步數(shù)。

第83頁/共617頁國家高性能計(jì)算中心（合肥）842023/4/4并行算法的復(fù)雜性度量Brent定理令W(n)是某并行算法A在運(yùn)行時(shí)間T(n)內(nèi)所執(zhí)行的運(yùn)算量，則A使用p臺(tái)處理器可在t(n)=O(W(n)/p+T(n))時(shí)間內(nèi)執(zhí)行完畢。W(n)和c(n)密切相關(guān)P=O(W(n)/T(n))時(shí)，W(n)和c(n)兩者是漸進(jìn)一致的對(duì)于任意的p，c(n)?W(n)第84頁/共617頁4.1并行算法的基礎(chǔ)知識(shí)

4.1.1

并行算法的定義和分類

4.1.2

并行算法的表達(dá)

4.1.3

并行算法的復(fù)雜性度量

4.1.4

并行算法中的同步和通訊第85頁/共617頁國家高性能計(jì)算中心（合肥）862023/4/4并行算法的同步同步概念同步是在時(shí)間上強(qiáng)使各執(zhí)行進(jìn)程在某一點(diǎn)必須互相等待；可用軟件、硬件和固件的辦法來實(shí)現(xiàn)。同步語句示例算法4.1共享存儲(chǔ)多處理器上求和算法輸入：A=(a0,…,an-1),處理器數(shù)p

輸出：S=ΣaiBegin(1)S=0(2.3)lock(S)(2)forallPiwhere0≤i≤p-1

doS=S+L(2.1)L=0(2.4)unlock(S)(2.2)forj=itonsteppdoendforL=L+ajEndendforendfor第86頁/共617頁國家高性能計(jì)算中心（合肥）872023/4/4并行算法的通訊通訊共享存儲(chǔ)多處理器使用：globalread(X,Y)和globalwrite(X,Y)分布存儲(chǔ)多計(jì)算機(jī)使用：send(X,i)和receive(Y,j)通訊語句示例算法4.2分布存儲(chǔ)多計(jì)算機(jī)上矩陣向量乘算法輸入：處理器數(shù)p,A劃分為B=A[1..n,(i-1)r+1..ir],x劃分為w=w[(i-1)r+1;ir]

輸出：P1保存乘積AXBegin(1)Computez=Bw(2)ifi=1thenyi=0elsereceive(y,left)endif(3)y=y+z(4)send(y,right)(5)ifi=1thenreceive(y,left)End第87頁/共617頁第四章并行算法的設(shè)計(jì)基礎(chǔ)

4.1并行算法的基礎(chǔ)知識(shí)

4.2并行計(jì)算模型

第88頁/共617頁4.2并行計(jì)算模型

4.2.1

PRAM模型

4.2.2

異步APRAM模型

4.2.3BSP模型

4.2.4logP模型第89頁/共617頁國家高性能計(jì)算中心（合肥）902023/4/4

PRAM模型基本概念由Fortune和Wyllie1978年提出，又稱SIMD-SM模型。有一個(gè)集中的共享存儲(chǔ)器和一個(gè)指令控制器，通過SM的R/W交換數(shù)據(jù)，隱式同步計(jì)算。結(jié)構(gòu)圖ControlUnitInterconnectionNetworkPLMPLMPLMPLMSharedMemory第90頁/共617頁國家高性能計(jì)算中心（合肥）912023/4/4

PRAM模型分類PRAM-CRCW并發(fā)讀并發(fā)寫CPRAM-CRCW(CommonPRAM-CRCW)：僅允許寫入相同數(shù)據(jù)PPRAM-CRCW(PriorityPRAM-CRCW)：僅允許優(yōu)先級(jí)最高的處理器寫入APRAM-CRCW(ArbitraryPRAM-CRCW)：允許任意處理器自由寫入PRAM-CREW并發(fā)讀互斥寫PRAM-EREW互斥讀互斥寫計(jì)算能力比較PRAM-CRCW是最強(qiáng)的計(jì)算模型，PRAM-EREW可logp倍模擬PRAM-CREW和PRAM-CRCW第91頁/共617頁國家高性能計(jì)算中心（合肥）922023/4/4

PRAM模型優(yōu)點(diǎn)適合并行算法表示和復(fù)雜性分析，易于使用，隱藏了并行機(jī)的通訊、同步等細(xì)節(jié)。缺點(diǎn)不適合MIMD并行機(jī)，忽略了SM的競(jìng)爭(zhēng)、通訊延遲等因素第92頁/共617頁4.2并行計(jì)算模型

4.2.1PRAM模型

4.2.2

異步APRAM模型

4.2.3BSP模型

4.2.4logP模型第93頁/共617頁國家高性能計(jì)算中心（合肥）942023/4/4異步APRAM模型基本概念又稱分相（Phase）PRAM或MIMD-SM。每個(gè)處理器有其局部存儲(chǔ)器、局部時(shí)鐘、局部程序；無全局時(shí)鐘，各處理器異步執(zhí)行；處理器通過SM進(jìn)行通訊；處理器間依賴關(guān)系，需在并行程序中顯式地加入同步路障。指令類型(1)全局讀(2)全局寫(3)局部操作(4)同步第94頁/共617頁國家高性能計(jì)算中心（合肥）952023/4/4異步APRAM模型計(jì)算過程由同步障分開的全局相組成

第95頁/共617頁國家高性能計(jì)算中心（合肥）962023/4/4異步APRAM模型計(jì)算時(shí)間

設(shè)局部操作為單位時(shí)間；全局讀/寫平均時(shí)間為d，d隨著處理器數(shù)目的增加而增加；同步路障時(shí)間為B=B(p)非降函數(shù)。滿足關(guān)系；或令為全局相內(nèi)各處理器執(zhí)行時(shí)間最長者，則APRAM上的計(jì)算時(shí)間為優(yōu)缺點(diǎn)

易編程和分析算法的復(fù)雜度，但與現(xiàn)實(shí)相差較遠(yuǎn)，其上并行算法非常有限，也不適合MIMD-DM模型。

第96頁/共617頁4.2并行計(jì)算模型

4.2.1PRAM模型

4.2.2

異步APRAM模型

4.2.3

BSP模型

4.2.4logP模型第97頁/共617頁國家高性能計(jì)算中心（合肥）982023/4/4

BSP模型基本概念由Valiant(1990)提出的，“塊”同步模型，是一種異步MIMD-DM模型，支持消息傳遞系統(tǒng)，塊內(nèi)異步并行，塊間顯式同步。

模型參數(shù)p：處理器數(shù)(帶有存儲(chǔ)器)l：同步障時(shí)間(Barriersynchronizationtime)g：帶寬因子(timesteps/packet)=1/bandwidth第98頁/共617頁國家高性能計(jì)算中心（合肥）992023/4/4

BSP模型計(jì)算過程由若干超級(jí)步組成，每個(gè)超級(jí)步計(jì)算模式為左圖優(yōu)缺點(diǎn)強(qiáng)調(diào)了計(jì)算和通訊的分離，提供了一個(gè)編程環(huán)境，易于程序復(fù)雜性分析。但需要顯式同步機(jī)制，限制至多h條消息的傳遞等。第99頁/共617頁4.2并行計(jì)算模型

4.2.1PRAM模型

4.2.2

異步APRAM模型

4.2.3BSP模型

4.2.4

logP模型第100頁/共617頁國家高性能計(jì)算中心（合肥）1012023/4/4

logP模型基本概念由Culler(1993)年提出的，是一種分布存儲(chǔ)的、點(diǎn)到點(diǎn)通訊的多處理機(jī)模型，其中通訊由一組參數(shù)描述，實(shí)行隱式同步。模型參數(shù)L：networklatencyo：communicationoverheadg：gap=1/bandwidthP：#processors注：L和g反映了通訊網(wǎng)絡(luò)的容量

第101頁/共617頁國家高性能計(jì)算中心（合肥）1022023/4/4

logP模型優(yōu)缺點(diǎn)

捕捉了MPC的通訊瓶頸，隱藏了并行機(jī)的網(wǎng)絡(luò)拓?fù)?、路由、協(xié)議，可以應(yīng)用到共享存儲(chǔ)、消息傳遞、數(shù)據(jù)并行的編程模型中；但難以進(jìn)行算法描述、設(shè)計(jì)和分析。BSPvs.LogPBSPLogP：BSP塊同步BSP子集同步BSP進(jìn)程對(duì)同步＝LogPBSP可以常數(shù)因子模擬LogP，LogP可以對(duì)數(shù)因子模擬BSPBSP＝LogP+Barriers－OverheadBSP提供了更方便的程設(shè)環(huán)境，LogP更好地利用了機(jī)器資源BSP似乎更簡(jiǎn)單、方便和符合結(jié)構(gòu)化編程

第102頁/共617頁并行計(jì)算

中國科學(xué)技術(shù)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系國家高性能計(jì)算中心(合肥)2003年9月第103頁/共617頁第二篇并行算法的設(shè)計(jì)

第四章并行算法的設(shè)計(jì)基礎(chǔ)

第五章并行算法的一般設(shè)計(jì)方法

第六章并行算法的基本設(shè)計(jì)技術(shù)

第七章并行算法的一般設(shè)計(jì)過程

第104頁/共617頁第五章并行算法的一般設(shè)計(jì)方法

5.1串行算法的直接并行化

5.2從問題描述開始設(shè)計(jì)并行算法

5.3借用已有算法求解新問題

第105頁/共617頁5.1串行算法的直接并行化

5.1.1

設(shè)計(jì)方法描述

5.1.2

快排序算法的并行化

第106頁/共617頁國家高性能計(jì)算中心（合肥）1072023/4/4設(shè)計(jì)方法的描述方法描述發(fā)掘和利用現(xiàn)有串行算法中的并行性，直接將串行算法改造為并行算法。評(píng)注由串行算法直接并行化的方法是并行算法設(shè)計(jì)的最常用方法之一；不是所有的串行算法都可以直接并行化的；一個(gè)好的串行算法并不能并行化為一個(gè)好的并行算法；許多數(shù)值串行算法可以并行化為有效的數(shù)值并行算法。第107頁/共617頁5.1串行算法的直接并行化

5.1.1

設(shè)計(jì)方法描述

5.1.2

快排序算法的并行化

第108頁/共617頁國家高性能計(jì)算中心（合肥）1092023/4/4快排序算法的并行化算法5.2PRAM-CRCW上的快排序二叉樹構(gòu)造算法輸入：序列(A1,…,An)和n個(gè)處理器輸出：供排序用的一棵二叉排序樹

Begin(1)foreachprocessorido(2)repeatforeachprocessori<>rootdo(1.1)root=iif(Ai<Afi)∨(Ai=Afi∧i<fi)then(1.2)fi=root(2.1)LCfi=i(1.3)LCi=RCi=n+1(2.2)ifi=LCfithenexitelsefi=LCfiendif

endforelse(2.3)RCfi=i

(2.4)ifi=RCfithenexitelsefi=RCfiendifendifendrepeatEnd第109頁/共617頁第五章并行算法的一般設(shè)計(jì)方法

5.1串行算法的直接并行化

5.2從問題描述開始設(shè)計(jì)并行算法

5.3借用已有算法求解新問題

第110頁/共617頁國家高性能計(jì)算中心（合肥）1112023/4/4從問題描述開始設(shè)計(jì)并行算法方法描述從問題本身描述出發(fā)，不考慮相應(yīng)的串行算法，設(shè)計(jì)一個(gè)全新的并行算法。評(píng)注挖掘問題的固有特性與并行的關(guān)系；設(shè)計(jì)全新的并行算法是一個(gè)挑戰(zhàn)性和創(chuàng)造性的工作；利用串的周期性的PRAM-CRCW算法是一個(gè)很好的范例；第111頁/共617頁第五章并行算法的一般設(shè)計(jì)方法

5.1串行算法的直接并行化

5.2從問題描述開始設(shè)計(jì)并行算法

5.3

借用已有算法求解新問題

第112頁/共617頁5.3借用已有算法求解新問題

5.3.1

設(shè)計(jì)方法描述

5.3.2

利用矩陣乘法求所有點(diǎn)對(duì)間最短路徑

第113頁/共617頁國家高性能計(jì)算中心（合肥）1142023/4/4設(shè)計(jì)方法的描述方法描述找出求解問題和某個(gè)已解決問題之間的聯(lián)系；改造或利用已知算法應(yīng)用到求解問題上。評(píng)注這是一項(xiàng)創(chuàng)造性的工作；使用矩陣乘法算法求解所有點(diǎn)對(duì)間最短路徑是一個(gè)很好的范例。第114頁/共617頁5.3借用已有算法求解新問題

5.3.1

設(shè)計(jì)方法描述

5.3.2

利用矩陣乘法求所有點(diǎn)對(duì)間最短路徑

第115頁/共617頁國家高性能計(jì)算中心（合肥）1162023/4/4利用矩陣乘法求所有點(diǎn)對(duì)間最短路徑計(jì)算原理有向圖G=(V,E)，邊權(quán)矩陣W=(wij)n×n，求最短路徑長度矩陣D=(dij)n×n，dij為vi到vj的最短路徑長度。假定圖中無負(fù)權(quán)有向回路，記d(k)ij為vi到vj至多有k-1個(gè)中間結(jié)點(diǎn)的最短路徑長，Dk=(d(k)ij)n×n，則(1)d(1)ij=wij

當(dāng)i<>j(如果vi到vj之間無邊存在記為∞)d(1)ij=0當(dāng)i=j

(2)無負(fù)權(quán)回路dij＝d(n-1)ij

(3)

利用最優(yōu)性原理：d(k)ij=min1≤l≤n{d(k/2)il+d(k/2)lj}

視：”+”“×”，“min”“∑”，則上式變?yōu)閐(k)ij=∑1≤l≤n{d(k/2)il×d(k/2)lj}

(4)應(yīng)用矩陣乘法：D1