并行算法第二章 并行計算性能測評

1、1 第二章 并行計算性能測評 2 Questions 1 對自己的計算機(手機)有 沒有不滿意的地方？ 3 有沒有評價是否值得升級？ 2 有沒有升過級？ 機器 性能 3 主要內(nèi)容 1 2 4 3 什么是并行計算機的基本性能？什么是并行計算機的基本性能？ 為什么要研究機器的性能測評？為什么要研究機器的性能測評？ 如何測評計算機的性能？如何測評計算機的性能？ 如何提高并行系統(tǒng)的性能？如何提高并行系統(tǒng)的性能？ 4 計算機的性能 ?Performance: 通常是指機器的速度，它是程 序執(zhí)行時間的倒數(shù) ?程序執(zhí)行時間：是指用戶的響應(yīng)時間 (訪問磁 盤和訪問存儲器的時間， CPU 時間， I/O 時 間

2、以及操作系統(tǒng)的開銷 ) ?CPU時間：它表示CPU的工作時間，不包括 I/O等待時間和運行其它任務(wù)的時間 5 為什么要進行并行機性能評測？ ?對管理人員來說：對管理人員來說： ?發(fā)揮并行機長處，提高并行機的使用效率發(fā)揮并行機長處，提高并行機的使用效率 ?對用戶來說對用戶來說 ?減少用戶購機盲目性，降低投資風(fēng)險減少用戶購機盲目性，降低投資風(fēng)險 ?對架構(gòu)師和設(shè)計人員來說：對架構(gòu)師和設(shè)計人員來說： ?改進系統(tǒng)結(jié)構(gòu)設(shè)計，提高機器的性能改進系統(tǒng)結(jié)構(gòu)設(shè)計，提高機器的性能 ?促進軟/硬件結(jié)合，合理功能劃分硬件結(jié)合，合理功能劃分 ?優(yōu)化 “結(jié)構(gòu)結(jié)構(gòu)-算法算法-應(yīng)用應(yīng)用”的最佳組合的最佳組合 ?對市場人士來說：

3、對市場人士來說： ?提供客觀、公正的評價并行機的標(biāo)準(zhǔn)提供客觀、公正的評價并行機的標(biāo)準(zhǔn) 如何進行并行機性能評測 CPU與存儲器 并行和通信開銷 機器的性價比 Linpack測試標(biāo)準(zhǔn) 機器級性機器級性 能測評能測評 算法級性 能測評 程序級性 能測評 加速比 效率 可擴放性 性能 測評 7 CPU的某些基本性能指標(biāo) ? 工作負(fù)載工作負(fù)載 ?執(zhí)行時間 ?浮點運算數(shù) ?指令數(shù)目 ? 并行執(zhí)行時間 T comput 為計算時間，T paro 為并行開銷 時間，T comm為相互通信時間 T n = T comput + T paro + T comm 8 算法級性能評測 1 加速比性能定律 Amdahl

4、定律 Gustafson定律 Sun和Ni定律 2 可擴放性測評標(biāo)準(zhǔn) 等效率測評標(biāo)準(zhǔn) 等速度測評標(biāo)準(zhǔn) 平均延遲度量標(biāo)準(zhǔn) 9 2.1 加速比定律 ?并行系統(tǒng)的加速比并行系統(tǒng)的加速比:對于一個給定的應(yīng)用， 并行算并行算 法（或并行程序）的執(zhí)行速度 相對于串行算法 （或 串行程序）的串行程序）的執(zhí)行速度加快了多少倍執(zhí)行速度加快了多少倍 。 ?相關(guān)定律： ?Amdahl定律：定律： ?Gustafson定律： ?Sun和Ni定律： 固定計算負(fù)載 固定計算時間 受限于存儲器 10 一、Amdahl 定律-固定計算負(fù)載 ?出發(fā)點出發(fā)點應(yīng)用于實時性要求較高的科學(xué)計算應(yīng)用于實時性要求較高的科學(xué)計算 ?固定不變

