并行計算基礎(chǔ)知識-中國科學(xué)技術(shù)大學(xué)超級計算中心

1、2024/3/27,并行計算基礎(chǔ)知識,1,并行計算基礎(chǔ)知識,馮圣中 fsz@ncic.ac.cn中國科學(xué)院計算技術(shù)研究所國家智能計算機研究開發(fā)中心國家高性能計算中心（北京）,2024/3/27,并行計算基礎(chǔ)知識,2/66,主要內(nèi)容,并行計算并行計算系統(tǒng)基礎(chǔ)并行計算基本概念幾種典型的benchmark,2024/3/27,并行計算基礎(chǔ)知識,3/66,并行計算基本概念,Parallel computing、high perfo

2、rmance computing、 high-end computingThe simultaneous use of more than one computer to solve a problem.多計算機-網(wǎng)絡(luò)多進程/線程-通信并行計算環(huán)境加速比/可擴展性,2024/3/27,并行計算基礎(chǔ)知識,4/66,并行計算系統(tǒng)基礎(chǔ),并行計算機分類主流并行計算機系統(tǒng)比較機群并行計算環(huán)境,2024/3/27,并行計算基礎(chǔ)知識,5

3、/66,并行計算機分類,根據(jù)指令流和數(shù)據(jù)流的不同，通常把計算機系統(tǒng)分為：單指令流單數(shù)據(jù)流（SISD）單指令流多數(shù)據(jù)流（SIMD）多指令流單數(shù)據(jù)流（MISD）多指令流多數(shù)據(jù)流（MIMD）并行計算機系統(tǒng)絕大部分為MIMD系統(tǒng)，包括并行向量機（PVP，Parallel Vector Processor）；對稱多處理機（SMP,Symmetric Multiprocessor）；大規(guī)模并行處理機（MPP，Massively Pa

4、rallel Processor）；機群（Cluster）；分布式共享存儲多處理機（DSM，Distributied Shared Memory）,2024/3/27,并行計算基礎(chǔ)知識,6/66,Top500中的超級計算機,地球模擬器ASCI QASCI White,2024/3/27,并行計算基礎(chǔ)知識,7/66,Earth Simulator,Earth simulator centerNecRmax:35.86Tflop

5、s8*8*640,2024/3/27,并行計算基礎(chǔ)知識,8/66,Earth Simulator,,2024/3/27,并行計算基礎(chǔ)知識,9/66,Earth Simulator,2024/3/27,并行計算基礎(chǔ)知識,10/66,ASCI Q,1024 nodes8cpu/node10240Gflops7727Gflops,2024/3/27,并行計算基礎(chǔ)知識,11/66,ASCI white,LLNL IBM SP power

6、3 Rmax 7.22Tflops,2024/3/27,并行計算基礎(chǔ)知識,12/66,SMP 對稱多處理機,SMP系統(tǒng)一般使用商品化微處理器，具有片上或外置高速緩存經(jīng)由高速總線（或交叉開關(guān)）連向共享存儲器。每個處理器可等同地訪問共享存儲器、I/O設(shè)備和操作系統(tǒng)服務(wù)。單一操作系統(tǒng)映像，全系統(tǒng)只有一個操作系統(tǒng)駐留在共享存儲器中，它根據(jù)各個處理器的負載情況，動態(tài)地分配各個進程到各個處理器，并保持負載平衡；低通信延遲，各個進程通過讀/寫操

7、作系統(tǒng)提供的共享數(shù)據(jù)緩存區(qū)來完成處理器間的通信，其延遲通常小于網(wǎng)絡(luò)通信延遲；共享總線帶寬，所有處理器共享總線帶寬，完成對內(nèi)存模塊和I/O模塊的訪問。,2024/3/27,并行計算基礎(chǔ)知識,13/66,SMP 對稱多處理機（續(xù)）,問題：欠可靠，總線、存儲器、操作系統(tǒng)失效可能導(dǎo)致系統(tǒng)崩潰；可擴展性較差，由于所有處理器都共享總線帶寬，而總線帶寬每3年才增加2倍，趕不上處理器速度和存儲容量的增長步伐，因此SMP的處理器個數(shù)一般少于64個，且

