哈工大并行計算課件第三章

第3章性能指標(biāo)和基準(zhǔn)程序

1系統(tǒng)和應(yīng)用的基準(zhǔn)程序

2性能和成本

3基本性能指標(biāo)

4并行計算機性能

5并行程序性能

6可擴展性和加速比分析1哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院如何描述應(yīng)用和系統(tǒng)的性能特征?

什么是用戶對性能和成本要求?

如何測量應(yīng)用程序的性能?使用何種類型的性能指標(biāo)?

當(dāng)在并行計算機上執(zhí)行并行程序時，如何描述系統(tǒng)性能的特征?影響性能的參數(shù)有哪些?典型的參數(shù)值為多少?如何量化和分析系統(tǒng)可擴展性?如何確定執(zhí)行給定應(yīng)用問題的并行機的可擴展性?2哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院一、前言

基準(zhǔn)程序是性能測試程序，并假設(shè)它能刻劃某一類應(yīng)用問題的處理和數(shù)據(jù)移動的特征?；鶞?zhǔn)程序用來測量和預(yù)測計算機系統(tǒng)的性能，并能提示它們的體系結(jié)構(gòu)的弱點和優(yōu)點。

1系統(tǒng)和應(yīng)用的基準(zhǔn)程序3哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院基準(zhǔn)程序分類：（1）按應(yīng)用類（2）按計算機系統(tǒng)來分基準(zhǔn)程序宏基準(zhǔn)程序宏基準(zhǔn)程序測量一個計算機系統(tǒng)的總體性能。微基準(zhǔn)程序兩類微基準(zhǔn)程序測量一個計算機系統(tǒng)的某一特定方面性能。4哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院5哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院二、微基準(zhǔn)程序

包括：3個微基準(zhǔn)程序組。1.LINPACK從1993起，美國明尼蘇達大學(xué)和田納西州立大學(xué)的JackDongarra

創(chuàng)作并加以維護。高性能計算機TOP500項目，收集和維護關(guān)于世界上前500名最強大的計算機系統(tǒng)的信息，每年兩次給出這些統(tǒng)計信息。根據(jù)超級計算機的Linpack基準(zhǔn)測試程序的性能進行排名。LINPACK簡單實用，它定期公布有關(guān)各種系統(tǒng)的LINPACK性能數(shù)值表。6哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院Return7哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院RankSiteCountry/YearComputer/ProcessorsManufacturerRmsxRpeak1EarthSimulatorCenterJapan/2002Earth-Simulator/5120NEC35860409602LawrenceLivermoreNational~aboratoryUnitedStates/2004ThunderIntelItanium2Tieer41.4GHz-Quadrics/4096CaliforniaDigitalCorporation19940229383LosAlamosNationalLaboratorvJnitedStates/2002ASCIO-A!ohaServerSC45.1.25GHz/8192HBM-RochesterUnitedStates/2004BlueGene/LDD1Prototvoe(0.5GHzPowerPC440w/Custom)/8192IBM/LLNL11680163845NCSAUnitedStates/2003TungstenPowerEd~,e1750,P4Xeon3.06GHz.Myrinet/2500Dell9819153006ECMWFUnitedKingdom/2004eServer

