并行分布式計算 并行計算性能評測

基本性能指標

參數(shù)

• 工作負載 W：是指某個算法的計算量；
• 加速：就是加速比；
• 峰值速度：是速度的理論上限；

CPU 基本性能指標

① 工作負載：

• 執(zhí)行時間：不僅包括 CPU 時間，還包括訪問存儲器、磁盤時間、 I/Ｏ 時間和 OS 開銷等；執(zhí)行時間是不穩(wěn)定的，波動較大；
• 浮點運算數(shù)（Flops）：其他類型的運算可以通過經(jīng)驗折算成浮點運算速度；只能衡量計算任務，不能用于衡量數(shù)據(jù)傳輸、IO密集型的操作（雖然并行計算前期只是用于計算密集型的任務）
• 指令數(shù)目（MIPS）通常以 百萬條/秒 作為單位（單條指令的執(zhí)行時間差別很大）

② 無重疊的假定下并行執(zhí)行時間 $T_n$ ：

• 計算時間 $T_{comput}$ ；并行開銷時間 $T_{paro}$ ；相互通信時間 $T_{comm}$ ：

$$T_n=T_{comput}+T_{paro}+T_{comm}$$

• $T_{comput}$ ：與串行的時間是一致的（無重疊的假定）；
• $T_{paro}$ ：與進程管理、組操作、進程查詢等相關；
• $T_{comm}$ ：同步（路障、鎖、臨界區(qū)、事件）、通信、聚合操作（規(guī)約、前綴運算），一般來說 $T_{comm}$ 比 $T_{paro}$ 要大得多；

存儲器性能

估計存儲器的帶寬：例如 RISC 的加法可以在單拍內完成（取出兩個數(shù)相加再送回寄存器）；假定字長為 8B，時鐘頻率 100MHZ，則帶寬：
$$B=3\times 8\times 100\times 10^{6}B/s=2.4GB/s$$

并行與存儲開銷

并行和通信的開銷相對于計算來說很大。

開銷的測量：

• 乒乓方法（Ping-Pong Scheme）：節(jié)點 - 發(fā)送 m 個字節(jié)給節(jié)點 1，節(jié)點 1 收到以后立即將消息發(fā)回節(jié)點 0，總時間除以 2；
• 熱土豆法（Hot-Potato）/救火隊法（Fire-Brigade）：再乒乓方法的基礎上，節(jié)點 1 收到以后立即發(fā)送給節(jié)點 2，直到發(fā)送給節(jié)點 n-1 后，最后發(fā)送回 0，總的時間除以 n；

點到點通信開銷表達式：
$$t(m)=t_0+m/r_{\infty }$$

• $m$ ：消息長度（字節(jié)數(shù)）；

• $t_0$ ：通信啟動時間；

• $r_{\infty }$ ：漸進帶寬，傳送無限長消息時的通信頻率；查利芳等網(wǎng)絡結構就是為了增大漸進帶寬；

• 半峰值長度 $m_{\frac{1}{2}}$ ：達到一半漸進帶寬所需要的消息長度；

• 特定性能 ${\pi }_0$ ：表示短消息帶寬；

• $t_0=m_{\frac{1}{2}}/r_{\infty }=1/{\pi }_0$ ；$t_0$ 就好像是發(fā)送一個很小的包時所需要花費的時間；

典型整體通信：

• 廣播（Broadcasting）：處理器 0 發(fā)送 m 個字節(jié)給所有的 n 個處理器；
• 收集（Gather）：處理器 0 接收所有 n 個處理器發(fā)送來的消息，最終接收 mn 個字節(jié)；盡量不要出現(xiàn)收集的情況，否則帶寬會被 n 個處理器瓜分；
• 散射（Scatter）：處理器 0 發(fā)送了 m 個字節(jié)的不同消息給所有 n 個處理器；
• 全交換（Total Exchange）：每個處理器均彼此相互發(fā)送 m 個字節(jié)的不同消息給對方，總通信量為 $m{n}^2$ 個字節(jié)；很多算法需要全交換，所以通行效率或者帶寬會隨著處理器數(shù)量上升而快速下降；
• 循環(huán)位移（Circular-shift）：處理器 i 發(fā)送 m 個字節(jié)給處理器 (i + 1) % n，總通信量為 mn 個字節(jié)；

機器的成本與價格：

• 機器的性價比（Performance/Cost Ratio）：單位代價（通常為百萬美元）所獲取的性能（通常用 MIPS 或 MFLOPS 表示）
• 利用率：可達到的速度與峰值速度之比；

要想提高利用率，就要提高通訊量級；要想保持通訊硬件不變而提高通訊量級，就要優(yōu)化算法。