8、只能提供每秒數(shù)百億次的浮點運算。SMP的典型代表有：SGI POWER Challenge XL系列、DEC Alphaserver 84005/440、HP9000/T600和IBM RS6000/R40。,2024/3/27,并行計算基礎(chǔ)知識,14/66,SMP 對稱多處理機（續(xù)）,2024/3/27,并行計算基礎(chǔ)知識,15/66,DSM 分布式共享存儲多處理機,DSM的典型代表為SGI的Origin2000和Origin3000

9、系列并行機處理器對物理分布的共享存儲器的訪問是不對稱的，因此遠端訪問延遲一般是本地訪問延遲的3倍以上單一內(nèi)存地址空間，所有這些內(nèi)存模塊都由硬件進行了統(tǒng)一編址，并通過互連網(wǎng)絡(luò)形成了并行機的共享存儲器,2024/3/27,并行計算基礎(chǔ)知識,16/66,DSM （續(xù)）,基于Cache的數(shù)據(jù)一致性DSM較好地改善了SMP的可擴展性能。一般地，DSM可以擴展到上百個節(jié)點，能提供每秒數(shù)千億次的浮點運算功能單一的系統(tǒng)映像，在DSM中，用戶只看

10、到一個操作系統(tǒng)，它可以根據(jù)各節(jié)點的負載情況，動態(tài)地分配進程,2024/3/27,并行計算基礎(chǔ)知識,17/66,DSM （續(xù)）,2024/3/27,并行計算基礎(chǔ)知識,18/66,機群（Cluster）,我國的曙光1000A、曙光2000、曙光3000以及前不久推出的曙光4000L等都是機群架構(gòu)的并行計算機Cluster的每個系統(tǒng)都是一個完整的工作站，一個節(jié)點可以是一臺PC或SMP各個節(jié)點一般由商品化的網(wǎng)絡(luò)互連，節(jié)點上的網(wǎng)絡(luò)接口是松散耦

11、合到I/O總線上的每個節(jié)點一般有本地磁盤，一個完整的操作系統(tǒng)駐留在每個節(jié)點上,2024/3/27,并行計算基礎(chǔ)知識,19/66,機群（Cluster）,2024/3/27,并行計算基礎(chǔ)知識,20/66,可擴展高性能機群服務(wù)器技術(shù),2024/3/27,并行計算基礎(chǔ)知識,21/66,單一系統(tǒng)映像,單一系統(tǒng)映像（Single System Image，SSI）并不是指系統(tǒng)中僅有唯一的操作系統(tǒng)映像駐留在內(nèi)存，而只是感覺上，像一個單一系統(tǒng)。其

12、基本特征是單一系統(tǒng)、單一控制、對稱性、位置透明。采用SSI的主要目的，是使機群的使用、控制和維護似乎和一臺工作站一樣。單一系統(tǒng)映像包括單一入口點、單一文件層次結(jié)構(gòu)、單一I/O空間、單一網(wǎng)絡(luò)、單一作業(yè)管理系統(tǒng)、單一存儲空間和單一進程空間。,2024/3/27,并行計算基礎(chǔ)知識,22/66,三種體系結(jié)構(gòu)比較（一）,2024/3/27,并行計算基礎(chǔ)知識,23/66,三種體系結(jié)構(gòu)比較（二）,2024/3/27,并行計算基礎(chǔ)知識,24/66,B

13、eowulf與機群,Beowulf：自己攢的“高性能計算機”買PC、網(wǎng)絡(luò)設(shè)備、裝linux、MPI、ATLAS降低了高性能計算門檻，促進了高性能計算普及迫切的問題：單一系統(tǒng)映像單一管理點單一文件系統(tǒng)單一作業(yè)管理負載自動均衡,2024/3/27,并行計算基礎(chǔ)知識,25/66,Beowulf：第一臺Hrothgar,2024/3/27,并行計算基礎(chǔ)知識,26/66,十年來CPU演變（1）,,2024/3/27,并行計算基礎(chǔ)知識

