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

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ì)算效能評(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)，通過并行實(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à)并行程序的性能之前，必須清楚并行程序的執(zhí)行時(shí)間是由哪些部分組成的。眾所周知，獨(dú)享處理器資源時(shí)，串行程序的執(zhí)行時(shí)間近似等于程序指令執(zhí)行花費(fèi)的,CPU,時(shí)間。但是，并行程序相對(duì)復(fù)雜，其,執(zhí)行時(shí)間（,execution time,）等于從并行程序開始執(zhí)行，到所有進(jìn)程執(zhí)行完畢，墻上時(shí)鐘走過的時(shí)間,，也稱之為,墻上時(shí)間,（,wall time,）。,對(duì)各個(gè)進(jìn)程，墻上時(shí)間可進(jìn)一步分解為：,計(jì)算,CPU,時(shí)間,通信,CPU,時(shí)間,同步開銷時(shí)間,進(jìn)程空閑時(shí)間,（是由同步導(dǎo)致的）,并行程序執(zhí)行時(shí)間,計(jì)算,CPU,時(shí)間,進(jìn)程指令執(zhí)行所花費(fèi)的,CPU,時(shí)間，它可以分解為兩個(gè)部分，一個(gè)是程序本身指令執(zhí)行占用的,CPU,時(shí)間，即通常所說的用戶時(shí)間（,user time,），主要包含指令在,CPU,內(nèi)部的執(zhí)行時(shí)間和內(nèi)存訪問時(shí)間，另一個(gè)是為了維護(hù)程序的執(zhí)行，操作系統(tǒng)花費(fèi)的,CPU,時(shí)間，即通常所說的系統(tǒng)時(shí)間（,system time,），主要包含內(nèi)存調(diào)度和管理開銷、,I/O,時(shí)間、以及維護(hù)程序執(zhí)行所必需要的操作系統(tǒng)開銷等。通常地，系統(tǒng)時(shí)間可以忽略。,并行程序執(zhí)行時(shí)間,通信,CPU,時(shí)間,包含進(jìn)程通信花費(fèi)的,CPU,時(shí)間。,同步開銷時(shí)間,包含進(jìn)程同步花費(fèi)的時(shí)間,進(jìn)程空閑時(shí)間,當(dāng)一個(gè)進(jìn)程阻塞式等待其他進(jìn)程的消息時(shí)，,CPU,通常是空閑的，或者處于等待狀態(tài)。進(jìn)程空閑時(shí)間是指并行程序執(zhí)行過程中，進(jìn)程所有這些空閑時(shí)間的總和。,顯然，進(jìn)程的計(jì)算,CPU,時(shí)間小于并行程序的墻上時(shí)間，而并行程序的,墻上時(shí)間,才是用戶真正關(guān)心的時(shí)間，是評(píng)價(jià)一個(gè)并行程序執(zhí)行速度的時(shí)間。,11/3/2024,9,/59,并行算法設(shè)計(jì)及效能分析,并行算法效能分析,并行加速比,并行效率,可擴(kuò)展性,（簡(jiǎn)單表述）,處理機(jī)數(shù),p,增加時(shí)，并行效率,E,p,不顯著下降。,效能分析分析說明,需要說明的是，,T,1,指處理器個(gè)數(shù)為,1,時(shí)，并行程序的執(zhí)行時(shí)間。通常情形下，,T,1,大于,TS,，因?yàn)椴⑿谐绦蛲胍恍┤哂嗟目刂坪凸芾黹_銷。,加速比和效率是衡量一個(gè)并行程序性能的最基本的評(píng)價(jià)方法。顯然，執(zhí)行最慢的進(jìn)程將決定并行程序的性能。,在以上加速比和效率的定義中，有一個(gè)基本的假設(shè)，要求并行機(jī)的各個(gè)處理器是同構(gòu),(homogeneous),的，即并行機(jī)各個(gè)處理器的結(jié)構(gòu)完全一致（包含,CPU,類型、內(nèi)存大小與性能、,cache,特征等等），或者說，串行程序在各個(gè)處理器執(zhí)行的墻上時(shí)間相等。,效能分析分析說明,如果并行機(jī)的各個(gè)處理器功能不一致，稱之為異構(gòu)并行機(jī)。對(duì)此，以上加速比和效率的定義不是很合適。其中，兩個(gè)突出的問題就是，串行程序的執(zhí)行時(shí)間是選擇最快的處理器運(yùn)行，還是選擇最慢的處理器運(yùn)行？在效率定義中，處理器個(gè)數(shù)選擇為,P,是否合適？一個(gè)比較好的方法就是，將所有處理器以最快的處理器為基準(zhǔn)，進(jìn)行歸一化處理。,并行程序性能評(píng)價(jià)方法,以上介紹的加速比和效率，只能反映并行程序的整體執(zhí)行性能，但是，無法反映并行程序的性能瓶頸。性能評(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è)試程序,并行計(jì)算的性能評(píng)測(cè),機(jī)器級(jí),的性能評(píng)測(cè),CPU,和存儲(chǔ)器的某些基本性能指標(biāo),并行通信開銷,機(jī)器的成本、價(jià)格、和性能,/,價(jià)格比等,算法級(jí),的性能評(píng)測(cè),加速比,效率,可擴(kuò)展性,程序級(jí),的性能評(píng)測(cè),基本測(cè)試程序,數(shù)學(xué)庫測(cè)試,并行測(cè)試程序等,并行機(jī)基本性能參數(shù)一覽表,名稱,符號(hào),含義,單位,機(jī)器規(guī)模,n,處理器的數(shù)目,無量綱,時(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,每秒百萬次浮點(diǎn)運(yùn)算,Mflops,加速,S,n,=T1/T,n,衡量并行機(jī)有多快,無量綱,效率,E,n,=S,n,/n,衡量處理器的利用率,無量綱,峰值速度,R,peak,=nR,peak,所有處理器峰值,(R,peak,),速度之積,Mflops,利用率,U=R,n,/R,peak,可達(dá)速度與峰值速度之比,無量綱,通信延遲,t,0,傳送,0,個(gè)字節(jié)或單字的時(shí)間,us,漸近帶寬,r,傳送長(zhǎng)消息通信速率,MB/,s,工作負(fù)載,工作負(fù)載（荷）：計(jì)算操作數(shù)目,執(zhí)行時(shí)間,掠過時(shí)間：墻上時(shí)間,所執(zhí)行的指令數(shù)目,所完成的浮點(diǎn)運(yùn)算數(shù),CPU,的某些基本性能指標(biāo),工作負(fù)載,執(zhí)行時(shí)間,:,程序從開始到結(jié)束的時(shí)間。,浮點(diǎn)運(yùn)算數(shù),指令數(shù)目：通常用百萬條指令,并行執(zhí)行時(shí)間,T,n,：,T,comput,為計(jì)算時(shí)間，,T,paro,為并行開銷時(shí)間，,T,comm,為相互通信時(shí)間,T,n,=T,comput,+T,paro,+T,comm,例：估計(jì),APRAM,模型下執(zhí)行時(shí)間,其中,T,1,為串行時(shí)間，,n,為處理器數(shù)，,T,為使用無限多處理器且不考慮,T,paro,與,T,comm,的并行執(zhí)行時(shí)間,存儲(chǔ)器性能,存儲(chǔ)器的層次結(jié)構(gòu),(C,L,B),-,容量,C,，延遲,L,，帶寬,B,估計(jì)存儲(chǔ)器的帶寬,RISC,指令,add r1,r2,r3,，寄存器,8bytes,，主頻,100MHz,B=3*8*100*10,6,B/s=2.4GB/s,并行與通信開銷,并行和通信開銷：相對(duì)于計(jì)算很大。,PowerPC (,每個(gè)周期,15ns,執(zhí)行,4flops;,創(chuàng)建一個(gè)進(jìn)程,1.4ms,可執(zhí)行,372000flops),開銷的測(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-Potato,），,也稱為救火隊(duì)法（,Fire-Brigade)01 2 n-1 0,即從節(jié)點(diǎn),0,發(fā)送,m,字節(jié)給,1,，節(jié)點(diǎn),1,給節(jié)點(diǎn),2,，依次類推，最后節(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,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-byte message to node 0,endif,并行開銷的表達(dá)式：點(diǎn)到點(diǎn)通信,通信開銷,t,(,m,)=,t,0,+,m,/,r,通信啟動(dòng)時(shí)間,t,0,漸近,帶寬,r,：,傳送無限長(zhǎng)的消息時(shí)的通信速率,m,為傳輸?shù)淖止?jié)數(shù),半,峰值長(zhǎng)度,m,1/2,：達(dá)到一半漸近帶寬所要的消息長(zhǎng)度,特定性能,0,：表示短消息帶寬,t,0,=m,1/2,/,r,=1/,0,并行開銷的表達(dá)式：組通信,典型的組通信有：,播送,（,Broadcasting,）：,處理器,0,發(fā)送,m,個(gè)字節(jié)給所有的,n,個(gè)處理器,-,廣播,收集,（,Gather,）：,處理,0,接收所有,n,個(gè)處理器發(fā)來在消息，所以處理器,0,最終接收了,m,x,n,個(gè)字節(jié)；,散射,（,Scatter,）：,處理器,0,發(fā)送了,m,個(gè)字節(jié)的不同消息給所有,n,個(gè)處理器，因此處理器,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à)（通常以百萬美元表示）所獲取的性能（通常以,MIPS,或,MFLOPS,表示）,利用率（,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í)行速度加快了多少倍。,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,：,問題規(guī)模（計(jì)算負(fù)載、工作負(fù)載，給定問題的總計(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,：,效率；,出發(fā)點(diǎn)：,固定不變的計(jì)算負(fù)載；,固定的計(jì)算負(fù)載分布在多個(gè)處理器上；,增加處理器加快執(zhí)行速度，從而達(dá)到了加速的目的。,Amdahl,定律,（,contd),固定負(fù)載的加速公式：,歸一化：,W,s,+W,p,可相應(yīng)地表示為,f+,（,1-f,）,近似公式：,p,時(shí)，上式極限為,S=1/f,考慮額外開銷,W,o,：,Amdahls law(co