并行計算機(jī)體系結(jié)構(gòu)第二章

1、第二章 并行計算機(jī)系統(tǒng)的性能度量并行計算機(jī)系統(tǒng)的性能度量硬件效率、各功能部件之間的性能平衡軟件效率軟硬件和需求之間的性能匹配。理想的系統(tǒng)應(yīng)該是無瓶頸的平衡系統(tǒng)、結(jié)構(gòu)支持應(yīng)用，應(yīng)用適應(yīng)結(jié)構(gòu)理想的計算機(jī)是為應(yīng)用量身定制的計算機(jī)并行計算機(jī)系統(tǒng)的性能度量衡量計算機(jī)性能的指標(biāo) 計算速度、存儲容量、響應(yīng)時間、通信帶寬和系統(tǒng)吞吐率、每條指令的平均執(zhí)行時間為了降低計算機(jī)成本，我們通過硬件功能的軟化實現(xiàn)，比如我們將視頻解壓卡換為信息解壓軟件。2.1 計算機(jī)速度計算機(jī)通過運行程序來完成工作。不能用一段程序的運行時間來衡量計算機(jī)的性能，往往一段程序的運行與它跟計算機(jī)適應(yīng)的程序相關(guān)為了客觀綜合描述計算機(jī)系能，我們往往

2、用大量程序運行的運行速度進(jìn)行衡量，或者我們還可以用所謂的制定運行庫來衡量計算機(jī)性能。2.1 計算機(jī)速度為了定量討論機(jī)器速度，定義下列參數(shù)：時鐘周期f=1/ ：時鐘頻率CPI：執(zhí)行每條指令的平均周期數(shù)。IPC=1/CPI：平均每拍流出的指令數(shù)。Ic：給定程序的指令數(shù)T：給定程序的執(zhí)行時間。TFU：功能部件時間常數(shù)，一般為功能部件的流水線段數(shù)+2.2.1 計算機(jī)速度指令條數(shù)Ic的程序的執(zhí)行時間為T=Ic*CPI* 。指令的執(zhí)行：取指令、指令譯碼、取操作數(shù)、操作、存操作數(shù)。指令部件和功能部件協(xié)同完成。在流水線中，指令流出時就完成了譯碼，所以每條指令有一個與操作相關(guān)的功能部件時間常數(shù)和數(shù)據(jù)傳送的最小執(zhí)

3、行周期數(shù)。對R-R型指令，CPI=TFU。2.1 計算機(jī)速度對m-m型指令，CPI=TFU+mk。其中k為存儲器周期與時鐘周期之比，m為訪存次數(shù)。當(dāng)訪存出現(xiàn)沖突時，導(dǎo)致CPI增加。2.1 計算機(jī)速度T=Ic*（TFU+mk）* Ic：與應(yīng)用程序、指令系統(tǒng)和編譯有關(guān)；：機(jī)器主頻的倒數(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和PDRMIPS速率 設(shè)C為執(zhí)行已知程序的時鐘周期數(shù)。則T=C*t MIPS M指令/秒。 MIPS=I

4、/（T*106）=f/(CPI*106) MIPS與時鐘頻率成正比，與CPI成反比 計算機(jī)系統(tǒng)中的指令系統(tǒng)、編譯器、處理器和存儲技術(shù)對MIPS都有影響。2.1.1 MIPS、Flops和PDRMIPS提高M(jìn)IPS的最有效的辦法就是提高主頻和每拍流出的指令條數(shù)。為提高主頻：指令盡量簡潔，功能實現(xiàn)的邏輯時間短，推動了RISC的發(fā)展為提高IPC：超長指令字，超標(biāo)量和并行處理機(jī)。2.1.1 MIPS、Flops和PDRMflops：反映計算機(jī)每秒產(chǎn)生的結(jié)果數(shù)，不計指令僅計結(jié)果比MIPS公正。MIPS和Mflops都沒有考慮機(jī)器的字長或數(shù)據(jù)的精度。但是精度與機(jī)器性能直接相關(guān)。2.1.1 MIPS、Flo

5、ps和PDRPDR：對不同操作和字長加權(quán)后的每秒處理多少位數(shù)據(jù)。用以衡量計算機(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和TPSSPEC：為了公正的評價計算機(jī)的性能，推出基準(zhǔn)測試程序，用這些程序在被測機(jī)上運行的時間除對應(yīng)程序的參考時間所得值的幾何平均值就是所謂的SPEC分?jǐn)?shù)值。SPEC主要針對處理器、存儲器和編譯性能的測試，不針對I/O和通信性能測試，尤其不適合于多機(jī)系統(tǒng)的性能評價。2.1.2 SPEC和TPSTPS：TPS評價更佳側(cè)重

