《并行計(jì)算概述》由會(huì)員分享，可在線閱讀，更多相關(guān)《并行計(jì)算概述（84頁珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、并行計(jì)算,,第一級(jí),,第二級(jí),,第三級(jí),,第一級(jí),,第二級(jí),,第三級(jí),,國家高性能計(jì)算中心（合肥）,*,*,并行計(jì)算,——,結(jié)構(gòu)?算法?編程,并行計(jì)算——結(jié)構(gòu),?,算法,?,編程,第一篇 并行計(jì)算的基礎(chǔ),,第一章 并行計(jì)算機(jī)系統(tǒng)及其結(jié)構(gòu)模型,,第二章 當(dāng)代并行機(jī)系統(tǒng)：,SMP、MPP,和,Cluster,,第三章 并行計(jì)算性能評(píng)測,,,第二篇 并行算法的設(shè)計(jì),,第四章 并行算法的設(shè)計(jì)基礎(chǔ),,第五章 并行算法的一般設(shè)計(jì)方法,,第六章 并行算法的基本設(shè)計(jì)技術(shù),,第七章 并行算法的一般設(shè)計(jì)過程,2024/9/28,2,,國家高性能計(jì)算中心（合肥）,并行計(jì)算——結(jié)構(gòu),?,算法,?,編程,第三篇 并行數(shù)

2、值算法,,第八章 基本通信操作,,第九章 稠密矩陣運(yùn)算,,第十章 線性方程組的求解,,第十一章 快速傅里葉變換,,,第四篇 并行程序設(shè)計(jì),,第十二章 并行程序設(shè)計(jì)基礎(chǔ),,第十三章 并行程序設(shè)計(jì)模型和共享存儲(chǔ)系統(tǒng)編程,,第十四章 分布存儲(chǔ)系統(tǒng)并行編程,,第十五章 并行程序設(shè)計(jì)環(huán)境與工具,2024/9/28,3,,國家高性能計(jì)算中心（合肥）,第一章并行計(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)

3、互聯(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ī)訪存模型,2024/9/28,4,,國家高性能計(jì)算中心（合肥）,并行計(jì)算,,并行計(jì)算：并行機(jī)上所作的計(jì)算，又稱高性能計(jì)算或超級(jí)計(jì)算。,,三大學(xué)科：計(jì)算科學(xué)，理論科學(xué)和實(shí)驗(yàn)科學(xué),,所有的學(xué)科都轉(zhuǎn)向定量化和精確化。,,計(jì)算科學(xué)是一個(gè)交叉學(xué)科，用計(jì)算的方法來解決應(yīng)用問題。,,,適用于理論模型復(fù)雜或尚未建立，實(shí)驗(yàn)費(fèi)用昂貴或無法進(jìn)行,,計(jì)算科學(xué)：計(jì)算物理、計(jì)算化學(xué)、計(jì)算生物學(xué)等,,科學(xué)與工程問題的需求：氣象預(yù)報(bào)、油藏模擬、核武器數(shù)值模擬、航天器設(shè)計(jì)、基因測序等。,,需求類型：計(jì)算密集、數(shù)據(jù)密集、網(wǎng)絡(luò)密集。,

4、2024/9/28,5,,國家高性能計(jì)算中心（合肥）,2024/9/28,6,,國家高性能計(jì)算中心（合肥）,2024/9/28,7,,國家高性能計(jì)算中心（合肥）,并行計(jì)算,,,美國,HPCC,計(jì)劃：高性能計(jì)算和通信，重大挑戰(zhàn)性課題，3,T,性能,,美國,Petaflops,研究項(xiàng)目：,Pflop/s,。,,美國,ASCI,計(jì)劃：加速戰(zhàn)略計(jì)算創(chuàng)新，核武器數(shù)值模擬。高性能,2024/9/28,8,,國家高性能計(jì)算中心（合肥）,2024/9/28,9,,國家高性能計(jì)算中心（合肥）,2024/9/28,10,,國家高性能計(jì)算中心（合肥）,2024/9/28,11,,國家高性能計(jì)算中心（合肥）,2024

5、/9/28,12,,國家高性能計(jì)算中心（合肥）,2024/9/28,13,,國家高性能計(jì)算中心（合肥）,高性能計(jì)算機(jī),,Intel（Option Red)： 1Tflops,1997,Pentium Pro,,SGI(Option Blue Mountain): 3Tflops,1998,MIPS10000,,IBM(Option White): 7Tflops,Top4,2001,Power3,,日本,Earth Simulator: 35Tflops,Top1,2002,VP,,Hewlett-Packard ASCI Q： 7Tflops ,Top2,3,200

6、2, Alpha Server,,中國聯(lián)想： 1,Tflops,Top43,2002,,,2024/9/28,14,,國家高性能計(jì)算中心（合肥）,系統(tǒng)互連,,不同帶寬與距離的互連技術(shù): 總線、,SAN、LAN、MAN、WAN,2024/9/28,15,,國家高性能計(jì)算中心（合肥）,局部總線、,I/O,總線、,SAN,和,LAN,,2024/9/28,16,,國家高性能計(jì)算中心（合肥）,網(wǎng)絡(luò)性能指標(biāo),,節(jié)點(diǎn)度（,Node Degree）：,射入或射出一個(gè)節(jié)點(diǎn)的邊數(shù)。在單向網(wǎng)絡(luò)中，入射和出射邊之和稱為節(jié)點(diǎn)度。,,網(wǎng)絡(luò)直徑（,Network Diameter）：,網(wǎng)絡(luò)中任何兩個(gè)節(jié)點(diǎn)

