高性能計(jì)算導(dǎo)論：并行計(jì)算性能評(píng)價(jià)1

《高性能計(jì)算導(dǎo)論：并行計(jì)算性能評(píng)價(jià)1》由會(huì)員分享，可在線閱讀，更多相關(guān)《高性能計(jì)算導(dǎo)論：并行計(jì)算性能評(píng)價(jià)1（48頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、Click to edit Master title style,,Click to Edit Master Text Styles Asd Gasd Glak Fdas Af Lkajds Laksdjf Hasldkf Asdkj H,,Second Level Asdf Ias;df Has;dlf As;df Asd Fasdf Asdf Asd Af Sdfs Fdsasdf Sa,,Third Level,,Fourth Level,,Fifth Level,,,并行計(jì)算性能評(píng)價(jià),上海大學(xué)計(jì)算機(jī)工程與科學(xué)學(xué)院,,計(jì)算的本質(zhì),,串行計(jì)算模型,—,圖靈機(jī),,并行計(jì)算模型,,,計(jì)算效

2、能評(píng)價(jià),計(jì)算模型與效能評(píng)價(jià),高性能計(jì)算導(dǎo)論,“并行計(jì)算”研究的四大分支,并行計(jì)算機(jī),體系結(jié)構(gòu),,并行,算法,,并行,程序設(shè)計(jì),,并行計(jì)算的,性能評(píng)測(cè),,,而介于并行計(jì)算機(jī),體系結(jié)構(gòu),與并行,算法,之間的是并行,計(jì)算模型,。,,,Performance Evaluation,并行計(jì)算效能評(píng)價(jià),,,程序性能評(píng)價(jià)與優(yōu)化,給定并行算法，采用并行程序設(shè)計(jì)平臺(tái)，通過(guò)并行實(shí)現(xiàn)獲得實(shí)際可運(yùn)行的并行程序后，一個(gè)重要的工作就是，在并行機(jī)上運(yùn)行該程序，評(píng)價(jià)該程序的實(shí)際性能，,揭示性能瓶頸，指導(dǎo)程序的性能優(yōu)化,。,,性能評(píng)價(jià)和優(yōu)化是設(shè)計(jì)高效率并行程序必不可少的重要工作。,并行程序執(zhí)行時(shí)間,評(píng)價(jià)并行程序的性能之前，必須

3、清楚并行程序的執(zhí)行時(shí)間是由哪些部分組成的。眾所周知，獨(dú)享處理器資源時(shí)，串行程序的執(zhí)行時(shí)間近似等于程序指令執(zhí)行花費(fèi)的,CPU,時(shí)間。但是，并行程序相對(duì)復(fù)雜，其,執(zhí)行時(shí)間（,execution time,）等于從并行程序開(kāi)始執(zhí)行，到所有進(jìn)程執(zhí)行完畢，墻上時(shí)鐘走過(guò)的時(shí)間,，也稱(chēng)之為,墻上時(shí)間,（,wall time,）。,,對(duì)各個(gè)進(jìn)程，墻上時(shí)間可進(jìn)一步分解為：,,計(jì)算,CPU,時(shí)間,,通信,CPU,時(shí)間,,同步開(kāi)銷(xiāo)時(shí)間,,進(jìn)程空閑時(shí)間,（是由同步導(dǎo)致的）,,并行程序執(zhí)行時(shí)間,計(jì)算,CPU,時(shí)間,,進(jìn)程指令執(zhí)行所花費(fèi)的,CPU,時(shí)間，它可以分解為兩個(gè)部分，一個(gè)是程序本身指令執(zhí)行占用的,CPU,時(shí)間，即