14、,27/66,十年來CPU演變（2）,,2024/3/27,并行計算基礎(chǔ)知識,28/66,十年來CPU演變（3）,,2024/3/27,并行計算基礎(chǔ)知識,29/66,十年來體系結(jié)構(gòu)的演變,,2024/3/27,并行計算基礎(chǔ)知識,30/66,機群：廠家面臨的問題,怎樣避免同質(zhì)化？一樣的CPU、一樣的網(wǎng)絡(luò)、一樣的操作系統(tǒng)、幾乎一樣的機群系統(tǒng)不一樣的用戶需求，一樣的系統(tǒng)能最優(yōu)滿足？SUMA標(biāo)準(zhǔn)Scalability可擴展性Usab

15、ility易用性Manageability可管理性Availability高可用性,2024/3/27,并行計算基礎(chǔ)知識,31/66,怎樣避免同質(zhì)化,應(yīng)用分類CPU密集、MEM密集、DISK密集、NIC密集針對不同應(yīng)用需求，提出不同的方案可重構(gòu)計算,2024/3/27,并行計算基礎(chǔ)知識,32/66,Intel與AMD,Opteron與32位兼容的64位處理器HyperTransportXeon主頻持續(xù)上升Ita

16、nium ？,2024/3/27,并行計算基礎(chǔ)知識,33/66,華大基因（北京）,Draft Sequence of Rice Genome,2024/3/27,并行計算基礎(chǔ)知識,34/66,曙光百萬億數(shù)據(jù)處理超級服務(wù)器,2024/3/27,并行計算基礎(chǔ)知識,35/66,4000L主要指標(biāo),40個機柜組成644個CPU每秒3萬億次浮點計算峰值速度644GB內(nèi)存百萬億字節(jié)（100TB）存儲最大可“在線”擴展到80個機柜130

17、0個CPU每秒6.75萬億次峰值速度4000G內(nèi)存600T存儲1200A最大電流，160千瓦最大功耗的海量處理系統(tǒng),2024/3/27,并行計算基礎(chǔ)知識,36/66,初步的面向網(wǎng)格的特點,Grid Terminal智能控制臺能夠?qū)崿F(xiàn)龐大系統(tǒng)的安全管理GridView網(wǎng)格監(jiān)控中心軟件則提供了邏輯視角、視角的可伸縮性、歷史記錄分析三項特色，被稱為系統(tǒng)的“千里眼”。,2024/3/27,并行計算基礎(chǔ)知識,37/66,中國近期的一些新

18、聞,曙光“紅色網(wǎng)格”孕育10萬億次超級計算機中科院網(wǎng)絡(luò)信息中心委托聯(lián)想研制高性能計算機系統(tǒng)高性能計算的“超級”對抗浪潮高性能計算 生命科學(xué)領(lǐng)域顯奇功高性能計算：處于什么樣的階段？,2024/3/27,并行計算基礎(chǔ)知識,38/66,HPC：處于什么樣的階段,機群高性能計算系統(tǒng)已經(jīng)成熟，步入量產(chǎn)階段國內(nèi)曙光、聯(lián)想、浪潮，還有大量小公司高性能計算應(yīng)用的快速擴展階段從去年開始，機群銷量猛增，應(yīng)用在科學(xué)計算和信息服務(wù)等所有領(lǐng)域高

19、性能計算教育相對滯后、人才相對稀缺階段北大、清華、科大等有限幾所高校設(shè)置相應(yīng)專業(yè)課程,2024/3/27,并行計算基礎(chǔ)知識,39/66,并行計算基本概念,并行算法的定義與分類并行算法的復(fù)雜性數(shù)據(jù)相關(guān)性與可并行化并行計算模型,2024/3/27,并行計算基礎(chǔ)知識,40/66,并行算法的定義與分類,算法是解題的精確描述，是一組有窮的規(guī)則，它規(guī)定了解決某一特定類型問題的一系列運算。并行計算時可同時求解的諸進程的集合，這些進程相互作用

