高性能計(jì)算導(dǎo)論并行計(jì)算性能評價ppt課件

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,我嚇了一跳，蝎子是多么丑惡和恐怖的東西，為什么把它放在這樣一個美麗的世界里呢？但是我也感到愉快，證實(shí)我的猜測沒有錯：表里邊有一個活的生物,并行計(jì)算性能評價,并行計(jì)算性能評價,上海大學(xué)計(jì)算機(jī)工程與科學(xué)學(xué)院,計(jì)算的本質(zhì),串行計(jì)算模型圖靈機(jī),并行計(jì)算模型,計(jì)算效能評價,計(jì)算模型與效能評價,高性能計(jì)算導(dǎo)論,上海大學(xué)計(jì)算機(jī)工程與科學(xué)學(xué)院 計(jì)算的本質(zhì)計(jì)算模型與效能評價高,“并行計(jì)算”研究的四大分支,并行計(jì)算機(jī),體系結(jié)構(gòu),并行,算法,并行,程序設(shè)計(jì),并行計(jì)算的,性能評測,而介于并行計(jì)算機(jī),體系結(jié)構(gòu),與并行,算法,之間的是并行,計(jì)算模型,并行計(jì)算”研究的四大分支并行計(jì)算機(jī)體系結(jié)構(gòu),Performance Evaluation,并行計(jì)算效能評價,Performance Evaluation并行計(jì)算效能評價,程序性能評價與優(yōu)化,給定并行算法，采用并行程序設(shè)計(jì)平臺，通過并行實(shí)現(xiàn)獲得實(shí)際可運(yùn)行的并行程序后，一個重要的工作就是，在并行機(jī)上運(yùn)行該程序，評價該程序的實(shí)際性能，,揭示性能瓶頸，指導(dǎo)程序的性能優(yōu)化,。

性能評價和優(yōu)化是設(shè)計(jì)高效率并行程序必不可少的重要工作程序性能評價與優(yōu)化給定并行算法，采用并行程序設(shè)計(jì)平臺，通過并,并行程序執(zhí)行時間,評價并行程序的性能之前，必須清楚并行程序的執(zhí)行時間是由哪些部分組成的眾所周知，獨(dú)享處理器資源時，串行程序的執(zhí)行時間近似等于程序指令執(zhí)行花費(fèi)的CPU 時間但是，并行程序相對復(fù)雜，其,執(zhí)行時間（execution time）等于從并行程序開始執(zhí)行，到所有進(jìn)程執(zhí)行完畢，墻上時鐘走過的時間,，也稱之為,墻上時間,（wall time）對各個進(jìn)程，墻上時間可進(jìn)一步分解為：,計(jì)算CPU 時間,通信CPU 時間,同步開銷時間,進(jìn)程空閑時間,（是由同步導(dǎo)致的）,并行程序執(zhí)行時間評價并行程序的性能之前，必須清楚并行程序的執(zhí),并行程序執(zhí)行時間,計(jì)算CPU 時間,進(jìn)程指令執(zhí)行所花費(fèi)的CPU 時間，它可以分解為兩個部分，一個是程序本身指令執(zhí)行占用的CPU 時間，即通常所說的用戶時間（user time），主要包含指令在CPU 內(nèi)部的執(zhí)行時間和內(nèi)存訪問時間，另一個是為了維護(hù)程序的執(zhí)行，操作系統(tǒng)花費(fèi)的CPU 時間，即通常所說的系統(tǒng)時間（system time），主要包含內(nèi)存調(diào)度和管理開銷、I/O 時間、以及維護(hù)程序執(zhí)行所必需要的操作系統(tǒng)開銷等。

