并行計算29中科大教案體系結構lec03evaluation

ParallelComputerArchitecture

并行計算機體系結構

Lecture4OverviewReviewofLec2性能評測機器級性能評測算法級性能評測程序級性能評測ReviewofLec2FundamentalDesignIssuesNaming:Howarelogicallyshareddataand/orprocessesreferenced?Operations:WhatoperationsareprovidedonthesedataOrdering:Howareaccessestodataorderedandcoordinated?Replication:Howaredatareplicatedtoreducecommunication?CommunicationCost:Latency,bandwidth,overhead,occupancySequentialProgrammingmodelSASMessagePassingProgramexampleReviewoflec2(cont’d)MainParallelComputerArchitectureParallelComputingModel同步PRAM異步PRAMBSPLogPOtherissue:同步Moreissues(intextbook1.5)并行化技術相關性分析：流相關反相關輸出相關控制相關并行調試斷點調試事件分析重放相關性分析假定語句Sj繼Si之后執(zhí)行流相關（flowdependent)：如果從Si到Sj存在執(zhí)行通路，而且Si至少有一個輸出作為Sj的輸入。反相關(antidependent)：如果Sj緊接Si，Sj的輸出與Si的輸入重疊。輸出相關(outputdependent)：如果兩語句能產(chǎn)生統(tǒng)一輸出變量?？刂葡嚓P(controldependent)：如果語句Sj的執(zhí)行依賴于語句Si。例子代碼優(yōu)化代碼向量化代碼并行化并行程序的調試與分析：并行化導致程序語句執(zhí)行次序運行不確定無法通過運行測試來保證程序的正確性探針效應三種方法：斷點調試、事件分析、重放靜態(tài)性能分析：模擬分析的方法對占用時間較多的程序結構進行分析。時間代價小。動態(tài)性能分析：用硬件獲取運行時數(shù)據(jù)，如有關CPU性能的參數(shù)、通信模式、訪存模式、同步通信頻率等，或軟件提供諸如并行度、負載平衡、等待時間等。國產(chǎn)曙光并行機 曙光一號：SMP,32CPU,<0.1G曙光1000：MPP,36CPU,2G曙光2000：Cluster,26CPU,25G小結Convergence軟硬件結合研究的幾個問題：多節(jié)點系統(tǒng)節(jié)點內的并行性并行機的存儲問題格點計算并行計算模型若干新技術：光技術超導計算機量子計算機分子計算機OverviewReviewofLec2性能評測機器級性能評測算法級性能評測程序級性能評測Chapter2性能評測主要內容什么是并行計算機的基本性能?為什么要研究機器的性能評測？如何評測計算機的性能？如何提高并行系統(tǒng)的性能計算機的性能Performance:

通常是指機器的速度，它是程序執(zhí)行時間的倒數(shù)。程序執(zhí)行時間：是指用戶的響應時間(訪問磁盤和訪問存儲器的時間，CPU時間，I/O時間以及操作系統(tǒng)的開銷)CPU時間：它表示CPU的工作時間，不包括I/O等待時間和運行其它任務的時間。

CPU性能公式機器的時鐘周期為TC，程序中指令總條數(shù)為IN，執(zhí)行每條指令所需的平均時鐘周期數(shù)為CPI，則一個程序在CPU上運行的時間TCPU為：

TCPU=IN×CPI×TC

（2.1）

MIPS(MillionInstructionsPerSecond)MIPS=IN/（TE×106）=RC/（CPI×106

）(2.4)MIPSRel=（TRef/TV

）×MIPSRef

MFLOPS(MillionFloatingPointOperationsPerSecond)MFLOPS=IFN/（TE×106）并行機的性能指標名

稱符

號含

意單

位機器規(guī)模n處理器的數(shù)目無量綱時鐘速率f時鐘周期長度的倒數(shù)MHZ工作負載W計算操作的數(shù)目Mflop順序執(zhí)行時間T1程序在單處理機上的運行時間s（秒）并行執(zhí)行時間Tn程序在并行機上的運行時間s（秒）速度Rn=W/Tn每秒百萬次浮點運算Mflop/s加速Sn=T1/Tn衡量并行機有多快無量綱效率En=Sn/n衡量處理器的利用率無量綱峰值速度Rpeak=nR’

