并行計算中科大講義_第1頁
并行計算中科大講義_第2頁
并行計算中科大講義_第3頁
并行計算中科大講義_第4頁
并行計算中科大講義_第5頁
已閱讀5頁,還剩612頁未讀, 繼續(xù)免費閱讀

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進行舉報或認領

文檔簡介

并行計算中科大講義第1頁/共617頁國家高性能計算中心(合肥)22023/4/4并行計算——結(jié)構(gòu)?算法?編程第三篇并行數(shù)值算法第八章基本通信操作第九章稠密矩陣運算第十章線性方程組的求解第十一章快速傅里葉變換第四篇并行程序設計第十二章并行程序設計基礎第十三章并行程序設計模型和共享存儲系統(tǒng)編程第十四章分布存儲系統(tǒng)并行編程第十五章并行程序設計環(huán)境與工具第2頁/共617頁國家高性能計算中心(合肥)32023/4/4第一章并行計算機系統(tǒng)及結(jié)構(gòu)模型1.1并行計算1.1.1并行計算與計算科學1.1.2當代科學與工程問題的計算需求1.2并行計算機系統(tǒng)互連1.2.1系統(tǒng)互連1.2.2靜態(tài)互聯(lián)網(wǎng)絡1.2.3動態(tài)互連網(wǎng)絡1.2.4標準互聯(lián)網(wǎng)絡1.3并行計算機系統(tǒng)結(jié)構(gòu)1.3.1并行計算機結(jié)構(gòu)模型1.3.2并行計算機訪存模型第3頁/共617頁國家高性能計算中心(合肥)42023/4/4并行計算并行計算:并行機上所作的計算,又稱高性能計算或超級計算。計算科學:計算物理、計算化學、計算生物等科學與工程問題的需求:氣象預報、油藏模擬、核武器數(shù)值模擬、航天器設計、基因測序等。需求類型:計算密集、數(shù)據(jù)密集、網(wǎng)絡密集。美國HPCC計劃:重大挑戰(zhàn)性課題,3T性能美國Petaflops研究項目:Pflop/s。美國ASCI計劃:核武器數(shù)值模擬。第4頁/共617頁國家高性能計算中心(合肥)52023/4/4高性能計算機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頁國家高性能計算中心(合肥)62023/4/4系統(tǒng)互連不同帶寬與距離的互連技術(shù): 總線、SAN、LAN、MAN、WAN第6頁/共617頁國家高性能計算中心(合肥)72023/4/4局部總線、I/O總線、SAN和LAN第7頁/共617頁國家高性能計算中心(合肥)82023/4/4網(wǎng)絡性能指標節(jié)點度(NodeDegree):射入或射出一個節(jié)點的邊數(shù)。在單向網(wǎng)絡中,入射和出射邊之和稱為節(jié)點度。網(wǎng)絡直徑(NetworkDiameter):網(wǎng)絡中任何兩個節(jié)點之間的最長距離,即最大路徑數(shù)。對剖寬度(BisectionWidth):對分網(wǎng)絡各半所必須移去的最少邊數(shù)對剖帶寬(BisectionBandwidth):每秒鐘內(nèi),在最小的對剖平面上通過所有連線的最大信息位(或字節(jié))數(shù)如果從任一節(jié)點觀看網(wǎng)絡都一樣,則稱網(wǎng)絡為對稱的(Symmetry)第8頁/共617頁國家高性能計算中心(合肥)92023/4/4靜態(tài)互連網(wǎng)絡與動態(tài)互連網(wǎng)絡靜態(tài)互連網(wǎng)絡:處理單元間有著固定連接的一類網(wǎng)絡,在程序執(zhí)行期間,這種點到點的鏈接保持不變;典型的靜態(tài)網(wǎng)絡有一維線性陣列、二維網(wǎng)孔、樹連接、超立方網(wǎng)絡、立方環(huán)、洗牌交換網(wǎng)、蝶形網(wǎng)絡等動態(tài)網(wǎng)絡:用交換開關(guān)構(gòu)成的,可按應用程序的要求動態(tài)地改變連接組態(tài);典型的動態(tài)網(wǎng)絡包括總線、交叉開關(guān)和多級互連網(wǎng)絡等。第9頁/共617頁國家高性能計算中心(合肥)102023/4/4靜態(tài)互連網(wǎng)絡(1)一維線性陣列(1-DLinearArray):并行機中最簡單、最基本的互連方式,每個節(jié)點只與其左、右近鄰相連,也叫二近鄰連接,N個節(jié)點用N-1條邊串接之,內(nèi)節(jié)點度為2,直徑為N-1,對剖寬度為1當首、尾節(jié)點相連時可構(gòu)成循環(huán)移位器,在拓撲結(jié)構(gòu)上等同于環(huán),環(huán)可以是單向的或雙向的,其節(jié)點度恒為2,直徑或為(雙向環(huán))或為N-1(單向環(huán)),對剖寬度為2第10頁/共617頁國家高性能計算中心(合肥)112023/4/4靜態(tài)互連網(wǎng)絡(2)二維網(wǎng)孔(2-DMesh):每個節(jié)點只與其上、下、左、右的近鄰相連(邊界節(jié)點除外),節(jié)點度為4,網(wǎng)絡直徑為,對剖寬度為在垂直方向上帶環(huán)繞,水平方向呈蛇狀,就變成Illiac網(wǎng)孔了,節(jié)點度恒為4,網(wǎng)絡直徑為,而對剖寬度為垂直和水平方向均帶環(huán)繞,則變成了2-D環(huán)繞(2-DTorus),節(jié)點度恒為4,網(wǎng)絡直徑為,對剖寬度為第11頁/共617頁國家高性能計算中心(合肥)122023/4/4靜態(tài)互連網(wǎng)絡(3)二叉樹:除了根、葉節(jié)點,每個內(nèi)節(jié)點只與其父節(jié)點和兩個子節(jié)點相連。節(jié)點度為3,對剖寬度為1,而樹的直徑為如果盡量增大節(jié)點度為,則直徑縮小為2,此時就變成了星形網(wǎng)絡,其對剖寬度為傳統(tǒng)二叉樹的主要問題是根易成為通信瓶頸。胖樹節(jié)點間的通路自葉向根逐漸變寬。第12頁/共617頁國家高性能計算中心(合肥)132023/4/4靜態(tài)互連網(wǎng)絡(4)超立方:一個n-立方由個頂點組成,3-立方如圖(a)所示;4-立方如圖(b)所示,由兩個3-立方的對應頂點連接而成。n-立方的節(jié)點度為n,網(wǎng)絡直徑也是n,而對剖寬度為。如果將3-立方的每個頂點代之以一個環(huán)就構(gòu)成了如圖(d)所示的3-立方環(huán),此時每個頂點的度為3,而不像超立方那樣節(jié)點度為n。第13頁/共617頁國家高性能計算中心(合肥)142023/4/4嵌入將網(wǎng)絡中的各節(jié)點映射到另一個網(wǎng)絡中去用膨脹(Dilation)系數(shù)來描述嵌入的質(zhì)量,它是指被嵌入網(wǎng)絡中的一條鏈路在所要嵌入的網(wǎng)絡中對應所需的最大鏈路數(shù)如果該系數(shù)為1,則稱為完美嵌入。環(huán)網(wǎng)可完美嵌入到2-D環(huán)繞網(wǎng)中超立方網(wǎng)可完美嵌入到2-D環(huán)繞網(wǎng)中第14頁/共617頁國家高性能計算中心(合肥)152023/4/4嵌入第15頁/共617頁國家高性能計算中心(合肥)162023/4/4網(wǎng)絡名稱網(wǎng)絡規(guī)模節(jié)點度網(wǎng)絡直徑對剖寬度對稱鏈路數(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)絡特性比較第16頁/共617頁國家高性能計算中心(合肥)172023/4/4動態(tài)互連網(wǎng)絡(1)總線:PCI、VME、Multics、Sbus、MicroChannel多處理機總線系統(tǒng)的主要問題包括總線仲裁、中斷處理、協(xié)議轉(zhuǎn)換、快速同步、高速緩存一致性協(xié)議、分事務、總線橋和層次總線擴展等第17頁/共617頁國家高性能計算中心(合肥)182023/4/4動態(tài)互連網(wǎng)絡(2)交叉開關(guān)(Crossbar):單級交換網(wǎng)絡,可為每個端口提供更高的帶寬。象電話交換機一樣,交叉點開關(guān)可由程序控制動態(tài)設置其處于“開”或“關(guān)”狀態(tài),而能提供所有(源、目的)對之間的動態(tài)連接。交叉開關(guān)一般有兩種使用方式:一種是用于對稱的多處理機或多計算機機群中的處理器間的通信;另一種是用于SMP服務器或向量超級計算機中處理器和存儲器之間的存取。第18頁/共617頁國家高性能計算中心(合肥)192023/4/4動態(tài)互聯(lián)網(wǎng)絡(3)單級交叉開關(guān)級聯(lián)起來形成多級互連網(wǎng)絡MIN(MultistageInterconnectionNetwork)第19頁/共617頁國家高性能計算中心(合肥)202023/4/4動態(tài)互連網(wǎng)絡(4)交換開關(guān)模塊:

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

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

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

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

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

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

