并行計算--第2章-并行計算性能評價.

1、第2章 并行計算性能評價2.1 加速比性能定律加速比性能定律2.2 可擴(kuò)放性可擴(kuò)放性2.1 加速比性能定律n2.1.1 Amdahl定律定律n2.1.2 Gustafsons定理定理n2.1.3 Sun and Nis 定理定理n2.1.4 加速比的幾個問題加速比的幾個問題n小結(jié)小結(jié)Amdahl定律nAmdahl定律nAmdahl定律nAmdahl定律nAmdahl幾何意義幾何意義計算負(fù)載固定不變處理機(jī)數(shù)增加，執(zhí)行時間縮短Amdahl定律nAmdahl幾何意義幾何意義2.1 加速比性能定律n2.1.1 Amdahl定律定律n2.1.2 Gustafsons定理定理n2.1.3 Sun and

2、Nis 定理定理n2.1.4 加速比的幾個問題加速比的幾個問題n小結(jié)小結(jié)Gustafsons定理nGustafsons定理nS=(Ws+p*Wp)/(Ws+p*Wp/p) =(Ws+p*Wp)/(Ws+Wp) =f+p*(1-f) =p+f(1-p) =p-f(p-1)可見可見:加速比加速比S與處理機(jī)數(shù)目與處理機(jī)數(shù)目p基礎(chǔ)成線性關(guān)系基礎(chǔ)成線性關(guān)系Gustafsons定理nGustafsons的幾何意義的幾何意義工作量增加，為了保證處理時間不變，需要增加處理器增加處理器數(shù)目，可保證執(zhí)行時間不變Gustafsons定理nGustafsons的幾何意義的幾何意義2.1 加速比性能定律n2.1.1 A

3、mdahl定律定律n2.1.2 Gustafsons定理定理n2.1.3 Sun and Nis 定理定理n2.1.4 加速比的幾個問題加速比的幾個問題n小結(jié)小結(jié)Sun and Nis 定理n在在Amdahl和和Gustafson定理中，都是認(rèn)為處定理中，都是認(rèn)為處理機(jī)數(shù)和存儲容量是不受限制地可增加的，但理機(jī)數(shù)和存儲容量是不受限制地可增加的，但可能有一些大的求解問題可能要受到存儲容量可能有一些大的求解問題可能要受到存儲容量的限制。這就是要求規(guī)劃負(fù)載。提供更高的加的限制。這就是要求規(guī)劃負(fù)載。提供更高的加速比、更高的精度和更好的資源利用率。速比、更高的精度和更好的資源利用率。n假定一個負(fù)載計算量可

4、以由于并行劃分而增加假定一個負(fù)載計算量可以由于并行劃分而增加G(p)倍，（倍，（G(p)代表負(fù)載量增加時，存儲容代表負(fù)載量增加時，存儲容量（需求）也增加量（需求）也增加p倍。）倍。）Sun and Nis 定理nSun and Nis 定理nSun and Nis 定理nSun and Nis 定理幾何意義定理幾何意義處理能力隨處理器數(shù)目的增加而增加處理器的增加，執(zhí)行時間隨之增加2.1 加速比性能定律n2.1.1 Amdahl定律定律n2.1.2 Gustafsons定理定理n2.1.3 Sun and Nis 定理定理n2.1.4 加速比的幾個問題加速比的幾個問題n小結(jié)小結(jié)加速比的幾個問題n

5、絕對加速絕對加速n對于給定的問題，最佳串行算法能使用的時間除以對于給定的問題，最佳串行算法能使用的時間除以同一問題的并行算法所使用的時間同一問題的并行算法所使用的時間n相對加速相對加速n同一問題的求解算法在單處理機(jī)上運(yùn)行的時間除以同一問題的求解算法在單處理機(jī)上運(yùn)行的時間除以在多個處理機(jī)上的運(yùn)行時間在多個處理機(jī)上的運(yùn)行時間n超線性加速超線性加速n一般的講，線性加速已很難達(dá)到，超線性加速則是一般的講，線性加速已很難達(dá)到，超線性加速則是難上加難。但在某些算法中，可能出現(xiàn)超線性加速難上加難。但在某些算法中，可能出現(xiàn)超線性加速現(xiàn)象?，F(xiàn)象。加速比的幾個問題n結(jié)論：結(jié)論：n由于最佳串行算法難于確定，所以相對

