并行分布式計(jì)算 并行計(jì)算性能評(píng)測(cè)

基本性能指標(biāo)

參數(shù)

• 工作負(fù)載 W：是指某個(gè)算法的計(jì)算量；
• 加速：就是加速比；
• 峰值速度：是速度的理論上限；

CPU 基本性能指標(biāo)

① 工作負(fù)載：

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

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

• 計(jì)算時(shí)間 $T_{comput}$ ；并行開(kāi)銷時(shí)間 $T_{paro}$ ；相互通信時(shí)間 $T_{comm}$ ：

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

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

存儲(chǔ)器性能

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

并行與存儲(chǔ)開(kāi)銷

并行和通信的開(kāi)銷相對(duì)于計(jì)算來(lái)說(shuō)很大。

開(kāi)銷的測(cè)量：

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

點(diǎn)到點(diǎn)通信開(kāi)銷表達(dá)式：
$$t(m)=t_0+m/r_{\infty }$$

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

• $t_0$ ：通信啟動(dòng)時(shí)間；

• $r_{\infty }$ ：漸進(jìn)帶寬，傳送無(wú)限長(zhǎng)消息時(shí)的通信頻率；查利芳等網(wǎng)絡(luò)結(jié)構(gòu)就是為了增大漸進(jìn)帶寬；

• 半峰值長(zhǎng)度 $m_{\frac{1}{2}}$ ：達(dá)到一半漸進(jìn)帶寬所需要的消息長(zhǎng)度；

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

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

典型整體通信：

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

機(jī)器的成本與價(jià)格：

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

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

加速比性能定律

Amdahl 定律

前提：

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

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

參數(shù)：

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

• $W$：問(wèn)題規(guī)模（計(jì)算負(fù)載、問(wèn)題的總計(jì)算量）
  $$W=W_s+W_p$$

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

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

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

• $S$ ：加速比；

• $E$ ：效率；

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

特點(diǎn)：

• 適用于實(shí)時(shí)應(yīng)用問(wèn)題。當(dāng)問(wèn)題的計(jì)算負(fù)載或者規(guī)模固定時(shí)，必須通過(guò)增加處理器數(shù)目來(lái)降低計(jì)算時(shí)間；

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

• 擴(kuò)展：若并行實(shí)現(xiàn)時(shí)還有額外開(kāi)銷，則：

$$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 定律

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

（增大精度的同時(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)$$
考慮并行開(kāi)銷 $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}$$
特點(diǎn)：隨著處理器數(shù)目的增加，串行執(zhí)行部分 $f$ 不再是并行算法的瓶頸。

Sun 和 Ni 定律

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

推導(dǎo)：設(shè)單機(jī)存儲(chǔ)容量為 $M$ ，其工作負(fù)載 $W=fW+(1?f)W$ ；

當(dāng)并行系統(tǒng)有 $p$ 個(gè)節(jié)點(diǎn)時(shí)，存儲(chǔ)容量變?yōu)?$pM$ ，用 $G(p)$ 表示系統(tǒng)的存儲(chǔ)容量增大 $p$ 倍時(shí)工作負(fù)載的增加量，即存儲(chǔ)容量擴(kuò)大后的工作負(fù)載為 $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}$$
考慮并行計(jì)算的開(kāi)銷 $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}$$

• 當(dāng) $G(p)=1$ 時(shí)，就是 Amdahl 定律，意味著節(jié)點(diǎn)的擴(kuò)展不會(huì)帶來(lái)額外開(kāi)銷；
• 當(dāng) $G(p)=p$ 時(shí)，就是 Gustafson 定律；
• 當(dāng) $G(p)>p$ 時(shí)，加速比比前面兩個(gè)定律得到的加速比更大；

加速比討論

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

• 線性加速比：很少通信開(kāi)銷的矩陣相加、內(nèi)積運(yùn)算等；

• $p/\log p$ 的加速比：分治類的應(yīng)用問(wèn)題；

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

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

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

相對(duì)加速：同一算法在單機(jī)和并行機(jī)的運(yùn)行時(shí)間。

可括放性評(píng)測(cè)標(biāo)準(zhǔn)

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

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

等效率度量標(biāo)準(zhǔn)

參數(shù)：令 $t_e^i$ 和 $t_o^i$ 分別是并行系統(tǒng)上第 $i$ 個(gè)處理器的有用計(jì)算時(shí)間和額外開(kāi)銷時(shí)間（包括通信、同步和空閑的等待時(shí)間等）
$$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$ 個(gè)處理器系統(tǒng)上并行算法的運(yùn)行時(shí)間，對(duì)于任意 $i$ 顯然有：
$$T_p=t_e^i+t_o^{i}p{T}_p=T_e+T_o$$
問(wèn)題的規(guī)模 $W$ 定義為最佳串行算法所完成的計(jì)算量，則 $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$ 增大時(shí)，開(kāi)銷 $T_o$ 增大，問(wèn)題規(guī)模 $W$ 也需要相應(yīng)增大。由此定義函數(shù) $fE(p)$ 為問(wèn)題規(guī)模 $W$ 隨處理器數(shù) $p$ 變化的函數(shù)，為等效率函數(shù)。

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

缺點(diǎn)：如果 $T_o$ 無(wú)法計(jì)算出的話就不能用這個(gè)方法（比如在共享存儲(chǔ)并行機(jī)中）

如圖，3 到 1 可括放性越來(lái)越好，2 以上的表示不可擴(kuò)放：

等速度度量標(biāo)準(zhǔn)

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

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

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

優(yōu)點(diǎn)：直觀使用易測(cè)量的機(jī)器性能速度指標(biāo)來(lái)度量；

缺點(diǎn)：某些非浮點(diǎn)運(yùn)算可能造成性能的變化沒(méi)有考慮；

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

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

平均延遲度量標(biāo)準(zhǔn)

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

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

基準(zhǔn)評(píng)測(cè)程序（Benchmark）

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

綜合型：Dhrystone、Whetstone

• 缺點(diǎn)：對(duì)編譯器比較敏感

核心型：Livermore Fortran Kernels、NASA 之 NAS

數(shù)學(xué)型：Linpack、FFT

• 常見(jiàn)的線性代數(shù)運(yùn)算

應(yīng)用型：SPEC、Perfect、Splash

并行型：NAS 之 NPB、PARKBENCH