第37頁/共617頁國家高性能計算中心(合肥)382023/4/4并行計算機訪存模型(5)NORMA(No-RemoteMemoryAccess)模型是非遠程存儲訪問模型的簡稱。NORMA的特點是:所有存儲器是私有的;絕大數(shù)NUMA都不支持遠程存儲器的訪問;在DSM中,NORMA就消失了。

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

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

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

為計算時間,Tparo為并行開銷時間,Tcomm為相互通信時間

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

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

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

創(chuàng)建一個進程1.4ms可執(zhí)行372000flops)開銷的測量:乒--乓方法(Ping-PongScheme)節(jié)點0發(fā)送m個字節(jié)給節(jié)點1;節(jié)點1從節(jié)點0接收m個字節(jié)后,立即將消息發(fā)回節(jié)點0。總的時間除以2,即可得到點到點通信時間,也就是執(zhí)行單一發(fā)送或接收操作的時間。可一般化為熱土豆法(Hot-Potato),也稱為救火隊法(Fire-Brigade)0——1——2——

——-n-1——0

第53頁/共617頁國家高性能計算中心(合肥)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頁國家高性能計算中心(合肥)552023/4/4并行開銷的表達式:點到點通信通信開銷

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

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

t0=m1/2/

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

Ws+Wp可相應地表示為f+(1-f)

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

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

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

