第二章加速比性能模型與可擴展性

1、第二章 加速比性能模型與可擴展性分析2.1 加速比性能分析2.1.1 一般概念2.1.2 加速比2.1.3 三種加速比性能模型2.2 可擴展性分析2.1 加速比性能模型2.1.1 一般概念1.處理機時間積處理機數(shù)目與處理時間的乘積用以度量這些處理機運行時的資源利用率。若一程序在P臺處理機上運行的時間為Tp，則此P臺處理機在Tp時間間隔內(nèi)完成的工作最大數(shù)量為Tp * P?？蓪⑻幚頇C實際工作曲線對時間的積分看成是這些處理機完成的有效工作量。效率為有效工作量與最大工作量之比。2.并行度（Degree Of ParallelismDOP）并行度（DOP）是在一定時間間隔內(nèi)執(zhí)行一個程序所用的處理機的數(shù)目

2、。3.并行性分布圖 執(zhí)行一個給定的程序時DOP對時間的分布圖。DOP與對應時間的間隔之積即為處理機要完成的工作或工作負載。 下圖所示為一個并行性分布圖。DOPt1tt2并行性分布圖2.1.2 加速比1. 絕對加速比將最好的串行算法與并行算法相比較. 定義一（與具體機器有關(guān)）將最好的串行算法在一臺上的運行時間與并行算法在N臺運行的時間相比。 定義二（與具體機器無關(guān)）將最好的串行算法在最快的順序機上的執(zhí)行時間與并行算法在并行機上的運行時間相比。T(N)TSbest2.相對加速比同一并行算法在單節(jié)點上運行時間與在多個相同節(jié)點構(gòu)成的處理機系統(tǒng)上的運行時間之比。這種定義側(cè)重于描述算法和并行計算機本身的可