peak所有處理器峰值速度之積，

R’peak為一個處理器的峰值速度Mflop/s利用率U=Rn/Rpeak可達速度與峰值速度之比無量綱通信延遲to傳送0-字節(jié)或單字的時間Μs漸近帶寬r∞傳送長消息通信速率MB/s并行機性能評測的意義發(fā)揮并行機長處，提高并行機的使用效率減少用戶購機盲目性，降低投資風險改進系統(tǒng)結構設計，提高機器的性能促進軟/硬件結合，合理功能劃分優(yōu)化“結構-算法-應用”的最佳組合提供客觀、公正的評價并行機的標準如何進行并行機性能評測機器級性能評測：CPU和存儲器的某些基本性能指標；并行和通信開銷分析；并行機的可用性與好用性以及機器成本、價格與性/價比算法級性能評測：加速比、效率、擴展性程序級性能評測：Benchmark機器級性能評測CPU的某些基本性能指標工作負載執(zhí)行時間浮點運算數(shù)指令數(shù)目并行執(zhí)行時間Tcomput

為計算時間，Tparo為并行開銷時間，Tcomm為相互通信時間

Tn=Tcomput+Tparo+Tcomm機器級性能評測（cont)存儲器的層次結構(C,L,B)估計存儲器的帶寬RISCaddr1,r2,r3register8bytes100MHzB=3*8*100*106B/s=2.4GB/s機器級性能評測（cont)并行和通信開銷：相對于計算很大。

PowerPC(每個周期15ns執(zhí)行4flops;

創(chuàng)建一個進程1.4ms可執(zhí)行372000flops)開銷的測量：乒--乓方法（Ping-PongScheme）節(jié)點0發(fā)送m個字節(jié)給節(jié)點1；節(jié)點1從節(jié)點0接收m個字節(jié)后，立即將消息發(fā)回節(jié)點0?？偟臅r間除以2，即可得到點到點通信時間，也就是執(zhí)行單一發(fā)送或接收操作的時間?？梢话慊癁闊嵬炼狗ǎ℉ot-Potato），也稱為救火隊法（Fire-Brigade)0——1——2——

…

——-n-1——0Ping-PongSchemeif（my_node_id=0）then/*發(fā)送者*/ start_time=second（）

sendanm-bytemessagetonode1 receiveanm-bytemessagefromnode1 end_time=second（）

total_time=end_time–start_timecommunication_time[i]=total_time/2 elseif（my_node_id=1）then/*接收者*/ receiveanm-bytemessagefromnode0 sendanm-bytemessagetonode0 endif并行開銷的表達式：點到點通信Transfertime(n)=T0+n/Busefulformessagepassing,memoryaccess,vectoropsetcAsnincreases,bandwidthapproachesasymptoticrateBHowquicklyitapproachesdependsonT0Sizeneededforhalfbandwidth(half-powerpoint):n1/2=T0Bπ0（MB/S），表示短消息帶寬T0=n1/2/B=1/π0

并行開銷的表達式：整體通信典型的整體通信有：播送（Broadcasting）：處理器0發(fā)送m個字節(jié)給所有的n個處理器收集（Gather）：處理0接收所有n個處理器發(fā)來在消息，所以處理器0最終接收了mn個字節(jié)；散射（Scatter）：處理器0發(fā)送了m個字節(jié)的不同消息給所有n個處理器，因此處理器0最終發(fā)送了mn個字節(jié)；全交換（TotalExchange）：每個處理器均彼此相互發(fā)送m個字節(jié)的不同消息給對方，所以總通信量為mn2個字節(jié)；循環(huán)移位（Circular-shift）：處理器i發(fā)送m個字節(jié)給處理器i+1，處理器n-1發(fā)送m個字節(jié)給處理器0，所以通信量為mn個字節(jié)。

