高級(jí)計(jì)算機(jī)體系結(jié)構(gòu)第4章1

1、1第四章第四章 性能評(píng)測(cè)性能評(píng)測(cè) 2第一節(jié)第一節(jié) 性能評(píng)測(cè)概述性能評(píng)測(cè)概述一、并行計(jì)算機(jī)性能指標(biāo)一、并行計(jì)算機(jī)性能指標(biāo)1 1、硬件性能、硬件性能參數(shù)參數(shù) -反映硬件系統(tǒng)基本性能反映硬件系統(tǒng)基本性能名稱名稱符號(hào)符號(hào)含義含義量綱量綱機(jī)器規(guī)模機(jī)器規(guī)模 n處理器處理器P P的數(shù)量的數(shù)量個(gè)個(gè)時(shí)鐘頻率時(shí)鐘頻率 f時(shí)鐘周期長(zhǎng)度的倒數(shù)時(shí)鐘周期長(zhǎng)度的倒數(shù)MHzMHz峰值速度峰值速度 Rpeak=nRpeak并行機(jī)峰值速度并行機(jī)峰值速度Mflop/sMflop/s通信延遲通信延遲 t0傳送傳送0/10/1字節(jié)的時(shí)間字節(jié)的時(shí)間usus漸進(jìn)帶寬漸進(jìn)帶寬 R長(zhǎng)消息的通信速率長(zhǎng)消息的通信速率MB/sMB/s * *硬件性

2、能硬件性能的輔助的輔助參數(shù)：參數(shù)： 存儲(chǔ)系統(tǒng)存儲(chǔ)系統(tǒng)主存主存/Cache/Cache容量、頁(yè)容量、頁(yè)/ /塊大小、關(guān)聯(lián)度等；塊大小、關(guān)聯(lián)度等； 通信系統(tǒng)通信系統(tǒng)通信服務(wù)、通信服務(wù)、ININ及及NICNIC性能參數(shù)性能參數(shù)3名稱名稱符號(hào)符號(hào)含義含義量綱量綱工作負(fù)載工作負(fù)載W W計(jì)算操作的數(shù)目計(jì)算操作的數(shù)目MFlopMFlop順序執(zhí)行時(shí)間順序執(zhí)行時(shí)間T T1 1程序在單處理機(jī)上運(yùn)行時(shí)間程序在單處理機(jī)上運(yùn)行時(shí)間s s并行執(zhí)行時(shí)間并行執(zhí)行時(shí)間T Tn n程序在并行機(jī)上運(yùn)行時(shí)間程序在并行機(jī)上運(yùn)行時(shí)間s s速度速度R Rn n=W=W/ /T Tn n程序在并行機(jī)上運(yùn)行速度程序在并行機(jī)上運(yùn)行速度Mflop

3、/sMflop/s加速比加速比S Sn n= T= T1 1/ /T Tn n并行機(jī)比單處理機(jī)速度的倍數(shù)并行機(jī)比單處理機(jī)速度的倍數(shù) 無(wú)量綱無(wú)量綱效率效率E En n= = S Sn n/ /n n并行機(jī)硬件部件的利用率并行機(jī)硬件部件的利用率無(wú)量綱無(wú)量綱利用率利用率U=RU=Rn n/ /R Rpeakpeak并行機(jī)峰值速度的利用率并行機(jī)峰值速度的利用率無(wú)量綱無(wú)量綱吞吐率吞吐率T TP P= =m m/ /T Tn n(m)(m)并行機(jī)單位時(shí)間內(nèi)處理任務(wù)數(shù)并行機(jī)單位時(shí)間內(nèi)處理任務(wù)數(shù) 個(gè)個(gè)/s/s2 2、系統(tǒng)性能、系統(tǒng)性能指標(biāo)指標(biāo) -反映軟硬件系統(tǒng)性能和可擴(kuò)放性反映軟硬件系統(tǒng)性能和可擴(kuò)放性 * *

4、程序參數(shù)：程序參數(shù)：?jiǎn)栴}規(guī)模、工作負(fù)載、負(fù)載不平衡開(kāi)銷、工作問(wèn)題規(guī)模、工作負(fù)載、負(fù)載不平衡開(kāi)銷、工作集尺寸、通信集尺寸、通信- -計(jì)算比、通信與同步開(kāi)銷、并行性開(kāi)銷計(jì)算比、通信與同步開(kāi)銷、并行性開(kāi)銷等等 * *影響系統(tǒng)性能因素：影響系統(tǒng)性能因素：硬件參數(shù)硬件參數(shù)( (結(jié)構(gòu)與速度結(jié)構(gòu)與速度) )、程序參數(shù)、程序參數(shù)( (應(yīng)應(yīng)用與算法用與算法) )，及，及兩者的兩者的相互作用相互作用回7頁(yè)回13頁(yè)回23頁(yè)回24頁(yè)回27頁(yè)4二、為何要進(jìn)行二、為何要進(jìn)行性能評(píng)測(cè)性能評(píng)測(cè) 1 1、購(gòu)買者進(jìn)行性能評(píng)測(cè)的目的、購(gòu)買者進(jìn)行性能評(píng)測(cè)的目的 主要主要是降低投資風(fēng)險(xiǎn)，提高投資是降低投資風(fēng)險(xiǎn)，提高投資效益效益 有利于