6、加速由于最佳串行算法難于確定，所以相對加速更為實(shí)用更為實(shí)用n如使用多個處理機(jī)在一個樹上并行搜索時，如使用多個處理機(jī)在一個樹上并行搜索時，一旦某個處理機(jī)找到解，它就可以立即向其一旦某個處理機(jī)找到解，它就可以立即向其他處理機(jī)發(fā)出中止搜索信號，防止無謂地搜他處理機(jī)發(fā)出中止搜索信號，防止無謂地搜索其他分支，獲得超線性加速。索其他分支，獲得超線性加速。2.1 加速比性能定律n2.1.1 Amdahl定律定律n2.1.2 Gustafsons定理定理n2.1.3 Sun and Nis 定理定理n2.1.4 加速比的幾個問題加速比的幾個問題n小結(jié)小結(jié)小結(jié)n影響加速比的因素影響加速比的因素：n求解問題中的串

7、行分量求解問題中的串行分量n并行處理所引起的額外開銷（通信，等待，并行處理所引起的額外開銷（通信，等待，冗余操作等）冗余操作等）n處理機(jī)數(shù)目的增加超過了算法中的并發(fā)程度處理機(jī)數(shù)目的增加超過了算法中的并發(fā)程度小結(jié)n增加問題的規(guī)模有利于提高加速比的因素增加問題的規(guī)模有利于提高加速比的因素：n加大問題的規(guī)?？商峁┹^高的并發(fā)程度加大問題的規(guī)模可提供較高的并發(fā)程度n額外開銷的增加可能慢于有效計算的增加額外開銷的增加可能慢于有效計算的增加n算法中的串行分量的比例不是固定不變的算法中的串行分量的比例不是固定不變的并行計算性能評價2.1 加速比性能定律加速比性能定律2.2 可擴(kuò)放性可擴(kuò)放性可擴(kuò)放性n2.2.1

8、 概念概念n2.2.2 等效率度量標(biāo)準(zhǔn)等效率度量標(biāo)準(zhǔn)n2.2.3 等速度度量標(biāo)準(zhǔn)等速度度量標(biāo)準(zhǔn)n2.2.4 平均延遲度量標(biāo)準(zhǔn)平均延遲度量標(biāo)準(zhǔn)概念n什么是可擴(kuò)放性什么是可擴(kuò)放性？一個計算機(jī)系統(tǒng)（硬件、軟件、算法、程序一個計算機(jī)系統(tǒng)（硬件、軟件、算法、程序等）被稱為可擴(kuò)放的，是指其性能隨處理機(jī)等）被稱為可擴(kuò)放的，是指其性能隨處理機(jī)數(shù)目的增加而按比例提高。例如，工作負(fù)載數(shù)目的增加而按比例提高。例如，工作負(fù)載能力和加速比都可隨處理機(jī)的數(shù)目的增加而能力和加速比都可隨處理機(jī)的數(shù)目的增加而增加。增加。概念n可擴(kuò)放性包括哪些方面可擴(kuò)放性包括哪些方面?n機(jī)器規(guī)模的可擴(kuò)放性機(jī)器規(guī)模的可擴(kuò)放性系統(tǒng)性能是如何隨著處理

9、機(jī)數(shù)目的增加而改善的系統(tǒng)性能是如何隨著處理機(jī)數(shù)目的增加而改善的n問題規(guī)模的可擴(kuò)放性問題規(guī)模的可擴(kuò)放性系統(tǒng)的性能是如何隨著數(shù)據(jù)規(guī)模和負(fù)載規(guī)模的增系統(tǒng)的性能是如何隨著數(shù)據(jù)規(guī)模和負(fù)載規(guī)模的增加而改善加而改善n技術(shù)的可擴(kuò)放性技術(shù)的可擴(kuò)放性系統(tǒng)的性能上如何隨著技術(shù)的改變而改善系統(tǒng)的性能上如何隨著技術(shù)的改變而改善概念n可擴(kuò)放性研究的可擴(kuò)放性研究的目的目的是什么是什么？n確定確定解決某類問題時何種并行算法與何種并解決某類問題時何種并行算法與何種并行體系結(jié)構(gòu)的組合，可以有效的利用大量的行體系結(jié)構(gòu)的組合，可以有效的利用大量的處理器處理器；n對于運(yùn)用于某種并行機(jī)上的某種算法，根據(jù)對于運(yùn)用于某種并行機(jī)上的某種算法，