T（m，n）=t0（n）+m/r∞（n）（2.17）SP2機器整體通信和路障同步開銷表達式整體通信操作表達式播送52logn+（0.029logn）m收集/散射（17logn+15）+（0.025n-0.02）m全交換80logn+（0.03n1.29）m循環(huán)移位（6logn+60）+（0.003logn+0.04）m路障同步94logn+10RAS可靠性（Reliability）：平均無故障時間MTTF（MeanTimeToFail）系指系統(tǒng)失效前平均正常運行的時間；服務性（Serviceability）:平均修復時間MTTR（MeanTimeToRepair）來度量，系指系統(tǒng)失效后修理恢復正常工作的時間可用性（Availability）

Availability=MTTF/（MTTF+MTTR）并行機的好用性目前的用戶環(huán)境：遠程登錄結合命令行GUI＋X協(xié)議客戶GUI＋服務器Web服務器＋瀏覽器用戶環(huán)境系統(tǒng)的好用性：靈活、易于擴充和集成，單一系統(tǒng)映象SSI（SingleSystemImage）用戶界面的好用性：實用性、高效性、易學習性、交互性、美觀性用戶界面設計的理論模型：實現(xiàn)模型（ImplementationModel），顯示模型（ManifestModel）和概念模型（ConceptualModel）機器的成本、價格與性/價比

機器的成本與價格機器的性能/價格比Performance/CostRatio：系指用單位代價（通常以百萬美元表示）所獲取的性能（通常以MIPS或MFLOPS表示）利用率（Utilization）：可達到的速度與峰值速度之比算法級性能評測加速比性能定律并行系統(tǒng)的加速比是指對于一個給定的應用，并行算法（或并行程序）的執(zhí)行速度相對于串行算法（或串行程序）的執(zhí)行速度加快了多少倍。Amdahl定律Gustafson定律SunNi定律可擴放性評測標準等效率度量標準等速度度量標準平均延遲度量標準Amdahl定律P：處理器數(shù)；W：問題規(guī)模（計算負載、工作負載，給定問題的總計算量）；Ws：應用程序中的串行分量，f是串行分量比例（f=Ws/W，Ws=W1）；WP：應用程序中可并行化部分，1-f為并行分量比例；Ws+Wp=W；Ts=T1：串行執(zhí)行時間，Tp：并行執(zhí)行時間；S：加速比，E：效率；出發(fā)點：固定不變的計算負載；固定的計算負載分布在多個處理器上的，增加處理器加快執(zhí)行速度，從而達到了加速的目的。Amdahl定律（cont‘d)固定負載的加速公式：

Ws+Wp可相應地表示為f+（1-f）

p→∞時，上式極限為：S=1/fWo為額外開銷 Amdahl’slaw(cont’d)Gustafson定律出發(fā)點：對于很多大型計算，精度要求很高，即在此類應用中精度是個關鍵因素，而計算時間是固定不變的。此時為了提高精度，必須加大計算量，相應地亦必須增多處理器數(shù)才能維持時間不變；除非學術研究，在實際應用中沒有必要固定工作負載而計算程序運行在不同數(shù)目的處理器上，增多處理器必須相應地增大問題規(guī)模才有實際意義。

Gustafson加速定律:并行開銷Wo：Gustafson定律（cont‘d)Sun和Ni定律基本思想：只要存儲空間許可，應盡量增大問題規(guī)模以產(chǎn)生更好和更精確的解（此時可能使執(zhí)行時間略有增加）。假定在單節(jié)點上使用了全部存儲容量M并在相應于W的時間內求解之，此時工作負載W=fW+（1-f）W。在p個節(jié)點的并行系統(tǒng)上，能夠求解較大規(guī)模的問題是因為存儲容量可增加到pM。令因子G（p）反應存儲容量增加到p倍時并行工作負載的增加量，所以擴大后的工作負載W=fW+（1-f）G（p）W。存儲受限的加速公式：并行開銷Wo:Sun和Ni定律(cont’d)G（p）=1時就是Amdahl加速定律；

