高性能計算導(dǎo)論：并行計算性能評價

《高性能計算導(dǎo)論：并行計算性能評價》由會員分享，可在線閱讀，更多相關(guān)《高性能計算導(dǎo)論：并行計算性能評價（48頁珍藏版）》請在裝配圖網(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,并行計算性能評價,上海大學(xué)計算機工程與科學(xué)學(xué)院,計算的本質(zhì),串行計算模型,圖靈機,并行計算模型,計算效能評價,計算模型與效能評價,高性

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

3、獨享處理器資源時，串行程序的執(zhí)行時間近似等于程序指令執(zhí)行花費的,CPU,時間。但是，并行程序相對復(fù)雜，其,執(zhí)行時間（,execution time,）等于從并行程序開始執(zhí)行，到所有進程執(zhí)行完畢，墻上時鐘走過的時間,，也稱之為,墻上時間,（,wall time,）。,對各個進程，墻上時間可進一步分解為：,計算,CPU,時間,通信,CPU,時間,同步開銷時間,進程空閑時間,（是由同步導(dǎo)致的）,并行程序執(zhí)行時間,計算,CPU,時間,進程指令執(zhí)行所花費的,CPU,時間，它可以分解為兩個部分，一個是程序本身指令執(zhí)行占用的,CPU,時間，即通常所說的用戶時間（,user time,），主要包含指令在,CP

4、U,內(nèi)部的執(zhí)行時間和內(nèi)存訪問時間，另一個是為了維護程序的執(zhí)行，操作系統(tǒng)花費的,CPU,時間，即通常所說的系統(tǒng)時間（,system time,），主要包含內(nèi)存調(diào)度和管理開銷、,I/O,時間、以及維護程序執(zhí)行所必需要的操作系統(tǒng)開銷等。通常地，系統(tǒng)時間可以忽略。,并行程序執(zhí)行時間,通信,CPU,時間,包含進程通信花費的,CPU,時間。,同步開銷時間,包含進程同步花費的時間,進程空閑時間,當(dāng)一個進程阻塞式等待其他進程的消息時，,CPU,通常是空閑的，或者處于等待狀態(tài)。進程空閑時間是指并行程序執(zhí)行過程中，進程所有這些空閑時間的總和。,顯然，進程的計算,CPU,時間小于并行程序的墻上時間，而并行程序的,墻

5、上時間,才是用戶真正關(guān)心的時間，是評價一個并行程序執(zhí)行速度的時間。,11/3/2024,9,/59,并行算法設(shè)計及效能分析,并行算法效能分析,并行加速比,并行效率,可擴展性,（簡單表述）,處理機數(shù),p,增加時，并行效率,E,p,不顯著下降。,效能分析分析說明,需要說明的是，,T,1,指處理器個數(shù)為,1,時，并行程序的執(zhí)行時間。通常情形下，,T,1,大于,TS,，因為并行程序往往引入一些冗余的控制和管理開銷。,加速比和效率是衡量一個并行程序性能的最基本的評價方法。顯然，執(zhí)行最慢的進程將決定并行程序的性能。,在以上加速比和效率的定義中，有一個基本的假設(shè)，要求并行機的各個處理器是同構(gòu),(homoge

6、neous),的，即并行機各個處理器的結(jié)構(gòu)完全一致（包含,CPU,類型、內(nèi)存大小與性能、,cache,特征等等），或者說，串行程序在各個處理器執(zhí)行的墻上時間相等。,效能分析分析說明,如果并行機的各個處理器功能不一致，稱之為異構(gòu)并行機。對此，以上加速比和效率的定義不是很合適。其中，兩個突出的問題就是，串行程序的執(zhí)行時間是選擇最快的處理器運行，還是選擇最慢的處理器運行？在效率定義中，處理器個數(shù)選擇為,P,是否合適？一個比較好的方法就是，將所有處理器以最快的處理器為基準，進行歸一化處理。,并行程序性能評價方法,以上介紹的加速比和效率，只能反映并行程序的整體執(zhí)行性能，但是，無法反映并行程序的性能瓶頸。

7、性能評價的主要目的在于，揭示并行程序的性能瓶頸，指導(dǎo)并行程序的性能優(yōu)化。因此，有必要進一步分解加速比和效率，提出更細致的性能評價方法。,并行計算性能評測,3.1,并行機的一些基本性能指標,3.2,加速比性能定律,3.2.1,Amdahl,定律,3.2.2,Gustafson,定律,3.2.3,Sun,和,Ni,定律,3.3,可擴放性評測標準,3.3.1,并行計算的可擴放性,3.3.2,等效率度量標準,3.3.3,等速度度量標準,3.3.4,平均延遲度量標準,3.4,基準測試程序,并行計算的性能評測,機器級,的性能評測,CPU,和存儲器的某些基本性能指標,并行通信開銷,機器的成本、價格、和性能,

8、/,價格比等,算法級,的性能評測,加速比,效率,可擴展性,程序級,的性能評測,基本測試程序,數(shù)學(xué)庫測試,并行測試程序等,并行機基本性能參數(shù)一覽表,名稱,符號,含義,單位,機器規(guī)模,n,處理器的數(shù)目,無量綱,時鐘速率,f,時鐘周期長度的倒數(shù),MHz,工作負載,W,計算操作的數(shù)目,Mflops,順序執(zhí)行時間,T,1,程序在單處理機上的運行時間,s,并行執(zhí)行時間,T,n,程序在并行機上的運行時間,s,速度,R,n,=W/T,n,每秒百萬次浮點運算,Mflops,加速,S,n,=T1/T,n,衡量并行機有多快,無量綱,效率,E,n,=S,n,/n,衡量處理器的利用率,無量綱,峰值速度,R,peak,=

9、nR,peak,所有處理器峰值,(R,peak,),速度之積,Mflops,利用率,U=R,n,/R,peak,可達速度與峰值速度之比,無量綱,通信延遲,t,0,傳送,0,個字節(jié)或單字的時間,us,漸近帶寬,r,傳送長消息通信速率,MB/,s,工作負載,工作負載（荷）：計算操作數(shù)目,執(zhí)行時間,掠過時間：墻上時間,所執(zhí)行的指令數(shù)目,所完成的浮點運算數(shù),CPU,的某些基本性能指標,工作負載,執(zhí)行時間,:,程序從開始到結(jié)束的時間。,浮點運算數(shù),指令數(shù)目：通常用百萬條指令,并行執(zhí)行時間,T,n,：,T,comput,為計算時間，,T,paro,為并行開銷時間，,T,comm,為相互通信時間,T,n,=

10、T,comput,+T,paro,+T,comm,例：估計,APRAM,模型下執(zhí)行時間,其中,T,1,為串行時間，,n,為處理器數(shù)，,T,為使用無限多處理器且不考慮,T,paro,與,T,comm,的并行執(zhí)行時間,存儲器性能,存儲器的層次結(jié)構(gòu),(C,L,B),-,容量,C,，延遲,L,，帶寬,B,估計存儲器的帶寬,RISC,指令,add r1,r2,r3,，寄存器,8bytes,，主頻,100MHz,B=3*8*100*10,6,B/s=2.4GB/s,并行與通信開銷,并行和通信開銷：相對于計算很大。,PowerPC (,每個周期,15ns,執(zhí)行,4flops;,創(chuàng)建一個進程,1.4ms,可執(zhí)

11、行,372000flops),開銷的測量：乒,-,乓方法（,Ping-Pong Scheme,）,節(jié)點,0,發(fā)送,m,個字節(jié)給節(jié)點,1,；節(jié)點,1,從節(jié)點,0,接收,m,個字節(jié)后，立即將消息發(fā)回節(jié)點,0,?？偟臅r間除以,2,，即可得到點到點通信時間，也就是執(zhí)行單一發(fā)送或接收操作的時間。,可一般化為熱土豆法（,Hot-Potato,），,也稱為救火隊法（,Fire-Brigade)01 2 n-1 0,即從節(jié)點,0,發(fā)送,m,字節(jié)給,1,，節(jié)點,1,給節(jié)點,2,，依次類推，最后節(jié)點,n-1,再將其返回給,0,，最后時間再除以,n,即可。,Ping-Pong Scheme,if,（,my _nod