4、通常所說(shuō)的用戶(hù)時(shí)間（,user time,），主要包含指令在,CPU,內(nèi)部的執(zhí)行時(shí)間和內(nèi)存訪問(wèn)時(shí)間，另一個(gè)是為了維護(hù)程序的執(zhí)行，操作系統(tǒng)花費(fèi)的,CPU,時(shí)間，即通常所說(shuō)的系統(tǒng)時(shí)間（,system time,），主要包含內(nèi)存調(diào)度和管理開(kāi)銷(xiāo)、,I/O,時(shí)間、以及維護(hù)程序執(zhí)行所必需要的操作系統(tǒng)開(kāi)銷(xiāo)等。通常地，系統(tǒng)時(shí)間可以忽略。,并行程序執(zhí)行時(shí)間,通信,CPU,時(shí)間,,,包含進(jìn)程通信花費(fèi)的,CPU,時(shí)間。,,同步開(kāi)銷(xiāo)時(shí)間,,,包含進(jìn)程同步花費(fèi)的時(shí)間,,進(jìn)程空閑時(shí)間,,,當(dāng)一個(gè)進(jìn)程阻塞式等待其他進(jìn)程的消息時(shí)，,CPU,通常是空閑的，或者處于等待狀態(tài)。進(jìn)程空閑時(shí)間是指并行程序執(zhí)行過(guò)程中，進(jìn)程所有這些空閑時(shí)

5、間的總和。,,顯然，進(jìn)程的計(jì)算,CPU,時(shí)間小于并行程序的墻上時(shí)間，而并行程序的,墻上時(shí)間,才是用戶(hù)真正關(guān)心的時(shí)間，是評(píng)價(jià)一個(gè)并行程序執(zhí)行速度的時(shí)間。,9/30/2024,9,/59,并行算法設(shè)計(jì)及效能分析,并行算法效能分析,并行加速比,并行效率,可擴(kuò)展性,（簡(jiǎn)單表述）,,處理機(jī)數(shù),p,增加時(shí)，并行效率,E,p,不顯著下降。,效能分析分析說(shuō)明,需要說(shuō)明的是，,T,1,指處理器個(gè)數(shù)為,1,時(shí)，并行程序的執(zhí)行時(shí)間。通常情形下，,T,1,大于,TS,，因?yàn)椴⑿谐绦蛲胍恍┤哂嗟目刂坪凸芾黹_(kāi)銷(xiāo)。,,加速比和效率是衡量一個(gè)并行程序性能的最基本的評(píng)價(jià)方法。顯然，執(zhí)行最慢的進(jìn)程將決定并行程序的性能。,,

6、在以上加速比和效率的定義中，有一個(gè)基本的假設(shè)，要求并行機(jī)的各個(gè)處理器是同構(gòu),(homogeneous),的，即并行機(jī)各個(gè)處理器的結(jié)構(gòu)完全一致（包含,CPU,類(lèi)型、內(nèi)存大小與性能、,cache,特征等等），或者說(shuō)，串行程序在各個(gè)處理器執(zhí)行的墻上時(shí)間相等。,效能分析分析說(shuō)明,如果并行機(jī)的各個(gè)處理器功能不一致，稱(chēng)之為異構(gòu)并行機(jī)。對(duì)此，以上加速比和效率的定義不是很合適。其中，兩個(gè)突出的問(wèn)題就是，串行程序的執(zhí)行時(shí)間是選擇最快的處理器運(yùn)行，還是選擇最慢的處理器運(yùn)行？在效率定義中，處理器個(gè)數(shù)選擇為,P,是否合適？一個(gè)比較好的方法就是，將所有處理器以最快的處理器為基準(zhǔn)，進(jìn)行歸一化處理。,,并行程序性能評(píng)價(jià)方法

7、,以上介紹的加速比和效率，只能反映并行程序的整體執(zhí)行性能，但是，無(wú)法反映并行程序的性能瓶頸。性能評(píng)價(jià)的主要目的在于，揭示并行程序的性能瓶頸，指導(dǎo)并行程序的性能優(yōu)化。因此，有必要進(jìn)一步分解加速比和效率，提出更細(xì)致的性能評(píng)價(jià)方法。,,并行計(jì)算性能評(píng)測(cè),3.1,并行機(jī)的一些基本性能指標(biāo),,3.2,加速比性能定律,,3.2.1,Amdahl,定律,,3.2.2,Gustafson,定律,,3.2.3,Sun,和,Ni,定律,,3.3,可擴(kuò)放性評(píng)測(cè)標(biāo)準(zhǔn),,3.3.1,并行計(jì)算的可擴(kuò)放性,,3.3.2,等效率度量標(biāo)準(zhǔn),,3.3.3,等速度度量標(biāo)準(zhǔn),,3.3.4,平均延遲度量標(biāo)準(zhǔn),,,﹡ 3.4,基準(zhǔn)測(cè)試程