G（p）=p變?yōu)閒+p（1-f），就是Gustafson加速定律G（p）>p時，相應于計算機負載比存儲要求增加得快，此時Sun和Ni加速均比Amdahl加速和Gustafson加速為高。加速比討論參考的加速經(jīng)驗公式：p/logp≤S≤P線性加速比：很少通信開銷的矩陣相加、內積運算等p/logp的加速比：分治類的應用問題通信密集類的應用問題：S=1/C（p）超線性加速絕對加速：最佳并行算法與串行算法相對加速：同一算法在單機和并行機的運行時間可擴放性評測標準并行計算的可擴放性（Scalability）也是主要性能指標可擴放性最簡樸的含意是在確定的應用背景下，計算機系統(tǒng)（或算法或程序等）性能隨處理器數(shù)的增加而按比例提高的能力影響加速比的因素：處理器數(shù)與問題規(guī)模求解問題中的串行分量并行處理所引起的額外開銷（通信、等待、競爭、冗余操作和同步等）加大的處理器數(shù)超過了算法中的并發(fā)程度增加問題的規(guī)模有利于提高加速的因素：較大的問題規(guī)?？商峁┹^高的并發(fā)度；額外開銷的增加可能慢于有效計算的增加；算法中的串行分量比例不是固定不變的（串行部分所占的比例隨著問題規(guī)模的增大而縮小）。增加處理器數(shù)會增大額外開銷和降低處理器利用率，所以對于一個特定的并行系統(tǒng)（算法或程序），它們能否有效利用不斷增加的處理器的能力應是受限的，而度量這種能力就是可擴放性這一指標?？蓴U放性評測標準（cont‘d)可擴放性:調整什么和按什么比例調整并行計算要調整的是處理數(shù)p和問題規(guī)模W，兩者可按不同比例進行調整，此比例關系（可能是線性的，多項式的或指數(shù)的等）就反映了可擴放的程度。并行算法和體系結構可擴放性研究的主要目的：確定解決某類問題用何種并行算法與何種并行體系結構的組合，可以有效地利用大量的處理器；對于運行于某種體系結構的并行機上的某種算法當移植到大規(guī)模處理機上后運行的性能；對固定的問題規(guī)模，確定在某類并行機上最優(yōu)的處理器數(shù)與可獲得的最大的加速比；用于指導改進并行算法和并行機體系結構，以使并行算法盡可能地充分利用可擴充的大量處理器目前無一個公認的、標準的和被普遍接受的嚴格定義和評判它的標準等效率度量標準令tie

和tio

分別是并行系統(tǒng)上第i個處理器的有用計算時間和額外開銷時間（包括通信、同步和空閑等待時間等）Tp

是p個處理器系統(tǒng)上并行算法的運行時間，對于任意i顯然有Tp=tie+tio

，且Te+To=pTp問題的規(guī)模W為最佳串行算法所完成的計算量W=Te

如果問題規(guī)模W保持不變，處理器數(shù)p增加，開銷To增大，效率E下降。為了維持一定的效率（介于0與1之間），當處理數(shù)p增大時，需要相應地增大問題規(guī)模W的值。由此定義函數(shù)fE（p）為問題規(guī)模W隨處理器數(shù)p變化的函數(shù)，為等效率函數(shù)（ISO-efficiencyFunction）（Kumar1987）等效率度量標準（cont‘d)曲線1表示算法具有很好的擴放性；曲線2表示算法是可擴放的；曲線3表示算法是不可擴放的。優(yōu)點：簡單可定量計算的、少量的參數(shù)計算等效率函數(shù)缺點：如果To無法計算出等速度度量標準p表示處理器個數(shù)，W表示要求解問題的工作量或稱問題規(guī)模（在此可指浮點操作個數(shù)），T為并行執(zhí)行時間，定義并行計算的速度V為工作量W除以并行時間Tp個處理器的并行系統(tǒng)的平均速度定義為并行速度V除以處理器個數(shù)p：W是使用p個處理器時算法的工作量，令W’表示當處理數(shù)從p增大到p’時，為了保持整個系統(tǒng)的平均速度不變所需執(zhí)行的工作量，則可得到處理器數(shù)從p到p’時平均速度可擴放度量標準公式等速度度量標準（cont’d）平均延遲度量標準Ti為Pi的執(zhí)行時間，包括包括延遲Li，Pi的總延遲時間為“Li+啟動時間+停止時間”。定義系統(tǒng)平均延遲時間為pTpara=To+Ts