和tio

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

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

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

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

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

第四章并行算法的設計基礎

第五章并行算法的一般設計方法

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

第七章并行算法的一般設計過程

第76頁/共617頁第四章并行算法的設計基礎

4.1并行算法的基礎知識

4.2并行計算模型

第77頁/共617頁4.1并行算法的基礎知識

4.1.1

并行算法的定義和分類

4.1.2

并行算法的表達

4.1.3

并行算法的復雜性度量

4.1.4

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

4.1.1

并行算法的定義和分類

4.1.2

并行算法的表達

4.1.3

并行算法的復雜性度量

4.1.4

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

fori=1tonpar-do

……endforforall語句

forallPi,where0≤i≤k

……endfor第81頁/共617頁4.1并行算法的基礎知識

4.1.1

并行算法的定義和分類

4.1.2

并行算法的表達

4.1.3

并行算法的復雜性度量

4.1.4

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

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

4.1.1

并行算法的定義和分類

4.1.2

并行算法的表達

4.1.3

并行算法的復雜性度量

4.1.4

并行算法中的同步和通訊第85頁/共617頁國家高性能計算中心(合肥)862023/4/4并行算法的同步同步概念同步是在時間上強使各執(zhí)行進程在某一點必須互相等待;可用軟件、硬件和固件的辦法來實現(xiàn)。同步語句示例算法4.1共享存儲多處理器上求和算法輸入: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頁國家高性能計算中心(合肥)872023/4/4并行算法的通訊通訊共享存儲多處理器使用:globalread(X,Y)和globalwrite(X,Y)分布存儲多計算機使用:send(X,i)和receive(Y,j)通訊語句示例算法4.2分布存儲多計算機上矩陣向量乘算法輸入:處理器數(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頁第四章并行算法的設計基礎

4.1并行算法的基礎知識

4.2并行計算模型

第88頁/共617頁4.2并行計算模型

4.2.1

PRAM模型

4.2.2

異步APRAM模型

4.2.3BSP模型

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

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

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

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

4.2.1PRAM模型

4.2.2

異步APRAM模型

4.2.3BSP模型

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

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

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

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

第96頁/共617頁4.2并行計算模型

4.2.1PRAM模型

4.2.2

異步APRAM模型

4.2.3

BSP模型

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

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

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

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

4.2.1PRAM模型

4.2.2

異步APRAM模型

4.2.3BSP模型

4.2.4

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

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

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

logP模型優(yōu)缺點

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

第102頁/共617頁并行計算

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

第四章并行算法的設計基礎

第五章并行算法的一般設計方法

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

第七章并行算法的一般設計過程

第104頁/共617頁第五章并行算法的一般設計方法

5.1串行算法的直接并行化

5.2從問題描述開始設計并行算法

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

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

5.1.1

設計方法描述

5.1.2

快排序算法的并行化

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

5.1.1

設計方法描述

5.1.2

快排序算法的并行化

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

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頁第五章并行算法的一般設計方法

5.1串行算法的直接并行化

5.2從問題描述開始設計并行算法

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

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

5.1串行算法的直接并行化

5.2從問題描述開始設計并行算法

5.3

借用已有算法求解新問題

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

5.3.1

設計方法描述

5.3.2

利用矩陣乘法求所有點對間最短路徑

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

5.3.1

設計方法描述

5.3.2

利用矩陣乘法求所有點對間最短路徑

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

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

(2)無負權(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)應用矩陣乘法:D1

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負責。
  • 6. 下載文件中如有侵權(quán)或不適當內(nèi)容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

最新文檔

評論

0/150

提交評論