并行計算(中科大講義)

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

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

3、.1 并行計算與計算科學1.1.2 當代科學與工程問題的計算需求1.2 并行計算機系統(tǒng)互連1.2.1 系統(tǒng)互連1.2.2 靜態(tài)互聯(lián)網絡1.2.3 動態(tài)互連網絡1.2.4 標準互聯(lián)網絡1.3 并行計算機系統(tǒng)結構1.3.1 并行計算機結構模型1.3.2 并行計算機訪存模型,國家高性能計算中心（合肥）,5,2024/3/29,并行計算,并行計算：并行機上所作的計算，又稱高性能計算或超級計算。計算科學：計算物理、計算化學、計

4、算生物等科學與工程問題的需求：氣象預報、油藏模擬、核武器數(shù)值模擬、航天器設計、基因測序等。需求類型：計算密集、數(shù)據(jù)密集、網絡密集。美國HPCC計劃：重大挑戰(zhàn)性課題，3T性能美國Petaflops研究項目：Pflop/s。美國ASCI計劃：核武器數(shù)值模擬。,國家高性能計算中心（合肥）,6,2024/3/29,高性能計算機,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,國家高性能計算中心（合肥）,7,2024/3/29,系統(tǒng)互連,不同帶寬與距離的互連技術: 總線、SAN、LAN、MAN、WAN,,國家高性能計算中心（合肥）,8,2024/3/29,局部總線、I/O總線、SAN和LAN,,國家高性能計算中心（合肥）,9,2024/3/29,網絡性能指標,節(jié)點度（Node Degree）：射入或射出一個節(jié)點的邊數(shù)。在單向網絡中，入射和出射邊之和稱為節(jié)點度。網絡直徑（Network

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

8、理單元間有著固定連接的一類網絡，在程序執(zhí)行期間，這種點到點的鏈接保持不變；典型的靜態(tài)網絡有一維線性陣列、二維網孔、樹連接、超立方網絡、立方環(huán)、洗牌交換網、蝶形網絡等動態(tài)網絡：用交換開關構成的，可按應用程序的要求動態(tài)地改變連接組態(tài)；典型的動態(tài)網絡包括總線、交叉開關和多級互連網絡等。,國家高性能計算中心（合肥）,11,2024/3/29,靜態(tài)互連網絡（1）,一維線性陣列（1-D Linear Array）：并行機中最簡單、最基本的互連方

9、式，每個節(jié)點只與其左、右近鄰相連，也叫二近鄰連接，N個節(jié)點用N-1條邊串接之，內節(jié)點度為2，直徑為N-1，對剖寬度為1當首、尾節(jié)點相連時可構成循環(huán)移位器，在拓撲結構上等同于環(huán)，環(huán)可以是單向的或雙向的，其節(jié)點度恒為2，直徑或為 （雙向環(huán)）或為N-1（單向環(huán)），對剖寬度為2,,國家高性能計算中心（合肥）,12,2024/3/29,靜態(tài)互連網絡（2）,二維網孔（2-D Mesh）：每個節(jié)點只與其上、下、左、右的近鄰相連（邊界

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

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

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

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

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

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

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

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

18、絡，其目的是為了構筑計算機機群，使系統(tǒng)互連成為一種商業(yè)產品。Myrinet是基于加州理工學院開發(fā)的多計算機和VLSI技術以及在南加州大學開發(fā)的ATOMIC/LAN技術。Myrinet能假設任意拓撲結構，不必限定為開關網孔或任何規(guī)則的結構。Myrinet在數(shù)據(jù)鏈路層具有可變長的包格式，對每條鏈路施行流控制和錯誤控制，并使用切通選路法以及定制的可編程的主機接口。在物理層上，Myrinet網使用全雙工SAN鏈路，最長可達3米，峰值速率為（

19、1.28＋1.28）Gbps（目前有2.56+2.56)Myrinet交換開關 :8,12,16端口Myrinet主機接口 : 32位的稱作LANai芯片的用戶定制的VLSI處理器，它帶有Myrinet接口、包接口、DMA引擎和快速靜態(tài)隨機存取存儲器SRAM。140 of the November 2002 TOP500 use Myrinet, including 15 of the top 100,國家高性能計算中心（合肥）,

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

21、可了HiPPI標準，它覆蓋了物理和數(shù)據(jù)鏈路層，但在這兩層之上的任何規(guī)定卻取決于用戶。HiPPI是個單工的點到點的數(shù)據(jù)傳輸接口，其速率可達800Mbps到1.6Gbps。開發(fā)成功了一種能提供潛在的6.4Gbps速率，比HiPPI快8倍且有很低時延的超級HiPPI技術，SGI公司和Los Alamos國家實驗室都開發(fā)了用來構筑速率高達25.6Gbps的HiPPI交換開關的HiPPI技術。HiPPI通道和HiPPI交換開關被用在SGI

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