6、于事務(wù)處理，單位時間內(nèi)完成的交易。主要取決于計算機(jī)硬件的計算、I/O和通信速度，也取決于操作系統(tǒng)和數(shù)據(jù)庫等軟件性能。2.2 并行計算機(jī)的速度計算并行化的應(yīng)用程序在并行計算機(jī)上的執(zhí)行時間最能反映并行系統(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ī)的加速比和效率程序的并行性并行度：并行化程序在有p個處理機(jī)的系統(tǒng)上運行，使用的處理機(jī)的數(shù)目，為時間的函數(shù)，記作DOP（t）=p。t0-t1期間并行度的算術(shù)平均值，稱為程

7、序的并行性A。2.3.2 加速比通式加速比反映并行系統(tǒng)運行并行程序時系統(tǒng)并行能力發(fā)揮的程度。加速比定義為其中T(1)是程序在單處理機(jī)上執(zhí)行完的時間，T(n)是程序以并行度i（i=P，其中P為處理機(jī)數(shù)目）并行執(zhí)行完程序的時間。1=S(p)P），應(yīng)該將i按P進(jìn)行分組，需要運行的次數(shù)為i/P次，此時的加速比其中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)化為其實現(xiàn)在多機(jī)系統(tǒng)中O(n)程序研

8、制并行系統(tǒng)的關(guān)鍵技術(shù)之一，無法忽視為0。上述的S(p)僅僅是理想狀態(tài)下的值。書19頁例題2.1，2.22.3.3 固定負(fù)載加速比固定負(fù)載加速比中，假設(shè)只有兩種工作：串行工作和全并行工作，所謂全并行工作就是P臺處理器全部工作。設(shè)串行工作量W1=f1W，Wp=（1-f1）W。此時S(P)轉(zhuǎn)化為希望f1越小越好，也被稱作串行瓶頸。2.3.3 固定負(fù)載加速比固定負(fù)載加速比中，我們發(fā)現(xiàn)只要增加并行工作的工作量。比如我們把并行工作的工作量增大P倍，則加速比工作可以轉(zhuǎn)化為我們可以發(fā)現(xiàn)，當(dāng)并行工作量增加P倍的時候，在P臺處理機(jī)上執(zhí)行的時間和在一臺處理機(jī)上執(zhí)行的時間相同。但是大家有沒有發(fā)現(xiàn)公式的問題呢？2.3.

9、4 固定時間加速比在剛剛的公式中，我們發(fā)現(xiàn)公式的問題。也就是并行工作量增加了p倍之后，分子上的并行工作量并未隨著發(fā)生改變。在此基礎(chǔ)上我們導(dǎo)出固定時間加速比2.3.5 固定存儲加速比在多機(jī)系統(tǒng)中，處理機(jī)數(shù)擴(kuò)展至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ù)載加速比。一般