在p個處理器上求解工作量為W問題的平均延遲在p’個處理器上求解工作量為W’問題的平均延遲當處理器數(shù)由p變到p’，而推持并行執(zhí)行效率不變，則定義平均延遲可擴放性度量標準為程序級性能評測基準測試程序（Benchmark）一組標準的測試程序提供一組控制測試條件步驟的規(guī)則說明（測試平臺環(huán)境、輸入數(shù)據(jù)、輸出結果和性能指標等）基準測試程序的分類真實程序：Ccompiler,Texteditor,spice核心程序:Livermore24loops,Linpack小測試程序:皇后問題、排序問題、求素數(shù)合成測試程序:Whetstone、Dhrystone應用：科學計算、商業(yè)應用、網(wǎng)絡服務、多媒體應用宏觀測試程序（Macro-benchmark）：計算機系統(tǒng)作為一個整體來測試其性能微觀測試程序（Micro-benchmark：測試機器的某一特定方面的性質BenchmarkSuites程序級性能評測（cont‘d)類

型名

稱意

義

用

途宏觀測試程序PARKBENCH并行計算NAS并行計算CFDSPEC混合基準測試程序Splash并行計算STAP信號處理TPC商業(yè)應用微觀測試程序LINPACK數(shù)值計算（線性代數(shù)）LMBECH系統(tǒng)調用和數(shù)據(jù)移動（UNIX）STREAM存儲器帶寬Whetstone和Dhrystone測試程序Whetstone：浮點性能合成測試程序最早用Algol-60寫成，后用Fortran改寫英國國立物理實驗室最頻繁使用的數(shù)值計算程序段。轉換到稱之為Whetstone虛擬計算機上的指令包括整數(shù)運算、浮點運算，涉及到數(shù)組下標索引、子程序調用、參數(shù)傳遞、條件轉移和三角/超越函數(shù)等，使用Kwhetstone/s數(shù)來度量。Dhrystone測試整數(shù)與邏輯運算性能合成測試程序用Ada、C和Pascal寫成CPU密集（CPU-intensive）型測試程序，包括很多整型語句與邏輯語句的小循環(huán)，使用KDhrystone/s數(shù)來度量VAX11/780（1MIPS)的性能為1.7KDhrystone/sWhetstone和Dhrystone的缺點：它們不能預測用戶程序性能，對編譯程序比較敏感。LINPACK測試程序機器名稱處理器數(shù)Rmax（Gflops）Nmax（階數(shù)）N1/2（階數(shù)）Rpeak（Gflops）IntelASCIoptionRed7264.1068215，00053，4001，453CP-PACS2048368.2103，68030，720614IntelParagonXP/SMP6768281.1128，60025，700338NumericalWindTunned167229.766，13218，018281FujitsuVpp500/153153200.662，73017，000245CrayT3D10241024100.581，92010，2241521BMSP2-T251288.473，50020，150136NECSX-4/323266.5315，3601，79264Fortran語言求解線性代數(shù)方程組的子程序，于1979年正式發(fā)布了LinPACK包,使用BLAS1測試的基準是用全精度64位字長的子程序求解100階線性方程組的速度，測試的結果以MflopsLAPACK測試程序和ScaLAPACK測試程序LAPACK:LinPACK作為測試程序現(xiàn)在仍很有生命力，但作為實際求解線性代數(shù)問題的軟件包已經(jīng)落伍了。1992年推出了代替LinPACK及EisPACK（特征值軟件包）的LAPACK，它使用了數(shù)值線性代數(shù)中最新、最精確的算法，同時采用了將大型矩陣分解成小塊矩陣的方法,從而可有效地使用存儲器。LAPACK是建立在BLAS1、BLAS2和BLS3基礎上的，其中BLS2執(zhí)行矩陣-向量運算，BLS3執(zhí)行矩陣-矩陣運算ScaLAPACK:LAPACK的增強版，主要為可擴放的、分布存儲的并行計算機而設計ScaLAPACK支持稠密和帶狀矩陣上各類操作，諸如乘法、轉置和分解等。在國際上，ScaLAPACK例程可以加入多個并行算法，并且可根據(jù)數(shù)據(jù)分布、問題規(guī)模和機器大小選擇這些算法，然而用戶卻不必關心這些細節(jié)LMBENCH和STREAM測試程序LMBENCHSGI的LarryMcVoy所維護用于測試不同Unix平臺上OS開銷以及處理器、高速緩存、主存、網(wǎng)絡和磁盤之間數(shù)據(jù)傳輸能力STREAMSGI的JohnMcCalpin所維護。測試可持續(xù)的存儲帶寬（MB/s）及其相應的計算速率迭代地執(zhí)行4種向量操作屬