12、e _id=0,）,then/*,發(fā)送者*,/,start _time=second,（）,send an m-byte message to node,1 /,發(fā)送,receive an m-byte message from node,1 /,接收,end_time=second,（）,total_time=end_time start_time,communication_timei=total_time/2,else if,（,my_node_id=1,）,then /*,接收者*,/,receive an m-byte message from node 0,send an m-by

13、te message to node 0,endif,并行開銷的表達式：點到點通信,通信開銷,t,(,m,)=,t,0,+,m,/,r,通信啟動時間,t,0,漸近,帶寬,r,：,傳送無限長的消息時的通信速率,m,為傳輸?shù)淖止?jié)數(shù),半,峰值長度,m,1/2,：達到一半漸近帶寬所要的消息長度,特定性能,0,：表示短消息帶寬,t,0,=m,1/2,/,r,=1/,0,并行開銷的表達式：組通信,典型的組通信有：,播送,（,Broadcasting,）：,處理器,0,發(fā)送,m,個字節(jié)給所有的,n,個處理器,-,廣播,收集,（,Gather,）：,處理,0,接收所有,n,個處理器發(fā)來在消息，所以處理器,0,

14、最終接收了,m,x,n,個字節(jié)；,散射,（,Scatter,）：,處理器,0,發(fā)送了,m,個字節(jié)的不同消息給所有,n,個處理器，因此處理器,0,最終發(fā)送了,m,x,n,個字節(jié)；,全交換,（,Total Exchange,）：,每個處理器均彼此相互發(fā)送,m,個字節(jié)的不同消息給對方，所以總通信量為,m,x,n,2,個字節(jié)；,循環(huán)移位,（,Circular-shift,）：,處理器,i,發(fā)送,m,個字節(jié)給處理器,i+1,，,處理器,n-1,發(fā)送,m,個字節(jié)給處理器,0,，所以通信量為,m,x,n,個字節(jié)。,機器的成本、價格與性,/,價比,機器的成本與價格,機器的性能,/,價格比,Performanc

15、e/Cost Ratio,：,系指用單位代價（通常以百萬美元表示）所獲取的性能（通常以,MIPS,或,MFLOPS,表示）,利用率（,Utilization,）：,可達到的速度與峰值速度之比,并行計算性能評測,3.1,并行機的一些基本性能指標,3.2,加速比性能定律,3.2.1,Amdahl,定律,3.2.2,Gustafson,定律,3.2.3,Sun,和,Ni,定律,3.3,可擴放性評測標準,3.3.1,并行計算的可擴放性,3.3.2,等效率度量標準,3.3.3,等速度度量標準,3.3.4,平均延遲度量標準,3.4,基準測試程序,算法級性能評測,加速比性能定律,并行系統(tǒng)的加速比是指對于一個

16、給定的應(yīng)用，并行算法（或并行程序）的執(zhí)行速度相對于串行算法（或串行程序）的執(zhí)行速度加快了多少倍。,Amdahl,定律,Gustafson,定律,Sun Ni,定律,可擴放性評測標準,等效率度量標準,等速度度量標準,平均延遲度量標準,Amdahl,定律（,1967,）,參數(shù)約定,P,：,處理器數(shù)；,W,：,問題規(guī)模（計算負載、工作負載，給定問題的總計算量）；,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í)行時間，,T,p,：,并行執(zhí)行時間；,S,：,加速比，,E,：,效率；,出發(fā)點：,固定不變的計算負載；,固定的計算負載分布在多個處理器上；,增加處理器加快執(zhí)行速度，從而達到了加速的目的。,Amdahl,定律,（,contd),固定負載的加速公式：,歸一化：,W,s,+W,p,可相應(yīng)地表示為,f+,（,1-f,）,近似公式：,p,時，上式極限為,S=1/f,考慮額外開銷,W,o,：,Amdahls law(co