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

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

2、024/3/29,并行計(jì)算——結(jié)構(gòu)?算法?編程,第三篇 并行數(shù)值算法第八章 基本通信操作第九章 稠密矩陣運(yùn)算第十章 線性方程組的求解第十一章 快速傅里葉變換第四篇 并行程序設(shè)計(jì)第十二章 并行程序設(shè)計(jì)基礎(chǔ)第十三章 并行程序設(shè)計(jì)模型和共享存儲系統(tǒng)編程第十四章 分布存儲系統(tǒng)并行編程第十五章 并行程序設(shè)計(jì)環(huán)境與工具,國家高性能計(jì)算中心（合肥）,4,2024/3/29,第一章并行計(jì)算機(jī)系統(tǒng)及結(jié)構(gòu)模型,1.1 并行計(jì)算1.1

3、.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ī)訪存模型,國家高性能計(jì)算中心（合肥）,5,2024/3/29,并行計(jì)算,并行計(jì)算：并行機(jī)上所作的計(jì)算，又稱高性能計(jì)算或超級計(jì)算。計(jì)算科學(xué)：計(jì)算物理、計(jì)算化學(xué)、計(jì)

4、算生物等科學(xué)與工程問題的需求：氣象預(yù)報(bào)、油藏模擬、核武器數(shù)值模擬、航天器設(shè)計(jì)、基因測序等。需求類型：計(jì)算密集、數(shù)據(jù)密集、網(wǎng)絡(luò)密集。美國HPCC計(jì)劃：重大挑戰(zhàn)性課題，3T性能美國Petaflops研究項(xiàng)目：Pflop/s。美國ASCI計(jì)劃：核武器數(shù)值模擬。,國家高性能計(jì)算中心（合肥）,6,2024/3/29,高性能計(jì)算機(jī),Intel（Option Red)：1Tflops,1997,Pentium ProSGI(Opti

5、on Blue Mountain): 3Tflops,1998,MIPS10000IBM(Option White): 7Tflops,Top4,2001,Power3日本Earth Simulator: 35Tflops,Top1,2002,VPHewlett-Packard ASCI Q： 7Tflops ,Top2,3,2002, Alpha Server中國聯(lián)想：1Tflops,Top43,

6、2002,國家高性能計(jì)算中心（合肥）,7,2024/3/29,系統(tǒng)互連,不同帶寬與距離的互連技術(shù): 總線、SAN、LAN、MAN、WAN,,國家高性能計(jì)算中心（合肥）,8,2024/3/29,局部總線、I/O總線、SAN和LAN,,國家高性能計(jì)算中心（合肥）,9,2024/3/29,網(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

7、Diameter）： 網(wǎng)絡(luò)中任何兩個(gè)節(jié)點(diǎn)之間的最長距離，即最大路徑數(shù)。對剖寬度（Bisection Width） ：對分網(wǎng)絡(luò)各半所必須移去的最少邊數(shù)對剖帶寬（ Bisection Bandwidth）:每秒鐘內(nèi)，在最小的對剖平面上通過所有連線的最大信息位（或字節(jié)）數(shù)如果從任一節(jié)點(diǎn)觀看網(wǎng)絡(luò)都一樣，則稱網(wǎng)絡(luò)為對稱的（Symmetry）,國家高性能計(jì)算中心（合肥）,10,2024/3/29,靜態(tài)互連網(wǎng)絡(luò) 與動(dòng)態(tài)互連網(wǎng)絡(luò),靜態(tài)互連網(wǎng)絡(luò)：處

8、理單元間有著固定連接的一類網(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)和多級互連網(wǎng)絡(luò)等。,國家高性能計(jì)算中心（合肥）,11,2024/3/29,靜態(tài)互連網(wǎng)絡(luò)（1）,一維線性陣列（1-D Linear Array）：并行機(jī)中最簡單、最基本的互連方

9、式，每個(gè)節(jié)點(diǎn)只與其左、右近鄰相連，也叫二近鄰連接，N個(gè)節(jié)點(diǎn)用N-1條邊串接之，內(nèi)節(jié)點(diǎn)度為2，直徑為N-1，對剖寬度為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)镹-1（單向環(huán)），對剖寬度為2,,國家高性能計(jì)算中心（合肥）,12,2024/3/29,靜態(tài)互連網(wǎng)絡(luò)（2）,二維網(wǎng)孔（2-D Mesh）：每個(gè)節(jié)點(diǎn)只與其上、下、左、右的近鄰相連（邊界