23、33、200、400和800Mbps。FCSI廠商也正在推出未來具有更高速度（1、2或4Gbps）的光纖通道 光纖通道的價值已被現(xiàn)在的某些千兆位局域網所證實，這些局域網就是基于光纖通道技術的 連網拓撲結構的靈活性是光纖通道的主要財富，它支持點到點、仲裁環(huán)及交換光纖連接 FDDI :光纖分布式數(shù)據(jù)接口FDDI（Fiber Distributed Data Interface）FDDI采用雙向光纖令牌環(huán)可提供100-200Mbps

24、數(shù)據(jù)傳輸速率 FDDI具有互連大量設備的能力 傳統(tǒng)的FDDI僅以異步方式操作,國家高性能計算中心（合肥）,28,2024/3/29,雙向FDDI環(huán)作為主干網,,國家高性能計算中心（合肥）,29,2024/3/29,標準互聯(lián)網絡（4）,ATM（Asynchronous Transfer Mode）:由成立于1991年的ATM論壇和ITU標準定義。ATM是一種獨立于介質的消息傳輸協(xié)議，它將消息段變成更短的固定長度為53字節(jié)的報元進行

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

26、國家高性能計算中心（合肥）,33,2024/3/29,并行計算機體系合一結構,SMP、MPP、DSM和COW并行結構漸趨一致。大量的節(jié)點通過高速網絡互連起來節(jié)點遵循Shell結構：用專門定制的Shell電路將商用微處理器和節(jié)點的其它部分（包括板級Cache、局存、NIC和DISK）連接起來。優(yōu)點是CPU升級只需要更換Shell。,,國家高性能計算中心（合肥）,34,2024/3/29,五種結構特性一覽表,國家高性能計算中心（合肥）,

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

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

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

30、Coherent-Cache Nonuniform Memory Access）模型是高速緩存一致性非均勻存儲訪問模型的簡稱。其特點是：大多數(shù)使用基于目錄的高速緩存一致性協(xié)議；保留SMP結構易于編程的優(yōu)點，也改善常規(guī)SMP的可擴放性；CC-NUMA實際上是一個分布共享存儲的DSM多處理機系統(tǒng)；它最顯著的優(yōu)點是程序員無需明確地在節(jié)點上分配數(shù)據(jù)，系統(tǒng)的硬件和軟件開始時自動在各節(jié)點分配數(shù)據(jù)，在運行期間，高速緩存一致性硬件會自動地將數(shù)據(jù)

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

32、024/3/29,第二章 當代并行機系統(tǒng),2.1 共享存儲多處理機系統(tǒng)2.1.1 對稱多處理機SMP結構特性2.2 分布存儲多計算機系統(tǒng)2.2.1 大規(guī)模并行機MPP結構特性2.3 機群系統(tǒng)2.3.1 大規(guī)模并行處理系統(tǒng)MPP機群SP22.3.2 工作站機群COW,國家高性能計算中心（合肥）,42,2024/3/29,對稱多處理機SMP(1),SMP: 采用商用微處理器，通常有片上和片外Cache，基于總線連接，集中式共享存

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

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

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

36、統(tǒng)映像 系統(tǒng)結構：高性能開關 HPS 多級Ω網絡 寬節(jié)點、窄節(jié)點和窄節(jié)點2,,國家高性能計算中心（合肥）,48,2024/3/29,工作站機群COW,分布式存儲，MIMD，工作站+商用互連網絡，每個節(jié)點是一個完整的計算機，有自己的磁盤和操作系統(tǒng)，而MPP中只有微內核優(yōu)點：投資風險小系統(tǒng)結構靈活性能/價格比高能充分利用分散的計算資源可擴放性好問題通信性能并行編程環(huán)境例子：Berkeley NOW，Alpha F

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

38、1 并行計算的可擴放性3.3.2 等效率度量標準3.3.3 等速度度量標準3.3.4 平均延遲度量標準,國家高性能計算中心（合肥）,52,2024/3/29,CPU的某些基本性能指標,工作負載執(zhí)行時間 浮點運算數(shù) 指令數(shù)目 并行執(zhí)行時間 T comput 為計算時間，T paro 為并行開銷時間，T comm為相互通信時間 T n = T comput + T paro+ T comm 例：估計A

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

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