5、的計算負(fù)載固定不變的計算負(fù)載 ?固定的計算負(fù)載分布在多個處理器上的固定的計算負(fù)載分布在多個處理器上的 ?增加處理器加快執(zhí)行速度，從而達到了加速的增加處理器加快執(zhí)行速度，從而達到了加速的 目的目的 11 1.相關(guān)參數(shù) ? P：處理器數(shù) ? W：問題規(guī)模（計算負(fù)載、工作負(fù)載，給定問題的總計算量） ?Ws：應(yīng)用程序中的串行分量，f是串行分量比例（f = Ws/W， W s=W1 ） ?WP：應(yīng)用程序中可并行化部分，1-f 為并行分量比例 ?Ws+W p=W ? Ts=T 1 ：串行執(zhí)行時間，Tp ：并行執(zhí)行時間； ? S：加速比，E：效率； 12 2.加速比公式 ?固定負(fù)載的加速公式：固定負(fù)載的加速

6、公式： ?W s+ W p可相應(yīng)地表示為 可相應(yīng)地表示為f+（1-f ） ?p時，上式極限為：時，上式極限為： S= 1 / f pWWs WpWs S P /? ? ? )1(1 1 )1( ? ? ? ? ? ? pf p p f f ff S 并行系統(tǒng)所能達到的 加速比上限為1/f，在 歷史上起悲觀的作用。 13 3.Amdahl定律的幾何意義 不論PE個數(shù)有多 少，可并行計算量 是不變的。 14 Amdahl定律的幾何意義 隨著隨著PE的增大，Tp可能可能 會越來越小，但T1不會 改變 15 Amdahl定律的幾何意義 16 4. 修改后的加速比考慮額外開銷 ? W o為額外開銷 ?

7、p時，上式極限為時，上式極限為 ? 串行分量和并行額外開銷的比例越大，則加速比越小。 WpWpf p W p fW fW W W p W W WW S P S PS /) 1(1 )1 ( 0 00 ? ? ? ? ? ? ? ? ? wwf S / 1 0 ? ? 17 例題 在不考慮通信開銷的情況下，若達到（不小于） 50%的加速效率（加速比與 p的比值），串行 計算部分f和所使用的處理器數(shù)目 p之間應(yīng)該存 在怎么樣的不等式關(guān)系？ 若 f=0.5, 則p只能取多少？ 18 二、Gustafson定律 ? 出發(fā)點：出發(fā)點： ?對于很多大型計算，對于很多大型計算，精度要求很高，即在此類應(yīng)用，即

8、在此類應(yīng)用 中精度是個關(guān)鍵因素，而計算時間是固定不變的。 此時為了提高精度，必須此時為了提高精度，必須加大計算量，相應(yīng)地亦必 須增多處理器數(shù)須增多處理器數(shù)才能維持時間不變； ?除非學(xué)術(shù)研究，在實際應(yīng)用中沒有必要固定工作負(fù) 載而計算程序運行在不同數(shù)目的處理器上，增多處增多處 理器必須相應(yīng)地增大問題規(guī)模才有實際意義。 19 1. 加速比公式 ?Gustafson加速定律 : ?說明： ?當(dāng)f很小時，S與P斜率為1-f ?當(dāng)p 時，S隨著PE的增加而增加，幾乎與 處理器數(shù)成比例的線性增加 ，f不再是程序的 瓶頸 PS S S S WW pWpW pWppW pWpW S ? ? ? ? ? ? /

9、f -f) p (S ?1 20 2. Gustafson定律幾何意義 處理器的增多，是為了 增加計算量，將同等大 小問題在各PE上求解 21 增加增加PE的同時，問題規(guī)的同時，問題規(guī) 模也增大，所以TP不變 2. Gustafson定律幾何意義 22 2. Gustafson定律幾何意義 23 3. 修改后的加速比 ?并行開銷W o ： ?注意： ?W0是P的函數(shù)，可能隨著P增大、減小或不變 ?要達到線性加速，必須使 W0隨P減少，但一般 比較困難 ? WW fpf WWW pWW S OOPS PS /1 1 ? ? ? ? ? ? 24 三、Sun 和 Ni定律 ?Xian-He Sun

10、和和Lionel Ni于于1993將將Amdahl定定 律和律和Gustafson定律一般化，提出了定律一般化，提出了 存儲受限存儲受限的的 加速定律。加速定律。 25 Sun 和 Ni定律 ? 基本思想： ?只要存儲空間許可，應(yīng)盡量增大問題規(guī)模以產(chǎn)生更好和 更精確的解（此時可能使執(zhí)行時間略有增加）。 ?假定在單節(jié)點上使用了全部存儲容量M并在相應(yīng)于W的 時間內(nèi)求解之，此時工作負(fù)載W= fW + （1-f ）W。 ?在p 個節(jié)點的并行系統(tǒng)上，能夠求解較大規(guī)模的問題是 因為存儲容量可增加到pM。令因子G（p）反應(yīng)存儲容 量增加到p倍時并行工作負(fù)載的增加量，所以擴大后的 工作負(fù)載W = fW + （

11、1-f ）G（p）W。 26 1. 加速比公式 ?G（p）：存儲容量增加到p倍時并行工作負(fù)載的增加 情況 ?擴大存儲容量后的工作負(fù)載 W =fw+(1-f)G(p)W ? ? ? ? ? ?pWpGffW WpGffW S /1 1 ? ? ? ? ? ? ? ? ?ppGff pGff /1 1 ? ? ? 27 Sun 和 Ni定律 ? G（p）=1 時； ? G（p）=p 時： ? G（p）p 時：計算機負(fù)載比存儲要求增加得快，此時 Sun 和 N i 加速均比 Amdahl 加速和 Gustafson 加速為高。 ? ? ? ? ? ?ppGff pGff S /1 1 ? ? ? ?

12、pff SS /1 1 ? ? -Amdahl 加速定律 )1 ( fpfSS?- Gustafson 加速定律 28 Sun 和 Ni定律 29 Sun 和 Ni定律 30 修改后的加速比 ?并行開銷并行開銷W o: ? ? ? ? ? ? ? ? ? ? ? ?WWppGff pGff WpWpGffW pWGffW S OO /1 1 /1 1 ? ? ? ? ? ? 31 四、加速比討論 ? 參考的加速經(jīng)驗公式： p/log pSP ?線性加速比：很少通信開銷的矩陣相加、內(nèi)積運算等 ?p/log p的加速比：分治類的應(yīng)用問題 ? 通信密集類的應(yīng)用問題 ：S = 1 / C （ p ）

13、? 超線性加速 ：SP ? 絕對加速：最佳并行算法與串行算法 ? 相對加速：同一算法在單機和并行機的運行時間 科學(xué)研究 者使用 工程實用者 32 2.2 可擴放性評測標(biāo)準(zhǔn) ?并行計算的可擴放性（ Scalability ） 評價并行計算性能的又一指標(biāo) 計算機系統(tǒng)（或算法或程序等）性能隨處理 器數(shù)的增加而按比例提高的能力 反映并行算法能否有效利用可擴充 PE數(shù)的能 力 33 一、并行計算的可擴放性 ?加速比：加速比：由由3個定律可知，增加個定律可知，增加PE和求解問題的和求解問題的 規(guī)?？梢蕴岣呒铀俦??影響加速比的因素：處理器數(shù)與問題規(guī)模影響加速比的因素：處理器數(shù)與問題規(guī)模 ?求解問題中的串行

14、分量 ?并行處理所引起的 額外開銷（通信、等待、 競爭、冗余操作和同步等） ?加大的處理器數(shù)超過了算法中的 并發(fā)程度 34 一、并行計算的可擴放性 ?增加規(guī)模有利于提高加速比的因素：增加規(guī)模有利于提高加速比的因素： ?較大的問題規(guī)?？梢?提高較高的并發(fā)度 ?額外開銷的增加可能 慢于有效計算的增加 ?算法中的串行分量比例不是固定不變 的（因 問題規(guī)模增加而縮?。?35 可擴放性評測標(biāo)準(zhǔn) ?增加處理器數(shù)，會增大額外開銷和降低處理器增加處理器數(shù)，會增大額外開銷和降低處理器 利用率，所以對于一個特定的并行系統(tǒng)（算法利用率，所以對于一個特定的并行系統(tǒng)（算法 或程序），它們或程序），它們能否有效利用不斷增

15、加的處理能否有效利用不斷增加的處理 器的能力應(yīng)是受限的器的能力應(yīng)是受限的 ，而度量這種能力就是，而度量這種能力就是 可 擴放性這一指標(biāo)。這一指標(biāo)。 36 1.可擴放性的內(nèi)涵 ?可擴放性:調(diào)整什么和按什么比例調(diào)整調(diào)整什么和按什么比例調(diào)整 ?并行計算要調(diào)整的是 處理數(shù)p和問題規(guī)模W ?兩者可按不同比例進行調(diào)整，此比例關(guān)系兩者可按不同比例進行調(diào)整，此比例關(guān)系 （可能是線性的，多項式的或指數(shù)的等）就 反映了可擴放的程度 37 可擴放性評測標(biāo)準(zhǔn) ? 可擴放性研究的主要目的：可擴放性研究的主要目的： ?確定解決某類問題用何種并行算法與何種并行體系 結(jié)構(gòu)的組合，可以有效地利用大量的處理器； ?對于運行于某種

16、體系結(jié)構(gòu)的并行機上的某種算法當(dāng) 移植到大規(guī)模處理機上后運行的性能； ?對固定的問題規(guī)模，確定在某類并行機上最優(yōu)的處 理器數(shù)與可獲得的最大的加速比； ?用于指導(dǎo)改進并行算法和并行機體系結(jié)構(gòu)，以使并 行算法盡可能地充分利用可擴充的大量處理器。 38 2.2.1 等效率度量標(biāo)準(zhǔn) ? 令tie ：并行系統(tǒng)上第i個處理器的有用計算時間 ? t io：第i個處理器的額外開銷時間（包括通信、同步和空 閑等待時間等） ? T p ：p個處理器系統(tǒng)上并行算法的運行時間 ? W：串行算法所完成的計算量 ? 對于任意i，顯然有T p = tie + t io ，且 T e+ T o= pT p ? 問題的規(guī)模W為最

17、佳串行算法所完成的計算量W=Te ? ? ? ? 1 0 p i i ee tT ? ? ? ? 1 0 p i i oo tT 39 等效率度量標(biāo)準(zhǔn) W T p T T p p TT T T T S o e ooe e p e ? ? ? ? ? ? 11 W T T T P S E o e o ? ? ? ? 1 1 1 1 ?說明： ?如果問題規(guī)模W 保持不變，處理器數(shù)p增加，開 銷To增大，效率E下降。 ?為了維持一定的效率（介于 0與1之間），當(dāng)處理 數(shù)p增大時，需要相應(yīng)地增大問題規(guī)模 W的值。 W隨P按什么比例 增加 40 等效率度量標(biāo)準(zhǔn) ?曲線1表示算法具有很好的擴放性； ?曲線

18、2表示算法是可擴放的； ?曲線 3表示算法是不可擴放的。 處理器數(shù) P 工 作 負(fù) 載 W 曲線 3 曲線 2 曲線 1 41 等效率度量標(biāo)準(zhǔn) ?優(yōu)點：通過少量的參數(shù)可計算出等效率函數(shù) ?缺點：如果To無法計算出（在共享存儲并行機中） 42 2.2.2 等速度度量標(biāo)準(zhǔn) ?等效率度量標(biāo)準(zhǔn)的缺點等效率度量標(biāo)準(zhǔn)的缺點 ：T0不能方便地計算出來 ?1994 年兩位學(xué)者提出試驗測試為主要手段的兩種 標(biāo)準(zhǔn)：等速度、平均延遲等速度、平均延遲 43 為什么用等速度度量標(biāo)準(zhǔn)為什么用等速度度量標(biāo)準(zhǔn) ? 速度是一個重要的參數(shù)，一般可以明確指出，單位 Mflops，因此用速度來度量可擴放性，應(yīng)更加方便。 ? 在并行系統(tǒng)中，增加P可以提高速度，如果速度能隨著 P的增加而增加，即意味著平均速度不變 ? p個處理器的并行系統(tǒng)的平均速度定義為并行速度V除 以處理器個數(shù) p： 44 等速度度量標(biāo)準(zhǔn)等速度度量標(biāo)準(zhǔn) ?p 表示處理器個數(shù) ?W表示要求解問題的工作量或稱問題規(guī)模（在 此可指浮點操作個數(shù)） ?T為并行執(zhí)行時間 ?并行計算的速度V: V=W/T ?p個處理器的并行系統(tǒng)的 平均速度 定義為: pT W p V V? V 45 等速度度量標(biāo)準(zhǔn)等速度度量標(biāo)準(zhǔn) ? W是使用p個處理器時算法的工作量，令W表示當(dāng)處理 數(shù)從p增大到p時，為了保持整個系統(tǒng)的平均速度不變 所需執(zhí)行的工作量，則可得