oSeries690(1.9GHzPower4+l/2112IBM8955160517InstituteofPhysicalandChemicalRes.(RIKEN)Japan/2004RIKENSuoerCombinedCluster/2048Fuiitqn8728125348IBM-ThomasWatsonResearchCenterUnitedStates/2004B!ueGene/LDD2Prototvoe(0.7GHzPowerPC440)/4096IBM/LLNL8655114699PacificNorthwestNationalLaboratoryUnitedStates/2003Mpp2hte~ritvrx2600Itanium21.5GHz.Quadrics/1936HP86331161610ShanghaiSupercomputerCenterChina/2004Dawning4000A,Onteron2.2GHz_Mvrinet/2560Dawning8061112642004年6月TOPl0

8哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院2004年11月TOP10

RankSiteCountry/YearComputer/ProcessorsManufacturerRmaxRpak1IBM/DOEUnitedStates/2004BlueGene/Lbeta-SystemBlueGene/LDD2beta-Svstem(0.7GHzPowerPC440)/32768IBM70720917502NASA/AmesResearchCenter/NASUnitedStates/2004ColumbiaSGIA!tix1.5GHz,VoltaireIufiniband/10160SGI51870609603TheEarthSimulatorCenterJapan/2002Earth-Simulator/5120NEC35860409604BarcelonaSuoercomouterCenterSpain/2004MareNostrum

eServer

B!adeCenterJS20(PowerPC9702.2GHzL

Mvrinet/3564IBM20530313635LawrenceLivermoreNational.aboratoryUnitedStates/2004ThunderIntelItanium2Ti2er41.4GHz-Quadrics/4096CaliforniaDigitalCorporation19940229386LosAlamosNationalLaboratoryUnitedStates/2002ASCIOASCIO-AIDhaServerSC45.1.25GHz/8192HiminiaTechUnitedStates/2004SystemX1100Dual2.3GHzADDleXServe/Me!!anox

Infiniband4X/CiscoGiuE/2200Sel[made12250202408IBM-RochesterUnitedStates/2004BlueGene/LDD1Prototwe(0.5GHzPowerPC440w/Custom}/8192IBM/LLNL11680163849NavalOceanoeraDhicOffice?NAVOCEANO)UnitedStates/2004eServer

DSeries655(1.7GHzPower4+)/2944~BM1031020019.210NCSAUnitedStates/2003TungstenPowerEd~,e1750,P4Xeon3.06GHz.Myrinet/2500Dell9819153009哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院

2004年11月的最新TOP500的特點DOE／IBM聯(lián)合研發(fā)的BlueGene／Lbeta-System以實測Linpack峰值70．72TFlops位于2004年11月TOP500排名的第一位。當(dāng)整個BlueGene／L系統(tǒng)完成時，將安裝到DOE(能源部)下的LawrenceLivermore國家實驗室。緊跟其后的是安裝在NASAAmes研究中心的SGl構(gòu)建的Columbia系統(tǒng)，它的實測峰值是51．87TFlops。上述兩個系統(tǒng)讓實測峰值35．86TFlops的日本NECEarthSimulator連續(xù)5次TOP500排名第1名成為歷史。10哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院該年度在TOP10中還有其他一些明顯的變化。安裝在Barcelona超級計算中心的IBMMareNostrum機群以20．53Tfops排名第四；采用AppleXserve服務(wù)器構(gòu)建的VirginiaTechX-system在六個月前由于主要的硬件更新出現(xiàn)了一些小問題退出TOP10后，現(xiàn)在以12．25TFlops重新回到了TOP10。TOP10的系統(tǒng)最低Linpack峰值達到了10TFlops，TOP100的最低Linpack峰值從1．922TFlops升到了2．026TFlops，TOP500的最低Linpack峰值從6個月前的624．3GFlops提高到850．6GFlops，而最新的TOP500中最后一名六個月前還列310位超過1TFlops的系統(tǒng)數(shù)量從242提高到399。整個TOP500中所有的系統(tǒng)的性能總和，已經(jīng)超過1PetaFIops，從六個月前的813TFlops突破到1．127PetaFlops。11哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院另外從TOP500中可以發(fā)現(xiàn)一些變化趨勢。從使用的處理器和系統(tǒng)類型來看，有320套系統(tǒng)采用Intel處理器，而六個月前這個數(shù)量是287，一年前只有189；其次是IBMPower處理器(54)，然后是Hewlett-PackardPA-RISC處理器(48)和AMD處理器(31)。結(jié)論：Intel的主導(dǎo)地位還是難以撼動機群(cluster)系統(tǒng)是主要的系統(tǒng)類型，共有296套系統(tǒng)是機群12哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院2.LMBENCHLMBENCH基準(zhǔn)程序組由SGI的LarryMcVoy

提出，是一個可移植的基準(zhǔn)程序。在各種Unix平臺上，用來測量操作系統(tǒng)開銷和處理器、高速緩存、存儲器、網(wǎng)絡(luò)及磁盤。13哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院屬性IntelAlderSunUltraIBM990帶寬(MB／s)存儲器復(fù)制讀文件管道TCP52523820858561512421878410時延(μs)讀存儲器創(chuàng)建文件管道TCP0．28238091013050．2718，181621620．2613,33391332系統(tǒng)開銷(μs)無系統(tǒng)調(diào)用創(chuàng)建進程現(xiàn)場切換7450036537001416120013由LMBENCH測得的帶寬、時延和系統(tǒng)開銷

14哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院3.STREAM是一個簡單的合成基準(zhǔn)程序；由SGl的JohnMcCalpin提出。測量持續(xù)的存儲器帶寬(以MB／s為單位)和相應(yīng)的計算速率。下表中的向量a、b和c均是有二百萬個元素的數(shù)組，其中每個元素是一個8字節(jié)的字。15哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院16哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院McCalpin提出一個機器平衡指標(biāo)，由下式定義：17哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院4.說明（如下表所示）：許多系統(tǒng)的機器平衡值隨年份增長而不斷增加，意味著存儲器帶寬越來越落后于處理器速度。IBMRS6000各種服務(wù)器是個例外，因為IBM公司對其中的存儲器系統(tǒng)設(shè)計總是給予足夠重視。其他公司也嘗試改進存儲器系統(tǒng)性能。18哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院19哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院三、并行計算的基準(zhǔn)程序測試分布共享存儲器機器數(shù)值計算基準(zhǔn)程序斯坦福大學(xué)開發(fā)的Splash和Splash-2；并行化編譯程序系統(tǒng)和技術(shù)：伊利諾斯大學(xué)開發(fā)的Perfect基準(zhǔn)程序常用的3個并行基準(zhǔn)程序組：NPB、PARKBENCH和STAP，它們代表了科學(xué)計算中的主要應(yīng)用組。20哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院1.NPB組在并行計算機供應(yīng)商、用戶和研究人員中，NPB已被廣泛接受。NAS并行基準(zhǔn)程序(NASParallelBenchmark，NPB)是由NASAAmesResearCenter為數(shù)值空氣動力模擬計劃開發(fā)的，用來評估并行超級計算機的性能。NPB模仿大型計流體動力學(xué)(computationalfluiddynamics，CFD)應(yīng)用中的計算和數(shù)據(jù)移動特征。21哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院NPB組由5個核心(EP、MG、CG、FT和IS)和3個模擬應(yīng)用(LU、SP和BT)程序組成。EP(EmbarrassinglyParallel)基準(zhǔn)程序；能運行在任意個數(shù)的處理器而只需很少通信。它能估計并行計算機可達到的浮點性能的上限。22哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院MG(MultiGridmethod，多柵格方法)基準(zhǔn)程序求解二維標(biāo)量泊松(Poisson)方程。要完成具有高度結(jié)構(gòu)化的短距離和遠程通信。CG(ConjugateGradientmethod，共軛梯度方法)基準(zhǔn)程序計算對稱正定矩陣的最小本征值。它的特點是進行非結(jié)構(gòu)柵格計算，需要不規(guī)則的遠程通信。23哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院

FT基準(zhǔn)程序使用基于FFT的光譜方法求解三維偏微分方程，也需要遠程通信。IS(整數(shù)排序，IntegerSorting)基準(zhǔn)程序基于桶型排序的并行排序程序。它需要很多全體交換通信。24哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院三種模擬應(yīng)用三者通信不同BT(BlockTri-diagonal，塊三對角)LU(blocklowertriangular，塊下三角，blockuppertriangular，塊上三角)；SP(ScalarPenta-diagonal，標(biāo)量五對角)基準(zhǔn)程序25哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院2.PARKBENCHPARKBENCH(并行核心和基準(zhǔn)程序)委員會在1992年超級計算會議上由一些對并行計算機基準(zhǔn)程序測試感興趣的人們創(chuàng)立的。該組織的一個貢獻是建立了一致的性能指標(biāo)和記號集。目前的基準(zhǔn)程序用于分布存儲多計算機用Fortran77編碼，并用PVM或MPI做消息傳遞。正在開發(fā)基準(zhǔn)程序的Fortran90和HPF版本以及適用于共享存儲體系結(jié)構(gòu)的基準(zhǔn)程序。26哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院該小組已提出4類基準(zhǔn)程序：低層基準(zhǔn)程序核心基準(zhǔn)程序壓縮應(yīng)用基準(zhǔn)程序目前只包括并行光譜轉(zhuǎn)換淺水建模應(yīng)用以及3個NPB模擬應(yīng)用HPF編譯器基準(zhǔn)程序是幾個簡單的合成應(yīng)用，用來測量HPF編譯器性能，側(cè)重對顯式并行HPF構(gòu)造的并行實現(xiàn)的檢測27哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院3.并行STAP組

空一時自適應(yīng)處理(Space-TimeAdaptiveProcessing)基準(zhǔn)程序組是一套實時雷達信號處理基準(zhǔn)程序。最初由MIT的林肯實驗室(LincolnLaboratory)開發(fā)。MIT的順序STAP近來已在南加州大學(xué)被轉(zhuǎn)換成并行STAP，用來評估各種MPP。STAP基準(zhǔn)程序是密集計算，要求在不到1秒時間內(nèi)對O(102-104)MB數(shù)據(jù)完成O(1010-1014)浮點操作。28哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院STAP基準(zhǔn)程序組由5個程序組成：AdaptiveProcessingTestbed(APT，自適應(yīng)處理試驗臺)High-OrderPost—Doppler(HO—PD，高階后多普勒)BeamSpacePRI-StaggeredPostDoppler(BM—Stag)ElementSpacePRI-StaggeredPostDoppler(EL—Stag)General(GEN)29哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院General(GEN)

GEN程序由4個獨立分程序組成：分別完成排序(SORT)快速傅里葉變換(FFT)向量乘(VEC)以及線性代數(shù)(LA)它們代表了在雷達信號處理應(yīng)用中經(jīng)常使用的核心子程序30哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院APT、HO-PD、BM、EL等4個基準(zhǔn)程序的結(jié)構(gòu)31哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院APT、HO-PD、BM、EL等4個基準(zhǔn)程序的結(jié)構(gòu)說明：全以DopplerProcessing(DP，多普勒處理)步開始。APT完成HouseholderTransform(HT，普通轉(zhuǎn)換)；它在以后的beamforming(BF，射束形成)步：以抑制人為干擾臺和雜亂回波；32哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院而在HO—PD程序中，兩個自適應(yīng)射束形成步被合成為一步。BM—Stag程序和EL—Stag程序與HO—PD類似，但各自在射束空間和元空間中使用交叉干擾訓(xùn)練算法。以targetdetection(TD，目標(biāo)探測)步結(jié)束。33哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院四、商業(yè)和TPC基準(zhǔn)程序

商用的最為流行的基準(zhǔn)程序組是TPC基準(zhǔn)程序，它由事務(wù)處理性能委員會(TransactionProcessingPerformanceCouncil，故名為TPC)開發(fā)，這是一個非盈利組織，主要從事事務(wù)處理和數(shù)據(jù)庫基準(zhǔn)程序的開發(fā)。34哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院TPC已發(fā)布了4個基準(zhǔn)程序。根據(jù)1995年6月資料，TPC-A和TPC-B已被廢棄。TPC-C是數(shù)據(jù)記載基準(zhǔn)程序，測量事務(wù)處理系統(tǒng)的性能和價格／性能比。TPC-D則測量決策支持系統(tǒng)。TPC正開發(fā)TPC-E(Enterprise，企業(yè))的新基準(zhǔn)程序，以量化支持適合于大型商業(yè)企業(yè)計算環(huán)境的特定系統(tǒng)的能力。35哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院TPC-C是一個在線事務(wù)處理(OLTP)基準(zhǔn)程序，用得最廣。它模擬一個完整的大規(guī)模公司環(huán)境，其中終端操作員對數(shù)據(jù)庫執(zhí)行事務(wù)操作。公司管理N個倉庫，每個倉庫供應(yīng)10個銷售區(qū)，每個區(qū)為3000名顧客服務(wù)。每個倉庫有10個終端，每個區(qū)有一個。在任何時間，一個操作員可執(zhí)行表中的處理36哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院37哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院被測系統(tǒng)必須具有ACID性質(zhì)原子性(atomicity)；一致性(consistency)；隔離性(isolation)；持久性(durability)。38哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院五、SPEC基準(zhǔn)程序系列SPEC基準(zhǔn)程序系列是由名為StandardPerformanceEvaluationCorporation非盈利公司所開發(fā)的。SPEC以測量CPU性能的基準(zhǔn)程序作為出發(fā)點，但已向客戶機／服務(wù)器計算I／O子系統(tǒng)等方面擴展。39哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院目前SPEC已公布如下的基準(zhǔn)程序組：SPEC95測量CPU、存儲器系統(tǒng)和編譯器代碼生成性能。

SPEC95CPU基準(zhǔn)程序從整體上測試CPU速度、高速緩存／存儲器系統(tǒng)以及編譯器。它不計操作系統(tǒng)和I／0操作時間。SPEC95由CINT95(8個整數(shù)程序)和CFP95(10個浮點程序)組成，兩者均是CPU密集應(yīng)用。40哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院SPEChpc96測量運行工業(yè)型應(yīng)用程序的高性能計算系統(tǒng)的性能。SPECweb96SFS為系統(tǒng)級文件服務(wù)器基準(zhǔn)程序。41哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院SDM為系統(tǒng)開發(fā)多任務(wù)基準(zhǔn)程序，測量一個系統(tǒng)如何處理一個有大量用戶發(fā)出典型的Unix軟件開發(fā)命令(如make、cp、grep及spell等)的環(huán)境。GPC圖形性能特征描述基準(zhǔn)程序，測量圖形學(xué)性能。42哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院下表給出了DigitalAlphaStation500／500的SPEC95結(jié)果該工作站使用500MHzAlpha21164微處理器，8MB高速緩存以及128MB主存。指定系統(tǒng)的所有SPEC95結(jié)果，均表示成與參照機SUNSPARC工作站10／40性能比較的比例。43哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院指標(biāo)速度吞吐率95_base95_rate95_ratebase95SPECint1512.6135113SPECfp20.418.3183165AlphaStation的SPEC95性能44哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院總結(jié)：探討了幾種常用的測試程序；45哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院第3章性能指標(biāo)和基準(zhǔn)程序

1系統(tǒng)和應(yīng)用的基準(zhǔn)程序

2性能和成本

3基本性能指標(biāo)

4并行計算機性能

5并行程序性能

6可擴展性和加速比分析46哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院

2性能和成本說明：用戶經(jīng)常提到6種性能：執(zhí)行時間；速度吞吐率：單位時間執(zhí)行的程序數(shù)；利用率成本有效性性能／成本比對在相同計算機平臺上執(zhí)行相同的應(yīng)期程序，這些需求可能導(dǎo)致很大差別的結(jié)論。47哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院用到的一些概念工作負載（W）是程序中的計算操作數(shù)Ppeak是處理器的峰值速度48哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院術(shù)語記號單位機器規(guī)模

n無量綱時鐘速率

fMHz工作負載

WMflop(兆浮點運算)順序執(zhí)行時間

T1s(秒)并行執(zhí)行時間

Tns(秒)速度Pn=W/TMflop／s加速比Sn=T1/Tn無量綱效率En=Sn/n無量綱利用率Un=Pn/(nPpeak)無量綱啟動時間t0μs漸近帶寬r∞MB/s49哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院例題：用執(zhí)行時間測量性能的不足

在并行計算機x上成功地運行他的代碼測得執(zhí)行時間為1000s。該代碼在另一臺機器y上運行需要500s時間，推不出：結(jié)論x機比y機慢50哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院一、執(zhí)行時間和吞吐率1.處理速度：是指單位時間的工作負載（W)的處理；對于許多應(yīng)用，用戶可能對達到某一處理速度感興趣。51哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院在256個結(jié)點的SP2上所測得的STAP性能程序執(zhí)行時間(s)速度(GFlop／s)加速比利用率APTHO-PDGEN

0．160．561．40

9233．8

9023386

13％

34％

6％52哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院例題：在256個結(jié)點的SP2上希望STAP在0.5秒完成根據(jù)上表，只有APT能完成例題：在256個結(jié)點的SP2上希望STAP速度為10GFLOP/S根據(jù)上表，只有HO-PD能完成53哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院2.系統(tǒng)吞吐率是指單位時間處理的作業(yè)數(shù)提高系統(tǒng)吞吐率的兩個方法流水化無相關(guān)的分配54哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院例題：在256個結(jié)點的SP2上APT程序的吞吐率是單位時間作業(yè)數(shù)0.16S一個APT或1/0.16=6.25例題：并行APT中吞吐率和速度改進上表的工作負載=9*0.16=1.44Gflop假設(shè)：用兩級流水0.14S，0.11S，每一級128個結(jié)點，總的時間0.25s吞吐率=1/0.14S個APT

=7.14個APT或1.44/0.14=10.34Gflop/s或7.14*0.14=10.2855哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院例題：每個節(jié)點無相關(guān)的分配一個分離任務(wù)：上例IBMSP2每個節(jié)點分配一個APT任務(wù)，在一個SP2節(jié)點上執(zhí)行時間需14s，這時的吞吐率是：

256/14=18.29個APT56哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院二、利用率和成本有效性執(zhí)行時間、速度和利用率是最重要的3個指標(biāo)利用率：它是一個給定計算機實際可達到速度與峰值速度之比57哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院例題：執(zhí)行APT的IBMSP2的利用率假定每個CPU小時需收費10美元則由下表，計算APT程序運行在256個結(jié)點和1個結(jié)點上時的利用率256個結(jié)點和1個結(jié)點哪一個更成本有效?58哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院程序執(zhí)行時間(s)速度(GFlop／s)加速比利用率APTHO-PDGEN

0．160．561．40

9233．8

9023386

13％

34％

6％在256個結(jié)點的SP2上所測得的STAP性能59哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院解：每個SP2結(jié)點的峰值速度為266Mflop／s（見表3-2136G/512=266）一個有256個結(jié)點的SP2，其峰值速度為：266x256=68Gflop／s；APT程序在256個結(jié)點上可達到的速度為：9Gflop／s；在1個結(jié)點可求出達到的速度為：利用Sn=T1/Tn；p1=w/t1,pn=w/tn1個結(jié)點速度=9Gflop／s/90=100Mflop／s；60哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院轉(zhuǎn)換成利用率則各自分別為:利用率Un=Pn/(nPpeak)256個結(jié)點利用率=9G/68G=13．3％單個結(jié)點利用率=100M/266M=37．6％結(jié)論：表明APT程序在SP2上運行，在一個結(jié)點上時是更為成本有效61哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院根據(jù)上面的要求：在256個結(jié)點上執(zhí)行APT需0.16s執(zhí)行一個APT的總成本為:$10x256x0.16／3600=$0.11這相應(yīng)于成本有效性為:(9Gflop／s)／$0．11=81Gflop／s每美元。62哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院在一個結(jié)點時，執(zhí)行時間約為14．4s總的成本僅為：$10x14．4／3600=$0．04，成本有效性為：(9Gflop/s?)/$0．04=225Gflop／s每美元(100Mflops／s)/0.04=2.5Gflop/s每美元63哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院總結(jié)：該例子表明較高利用率對應(yīng)地有較高的每美元Gflop／s當(dāng)CPU1小時費用值固定時這總是成立的CPU一小時的費用在不同機器上對不同類型的作業(yè)可能有高有低。64哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院推廣如果用成本來衡量：Gflops/美元執(zhí)行時間、速度和利用率是重要的指標(biāo)：低利用率總是對應(yīng)一個差的程序或編譯器。65哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院經(jīng)驗估計值：運行在單MPP處理器上：順序應(yīng)用程序（利用率）--5％到40％之間；典型是--8％到25％之間。某些個別的子程序可達到75％以上。對于在多個處理器上運行的并行應(yīng)用程序利用率在1％到35％之間；典型地則是在4％到20％之間。66哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院一個廣為流傳的錯誤概念是：單結(jié)點或順序計算總是有最高的利用率?(由下圖說明）并行計算有額外通信和閑置開銷,這并非總是正確的。67哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院例子：給出在3個MPP(IntelParagon，IBMSP2和CrayT3D)上；運行并行APT和HO基準(zhǔn)程序；測出利用率如下：

68哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院69哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院70哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院NAS并行基準(zhǔn)測試程序的3種MPP的利用率71哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院72哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院例題：峰值性能／價格比可能產(chǎn)生錯誤概念持續(xù)性能／價格比都在一個區(qū)域之間。CrayJ916的峰值性能／價格比比ConvexSPP1000、CrayT3D以及SGIPowerChallenge要低得多。但它的持續(xù)性能／價格比，實際上比它們的都要高。73哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院74哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院第3章性能指標(biāo)和基準(zhǔn)程序

1系統(tǒng)和應(yīng)用的基準(zhǔn)程序

2性能和成本

3基本性能指標(biāo)

4并行計算機性能

5并行程序性能

6可擴展性和加速比分析75哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院一、工作負載和速度指標(biāo)

常用3個指標(biāo)來測量程序C的計算工作負載：執(zhí)行時間；執(zhí)行的指令數(shù)；執(zhí)行的浮點操作數(shù)。76哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院77哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院關(guān)于指令數(shù)的說明:依賴太多關(guān)于執(zhí)行時間的說明執(zhí)行時間依賴于許多因素：算法、數(shù)據(jù)結(jié)構(gòu)、輸入數(shù)據(jù)、平臺、語言浮點數(shù)78哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院79哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院例題：FFT處理的利用率

假定STAP一個DP(多普勒處理)步由2048個，每個為8192點的FFT所組成。每個N點FFT處理的工作負載為W=5NlogNflop。則多普勒處理步的總工作負載是2048x(5x8192xlog8192)flop，約為1．09Gflop。對于在X機上50s的執(zhí)行時間，其速度約為22Mflop／s。假設(shè)X機的峰值速度為266Mflop／s，則多普勒處理可達到的利用率為22／266=8．27％僅為峰值性能的很低比值。80哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院在進行理論性能分析時，常假設(shè)每條指令或flop需要相同時間量。在實際系統(tǒng)中這種均勻速度假設(shè)是不成立的。在單IBMSP2結(jié)點上，觀察到的速度可從5變化到250Mflop/s。在測量工作負載時，也廣泛使用順序執(zhí)行時間以補充統(tǒng)計flop或指令數(shù)的方法81哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院二、有關(guān)性能指標(biāo)的總結(jié)所有3種指標(biāo)都是有用的，特別是flop數(shù)和執(zhí)行時間。在預(yù)測和測量應(yīng)用的性能時，應(yīng)統(tǒng)一地使用單工作負載，即使是在并行計算機上也應(yīng)如此。82哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院例題：83哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院84哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院第3章性能指標(biāo)和基準(zhǔn)程序

1系統(tǒng)和應(yīng)用的基準(zhǔn)程序

2性能和成本

3基本性能指標(biāo)

4并行計算機性能

5并行程序性能

6可擴展性和加速比分析85哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院

4并行計算機性能針對一個并行系統(tǒng)，需討論計算和開銷特征一、計算特征下表給出了3種商品化并行計算機系列的性能參數(shù)的歷史值86哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院87哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院存儲器層次結(jié)構(gòu)：存儲器容量存儲器時延存儲器帶寬1996年前后計算機中這3個參數(shù)的典型值88哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院89哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院二、并行性和通信開銷

并行程序中的開銷可分為3類負載不平衡開銷—計算部分；并行性開銷；通信開銷(包括同步、通信和聚集)。

T=Tcomp+Tpar+Tinteract90哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院說明：并行性開銷包括3種的并行性操作:進程管理；分組操作進程查詢操作91哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院通信開銷的來源有3種類型的操作同步聚集通信92哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院巨大開銷:注意有關(guān)并行性和通信開銷的兩個要點：通常比基本計算時間要大得多，在不同系統(tǒng)上變化很大。93哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院94哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院95哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院三、開銷定量化1.問題的提出應(yīng)對計算的并行性和通信開銷進行量化。96哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院2.開銷測量條件進行測量實驗的確切條件必須清楚地加以說明。以下是部分列表:所使用的數(shù)據(jù)結(jié)構(gòu)。所使用的編程語言、庫以及編譯器選擇。一般地，開銷測量應(yīng)以批處理方式進行，都會被執(zhí)行。97哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院所使用的通信硬件和協(xié)議。因為在這種方式下大多數(shù)生成路徑(productionrun)測量掛鐘時間或是CPU時間。一般來講，掛鐘時間更有用。98哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院3.開銷測量方法雖然測量開銷粗看起來非常簡單，但要獲得精確測量結(jié)果卻是很具挑戰(zhàn)性的任務(wù)主要的原因有3種：微秒定時精度誤差；MIMD異步；相同的通信操作誤差大。99哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院乒乓方案：是測量點對點通信常用的方法:結(jié)點0執(zhí)行一個發(fā)送操作向結(jié)點1發(fā)送一個m字節(jié)的消息，后者執(zhí)行一個接收操作收到此消息結(jié)點1立即發(fā)送相同消息給結(jié)點0100哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院例題：測量時延的乒乓方案：

for(i=0；i<Runs；i++)

if(my_node_id==0){/*發(fā)送方*/

Tmp=Second()；

start_time=Second()；向結(jié)點1發(fā)送一個m字節(jié)消息；從結(jié)點1接收一個m字節(jié)消息；

end_time=Second()；101哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院timer_overhead=start_time-tmp；total_time=end_time-start_time-timer_overhead；communication_time[i]=total_time／2；}elseif(my_node_id==1){/*接收方*/從結(jié)點0接收一個m字節(jié)消息；向結(jié)點0發(fā)送一個m字節(jié)消息；}}102哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院熱土豆(hot_potato)方法(也稱為救火隊方法)。該方法面向n個結(jié)點；方法是個循環(huán)的發(fā)送接收。

103哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院集合通信條件：設(shè)分布式存儲器多計算機中n個結(jié)點中的每一個均執(zhí)行以下的SPMD程序。使用路障來同步測量進程中的異步操作。104哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院for(i=0；i<Runs；i++){

Barriersynchronization；Tmp=Second()；start_time=Second()；for(j=0；j<Iterations；j++)The_collective_routine_being_measured；End_time=Second()；105哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院Timer_overhead=start_time-tmp；Total_time=end_time-start_time–timer_overhead；Local_time=total_time/Iterations；Communication_time[i]=maximumOfallnlocaltimevalues；}106哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院改用集合操作的通用化乒乓方法：for(i=0；i<Runs；i++){if(my_node_id==0){tmp=Second()；start_time=Second();結(jié)點0向所有n個結(jié)點廣播一個空消息；For(j=0；i<Iterations；j++)107哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院thecollective_routine_being_measured；所有結(jié)點向結(jié)點0完成一個空歸約；

if(my_node_id=0){end_time=Second()；timer_overhead=start_time-tmp；Communication_time[i]=end_time-start_time-

timer_overhead}108哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院4.開銷表達式經(jīng)測量獲得開銷數(shù)據(jù)，有3種表示方法：用表格來表示數(shù)據(jù)。例如，下表給出了在SP2上運行專有MPL通信庫所測得的點對點通信的定時結(jié)果。109哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院110哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院以曲線來表示數(shù)據(jù)如下圖所示。其優(yōu)點是曲線可示出通信開銷增長趨向。

111哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院112哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院表達式表示例如，將所測得的定時數(shù)據(jù)用最小二乘法適當(dāng)?shù)丶右詳M合。就可將SP2上的點對點通信開銷表示成消息長度的線性函數(shù)：t=46+0.035mμs如果加以擬合，它與曲線之間的誤差是很小的，如上圖所表明的那樣。113哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院5.點對點通信表達式Hockney提出操作通信時間(以μs表示)特征的1個模型，其中的通信開銷t(m)是消息長度m(以字節(jié)表示)的線性函數(shù)：

t(m)=t0+m／r∞式中t0是以μs表示的啟動時間，而r∞是漸近帶寬，單位MB／s。114哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院Hockney還引入了兩個附加的參數(shù)。半峰值長度記為m1/2字節(jié)，是達到半漸近帶寬所需的消息長度。特殊性能，記為

0MB／s，用來表明短消息帶寬。115哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院4個參數(shù)t0、r∞

、

m1/2、

0MB中的兩個是獨立的。另兩個可用以下關(guān)系推得：t0=m1/2

／r∞=1/

0其中m1/2是表示系統(tǒng)支持短消息通信好壞程序的參數(shù)。

116哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院例如：SP2的t(m)=46+0.035m。啟動開銷為t0=46μs；漸近帶寬為：r∞=1／0.035=28.57MB／s，以及半峰值消息長度為：m1/2

=t0×r∞=1314字節(jié)。117哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院6.集合通信

將式Hockney表達式擴展成如下：通信開銷T(m,n)現(xiàn)改為是m和n兩者的函數(shù)。但啟動時延仍只依賴于n。漸近帶寬變?yōu)閞∞(n)。

T(m,n)=t0(n)+m/r∞(n)118哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院在將測得的定時數(shù)據(jù)與不同的t0(n)和r∞(n)形式擬合可推得如表中所示的4個集合操作的公式119哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院120哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院7.集合計算測量了3種代表性的集合計算操作：路障、歸約和掃描。它們擬合曲線開銷表達式如下表所示。注意當(dāng)處理器數(shù)超過256時，路障開銷為762μs，相當(dāng)于執(zhí)行762x266=202,692flop所需的時間?，F(xiàn)在可以回答這樣問題，是否應(yīng)使用同步算法?121哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院122哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院短消息和長消息全交換開銷的方法作了比較：在下圖中示出了當(dāng)mn2=16MB(例如，m=1024字節(jié)和n=128)時兩種表示方法的相對誤差。結(jié)論：如圖123哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院124哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院在下圖，比較了當(dāng)mn2=64KB(例如，m=4字節(jié)及n=128)時，所測得的開銷與由兩種方法推測所得的開銷。125哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院126哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院第3章性能指標(biāo)和基準(zhǔn)程序

1系統(tǒng)和應(yīng)用的基準(zhǔn)程序

2性能和成本

3基本性能指標(biāo)

4并行計算機性能

5并行程序性能

6可擴展性和加速比分析127哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院

5并行程序性能說明：討論有關(guān)并行應(yīng)用的一些性能問題和性能指標(biāo)提出的所有性能指標(biāo)，有通用性128哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院一、性能指標(biāo)1.前言設(shè)順序程序C由一串A個分計算階段C1，C2，…Ck所組成DOPi是并行性下圖給出了一個階段并行程序129哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院130哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院2.基本指標(biāo)從語義上講，上圖有順序執(zhí)行的步Ci計算的工作負載，如上圖示可求總并行性開銷131哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院當(dāng)在n個處理器上執(zhí)行工作負載時，步Ci并行執(zhí)行時間：Tn(i)=T1(i)/n在n個結(jié)點上總的并行執(zhí)行時間為：

132哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院3.極值指標(biāo)

存在幾個極值指標(biāo)以給出Pn、Tn和Sn的下限和上限。設(shè)T∞是關(guān)鍵路徑的長度，有：133哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院使得Tn=T∞的n最小值稱為最大并行性，記為Nmax。可由Nmax=max1≤j

k(DOPi)計算該指標(biāo)。持續(xù)加速比Pn的最大值P∞=W／T∞是它的上限。N個結(jié)點執(zhí)行時間Tn的下限值為T1／n和T∞。Tn≥max(T1/n,T∞

)134哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院平均并行性T1/T∞，是加速比的上限。即Sn≤T1/Tn。Brent已證明，若不計所有并行性和交互開銷，Tn受限于下列不等式：T1/n≤Tn

T1/n+T∞將Tn≥max(T1/n,T∞

)代入可得：max(T1/n

,T∞)≤

Tn

T1/n+T∞。這些不等式在估計并行執(zhí)行時間時很有用。135哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院下表基于階段并行模型性能的一些指標(biāo)：136哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院137哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院4.例題：STP中APT基準(zhǔn)程序

為便于理解，STAP基準(zhǔn)程序組中的APT程序可描述如下：其中變量N為問題參數(shù)。記號[.]變量house是一個含有約80KB信息的矩陣，與N無關(guān)138哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院For(j=0；j<N；j++)for(k=0；k<32；k++)fft(data[.][j][k])；ht(data[1][.][.]，house)；for(i=0；i<N；i++)bf(data[i][.][.],housedetect[i][.])For(j=0；j<N；j++)for(i=0；i<N；i++)td(detect[i][j]，target_report)；139哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院140哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院5.例題：并行APT基準(zhǔn)測試程序的性能指標(biāo)141哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院假設(shè)條件：每個計算步的工作負載由上圖(STP中APT圖）中值求得，以單SP2結(jié)點的Mflop和執(zhí)行時間表示。并行性開銷忽略不計。在忽略不計所有通信開銷情況下，來預(yù)測性能指標(biāo)的極端值，稱其為0_開銷預(yù)測。一個粗粒度階段并行算法，參數(shù)N=256。142哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院由上圖可知最大并行性為:max(8192，1，256，256)=8192總工作負載W=1447Mflop；順序執(zhí)行時間T1=14．37s；關(guān)鍵路徑為143哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院求得最大性能值P∞=W/T∞=1447/0.08=18087Mflop／s，而平均并行性為T1/T∞=14．37/0.08=180。144哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院6.例題：估計APT基準(zhǔn)測試程序中的交互開銷可用上述表的表達式來估計運行在SP2上的并行APT程序的交互開銷。交互開銷是3種通信的和：T=Tcomp+Tpar+Tinteract145哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院146哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院147哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院148哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院從上表和圖可見，16.7/n2MB的全交換開銷為：Tindex=80logn+0.03n1.29mμs=0.00008logn+0.5n-0.71秒廣播開銷的表達式為:Tbcast=52logn+(0.029logn)mμs=0.00237logn秒；

m=80kB=80x1024B149哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院歸約n個flop數(shù)所需時間為：20logn+23μs；其中由n個結(jié)點中的每一個提供一個flop數(shù)。在APT圖的歸約步中，組合了n個目標(biāo)報告，每個有100個flop數(shù)?？杀Ｊ氐卦u估歸約開銷：Treduce=100(20logn+23)μs=0.002logn+0.0023秒150哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院那么總的交互開銷為：T0=Tinteract=0.5n-0.71+0.00445logn+0.0023；有以下說明：并行處理中的一個觀念是通信開銷隨所使用結(jié)點數(shù)的增加而增長。但由上面例子可見，這可能是錯的。在APT程序中當(dāng)所使用結(jié)點不多于256時，總的通信開銷隨機器規(guī)模增加而減少。151哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院7.例題：APT基準(zhǔn)測試程序期望執(zhí)行時間來預(yù)測并行APT算法在n<256結(jié)點的SP2上的執(zhí)行時間。并計算當(dāng)n=256時的平均顆粒度。使用n個結(jié)點的總執(zhí)行時間為：T=Tcomp+Tpar+Tinteract=14.33/n+0.5n-0.71+0.00445logn+0.0423串行通訊：0.0023+0.04152哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院單SP2結(jié)點的總工作負載W=1447Mflop或14．37s。平均顆粒度為:W/T0=1447M/0.0479=30209對于每Mflop計算，平均的通信開銷為:1／30209=33μs153哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院也可將執(zhí)行時間作為工作負載。那么平均顆粒度變?yōu)閃/T0=14.37/0.0479=300

因此平均而言，對于每秒通信，256個結(jié)點共完成300s計算，或?qū)τ诿棵胪ㄐ牛總€結(jié)點完成300／256=1．17s計算。154哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院二、基準(zhǔn)程序中的可用并行性關(guān)于并行成分的討論應(yīng)用程序中潛在并行性有很寬的范圍。工程和科學(xué)代碼具有數(shù)據(jù)并行性，有很高的DOP。155哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院數(shù)據(jù)的并行：Kumar(1988年)已報導(dǎo)過密集計算代碼在理想環(huán)境下于每個時鐘內(nèi)可并發(fā)地執(zhí)行500到3500個算術(shù)操作。指令級并行：要低得多。Wall指出指令級并行性的極限約在5左右，很少超過7。Bulter等(1991年)曾報道過當(dāng)去除所有約束時，在某些科學(xué)程序中l(wèi)LP可超過每周期17條指令。156哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院某些程序跟蹤結(jié)果指出，如果體系結(jié)構(gòu)和編譯器能完滿地工作，則在一個合理設(shè)計的超標(biāo)量處理器上，可期待的lLP為每周期并發(fā)執(zhí)行2.0到5.8條指令。下表中為PERFECT基準(zhǔn)測試程序組中12個程序中的每一個給出了其平均并行性。

157哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院158哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院例題：3個STAP基準(zhǔn)測試程序性能下表中示出了使用最小、最大和名義數(shù)據(jù)集時，STAP基準(zhǔn)測試程序組中3個程序的某些性能指標(biāo)。其中的輸入數(shù)據(jù)規(guī)模和工作負載由STAP基準(zhǔn)測試程序規(guī)范給定。159哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院160哈爾濱工業(yè)大學(xué)計算機科學(xué)與技術(shù)學(xué)院以上可用并行性的測量表明：非數(shù)值計算的相對并行性很小。編譯