10、節(jié)點(diǎn)除外），節(jié)點(diǎn)度為4，網(wǎng)絡(luò)直徑為 ，對剖寬度為 在垂直方向上帶環(huán)繞，水平方向呈蛇狀，就變成Illiac網(wǎng)孔了，節(jié)點(diǎn)度恒為4，網(wǎng)絡(luò)直徑為 ，而對剖寬度為 垂直和水平方向均帶環(huán)繞，則變成了2-D環(huán)繞（2-D Torus），節(jié)點(diǎn)度恒為4，網(wǎng)絡(luò)直徑為 ，對剖寬度為,,,,,,,,,國家高性能計(jì)算中心（合肥）,13,2024/3/29,靜態(tài)互連網(wǎng)絡(luò)（3）,二叉樹：除了根、葉

11、節(jié)點(diǎn)，每個(gè)內(nèi)節(jié)點(diǎn)只與其父節(jié)點(diǎn)和兩個(gè)子節(jié)點(diǎn)相連。節(jié)點(diǎn)度為3，對剖寬度為1，而樹的直徑為 如果盡量增大節(jié)點(diǎn)度為，則直徑縮小為2，此時(shí)就變成了星形網(wǎng)絡(luò)，其對剖寬度為傳統(tǒng)二叉樹的主要問題是根易成為通信瓶頸。胖樹節(jié)點(diǎn)間的通路自葉向根逐漸變寬。,,,,國家高性能計(jì)算中心（合肥）,14,2024/3/29,靜態(tài)互連網(wǎng)絡(luò)（4）,超立方 ：一個(gè)n-立方由 個(gè)頂點(diǎn)組成，3-立方如圖(a)所示；4-立方如圖(

12、b)所示，由兩個(gè)3-立方的對應(yīng)頂點(diǎn)連接而成。n-立方的節(jié)點(diǎn)度為n，網(wǎng)絡(luò)直徑也是n ，而對剖寬度為 。如果將3-立方的每個(gè)頂點(diǎn)代之以一個(gè)環(huán)就構(gòu)成了如圖(d)所示的3-立方環(huán)，此時(shí)每個(gè)頂點(diǎn)的度為3，而不像超立方那樣節(jié)點(diǎn)度為n。,,,,,國家高性能計(jì)算中心（合肥）,15,2024/3/29,嵌入,將網(wǎng)絡(luò)中的各節(jié)點(diǎn)映射到另一個(gè)網(wǎng)絡(luò)中去用膨脹（Dilation）系數(shù)來描述嵌入的質(zhì)量，它是指被嵌入網(wǎng)絡(luò)中的一條鏈路在所要嵌入的網(wǎng)絡(luò)中對

13、應(yīng)所需的最大鏈路數(shù) 如果該系數(shù)為1，則稱為完美嵌入。 環(huán)網(wǎng)可完美嵌入到2-D環(huán)繞網(wǎng)中 超立方網(wǎng)可完美嵌入到2－D環(huán)繞網(wǎng)中,,,國家高性能計(jì)算中心（合肥）,16,2024/3/29,嵌入,,國家高性能計(jì)算中心（合肥）,17,2024/3/29,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,靜態(tài)互連網(wǎng)絡(luò)特性比較,國家高性能計(jì)算中心（合肥）,18,2

14、024/3/29,動(dòng)態(tài)互連網(wǎng)絡(luò) (1),總線：PCI、VME、Multics、Sbus、MicroChannel 多處理機(jī)總線系統(tǒng)的主要問題包括總線仲裁、中斷處理、協(xié)議轉(zhuǎn)換、快速同步、高速緩存一致性協(xié)議、分事務(wù)、總線橋和層次總線擴(kuò)展等,,國家高性能計(jì)算中心（合肥）,19,2024/3/29,動(dòng)態(tài)互連網(wǎng)絡(luò) （2）,交叉開關(guān)（Crossbar）：單級交換網(wǎng)絡(luò)，可為每個(gè)端口提供更高的帶寬。象電話交換機(jī)一樣，交叉點(diǎn)開關(guān)可由程序控制動(dòng)態(tài)設(shè)置其