7、之間的最長距離，即最大路徑數(shù)。,,對(duì)剖寬度（,Bisection Width） ：,對(duì)分網(wǎng)絡(luò)各半所必須移去的最少邊數(shù),,對(duì)剖帶寬（,Bisection Bandwidth）:,每秒鐘內(nèi)，在最小的對(duì)剖平面上通過所有連線的最大信息位（或字節(jié)）數(shù),,如果從任一節(jié)點(diǎn)觀看網(wǎng)絡(luò)都一樣，則稱網(wǎng)絡(luò)為對(duì)稱的（,Symmetry）,2024/9/28,17,,國家高性能計(jì)算中心（合肥）,靜態(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ò)：用交

8、換開關(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ò)等。,,2024/9/28,18,,國家高性能計(jì)算中心（合肥）,靜態(tài)互連網(wǎng)絡(luò)（1）,,一維線性陣列（1-,D Linear Array）：,,并行機(jī)中最簡單、最基本的互連方式，,,每個(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)?,（雙向環(huán)）或?yàn)?N-1（,單向環(huán)），對(duì)剖寬度為2,2024/9/28,19,,國

9、家高性能計(jì)算中心（合肥）,靜態(tài)互連網(wǎng)絡(luò)（2）,,二維網(wǎng)孔（2-,D Mesh）：,,每個(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-,D,Torus,），,節(jié)點(diǎn)度恒為4，網(wǎng)絡(luò)直徑為 ，對(duì)剖寬度為,2024/9/28,20,,國家高性能計(jì)算中心（合肥）,靜態(tài)互連網(wǎng)絡(luò)（3）,,二叉樹：,,除了根、葉節(jié)點(diǎn)，每個(gè)內(nèi)節(jié)點(diǎn)只與其父節(jié)點(diǎn)和兩個(gè)子節(jié)

10、點(diǎn)相連。,,節(jié)點(diǎn)度為3，對(duì)剖寬度為1，而樹的直徑為,,如果盡量增大節(jié)點(diǎn)度為， 則直徑縮小為2，此時(shí)就變成了星形網(wǎng)絡(luò)，其對(duì)剖寬度為,,傳統(tǒng)二叉樹的主要問題是根易成為通信瓶頸。胖樹節(jié)點(diǎn)間的通路自葉向根逐漸變寬。,2024/9/28,21,,國家高性能計(jì)算中心（合肥）,靜態(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-立

11、方環(huán)，此時(shí)每個(gè)頂點(diǎn)的度為3，而不像超立方那樣節(jié)點(diǎn)度為,n。,2024/9/28,22,,國家高性能計(jì)算中心（合肥）,嵌入,,將網(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)中,,,2024/9/28,23,,國家高性能計(jì)算中心（合肥）,嵌入,,,2024/9/28,24,,國家高性能計(jì)算中心（合肥）,網(wǎng)絡(luò)名稱,網(wǎng)絡(luò)規(guī)模,節(jié)點(diǎn)度,網(wǎng)絡(luò)直徑,對(duì)剖寬度,對(duì)稱,鏈路數(shù)

12、,線性陣列,,2,,1,非,,環(huán)形,,2,（雙向）,2,是,,2-,D,網(wǎng)孔,,4,,,非,,Illiac,網(wǎng)孔,,4,,,非,,2-,D,環(huán)繞,,4,,,是,,二叉樹,,3,,1,非,,星形,,,2,,非,,超立方,,,n,n,,是,,立方環(huán),,3,,,是,,靜態(tài)互連網(wǎng)絡(luò)特性比較,,2024/9/28,25,,國家高性能計(jì)算中心（合肥）,動(dòng)態(tài)互連網(wǎng)絡(luò) (1),,總線：,PCI、VME、Multics、Sbus、MicroChannel,,,多處理機(jī)總線系統(tǒng)的主要問題包括總線仲裁、中斷處理、協(xié)議轉(zhuǎn)換、快速同步、高速緩存一致性協(xié)議、分事務(wù)、總線橋和層次總線擴(kuò)展等,2024/9/28,26,,國家

13、高性能計(jì)算中心（合肥）,動(dòng)態(tài)互連網(wǎng)絡(luò) （2）,,交叉開關(guān)（,Crossbar）：,,單級(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ǔ)器之間的存取。,2024/9/28,27,,國家高性能計(jì)算中心（合肥）,動(dòng)態(tài)互聯(lián)網(wǎng)絡(luò) （3）,,單級(jí)交叉開關(guān)級(jí)聯(lián)起來形成多級(jí)互連網(wǎng)絡(luò),MIN（Multistage Interconnection Network

14、）,,,2024/9/28,28,,國家高性能計(jì)算中心（合肥）,動(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í)間互連（,Interstage,Connection ）：,,均勻洗牌、蝶網(wǎng)、多路均勻洗牌、交叉開關(guān)、立方連接,,n,輸入的,Ω,網(wǎng)絡(luò)需要 級(jí) 開關(guān)，在,Ilinois,大學(xué)的,Cedar[2],多處理機(jī)系統(tǒng)中采用了,Ω,網(wǎng)絡(luò),,Cray Y/MP,多級(jí)網(wǎng)絡(luò)，該網(wǎng)絡(luò)用來支持8個(gè)向量處理器和256個(gè)存儲(chǔ)器模塊之間的

15、數(shù)據(jù)傳輸。網(wǎng)絡(luò)能夠避免8個(gè)處理器同時(shí)進(jìn)行存儲(chǔ)器存取時(shí)的沖突。,2024/9/28,29,,國家高性能計(jì)算中心（合肥）,動(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.67,GB/s,IBM SP2,中的512節(jié)點(diǎn)的,HPS：10.24GB/s,Digital,的千兆開關(guān)：3.4,GB/s,2024/9/28,30,,國家高性能計(jì)算中心（合肥）,標(biāo)準(zhǔn)互聯(lián)網(wǎng)絡(luò)（1）,,Myrinet,:,

16、,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),,M

17、yrinet,交換開關(guān) :8,12,16端口,,Myrinet,主機(jī)接口 : 32位的稱作,LANai,芯片的用戶定制的,VLSI,處理器，它帶有,Myrinet,接口、包接口、,DMA,引擎和快速靜態(tài)隨機(jī)存取存儲(chǔ)器,SRAM。,,140,of the November 2002 TOP500 use,Myrinet,, including 15 of the top 100,,2024/9/28,31,,國家高性能計(jì)算中心（合肥）,Myrinet,連接的,LAN/Cluster,,,2024/9/28,32,,國家高性能計(jì)算中心（合肥）,標(biāo)準(zhǔn)互連網(wǎng)絡(luò)（2,),,高性能并行接口（,HiPPI,

18、）,,Los Alamos,國家實(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年，,ANSI X3T9.3,委員會(huì)認(rèn)可了,HiPPI,標(biāo)準(zhǔn)，它覆蓋了物理和數(shù)據(jù)鏈路層，但在這兩層之上的任何規(guī)定卻取決于用戶。,,HiPPI,是個(gè)單工的點(diǎn)到點(diǎn)的數(shù)據(jù)傳輸接口，其速率可達(dá)800,Mbps,到1.6,Gbps,。,,開發(fā)成功了一種能提供潛在的6.4,Gbps,速率，比,HiPPI,快8倍且有很低時(shí)延的超級(jí),HiPPI,技術(shù)，,,SGI,公司

19、和,Los Alamos,國家實(shí)驗(yàn)室都開發(fā)了用來構(gòu)筑速率高達(dá)25.6,Gbps,的,HiPPI,交換開關(guān)的,HiPPI,技術(shù)。,,HiPPI,通道和,HiPPI,交換開關(guān)被用在,SGI Power Challenge,服務(wù)器、,IBM 390,主機(jī)、,Cray Y/MP、C90,和,T3D/T3E,等系統(tǒng),,2024/9/28,33,,國家高性能計(jì)算中心（合肥）,使用,HiPPI,通道和開關(guān)構(gòu)筑的,LAN,主干網(wǎng),,2024/9/28,34,,國家高性能計(jì)算中心（合肥）,標(biāo)準(zhǔn)互連網(wǎng)絡(luò)（3）,,光纖通道,FC（Fiber Channel） :,,通道和網(wǎng)絡(luò)標(biāo)準(zhǔn)的集成,,光纖通道既可以是共享介質(zhì)，

20、也可以是一種交換技術(shù),,光纖通道操作速度范圍可從100到133、200、400和800,Mbps。FCSI,廠商也正在推出未來具有更高速度（1、2或4,Gbps,）,的光纖通道,,光纖通道的價(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（Fiber Distributed Data Interface）,,FDDI,采用雙向光纖令牌環(huán)可提供100-200,Mbps,數(shù)據(jù)傳輸速率,,FDDI,具有互連大量設(shè)備的能力,,傳統(tǒng)的,FDDI,僅以異步方

21、式操作,2024/9/28,35,,國家高性能計(jì)算中心（合肥）,雙向,FDDI,環(huán)作為主干網(wǎng),,2024/9/28,36,,國家高性能計(jì)算中心（合肥）,標(biāo)準(zhǔn)互聯(lián)網(wǎng)絡(luò)（4）,,ATM（Asynchronous Transfer Mode）:,,由成立于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和622,Mbps,不同的速率，其速率越低,ATM,交換器和使用的鏈路

22、價(jià)格越低。,,2024/9/28,37,,國家高性能計(jì)算中心（合肥）,香港大學(xué)開發(fā)的,Pearl,機(jī)群,,2024/9/28,38,,國家高性能計(jì)算中心（合肥）,標(biāo)準(zhǔn)互連網(wǎng)絡(luò)（5）,,代別,,類型,,以太網(wǎng),,10,BaseT,快速以太網(wǎng),,100,BaseT,千兆位以太網(wǎng),,1,GB,引入年代,,1982,1994,1997,速度（帶寬）,,10,Mb/s,100,Mb/s,1,Gb/s,最,,大,,距,,離,UTR（,非屏蔽雙扭對(duì)）,100,m,100,m,25－100,m,,STP（,屏蔽雙扭對(duì)）,,同軸電纜,500,m,100,m,25－100,m,,多模光纖,2,Km,412,m（,

23、半雙工）,,2,Km（,全雙工）,500,m,,單模光纖,25,Km,20,Km,3,Km,主要應(yīng)用領(lǐng)域,,文件共享，,,打印機(jī)共享,COW,計(jì)算，,,C/S,結(jié)構(gòu)，,,大型數(shù)據(jù)庫存取等,大型圖像文件，,,多媒體，,,因特網(wǎng)，,,內(nèi)部網(wǎng)，,,數(shù)據(jù)倉庫等,2024/9/28,39,,國家高性能計(jì)算中心（合肥）,并行計(jì)算機(jī)結(jié)構(gòu)模型,,2024/9/28,40,,國家高性能計(jì)算中心（合肥）,并行計(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)的其它部分（包括

24、板級(jí),Cache、,局存、,NIC,和,DISK）,連接起來。優(yōu)點(diǎn)是,CPU,升級(jí)只需要更換,Shell。,2024/9/28,41,,國家高性能計(jì)算中心（合肥）,五種結(jié)構(gòu)特性一覽表,,屬性,,PVP,,SMP,,MPP,,DSM,,COW,,結(jié)構(gòu)類型,,MIMD,,MIMD,,MIMD,,MIMD,,MIMD,,處理器類型,,專用定制,,商用,,商用,(,可定制,),,商用,,商用,,互連網(wǎng)絡(luò),,定制交叉開關(guān),,總線、交叉開關(guān),,定制網(wǎng)絡(luò),,定制網(wǎng)絡(luò),,商用網(wǎng)絡(luò)（以太,ATM,）,,通信機(jī)制,,共享變量,,共享變量,,消息傳遞,,共享變量,,消息傳遞,,地址空間,,單地址空間,,單地址空間,

25、,多地址空間,,單地址空間,,多地址空間,,系統(tǒng)存儲(chǔ)器,,集中共享,,集中共享,,分布非共享,,分布共享,,分布非共享,,訪存模型,,UMA,,UMA,,NORMA,,NUMA,,NORMA,,代表機(jī)器,,Cray C-90,，,,Cray T-90,，,,銀河,1,號(hào),,IBM R50,，,SGI Power Challenge,，,,曙光,1,號(hào),,Intel Paragon,，,IBMSP2,，,曙光,1000/2000,,Stanford DASH,，,Cray T 3D,,Berkeley NOW,，,Alpha Farm,,2024/9/28,42,,國家高性能計(jì)算中心（合肥）,并

26、行計(jì)算機(jī)訪存模型（1),,UMA,（,Uniform Memory Access,）,模型是均勻存儲(chǔ)訪問模型的簡稱。其特點(diǎn)是：,,物理存儲(chǔ)器被所有處理器均勻共享；,,所有處理器訪問任何存儲(chǔ)字取相同的時(shí)間；,,每臺(tái)處理器可帶私有高速緩存；,,外圍設(shè)備也可以一定形式共享。,2024/9/28,43,,國家高性能計(jì)算中心（合肥）,并行計(jì)算機(jī)訪存模型（2),,NUMA(Nonuniform,Memory Access),模型是,非均勻存儲(chǔ)訪問,模型的簡稱。特點(diǎn)是：,,被共享的存儲(chǔ)器在物理上是分布在所有的處理器中的，其所有本地存儲(chǔ)器的集合就組成了全局地址空間；,,處理器訪問存儲(chǔ)器的時(shí)間是不一樣的；訪問本

27、地存儲(chǔ)器,LM,或群內(nèi)共享存儲(chǔ)器,CSM,較快，而訪問外地的存儲(chǔ)器或全局共享存儲(chǔ)器,GSM,較慢,(,此即非均勻存儲(chǔ)訪問名稱的由來,),；,,每臺(tái)處理器照例可帶私有高速緩存，外設(shè)也可以某種形式共享。,,LM,1,P,1,LM,2,P,2,LM,n,P,n,互,連,網(wǎng),絡(luò),(,a),共享本地存儲(chǔ)模型,全局互連網(wǎng)絡(luò),(,b),層次式機(jī)群模型,GSM,GSM,GSM,…,…,…,…,P,C,I,N,CSM,P,P,CSM,CSM,群1,…,…,P,C,I,N,CSM,群,N,P,P,CSM,CSM,…,…,2024/9/28,44,,國家高性能計(jì)算中心（合肥）,并行計(jì)算機(jī)訪存模型（3),,COMA(

28、Cache-Only Memory Access),模型是,全高速緩存存儲(chǔ)訪問,的簡稱。其特點(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ì)被遷移到要用到它們的地方。,,2024/9/28,45,,國家高性能計(jì)算中心（合肥）,并行計(jì)算機(jī)訪存模型（4),,CC-NUMA,（,Coherent-Cache,Nonuniform,Memory Access,）,模型是,高速緩存一致性非均勻存儲(chǔ)

