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