5、有利于選擇并行機(jī)型號(hào)選擇并行機(jī)型號(hào)( (性性/價(jià)價(jià)、RARSRARS、可可擴(kuò)展性擴(kuò)展性) ) 有利于有利于配置系統(tǒng)相關(guān)參數(shù)配置系統(tǒng)相關(guān)參數(shù)( (需求、性能、性需求、性能、性/ /價(jià)價(jià)) )2 2、設(shè)計(jì)者進(jìn)行性能評(píng)測(cè)的目的、設(shè)計(jì)者進(jìn)行性能評(píng)測(cè)的目的 主要主要是為優(yōu)化設(shè)計(jì)提供量化是為優(yōu)化設(shè)計(jì)提供量化依據(jù)依據(jù) 有利于有利于發(fā)現(xiàn)發(fā)現(xiàn)系統(tǒng)設(shè)計(jì)中存在的系統(tǒng)設(shè)計(jì)中存在的問(wèn)題問(wèn)題 有利于有利于合理地進(jìn)行軟合理地進(jìn)行軟/ /硬件功能分配硬件功能分配，提高系統(tǒng)性，提高系統(tǒng)性/ /價(jià)價(jià) 有利于有利于優(yōu)化結(jié)構(gòu)優(yōu)化結(jié)構(gòu)- -算法算法- -應(yīng)用的組合應(yīng)用的組合，設(shè)計(jì)高效，設(shè)計(jì)高效算法算法5三、三、如何進(jìn)行性能評(píng)測(cè)如何進(jìn)行

6、性能評(píng)測(cè) * *系統(tǒng)性能指標(biāo)：系統(tǒng)性能指標(biāo)：不同測(cè)試者所關(guān)心的性能指標(biāo)種類不同測(cè)試者所關(guān)心的性能指標(biāo)種類不同不同 * *性能評(píng)測(cè)層次：性能評(píng)測(cè)層次：機(jī)器級(jí)、算法級(jí)、程序機(jī)器級(jí)、算法級(jí)、程序級(jí)級(jí)1 1、機(jī)器級(jí)性能評(píng)測(cè)、機(jī)器級(jí)性能評(píng)測(cè) * *評(píng)測(cè)內(nèi)容：評(píng)測(cè)內(nèi)容： CPUCPU及存儲(chǔ)器基本性能及存儲(chǔ)器基本性能( (T Tn n、R Rn n等等) )； 并行并行與通信開(kāi)銷與通信開(kāi)銷( (T Tparpar、t t0 0、R R等等) )； 可用性可用性、好用性、好用性( (運(yùn)行運(yùn)行正常百分比正常百分比、環(huán)境及界面、環(huán)境及界面) )； 性能性能與與成本成本 * *評(píng)測(cè)方法評(píng)測(cè)方法：通過(guò)基準(zhǔn)測(cè)試程序，通

7、過(guò)基準(zhǔn)測(cè)試程序， 不斷改變硬件參數(shù)進(jìn)行測(cè)試不斷改變硬件參數(shù)進(jìn)行測(cè)試回7頁(yè)62 2、算法級(jí)性能評(píng)測(cè)、算法級(jí)性能評(píng)測(cè) * *評(píng)測(cè)內(nèi)容：評(píng)測(cè)內(nèi)容：應(yīng)用應(yīng)用- -算法算法- -結(jié)構(gòu)組合的可擴(kuò)放結(jié)構(gòu)組合的可擴(kuò)放性；性； 即給定應(yīng)用背景，系統(tǒng)即給定應(yīng)用背景，系統(tǒng)擴(kuò)擴(kuò)放時(shí)的性能放時(shí)的性能 * *評(píng)測(cè)評(píng)測(cè)方法方法：通過(guò)基準(zhǔn)測(cè)試通過(guò)基準(zhǔn)測(cè)試程序程序， 不斷改變不斷改變問(wèn)題規(guī)模及機(jī)器規(guī)模進(jìn)行問(wèn)題規(guī)模及機(jī)器規(guī)模進(jìn)行測(cè)試測(cè)試3 3、程序級(jí)性能評(píng)測(cè)、程序級(jí)性能評(píng)測(cè) * *評(píng)測(cè)內(nèi)容：評(píng)測(cè)內(nèi)容：各種系統(tǒng)性能各種系統(tǒng)性能( (如如T Tn n、R Rn n、U U、T TP P等等) ) * *評(píng)測(cè)方法：評(píng)測(cè)方法：通過(guò)基準(zhǔn)測(cè)

8、試程序進(jìn)行通過(guò)基準(zhǔn)測(cè)試程序進(jìn)行測(cè)試測(cè)試 * *基準(zhǔn)測(cè)試程序種類：基準(zhǔn)測(cè)試程序種類： 按按生成方式生成方式真實(shí)、核心、小、綜合程序；真實(shí)、核心、小、綜合程序； 按按應(yīng)用類型應(yīng)用類型科學(xué)計(jì)算、商業(yè)應(yīng)用、信息處理等；科學(xué)計(jì)算、商業(yè)應(yīng)用、信息處理等； 按程序按程序功能功能宏觀測(cè)試程序、微觀測(cè)試宏觀測(cè)試程序、微觀測(cè)試程序程序回15頁(yè)7第二節(jié)第二節(jié) 機(jī)器級(jí)性能評(píng)測(cè)機(jī)器級(jí)性能評(píng)測(cè)一、一、 CPUCPU及存儲(chǔ)器的基本性能指標(biāo)及存儲(chǔ)器的基本性能指標(biāo)轉(zhuǎn)5頁(yè)轉(zhuǎn)3頁(yè) * *基本性能指標(biāo)：基本性能指標(biāo)： 并行并行執(zhí)行時(shí)間執(zhí)行時(shí)間 T Tn n= =T Tcomputcomput+ +T Tcommcomm+ +T Ts