20、和協(xié)調(diào)動作，并最終獲得問題的求解并行算法就是對并行計算過程的精確描述并行算法可以從不同的角度分類為數(shù)值計算并行算法和非數(shù)值計算并行算法同步并行算法和異步并行算法共享存儲并行算法和分布存儲并行算法,2024/3/27,并行計算基礎(chǔ)知識,41/66,數(shù)值算法與非數(shù)值算法,數(shù)值計算是指基于代數(shù)關(guān)系運算的計算問題，如矩陣運算、多項式求值、線性代數(shù)方程組求解等。求解數(shù)值計算問題的算法稱為數(shù)值算法（Numerical Algorithm

21、）?？茖W(xué)與工程中的計算問題如計算力學(xué)、計算物理、計算化學(xué)等一般是數(shù)值計算問題。非數(shù)值計算是指基于比較關(guān)系運算諸如排序、選擇、搜索、匹配等符號處理，相應(yīng)的算法也稱為非數(shù)值算法（Non-numerical Algorithm）。非數(shù)值計算在符號類信息處理中獲得廣泛應(yīng)用，如數(shù)據(jù)庫領(lǐng)域的計算問題、海量數(shù)據(jù)挖掘等，近年來廣泛關(guān)注的生物信息學(xué)主要也是非數(shù)值計算,2024/3/27,并行計算基礎(chǔ)知識,42/66,并行算法的復(fù)雜性,上界 f