加速比性能定律

Amdahl 定律

前提：

• 固定不變的計算機負載；
• 固定的計算負載分布在多個處理器上；
• 增加處理器加快執(zhí)行速度，從而達到了加快處理速度的目的；

（總的計算量不變，并且被固定地、平均地分配給 p 個處理器）

參數(shù)：

• $P$：處理器數(shù)；

• $W$：問題規(guī)模（計算負載、問題的總計算量）
  $$W=W_s+W_p$$

  • $W_s$ ：應用程序中的串行分量，$f$ 是串行分量比例（$f=W_s/W$）；
  • $W_p$ ：應用程序中可并行化部分；

• $T_s=T_1$ ：串行執(zhí)行時間；

• $T_p$ ：并行執(zhí)行時間；

• $S$ ：加速比；

• $E$ ：效率；

$$S=\frac{W_s+W_p}{W_s+W_p/p}\stackrel{p\to \infty }{\to }\frac{1}{f}$$

特點：

• 適用于實時應用問題。當問題的計算負載或者規(guī)模固定時，必須通過增加處理器數(shù)目來降低計算時間；

• 加速比受到算法中串行工作量的限制；

• 擴展：若并行實現(xiàn)時還有額外開銷，則：

$$S=\frac{W_s+W_p}{W_s+W_p/p+W_o}\stackrel{p\to \infty }{\to }\frac{1}{f+W_o/W}$$

Gustafson 定律

前提：對于很多大型計算，精度要求很高，而計算時間時固定不變的。此時為了提高精度，必須加大計算量，相應地必須增多處理器數(shù)才能維持時間不變。

（增大精度的同時 $W_s$ 幾乎是不變的）
$$S^{\prime }=\frac{W_s+p{W}_p}{W_s+p{W}_p/p}=\frac{W_s+p{W}_p}{W_s+W_p}=f+p(1?f)$$
考慮并行開銷 $W_o$ ：
$$S^{\prime }=\frac{W_s+p{W}_p}{W_s+p{W}_p/p+W_o}=\frac{f+p(1?f)}{1+W_o/W}$$
特點：隨著處理器數(shù)目的增加，串行執(zhí)行部分 $f$ 不再是并行算法的瓶頸。

Sun 和 Ni 定律

前提：充分利用存儲空間等計算資源，盡量增大問題規(guī)模以產(chǎn)生更好/更精確的解，是 Amdahl 定律和 Gustafson 定律的推廣。

推導：設單機存儲容量為 $M$ ，其工作負載 $W=fW+(1?f)W$ ；

當并行系統(tǒng)有 $p$ 個節(jié)點時，存儲容量變?yōu)?$pM$ ，用 $G(p)$ 表示系統(tǒng)的存儲容量增大 $p$ 倍時工作負載的增加量，即存儲容量擴大后的工作負載為 $W=fW+(1?f)G(p)W$ ，加速比為：
$$S^{\prime \prime }=\frac{fW+(1?f)G(p)W}{fW+(1?f)G(p)W/p}=\frac{f+(1?f)G(p)}{f+(1?f)G(p)/p}$$
考慮并行計算的開銷 $W_o$ ：
$$S^{\prime \prime }=\frac{fW+(1?f)G(p)W}{fW+(1?f)G(p)W/p+W_o}=\frac{f+(1?f)G(p)}{f+(1?f)G(p)/p+W_o/W}$$

• 當 $G(p)=1$ 時，就是 Amdahl 定律，意味著節(jié)點的擴展不會帶來額外開銷；
• 當 $G(p)=p$ 時，就是 Gustafson 定律；
• 當 $G(p)>p$ 時，加速比比前面兩個定律得到的加速比更大；

加速比討論

加速比經(jīng)驗公式：
$$\frac{p}{\log p}\le S\le p$$

• 線性加速比：很少通信開銷的矩陣相加、內積運算等；

• $p/\log p$ 的加速比：分治類的應用問題；

• 通信密集類的應用問題：$S=\frac{1}{C(p)}$ ，這里 $C(p)$ 時 $p$ 個處理器的某一通信函數(shù)；

超線性加速：特殊情況下出現(xiàn)，例如在不同分支上進行搜索，某個處理器搜索發(fā)現(xiàn)結果后結束整個任務；

絕對加速：最佳串行算法與并行算法所用時間之比；（有些算法是沒法直接并行化的，因此絕對加速更合理）

相對加速：同一算法在單機和并行機的運行時間。

可括放性評測標準

可括放性（Scalability）：性能隨處理器數(shù)的增加而按比例提高的能力。

