哈工大并行計(jì)算課件第三章

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

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

2性能和成本

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

4并行計(jì)算機(jī)性能

5并行程序性能

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

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

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

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

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

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

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

創(chuàng)作并加以維護(hù)。高性能計(jì)算機(jī)TOP500項(xiàng)目，收集和維護(hù)關(guān)于世界上前500名最強(qiáng)大的計(jì)算機(jī)系統(tǒng)的信息，每年兩次給出這些統(tǒng)計(jì)信息。根據(jù)超級計(jì)算機(jī)的Linpack基準(zhǔn)測試程序的性能進(jìn)行排名。LINPACK簡單實(shí)用，它定期公布有關(guān)各種系統(tǒng)的LINPACK性能數(shù)值表。6哈爾濱工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院Return7哈爾濱工業(yè)大學(xué)計(jì)算機(jī)科學(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é)計(jì)算機(jī)科學(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é)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院

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

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

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

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

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

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

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

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

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

2性能和成本

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

4并行計(jì)算機(jī)性能

5并行程序性能

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

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

n無量綱時(shí)鐘速率

fMHz工作負(fù)載

WMflop(兆浮點(diǎn)運(yùn)算)順序執(zhí)行時(shí)間

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

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

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

0．160．561．40

9233．8

9023386

13％

34％

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

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

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

0．160．561．40

9233．8

9023386

13％

34％

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

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

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

2性能和成本

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

4并行計(jì)算機(jī)性能

5并行程序性能

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

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

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

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

2性能和成本

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

4并行計(jì)算機(jī)性能

5并行程序性能

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

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

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

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

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

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

Tmp=Second()；

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

end_time=Second()；101哈爾濱工業(yè)大學(xué)計(jì)算機(jī)科學(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é)點(diǎn)0接收一個(gè)m字節(jié)消息；向結(jié)點(diǎn)0發(fā)送一個(gè)m字節(jié)消息；}}102哈爾濱工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院熱土豆(hot_potato)方法(也稱為救火隊(duì)方法)。該方法面向n個(gè)結(jié)點(diǎn)；方法是個(gè)循環(huán)的發(fā)送接收。

103哈爾濱工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院集合通信條件：設(shè)分布式存儲器多計(jì)算機(jī)中n個(gè)結(jié)點(diǎn)中的每一個(gè)均執(zhí)行以下的SPMD程序。使用路障來同步測量進(jìn)程中的異步操作。104哈爾濱工業(yè)大學(xué)計(jì)算機(jī)科學(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é)計(jì)算機(jī)科學(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é)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院改用集合操作的通用化乒乓方法：for(i=0；i<Runs；i++){if(my_node_id==0){tmp=Second()；start_time=Second();結(jié)點(diǎn)0向所有n個(gè)結(jié)點(diǎn)廣播一個(gè)空消息；For(j=0；i<Iterations；j++)107哈爾濱工業(yè)大學(xué)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院thecollective_routine_being_measured；所有結(jié)點(diǎn)向結(jié)點(diǎn)0完成一個(gè)空歸約；

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

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

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

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

、

m1/2、

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

／r∞=1/

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

116哈爾濱工業(yè)大學(xué)計(jì)算機(jī)科學(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é)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院6.集合通信

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

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

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

2性能和成本

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

4并行計(jì)算機(jī)性能

5并行程序性能

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

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

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

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

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

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

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

)代入可得：max(T1/n

,T∞)≤

Tn

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

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

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

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

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