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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

24、就是要又針對(duì)性的消除相應(yīng)的瓶頸，從而達(dá)到縮短計(jì)算時(shí)間的目的。,2024/3/27,并行計(jì)算基礎(chǔ)知識(shí),45/66,相關(guān)性與可并行化,伯恩斯坦準(zhǔn)則I1∩O2＝Φ，即P1的輸入變量集與P2的輸出變量集不相交；I2∩O1＝Φ，即P2的輸入變量集與P1的輸出變量集不相交；O1∩O2＝Φ，即P1和P2的輸出變量集不相交可并行處理,2024/3/27,并行計(jì)算基礎(chǔ)知識(shí),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í)行的語(yǔ)義正確性，變量A必須是先在P1中寫入后方可從P2中讀出，即必須先寫后讀。顯然，P1和P2不能并行執(zhí)行。,2024/3/27,并行計(jì)算基礎(chǔ)知識(shí),47/66,數(shù)據(jù)反相關(guān),P1： A＝B×CP2： C＝E+DP1通過(guò)變量C數(shù)據(jù)相關(guān)于P2。為保證語(yǔ)義正確性，必須等P1將變量C讀出后，P2方可向變量C進(jìn)行寫入操作，即必須先讀后寫。也不可并行化,2024/3/2

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

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

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

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

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

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

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

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

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

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

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

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

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