并行計(jì)算機(jī)體系結(jié)構(gòu)第二章課件
Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,11/7/2009,,?#?,,,,,單擊此處編輯母版標(biāo)題樣式,單擊此處編輯母版文本樣式,第二級,第三級,第四級,第五級,*,,*,,,單擊此處編輯母版標(biāo)題樣式,單擊此處編輯母版文本樣式,第二級,第三級,第四級,第五級,*,,*,,,第二章,,并行計(jì)算機(jī)系統(tǒng)的性能度量,并行計(jì)算機(jī)系統(tǒng)的性能度量,硬件效率、各功能部件之間的性能平衡,軟件效率,軟硬件和需求之間的性能匹配理想的系統(tǒng)應(yīng)該是無瓶頸的平衡系統(tǒng)、結(jié)構(gòu)支持應(yīng)用，應(yīng)用適應(yīng)結(jié)構(gòu),理想的計(jì)算機(jī)是為應(yīng)用量身定制的計(jì)算機(jī),并行計(jì)算機(jī)系統(tǒng)的性能度量,衡量計(jì)算機(jī)性能的指標(biāo),,計(jì)算速度、存儲容量、響應(yīng)時(shí)間、通信帶寬和系統(tǒng)吞吐率、每條指令的平均執(zhí)行時(shí)間,,為了降低計(jì)算機(jī)成本，我們通過硬件功能的軟化實(shí)現(xiàn)，比如我們將視頻解壓卡換為信息解壓軟件2.1,計(jì)算機(jī)速度,計(jì)算機(jī)通過運(yùn)行程序來完成工作不能用一段程序的運(yùn)行時(shí)間來衡量計(jì)算機(jī)的性能，往往一段程序的運(yùn)行與它跟計(jì)算機(jī)適應(yīng)的程序相關(guān),為了客觀綜合描述計(jì)算機(jī)系能，我們往往用大量程序運(yùn)行的運(yùn)行速度進(jìn)行衡量，或者我們還可以用所謂的制定運(yùn)行庫來衡量計(jì)算機(jī)性能。
2.1,計(jì)算機(jī)速度,為了定量討論機(jī)器速度，定義下列參數(shù),ζ,：時(shí)鐘周期,f=1/,ζ,：時(shí)鐘頻率,CPI,：執(zhí)行每條指令的平均周期數(shù)IPC=1/CPI,：平均每拍流出的指令數(shù)Ic,：給定程序的指令數(shù),T,：給定程序的執(zhí)行時(shí)間TFU,：功能部件時(shí)間常數(shù)，一般為功能部件的流水線段數(shù),+2.,2.1,計(jì)算機(jī)速度,指令條數(shù),Ic,的程序的執(zhí)行時(shí)間為,T=Ic*CPI*,ζ,指令的執(zhí)行：取指令、指令譯碼、取操作數(shù)、操作、存操作數(shù)指令部件和功能部件協(xié)同完成在流水線中，指令流出時(shí)就完成了譯碼，所以每條指令有一個與操作相關(guān)的功能部件時(shí)間常數(shù)和數(shù)據(jù)傳送的最小執(zhí)行周期數(shù)對,R-R,型指令，,CPI=TFU,2.1,計(jì)算機(jī)速度,對,m-m,型指令，,CPI=TFU+mk,其中,k,為存儲器周期與時(shí)鐘周期之比，,m,為訪存次數(shù)當(dāng)訪存出現(xiàn)沖突時(shí)，導(dǎo)致,CPI,增加2.1,計(jì)算機(jī)速度,T=Ic*,（,TFU+mk,）,*,ζ,Ic,：與應(yīng)用程序、指令系統(tǒng)和編譯有關(guān)；,ζ,：機(jī)器主頻的倒數(shù)受限于指令功能的復(fù)雜程度、器件的水平和采用的技術(shù)，與指令系統(tǒng)和實(shí)現(xiàn)技術(shù)有關(guān),m,：與存儲系統(tǒng)結(jié)構(gòu)和訪存指令類型有關(guān),k,：與存儲器結(jié)構(gòu)、實(shí)現(xiàn)技術(shù)和,ζ,有關(guān)。
TFU,：與指令功能、實(shí)現(xiàn)技術(shù)和,ζ,有關(guān)2.1.1 MIPS,、,Flops,和,PDR,MIPS,速率,設(shè),C,為執(zhí)行已知程序的時(shí)鐘周期數(shù)則,T=C*t,MIPS M,指令,/,秒MIPS=I/,（,T*10,6,）,=f/(CPI*10,6,),MIPS,與時(shí)鐘頻率成正比，與,CPI,成反比,計(jì)算機(jī)系統(tǒng)中的指令系統(tǒng)、編譯器、處理器和存儲技術(shù)對,MIPS,都有影響2.1.1 MIPS,、,Flops,和,PDR,MIPS,提高,MIPS,的最有效的辦法就是提高主頻和每拍流出的指令條數(shù)為提高主頻：指令盡量簡潔，功能實(shí)現(xiàn)的邏輯時(shí)間短，推動了,RISC,的發(fā)展,為提高,IPC,：超長指令字，超標(biāo)量和并行處理機(jī)2.1.1 MIPS,、,Flops,和,PDR,Mflops,：,反映計(jì)算機(jī)每秒產(chǎn)生的結(jié)果數(shù)，不計(jì)指令僅計(jì)結(jié)果比,MIPS,公正MIPS,和,Mflops,都沒有考慮機(jī)器的字長或數(shù)據(jù)的精度但是精度與機(jī)器性能直接相關(guān)2.1.1 MIPS,、,Flops,和,PDR,PDR,：,對不同操作和字長加權(quán)后的每秒處理多少位數(shù)據(jù)用以衡量計(jì)算機(jī)的速度,PDR=L/R,L=0.85*,定點(diǎn)指令位數(shù),+0.15*,浮點(diǎn)指令數(shù),+0.4*,定點(diǎn)數(shù)字長,+0.15*,浮點(diǎn)數(shù)字長,R=0.85*,定點(diǎn)加時(shí)間,+0.09*,浮點(diǎn)加時(shí)間,+0.06*,浮點(diǎn)乘時(shí)間,2.1.2 SPEC,和,TPS,SPEC,：,為了公正的評價(jià)計(jì)算機(jī)的性能，推出基準(zhǔn)測試程序，用這些程序在被測機(jī)上運(yùn)行的時(shí)間除對應(yīng)程序的參考時(shí)間所得值的幾何平均值就是所謂的,SPEC,分?jǐn)?shù)值。
SPEC,主要針對處理器、存儲器和編譯性能的測試，不針對,I/O,和通信性能測試，尤其不適合于多機(jī)系統(tǒng)的性能評價(jià)2.1.2 SPEC,和,TPS,TPS,：,TPS,評價(jià)更佳側(cè)重于事務(wù)處理，單位時(shí)間內(nèi)完成的交易主要取決于計(jì)算機(jī)硬件的計(jì)算、,I/O,和通信速度，也取決于操作系統(tǒng)和數(shù)據(jù)庫等軟件性能2.2,并行計(jì)算機(jī)的速度計(jì)算,并行化的應(yīng)用程序在并行計(jì)算機(jī)上的執(zhí)行時(shí)間最能反映并行系統(tǒng)的處理性能與系統(tǒng)提供的性能支持、應(yīng)用程序特性、并行算法、并行程序和并行編譯水平有關(guān)應(yīng)能最大程度地利用并行系統(tǒng)中處理機(jī)資源，發(fā)揮其性能潛力2.2.1,算術(shù)平均速度,2.2.2,調(diào)和平均速度,2.2.3,幾何平均速度,2.3,并行計(jì)算機(jī)的加速比和效率,程序的并行性,并行度：并行化程序在有,p,個處理機(jī)的系統(tǒng)上運(yùn)行，使用的處理機(jī)的數(shù)目，為時(shí)間的函數(shù)，記作,DOP,（,t,）,<=p,t0-t1,期間并行度的算術(shù)平均值，稱為程序的并行性,A,2.3.2,加速比通式,加速比反映并行系統(tǒng)運(yùn)行并行程序時(shí)系統(tǒng)并行能力發(fā)揮的程度加速比定義為,,其中,T(1),是程序在單處理機(jī)上執(zhí)行完的時(shí)間，,T(n),是程序以并行度,i,（,i<=P,，其中,P,為處理機(jī)數(shù)目）并行執(zhí)行完程序的時(shí)間。
1<=S(p)<=P,2.3.2,加速比通式,多機(jī)運(yùn)行過程中，一定會有多個計(jì)算機(jī)之間的通信,,,設(shè)總工作量為,W,，并設(shè)程序中并行度為,i,的工作量為,W,i,=f,i,W,則，其中,V1,為單機(jī)運(yùn)行速度2.3.2,加速比通式,當(dāng)程序的并行度大于系統(tǒng)的處理機(jī)數(shù)時(shí)（,i>P,），應(yīng)該將,i,按,P,進(jìn)行分組，需要運(yùn)行的次數(shù)為,i/P,次，此時(shí)的加速比,,,,其中,O(n),為并行開銷，包括并行化開銷、交互開銷和通信開銷等，是一個與硬件、軟件和應(yīng)用均有關(guān)的函數(shù)目前,O(n),已經(jīng)是影響大規(guī)模并行處理系統(tǒng)性能發(fā)揮的瓶頸2.3.2,加速比通式,為了突出并行度對加速比的貢獻(xiàn)，有些加速比公式中，往往假設(shè),O(n)=0,，加速比公式將轉(zhuǎn)化為,,,其實(shí)現(xiàn)在多機(jī)系統(tǒng)中,O(n),程序研制并行系統(tǒng)的關(guān)鍵技術(shù)之一，無法忽視為,0,上述的,S(p),僅僅是理想狀態(tài)下的值書,19,頁例題,2.1,，,2.2,,,,,2.3.3,固定負(fù)載加速比,固定負(fù)載加速比中，假設(shè)只有兩種工作：串行工作和全并行工作，所謂全并行工作就是,P,臺處理器全部工作設(shè)串行工作量,W,1,=f,1,W,，,W,p,=,（,1-f,1,）,W,。
此時(shí),S(P),轉(zhuǎn)化為,,,,希望,f,1,越小越好，也被稱作串行瓶頸2.3.3,固定負(fù)載加速比,固定負(fù)載加速比中，我們發(fā)現(xiàn)只要增加并行工作的工作量比如我們把并行工作的工作量增大,P,倍，則加速比工作可以轉(zhuǎn)化為,,,,我們可以發(fā)現(xiàn)，當(dāng)并行工作量增加,P,倍的時(shí)候，在,P,臺處理機(jī)上執(zhí)行的時(shí)間和在一臺處理機(jī)上執(zhí)行的時(shí)間相同但是大家有沒有發(fā)現(xiàn)公式的問題呢？,2.3.4,固定時(shí)間加速比,在剛剛的公式中，我們發(fā)現(xiàn)公式的問題也就是并行工作量增加了,p,倍之后，分子上的并行工作量并未隨著發(fā)生改變在此基礎(chǔ)上我們導(dǎo)出固定時(shí)間加速比,,,,,,,2.3.5,固定存儲加速比,在多機(jī)系統(tǒng)中，處理機(jī)數(shù)擴(kuò)展至,P,倍，系統(tǒng)的存儲能力也應(yīng)該做相應(yīng)的增加對于有些空間復(fù)雜性低于時(shí)間復(fù)雜性的科學(xué)計(jì)算問題，系統(tǒng)存儲容量的增大，可支持更大的并行工作量的增加，增加的倍數(shù)為,G(p),倍（,G(P)>=P,）G(P),受限于存儲器的容量則得到如下加速比公式,,,,,,2.3.5,固定存儲加速比,在上面的公式中，如果多計(jì)算系統(tǒng)中的存儲器不是全局共享，則,G(P)=P,，此時(shí)變成固定時(shí)間加速比當(dāng)并行負(fù)載并不增加時(shí)，變成固定負(fù)載加速比。
一般情況下隨著存儲容量的增加，其并行工作量的增加,G(P)>P,，所以固定負(fù)載加速比會比固定時(shí)間加速比有更好的加速能力和可擴(kuò)展性書,22,頁例題,2.3,2.3.6,粒度匹配加速比模型,前面我們提到的并行程序不包括并行化和任務(wù)間的互操作開銷并行化包括進(jìn)行的管理、分配和查詢等操作，開銷來自軟件系統(tǒng)；互操作包括進(jìn)程間的同步、通信和集散等操作，開銷取決于同步與通信系統(tǒng)的性能而并行化和互操作開銷往往與程序的粒度緊密結(jié)合2.3.6,粒度匹配加速比模型,補(bǔ)充：粒度及相關(guān)概念,粒度：衡量軟件進(jìn)程包含計(jì)算量的尺度比如程序段中的指令數(shù)目粒度分為粗、中、細(xì)三種粒度時(shí)延：各子系統(tǒng)之間通信開銷的時(shí)間度量例如存儲器的時(shí)延就是存儲器完成一次讀寫鎖完成的時(shí)間，處理器時(shí)間就是各個處理器之間互相同步的時(shí)間存儲器容量越大時(shí)延越大，處理器數(shù)目越多時(shí)延越大粒度與時(shí)延密切相關(guān)2.3.6 粒度匹配加速比模型,作業(yè)或程序,子程序，部分作業(yè)或程序,過程、子程序和任務(wù),非遞歸循環(huán)或迭代,指令或語句,并,行,性,程,度,,,,細(xì)粒度,中粒度,粗粒度,通,信,開,銷,增,加,2.3.6 粒度匹配加速比模型,指令級：粒度一般包含的指令數(shù)小于,20,。
細(xì)粒度的并行性在,2~,數(shù)千范圍變化優(yōu)點(diǎn)：可以充分利用機(jī)器資源細(xì)粒度并行性的開發(fā)可以借助于優(yōu)化編譯器，自動檢測并行性，并將源代碼變成運(yùn)行時(shí)系統(tǒng)能識別的并行形式2.3.6 粒度匹配加速比模型,循環(huán)級：循環(huán)操作在連續(xù)迭代中不相關(guān)，循環(huán)級并行性是在并行或者向量計(jì)算機(jī)上運(yùn)行的最有程序結(jié)構(gòu)但是遞歸循環(huán)的并行性優(yōu)化難以實(shí)現(xiàn)2.3.6 粒度匹配加速比模型,作業(yè)級：對應(yīng)在并行處理機(jī)上并行執(zhí)行的獨(dú)立作業(yè)，粒度在單個程序中可以達(dá)到數(shù)萬條指令作業(yè)級并行性一般由加載程序和操作系統(tǒng)來處理2.3.6 粒度匹配加速比模型,細(xì)粒度并行性在指令級或循環(huán)級上借助并行化或向量化編譯器來開發(fā)，中粒度并行性的開發(fā)需要程序員和編譯器協(xié)同工作，粗粒度級的并行性取決于高效的操作系統(tǒng)和算法效率共享變量通信支持細(xì)粒度和中粒度，消息傳遞多計(jì)算機(jī)用于中粒度和粗粒度2.3.6 粒度匹配加速比模型,通信時(shí)延：不同的通信時(shí)延是由計(jì)算機(jī)體系結(jié)構(gòu)、實(shí)現(xiàn)技術(shù)和通信方式?jīng)Q定的時(shí)延是機(jī)器規(guī)模擴(kuò)展的限制因素比如存儲器時(shí)延隨著容量的增加而增大，所以存儲器的容量不能無限制的增大通信方式由算法和系統(tǒng)結(jié)構(gòu)決定并行系統(tǒng)：縮小通信時(shí)延、防止死鎖、優(yōu)化粒度,2.3.6 粒度匹配加速比模型,并行程序設(shè)計(jì)的兩個基本問題：,,1.,如何將一個程序分解為合適的粒度。
以便獲得盡可能短的運(yùn)行時(shí)間2.,在計(jì)算中最佳的并行粒度是多大2.3.6 粒度匹配加速比模型,組合粒度前程序圖,細(xì)粒度,每個節(jié)點(diǎn)用（,n,s,）,表示n,為節(jié)點(diǎn)名,s,為節(jié)點(diǎn)粒度兩個節(jié)點(diǎn)之間的邊,記為（,v,d,），,v,表示,輸出或者輸入的變量,d,表示節(jié)點(diǎn)之間的通,信延時(shí),,組合粒度后,程序圖,粗粒度,,粗細(xì)粒度比較,2.3.6 粒度匹配加速比模型,粒度組合先用細(xì)粒度獲得較高的并行度，然后分析加大粒度是否會消除一些不必要的通信延遲或降低總的調(diào)度開銷細(xì)粒度可以更好的利用資源，但是可能需要更多的處理機(jī)之間的通信粒度組合需要在并行性和調(diào)度開銷中間取折中,2.3.6 粒度匹配加速比模型,單一依靠粒度組合，不一定就能得到一個好的調(diào)度調(diào)度方案動態(tài)處理機(jī)調(diào)度是,NP,難解問題，通常需要采用啟發(fā)式方法以便得到局部優(yōu)解我們主要介紹靜態(tài)處理機(jī)調(diào)度方式2.3.6 粒度匹配加速比模型,結(jié)點(diǎn)復(fù)制：將某一處理機(jī)上的數(shù)據(jù)復(fù)制到其他處理機(jī)，達(dá)到降低處理機(jī)間通信延遲的目標(biāo)結(jié)點(diǎn)復(fù)制前后調(diào)服方案,2.3.6 粒度匹配加速比模型,通常需要將粒度組合和結(jié)點(diǎn)復(fù)制結(jié)合起來來確定最佳力度和調(diào)度方案步驟：,,1.,構(gòu)造細(xì)粒度程序圖,,2.,調(diào)度細(xì)粒度運(yùn)算,,3.,進(jìn)行力度組合得到粗粒度,,4.,在組合圖基礎(chǔ)上產(chǎn)生并行調(diào)度方案,2.3.6 粒度匹配加速比模型,靜態(tài)多處理機(jī)調(diào)度的程序分解,2.3.6 粒度匹配加速比模型,1.,細(xì)粒度分解：,乘法器,101,個周期,加法器,8,個周期,2.3.6 粒度匹配加速比模型,1.,細(xì)粒度分解：通信時(shí)間分析,T1=T2=T4=T5=20,T3=32,串行通信時(shí)間,T6= 100,通信軟件協(xié)議延遲,d=T1+T2+T3+T4+T5+T6,M,M,2.3.6 粒度匹配加速比模型,2.,調(diào)度細(xì)粒度運(yùn)算：,,2.3.6 粒度匹配加速比模型,2.,評價(jià)：,,2.3.6 粒度匹配加速比模型,3.,進(jìn)行粒度組合得到粗粒度：,,2.3.6 粒度匹配加速比模型,3.,組合得到粗粒度產(chǎn)生并行調(diào)度方案：,,2.3.6,粒度匹配加速比模型,下面我們進(jìn)行粒度分析,V1,：節(jié)點(diǎn)機(jī)的平均速度；,P,：節(jié)點(diǎn)機(jī)數(shù)目；,W,：網(wǎng)絡(luò)的統(tǒng)計(jì)平均通信帶寬；,t,：每次同步的平均時(shí)間,Ic,：程序的指令條數(shù)；,f1,：串行瓶頸；,1-f1,：程序中,P,并行度指令百分比；,e,m,：并行負(fù)載系數(shù),N,：程序執(zhí)行過程中的同步次數(shù)；,B:,每次通訊時(shí)一個節(jié)點(diǎn)向另一個節(jié)點(diǎn)發(fā)送的字節(jié)數(shù),K:,每次通信時(shí)一個節(jié)點(diǎn)需要通信的節(jié)點(diǎn)數(shù),T0:,每次通信的軟件開銷,Tb,：每次通信的平均延遲時(shí)間,β,：通信隱藏系數(shù)，并行計(jì)算與通信重疊時(shí)間占通信時(shí)間的百分比,2.3.6,粒度匹配加速比模型,設(shè)在,P,臺機(jī)器上執(zhí)行的時(shí)間為,T(P),，同步時(shí)間為,Ts,，通信時(shí)間為,Tc,2.3.6,粒度匹配加速比模型,2.3.6,粒度匹配加速比模型,G,s,=V,1,t,，被稱為同步粒度，為每次同步損失的節(jié)點(diǎn)計(jì)算量。
與系統(tǒng)同步機(jī)制和結(jié)點(diǎn)速度有關(guān)G,o,=V,1,T,0,，系統(tǒng)開銷粒度，每次通信的系統(tǒng)開銷時(shí)間損失的節(jié)點(diǎn)計(jì)算量與系統(tǒng)通信機(jī)制和節(jié)點(diǎn)速度有關(guān),G,b,=V,1,T,b,，系統(tǒng)延遲粒度，每次通信時(shí)建立時(shí)間和阻塞時(shí)間引起的延遲損失的節(jié)點(diǎn)計(jì)算量與節(jié)點(diǎn)存儲器、網(wǎng)絡(luò)接口、特性、消息特性和節(jié)點(diǎn)速度有關(guān)G,c,=V,1,/W,，系統(tǒng)通信帶寬對節(jié)點(diǎn)速度的支持能力，與網(wǎng)絡(luò)帶寬和節(jié)點(diǎn)速度有關(guān)2.3.6,粒度匹配加速比模型,g,s,=I,c,/N,，應(yīng)用同步粒度，兩次同步間平均執(zhí)行的指令條數(shù)取決于程序特性,g,b,=I,c,/NK,，應(yīng)用延遲粒度，每次通信延遲時(shí)間內(nèi)執(zhí)行的指令條數(shù)g,c,=I,c,/NPKB,，通信的單位字節(jié)平均支持的指令條數(shù),e,m,反映各節(jié)點(diǎn)不行負(fù)載的不平衡程度，,e,m,=1,說明各個結(jié)點(diǎn)負(fù)載時(shí)平衡的書,25,頁，例題,2.4,并行系統(tǒng)的效率和可擴(kuò)展性,加速比,S(P),的最大值，應(yīng)該是系統(tǒng)的結(jié)點(diǎn)數(shù),P,實(shí)際受到串行瓶頸、負(fù)載不平衡、同步和通信開銷等問題，實(shí)際,S(p) 并行性好的系統(tǒng)，加速比應(yīng)隨并行度的增加而線性增加，或者效率隨并行度的增加而保持常數(shù)我們用,C(P),來表示可擴(kuò)展性并行系統(tǒng)的效率和可擴(kuò)展性,C(P)=E(P)/E’(P),，其中,E’(P),是忽略了并行開銷時(shí)的系統(tǒng)效率C(P)= E(P)/E’(P)= S(P)/S’(P)=1/[1+O(P)/T(P)],C(P),值越大系統(tǒng)可擴(kuò)展性越好這里的,O(P),是總的并行開銷，包括同步和通信開銷并行系統(tǒng)的效率和可擴(kuò)展性,為考察相對量的變化對可擴(kuò)展性的影響，將,C,（,P,）定義為,,,,當(dāng),C(P)<=0,時(shí)，系統(tǒng)是不可擴(kuò)展的；,0 U(P)=R(P)E(P),如果處理機(jī)的,CPI=1,，則有,I(1)=T(1),，此時(shí)有,2.3.8,并行系統(tǒng)的并行質(zhì)量,,并行計(jì)算質(zhì)量是用加速比、效率和冗余度的綜合效果來表征在并行系統(tǒng)上并行計(jì)算的相對性能并行計(jì)算的質(zhì)量用,Q(P),來表示Q(P)=S(P)E(P)/R(P),,,,,內(nèi)容總結(jié),第二章 并行計(jì)算機(jī)系統(tǒng)的性能度量TFU：功能部件時(shí)間常數(shù)，一般為功能部件的流水線段數(shù)+2.指令部件和功能部件協(xié)同完成對R-R型指令，CPI=TFU對m-m型指令，CPI=TFU+mkMIPS與時(shí)鐘頻率成正比，與CPI成反比MIPS和Mflops都沒有考慮機(jī)器的字長或數(shù)據(jù)的精度t0-t1期間并行度的算術(shù)平均值，稱為程序的并行性A上述的S(p)僅僅是理想狀態(tài)下的值比如我們把并行工作的工作量增大P倍，則加速比工作可以轉(zhuǎn)化為當(dāng)并行負(fù)載并不增加時(shí)，變成固定負(fù)載加速比前面我們提到的并行程序不包括并行化和任務(wù)間的互操作開銷存儲器容量越大時(shí)延越大，處理器數(shù)目越多時(shí)延越大作業(yè)級：對應(yīng)在并行處理機(jī)上并行執(zhí)行的獨(dú)立作業(yè)，粒度在單個程序中可以達(dá)到數(shù)萬條指令單一依靠粒度組合，不一定就能得到一個好的調(diào)度調(diào)度方案gc=Ic/NPKB，通信的單位字節(jié)平均支持的指令條數(shù)。 0