15、處于“開”或“關(guān)”狀態(tài)，而能提供所有（源、目的）對之間的動(dòng)態(tài)連接。交叉開關(guān)一般有兩種使用方式：一種是用于對稱的多處理機(jī)或多計(jì)算機(jī)機(jī)群中的處理器間的通信；另一種是用于SMP服務(wù)器或向量超級計(jì)算機(jī)中處理器和存儲器之間的存取。,國家高性能計(jì)算中心（合肥）,20,2024/3/29,動(dòng)態(tài)互聯(lián)網(wǎng)絡(luò) （3）,單級交叉開關(guān)級聯(lián)起來形成多級互連網(wǎng)絡(luò)MIN（Multistage Interconnection Network）,,國家高性能計(jì)算中心（合

16、肥）,21,2024/3/29,動(dòng)態(tài)互連網(wǎng)絡(luò)（4）,交換開關(guān)模塊： 一個(gè)交換開關(guān)模塊有n個(gè)輸入和n個(gè)輸出，每個(gè)輸入可連接到任意輸出端口，但只允許一對一或一對多的映射，不允許多對一的映射，因?yàn)檫@將發(fā)生輸出沖突 級間互連（Interstage Connection ）：均勻洗牌、蝶網(wǎng)、多路均勻洗牌、交叉開關(guān)、立方連接n輸入的Ω網(wǎng)絡(luò)需要 級 開關(guān)，在Ilinois大學(xué)的Cedar[2]多處理機(jī)系統(tǒng)中采用了Ω

17、網(wǎng)絡(luò) Cray Y/MP多級網(wǎng)絡(luò)，該網(wǎng)絡(luò)用來支持8個(gè)向量處理器和256個(gè)存儲器模塊之間的數(shù)據(jù)傳輸。網(wǎng)絡(luò)能夠避免8個(gè)處理器同時(shí)進(jìn)行存儲器存取時(shí)的沖突。,,,國家高性能計(jì)算中心（合肥）,22,2024/3/29,動(dòng)態(tài)互連網(wǎng)絡(luò)比較,n,節(jié)點(diǎn)規(guī)模 w，數(shù)據(jù)寬度,,,,,,,,,,,,,,國家高性能計(jì)算中心（合肥）,23,2024/3/29,標(biāo)準(zhǔn)互聯(lián)網(wǎng)絡(luò)（1）,Myrinet:Myrinet是由Myricom公司設(shè)計(jì)的千兆位包交換網(wǎng)

18、絡(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ù)鏈路層具有可變長的包格式，對每條鏈路施行流控制和錯(cuò)誤控制，并使用切通選路法以及定制的可編程的主機(jī)接口。在物理層上，Myrinet網(wǎng)使用全雙工SAN鏈路，最長可達(dá)3米，峰值速率為（

19、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ī)存取存儲器SRAM。140 of the November 2002 TOP500 use Myrinet, including 15 of the top 100,國家高性能計(jì)算中心（合肥）,

20、24,2024/3/29,Myrinet連接的LAN/Cluster,,,國家高性能計(jì)算中心（合肥）,25,2024/3/29,標(biāo)準(zhǔn)互連網(wǎng)絡(luò)（2),高性能并行接口（HiPPI）Los Alamos國家實(shí)驗(yàn)室于1987年提出的一個(gè)標(biāo)準(zhǔn)，其目的是試圖統(tǒng)一來自不同產(chǎn)商生產(chǎn)的所有大型機(jī)和超級計(jì)算機(jī)的接口。在大型機(jī)和超級計(jì)算機(jī)工業(yè)界，HiPPI作為短距離的系統(tǒng)到系統(tǒng)以及系統(tǒng)到外設(shè)連接的高速I/O通道。1993年，ANSI X3T9.3委員會認(rèn)

21、可了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í)延的超級HiPPI技術(shù)，SGI公司和Los Alamos國家實(shí)驗(yàn)室都開發(fā)了用來構(gòu)筑速率高達(dá)25.6Gbps的HiPPI交換開關(guān)的HiPPI技術(shù)。HiPPI通道和HiPPI交換開關(guān)被用在SGI

22、 Power Challenge服務(wù)器、IBM 390主機(jī)、Cray Y/MP、C90和T3D/T3E等系統(tǒng),國家高性能計(jì)算中心（合肥）,26,2024/3/29,使用HiPPI通道和開關(guān)構(gòu)筑的LAN主干網(wǎng),,國家高性能計(jì)算中心（合肥）,27,2024/3/29,標(biāo)準(zhǔn)互連網(wǎng)絡(luò)（3）,光纖通道FC（Fiber Channel） :通道和網(wǎng)絡(luò)標(biāo)準(zhǔn)的集成 光纖通道既可以是共享介質(zhì)，也可以是一種交換技術(shù) 光纖通道操作速度范圍可從100到1