性IntelAlderSunUltraIBM990帶寬（MB/s）存儲器復制5285242文件讀5285187管道（pipe）386184TCP205110延遲（μs）存儲器讀0.280.270.26文件生成23，80918，18113，333管道1016291TCP305162332系統(tǒng)開銷（μs）空系統(tǒng)調用7516進程生成4，5003，7001，200現(xiàn)場交換361413并行基準測試程序NPB測試程序NAS（NumericalAerodynamicSimulation）ParallelBenchmark8個程序組成，測試范圍從整數(shù)排序到復雜的數(shù)值計算EPMGCGFTISLUSPBTPARKBENCH測試程序PARallelKernelsandBENCHmarks目前分布存儲的多計算機編寫，使用Fortran77加上PVM或MPI底層基準程序、核心基準程序、密集應用基準程序、HPF編譯基準程序STAP測試程序Space-TimeAdaptiveProcessingAPT（AddtiveProcessingTestbed）、HO-PD（High-OrderPost-Doppler）、BM-stag（BeamSpacePRI-StaggeredPostDoppler）、EL-stag（ElementSpacePRI-StaggeredPostDoppler）、GEN（General）商用基準測試程序TPCTransactionProcessingPerformanceCouncilTPC已發(fā)布了4個基準測試程序，TPC-A和TPC-B于1995年6月廢棄；TPC-C用于測試事務處理系統(tǒng)的性能與價格/性能比；而TPC-D測試決策支持系統(tǒng)的性能。TPC-C是目前最流行的在線事務處理（OLTP）商用基準測試程序，能模擬一個大公司的整個銷售環(huán)境（倉庫、區(qū)域、用戶、定單、各種事務的比例、響應時間）性能結果tpmC：描述了系統(tǒng)在執(zhí)行Payment、Order-status、Delivery、Stock-Level這四種交易的同時，每分鐘可以處理多少個New-Order交易。所有交易的響應時間必須滿足TPC-C測試規(guī)范的要求。流量指標值越大越好。和價格/性能結果＄/tpmC：性價比越小越好各廠商的TPC-C測試結果都按TPC組織規(guī)定的兩種形式發(fā)布：測試結果概要(ExecutiveSummary)和詳細測試報告(FullDisclosureReport)。測試結果概要中描述了主要的測試指標、測試環(huán)境示意圖以及完整的系統(tǒng)配置與報價，而詳細測試報告中除了包含上述內容外，還詳細說明了整個測試環(huán)境的設置與測試過程TPC-C允許被測系統(tǒng)放大和縮小，但終端數(shù)和數(shù)據(jù)庫規(guī)模也必須按比例調整SPEC測試程序StandardPerformanceEvaluationCooperation第一組基準程序叫作SPEC89，包含10個程序；SPEC92擴充至20個程序，6個整數(shù)程序和