9、yncsync+ +T Tparapara 速度速度- R Rn n= =W W / /T Tn n，為系統(tǒng)實(shí)際速度，為系統(tǒng)實(shí)際速度( (非峰值非峰值) )1 1n n并行度并行度時(shí)間時(shí)間1 1、CPUCPU性能指標(biāo)性能指標(biāo) * *基本參數(shù)：基本參數(shù)：工作負(fù)載工作負(fù)載( (W W ) )、順序執(zhí)行時(shí)間、順序執(zhí)行時(shí)間( (T T1 1) ) 工作工作負(fù)載負(fù)載計(jì)算量計(jì)算量，常用指令或浮點(diǎn)運(yùn)算表示；，常用指令或浮點(diǎn)運(yùn)算表示；( (算法相關(guān)算法相關(guān)) ) 順序順序執(zhí)行時(shí)間執(zhí)行時(shí)間工作負(fù)載在工作負(fù)載在單處理器單處理器上的執(zhí)行時(shí)間上的執(zhí)行時(shí)間82 2、存儲(chǔ)器性能指標(biāo)、存儲(chǔ)器性能指標(biāo) * *存儲(chǔ)器層次結(jié)構(gòu)：

10、存儲(chǔ)器層次結(jié)構(gòu)： 各各層性能指標(biāo)層性能指標(biāo)容量容量C C、延遲、延遲L L、帶寬、帶寬B B； 相關(guān)相關(guān)參數(shù)參數(shù)交換粒度、一致性粒度、層間管理方案交換粒度、一致性粒度、層間管理方案等等 * *影響容量影響容量C設(shè)計(jì)的因素：設(shè)計(jì)的因素： 與應(yīng)用與應(yīng)用的的進(jìn)程數(shù)進(jìn)程數(shù)及各進(jìn)程及各進(jìn)程工作集尺工作集尺寸寸等等有關(guān)有關(guān) * *影響延遲影響延遲L設(shè)計(jì)的因素：設(shè)計(jì)的因素： 與與CPUCPU主頻主頻f f、指令系統(tǒng)、指令系統(tǒng)CPICPI及及帶寬帶寬B等等有關(guān)有關(guān) * *影響帶寬影響帶寬B設(shè)計(jì)的因素：設(shè)計(jì)的因素： 與與應(yīng)用的數(shù)據(jù)應(yīng)用的數(shù)據(jù)通信量通信量、通信頻率通信頻率和和通信延遲通信延遲等有關(guān)等有關(guān)REGRE

11、G一級(jí)一級(jí)CacheCache主存主存二級(jí)二級(jí)CacheCache磁盤(pán)磁盤(pán)遠(yuǎn)程存儲(chǔ)器遠(yuǎn)程存儲(chǔ)器9二、二、 并行及通信開(kāi)銷并行及通信開(kāi)銷2 2、開(kāi)銷量化方法、開(kāi)銷量化方法 * *測(cè)量準(zhǔn)備測(cè)量準(zhǔn)備：選擇選擇測(cè)量所用的參數(shù)，它們會(huì)影響測(cè)量結(jié)果測(cè)量所用的參數(shù)，它們會(huì)影響測(cè)量結(jié)果 ( (數(shù)據(jù)結(jié)構(gòu)、語(yǔ)言數(shù)據(jù)結(jié)構(gòu)、語(yǔ)言及編譯器、通信硬件及協(xié)議、計(jì)時(shí)方法及編譯器、通信硬件及協(xié)議、計(jì)時(shí)方法等等) ) * *測(cè)量方法測(cè)量方法： 點(diǎn)點(diǎn)點(diǎn)點(diǎn)通信通信乒乒- -乓法、熱土豆乓法、熱土豆( (又稱救火隊(duì)又稱救火隊(duì)) )法法等等 集合集合通信通信較復(fù)雜，原則是盡量較復(fù)雜，原則是盡量避免避免/ /減少額外干擾減少額外干擾 *

12、*測(cè)量測(cè)量結(jié)果表示結(jié)果表示： 表格表格法、曲線法、表達(dá)式法法、曲線法、表達(dá)式法等等1 1、開(kāi)銷來(lái)源、開(kāi)銷來(lái)源 * *并行開(kāi)銷：并行開(kāi)銷：包括包括進(jìn)程進(jìn)程/ /進(jìn)程組管理進(jìn)程組管理、數(shù)據(jù)分配、數(shù)據(jù)分配等時(shí)間等時(shí)間 * *通信開(kāi)銷：通信開(kāi)銷：包括通信及包括通信及同步操作時(shí)間同步操作時(shí)間( (軟硬件軟硬件) )103 3、開(kāi)銷量化、開(kāi)銷量化 * *并行性開(kāi)銷：并行性開(kāi)銷： 特性特性-生命周期中分期償還生命周期中分期償還( (總開(kāi)銷總開(kāi)銷/ /計(jì)算量計(jì)算量) )； 量化量化測(cè)量并行性開(kāi)銷對(duì)應(yīng)測(cè)量并行性開(kāi)銷對(duì)應(yīng)的計(jì)算的計(jì)算量；量； 如如：POWER2POWER2處理器的處理器的T T進(jìn)程創(chuàng)建進(jìn)程創(chuàng)建=3