23、33、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（Fiber Distributed Data Interface）FDDI采用雙向光纖令牌環(huán)可提供100-200Mbps

24、數(shù)據(jù)傳輸速率 FDDI具有互連大量設(shè)備的能力 傳統(tǒng)的FDDI僅以異步方式操作,國家高性能計(jì)算中心（合肥）,28,2024/3/29,雙向FDDI環(huán)作為主干網(wǎng),,國家高性能計(jì)算中心（合肥）,29,2024/3/29,標(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)行

25、傳輸。這種技術(shù)是基于報(bào)元交換機(jī)制。ATM的目的是將實(shí)時(shí)和突發(fā)數(shù)據(jù)的傳輸合并成單一的網(wǎng)絡(luò)技術(shù)。ATM網(wǎng)絡(luò)支持從25到51、155和622Mbps不同的速率，其速率越低ATM交換器和使用的鏈路價(jià)格越低。,國家高性能計(jì)算中心（合肥）,30,2024/3/29,香港大學(xué)開發(fā)的Pearl機(jī)群,,國家高性能計(jì)算中心（合肥）,31,2024/3/29,標(biāo)準(zhǔn)互連網(wǎng)絡(luò)（5）,國家高性能計(jì)算中心（合肥）,32,2024/3/29,并行計(jì)算機(jī)結(jié)構(gòu)模型,,

26、國家高性能計(jì)算中心（合肥）,33,2024/3/29,并行計(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)的其它部分（包括板級Cache、局存、NIC和DISK）連接起來。優(yōu)點(diǎn)是CPU升級只需要更換Shell。,,國家高性能計(jì)算中心（合肥）,34,2024/3/29,五種結(jié)構(gòu)特性一覽表,國家高性能計(jì)算中心（合肥）,

27、35,2024/3/29,并行計(jì)算機(jī)訪存模型（1),,,,,UMA（Uniform Memory Access）模型是均勻存儲訪問模型的簡稱。其特點(diǎn)是：物理存儲器被所有處理器均勻共享；所有處理器訪問任何存儲字取相同的時(shí)間；每臺處理器可帶私有高速緩存；外圍設(shè)備也可以一定形式共享。,國家高性能計(jì)算中心（合肥）,36,2024/3/29,并行計(jì)算機(jī)訪存模型（2),NUMA(Nonuniform Memory Access)模型是非均勻

28、存儲訪問模型的簡稱。特點(diǎn)是：被共享的存儲器在物理上是分布在所有的處理器中的，其所有本地存儲器的集合就組成了全局地址空間；處理器訪問存儲器的時(shí)間是不一樣的；訪問本地存儲器LM或群內(nèi)共享存儲器CSM較快，而訪問外地的存儲器或全局共享存儲器GSM較慢(此即非均勻存儲訪問名稱的由來)；每臺處理器照例可帶私有高速緩存，外設(shè)也可以某種形式共享。,國家高性能計(jì)算中心（合肥）,37,2024/3/29,并行計(jì)算機(jī)訪存模型（3),COMA(Cach

29、e-Only Memory Access)模型是全高速緩存存儲訪問的簡稱。其特點(diǎn)是：各處理器節(jié)點(diǎn)中沒有存儲層次結(jié)構(gòu)，全部高速緩存組成了全局地址空間；利用分布的高速緩存目錄D進(jìn)行遠(yuǎn)程高速緩存的訪問;COMA中的高速緩存容量一般都大于2 級高速緩存容量；使用COMA時(shí)，數(shù)據(jù)開始時(shí)可任意分配，因?yàn)樵谶\(yùn)行時(shí)它最終會被遷移到要用到它們的地方。,國家高性能計(jì)算中心（合肥）,38,2024/3/29,并行計(jì)算機(jī)訪存模型（4),CC-NUMA（

30、Coherent-Cache Nonuniform Memory Access）模型是高速緩存一致性非均勻存儲訪問模型的簡稱。其特點(diǎn)是：大多數(shù)使用基于目錄的高速緩存一致性協(xié)議；保留SMP結(jié)構(gòu)易于編程的優(yōu)點(diǎn)，也改善常規(guī)SMP的可擴(kuò)放性；CC-NUMA實(shí)際上是一個(gè)分布共享存儲的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)行期間，高速緩存一致性硬件會自動(dòng)地將數(shù)據(jù)