8、序,并行計(jì)算的性能評(píng)測(cè),機(jī)器級(jí),的性能評(píng)測(cè),,CPU,和存儲(chǔ)器的某些基本性能指標(biāo),,并行通信開(kāi)銷(xiāo),,機(jī)器的成本、價(jià)格、和性能,/,價(jià)格比等,,算法級(jí),的性能評(píng)測(cè),,加速比,,效率,,可擴(kuò)展性,,程序級(jí),的性能評(píng)測(cè),,基本測(cè)試程序,,數(shù)學(xué)庫(kù)測(cè)試,,并行測(cè)試程序等,并行機(jī)基本性能參數(shù)一覽表,名稱(chēng),符號(hào),含義,單位,機(jī)器規(guī)模,n,處理器的數(shù)目,無(wú)量綱,時(shí)鐘速率,f,時(shí)鐘周期長(zhǎng)度的倒數(shù),MHz,工作負(fù)載,W,計(jì)算操作的數(shù)目,Mflops,順序執(zhí)行時(shí)間,T,1,程序在單處理機(jī)上的運(yùn)行時(shí)間,s,并行執(zhí)行時(shí)間,T,n,程序在并行機(jī)上的運(yùn)行時(shí)間,s,速度,R,n,=W/T,n,每秒百萬(wàn)次浮點(diǎn)運(yùn)算,Mflops

9、,加速,S,n,=T1/T,n,衡量并行機(jī)有多快,無(wú)量綱,效率,E,n,=S,n,/n,衡量處理器的利用率,無(wú)量綱,峰值速度,R,peak,=nR,’,peak,所有處理器峰值,(R,’,peak,),速度之積,Mflops,利用率,U=R,n,/R,peak,可達(dá)速度與峰值速度之比,無(wú)量綱,通信延遲,t,0,傳送,0,個(gè)字節(jié)或單字的時(shí)間,us,漸近帶寬,r,∞,傳送長(zhǎng)消息通信速率,MB/,s,工作負(fù)載,工作負(fù)載（荷）：計(jì)算操作數(shù)目,,執(zhí)行時(shí)間,—,掠過(guò)時(shí)間：墻上時(shí)間,,所執(zhí)行的指令數(shù)目,,所完成的浮點(diǎn)運(yùn)算數(shù),CPU,的某些基本性能指標(biāo),工作負(fù)載,,執(zhí)行時(shí)間,:,程序從開(kāi)始到結(jié)束的時(shí)間。,,浮

10、點(diǎn)運(yùn)算數(shù),,指令數(shù)目 ：通常用百萬(wàn)條指令,,,并行執(zhí)行時(shí)間,T,n,,：,T,,comput,,為計(jì)算時(shí)間，,T,paro,,為并行開(kāi)銷(xiāo)時(shí)間，,T,comm,為相互通信時(shí)間,,,,,T,n,= T,,comput,+ T,,paro,+ T,,comm,,,,,例：估計(jì),APRAM,模型下執(zhí)行時(shí)間,,,,,其中,T,1,為串行時(shí)間，,n,為處理器數(shù)，,T,∞,為使用無(wú)限多處理器且不考慮,T,,paro,與,T,,comm,,的并行執(zhí)行時(shí)間,存儲(chǔ)器性能,存儲(chǔ)器的層次結(jié)構(gòu),(C, L, B),,-----,容量,C,，延遲,L,，帶寬,B,,,,,,,估計(jì)存儲(chǔ)器的帶寬,,RISC,指令,add r