13、72,000=372,000T T浮點(diǎn)運(yùn)算浮點(diǎn)運(yùn)算 結(jié)果結(jié)果計(jì)算粒度較大時(shí)，才需要?jiǎng)?chuàng)建進(jìn)程計(jì)算粒度較大時(shí)，才需要?jiǎng)?chuàng)建進(jìn)程 * *點(diǎn)點(diǎn)通信點(diǎn)點(diǎn)通信( (通信、互斥通信、互斥/ /事件等事件等) )開(kāi)銷：開(kāi)銷： 量化量化-測(cè)量測(cè)量t t(m)=(m)=t t0 0+ +m m/ /R R的各項(xiàng)參數(shù)；的各項(xiàng)參數(shù)； 結(jié)果結(jié)果-根據(jù)根據(jù)t t0 0與與R R關(guān)系確定最佳關(guān)系確定最佳m(m(平衡設(shè)計(jì)原理平衡設(shè)計(jì)原理) ) * *集合通信集合通信( (廣播、集合、柵障等廣播、集合、柵障等) )開(kāi)銷：開(kāi)銷： 量化量化-測(cè)量測(cè)量t t( (m,m,n n)=)=t t0 0( (n n)+)+m m/ /R R

14、( (n n) )的各項(xiàng)參數(shù)；的各項(xiàng)參數(shù)； 結(jié)果結(jié)果-根據(jù)測(cè)量確定軟根據(jù)測(cè)量確定軟/ /硬件功能分配硬件功能分配( (高性高性/ /價(jià)價(jià)) )11三、三、 可用性與好用性可用性與好用性MTTRMTTFMTTF平均修復(fù)時(shí)間平均無(wú)故障時(shí)間平均無(wú)故障時(shí)間可用性 * *可用性的提高：可用性的提高： 方法方法-增加增加MTTFMTTF，或減少，或減少M(fèi)TTRMTTR； 技術(shù)技術(shù)分隔的冗余設(shè)備分隔的冗余設(shè)備( (雙管理機(jī)雙管理機(jī)) )， 故障診斷故障診斷、通知與接管、通知與接管( (如系統(tǒng)監(jiān)控如系統(tǒng)監(jiān)控) )， 故障故障恢復(fù)恢復(fù)( (如檢查點(diǎn)如檢查點(diǎn)) )等等1 1、可用性、可用性 指指系統(tǒng)正常運(yùn)行時(shí)間占

15、總時(shí)間的系統(tǒng)正常運(yùn)行時(shí)間占總時(shí)間的百分比百分比 * *量化方法量化方法：根據(jù)根據(jù)實(shí)際使用情況進(jìn)行測(cè)量與實(shí)際使用情況進(jìn)行測(cè)量與統(tǒng)計(jì)統(tǒng)計(jì) 注意注意排除環(huán)境、人為等因素的干擾排除環(huán)境、人為等因素的干擾122 2、好用、好用性性 指指用戶環(huán)境用戶環(huán)境的好用性的好用性，包括包括環(huán)境系統(tǒng)環(huán)境系統(tǒng)及及界面界面2 2方面方面 * *并行機(jī)用戶環(huán)境：并行機(jī)用戶環(huán)境：命令行命令行遠(yuǎn)程登錄、遠(yuǎn)程登錄、GUIGUIX X協(xié)議、協(xié)議、 客戶客戶GUIGUI服務(wù)器服務(wù)器、瀏覽器瀏覽器WEBWEB服務(wù)器服務(wù)器 * *用戶環(huán)境系統(tǒng)的好用性：用戶環(huán)境系統(tǒng)的好用性： 靈活、易擴(kuò)充和易集成；靈活、易擴(kuò)充和易集成； 使應(yīng)用軟件開(kāi)發(fā)使

16、應(yīng)用軟件開(kāi)發(fā)與平臺(tái)無(wú)關(guān)；與平臺(tái)無(wú)關(guān)； 用戶可不了解低層系統(tǒng)的實(shí)現(xiàn)用戶可不了解低層系統(tǒng)的實(shí)現(xiàn)細(xì)節(jié)；細(xì)節(jié)； 提供提供單一系統(tǒng)單一系統(tǒng)映像映像 * *用戶界面的好用性：用戶界面的好用性： 實(shí)用性實(shí)用性( (提供服務(wù)提供服務(wù)) )、高效、高效性性( (提供幫助提供幫助) )、易學(xué)、易學(xué)習(xí)性習(xí)性( (簡(jiǎn)單簡(jiǎn)單/ /易理易理解解/ /風(fēng)格風(fēng)格統(tǒng)一統(tǒng)一) )、交互、交互性性( (交互交互手段多手段多) )、美觀性、美觀性( (感覺(jué)好感覺(jué)好) )13四、四、 性能與成本性能與成本2 2、性能、性能/ /價(jià)格價(jià)格 指指性能性能/ /買價(jià)，性能常用買價(jià)，性能常用速度速度( (R Rn n) )表示表示 高性能高性