31、遷移至要用到它的地方。,,國家高性能計(jì)算中心（合肥）,39,2024/3/29,并行計(jì)算機(jī)訪存模型（5),NORMA（No-Remote Memory Access）模型是非遠(yuǎn)程存儲訪問模型的簡稱。NORMA的特點(diǎn)是：所有存儲器是私有的；絕大數(shù)NUMA都不支持遠(yuǎn)程存儲器的訪問；在DSM中，NORMA就消失了。,國家高性能計(jì)算中心（合肥）,40,2024/3/29,構(gòu)筑并行機(jī)系統(tǒng)的不同存儲結(jié)構(gòu),,國家高性能計(jì)算中心（合肥）,41,2

32、024/3/29,第二章 當(dāng)代并行機(jī)系統(tǒng),2.1 共享存儲多處理機(jī)系統(tǒng)2.1.1 對稱多處理機(jī)SMP結(jié)構(gòu)特性2.2 分布存儲多計(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,國家高性能計(jì)算中心（合肥）,42,2024/3/29,對稱多處理機(jī)SMP(1),SMP: 采用商用微處理器，通常有片上和片外Cache，基于總線連接，集中式共享存

33、儲，UMA結(jié)構(gòu)例子：SGI Power Challenge, DEC Alpha Server,Dawning 1,,國家高性能計(jì)算中心（合肥）,43,2024/3/29,對稱多處理機(jī)SMP(2),優(yōu)點(diǎn)對稱性單地址空間，易編程性，動(dòng)態(tài)負(fù)載平衡，無需顯示數(shù)據(jù)分配高速緩存及其一致性，數(shù)據(jù)局部性，硬件維持一致性低通信延遲，Load/Store完成問題欠可靠，BUS,OS,SM通信延遲（相對于CPU），競爭加劇慢速增加的帶寬（

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

35、儲器和I/O能力例子：Intel Option Red IBM SP2 Dawning 1000,,國家高性能計(jì)算中心（合肥）,45,2024/3/29,典型MPP系統(tǒng)特性比較,國家高性能計(jì)算中心（合肥）,46,2024/3/29,MPP所用的高性能CPU特性比較,國家高性能計(jì)算中心（合肥）,47,2024/3/29,機(jī)群型大規(guī)模并行機(jī)SP2,設(shè)計(jì)策略：機(jī)群體系結(jié)構(gòu) 標(biāo)準(zhǔn)環(huán)境 標(biāo)準(zhǔn)編程模型 系統(tǒng)可用性 精選的單一系

36、統(tǒng)映像 系統(tǒng)結(jié)構(gòu)：高性能開關(guān) HPS 多級Ω網(wǎng)絡(luò) 寬節(jié)點(diǎn)、窄節(jié)點(diǎn)和窄節(jié)點(diǎn)2,,國家高性能計(jì)算中心（合肥）,48,2024/3/29,工作站機(jī)群COW,分布式存儲，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)境例子：Berkeley NOW，Alpha F

37、arm, FXCOW,國家高性能計(jì)算中心（合肥）,49,2024/3/29,典型的機(jī)群系統(tǒng),國家高性能計(jì)算中心（合肥）,50,2024/3/29,SMP\MPP\機(jī)群比較,國家高性能計(jì)算中心（合肥）,51,2024/3/29,第三章 并行計(jì)算性能評測,3.1 并行機(jī)的一些基本性能指標(biāo)3.2 加速比性能定律3.2.1 Amdahl定律3.2.2 Gustafson定律3.2.3 Sun和Ni定律3.3 可擴(kuò)放性評測標(biāo)準(zhǔn)3.3.

38、1 并行計(jì)算的可擴(kuò)放性3.3.2 等效率度量標(biāo)準(zhǔn)3.3.3 等速度度量標(biāo)準(zhǔn)3.3.4 平均延遲度量標(biāo)準(zhǔn),國家高性能計(jì)算中心（合肥）,52,2024/3/29,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ì)A