通常地，系統(tǒng)時間可以忽略并行程序執(zhí)行時間計(jì)算CPU 時間,并行程序執(zhí)行時間,通信CPU 時間,包含進(jìn)程通信花費(fèi)的CPU 時間同步開銷時間,包含進(jìn)程同步花費(fèi)的時間,進(jìn)程空閑時間,當(dāng)一個進(jìn)程阻塞式等待其他進(jìn)程的消息時，CPU 通常是空閑的，或者處于等待狀態(tài)進(jìn)程空閑時間是指并行程序執(zhí)行過程中，進(jìn)程所有這些空閑時間的總和顯然，進(jìn)程的計(jì)算CPU 時間小于并行程序的墻上時間，而并行程序的,墻上時間,才是用戶真正關(guān)心的時間，是評價一個并行程序執(zhí)行速度的時間并行程序執(zhí)行時間通信CPU 時間,11/15/2024,9,/59,并行算法設(shè)計(jì)及效能分析,并行算法效能分析,并行加速比,并行效率,可擴(kuò)展性,（簡單表述）,處理機(jī)數(shù),p,增加時，并行效率,E,p,不顯著下降8/8/20239/59并行算法設(shè)計(jì)及效能分析并行算法效能分,效能分析分析說明,需要說明的是，,T,1 指處理器個數(shù)為1 時，并行程序的執(zhí)行時間通常情形下，,T,1 大于,TS,，因?yàn)椴⑿谐绦蛲胍恍┤哂嗟目刂坪凸芾黹_銷加速比和效率是衡量一個并行程序性能的最基本的評價方法顯然，執(zhí)行最慢的進(jìn)程將決定并行程序的性能在以上加速比和效率的定義中，有一個基本的假設(shè)，要求并行機(jī)的各個處理器是同構(gòu)(homogeneous)的，即并行機(jī)各個處理器的結(jié)構(gòu)完全一致（包含CPU 類型、內(nèi)存大小與性能、cache 特征等等），或者說，串行程序在各個處理器執(zhí)行的墻上時間相等。

效能分析分析說明需要說明的是，T1 指處理器個數(shù)為1 時，并,效能分析分析說明,如果并行機(jī)的各個處理器功能不一致，稱之為異構(gòu)并行機(jī)對此，以上加速比和效率的定義不是很合適其中，兩個突出的問題就是，串行程序的執(zhí)行時間是選擇最快的處理器運(yùn)行，還是選擇最慢的處理器運(yùn)行？在效率定義中，處理器個數(shù)選擇為,P,是否合適？一個比較好的方法就是，將所有處理器以最快的處理器為基準(zhǔn)，進(jìn)行歸一化處理效能分析分析說明如果并行機(jī)的各個處理器功能不一致，稱之為異構(gòu),并行程序性能評價方法,以上介紹的加速比和效率，只能反映并行程序的整體執(zhí)行性能，但是，無法反映并行程序的性能瓶頸性能評價的主要目的在于，揭示并行程序的性能瓶頸，指導(dǎo)并行程序的性能優(yōu)化因此，有必要進(jìn)一步分解加速比和效率，提出更細(xì)致的性能評價方法并行程序性能評價方法以上介紹的加速比和效率，只能反映并行程序,并行計(jì)算性能評測,3.1 并行機(jī)的一些基本性能指標(biāo),3.2 加速比性能定律,3.2.1 Amdahl定律,3.2.2 Gustafson定律,3.2.3 Sun和Ni定律,3.3 可擴(kuò)放性評測標(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)測試程序,并行計(jì)算性能評測3.1 并行機(jī)的一些基本性能指標(biāo),并行計(jì)算的性能評測,機(jī)器級,的性能評測,CPU和存儲器的某些基本性能指標(biāo),并行通信開銷,機(jī)器的成本、價格、和性能/價格比等,算法級,的性能評測,加速比,效率,可擴(kuò)展性,程序級,的性能評測,基本測試程序,數(shù)學(xué)庫測試,并行測試程序等,并行計(jì)算的性能評測機(jī)器級的性能評測,并行機(jī)基本性能參數(shù)一覽表,名稱,符號,含義,單位,機(jī)器規(guī)模,n,處理器的數(shù)目,無量綱,時鐘速率,f,時鐘周期長度的倒數(shù),MHz,工作負(fù)載,W,計(jì)算操作的數(shù)目,Mflops,順序執(zhí)行時間,T,1,程序在單處理機(jī)上的運(yùn)行時間,s,并行執(zhí)行時間,T,n,程序在并行機(jī)上的運(yùn)行時間,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個字節(jié)或單字的時間,us,漸近帶寬,r,傳送長消息通信速率,MB/,s,并行機(jī)基本性能參數(shù)一覽表名稱符號含義單位機(jī)器規(guī)模n處理器的數(shù),工作負(fù)載,工作負(fù)載（荷）：計(jì)算操作數(shù)目,執(zhí)行時間掠過時間：墻上時間,所執(zhí)行的指令數(shù)目,所完成的浮點(diǎn)運(yùn)算數(shù),工作負(fù)載工作負(fù)載（荷）：計(jì)算操作數(shù)目,CPU的某些基本性能指標(biāo),工作負(fù)載,執(zhí)行時間:程序從開始到結(jié)束的時間。