17、能/ /價(jià)格價(jià)格性能性能或性能或性能/ /成本成本不一定好不一定好3 3、成本有效性、成本有效性 指指性能性能/ /成本，性能通常用成本，性能通常用利用率利用率( (U U ) )表示表示 高性能高性能/ /成本成本體系結(jié)構(gòu)體系結(jié)構(gòu)較為較為合理合理1 1、成本與、成本與價(jià)格價(jià)格 常見(jiàn)關(guān)系為：常見(jiàn)關(guān)系為：轉(zhuǎn)3頁(yè)原料成本原料成本直接成本直接成本毛利潤(rùn)毛利潤(rùn)平均折扣平均折扣原料成本原料成本直接成本直接成本原料成本原料成本毛利潤(rùn)毛利潤(rùn)直接成本直接成本原料成本原料成本100%100%75%75%25%25%37.5%37.5%12.5%12.5%50%50%25.1%25.1%8.3%8.3%33.3%

18、33.3%33.3%33.3%成本成本價(jià)格價(jià)格14第三節(jié)第三節(jié) 算法級(jí)性能評(píng)測(cè)算法級(jí)性能評(píng)測(cè)一、一、 并行計(jì)算性能參數(shù)并行計(jì)算性能參數(shù) * *研究加速比的研究加速比的目的：目的： + +對(duì)對(duì)并行算法并行算法，研究，研究順序順序/ /并行并行部分部分對(duì)性能的影響；對(duì)性能的影響； + +對(duì)算法對(duì)算法- -結(jié)構(gòu)，研究結(jié)構(gòu)，研究基于結(jié)構(gòu)的并行性開(kāi)發(fā)基于結(jié)構(gòu)的并行性開(kāi)發(fā)方法方法 性能提高方法性能提高方法有有并行化并行化和和容量容量增加增加2 2方面方面1 1、加速比、加速比 指指對(duì)對(duì)給定應(yīng)用給定應(yīng)用，并行并行相對(duì)于串行的性能相對(duì)于串行的性能提高程度提高程度 即即 SnT1/TnRn /R1，通常，通常