10、根據(jù)在小規(guī)模處理機(jī)的運(yùn)行性能預(yù)測移植到大規(guī)在小規(guī)模處理機(jī)的運(yùn)行性能預(yù)測移植到大規(guī)模處理機(jī)上的運(yùn)行模處理機(jī)上的運(yùn)行性能性能n對固定問題規(guī)模，確定最優(yōu)處理機(jī)數(shù)和可獲對固定問題規(guī)模，確定最優(yōu)處理機(jī)數(shù)和可獲得的最大的得的最大的加速比加速比概念n指導(dǎo)和改進(jìn)并行算法和并行處理機(jī)結(jié)構(gòu)，充指導(dǎo)和改進(jìn)并行算法和并行處理機(jī)結(jié)構(gòu)，充分利用處理機(jī)可擴(kuò)放性的度量標(biāo)準(zhǔn)分利用處理機(jī)可擴(kuò)放性的度量標(biāo)準(zhǔn)nISO-efficiency等效度量標(biāo)準(zhǔn)等效度量標(biāo)準(zhǔn) nISO-speed 等速度量標(biāo)準(zhǔn)等速度量標(biāo)準(zhǔn)nAerage Lantency 平均延遲度量標(biāo)準(zhǔn)平均延遲度量標(biāo)準(zhǔn)等效率度量標(biāo)準(zhǔn)（ISO-efficiency）n基本概念基本

11、概念n等效度量標(biāo)準(zhǔn)是研究如何維持并行系統(tǒng)的等效性等效度量標(biāo)準(zhǔn)是研究如何維持并行系統(tǒng)的等效性n推導(dǎo)推導(dǎo)n設(shè)設(shè)T1是一個給定問題在一臺機(jī)器上串行執(zhí)行的是一個給定問題在一臺機(jī)器上串行執(zhí)行的時間（例如時間（例如W），），Tp是在是在p臺處理機(jī)上并行執(zhí)行臺處理機(jī)上并行執(zhí)行的時間，的時間，T0是額外開銷是額外開銷等效率度量標(biāo)準(zhǔn)（ISO-efficiency）n等效率度量標(biāo)準(zhǔn)（ISO-efficiency）n等效率度量標(biāo)準(zhǔn)（ISO-efficiency）n優(yōu)點(diǎn)優(yōu)點(diǎn)n等效率函數(shù)是一種用分析方法處理工作負(fù)載等效率函數(shù)是一種用分析方法處理工作負(fù)載增長率與處理機(jī)增長率之間關(guān)系的有用的工增長率與處理機(jī)增長率之間關(guān)系的

12、有用的工具，可用簡單的、可定量計算的、少量的參具，可用簡單的、可定量計算的、少量的參數(shù)就能計算出等效率函數(shù)，并由其復(fù)雜性可數(shù)就能計算出等效率函數(shù)，并由其復(fù)雜性可指出算法的可擴(kuò)放程度指出算法的可擴(kuò)放程度n如果如果W與與p呈線性關(guān)系，則系統(tǒng)是可擴(kuò)放的呈線性關(guān)系，則系統(tǒng)是可擴(kuò)放的n如果如果W與與p呈指數(shù)關(guān)系，則系統(tǒng)是不可擴(kuò)放的呈指數(shù)關(guān)系，則系統(tǒng)是不可擴(kuò)放的等效率度量標(biāo)準(zhǔn)（ISO-efficiency）n缺點(diǎn)缺點(diǎn)n對共享存儲器結(jié)構(gòu)的機(jī)器難以計算等效率函對共享存儲器結(jié)構(gòu)的機(jī)器難以計算等效率函數(shù)值數(shù)值ISO-speed 等速度量標(biāo)準(zhǔn)nISO-speed 等速度量標(biāo)準(zhǔn)此時的可擴(kuò)放的速度度量標(biāo)準(zhǔn)函數(shù)為：此時的