39、PRAM模型下執(zhí)行時(shí)間,,國家高性能計(jì)算中心（合肥）,53,2024/3/29,存儲器性能,存儲器的層次結(jié)構(gòu)(C,L,B)估計(jì)存儲器的帶寬RISC add r1,r2,r3 r 8bytes 100MHzB = 3*8*100*106 B/s= 2.4GB/s,,國家高性能計(jì)算中心（合肥）,54,2024/3/29,并行與通信開銷,并行和通信開銷：相對于計(jì)算很大。 PowerPC (每個(gè)周期 15ns 執(zhí)行

40、4flops; 創(chuàng)建一個(gè)進(jìn)程1.4ms 可執(zhí)行372000flops)開銷的測量：乒--乓方法（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í)間?？梢话慊癁闊嵬炼狗ǎ℉ot-Potato），也稱為救火隊(duì)法（Fire-Brigade) 0——

41、1 —— 2 —— … —— -n-1 —— 0,國家高性能計(jì)算中心（合肥）,55,2024/3/29,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 1en

42、d_time = second（ ）total_time = end_time – start_time communication_time[i] = total_time/2 else if （my_node_id = 1） then /*接收者*/ receive an m-byte message from node 0 send an m-byte m

43、essage to node 0endif,國家高性能計(jì)算中心（合肥）,56,2024/3/29,并行開銷的表達(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,國家高性能計(jì)算

44、中心（合肥）,57,2024/3/29,并行開銷的表達(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è)

45、字節(jié)的不同消息給對方，所以總通信量為mn2個(gè)字節(jié)；循環(huán)移位（Circular-shift）：處理器i發(fā)送m個(gè)字節(jié)給處理器i+1，處理器n-1發(fā)送m個(gè)字節(jié)給處理器0，所以通信量為m n個(gè)字節(jié)。,國家高性能計(jì)算中心（合肥）,58,2024/3/29,機(jī)器的成本、價(jià)格與性/價(jià)比,機(jī)器的成本與價(jià)格機(jī)器的性能/價(jià)格比 Performance/Cost Ratio ：系指用單位代價(jià)（通常以百萬美元表示）所獲取的性能（通常以MIPS或MFLOPS

46、表示） 利用率（Utilization）：可達(dá)到的速度與峰值速度之比,國家高性能計(jì)算中心（合肥）,59,2024/3/29,算法級性能評測,加速比性能定律并行系統(tǒng)的加速比是指對于一個(gè)給定的應(yīng)用，并行算法（或并行程序）的執(zhí)行速度相對于串行算法（或串行程序）的執(zhí)行速度加快了多少倍。Amdahl 定律Gustafson定律Sun Ni定律可擴(kuò)放性評測標(biāo)準(zhǔn)等效率度量標(biāo)準(zhǔn)等速度度量標(biāo)準(zhǔn)平均延遲度量標(biāo)準(zhǔn),國家高性能計(jì)算中心（合肥）

47、,60,2024/3/29,Amdahl 定律,P：處理器數(shù)；W：問題規(guī)模（計(jì)算負(fù)載、工作負(fù)載，給定問題的總計(jì)算量）；Ws：應(yīng)用程序中的串行分量，f是串行分量比例（f = Ws/W， Ws=W1）；WP：應(yīng)用程序中可并行化部分，1-f為并行分量比例；Ws +W p =W；Ts=T1 ：串行執(zhí)行時(shí)間，T p ：并行執(zhí)行時(shí)間；S：加速比，E：效率； 出發(fā)點(diǎn)：固定不變的計(jì)算負(fù)載； 固定的計(jì)算負(fù)載分布在多個(gè)處理器上的，增加處

48、理器加快執(zhí)行速度，從而達(dá)到了加速的目的。,國家高性能計(jì)算中心（合肥）,61,2024/3/29,Amdahl定律（cont‘d),固定負(fù)載的加速公式： W s+ W p可相應(yīng)地表示為f+（1-f）p→∞時(shí)，上式極限為： S= 1 / f W o為額外開銷,,,,國家高性能計(jì)算中心（合肥）,62,2024/3/29,Amdahl

49、’s law (cont’d),,國家高性能計(jì)算中心（合肥）,63,2024/3/29,Gustafson定律,出發(fā)點(diǎn)：對于很多大型計(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加

50、速定律 :并行開銷W o ：,,,,國家高性能計(jì)算中心（合肥）,64,2024/3/29,Gustafson定律（cont‘d),,國家高性能計(jì)算中心（合肥）,65,2024/3/29,Sun 和 Ni定律,基本思想：只要存儲空間許可，應(yīng)盡量增大問題規(guī)模以產(chǎn)生更好和更精確的解（此時(shí)可能使執(zhí)行時(shí)間略有增加）。假定在單節(jié)點(diǎn)上使用了全部存儲容量M并在相應(yīng)于W的時(shí)間內(nèi)求解之，此時(shí)工作負(fù)載W= fW + （1-f）W。 在p 個(gè)節(jié)點(diǎn)的