22、(n)=cg(n)，則稱g(n)是f(n)的一個下界，記做f(n)=Ω(g(n))緊致界 c1g(n)<=f(n)<=c2g(n)，則稱g(n)是f(n)的一個緊致界，記做f(n)=Θ(g(n))。,2024/3/27,并行計算基礎(chǔ)知識,43/66,描述并行算法,如果要求輸入輸出N個數(shù)據(jù)，則認為該算法的I/O時間界為O(N)如果問題規(guī)模為n，涉及的計算量一般為t(n)，則該算法的計算CPU時間界為O(t(n)對要求通

23、信和同步的次數(shù)為L、通信量為M個數(shù)據(jù)，則該算法的并行開銷為O(L+M),2024/3/27,并行計算基礎(chǔ)知識,44/66,問題規(guī)模,問題規(guī)模有可分為輸入輸出規(guī)模、計算規(guī)模、內(nèi)存需求、通信（同步）規(guī)模，分別表示問題求解所需要的I/O量、計算量、內(nèi)存大小和通信量（包括通信次數(shù)與通信數(shù)據(jù)量）。根據(jù)消耗資源程度，又相應(yīng)分為CPU密集應(yīng)用、memory密集應(yīng)用、disk密集應(yīng)用和網(wǎng)絡(luò)密集應(yīng)用。不同類型的問題，性能瓶頸也往往不同。并行算法

24、就是要又針對性的消除相應(yīng)的瓶頸，從而達到縮短計算時間的目的。,2024/3/27,并行計算基礎(chǔ)知識,45/66,相關(guān)性與可并行化,伯恩斯坦準(zhǔn)則I1∩O2＝Φ，即P1的輸入變量集與P2的輸出變量集不相交；I2∩O1＝Φ，即P2的輸入變量集與P1的輸出變量集不相交；O1∩O2＝Φ，即P1和P2的輸出變量集不相交可并行處理,2024/3/27,并行計算基礎(chǔ)知識,46/66,數(shù)據(jù)相關(guān),P1： A＝B+CP2： D＝A×B

25、其中，變量A是導(dǎo)致P1和P2發(fā)生數(shù)據(jù)相關(guān)的原因。為了保證程序執(zhí)行的語義正確性，變量A必須是先在P1中寫入后方可從P2中讀出，即必須先寫后讀。顯然，P1和P2不能并行執(zhí)行。,2024/3/27,并行計算基礎(chǔ)知識,47/66,數(shù)據(jù)反相關(guān),P1： A＝B×CP2： C＝E+DP1通過變量C數(shù)據(jù)相關(guān)于P2。為保證語義正確性，必須等P1將變量C讀出后，P2方可向變量C進行寫入操作，即必須先讀后寫。也不可并行化,2024/3/2

26、7,并行計算基礎(chǔ)知識,48/66,數(shù)據(jù)輸出相關(guān),P1： A＝B+CP2： A＝D×E為保證語義正確性，必須保證P1先寫入A，然后允許P2再寫入A。除了上述3種相關(guān)外，還存在一種特殊情況，即兩個程序段的輸入變量互為輸出變量。此時，兩者必須并行執(zhí)行，方可保證語義的正確性。這就要求硬件機構(gòu)能保證兩者進行同步讀寫。但若兩個處理機各帶有局部存儲器，則可降低同步要求。,2024/3/27,并行計算基礎(chǔ)知識,49/66,并行計算模

27、型,計算模型是對計算機的抽象計算模型為設(shè)計、分析和評價算法提供基礎(chǔ)馮.偌依曼機就是一個理想的串行計算模型但現(xiàn)在還沒有一個通用的并行計算模型PRAM模型LogP模型,2024/3/27,并行計算基礎(chǔ)知識,50/66,PRAM模型,PRAM（Parallel Random Access Machine）模型，即并行隨機存取模型，是一種抽象的并行計算模型。假設(shè)存在著一個容量無限大的共享存儲器；每臺處理器有簡單的算術(shù)運算和邏輯判斷

28、功能；在任何時刻各處理器均可以通過共享存儲單元交換數(shù)據(jù)。,2024/3/27,并行計算基礎(chǔ)知識,51/66,PRAM模型,可分為SIMD-PRAM和MIMD-PRAM。SIMD-PRAM模型又可以細分為PRAM-EREW模型；PRAM-CREW模型；PRAM-CRCW模型。CPRAM-EREW模型；PPRAM-EREW模型APRAM-EREW模型。,2024/3/27,并行計算基礎(chǔ)知識,52/66,PRAM模型,SIMD

29、-PRAM計算模型 MIMD-PRAM計算模型,2024/3/27,并行計算基礎(chǔ)知識,53/66,LogP 模型,充分說明了互連網(wǎng)絡(luò)的性能特點，而未涉及網(wǎng)絡(luò)的結(jié)構(gòu)。模型主要由4個參數(shù)描述。L（Latency） 源處理機與目的處理機進行消息（一個或幾個字）通信所需要的等待或延遲時間的上限。o（overhead） 處理機準(zhǔn)備發(fā)送或準(zhǔn)備接受每個消息的時間開銷（包括操作系統(tǒng)核心開銷和網(wǎng)絡(luò)軟件開銷），在這段

30、時間里處理機不能執(zhí)行其他操作。g（gap） 一臺處理機連續(xù)兩次發(fā)送或連續(xù)兩次接受消息時的最小時間間隔，其倒數(shù)即為處理機的通信帶寬。P（Processor） 處理機的個數(shù)。,2024/3/27,并行計算基礎(chǔ)知識,54/66,LogP 模型,揭示了分布存儲并行計算機的性能瓶頸，用L、o、g三個參數(shù)刻畫了通信網(wǎng)絡(luò)的特性，但屏蔽了網(wǎng)絡(luò)拓撲、選路算法和通信協(xié)議等具體細節(jié)參數(shù)g反映了通信帶寬在任何時刻，最多只能有[L/g]條消息從一個處理

31、器傳到另一個處理器，這就是網(wǎng)絡(luò)容限，當(dāng)一臺處理機發(fā)送的消息達到這個容限時，在發(fā)送的消息就會被阻塞；在網(wǎng)絡(luò)容限范圍內(nèi)，點到點傳送一條消息的時間為（2*o+L）。設(shè)想LogP模型中的L、o、g都為0，那么LogP模型就等同于PRAM模型,2024/3/27,并行計算基礎(chǔ)知識,55/66,各種計算模型比較,2024/3/27,并行計算基礎(chǔ)知識,56/66,性能評價與benchmark,加速比定律與并行效率常見benchmark簡介,20

32、24/3/27,并行計算基礎(chǔ)知識,57/66,加速比定律,在給定的并行計算系統(tǒng)上給定的應(yīng)用，并行算法（并行程序）的執(zhí)行速度相對于串行算法（串行程序）加快的倍數(shù)，就是該并行算法（并行程序）的加速比。Amdahl定律適用于固定計算規(guī)模的加速比性能描述，Gustafson定律適用于可擴展問題,2024/3/27,并行計算基礎(chǔ)知識,58/66,Amdahl定律,S=(WS+WP)/(WS+WP/p) =1/(1/p+f(1-1/p)顯

33、然，當(dāng)p→∞時，S=1/f即對于固定規(guī)模的問題，并行系統(tǒng)所能達到的加速上限為1/f。假定并行計算系統(tǒng)的處理器數(shù)為p，W為問題規(guī)模，WS為應(yīng)用程序中的串行分量，W­P為可并行化部分；f為串行分量的比例（f=Ws/W），1-f為并行分量的比例；Ts=T1為串行執(zhí)行時間，Tp為并行計算時間；S為加速比，E為并行效率,2024/3/27,并行計算基礎(chǔ)知識,59/66,Gustafson定律,S‘=（WS+pwp）/（WS+WP）

34、 =p-f（p-1）=f+p（1-f）加速比與處理器數(shù)成斜率為（1-f）的線性關(guān)系這樣串行比例f就不再是程序擴展性的瓶頸，當(dāng)然，f越低，斜率會越大，加速性能越好。,2024/3/27,并行計算基礎(chǔ)知識,60/66,Linpack,由J. Dongarra編寫的Linpack采用主元高斯消去法求解雙精度(64bits)稠密線性代數(shù)方程組，結(jié)果按每秒浮點運算次數(shù)（flops）表示。包含三類測試，問題規(guī)模與優(yōu)化選擇各不相

35、同： 100×100測試 在該測試中，不允許對Linpack測試程序進行任何修改（包括注釋行）。 1000×1000測試 在該測試中，允許對算法和軟件進行修改或替換，并盡量利用系統(tǒng)的硬件特點，以達到盡可能高的性能。但是所有的優(yōu)化都必須保持和標(biāo)準(zhǔn)算法如高斯消去法相同的相對精度，而且必須使用Linpack的主程序進行調(diào)用。,2024/3/27,并行計算基礎(chǔ)知識,61/66,linpack,HPL測試 針對

36、大規(guī)模并行計算系統(tǒng)的測試，其名稱為High Performance Linpack (HPL)，1.0版于2000年9月發(fā)布，是第一個標(biāo)準(zhǔn)的公開版本并行Linpack測試軟件包，一般用于TOP500超級計算機上的并行超級計算機。HPL與其前輩不同，使用者可以改變問題規(guī)模。要獲得Linpack實測峰值，需要使用與內(nèi)存匹配的最大的問題規(guī)模（一般接近內(nèi)存總?cè)萘康?0%）。,2024/3/27,并行計算基礎(chǔ)知識,62/66,HPL測試,R

37、peak:系統(tǒng)的最大的理論峰值性能，按GFLOPS表示。Nmax: 給出達到最高GFLOPS值時的問題規(guī)模（矩陣規(guī)模）。Rmax: 在Nmax問題規(guī)模下，達到的最大峰值（GFLOPS）。 NB: 矩陣分塊大小，與高速緩存大小相關(guān)。一般在32到256之間。,2024/3/27,并行計算基礎(chǔ)知識,63/66,,,2024/3/27,并行計算基礎(chǔ)知識,64/66,NAS Parallel Benchmark,NPB套件由八個程序組成每

38、個基準(zhǔn)測試有五類：A、B、C、D、W (工作站)。A是最小的，D是最大的。NPB套件以每秒百萬次運算為單位輸出結(jié)果。整數(shù)排序(IS)快速Fourier變換（FT）多柵格基準(zhǔn)測試（MG） 共軛梯度(CG) 基準(zhǔn)測試 稀疏矩陣分解（LU） 五對角方程（SP）和塊狀三角(BT)求解 密集并行(EP),2024/3/27,并行計算基礎(chǔ)知識,65/66,參考文獻,黃鎧、徐志偉，《可擴展并行計算》，機械工業(yè)出版社，2000年陳國良