• 影響因素：處理器數(shù)和問題規(guī)模；串行分量；并行處理的額外開銷；處理器數(shù)是否超過了算法中的并發(fā)程度；
• 增加問題規(guī)模的好處：提供較高的并發(fā)機會；overhead 增加可能慢于有效計算的增加；串行分量比例隨著問題規(guī)模增大而縮小；
• 增加處理器數(shù)量會增大 overhead 并降低處理器利用率，對于一個特定的并行系統(tǒng)（算法或程序），它們能否有效利用不斷增加的處理器的能力應是受限的，而度量這種能力就是可括放性這一指標。

等效率度量標準

參數(shù)：令 $t_e^i$ 和 $t_o^i$ 分別是并行系統(tǒng)上第 $i$ 個處理器的有用計算時間和額外開銷時間（包括通信、同步和空閑的等待時間等）
$$T_s=T_e=\sum _{i=0}^{p?1}{t}_e^i{T}_0=\sum _{i=0}^{p?1}{t}_o^i$$
$T_p$ 是 $p$ 個處理器系統(tǒng)上并行算法的運行時間，對于任意 $i$ 顯然有：
$$T_p=t_e^i+t_o^{i}p{T}_p=T_e+T_o$$
問題的規(guī)模 $W$ 定義為最佳串行算法所完成的計算量，則 $W=T_e$ ，因此有：
$$S=\frac{T_e}{T_p}=\frac{T_e}{(T_e+T_o)/p}=\frac{p}{1+T_o/W}E=\frac{S}{p}=\frac{1}{1+T_o/W}$$
為了維持一定的效率，處理器數(shù) $p$ 增大時，開銷 $T_o$ 增大，問題規(guī)模 $W$ 也需要相應增大。由此定義函數(shù) $fE(p)$ 為問題規(guī)模 $W$ 隨處理器數(shù) $p$ 變化的函數(shù)，為等效率函數(shù)。

優(yōu)點：簡單可定量計算的、少量參數(shù)計算等效率函數(shù)

缺點：如果 $T_o$ 無法計算出的話就不能用這個方法（比如在共享存儲并行機中）

如圖，3 到 1 可括放性越來越好，2 以上的表示不可擴放：

等速度度量標準

前提：在共享存儲并行機中 $T_o$ 難以計算；換一種方法，如果速度能以處理器數(shù)的增加而線性增加，則說明系統(tǒng)具有很好的擴放性。

參數(shù)：$p$ 和 $W$ 前面一樣，$T$ 為并行執(zhí)行時間，并行計算的速度 $v=W/T$ ；

$p$ 個處理器的并行系統(tǒng)的平均速度定義為并行速度除以處理器個數(shù)：
$$\bar{v}=\frac{v}{p}=\frac{W}{pT}$$
令 $W^{\prime }$ 表示當處理器數(shù)從 $p$ 增大到 $p^{\prime }$ 時，為了保持整個系統(tǒng)的平均速度不變所需執(zhí)行的工作量，則可得到處理器數(shù)從 $p$ 到 $p^{\prime }$ 時平均速度可擴放度量標準公式：
$$\Psi (p,p^{\prime })=\frac{p^{\prime }W}{p{W}^{\prime }}$$
$\Psi (p,p^{\prime })$ 介于 0 到 1 之間，越靠近 1 越好；

優(yōu)點：直觀使用易測量的機器性能速度指標來度量；

缺點：某些非浮點運算可能造成性能的變化沒有考慮；

當 $p=1$ 時，有：
$$\Psi (p^{\prime })=\Psi (1,p^{\prime })=\frac{p^{\prime }W}{W^{\prime }}=\frac{T_1}{T_{p^{\prime }}}=\frac{\text{解決工作量為W的問題所需串行時間}}{\text{解決工作量為W′的問題所需并行時間}}$$
區(qū)別：

• 加速比的定義是保持問題規(guī)模不變，標志對于串行系統(tǒng)的性能增加；
• 擴放性定義時保持平均速度不變，標志對于小系統(tǒng)到大規(guī)模系統(tǒng)所引起的性能變化；

平均延遲度量標準

一個并行系統(tǒng)執(zhí)行的時間圖譜

• $T_{para}$ 是最大的，作為總的并行時間

基準評測程序（Benchmark）

不同程序會涉及到硬件、體系結構、編譯優(yōu)化、編程環(huán)境、測試條件、解題算法等眾多因素；根據(jù)側重點不同，分為：

綜合型：Dhrystone、Whetstone

• 缺點：對編譯器比較敏感

核心型：Livermore Fortran Kernels、NASA 之 NAS

數(shù)學型：Linpack、FFT

• 常見的線性代數(shù)運算

應用型：SPEC、Perfect、Splash

并行型：NAS 之 NPB、PARKBENCH