19、1Snn 給定給定應(yīng)用應(yīng)用-指工作負(fù)載指工作負(fù)載W 、處理器數(shù)、處理器數(shù)n為為給定值給定值 * *影響影響S Sn n的的因素：因素：算法并行性、并行機(jī)算法并行性、并行機(jī)體系結(jié)構(gòu)體系結(jié)構(gòu)152 2、可擴(kuò)放性、可擴(kuò)放性 指指對(duì)對(duì)給定應(yīng)用背景給定應(yīng)用背景，性能隨，性能隨P P增加增加( (n) )的的按按比例比例提高能力提高能力 即即 (n,n)=Sn(W)/n/Sn(W)/n ，(n,n)(0,1) 應(yīng)用應(yīng)用背景背景擴(kuò)擴(kuò)放時(shí)對(duì)放時(shí)對(duì)W 及及Tn的要求或限制；的要求或限制； ( (n n, ,n n)為曲線，希望很快接近常數(shù)為曲線，希望很快接近常數(shù) * *影響影響( (n n, ,n n) )的的

20、因素：因素： 算法算法并行性、并行體系結(jié)構(gòu)、應(yīng)用并行性、并行體系結(jié)構(gòu)、應(yīng)用背景等背景等 * *研究可研究可擴(kuò)放擴(kuò)放性的性的目的：目的： + +對(duì)對(duì)給定問(wèn)題給定問(wèn)題，選擇算法及結(jié)構(gòu)選擇算法及結(jié)構(gòu)，以充分利用可擴(kuò)充資源，以充分利用可擴(kuò)充資源 + +對(duì)對(duì)給定應(yīng)用及算法給定應(yīng)用及算法，評(píng)測(cè)體系結(jié)構(gòu)評(píng)測(cè)體系結(jié)構(gòu)的擴(kuò)放性能的擴(kuò)放性能 + +對(duì)對(duì)給定結(jié)構(gòu)給定結(jié)構(gòu)，評(píng)測(cè)評(píng)測(cè)并行算法并行算法的擴(kuò)放性能的擴(kuò)放性能 + +對(duì)對(duì)給定可擴(kuò)充資源給定可擴(kuò)充資源，指導(dǎo)改進(jìn)體系結(jié)構(gòu)和并行算法指導(dǎo)改進(jìn)體系結(jié)構(gòu)和并行算法轉(zhuǎn)6頁(yè)回下頁(yè)回23頁(yè) * *特征：特征：反映反映應(yīng)用應(yīng)用- -算法算法- -結(jié)構(gòu)組合結(jié)構(gòu)組合的有效性的有效性(

21、 (有效利用有效利用n) )16二、擴(kuò)放模型及性能分析二、擴(kuò)放模型及性能分析1 1、應(yīng)用背景與擴(kuò)放模型、應(yīng)用背景與擴(kuò)放模型 * *應(yīng)用背景種類：應(yīng)用背景種類： 實(shí)時(shí)性要求較高實(shí)時(shí)性要求較高關(guān)注關(guān)注Tn，W可不變，如可不變，如WebWeb服務(wù)服務(wù) 結(jié)果精度要求較高結(jié)果精度要求較高關(guān)注關(guān)注，Tn可不變可不變，如，如天氣預(yù)報(bào)天氣預(yù)報(bào) 充分利用硬件資源充分利用硬件資源關(guān)注關(guān)注Un，T Tn n及及W均可變均可變，如，如計(jì)算中心計(jì)算中心 充分利用充分利用CPUCPU和和MEMMEM等等 * *擴(kuò)放模型種類擴(kuò)放模型種類： 固定負(fù)載擴(kuò)放模型固定負(fù)載擴(kuò)放模型增加增加n( (W固定固定) )，以減小，以減小Tn

22、 固定時(shí)間擴(kuò)放模型固定時(shí)間擴(kuò)放模型增加增加n及及W，以，以提高精度提高精度( (保持保持Tn) ) 存儲(chǔ)器受限擴(kuò)放模型存儲(chǔ)器受限擴(kuò)放模型增加增加n及及W，以提高以提高Un * *擴(kuò)放模型性能分析擴(kuò)放模型性能分析： 可用可用3 3個(gè)加速比性能個(gè)加速比性能定律進(jìn)行性能分析定律進(jìn)行性能分析轉(zhuǎn)上頁(yè)回下頁(yè)回19頁(yè)回21頁(yè)172 2、AmdahlAmdahl定律定律 -適用于固定負(fù)載擴(kuò)放適用于固定負(fù)載擴(kuò)放模型模型 * *基本思想基本思想：W不變，不變，增加增加n，以，以提高處理提高處理速度速度( (減小減小Tn ) )時(shí)當(dāng)nffnnnWffWWnS 1)1(1)/)(1( * *定律公式：定律公式：設(shè)設(shè)W

23、 fW (1- -f )W，f 為順序部分比例為順序部分比例，則，則 * *定律幾何意義：定律幾何意義：工作負(fù)載工作負(fù)載(a(a) )固定負(fù)載固定負(fù)載T T1 1n n執(zhí)行時(shí)間執(zhí)行時(shí)間(b)(b)減少執(zhí)行時(shí)間減少執(zhí)行時(shí)間 1 2 3 1 2 3 4 4f f加速比加速比S Sn n102410240% 1% 2% 3% 4% 0% 1% 2% 3% 4% fS1023110241024(c)(c)固定負(fù)載的加速比固定負(fù)載的加速比T Tp pT Tp pT Tp pT Tp pT T1 1T T1 1T T1 1n n 1 2 3 1 2 3 4 4W Wp pW W1 1W Wp pW W1

24、1W Wp pW W1 1W Wp pW W1 19191484831312424轉(zhuǎn)上頁(yè)回下頁(yè)回19頁(yè)18 * *引入引入開(kāi)銷的開(kāi)銷的加速比加速比：設(shè)額外開(kāi)銷為設(shè)額外開(kāi)銷為T(mén)0 0( (含通信含通信/ /同步同步/ /并行化并行化) ) * *定律含義：定律含義： -性能分析性能分析 對(duì)給定工作負(fù)載對(duì)給定工作負(fù)載，Sn1/1/f； 僅增加僅增加n，順序部分依然是瓶頸順序部分依然是瓶頸時(shí)當(dāng)nWTfWnTfnnTnWffWWnS /1/) 1(1)/)(1 (000轉(zhuǎn)上頁(yè)193 3、GustafsonGustafson定律定律 -適用于固定時(shí)間擴(kuò)放適用于固定時(shí)間擴(kuò)放模型模型 * *基本思想基本思想

25、：保持保持Tn不變，增加不變，增加n及及W，以增加計(jì)算量，以增加計(jì)算量( (精度精度) ) * *定律公式：定律公式：設(shè)設(shè)W fW (1- -f )nW，f 為順序部分比例為順序部分比例，則，則fnnnffnnWffWnWffWnS) 1()1 (/)1 ()1 ( * *定律幾何意義：定律幾何意義：工作負(fù)載工作負(fù)載執(zhí)行時(shí)間執(zhí)行時(shí)間n n 1 2 3 1 2 3 4 4T Tp pT T1 1T Tp pT T1 1T Tp pT T1 1T Tp pT T1 1W W1 1n n 1 2 3 1 2 3 4 4W Wp pW Wp pW Wp pW Wp pW W1 1W W1 1W W1

26、1f f加速比加速比S Sn n102410240% 1% 2% 3% 4% 0% 1% 2% 3% 4% (c)(c)固定時(shí)間的加速比固定時(shí)間的加速比10141014(a)(a)規(guī)模擴(kuò)展的負(fù)載規(guī)模擴(kuò)展的負(fù)載(b)(b)固定執(zhí)行時(shí)間固定執(zhí)行時(shí)間10041004993993983983S S10241024=1024-1023=1024-1023f f轉(zhuǎn)16頁(yè)轉(zhuǎn)17頁(yè)回下頁(yè)回21頁(yè)20 * *定律含義：定律含義： -性能分析性能分析 當(dāng)當(dāng)W可擴(kuò)展以保持可擴(kuò)展以保持Tn不變時(shí)，不變時(shí)，Sn是是n的線性的線性函數(shù)函數(shù) 當(dāng)當(dāng)n充分大、充分大、W成比例增加成比例增加時(shí)，時(shí)，順序部分不再是瓶頸順序部分不再

27、是瓶頸 關(guān)鍵：關(guān)鍵：順序部分順序部分fW基本基本不變不變WTnffTWnWffWnS/1)1()1(00轉(zhuǎn)上頁(yè) * *引入引入開(kāi)銷的開(kāi)銷的加速比加速比：設(shè)額外開(kāi)銷為設(shè)額外開(kāi)銷為T(mén)0 0( (含通信含通信/ /同步同步/ /并行化并行化) )214 4、SunSun和和NiNi定律定律 -適用于存儲(chǔ)器受限擴(kuò)放適用于存儲(chǔ)器受限擴(kuò)放模型模型 * *基本思想基本思想：增加增加n及及W ，以提高，以提高Un( (充分利用充分利用CPUCPU和和MEMMEM資源資源) ) * *定律公式：定律公式：設(shè)設(shè)WfW (1- -f )G(n)W，f為順序部分比例為順序部分比例，則，則nnGffnGffnWnGff

28、WWnGffWnS/ )()1()()1(/)()1()()1( * *定律幾何意義：定律幾何意義：工作負(fù)載工作負(fù)載執(zhí)行時(shí)間執(zhí)行時(shí)間n n 1 2 3 1 2 3 4 4T Tp pT T1 1T Tp pT T1 1T Tp pT T1 1T Tp pT T1 1W W1 1n n 1 2 3 1 2 3 4 4W Wp pW Wp pW Wp pW Wp pW W1 1W W1 1W W1 1f f加速比加速比S Sn n102410240% 1% 2% 3% 4% 0% 1% 2% 3% 4% (c)(c)存儲(chǔ)器受限的加速比存儲(chǔ)器受限的加速比10161016(a)(a)規(guī)模擴(kuò)展的負(fù)載規(guī)模

29、擴(kuò)展的負(fù)載(b)(b)執(zhí)行時(shí)間稍增執(zhí)行時(shí)間稍增10071007999999991991ffS25. 025. 1127912801024G(n)=1.25n轉(zhuǎn)16頁(yè)轉(zhuǎn)19頁(yè)回下頁(yè)22WTnnGffnGffTnWnGffWWnGffWnS/ )()1()()1(/)()1()()1(00 * *定律含義：定律含義： -性能分析性能分析 若若G(n)1 1，Sn性能性能與與AmdahlAmdahl定律定律等效等效； 若若G(n)n， Sn性能性能與與GustafsonGustafson定律定律等效等效； 若若G(n)n，Sn性能性能比固定負(fù)載、固定時(shí)間擴(kuò)放模型比固定負(fù)載、固定時(shí)間擴(kuò)放模型都都高高

30、即即W W增增加加速度速度MEMMEM增長(zhǎng)速度增長(zhǎng)速度 ( (n增長(zhǎng)速度增長(zhǎng)速度) )S Sn nn n存儲(chǔ)器受限存儲(chǔ)器受限擴(kuò)放模型擴(kuò)放模型固定時(shí)間固定時(shí)間擴(kuò)放模型擴(kuò)放模型固定負(fù)載固定負(fù)載擴(kuò)放模型擴(kuò)放模型工作工作負(fù)載負(fù)載W( (問(wèn)題規(guī)模問(wèn)題規(guī)模) )機(jī)器規(guī)模機(jī)器規(guī)模 n n固定負(fù)載擴(kuò)放模型固定負(fù)載擴(kuò)放模型通信界限通信界限存儲(chǔ)器界限存儲(chǔ)器界限固定時(shí)間擴(kuò)放模型固定時(shí)間擴(kuò)放模型存儲(chǔ)器受限擴(kuò)放模型存儲(chǔ)器受限擴(kuò)放模型轉(zhuǎn)上頁(yè)回下頁(yè) * *引入引入開(kāi)銷的開(kāi)銷的加速比加速比：設(shè)額外開(kāi)銷為設(shè)額外開(kāi)銷為T(mén)0 0( (含通信含通信/ /同步同步/ /并行化并行化) )23三、可擴(kuò)放性評(píng)測(cè)標(biāo)準(zhǔn)三、可擴(kuò)放性評(píng)測(cè)標(biāo)準(zhǔn) *

31、 *可可擴(kuò)放擴(kuò)放性的特征：性的特征：可用效率、速度、利用率等反映可用效率、速度、利用率等反映11/)(/ )(/)(/ )() ,(nnnnnnnnRRnRnREEnWTWTnWTWTnn1 1、可擴(kuò)放性評(píng)測(cè)標(biāo)準(zhǔn)、可擴(kuò)放性評(píng)測(cè)標(biāo)準(zhǔn)回下頁(yè)轉(zhuǎn)3頁(yè)轉(zhuǎn)上頁(yè)轉(zhuǎn)15頁(yè) 度量方法度量方法解析法、測(cè)量法解析法、測(cè)量法 * *可可擴(kuò)放擴(kuò)放性的度量：性的度量： 存在問(wèn)題存在問(wèn)題W較大時(shí)較大時(shí)T1 1( (W) )無(wú)法測(cè)量無(wú)法測(cè)量Sn等無(wú)法測(cè)量等無(wú)法測(cè)量 解決方法解決方法同時(shí)增加同時(shí)增加n及及W，以保持，以保持性能不變性能不變，用所增加，用所增加的的W來(lái)衡量可擴(kuò)放性來(lái)衡量可擴(kuò)放性 * *可擴(kuò)放性可擴(kuò)放性評(píng)測(cè)標(biāo)準(zhǔn)評(píng)測(cè)

32、標(biāo)準(zhǔn)： 現(xiàn)狀現(xiàn)狀無(wú)公認(rèn)的、定義嚴(yán)格的評(píng)測(cè)標(biāo)準(zhǔn)無(wú)公認(rèn)的、定義嚴(yán)格的評(píng)測(cè)標(biāo)準(zhǔn) 標(biāo)準(zhǔn)標(biāo)準(zhǔn)-等效率標(biāo)準(zhǔn)、等速度標(biāo)準(zhǔn)、等效率標(biāo)準(zhǔn)、等速度標(biāo)準(zhǔn)、等延遲標(biāo)準(zhǔn)等延遲標(biāo)準(zhǔn) ( (解析法解析法) () (測(cè)量法測(cè)量法) () (測(cè)量法測(cè)量法) )回28頁(yè)242 2、等、等效率標(biāo)準(zhǔn)效率標(biāo)準(zhǔn) 用用維持效率不變維持效率不變時(shí)，時(shí)，所需增加的所需增加的W W來(lái)度量可擴(kuò)放性來(lái)度量可擴(kuò)放性 * *等效率需求：等效率需求：增大增大n時(shí)時(shí)，需增大，需增大s，E才可能保持不變才可能保持不變/ )(/),(11),()()(),(/ )()()() 1 (000nsWnsTnsnTsWsWnsTnsWnsWnnTTE(1)(1)等效

33、率函數(shù)等效率函數(shù) 設(shè)問(wèn)題規(guī)模為設(shè)問(wèn)題規(guī)模為s，工作負(fù)載，工作負(fù)載W( (s) )為為s的函數(shù)，的函數(shù)， 并行開(kāi)銷為并行開(kāi)銷為T(mén)0 0( (s, ,n) )為為s及及n的函數(shù)的函數(shù) 則則 * *等效率等效率函數(shù)：函數(shù)：為保持效率為保持效率E不變，增大不變，增大n時(shí)增加時(shí)增加W( (s) )，此時(shí)，此時(shí)W( (s) )與與n的函數(shù)的函數(shù)關(guān)系即為關(guān)系即為等效率等效率函數(shù)函數(shù) 因因E為常數(shù)，則對(duì)上式求解為常數(shù)，則對(duì)上式求解方程，可方程，可得得s y( (n) ) 由由效率效率公式得，公式得，W( (s) )E/( (1-1-E) )nT0 0( (s,s,n) )回下頁(yè)回26頁(yè)轉(zhuǎn)3頁(yè) 等效率函數(shù)等效率

34、函數(shù)為為 fE( (n) )W( (s) )W( ( y( (n)解析法解析法25(2)(2)可擴(kuò)放可擴(kuò)放性評(píng)測(cè)性評(píng)測(cè) * *度量：度量：對(duì)給定的等效率值對(duì)給定的等效率值，可獲得具體的等，可獲得具體的等效率效率函數(shù)函數(shù)系統(tǒng)系統(tǒng)1 1效率效率E En nE E系統(tǒng)系統(tǒng)1 1= =E E系統(tǒng)系統(tǒng)2 2= =E E系統(tǒng)系統(tǒng)3 3等效率函數(shù)等效率函數(shù)f fE E( (n n) )n n系統(tǒng)系統(tǒng)2 2系統(tǒng)系統(tǒng)3 31 1可擴(kuò)放性排序可擴(kuò)放性排序( (好好差差) )結(jié)果：結(jié)果：系統(tǒng)系統(tǒng)11系統(tǒng)系統(tǒng)22系統(tǒng)系統(tǒng)3 3 * *等效率等效率值的特性值的特性：等效率等效率值值E越越小小，可，可擴(kuò)放性越擴(kuò)放性越好好

35、效率效率E En nE E系統(tǒng)系統(tǒng)1 1= =E E系統(tǒng)系統(tǒng)2 2等效率函數(shù)等效率函數(shù)f fE E( (n n) )n n系統(tǒng)系統(tǒng)1 1系統(tǒng)系統(tǒng)2 21 10.50.50.30.3轉(zhuǎn)上頁(yè) * *評(píng)價(jià)：評(píng)價(jià)：等效率等效率函數(shù)函數(shù)fE(n)(n)越越小小，可擴(kuò)放性越，可擴(kuò)放性越好好26 例例兩兩個(gè)個(gè)N NN N 矩陣相乘，矩陣相乘，W W( (s s)=)=cNcN 3 3，A A、B B兩系統(tǒng)運(yùn)行時(shí)間兩系統(tǒng)運(yùn)行時(shí)間分別為分別為 、 ，評(píng)價(jià)等效率值，評(píng)價(jià)等效率值E Ec c分別分別保持保持1/31/3和和1/41/4時(shí)，哪個(gè)系統(tǒng)具有更好的可擴(kuò)放性。時(shí)，哪個(gè)系統(tǒng)具有更好的可擴(kuò)放性。 n/bNcN23

36、)2/(232nbNcN 即即當(dāng)當(dāng)E Ec c=1/3=1/3時(shí)時(shí)，可擴(kuò)放性可擴(kuò)放性A A、B B系統(tǒng)相同系統(tǒng)相同 即即當(dāng)當(dāng)E Ec c=1/4=1/4時(shí)時(shí)，可可擴(kuò)放擴(kuò)放性性B B系統(tǒng)比系統(tǒng)比A A系統(tǒng)系統(tǒng)好好 (1)(1)當(dāng)當(dāng)E Ec c=1/3=1/3時(shí)，時(shí)，1/3=1/3=cNcN 3 3/(/(cNcN 3 3+ +T T0 0) ) 對(duì)對(duì)A A系統(tǒng)系統(tǒng)有有 ，即，即 ， 等效率等效率函數(shù)函數(shù) 對(duì)對(duì)B B系統(tǒng)系統(tǒng)，等效率，等效率函數(shù)函數(shù)322cNnbN)2(ncbN 5 . 13)2/()(ncbcnfE5 . 13)2/()(ncbcnfE (2) (2)當(dāng)當(dāng)E Ec c=1/4=1/4時(shí)，時(shí)，1/4=1/4=cNcN