并行計(jì)算--第2章-并行計(jì)算性能評(píng)價(jià).

1、第2章 并行計(jì)算性能評(píng)價(jià)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 加速比的幾個(gè)問題加速比的幾個(gè)問題n小結(jié)小結(jié)Amdahl定律nAmdahl定律nAmdahl定律nAmdahl定律nAmdahl幾何意義幾何意義計(jì)算負(fù)載固定不變處理機(jī)數(shù)增加，執(zhí)行時(shí)間縮短Amdahl定律nAmdahl幾何意義幾何意義2.1 加速比性能定律n2.1.1 Amdahl定律定律n2.1.2 Gustafsons定理定理n2.1.3 Sun and

2、Nis 定理定理n2.1.4 加速比的幾個(gè)問題加速比的幾個(gè)問題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í)間不變，需要增加處理器增加處理器數(shù)目，可保證執(zhí)行時(shí)間不變Gustafsons定理nGustafsons的幾何意義的幾何意義2.1 加速比性能定律n2.1.1 A

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

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

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

6、加速由于最佳串行算法難于確定，所以相對(duì)加速更為實(shí)用更為實(shí)用n如使用多個(gè)處理機(jī)在一個(gè)樹上并行搜索時(shí)，如使用多個(gè)處理機(jī)在一個(gè)樹上并行搜索時(shí)，一旦某個(gè)處理機(jī)找到解，它就可以立即向其一旦某個(gè)處理機(jī)找到解，它就可以立即向其他處理機(jī)發(fā)出中止搜索信號(hào)，防止無謂地搜他處理機(jī)發(fā)出中止搜索信號(hào)，防止無謂地搜索其他分支，獲得超線性加速。索其他分支，獲得超線性加速。2.1 加速比性能定律n2.1.1 Amdahl定律定律n2.1.2 Gustafsons定理定理n2.1.3 Sun and Nis 定理定理n2.1.4 加速比的幾個(gè)問題加速比的幾個(gè)問題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額外開銷的增加可能慢于有效計(jì)算的增加額外開銷的增加可能慢于有效計(jì)算的增加n算法中的串行分量的比例不是固定不變的算法中的串行分量的比例不是固定不變的并行計(jì)算性能評(píng)價(jià)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ò)放性？一個(gè)計(jì)算機(jī)系統(tǒng)（硬件、軟件、算法、程序一個(gè)計(jì)算機(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確定確定解決某類問題時(shí)何種并行算法與何種并解決某類問題時(shí)何種并行算法與何種并行體系結(jié)構(gòu)的組合，可以有效的利用大量的行體系結(jié)構(gòu)的組合，可以有效的利用大量的處理器處理器；n對(duì)于運(yùn)用于某種并行機(jī)上的某種算法，根據(jù)對(duì)于運(yùn)用于某種并行機(jī)上的某種算法，

10、根據(jù)在小規(guī)模處理機(jī)的運(yùn)行性能預(yù)測(cè)移植到大規(guī)在小規(guī)模處理機(jī)的運(yùn)行性能預(yù)測(cè)移植到大規(guī)模處理機(jī)上的運(yùn)行模處理機(jī)上的運(yùn)行性能性能n對(duì)固定問題規(guī)模，確定最優(yōu)處理機(jī)數(shù)和可獲對(duì)固定問題規(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是一個(gè)給定問題在一臺(tái)機(jī)器上串行執(zhí)行的是一個(gè)給定問題在一臺(tái)機(jī)器上串行執(zhí)行的時(shí)間（例如時(shí)間（例如W），），Tp是在是在p臺(tái)處理機(jī)上并行執(zhí)行臺(tái)處理機(jī)上并行執(zhí)行的時(shí)間，的時(shí)間，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ù)載增長(zhǎng)率與處理機(jī)增長(zhǎng)率之間關(guān)系的有用的工增長(zhǎng)率與處理機(jī)增長(zhǎng)率之間關(guān)系的

12、有用的工具，可用簡(jiǎn)單的、可定量計(jì)算的、少量的參具，可用簡(jiǎn)單的、可定量計(jì)算的、少量的參數(shù)就能計(jì)算出等效率函數(shù)，并由其復(fù)雜性可數(shù)就能計(jì)算出等效率函數(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對(duì)共享存儲(chǔ)器結(jié)構(gòu)的機(jī)器難以計(jì)算等效率函對(duì)共享存儲(chǔ)器結(jié)構(gòu)的機(jī)器難以計(jì)算等效率函數(shù)值數(shù)值ISO-speed 等速度量標(biāo)準(zhǔn)nISO-speed 等速度量標(biāo)準(zhǔn)此時(shí)的可擴(kuò)放的速度度量標(biāo)準(zhǔn)函數(shù)為：此時(shí)的

13、可擴(kuò)放的速度度量標(biāo)準(zhǔn)函數(shù)為：*) ,(WpWppWpWpp 當(dāng)平均速度嚴(yán)格不變時(shí)當(dāng)平均速度嚴(yán)格不變時(shí): :TpWTpWTpTppWWp即：) ,(TpTpppISO-speed 等速度量標(biāo)準(zhǔn)當(dāng)p=1時(shí)，間的問題所需并行工作時(shí)解決工作量為間的問題所需串行工作時(shí)解決工作量為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ò)放性是比較直觀的（速度常被用來測(cè)量浮點(diǎn)可擴(kuò)放性是比較直觀的（速度

14、常被用來測(cè)量浮點(diǎn)運(yùn)算）運(yùn)算）n速度是由工作負(fù)載速度是由工作負(fù)載W和執(zhí)行時(shí)間和執(zhí)行時(shí)間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í)行時(shí)間包含了計(jì)算和延遲這兩個(gè)主要的時(shí)間量執(zhí)行時(shí)間包含了計(jì)算和延遲這兩個(gè)主要的時(shí)間量n.速度是比較容易測(cè)量的。（如何使用浮點(diǎn)操作數(shù)量）速度是比較容易測(cè)量的。（如何使用浮點(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í)行時(shí)間中，但它明確地定