51、并行系統(tǒng)上，能夠求解較大規(guī)模的問題是因?yàn)榇鎯θ萘靠稍黾拥絧M。令因子G（p）反應(yīng)存儲容量增加到p倍時(shí)并行工作負(fù)載的增加量，所以擴(kuò)大后的工作負(fù)載W = fW + （1-f）G（p）W。存儲受限的加速公式 ： 并行開銷W o:,,,,國家高性能計(jì)算中心（合肥）,66,2024/3/29,Sun 和 Ni定律(cont’d),G（p）=1時(shí)就是Amdahl加速定律； G（p）=p 變?yōu)?f + p（1-f），就是Gustafson

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

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

54、等）加大的處理器數(shù)超過了算法中的并發(fā)程度增加問題的規(guī)模有利于提高加速的因素：較大的問題規(guī)?？商峁┹^高的并發(fā)度；額外開銷的增加可能慢于有效計(jì)算的增加；算法中的串行分量比例不是固定不變的（串行部分所占的比例隨著問題規(guī)模的增大而縮?。?。增加處理器數(shù)會增大額外開銷和降低處理器利用率，所以對于一個(gè)特定的并行系統(tǒng)（算法或程序），它們能否有效利用不斷增加的處理器的能力應(yīng)是受限的，而度量這種能力就是可擴(kuò)放性這一指標(biāo)。,國家高性能計(jì)算中心（合

55、肥）,69,2024/3/29,可擴(kuò)放性評測標(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)的組合，可以有效地利用大量的處理器；對于運(yùn)行于某種體系結(jié)構(gòu)的并行機(jī)上的某種算法當(dāng)移植到大規(guī)模處理機(jī)上后

56、運(yùn)行的性能；對固定的問題規(guī)模，確定在某類并行機(jī)上最優(yōu)的處理器數(shù)與可獲得的最大的加速比；用于指導(dǎo)改進(jìn)并行算法和并行機(jī)體系結(jié)構(gòu)，以使并行算法盡可能地充分利用可擴(kuò)充的大量處理器 目前無一個(gè)公認(rèn)的、標(biāo)準(zhǔn)的和被普遍接受的嚴(yán)格定義和評判它的標(biāo)準(zhǔn),國家高性能計(jì)算中心（合肥）,70,2024/3/29,等效率度量標(biāo)準(zhǔn),令tie 和t io 分別是并行系統(tǒng)上第i個(gè)處理器的有用計(jì)算時(shí)間和額外開銷時(shí)間（包括通信、同步和空閑等待時(shí)間等）T p

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

58、 Function）（Kumar1987）,,,,,國家高性能計(jì)算中心（合肥）,71,2024/3/29,等效率度量標(biāo)準(zhǔn)（cont‘d),曲線1表示算法具有很好的擴(kuò)放性；曲線2表示算法是可擴(kuò)放的；曲線 3表示算法是不可擴(kuò)放的。 優(yōu)點(diǎn)：簡單可定量計(jì)算的、少量的參數(shù)計(jì)算等效率函數(shù) 缺點(diǎn)：如果To無法計(jì)算出（在共享存儲并行機(jī)中）,,國家高性能計(jì)算中心（合肥）,72,2024/3/29,等速度度量標(biāo)準(zhǔn),p 表示處理器個(gè)數(shù)，W表示要求解問題的

59、工作量或稱問題規(guī)模（在此可指浮點(diǎn)操作個(gè)數(shù)），T為并行執(zhí)行時(shí)間，定義并行計(jì)算的速度V為工作量W除以并行時(shí)間T p個(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)公式,,,國家高性能計(jì)算中心（合肥）,73,2024/3/29,等速度度量標(biāo)準(zhǔn)（cont

60、’d）,,,優(yōu)點(diǎn)：直觀地使用易測量的機(jī)器性能速度指標(biāo)來度量缺點(diǎn)：某些非浮點(diǎn)運(yùn)算可能造成性能的變化,國家高性能計(jì)算中心（合肥）,74,2024/3/29,平均延遲度量標(biāo)準(zhǔn),Ti為Pi的執(zhí)行時(shí)間，包括包括延遲Li，Pi的總延遲時(shí)間為“L i+啟動(dòng)時(shí)間+停止時(shí)間”。定義系統(tǒng)平均延遲時(shí)間為pTpara =To+ Ts 在p個(gè)處理器上求解工作量為W問題的平均延遲 在p’個(gè)處