41、1 —— 2 —— … —— -n-1 —— 0,國家高性能計算中心（合肥）,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,國家高性能計算中心（合肥）,56,2024/3/29,并行開銷的表達式：點到點通信,通信開銷 t(m) = t0 + m/ r∞通信啟動時間 t0漸近帶寬r∞ ：傳送無限長的消息時的通信速率半峰值長度m1/2 ：達到一半漸近帶寬所要的消息長度特定性能π0：表示短消息帶寬 t0 = m1/2 / r∞ = 1 /π0,國家高性能計算

44、中心（合肥）,57,2024/3/29,并行開銷的表達式：整體通信,典型的整體通信有： 播送（Broadcasting）：處理器0發(fā)送m個字節(jié)給所有的n個處理器收集（Gather）：處理0接收所有n個處理器發(fā)來在消息，所以處理器0最終接收了m n個字節(jié)；散射（Scatter）：處理器0發(fā)送了m個字節(jié)的不同消息給所有n個處理器，因此處理器0最終發(fā)送了m n個字節(jié)；全交換（Total Exchange）：每個處理器均彼此相互發(fā)送m個

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

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

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

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

49、’s law (cont’d),,國家高性能計算中心（合肥）,63,2024/3/29,Gustafson定律,出發(fā)點：對于很多大型計算，精度要求很高，即在此類應用中精度是個關鍵因素，而計算時間是固定不變的。此時為了提高精度，必須加大計算量，相應地亦必須增多處理器數(shù)才能維持時間不變；除非學術研究，在實際應用中沒有必要固定工作負載而計算程序運行在不同數(shù)目的處理器上，增多處理器必須相應地增大問題規(guī)模才有實際意義。 Gustafson加

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

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

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

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

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

55、肥）,69,2024/3/29,可擴放性評測標準（cont‘d),可擴放性:調整什么和按什么比例調整并行計算要調整的是處理數(shù)p和問題規(guī)模W，兩者可按不同比例進行調整，此比例關系（可能是線性的，多項式的或指數(shù)的等）就反映了可擴放的程度。 并行算法和體系結構可擴放性研究的主要目的：確定解決某類問題用何種并行算法與何種并行體系結構的組合，可以有效地利用大量的處理器；對于運行于某種體系結構的并行機上的某種算法當移植到大規(guī)模處理機上后

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

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

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

59、工作量或稱問題規(guī)模（在此可指浮點操作個數(shù)），T為并行執(zhí)行時間，定義并行計算的速度V為工作量W除以并行時間T p個處理器的并行系統(tǒng)的平均速度定義為并行速度V除以處理器個數(shù) p：W是使用p個處理器時算法的工作量，令W’表示當處理數(shù)從p增大到p’時，為了保持整個系統(tǒng)的平均速度不變所需執(zhí)行的工作量，則可得到處理器數(shù)從 p到p’時平均速度可擴放度量標準公式,,,國家高性能計算中心（合肥）,73,2024/3/29,等速度度量標準（cont

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

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

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

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

64、高性能計算中心（合肥）,82,2024/3/29,并行算法的表達,描述語言可以使用類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 并行算法的基礎知識 4.1.1 并行算法的定義和分類 4.1.2 并行算法的表達 4.1.3 并行算法的復雜性度量 4.1.4 并行算法中的同步和通訊,國家高性能計算中心（合肥）,84,2024/3/29,并行算法的復雜性度量,串行算法的復雜性度量最壞情況下的復雜度(Worst-CASE Complexity)期望復雜度(Expected Co

66、mplexity)并行算法的幾個復雜性度量指標運行時間t(n):包含計算時間和通訊時間，分別用計算時間步和選路時間步作單位。n為問題實例的輸入規(guī)模。處理器數(shù)p(n)并行算法成本c(n): c(n)=t(n)p(n)總運算量W(n): 并行算法求解問題時所完成的總的操作步數(shù)。,國家高性能計算中心（合肥）,85,2024/3/29,并行算法的復雜性度量,Brent定理令W(n)是某并行算法A在運行時間T(n)內所執(zhí)行的運算量，

67、則A使用p臺處理器可在t(n)=O(W(n)/p+T(n))時間內執(zhí)行完畢。W(n)和c(n)密切相關P=O(W(n)/T(n))時，W(n)和c(n)兩者是漸進一致的對于任意的p，c(n)?W(n),4.1 并行算法的基礎知識 4.1.1 并行算法的定義和分類 4.1.2 并行算法的表達 4.1.3 并行算法的復雜性度量 4.1.4 并行算法中的同步和通訊,國家高性能計算中心（合肥）,87,2024/

68、3/29,并行算法的同步,同步概念同步是在時間上強使各執(zhí)行進程在某一點必須互相等待；可用軟件、硬件和固件的辦法來實現(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)