15、義延遲雖包含在執(zhí)行時(shí)間中，但它明確地定義為為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)系。平。平均延遲均延遲時(shí)間定義為一個(gè)處理機(jī)完成分配給他的任務(wù)時(shí)間定義為一個(gè)處理機(jī)完成分配給他的任務(wù)所需要的平均時(shí)間開銷。包括運(yùn)行時(shí)的延遲所需要的平均時(shí)間開銷。包括運(yùn)行時(shí)的延遲Li，啟動(dòng)時(shí)間及停止時(shí)，啟動(dòng)時(shí)間及停止時(shí)間間。 因此因此第第i個(gè)處理器個(gè)處理器Pi的總的延遲時(shí)間的總的延遲時(shí)間為為： Li + 啟動(dòng)時(shí)間啟動(dòng)時(shí)間 +停止時(shí)間停止時(shí)間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)的平均延遲時(shí)系統(tǒng)的平均延遲時(shí)間為間為：piparapLiTiTpWL1)(),(由于由于),(00pWLpTTTpTseqpara和所以所以pTTpWLseqpara),(Aerage Lantency 平均延遲度量標(biāo)準(zhǔn)令令),(pWL表示在表示在p個(gè)處理器上求解工作個(gè)處理器上求解工作 量為量為W問題的平均延遲問題的平均延遲，) , (pWL表示表示在在p個(gè)處理器上求解工作量為個(gè)處理器上求解工作量為W問題問題的平均延遲，則定義平均延遲可擴(kuò)放的平均延遲，則定義平均延遲可擴(kuò)放性度量標(biāo)準(zhǔn)為性度量標(biāo)準(zhǔn)為：) , (),() ,(pWLpWLppEAerage Lantency 平均延遲度量標(biāo)