浮點(diǎn)運(yùn)算數(shù),指令數(shù)目：通常用百萬條指令,并行執(zhí)行時間,T,n,：T,comput,為計(jì)算時間，T,paro,為并行開銷時間，T,comm,為相互通信時間,T,n,=T,comput,+T,paro,+T,comm,例：估計(jì)APRAM模型下執(zhí)行時間,其中T,1,為串行時間，n為處理器數(shù)，T,為使用無限多處理器且不考慮T,paro,與T,comm,的并行執(zhí)行時間,CPU的某些基本性能指標(biāo)工作負(fù)載,存儲器性能,存儲器的層次結(jié)構(gòu)(C,L,B),-容量C，延遲L，帶寬B,估計(jì)存儲器的帶寬,RISC指令 add r1,r2,r3，寄存器 8bytes，主頻 100MHz,B=3*8*100*10,6,B/s=2.4GB/s,存儲器性能存儲器的層次結(jié)構(gòu)(C,L,B),并行與通信開銷,并行和通信開銷：相對于計(jì)算很大PowerPC (每個周期 15ns 執(zhí)行4flops;創(chuàng)建一個進(jìn)程1.4ms 可執(zhí)行372000flops),開銷的測量：乒-乓方法（Ping-Pong Scheme）節(jié)點(diǎn)0發(fā)送m個字節(jié)給節(jié)點(diǎn)1；節(jié)點(diǎn)1從節(jié)點(diǎn)0接收m個字節(jié)后，立即將消息發(fā)回節(jié)點(diǎn)0總的時間除以2，即可得到點(diǎn)到點(diǎn)通信時間，也就是執(zhí)行單一發(fā)送或接收操作的時間。

可一般化為熱土豆法（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，最后時間再除以n即可并行與通信開銷并行和通信開銷：相對于計(jì)算很大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,Ping-Pong Schemeif（my _node _,并行開銷的表達(dá)式：點(diǎn)到點(diǎn)通信,通信開銷,t,(,m,)=,t,0,+,m,/,r,通信啟動時間,t,0,漸近帶寬r,：傳送無限長的消息時的通信速率,m為傳輸?shù)淖止?jié)數(shù),半峰值長度m,1/2,：達(dá)到一半漸近帶寬所要的消息長度,特定性能,0,：表示短消息帶寬,t,0,=m,1/2,/,r,=1/,0,并行開銷的表達(dá)式：點(diǎn)到點(diǎn)通信 通信開銷 t(m)=t0,并行開銷的表達(dá)式：組通信,典型的組通信有：,播送,（Broadcasting）：處理器0發(fā)送m個字節(jié)給所有的n個處理器-,廣播,收集,（Gather）：處理0接收所有n個處理器發(fā)來在消息，所以處理器0最終接收了,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é)。

并行開銷的表達(dá)式：組通信典型的組通信有：,機(jī)器的成本、價格與性/價比,機(jī)器的成本與價格,機(jī)器的性能/價格比 Performance/Cost Ratio：系指用單位代價（通常以百萬美元表示）所獲取的性能（通常以MIPS或MFLOPS表示）,利用率（Utilization）：可達(dá)到的速度與峰值速度之比,機(jī)器的成本、價格與性/價比機(jī)器的成本與價格,并行計(jì)算性能評測,3.1 并行機(jī)的一些基本性能指標(biāo),3.2 加速比性能定律,3.2.1 Amdahl定律,3.2.2 Gustafson定律,3.2.3 Sun和Ni定律,3.3 可擴(kuò)放性評測標(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)測試程序,并行計(jì)算性能評測3.1 并行機(jī)的一些基本性能指標(biāo),算法級性能評測,加速比性能定律,并行系統(tǒng)的加速比是指對于一個給定的應(yīng)用，并行算法（或并行程序）的執(zhí)行速度相對于串行算法（或串行程序）。