10、情況下隨著存儲容量的增加，其并行工作量的增加G(P)P，所以固定負(fù)載加速比會比固定時間加速比有更好的加速能力和可擴(kuò)展性。書22頁例題2.32.3.6 粒度匹配加速比模型前面我們提到的并行程序不包括并行化和任務(wù)間的互操作開銷。并行化包括進(jìn)行的管理、分配和查詢等操作，開銷來自軟件系統(tǒng)；互操作包括進(jìn)程間的同步、通信和集散等操作，開銷取決于同步與通信系統(tǒng)的性能。而并行化和互操作開銷往往與程序的粒度緊密結(jié)合。2.3.6 粒度匹配加速比模型補(bǔ)充：粒度及相關(guān)概念粒度：衡量軟件進(jìn)程包含計算量的尺度。比如程序段中的指令數(shù)目。粒度分為粗、中、細(xì)三種粒度。時延：各子系統(tǒng)之間通信開銷的時間度量。例如存儲器的時延就是存

11、儲器完成一次讀寫鎖完成的時間，處理器時間就是各個處理器之間互相同步的時間。存儲器容量越大時延越大，處理器數(shù)目越多時延越大。粒度與時延密切相關(guān)。2.3.6 粒度匹配加速比模型作業(yè)或程序子程序，部分作業(yè)或程序過程、子程序和任務(wù)非遞歸循環(huán)或迭代指令或語句并行性程度細(xì)粒度中粒度粗粒度通信開銷增加2.3.6 粒度匹配加速比模型指令級：粒度一般包含的指令數(shù)小于20。細(xì)粒度的并行性在2數(shù)千范圍變化。 優(yōu)點：可以充分利用機(jī)器資源。細(xì)粒度并行性的開發(fā)可以借助于優(yōu)化編譯器，自動檢測并行性，并將源代碼變成運行時系統(tǒng)能識別的并行形式。2.3.6 粒度匹配加速比模型循環(huán)級：循環(huán)操作在連續(xù)迭代中不相關(guān)，循環(huán)級并行性是在并

12、行或者向量計算機(jī)上運行的最有程序結(jié)構(gòu)。但是遞歸循環(huán)的并行性優(yōu)化難以實現(xiàn)。2.3.6 粒度匹配加速比模型作業(yè)級：對應(yīng)在并行處理機(jī)上并行執(zhí)行的獨立作業(yè)，粒度在單個程序中可以達(dá)到數(shù)萬條指令。作業(yè)級并行性一般由加載程序和操作系統(tǒng)來處理。2.3.6 粒度匹配加速比模型細(xì)粒度并行性在指令級或循環(huán)級上借助并行化或向量化編譯器來開發(fā)，中粒度并行性的開發(fā)需要程序員和編譯器協(xié)同工作，粗粒度級的并行性取決于高效的操作系統(tǒng)和算法效率。共享變量通信支持細(xì)粒度和中粒度，消息傳遞多計算機(jī)用于中粒度和粗粒度。2.3.6 粒度匹配加速比模型通信時延：不同的通信時延是由計算機(jī)體系結(jié)構(gòu)、實現(xiàn)技術(shù)和通信方式?jīng)Q定的。時延是機(jī)器規(guī)模擴(kuò)展

13、的限制因素。比如存儲器時延隨著容量的增加而增大，所以存儲器的容量不能無限制的增大。通信方式由算法和系統(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ì)粒度獲得較高的并行度，

14、然后分析加大粒度是否會消除一些不必要的通信延遲或降低總的調(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é)點復(fù)制：將某一處理機(jī)上的數(shù)據(jù)復(fù)制到其他處理機(jī)，達(dá)到降低處理機(jī)間通信延遲的目標(biāo)。結(jié)點復(fù)制前后調(diào)服方案2.3.6 粒度匹配加速比模型通常需要將粒度組合和結(jié)點復(fù)制結(jié)合起來來確定最佳力度和調(diào)度方案。步驟： 1.構(gòu)造細(xì)粒度程

15、序圖 2.調(diào)度細(xì)粒度運算 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ì)粒度分解：通信時間分析T1=T2=T4=T5=20T3=32 串行通信時間T6= 100 通信軟件協(xié)議延遲d=T1+T2+T3+T4+T5+T6MM2.3.6 粒度匹配加速比模型2.調(diào)度細(xì)粒度運算：2.3.6 粒度匹配加速比模型2.評價：2.3.6 粒度匹配加速比模型3.進(jìn)行粒度組合得到粗粒度：2.3.6 粒度匹配加速比模型3. 組合得