11、1,r2,r3,，寄存器,,8bytes,，主頻,100MHz,,B = 3*8*100*10,6,B/s= 2.4GB/s,并行與通信開(kāi)銷(xiāo),并行和通信開(kāi)銷(xiāo)：相對(duì)于計(jì)算很大。,,PowerPC (,每個(gè)周期,15ns,執(zhí)行,4flops;,創(chuàng)建一個(gè)進(jìn)程,1.4ms,可執(zhí)行,372000flops),,開(kāi)銷(xiāo)的測(cè)量：乒,--,乓方法（,Ping-Pong Scheme,）,節(jié)點(diǎn),0,發(fā)送,m,個(gè)字節(jié)給節(jié)點(diǎn),1,；節(jié)點(diǎn),1,從節(jié)點(diǎn),0,接收,m,個(gè)字節(jié)后，立即將消息發(fā)回節(jié)點(diǎn),0,?？偟臅r(shí)間除以,2,，即可得到點(diǎn)到點(diǎn)通信時(shí)間，也就是執(zhí)行單一發(fā)送或接收操作的時(shí)間。,,可一般化為熱土豆法（,Hot-Po

12、tato,），,也稱(chēng)為救火隊(duì)法（,Fire-Brigade) 0——1 —— 2 —— … —— n-1 —— 0,即從節(jié)點(diǎn),0,發(fā)送,m,字節(jié)給,1,，節(jié)點(diǎn),1,給節(jié)點(diǎn),2,，依次類(lèi)推，最后節(jié)點(diǎn),n-1,再將其返回給,0,，最后時(shí)間再除以,n,即可。,Ping-Pong Scheme,if,（,my _node _id =0,）,then /*,發(fā)送者*,/,,start _time =second,（ ）,,,send an m-byte message to node,1 //,發(fā)送,,,receive an m-byte message from node,

13、1 //,接收,,,end_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 message to node 0,,,endif,并行開(kāi)銷(xiāo)的表達(dá)式：點(diǎn)到點(diǎn)通信,通信開(kāi)銷(xiāo),,t,(,m,) =,t,0,+,m,/,r,∞,,通信啟動(dòng)時(shí)間,t,0,,漸近,帶寬,r

14、,∞,,：,傳送無(wú)限長(zhǎng)的消息時(shí)的通信速率,,m,為傳輸?shù)淖止?jié)數(shù),,,半,峰值長(zhǎng)度,m,1/2,：達(dá)到一半漸近帶寬所要的消息長(zhǎng)度,,特定性能,π,0,：表示短消息帶寬,,,t,0,= m,1/2,/,,r,∞,= 1 /,π,0,并行開(kāi)銷(xiāo)的表達(dá)式：組通信,典型的組通信有：,,播送,（,Broadcasting,）：,處理器,0,發(fā)送,m,個(gè)字節(jié)給所有的,n,個(gè)處理器,----,廣播,,收集,（,Gather,）：,處理,0,接收所有,n,個(gè)處理器發(fā)來(lái)在消息，所以處理器,0,最終接收了,m,x,n,個(gè)字節(jié)；,,散射,（,Scatter,）：,處理器,0,發(fā)送了,m,個(gè)字節(jié)的不同消息給所有,n,個(gè)處

15、理器，因此處理器,0,最終發(fā)送了,m,x,n,個(gè)字節(jié)；,,全交換,（,Total Exchange,）：,每個(gè)處理器均彼此相互發(fā)送,m,個(gè)字節(jié)的不同消息給對(duì)方，所以總通信量為,m,x,n,2,個(gè)字節(jié)；,,循環(huán)移位,（,Circular-shift,）：,處理器,i,發(fā)送,m,個(gè)字節(jié)給處理器,i+1,，,處理器,n-1,發(fā)送,m,個(gè)字節(jié)給處理器,0,，所以通信量為,m,x,n,個(gè)字節(jié)。,機(jī)器的成本、價(jià)格與性,/,價(jià)比,機(jī)器的成本與價(jià)格,,機(jī)器的性能,/,價(jià)格比,Performance/Cost Ratio,：,系指用單位代價(jià)（通常以百萬(wàn)美元表示）所獲取的性能（通常以,MIPS,或,MFLOPS,

16、表示）,,利用率（,Utilization,）：,可達(dá)到的速度與峰值速度之比,并行計(jì)算性能評(píng)測(cè),3.1,并行機(jī)的一些基本性能指標(biāo),,3.2,加速比性能定律,,3.2.1,Amdahl,定律,,3.2.2,Gustafson,定律,,3.2.3,Sun,和,Ni,定律,,3.3,可擴(kuò)放性評(píng)測(cè)標(biāo)準(zhǔn),,3.3.1,并行計(jì)算的可擴(kuò)放性,,3.3.2,等效率度量標(biāo)準(zhǔn),,3.3.3,等速度度量標(biāo)準(zhǔn),,3.3.4,平均延遲度量標(biāo)準(zhǔn),,,﹡ 3.4,基準(zhǔn)測(cè)試程序,算法級(jí)性能評(píng)測(cè),加速比性能定律,,并行系統(tǒng)的加速比是指對(duì)于一個(gè)給定的應(yīng)用，并行算法（或并行程序）的執(zhí)行速度相對(duì)于串行算法（或串行程序）的執(zhí)行速度加快

17、了多少倍。,,Amdahl,定律,,Gustafson,定律,,Sun Ni,定律,,可擴(kuò)放性評(píng)測(cè)標(biāo)準(zhǔn),,等效率度量標(biāo)準(zhǔn),,等速度度量標(biāo)準(zhǔn),,平均延遲度量標(biāo)準(zhǔn),Amdahl,定律（,1967,）,參數(shù)約定,,P,：,處理器數(shù)；,,W,：,問(wèn)題規(guī)模（計(jì)算負(fù)載、工作負(fù)載，給定問(wèn)題的總計(jì)算量）；,,W,s,：,應(yīng)用程序中的串行分量，,f,是串行分量比例（,f = W,s,/W,，,W,s,=W,1,）；,,W,P,：,應(yīng)用程序中可并行化部分，,1,-,f,,為并行分量比例；,,W,s,+W,p,=W,；,,T,s,=T,1,：,串行執(zhí)行時(shí)間，,T,p,：,并行執(zhí)行時(shí)間；,,S,：,加速比，,E,：

18、,效率；,,出發(fā)點(diǎn)：,,固定不變的計(jì)算負(fù)載；,,固定的計(jì)算負(fù)載分布在多個(gè)處理器上；,,增加處理器加快執(zhí)行速度，從而達(dá)到了加速的目的。,Amdahl,定律,（,cont‘d),固定負(fù)載的加速公式：,,,,歸一化：,W,s,+ W,p,可相應(yīng)地表示為,f+,（,1-f,）,,,,,,近似公式：,p→∞,時(shí)，上式極限為,S= 1 / f,,考慮額外開(kāi)銷(xiāo),W,o,：,,Amdahl’s law (cont’d),Gustafson,定律（,1988,）,出發(fā)點(diǎn)：,,對(duì)于很多大型計(jì)算，精度要求很高，即在此類(lèi)應(yīng)用中精度是個(gè)關(guān)鍵因素，而計(jì)算時(shí)間是固定不變的。此時(shí)為提高精度，必須加大計(jì)算量，相應(yīng)地亦必須增多處

19、理器數(shù)才能維持時(shí)間不變；,,除非學(xué)術(shù)研究，在實(shí)際應(yīng)用中沒(méi)有必要固定工作負(fù)載而計(jì)算程序運(yùn)行在不同數(shù)目的處理器上，增多處理器必須相應(yīng)地增大問(wèn)題規(guī)模才有實(shí)際意義。,Gustafson,定律（,1988,）,,,Gustafson,加速定律,:,,,,近似公式：,p→∞,時(shí)，,S’=,p-fp,=(1-f)P,1-f,為斜率,,并行開(kāi)銷(xiāo),W,o,：,,Gustafson,定律（,cont‘d),Sun,和,Ni,定律,基本思想：,,只要存儲(chǔ)空間許可，應(yīng)盡量增大問(wèn)題規(guī)模以產(chǎn)生更好和更精確的解（此時(shí)可能使執(zhí)行時(shí)間略有增加）。,,假定在單節(jié)點(diǎn)上使用了全部存儲(chǔ)容量,M,并在相應(yīng)于,W,的時(shí)間內(nèi)求解之，此時(shí)工作

20、負(fù)載,W=,fW,+,（,1-f,）,W,。,,在,p,個(gè)節(jié)點(diǎn)的并行系統(tǒng)上，能夠求解較大規(guī)模的問(wèn)題是因?yàn)榇鎯?chǔ)容量可增加到,pM,。,令因子,G,（,p,）,反應(yīng)存儲(chǔ)容量增加到,p,倍時(shí)并行工作負(fù)載的增加量，所以擴(kuò)大后的工作負(fù)載,W =,fW,+,（,1-f,）,G,（,p,）,W,。,Sun,和,Ni,定律,存儲(chǔ)受限的加速公式 ：,,,,,,并行開(kāi)銷(xiāo),W,o,:,Sun,和,Ni,定律,(cont’d),Sun,和,Ni,定律,(cont’d),討論：,,G,（,p,）,=1,時(shí)，就是,Amdahl,加速定律；,,,G,（,p,）,=p,時(shí),, s’’,變?yōu)?f + p,（,1-f,），,就是

21、,Gustafson,加速定律,,G,（,p,）,>p,時(shí)，相應(yīng)于計(jì)算機(jī)負(fù)載比存儲(chǔ)要求增加得快，此時(shí),Sun,和,N i,加速均比,Amdahl,加速和,Gustafson,加速為高。,加速比討論,參考的加速經(jīng)驗(yàn)公式：,p/log p≤S≤P,,線性加速比：很少通信開(kāi)銷(xiāo)的矩陣相加、內(nèi)積運(yùn)算等,,p/log p,的加速比：分治類(lèi)的應(yīng)用問(wèn)題,,通信密集類(lèi)的應(yīng)用問(wèn)題 ：,S = 1 / C,（,p,）,, C,（,p,）,為與,p,有關(guān)的通信函數(shù),,超線性加速：并行搜索，,Cache,效應(yīng),,絕對(duì)加速：最佳并行算法與串行算法,,相對(duì)加速：同一算法在單機(jī)和并行機(jī)的運(yùn)行時(shí)間,可擴(kuò)展分析,給定并行算法（程

22、序）和并行機(jī)，如何調(diào)整參與并行計(jì)算的處理器個(gè)數(shù),P,和求解問(wèn)題的計(jì)算規(guī)模,W,，使得隨著處理器個(gè)數(shù)的增長(zhǎng)，并行計(jì)算的效率可以保持不變，稱(chēng)之為并行程序和并行機(jī)相結(jié)合的可擴(kuò)展分析。,,可擴(kuò)展分析是并行計(jì)算一個(gè)重要研究課題，被廣泛應(yīng)用于描述并行算法（程序）能否有效利用可擴(kuò)展的處理器個(gè)數(shù)的能力。,可擴(kuò)展分析目的,通常地，可擴(kuò)展分析具有四個(gè)目的：,,選擇合理的算法與結(jié)構(gòu)組合,,,確定求解某類(lèi)問(wèn)題的何種并行算法與何種并行機(jī)的組合，它可以有效地利用所期望的處理器規(guī)模,。,,性能預(yù)測(cè),,,對(duì)于運(yùn)行在某臺(tái)并行機(jī)上的某種算法（程序），根據(jù)算法（程序）在小處理器規(guī)模上的運(yùn)行性能，預(yù)測(cè)該算法（程序）移植到大處理器規(guī)模

23、上后運(yùn)行的性能。,,最優(yōu)性能選擇,,,對(duì)某類(lèi)算法，假設(shè)問(wèn)題規(guī)模固定，確定在某類(lèi)并行機(jī)上最優(yōu)的處理器個(gè)數(shù)和可獲得的最優(yōu)的加速比。指導(dǎo)性能優(yōu)化指導(dǎo)改進(jìn)并行算法（程序），使得并行算法充分利用可擴(kuò)展的處理器規(guī)模。,,指導(dǎo)性能優(yōu)化,,,指導(dǎo)改進(jìn)并行算法（程序），使得并行算法充分利用可擴(kuò)展的處理器規(guī)模。,,可擴(kuò)展分析方法（,1,）,等效率度量,,對(duì)于某類(lèi)算法和并行機(jī)，如何保持問(wèn)題規(guī)模,W,與處理器個(gè)數(shù),P,之間的關(guān)系,W,p,P,q,，使得隨著處理器個(gè)數(shù),P,的增長(zhǎng)，保持并行計(jì)算的效率不變。也就是求出等效率函數(shù)：,,,,W=,,f,E,(,P),,E,固定,,,等效率值越小，則當(dāng)處理器個(gè)數(shù)增多時(shí)為保持相同

24、效率所需增加的問(wèn)題規(guī)模就越小，因此就有更好的可擴(kuò)展性。,,可擴(kuò)展分析方法（,2,）,等速度度量,,對(duì)于運(yùn)行在并行機(jī)上的某個(gè)算法，當(dāng)處理器個(gè)數(shù)增加時(shí)，需要增加多大的計(jì)算量，才能保持并行程序的平均速度不變。,,定義平均速度,:,,V,為并行程序的執(zhí)行速度，問(wèn)題規(guī)模從,(,W, P),,變化到,(,W,’,, P,’,),，則等速度可擴(kuò)展度量公式可寫(xiě)為：,,,越接近,1,，說(shuō)明可擴(kuò)展性越好。,,并行程序性能優(yōu)化,并行程序的性能優(yōu)化相對(duì)于串行程序而言更加復(fù)雜，其中最主要的是選擇好的并行算法及通信模式。在并行算法確定之后，影響并行程序效率的主要因素是通信開(kāi)銷(xiāo)、由于數(shù)據(jù)相關(guān)性或負(fù)載不平衡引起的進(jìn)程空閑等待

25、、以及并行算法引入的冗余計(jì)算。在設(shè)計(jì)并行程序時(shí)，可以采用多種技術(shù)來(lái)減少或消除這些因素對(duì)并行效率的影響。,并行程序優(yōu)化技術(shù),1.,減少通信量、提高通信粒度,,2.,全局通信盡量利用高效聚合通信算法,,3.,挖掘算法的并行度，減少,CPU,空閑等待,,4.,負(fù)載平衡,,5.,通信、計(jì)算的重疊,,6.,通過(guò)引入重復(fù)計(jì)算來(lái)減少通信,1.,減少通信量、提高通信粒度,在消息傳遞并行程序中，花費(fèi)在通信上的時(shí)間是純開(kāi)銷(xiāo)，因此如何減少通信時(shí)間是并行程序設(shè)計(jì)中首先要考慮的問(wèn)題。減少通信時(shí)間的途徑主要有三個(gè)：減少通信量、提高通信粒度和提高通信中的并發(fā)度,(,即不同結(jié)點(diǎn)對(duì)間同時(shí)進(jìn)行通信，要注意的是，這些手段都是相對(duì)于

26、特定條件而言的，例如，在網(wǎng)絡(luò)重負(fù)載的情況下，提高通信并行度并不能改善程序的性能,),。,,提高通信粒度的有效方法是減少通信次數(shù)，即盡可能將可以一起傳遞的數(shù)據(jù)合并起來(lái)一次傳遞。在收發(fā)不同類(lèi)型的數(shù)據(jù)時(shí)，定義適當(dāng)?shù)?MPI,數(shù)據(jù)類(lèi)型來(lái)避免內(nèi)存中的數(shù)據(jù)拷貝。,2.,全局通信盡量利用高效聚合通信算法,當(dāng)組織多個(gè)進(jìn)程之間的聚合通信時(shí)，使用高效的通信算法可以大大提高通信效率、降低通信開(kāi)銷(xiāo)。對(duì)于標(biāo)準(zhǔn)的聚合通信，如廣播、歸約、數(shù)據(jù)散發(fā)與收集等，盡量調(diào)用,MPI,標(biāo)準(zhǔn)庫(kù)中的函數(shù)，因?yàn)檫@些函數(shù)往往經(jīng)過(guò)專(zhuān)門(mén)優(yōu)化。但使用標(biāo)準(zhǔn)庫(kù)函數(shù)的一個(gè)缺點(diǎn)是整個(gè)通信過(guò)程被封裝起來(lái)，無(wú)法在通信的同時(shí)進(jìn)行計(jì)算工作，此時(shí)，可以自行編制相應(yīng)通

27、信代碼，將其與計(jì)算過(guò)程結(jié)合起來(lái)，以達(dá)到最佳的效果。,,,3.,挖掘算法的并行度，減少,CPU,空閑等待,一些具有數(shù)據(jù)相關(guān)性的計(jì)算過(guò)程會(huì)導(dǎo)致并行運(yùn)行的部分進(jìn)程空閑等待。在這種情況下，可以考慮改變算法來(lái)消除數(shù)據(jù)相關(guān)性。某些情況下數(shù)據(jù)相關(guān)性的消除是以增加計(jì)算量做為代價(jià)的，這方面的典型例子有用,Jacobi,迭代替換,Gauss,–,Seidel,或超松弛迭代、三對(duì)角線性方程組的并行解法等。當(dāng)算法在某個(gè)空間方向具有相關(guān)性時(shí)，應(yīng)該考慮充分挖掘其他空間方向以及時(shí)間上的并行度，在這類(lèi)問(wèn)題中流水線方法往往發(fā)揮著重要的作用。,4.,負(fù)載平衡,負(fù)載不平衡是導(dǎo)致進(jìn)程空閑等待的另外一個(gè)重要因素。在設(shè)計(jì)并行算法時(shí)應(yīng)該充

28、分考慮負(fù)載平衡問(wèn)題，必要時(shí)使用動(dòng)態(tài)負(fù)載平衡技術(shù)，即根據(jù)各進(jìn)程計(jì)算完成的情況動(dòng)態(tài)地分配或調(diào)整各進(jìn)程的計(jì)算任務(wù)。動(dòng)態(tài)調(diào)整負(fù)載時(shí)要考慮負(fù)載調(diào)整的開(kāi)銷(xiāo)及由于負(fù)載不平衡而引起的空閑等待對(duì)性能的影響，尋找最優(yōu)負(fù)載調(diào)整方案。,,5.,通信、計(jì)算的重疊,通過(guò)讓通信與計(jì)算重疊進(jìn)行，利用計(jì)算時(shí)間來(lái)屏蔽通信時(shí)間，是減少通信開(kāi)銷(xiāo)的非常有效的方法。實(shí)現(xiàn)通信與計(jì)算重疊的方法一般基于非阻塞通信，先發(fā)出非阻塞的消息接收或發(fā)送命令，然后處理與收發(fā)數(shù)據(jù)無(wú)關(guān)的計(jì)算任務(wù)，完成這些計(jì)算后再等待消息收發(fā)的完成。通信與計(jì)算的重疊能否實(shí)現(xiàn)，除了取決于算法和程序的實(shí)現(xiàn)方式之外，還取決于并行機(jī)的通信網(wǎng)絡(luò)及通信協(xié)議。,,,6.,通過(guò)引入重復(fù)計(jì)算來(lái)減少通信,有時(shí)通過(guò)適當(dāng)引入一些重復(fù)計(jì)算，可以減少通信量或通信次數(shù)。由于當(dāng)前大部分并行機(jī)的計(jì)算速度遠(yuǎn)遠(yuǎn)快于通信速度，并且一些情況下，當(dāng)一個(gè)進(jìn)程計(jì)算時(shí)，其他進(jìn)程往往處于空閑等待狀態(tài)，因而適當(dāng)引入重復(fù)計(jì)算可以提高程序的總體性能。,,例如一些公共量的計(jì)算，可以由一個(gè)進(jìn)程完成然后再發(fā)送給其他進(jìn)程，也可以各進(jìn)程分別獨(dú)立計(jì)算。后一個(gè)做法在性能上通常要好于前一個(gè)做法。另外一個(gè)通過(guò)引入重復(fù)計(jì)算來(lái)提高通信粒度。,,,