3、擴展性。)()1(NTTS 線性加速比：中間開銷小，通信少，弱耦合計算超線性加速比：當應用需要大內(nèi)存時可能出現(xiàn)病態(tài)加速比：加速比遞減，可能是計算量太小2.1.3 三種加速比性能模型1.固定負載加速比性能模型Amdahl定律在許多實時應用領(lǐng)域，計算負載的大小常固定。在并行機中，此負載可分布至多臺并行執(zhí)行，獲得的加速比稱為fixed-load speedup。一個問題的負載可表示如下：W = Ws + Wp其中，Ws代表問題中不可并行化的串行部分負載， Wp表示可并行化的部分負載。 則n個節(jié)點情況下，加速比可以表示如下：nWpWsWpWsSn/設(shè)串行因子為串行部分所占的比例。即WpWsWpWpWs

4、Ws1或nWpWsnWpWpWsWsWpWsWpWsSn/)1(1/代入即得Amdahllaw：不管采用多少處理機，可望達到的最好加速比：1/)1(1limnSnn效率En可以表示為：)1(1111/)1(1nnnnnSnEn處理機數(shù)目n越大，效率En越低。Amdahl定律告訴我們：系統(tǒng)中某一部件由于采用某種更快的執(zhí)行方式后整個系統(tǒng)性能的提高與這種執(zhí)行方式的使用頻率或占總執(zhí)行時間的比例有關(guān)。任務的時間采用改進措施后執(zhí)行某行某任務的時間沒有采用改進措施前執(zhí)性能沒有采用改進措施前的采用改進措施后的性能加速比加速比的兩個決定因素：1.計算機執(zhí)行某個任務的總時間中可被改進部分的時間所占的百分比，即可被

5、改進部分占用時間/改進前整個任務的執(zhí)行時間，記為Fe，它總小于1。2.改進部分采用改進措施后比沒有采用改進措施前性能提高的倍數(shù)，即改進前改進部分執(zhí)行時間/改進后改進部分執(zhí)行時間，記為Se。SeFeFeS)1(1例1：假設(shè)將某系統(tǒng)的某一部件的處理速度加快到10倍，但該部件的原處理時間僅為整個運行時間的40%，則整個系統(tǒng)的性能提高了多少？解：Fe = 0.4，Se = 10，56.1104.0)4.01(1 S例2：采用哪種實現(xiàn)技術(shù)來求浮點數(shù)平方根FPSQR的操作對系統(tǒng)的性能影響較大。假設(shè)FPSQR操作占整個測試程序執(zhí)行時間的20%。一種實現(xiàn)方法是采用FPSQR硬件，使FPSQR操作的速度加快到1

6、0倍。另一種方法是使所有浮點數(shù)據(jù)指令的速度加快，使FP指令的速度加快到2倍，還假設(shè)FP指令占整個執(zhí)行時間的50%。請比較這兩種設(shè)計方案。解：Fe_FPSQR = 0.2，Se_FPSQR = 10， Fe_FP = 0.5，Se_FP = 2，22.1102.0)2.01(1FPSQRS33.125.0)5.01(1FPSAmdahllaw又稱為固定規(guī)模加速比模型，問題規(guī)模不隨處理機變化而變化。固定問題規(guī)模，看用并行技術(shù)能達到的最短時間是多少。在固定規(guī)模加速比模型下，負載和執(zhí)行時間隨系統(tǒng)中處理機數(shù)目n變化的情況如下圖：WsWpWsWpWsWpWsWpWorkloadN1234Execution

7、 TimeNTsTp1TsTp2TsTp3TsTp4固定負載執(zhí)行時間隨N增加而減少固定負載加速比模型下的負載和執(zhí)行時間情況當處理器數(shù)目n=1024，加速比Sn隨變化的情況如下：102311024)11024(110241024S得出曲線如下圖：00.010.020.030.040.050.060.070.080.090.102004006008001000120091Sn102448312410可以比較不同的對加速比帶來的不同影響：100101102103104100101102103104 =0Snn =0.01 =0.1 =0.9=0時得到理想加速比，當值增加時，加速比性能急劇下降。結(jié)論：

8、加速比曲線隨的上升急劇下降，原因是存在順序部分Ws，無法用增加系統(tǒng)的處理機數(shù)目來解決。這一性質(zhì)在過去二十年間給人們造成了對并行處理非常悲觀的印象。影響：兩種意見： 1.勸阻制造商生產(chǎn)大規(guī)模并行計算機。 2.研究并行編譯器，以降低的值，從而提高系統(tǒng)的性能。規(guī)定負載加速比模型的可能應用范圍： 對時間要求嚴格的應用問題。2.固定時間加速比性能模型Gustafsun定律有許多應用領(lǐng)域強調(diào)精度而不時運行時間。1988年，Gustafsun提出了固定時間加速比模型。當機器的規(guī)模擴大時，解題的規(guī)模也隨著擴大，從而得到更加精確的解，而使運行時間保持不變。比如：有限元方法做結(jié)構(gòu)分析，流體動力學做天氣預報解PDE

9、(偏微分方程組)就需要提高精度。粗格要求的計算量較少，而細格的計算量多，得到的精確度也較高。天氣預報模擬求解四維PDE，如果使每個實際方向（X，Y，Z）的格點距離減少10倍，并以同一幅度增加時間步，那么可以說格點增加了104倍，因而工作負載也至少增大了10000倍。模型提出的背景：固定負載模型有缺陷：因為Amdahllaw中，取決于問題及并行編譯器的效率，無法描述系統(tǒng)固有的特性。加速比的公式：) 1()1 ()1 (/ nnnWpWsnWpWsnWpWsWpWsSn其中，Wp=nWp和Ws+Wp=Ws+Wp/n作為固定時間的條件。 Ws+Wp/n表示在擴大負載后在增加處理機臺數(shù)的情況下的平均負

10、載（執(zhí)行時間），它應當和負載沒有擴大情況下的平均負載（執(zhí)行時間）Ws+Wp相等。即有Ws+Wp=Ws+Wp/n。同時，負載的串行部分并沒有改變，即有Ws=Ws。在固定時間加速比模型下，負載和執(zhí)行時間隨系統(tǒng)中處理機數(shù)目n變化的情況如下圖：WsWpWsWpWsWpWsWpWorkloadN1234Execution TimeNTsTp1TsTp2TsTp3TsTp4并行負載不斷增加執(zhí)行時間固定固定時間加速比模型下的負載和執(zhí)行時間情況00.010.020.030.040.050.060.070.080.090.180085090095010001050110010231024)1(1024nnS增大

11、問題規(guī)模的辦法使所有處理機保持忙碌狀態(tài)，在問題擴大到與可用的計算能力匹配時，程序中的順序部分就不再是瓶頸了。當處理器數(shù)目n=1024，加速比Sn隨變化的情況如下：Sn1024101410049939833.受限于存儲器的加速比模型1993年，由Sun和Ni提出。大型科學計算和工程設(shè)計需要較大的存儲空間，許多應用問題是存儲器受限，而不是CPU受限或者I/O受限。比如：在分布存儲系統(tǒng)中常遇到，總存儲容量隨節(jié)點數(shù)線性增加，許多節(jié)點集合起來解一個大題?；舅枷耄阂诖鎯臻g有限條件下解盡可能大的問題，這同樣需要擴展工作負載，才能提供較高的加速比、較高的精度和較好的資源利用率。加速比可以表示如下：nWp

12、nGWsWpnGWsnWWWWSpspsn/)()(/*sWWsWs其中：在單個處理機上順序執(zhí)行的工作負載與問題的規(guī)?；蛳到y(tǒng)的規(guī)模無關(guān)，即：而G(n)反映的是存儲容量增加n倍時并行工作負載增加的倍數(shù)。nnnSSS*討論：1.G(n) = 1，即為固定負載的情況；2.G(n) = n，即存儲器增加n倍，負載也增加n倍，為固定時間的情形；3.G(n) n，計算負載的增加情況比存儲器增加快，會有較高的加速比。比較三種加速比，對于相同的處理機數(shù)量，有：在受限于存儲器的加速比模型下，負載和執(zhí)行時間隨系統(tǒng)中處理機數(shù)目n變化的情況如下圖：WsWpWsWpWsWpWsWpWorkloadN1234Execut

13、ion TimeNTsTp1TsTp2TsTp3TsTp4規(guī)模擴展的工作負載執(zhí)行時間稍有增加受限于存儲器的加速比模型下的負載和執(zhí)行時間情況例：n維矩陣乘法：A * B = C，其中A、B、C都是n*n的方陣。為得到C的每一個元素需要進行n次乘法、n次加法，所以總的計算量為：（n+n)*n2 = 2n3。需要的存儲量為3n2（兩個源矩陣，一個結(jié)果矩陣）。如果n臺計算機組成多計算機系統(tǒng)，則存儲容量擴大n倍，那么矩陣的維數(shù)（原來為n)也可以增加了，設(shè)為N倍，那么加速比為多少？ 解：存儲容量變?yōu)椋簄M = n* 3n2 = 3n3，而N維需要的存儲量為3N2，計算量變?yōu)?N3，則有：5.12333nN

14、NnpspspspsWnWWnWnWnWWnWS5.0*/5.135.433*2222)(nnnnNWWnG原來擴大后01002003004005006007008009001000010020030040050060070080090010004.并行計算的應用模型隨機器規(guī)模的增大，工作負載增長的模式如下圖：工作負載（問題規(guī)模）n（指數(shù)）（線性）（亞線性）（常數(shù)）上圖中：采用受限于存儲器的加速比模型中給出的公式，曲線對應的G(n) = n1.5曲線對應的G(n) = n曲線對應的G(n) = 0.5n曲線對應的G(n) = 1則有加速比公式:nWpnGWsWpnGWsSn/

15、)()(*給定一個程序，假設(shè)Ws/Wp = 0.4，那么效率為：nSEn*0100200300400500600700800900100001相應的處理器數(shù)目效率曲線如下圖：效率n（指數(shù)）（線性）（亞線性）（常數(shù)）結(jié)論：1.如果工作負載（問題規(guī)模）保持不變，那么效率E隨機器規(guī)模的增大而迅速下降，其原因是開銷h比機器規(guī)模增加得快，為了使效率保持在一定的水平上，我們可以按比例增大機器規(guī)模和問題規(guī)模。2.如果工作負載按指數(shù)增長模式，效率要保持恒定或保持良好的加速比，必須使問題規(guī)模猛增才行，這樣就會超過存儲器或I/O限制，而問題規(guī)模只允許在計算機存

16、儲器可用的限度以內(nèi)增長。并行計算機的應用模型如下圖：通信界限 存儲器界限受限于存儲器模型工作負載（問題規(guī)模）機器規(guī)模固定負載模型固定時間模型第二章 加速比性能模型與可擴展性分析2.1 加速比性能分析2.2 可擴展性分析2.2.1 可擴展性2.2.2 可擴展性分析2.2 可擴展性分析2.2.1 可擴展性1.可擴展性與可編程性增加可擴展性增加可編程性分布存儲的消息傳遞型多計算機共享存儲型多處理機理想并行計算機2.可擴展性指標機器規(guī)模（n）時鐘頻率（f）問題規(guī)模（s）CPU時間（T）I/O需求（d）存儲容量（m）通信開銷（h）計算機價格（c）程序設(shè)計開銷（p）3.可擴展性的直觀定義對任意數(shù)量（n）的

17、處理機和任意規(guī)模（s）的問題，若所有算法的系統(tǒng)效率 E = 1， 則系統(tǒng)是可擴展的。4.規(guī)?？蓴U展性系統(tǒng)性能隨處理機數(shù)量線性增長，包括：處理速度和效率存儲速度和容量互連帶寬和時延I/O速度和容量軟件開銷規(guī)?？蓴U展性與空間局部性、時間局部性以及部件瓶頸都有關(guān)系。例子：Cray Y-MP：16臺處理機范圍可伸縮CM-2：8K-64K臺處理機范圍可伸縮CM-5：1024-16K臺處理機范圍可伸縮KSR-1：8-1088臺處理機范圍可伸縮5.換代（時間）可擴展性對系統(tǒng)各部分更換成新技術(shù)后，性能隨之易擴展，要求算法、S/W均能兼容運行。6.問題可擴展性問題規(guī)模擴大時，系統(tǒng)仍能很好的運行，或說問題規(guī)模擴展

18、到很大時，系統(tǒng)能在給定粒度下高效運行。2.2.2 可擴展性1.恒等效率概念（Isoefficiency）恒等效率定義為一個并行算法在并行計算機上實現(xiàn)時，為保持效率E固定所需的工作負載與機器規(guī)模n的相對關(guān)系。設(shè):W = W（s）為工作負載， h = h （s，n）為通信開銷，它隨s、n增加而增大。其中，s為問題規(guī)模，n為機器規(guī)模。則效率可以表示為：),()()(nshsWsWE 問題的關(guān)鍵在于W（s）與h（s，n）之間的相對增長速度。機器規(guī)模一定，開銷h的增長比工作負載W要慢。因而，對一定規(guī)模的機器來說，效率會隨問題規(guī)模增大而提高。所以，假若工作負載W隨機器規(guī)模適當增加，那么就有希望保持效率不變

19、。 對于已知的算法來說，為了保持恒定的效率，工作負載W可能需要對n以多項式或指數(shù)規(guī)律增長。不同的算法可能需要不同的工作負載增長速率以便在n增加時保持效率不致下降。 一般并行算法的恒定效率函數(shù)是n的多項式函數(shù)，即它們?yōu)镺（nk），k 1。n的冪越小，并行系統(tǒng)的可擴展性越大（系統(tǒng)包括算法和結(jié)構(gòu)的組合）。2.恒等效率函數(shù)并行程序執(zhí)行時間 Tp = (T1+T0)/p，其中，T1為總工作負載串行執(zhí)行時間，T0為多節(jié)點總通信延時，p為節(jié)點數(shù)。那么，加速比為：pTTS1而T1 = W tc，W為以操作次數(shù)計算的總工作負載，tc為每個操作的平均執(zhí)行時間。10011111TTTTTpTTpSEp的函數(shù)）與工作