16、到粗粒度產(chǎn)生并行調(diào)度方案：2.3.6 粒度匹配加速比模型下面我們進(jìn)行粒度分析V1：節(jié)點機(jī)的平均速度；P：節(jié)點機(jī)數(shù)目；W：網(wǎng)絡(luò)的統(tǒng)計平均通信帶寬；t：每次同步的平均時間Ic：程序的指令條數(shù)；f1：串行瓶頸；1-f1：程序中P并行度指令百分比；em：并行負(fù)載系數(shù)N：程序執(zhí)行過程中的同步次數(shù)；B:每次通訊時一個節(jié)點向另一個節(jié)點發(fā)送的字節(jié)數(shù)K:每次通信時一個節(jié)點需要通信的節(jié)點數(shù)T0:每次通信的軟件開銷Tb：每次通信的平均延遲時間：通信隱藏系數(shù)，并行計算與通信重疊時間占通信時間的百分比2.3.6 粒度匹配加速比模型設(shè)在P臺機(jī)器上執(zhí)行的時間為T(P)，同步時間為Ts，通信時間為Tc2.3.6 粒度匹配加速

17、比模型2.3.6 粒度匹配加速比模型Gs=V1t，被稱為同步粒度，為每次同步損失的節(jié)點計算量。與系統(tǒng)同步機(jī)制和結(jié)點速度有關(guān)。Go=V1T0，系統(tǒng)開銷粒度，每次通信的系統(tǒng)開銷時間損失的節(jié)點計算量。與系統(tǒng)通信機(jī)制和節(jié)點速度有關(guān)Gb=V1Tb，系統(tǒng)延遲粒度，每次通信時建立時間和阻塞時間引起的延遲損失的節(jié)點計算量。與節(jié)點存儲器、網(wǎng)絡(luò)接口、特性、消息特性和節(jié)點速度有關(guān)。Gc=V1/W，系統(tǒng)通信帶寬對節(jié)點速度的支持能力，與網(wǎng)絡(luò)帶寬和節(jié)點速度有關(guān)。2.3.6 粒度匹配加速比模型gs=Ic/N，應(yīng)用同步粒度，兩次同步間平均執(zhí)行的指令條數(shù)。取決于程序特性gb=Ic/NK，應(yīng)用延遲粒度，每次通信延遲時間內(nèi)執(zhí)行的指

18、令條數(shù)。gc=Ic/NPKB，通信的單位字節(jié)平均支持的指令條數(shù)em反映各節(jié)點不行負(fù)載的不平衡程度， em =1說明各個結(jié)點負(fù)載時平衡的。書25頁，例題2.42.3.7并行系統(tǒng)的效率和可擴(kuò)展性加速比S(P)的最大值，應(yīng)該是系統(tǒng)的結(jié)點數(shù)P。實際受到串行瓶頸、負(fù)載不平衡、同步和通信開銷等問題，實際S(p)P。為了表征并行系統(tǒng)加速比接近P的程序，用效率E(P)進(jìn)行描述。 E(P) = S(p)/P。E(p) 越大系統(tǒng)可擴(kuò)展性越好。并行性好的系統(tǒng)，加速比應(yīng)隨并行度的增加而線性增加，或者效率隨并行度的增加而保持常數(shù)。我們用C(P)來表示可擴(kuò)展性。2.3.7并行系統(tǒng)的效率和可擴(kuò)展性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)可擴(kuò)展性越好。這里的O(P)是總的并行開銷，包括同步和通信開銷。2.3.7并行系統(tǒng)的效率和可擴(kuò)展性為考察相對量的變化對可擴(kuò)展性的影響，將C（P）定義為當(dāng)C(P)=0時，系統(tǒng)是不可擴(kuò)展的；0C(P)=1時，是超線性可擴(kuò)展的。2.3.8 并行系統(tǒng)的并行質(zhì)量并行計