61、理器上求解工作量為W’問題的平均延遲當(dāng)處理器數(shù)由p變到p’，而推持并行執(zhí)行效率不變，則定義平均延遲可擴(kuò)放性度量標(biāo)準(zhǔn)為,,,,,,國家高性能計(jì)算中心（合肥）,75,2024/3/29,平均延遲度量標(biāo)準(zhǔn)（Cont’d),,優(yōu)點(diǎn)：平均延遲能在更低層次上衡量機(jī)器的性能缺點(diǎn)：需要特定的軟硬件才能獲得平均延遲,并 行 計(jì) 算,中國科學(xué)技術(shù)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)系國家高性能計(jì)算中心(合肥)2003年9月,第二篇 并行算法的設(shè)計(jì) 第四章 并

62、行算法的設(shè)計(jì)基礎(chǔ) 第五章 并行算法的一般設(shè)計(jì)方法 第六章 并行算法的基本設(shè)計(jì)技術(shù) 第七章 并行算法的一般設(shè)計(jì)過程,第四章 并行算法的設(shè)計(jì)基礎(chǔ) 4.1 并行算法的基礎(chǔ)知識 4.2 并行計(jì)算模型,4.1 并行算法的基礎(chǔ)知識 4.1.1 并行算法的定義和分類 4.1.2 并行算法的表達(dá) 4.1.3 并行算法的復(fù)雜性度量 4.1.4 并行算法中的同步和通訊,國家高性能計(jì)算中心（合肥）,

63、80,2024/3/29,并行算法的定義和分類,并行算法的定義算法并行算法：一些可同時(shí)執(zhí)行的諸進(jìn)程的集合，這些進(jìn)程互相作用和協(xié)調(diào)動(dòng)作從而達(dá)到給定問題的求解。并行算法的分類數(shù)值計(jì)算和非數(shù)值計(jì)算同步算法和異步算法分布算法確定算法和隨機(jī)算法,4.1 并行算法的基礎(chǔ)知識 4.1.1 并行算法的定義和分類 4.1.2 并行算法的表達(dá) 4.1.3 并行算法的復(fù)雜性度量 4.1.4 并行算法中的同步和通訊,國家

64、高性能計(jì)算中心（合肥）,82,2024/3/29,并行算法的表達(dá),描述語言可以使用類Algol、類Pascal等；在描述語言中引入并行語句。并行語句示例Par-do語句 for i=1 to n par-do …… end forfor all語句 for all Pi, where 0≤i≤k

65、 …… end for,4.1 并行算法的基礎(chǔ)知識 4.1.1 并行算法的定義和分類 4.1.2 并行算法的表達(dá) 4.1.3 并行算法的復(fù)雜性度量 4.1.4 并行算法中的同步和通訊,國家高性能計(jì)算中心（合肥）,84,2024/3/29,并行算法的復(fù)雜性度量,串行算法的復(fù)雜性度量最壞情況下的復(fù)雜度(Worst-CASE Complexity)期望復(fù)雜度(Expected Co

66、mplexity)并行算法的幾個(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ù)。,國家高性能計(jì)算中心（合肥）,85,2024/3/29,并行算法的復(fù)雜性度量,Brent定理令W(n)是某并行算法A在運(yùn)行時(shí)間T(n)內(nèi)所執(zhí)行的運(yùn)算量，

67、則A使用p臺處理器可在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)一致的對于任意的p，c(n)?W(n),4.1 并行算法的基礎(chǔ)知識 4.1.1 并行算法的定義和分類 4.1.2 并行算法的表達(dá) 4.1.3 并行算法的復(fù)雜性度量 4.1.4 并行算法中的同步和通訊,國家高性能計(jì)算中心（合肥）,87,2024/

68、3/29,并行算法的同步,同步概念同步是在時(shí)間上強(qiáng)使各執(zhí)行進(jìn)程在某一點(diǎn)必須互相等待；可用軟件、硬件和固件的辦法來實(shí)現(xiàn)。同步語句示例算法4.1 共享存儲多處理器上求和算法 輸入：A=(a0,…,an-1),處理器數(shù)p 輸出：S=Σai Begin (1)S=0

69、 (2.3) lock(S) (2)for all Pi where 0≤i≤p-1 do S=S+L (2.1) L=0 (2.4) unlock(S)