20、負載是節(jié)點數(shù)可得為常數(shù)為定值W()1(1)1(1)1(1100000pTKTWEEtETEEtWEEtWTWtTEcccc如前面所述，工作負載W與開銷h均可以表示成n與s的函數(shù)，所以，效率也可以表示如下：)(/),(11sWnshE為了使E保持不變，工作負載W（s）應該與開銷h(s,n)成比例增長，由此可以得出以下條件：),()(1),(1)(nshCnfCEEnshEEsWE為：表示，則恒等效率函數(shù)為常數(shù)，用如果工作負載W(s)與fE(n)一樣快的增長，那么已知算法結(jié)構(gòu)組合就能使效率保持恒定。這個結(jié)論和前面的結(jié)論是一致的。此時， W(s)與fE(n)是相同的，只要求出了W(s)的數(shù)量級，就可

21、知道fE(n)了。為了得到恒等效率，只要使W(s)與h(s,n)同一個數(shù)量級就可以了。例1：矩陣乘法的W(s) = O（s3）（其中s為維數(shù)），還設(shè)h（s，n）= O（nlogn+s2n0.5）。求fE(n) 。 解：)()()()()()()log()()log()()()(5.1323323nOsOnOsOnsOsOnnOsOnsnnOsOshsW或者即要滿足W與h同數(shù)量級的條件，需要在兩式中選出大的：)()()()(5 . 15 . 13nOnfnOsOE例2：W(s) = O（s3），h（s，n）= O（nlogn+s2n1/3logn）。求fE(n) 。 解：)(log()()log(