第二章加速比性能模型與可擴(kuò)展性分析

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

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

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

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

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

6、0倍。另一種方法是使所有浮點(diǎn)數(shù)據(jù)指令的速度加快，使FP指令的速度加快到2倍，還假設(shè)FP指令占整個(gè)執(zhí)行時(shí)間的50%。請(qǐng)比較這兩種設(shè)計(jì)方案。解：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ī)模加速比模型，問(wèn)題規(guī)模不隨處理機(jī)變化而變化。固定問(wèn)題規(guī)模，看用并行技術(shù)能達(dá)到的最短時(shí)間是多少。在固定規(guī)模加速比模型下，負(fù)載和執(zhí)行時(shí)間隨系統(tǒng)中處理機(jī)數(shù)目n變化的情況如下圖：WsWpWsWpWsWpWsWpWorkloadN1234Execution

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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