13、可擴(kuò)放的速度度量標(biāo)準(zhǔn)函數(shù)為：*) ,(WpWppWpWpp 當(dāng)平均速度嚴(yán)格不變時當(dāng)平均速度嚴(yán)格不變時: :TpWTpWTpTppWWp即：) ,(TpTpppISO-speed 等速度量標(biāo)準(zhǔn)當(dāng)p=1時，間的問題所需并行工作時解決工作量為間的問題所需串行工作時解決工作量為WW1) , 1 (pWWTpTpn結(jié)論n如果速度能與處理機(jī)的數(shù)目的增加而線性增加，即意味著平均速度不變，則說明此系統(tǒng)具有很好的擴(kuò)放性ISO-speed 等速度量標(biāo)準(zhǔn)n優(yōu)點(diǎn)優(yōu)點(diǎn)n使用機(jī)器性能速度指標(biāo)這一明確的物理量來度量使用機(jī)器性能速度指標(biāo)這一明確的物理量來度量可擴(kuò)放性是比較直觀的（速度常被用來測量浮點(diǎn)可擴(kuò)放性是比較直觀的（速度

14、常被用來測量浮點(diǎn)運(yùn)算）運(yùn)算）n速度是由工作負(fù)載速度是由工作負(fù)載W和執(zhí)行時間和執(zhí)行時間T決定的，而決定的，而W反映了反映了應(yīng)用程序的性質(zhì)，應(yīng)用程序的性質(zhì)，T反映了結(jié)構(gòu)和程序效率的影響反映了結(jié)構(gòu)和程序效率的影響n速度在各種結(jié)構(gòu)的機(jī)器之間具有可比性速度在各種結(jié)構(gòu)的機(jī)器之間具有可比性n執(zhí)行時間包含了計算和延遲這兩個主要的時間量執(zhí)行時間包含了計算和延遲這兩個主要的時間量n.速度是比較容易測量的。（如何使用浮點(diǎn)操作數(shù)量）速度是比較容易測量的。（如何使用浮點(diǎn)操作數(shù)量）ISO-speed 等速度量標(biāo)準(zhǔn)n缺點(diǎn)缺點(diǎn)n某些非浮點(diǎn)運(yùn)算可造成性能的變化某些非浮點(diǎn)運(yùn)算可造成性能的變化n延遲雖包含在執(zhí)行時間中，但它明確地定

15、義延遲雖包含在執(zhí)行時間中，但它明確地定義為為W的函數(shù)的函數(shù)Aerage Lantency 平均延遲度量標(biāo)準(zhǔn)n基本概基本概念念n效率不變前提下，用平均延遲來標(biāo)志處理機(jī)效率不變前提下，用平均延遲來標(biāo)志處理機(jī)數(shù)數(shù)p和工作量和工作量W之間的增量關(guān)系之間的增量關(guān)系。平。平均延遲均延遲時間定義為一個處理機(jī)完成分配給他的任務(wù)時間定義為一個處理機(jī)完成分配給他的任務(wù)所需要的平均時間開銷。包括運(yùn)行時的延遲所需要的平均時間開銷。包括運(yùn)行時的延遲Li，啟動時間及停止時，啟動時間及停止時間間。 因此因此第第i個處理器個處理器Pi的總的延遲時間的總的延遲時間為為： Li + 啟動時間啟動時間 +停止時間停止時間Aerag

16、e Lantency 平均延遲度量標(biāo)準(zhǔn)12345TparaT1T2T3 T4T5T6T7T8P3P4P5P6P7P8T5 = TparaP1P2idle time before starting / stoppingthe computation time on each processor ( T i )o v e r h e a d s latency ( L i ) Aerage Lantency 平均延遲度量標(biāo)準(zhǔn)系統(tǒng)的平均延遲時系統(tǒng)的平均延遲時間為間為：piparapLiTiTpWL1)(),(由于由于),(00pWLpTTTpTseqpara和所以所以pTTpWLseqpara),(Aerage Lantency 平均延遲度量標(biāo)準(zhǔn)令令),(pWL表示在表示在p個處理器上求解工作個處理器上求解工作 量為量為W問題的平均延遲問題的平均延遲，) , (pWL表示表示在在p個處理器上求解工作量為個處理器上求解工作量為W問題問題的平均延遲，則定義平均延遲可擴(kuò)放的平均延遲，則定義平均延遲可擴(kuò)放性度量標(biāo)準(zhǔn)為性度量標(biāo)準(zhǔn)為：) , (),() ,(pWLpWLppEAerage Lantency 平均延遲度量標(biāo)