29、訪問,模型的簡稱。其特點(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ù)遷移至要用到它的地方。,,2024/9/28,46,,國家高性能計(jì)算中心（合肥）,并行計(jì)算機(jī)訪存模型（5),,NORMA（No-Remote Memory Access）,模型是,非遠(yuǎn)程存儲(chǔ)訪問,模型的簡稱。,NORMA,的特點(diǎn)是：,,所有存儲(chǔ)器

30、是私有的；,,絕大數(shù),NUMA,都不支持遠(yuǎn)程存儲(chǔ)器的訪問；,,在,DSM,中，,NORMA,就消失了。,,2024/9/28,47,,國家高性能計(jì)算中心（合肥）,構(gòu)筑并行機(jī)系統(tǒng)的不同存儲(chǔ)結(jié)構(gòu),,2024/9/28,48,,國家高性能計(jì)算中心（合肥）,第二章 當(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ī)群,SP2,,2.3.2,工作站機(jī)群,COW,2024/9/28,49,,國家高性能計(jì)算中心（合肥）,對(duì)稱

31、多處理機(jī),SMP(1),,SMP:,采用商用微處理器，通常有片上和片外,Cache，,基于總線連接，集中式共享存儲(chǔ)，,UMA,結(jié)構(gòu),,例子：,SGI Power Challenge, DEC Alpha Server,Dawning 1,2024/9/28,50,,國家高性能計(jì)算中心（合肥）,對(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），,競爭加劇,,慢速增加的帶寬（,MB d

32、ouble/3,年,,IOB,更慢）,,不可擴(kuò)放性---〉,CC-NUMA,,2024/9/28,51,,國家高性能計(jì)算中心（合肥）,大規(guī)模并行機(jī),MPP,,成百上千個(gè)處理器組成的大規(guī)模計(jì)算機(jī)系統(tǒng)，規(guī)模是變化的。,,NORMA,結(jié)構(gòu)，高帶寬低延遲定制互連。,,可擴(kuò)放性：,Mem,, I/O,,平衡設(shè)計(jì),,系統(tǒng)成本：商用處理器，相對(duì)穩(wěn)定的結(jié)構(gòu),(shell),，,SMP,節(jié)點(diǎn),,,分布,,通用性和可用性：不同的應(yīng)用，,PVM,MPI,,交互，批處理，互連對(duì)用戶透明，單一系統(tǒng)映象，故障,,通信要求,,存儲(chǔ)器和,I/O,能力,,例子：,Intel Option Red,,,IBM SP2 Dawn

33、ing 1000,2024/9/28,52,,國家高性能計(jì)算中心（合肥）,典型,MPP,系統(tǒng)特性比較,,MPP,模型,,Intel/,Sandia,ASCI Option Red,,IBM SP2,,SGI/Cray Origin2000,,一個(gè)大型樣機(jī)的配置,,9072,個(gè)處理器，,1.8,Tflop/s(NSL,),,400,個(gè)處理器，,100,Gflop/s(MHPCC,),,128,個(gè)處理器，,51,Gflop/s(NCSA,),,問世日期,,1996,年,12,月,,1994,年,9,月,,1996,年,10,月,,處理器類型,,200,MHz, 200Mflop/s Pentium

34、 Pro,,67,MHz,，,267Mflop/s POWER2,,200,MHz,，,400Mflop/s MIPS R10000,,節(jié)點(diǎn)體系結(jié)構(gòu),,和數(shù)據(jù)存儲(chǔ)器,,2,個(gè)處理器，,32,到,256,MB,主存，共享磁盤,,1,個(gè)處理器，,64,MB,到,2,GB,本地主存，,1,GB,到,14.5,GB,本地磁盤,,2,個(gè)處理器，,64,MB,到,256,MB,分布共享主存和共享磁盤,,互連網(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,（,IBM UNIX,）,,微內(nèi)核

35、,Cellular IRIX,,自然編程機(jī)制,,基于,PUMA Portals,的,MPI,,MPI,和,PVM,,Power C,，,Power Fortran,,其他編程模型,,Nx,，,PVM,，,HPF,,HPF,，,Linda,,MPI,，,PVM,,2024/9/28,53,,國家高性能計(jì)算中心（合肥）,MPP,所用的高性能,CPU,特性比較,,屬性,,Pentium Pro,,PowerPC 602,,Alpha 21164A,,Ultra SPARC II,,MIPS R10000,,工藝,,BiCMOS,,CMOS,,CMOS,,CMOS,,CMOS,,晶體管數(shù),,5.5,M

36、/15.5M,,7,M,,9.6,M,,5.4,M,,6.8,M,,時(shí)鐘頻率,,150,MHz,,133,MHz,,417,MHz,,200,MHz,,200,MHz,,電壓,,2.9,V,,3.3,V,,2.2,V,,2.5,V,,3.3,V,,功率,,20,W,,30,W,,20,W,,28,W,,30,W,,字長,,32,位,,64,位,,64,位,,64,位,,64,位,,I/O,,高速緩存,,8,KB/8KB,,32,KB/32KB,,8,KB/8KB,,16,KB/16KB,,32,KB/32KB,,2,級(jí),,高速緩存,,256,KB,,(,多芯片模塊,),,1~128,MB,,(

37、,片外,),,96,KB,,(,片上,),,16,MB,,(,片外,),,16,MB,,(,片外,),,執(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í),,SPECint,92,,366,,225,,>500,,350,,300,,SPECfp,92,,283,,300,,>750,,550,,600,,SPECint,95,,8.09,,225,,>11,,N/A,,7.4,,SPECfp,95,,6.70,,3

38、00,,>17,,N/A,,15,,其它特性,,CISC/RISC,混合,,短流水線長,L1,高速緩存,,最高時(shí)鐘頻率最大片上,2,級(jí)高速緩存,,多媒體和圖形指令,,MP,機(jī)群總線可支持,4,個(gè),CPU,,2024/9/28,54,,國家高性能計(jì)算中心（合肥）,機(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,2024/9/28,55,,國家高性能計(jì)算中心（合肥）,工作站機(jī)群,COW,,分布式存儲(chǔ)，,MIMD，,工作站+商用互連網(wǎng)絡(luò)，每個(gè)節(jié)點(diǎn)是

39、一個(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)境,,,例子：,Berkeley NOW，Alpha Farm, FXCOW,,,,P/C,M,MIO,MIO,M,P/C,NIC,NIC,D,D,LAN,2024/9/28,56,,國家高性能計(jì)算中心（合肥）,典型的機(jī)群系統(tǒng),,典型的機(jī)群系統(tǒng)特點(diǎn)一覽表,,名稱,,系統(tǒng)特點(diǎn),,Princeton:SHRIMP,,PC,商用組件，通過專用網(wǎng)絡(luò)接口達(dá)到共享虛擬存儲(chǔ)，支持有效通信,,Karsruhe:P

40、arastation,,用于分布并行處理的有效通信網(wǎng)絡(luò)和軟件開發(fā),,Rice:TreadMarks,,軟件實(shí)現(xiàn)分布共享存儲(chǔ)的工作站機(jī)群,,Wisconsin:Wind Tunnel,,在經(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:Pearl Clus

41、ter,,研究機(jī)群在分布式多媒體和金融數(shù)字庫方面的應(yīng)用,,Virgina:Legion,,在國家虛擬計(jì)算機(jī)設(shè)施上開發(fā)元計(jì)算軟件,,2024/9/28,57,,國家高性能計(jì)算中心（合肥）,SMP\MPP\,機(jī)群比較,,系統(tǒng)特征,,SMP,,MPP,,機(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),,1,,N(,微內(nèi)核,),,和,1,個(gè)主機(jī),OS(,單一,),,N (,希望為同構(gòu)

42、,),,支持單一系統(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),,定制,,商用,,2024/9/28,58,,國家高性能計(jì)算中心（合肥）,第三章 并行計(jì)算性能評(píng)測,,3.1 并行機(jī)的一些基本性能指標(biāo),,3.2 加速比性能定律,,3.2.1,Amdahl,定律,,3.2.2,Gustafson,定律,,3.2.3,Sun

43、,和,Ni,定律,,3.3 可擴(kuò)放性評(píng)測標(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),2024/9/28,59,,國家高性能計(jì)算中心（合肥）,CPU,的某些基本性能指標(biāo),,工作負(fù)載,,執(zhí)行時(shí)間,,浮點(diǎn)運(yùn)算數(shù),,指令數(shù)目,,,并行執(zhí)行時(shí)間,T,,comput,,為計(jì)算時(shí)間，,T,paro,,為并行開銷時(shí)間，,T,comm,為相互通信時(shí)間,,,T,n,= T,,comput,+ T,,paro,+ T,,comm,,,,例：估計(jì),APRAM,模型下執(zhí)行時(shí)間,,,2024/9/28,60,,國家高性能計(jì)算中心（合肥

44、）,存儲(chǔ)器性能,,存儲(chǔ)器的層次結(jié)構(gòu),(,C,L,B),,各層性能參數(shù),：,容量,C,、,延遲,L,、,帶寬,B,。,,,相關(guān)參數(shù)：,存儲(chǔ)粒度、一致性粒度、層管理方案等。,2024/9/28,61,,國家高性能計(jì)算中心（合肥）,影響存儲(chǔ)器容量,C,設(shè)計(jì)因素,：,,,與主流應(yīng)用的進(jìn)程數(shù)及各進(jìn)程工作集尺寸等有關(guān)。,影響存儲(chǔ)器延遲,L,設(shè)計(jì)因素,：,,與,CPU,指令系統(tǒng),CPI,及指令所需數(shù)據(jù)量等有關(guān)。,影響存儲(chǔ)器帶寬,B,設(shè)計(jì)因素,：,,與應(yīng)用的數(shù)據(jù)通信量、通信頻率和延遲,L,等有關(guān)。,2024/9/28,62,,國家高性能計(jì)算中心（合肥）,并行與通信開銷,,并行和通信開銷：相對(duì)于計(jì)算很大。,,,

45、PowerPC (,每個(gè)周期,15,ns,執(zhí)行,4,flops;,,,創(chuàng)建一個(gè)進(jìn)程,1.4,ms,可執(zhí)行,372000,flops),,開銷的測量：乒,--,乓方法（,Ping-Pong Scheme）,節(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í)間。,,可一般化為熱土豆法（,Hot-Potato），,也稱為救火隊(duì)法（,Fire-Brigade) 0——1 —— 2 —— … —— -n-1 —— 0,,,2024/9/28,63,,國家高性能計(jì)算

46、中心（合肥）,Ping-Pong Scheme,,if （my _node _id =0） then /*,發(fā)送者*,/,,,start _time =second（ ）,,send an m-byte message to node 1,,receive an m-byte message from node 1,,end_time = second（ ）,,total_time = end_time – start_time,,communication_time[i] = total_time/2,,else if （my_node_id = 1） then /*,接收者*,/,,

47、,receive an m-byte message from node 0,,send an m-byte message to node 0,,,endif,,2024/9/28,64,,國家高性能計(jì)算中心（合肥）,并行開銷的表達(dá)式：點(diǎn)到點(diǎn)通信,,通信開銷,,t,(,m,) =,t,0,+,m,/,r,∞,,通信啟動(dòng)時(shí)間,t,0,,漸近,帶寬,r,∞,,：,傳送無限長的消息時(shí)的通信速率,,,半,峰值長度,m,1/2,：達(dá)到一半漸近帶寬所要的消息長度,,特定性能,π,0,：表示短消息帶寬,,,t,0,= m,1/2,/,,r,∞,= 1 /,π,0,2024/9/28,65,,國家高性能計(jì)

48、算中心（合肥）,并行開銷的表達(dá)式：整體通信,,典型的整體通信有：,,,播送（,Broadcasting）：,處理器,0,發(fā)送,m,個(gè)字節(jié)給所有的,n,個(gè)處理器,,收集（,Gather）：,處理,0,接收所有,n,個(gè)處理器發(fā)來在消息，所以處理器,0,最終接收了,m n,個(gè)字節(jié)；,,散射（,Scatter）：,處理器,0,發(fā)送了,m,個(gè)字節(jié)的不同消息給所有,n,個(gè)處理器，因此處理器,0,最終發(fā)送了,m n,個(gè)字節(jié)；,,全交換（,Total Exchange）：,每個(gè)處理器均彼此相互發(fā)送,m,個(gè)字節(jié)的不同消息給對(duì)方，所以總通信量為,mn,2,個(gè)字節(jié)；,,循環(huán)移位（,Circular-shift）：,

49、處理器,i,發(fā)送,m,個(gè)字節(jié)給處理器,i+1，,處理器,n-1,發(fā)送,m,個(gè)字節(jié)給處理器,0,，所以通信量為,m n,個(gè)字節(jié)。,2024/9/28,66,,國家高性能計(jì)算中心（合肥）,機(jī)器的成本、價(jià)格與性,/,價(jià)比,,機(jī)器的成本與價(jià)格,,機(jī)器的性能,/,價(jià)格比,Performance/Cost Ratio ：,系指用單位代價(jià)（通常以百萬美元表示）所獲取的性能（通常以,MIPS,或,MFLOPS,表示）每秒執(zhí)行的指令數(shù),,利用率（,Utilization）：,可達(dá)到的速度與峰值速度之比,,2024/9/28,67,,國家高性能計(jì)算中心（合肥）,算法級(jí)性能評(píng)測,,加速比性能定律,,并行系統(tǒng)的加速比

50、是指對(duì)于一個(gè)給定的應(yīng)用，并行算法（或并行程序）的執(zhí)行速度相對(duì)于串行算法（或串行程序）的執(zhí)行速度加快了多少倍。,,Amdahl,定律,,Gustafson,定律,,Sun Ni,定律,,可擴(kuò)放性評(píng)測標(biāo)準(zhǔn),,等效率度量標(biāo)準(zhǔn),,等速度度量標(biāo)準(zhǔn),,平均延遲度量標(biāo)準(zhǔn),2024/9/28,68,,國家高性能計(jì)算中心（合肥）,Amdahl,定律,,P：,處理器數(shù)；,,W：,問題規(guī)模（,計(jì)算負(fù)載、工作負(fù)載，給定問題的總計(jì)算量,）；,,W,s,：,應(yīng)用程序中的串行分量，,f,是串行分量比例（,f = W,s,/W， W,s,=W,1,）；,,W,P,：,應(yīng)用程序中可并行化部分，,1-,f,為并行分量比例；,,W

51、,s,+W,p,=W；,,T,s,=T,1,：,串行執(zhí)行時(shí)間，,T,p,：,并行執(zhí)行時(shí)間；,,S：,加速比，,E：,效率；,,出發(fā)點(diǎn)：,,固定不變的計(jì)算負(fù)載；,,固定的計(jì)算負(fù)載分布在多個(gè)處理器上的，,,增加處理器加快執(zhí)行速度，從而達(dá)到了加速的目的。,2024/9/28,69,,國家高性能計(jì)算中心（合肥）,Amdahl,定律,（,cont‘d),,固定負(fù)載的加速公式：,,,,W,s,+ W,p,可相應(yīng)地表示為,f+（1-f）,,,,,,p→∞,時(shí)，上式極限為：,S= 1 / f,,W,o,為額外開銷,,2024/9/28,70,,國家高性能計(jì)算中心（合肥）,Amdahl’s law (cont’

52、d),,2024/9/28,71,,國家高性能計(jì)算中心（合肥）,Gustafson,定律,,出發(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,加速定律,:,,,,并行開銷,W,o,：,,2024/9/28,72,,國家高性能計(jì)算中心（合肥）,Gustafson,定律（,cont‘d),,2024/9/28,73,,

53、國家高性能計(jì)算中心（合肥）,Sun,和,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ǔ)受限的加速公式 ：,,,,,并行開銷,W,o,:,2024/9/28,74,,國家高性能計(jì)算中心（

54、合肥）,Sun,和,Ni,定律,(,cont’d),,G（p）=1,時(shí)就是,Amdahl,加速定律；,,,G（p）=p,變?yōu)?f + p（1-f），,就是,Gustafson,加速定律,,G（p）>p,時(shí)，相應(yīng)于計(jì)算機(jī)負(fù)載比存儲(chǔ)要求增加得快，此時(shí),Sun,和,N i,加速均比,Amdahl,加速和,Gustafson,加速為高。,2024/9/28,75,,國家高性能計(jì)算中心（合肥）,加速比討論,,參考的加速經(jīng)驗(yàn)公式：,p/log p≤S≤P,,線性加速比：很少通信開銷的矩陣相加、內(nèi)積運(yùn)算等,,p/log p,的加速 比：分治類的應(yīng)用問題,,通信密集類的應(yīng)用問題 ：,S = 1 / C （ p

55、 ）,,超線性加速,,絕對(duì)加速：最佳并行算法與串行算法,,相對(duì)加速：同一算法在單機(jī)和并行機(jī)的運(yùn)行時(shí)間,,2024/9/28,76,,國家高性能計(jì)算中心（合肥）,可擴(kuò)放性評(píng)測標(biāo)準(zhǔn),,并行計(jì)算的可擴(kuò)放性（,Scalability）,也是主要性能指標(biāo),,可擴(kuò)放性最簡樸的含意是在確定的應(yīng)用背景下，計(jì)算機(jī)系統(tǒng)（或算法或程序等）性能隨處理器數(shù)的增加而按比例提高的能力,,影響加速比的因素：處理器數(shù)與問題規(guī)模,,求解問題中的串行分量,,并行處理所引起的額外開銷（通信、等待、競爭、冗余操作和同步等）,,加大的處理器數(shù)超過了算法中的并發(fā)程度,,增加問題的規(guī)模有利于提高加速的因素：,,較大的問題規(guī)模可提供較高的并發(fā)

56、度；,,額外開銷的增加可能慢于有效計(jì)算的增加；,,算法中的串行分量比例不是固定不變的（串行部分所占的比例隨著問題規(guī)模的增大而縮?。?。,,增加處理器數(shù)會(huì)增大額外開銷和降低處理器利用率，所以對(duì)于一個(gè)特定的并行系統(tǒng)（算法或程序），它們能否有效利用不斷增加的處理器的能力應(yīng)是受限的，而度量這種能力就是可擴(kuò)放性這一指標(biāo)。,2024/9/28,77,,國家高性能計(jì)算中心（合肥）,可擴(kuò)放性評(píng)測標(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ò)放的程度。,,并行

57、算法和體系結(jié)構(gòu),,可擴(kuò)放性研究的主要目的：,,確定解決某類問題用何種并行算法與何種并行體系結(jié)構(gòu)的組合，可以有效地利用大量的處理器,(,算法與結(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),2024/9/28,78,,國家高性能計(jì)算中心（合肥）,等效率度量標(biāo)準(zhǔn),,令,t,ie,,和,t,,io,,分別是并行系統(tǒng)上第,

58、i,個(gè)處理器的有用計(jì)算時(shí)間和額外開銷時(shí)間（包括通信、同步和空閑等待時(shí)間等）,,,,T,p,,是,p,個(gè)處理器系統(tǒng)上并行算法的運(yùn)行時(shí)間，對(duì)于任意,i,顯然有,T,p,= t,ie,+t,,io,，,且,T,e,+ T,o,=,pT,p,,問題的規(guī)模,W,為最佳串行算法所完成的計(jì)算,量,W=T,e,,,,,如果問題規(guī)模,W,保持不變，處理器數(shù),p,增加，開銷,T,o,增大，效率,E,下降。為了維持一定的效率（介于,0與1,之間），當(dāng)處理,數(shù),p,增大時(shí)，需要相應(yīng)地增大問題規(guī)模,W,的值。由此定義函數(shù),f,E,（p）,為問題規(guī)模,W,隨處理器數(shù),p,變化的函數(shù)，為等效率函數(shù)（,ISO-efficie

59、ncy Function）（Kumar1987）,2024/9/28,79,,國家高性能計(jì)算中心（合肥）,等效率度量標(biāo)準(zhǔn)（,cont‘d),,曲線,1,表示算法具有很好的擴(kuò)放性；曲線,2,表示算法是可擴(kuò)放的；曲線,3,表示算法是不可擴(kuò)放的。,,優(yōu)點(diǎn)：簡單可定量計(jì)算的、少量的參數(shù)計(jì)算等效率函數(shù),,缺點(diǎn)：如果,T,o,無法計(jì)算出（在共享存儲(chǔ)并行機(jī)中）,,2024/9/28,80,,國家高性能計(jì)算中心（合肥）,等速度度量標(biāo)準(zhǔn),,p,表示處理器個(gè)數(shù)，,W,表示要求解問題的工作量或稱問題規(guī)模（在此可指浮點(diǎn)操作個(gè)數(shù)），,T,為并行執(zhí)行時(shí)間，定義并行計(jì)算的速度,V,為工作量,W,除以并行時(shí)間,T,,p,個(gè)處

60、理器的并行系統(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)公式,2024/9/28,81,,國家高性能計(jì)算中心（合肥）,等速度度量標(biāo)準(zhǔn)（,cont’d）,,優(yōu)點(diǎn)：直觀地使用易測量的機(jī)器性能速度指標(biāo)來度量,,缺點(diǎn)：某些非浮點(diǎn)運(yùn)算可能造成性能的變化,,,2024/9/28,82,,國家高性能計(jì)算中心（合肥）,平均延遲度量標(biāo)準(zhǔn),,T,i,為,P,i,的執(zhí)行時(shí)間，包括延遲,L,i,，Pi,的總延遲時(shí)間為“,L i+,啟動(dòng)時(shí)間,+,停止時(shí)間”。定義系統(tǒng)平均延遲時(shí)間為,,,,pT,para,=T,o,+ T,s,,,,,,在,p,個(gè)處理器上求解工作量為,W,問題的平均延遲,,在,p’,個(gè)處理器上求解工作量為,W’,問題的平均延遲當(dāng)處理器數(shù)由,p,變到,p’，,而推持并行執(zhí)行效率不變，則定義平均延遲可擴(kuò)放性度量標(biāo)準(zhǔn)為,2024/9/28,83,,國家高性能計(jì)算中心（合肥）,平均延遲度量標(biāo)準(zhǔn)（,Cont’d),,優(yōu)點(diǎn)：平均延遲能在更低層次上衡量機(jī)器的性能,,缺點(diǎn)：需要特定的軟硬件才能獲得平均延遲,,,2024/9/28,84,,國家高性能計(jì)算中心（合肥）,