高級(jí)計(jì)算機(jī)體系結(jié)構(gòu)第3幸性能評(píng)測(cè)

m

第3幸性能評(píng)測(cè)

五神敖師,‘未明

電話：67792165

Email:zhuming@

0?也

本章學(xué)習(xí)要求:

合了解：什么是并行機(jī)的基本性能。

卷了解：為什么要研究并行機(jī)的性能評(píng)測(cè)。

⑥掌握：如何評(píng)測(cè)并行機(jī)的性能：

B機(jī)器級(jí)性能評(píng)測(cè)

■算法級(jí)性能評(píng)測(cè)

I程序級(jí)性能評(píng)測(cè)

3

3.1什么是并行機(jī)的基本性能

?所謂機(jī)器的性能(Performance)通常是指機(jī)器的速度，

它是程序執(zhí)行時(shí)間的倒數(shù)。而程序執(zhí)行時(shí)間是指用戶(hù)

向計(jì)算機(jī)送入一個(gè)任務(wù)后，直到獲得他需要的結(jié)果這一

段等待時(shí)間，包括訪問(wèn)磁盤(pán)和訪問(wèn)存儲(chǔ)器的時(shí)間，CPU

運(yùn)算時(shí)間，I/0動(dòng)作時(shí)間以及操作系統(tǒng)的開(kāi)銷(xiāo)時(shí)間等。

但在多任務(wù)系統(tǒng)中，CPU在等待I/0操作的同時(shí)可以轉(zhuǎn)去

處理另一個(gè)任務(wù),這樣分析起來(lái)就比較麻煩。所以在討

論性能時(shí)，有時(shí)也使用CPU時(shí)間，它表示CPU的工作時(shí)間,

不包括I/O等待時(shí)間和運(yùn)行其它任務(wù)的時(shí)間。很顯然，

用戶(hù)所看到的執(zhí)行時(shí)間是程序結(jié)束時(shí)所花費(fèi)的全部時(shí)

間，而不單是CPU時(shí)間。

4

1.單CPU性能

假定機(jī)器的時(shí)鐘周期為T(mén)c,程序中指令總條數(shù)為IN，

執(zhí)行每條指令所需的平均時(shí)鐘周期數(shù)為CPI,則一個(gè)程

序在CPU上運(yùn)行的時(shí)間Tcpu為：

=【(3.1)

TCPUNxCPIxTc

其中,n

執(zhí)行整個(gè)程序所需的睡中周期數(shù)二'（b'x，）

(3.2)

程序中指令總數(shù)■TN

nA/、

cpi-ycPL1x，T(3.3)

i=l\】NJ

n為程序中所有指令種類(lèi)數(shù)

"In表示第i種指令在程序中所占的比例

5

0■也

?TFT夕A千八3

2.MIPS和MFLOPS

MIPS(Mi11ionInstructionsPerSecond)即每

秒百萬(wàn)條指令，它很適合于評(píng)測(cè)標(biāo)量機(jī)。對(duì)于一個(gè)給定

的程序，MIPS可表示為：

66

MIPS=IN/(TEX10)=RC/(CPIx10)

=IN/(INxCPIxTcx1Q6)(3.4)

其中，TE表示程序執(zhí)行時(shí)間，Rc表示時(shí)鐘速率，它是Tc的倒數(shù)。

MFLOPS(Mi1lionFloatingPointOperations

PerSecond)常用來(lái)評(píng)價(jià)向量計(jì)算機(jī)的性能，表示每

秒百萬(wàn)次浮點(diǎn)運(yùn)算：

6

MFLOPS=IFN/(TEX10)(3.5)

其中，IFN表示程序中的浮點(diǎn)運(yùn)算次數(shù)。

6

）熏學(xué)大號(hào)

3.并行機(jī)的基本性能指標(biāo)

并行計(jì)算機(jī)的基本性能參數(shù)可概括于表3.1中。

7

0■也

林口

名稱(chēng)付萬(wàn)含意單位

機(jī)器規(guī)模n處理器的數(shù)目無(wú)量綱

時(shí)鐘速率f時(shí)鐘周期長(zhǎng)度的倒數(shù)MHZ

工作負(fù)載W計(jì)算操作的數(shù)目Mflop

順序執(zhí)行時(shí)間J程序在單處理機(jī)上的運(yùn)行時(shí)間s（秒）

并行執(zhí)行時(shí)間程序在并行機(jī)上的運(yùn)行時(shí)間S（秒）

Tn

速度每秒百萬(wàn)次浮點(diǎn)運(yùn)算Mflop/s

Rn=W/Tn

加速ST￡衡量并行機(jī)有多快無(wú)量綱

效率En=S"n衡量處理器的利用率無(wú)量綱

峰值速度Rpeak—□Rpeak所有處理器峰值速度之積，R”akMflop/s

為一個(gè)處理器的峰值速度

利用率可達(dá)速度與峰值速度之比無(wú)量綱

U=R"Roeak

通信延遲傳送0-字節(jié)或單字的時(shí)間Ms

漸近帶寬_傳送長(zhǎng)消息通信速率___________MB/j

8

當(dāng)今,計(jì)算機(jī)的性能評(píng)價(jià)與測(cè)試是一個(gè)正在研究中

的課題,它與計(jì)算機(jī)體系結(jié)構(gòu),計(jì)算機(jī)軟件,計(jì)算機(jī)算法

共同構(gòu)成了新興的計(jì)算科學(xué)(ComputationalSciences)

的四大支柱。并行計(jì)算機(jī)系統(tǒng)遠(yuǎn)比單處理機(jī)系統(tǒng)復(fù)雜

得多，所以為了更好地用好并行機(jī),充分發(fā)揮其長(zhǎng)處，以

適應(yīng)不同應(yīng)用問(wèn)題的需求,評(píng)價(jià)與測(cè)試并行計(jì)算機(jī)的多

種性能是非常必要的。

9

?0T■FT也夕A千八3

1.發(fā)揮并行機(jī)長(zhǎng)處,提高并行機(jī)的使用效率

通過(guò)對(duì)不同并行計(jì)算機(jī)的性能進(jìn)行測(cè)試,可以評(píng)價(jià)

其優(yōu)、缺點(diǎn)。根據(jù)它們的特點(diǎn)，對(duì)口相應(yīng)的應(yīng)用領(lǐng)域，

充分發(fā)揮其長(zhǎng)處，以提高并行計(jì)算機(jī)的使用效率。例如,

通過(guò)測(cè)試CPU性能可以為計(jì)算密集(Compute-

Intensive)型應(yīng)用問(wèn)題建議較合適的并行機(jī)；通過(guò)測(cè)

試網(wǎng)絡(luò)性能，可以為網(wǎng)絡(luò)密集(Network-Intensive)型

應(yīng)用問(wèn)題建議較適宜的并行機(jī)；通過(guò)對(duì)存儲(chǔ)器和I/O

通道性能的評(píng)試,可以為數(shù)據(jù)密集(Data-Intensive)型

應(yīng)用問(wèn)題建議較滿意的并行機(jī)等。

10

?0T■FT也夕A千八3

2.減少用戶(hù)購(gòu)機(jī)盲目性，降低投資風(fēng)險(xiǎn)

對(duì)于某一特定用戶(hù)而言，并非購(gòu)買(mǎi)越貴的機(jī)器越好。

應(yīng)該根據(jù)自己的計(jì)算問(wèn)題特點(diǎn)，通過(guò)使用基準(zhǔn)測(cè)試程序

（見(jiàn)本章2.4節(jié)）所得到的一些結(jié)果數(shù)據(jù)，來(lái)幫助你決策

購(gòu)買(mǎi)何種并行計(jì)算機(jī)。并行計(jì)算機(jī)一般都很貴,一旦所

購(gòu)買(mǎi)的計(jì)算機(jī)在具體的應(yīng)用中不能發(fā)揮應(yīng)有的作用，那

將是莫大的浪費(fèi)。一般而言，用戶(hù)大都不是并行計(jì)算機(jī)

方面的專(zhuān)家，為減少購(gòu)買(mǎi)并行機(jī)的投資風(fēng)險(xiǎn)，通過(guò)各種

性能評(píng)測(cè)手段來(lái)最大限度地減少引進(jìn)和購(gòu)買(mǎi)并行計(jì)算

機(jī)的盲目性是非常重要的。

11

0■也

3.改進(jìn)系統(tǒng)結(jié)構(gòu)設(shè)計(jì)，提高機(jī)器的性能

并行計(jì)算機(jī)是個(gè)龐大復(fù)雜的系統(tǒng)，即使具有豐富

設(shè)計(jì)經(jīng)驗(yàn)的人員，也很難保證所設(shè)計(jì)出的計(jì)算機(jī)系統(tǒng)

十全十美。任何成功的設(shè)計(jì)都不可能一次完成，總是

通過(guò)測(cè)試試用，不斷修改、補(bǔ)充以臻完善。其中，按照

性能測(cè)試所產(chǎn)生的測(cè)試結(jié)果比較全面，能夠暴露設(shè)計(jì)中

的一些問(wèn)題，這些問(wèn)題對(duì)計(jì)算機(jī)設(shè)計(jì)者具有比較大的指

導(dǎo)意義,針對(duì)這些問(wèn)題改進(jìn)現(xiàn)有的設(shè)計(jì),可進(jìn)一步提高

計(jì)算機(jī)的性能，以適應(yīng)各方面的應(yīng)用需求。

12

?0T■FT也夕A千八3

4.促進(jìn)軟/硬件結(jié)合，合理功能劃分

根據(jù)對(duì)計(jì)算機(jī)性能的實(shí)際測(cè)試和統(tǒng)計(jì)分析,可以明

確計(jì)算機(jī)所應(yīng)完成的軟件與硬件職能，合理的功能劃

分以及適當(dāng)?shù)能?硬件折衷。對(duì)于那些使用頻繁、功能

較簡(jiǎn)單的操作，在硬件工藝許可的情況下，當(dāng)以硬件實(shí)

現(xiàn)之；而對(duì)于那些不常使用、功能又較復(fù)雜的操作，在

軟件復(fù)雜度允許的情況下，當(dāng)以軟件代替之。這些常識(shí)

范圍內(nèi)的知識(shí)，必須建立在對(duì)計(jì)算機(jī)的性能進(jìn)行全面地

測(cè)試和客觀地分析的基礎(chǔ)上。特別是在技術(shù)工藝水平

不斷提高，器件成本不斷下降的今天,計(jì)算機(jī)軟件功能

硬化的趨勢(shì)似乎越來(lái)越明顯。

13

?0T■FT也夕A千八3

5.優(yōu)化“結(jié)構(gòu)-算法-應(yīng)用”的最佳組合

通過(guò)對(duì)計(jì)算機(jī)性能的評(píng)測(cè)，可以發(fā)現(xiàn)什么類(lèi)型的體

系結(jié)構(gòu)比較適合于什么類(lèi)型的問(wèn)題求解算法；哪一類(lèi)

體系結(jié)構(gòu)對(duì)哪一類(lèi)應(yīng)用問(wèn)題比較有效；某類(lèi)算法比較

適合于求解某類(lèi)應(yīng)用問(wèn)題。例如，網(wǎng)孔連接的并行機(jī)

結(jié)構(gòu)比較適合于矩陣運(yùn)算之類(lèi)的算法；樹(shù)連接的并行

結(jié)構(gòu)比較適合于與數(shù)據(jù)庫(kù)有關(guān)的一類(lèi)應(yīng)用問(wèn)題；數(shù)字

濾波這一類(lèi)的算法是數(shù)字信號(hào)處理應(yīng)用中經(jīng)常使用的

算法。當(dāng)通過(guò)性能評(píng)測(cè)得出上述結(jié)論后，我們就可針

對(duì)某類(lèi)應(yīng)用問(wèn)題，設(shè)計(jì)出可以高效運(yùn)行某種體系結(jié)構(gòu)

上的算法了。

14

0■也

?TFT夕A千八3

6.提供客觀、公正的評(píng)價(jià)并行機(jī)的標(biāo)準(zhǔn)

不同的用戶(hù)（包括機(jī)器的系統(tǒng)操作員），會(huì)從不

同的角度來(lái)評(píng)價(jià)并行機(jī)的性能優(yōu)劣。研究并行機(jī)的性

能評(píng)測(cè)的根本目的之一，就是要試圖提供一個(gè)統(tǒng)一的、

客觀的、公正的和可相互比較的評(píng)價(jià)并行計(jì)算機(jī)的標(biāo)

準(zhǔn)。為此就要從并行機(jī)的硬件體系、軟件功能、解題

能力、使用目的和測(cè)試手段等各個(gè)方面來(lái)評(píng)測(cè)并行計(jì)

算機(jī)的性能。

15

3.3如何評(píng)測(cè)并行機(jī)的性能

怎樣評(píng)測(cè)一臺(tái)計(jì)算機(jī)的性能，與測(cè)試者的出發(fā)點(diǎn)

有關(guān)。例如，計(jì)算機(jī)用戶(hù)說(shuō)機(jī)器很快，往往是因?yàn)槌?/p>

序運(yùn)行時(shí)間短；而計(jì)算機(jī)管理員說(shuō)機(jī)器很快，往往是

因?yàn)樵谝欢螘r(shí)間內(nèi)它能夠完成更多的任務(wù)。用戶(hù)所關(guān)

心的是從提交任務(wù)開(kāi)始到運(yùn)行結(jié)束之間的時(shí)間，即執(zhí)

行時(shí)間；而管理員所關(guān)心的是在單位時(shí)間能完成的工

作量，即吞吐率(Throughput)。

所以，如何客觀、公正地評(píng)價(jià)計(jì)算機(jī)的性能不是

一件容易的事，要涉及到計(jì)算機(jī)系統(tǒng)的諸多因素，它不

僅與機(jī)器硬件速度有關(guān)，而且還與機(jī)器體系結(jié)構(gòu)、計(jì)算

方法與算法、程序編譯優(yōu)化、編程工具與環(huán)境,甚至與

測(cè)試方法手段等有關(guān)。

16

0■也

■■

本節(jié)試圖根據(jù)機(jī)器性能評(píng)測(cè)的層次,分別從

機(jī)器級(jí)、算法級(jí)和程序級(jí)三個(gè)層次來(lái)研究它們。

請(qǐng)注意這種分層也只是為了討論的方便。

17

3.3.1機(jī)器級(jí)的性能評(píng)測(cè)

機(jī)器級(jí)的性能評(píng)測(cè)，包括:

AcPU和存儲(chǔ)器的某些基本性能指標(biāo)；

?并行和通信開(kāi)銷(xiāo)分析；

A并行機(jī)的可用性與好用性；

A機(jī)器成本、價(jià)格與性/價(jià)比等。

它們中的有些是由機(jī)器廠商在銷(xiāo)售時(shí)直接提供給

用戶(hù)的，是廣大用戶(hù)對(duì)并行計(jì)算機(jī)的第一印象,是引進(jìn)

和購(gòu)買(mǎi)并行計(jì)算機(jī)時(shí)最主要的選擇依據(jù),特別是機(jī)器的

基本性能指標(biāo)和機(jī)器的價(jià)格是諸多并行機(jī)之間最可比

的數(shù)據(jù),也是非計(jì)算機(jī)專(zhuān)業(yè)用戶(hù)選購(gòu)并行機(jī)時(shí)決策的主

要依據(jù)。

18

CPU和存儲(chǔ)器的某些基本性能

指標(biāo)

1.CPU性能

⑴工作負(fù)載(W)：所謂工作負(fù)載(荷)，就是計(jì)算操作的

數(shù)目，通?？捎脠?zhí)行時(shí)間，所執(zhí)行的指令數(shù)目和所完成

的浮點(diǎn)運(yùn)算數(shù)三個(gè)物理量來(lái)度量它。其中，

①執(zhí)行時(shí)間：它可定義為在特定的計(jì)算機(jī)系統(tǒng)上的一

個(gè)給定的應(yīng)用所占用的總時(shí)間，系指應(yīng)用程序從開(kāi)始到

結(jié)束所掠過(guò)的時(shí)間(ElapsedTime),它不只是CPU時(shí)間,

還包括了訪問(wèn)存儲(chǔ)器、磁盤(pán)、I/O通道的時(shí)間和OS開(kāi)

銷(xiāo)等。影響執(zhí)行時(shí)間主要因素有求解應(yīng)用問(wèn)題所使用

的算法；輸入數(shù)據(jù)集及其數(shù)據(jù)結(jié)構(gòu)；求解問(wèn)題的硬件

平臺(tái)和操作系統(tǒng)以及所使用的語(yǔ)言、編譯/編輯器和二

進(jìn)制代碼的庫(kù)函數(shù)等。

19

0■也

②浮點(diǎn)運(yùn)算數(shù)：對(duì)于大型科學(xué)與工程計(jì)算問(wèn)題,使用所

執(zhí)行的浮點(diǎn)運(yùn)算數(shù)目來(lái)表示工作負(fù)載是很自然的。對(duì)

于程序中的其它類(lèi)型的運(yùn)算，可按如下經(jīng)驗(yàn)規(guī)則折算

成浮點(diǎn)運(yùn)算（FLOP）數(shù)：在運(yùn)算表達(dá)式中的賦值操作、

變址計(jì)算等均不單獨(dú)考慮（即它們被折算成0FLOP）;

單獨(dú)賦值操作、加法、減法、乘法、比較、數(shù)據(jù)類(lèi)型

轉(zhuǎn)換等運(yùn)算均各折算成1FLOP;除法和開(kāi)平方運(yùn)算各

折算成4FLOP;正（余）弦、指數(shù)類(lèi)運(yùn)算各折算成8

FLOP;其它類(lèi)運(yùn)算，可按其復(fù)雜程度，參照上述經(jīng)驗(yàn)

數(shù)據(jù)進(jìn)行折算之。注意，在理論分析時(shí)，常常假定各

條指令和每個(gè)浮點(diǎn)運(yùn)算均取相同時(shí)間，這種均勻一致

的速度假定在實(shí)際的計(jì)算系統(tǒng)中總是難以成立的。

20

?0T■FT也夕A千八3

③指令數(shù)目：它與機(jī)器的指令系統(tǒng)有關(guān)。對(duì)于任何給

定的應(yīng)用，它所執(zhí)行的指令條數(shù)就可視為工作負(fù)載，

常以百萬(wàn)條指令為計(jì)算單位，與其相應(yīng)的速度單位就

是MIPS（每秒百萬(wàn)條指令）。不過(guò)用MIPS來(lái)表示工作

負(fù)載時(shí)要注意機(jī)器實(shí)際執(zhí)行的指令數(shù)不一定就是匯編

程序中的指令數(shù)；所需執(zhí)行的指令數(shù)目可能是依賴(lài)于

輸入數(shù)據(jù)值；即使對(duì)于固定的輸入使用相同的高級(jí)語(yǔ)

言，執(zhí)行在RISC機(jī)器上的指令數(shù)通常比在CISC機(jī)器上

指令數(shù)要多50%?150%;即使在相同的機(jī)器上，使用固

定的輸入，程序執(zhí)行的指令數(shù)也會(huì)因不同的編譯或優(yōu)

化方法而不同；最后，較多的指令數(shù)也不一定意味著

程序地執(zhí)行時(shí)間就長(zhǎng)。

21

?0T■FT也夕A千八3

（2）并行執(zhí)行時(shí)間：

在無(wú)重疊操作的假定下，并行程序的執(zhí)行時(shí)間Tn為：

T_T_|_T+T6）

1n-1comput1paro1comm0）

其中，、。呻玳為計(jì)算時(shí)間，Tparo為并行開(kāi)銷(xiāo)時(shí)

間，幾。1nm為相互通信時(shí)間。而Tpar。包括進(jìn)程管理（如進(jìn)

程生成、結(jié)束和切換等）時(shí)間，組操作（如進(jìn)程組的生成

與消亡等）時(shí)間和進(jìn)程查尋（如詢(xún)問(wèn)進(jìn)程的標(biāo)志、等級(jí)、

組標(biāo)志和組大小等）時(shí)間；口項(xiàng)包括同步（如路障、鎖、

臨界區(qū)、事件等）時(shí)間，通信（如點(diǎn)到點(diǎn)通信、整體

通信、讀/寫(xiě)共享變量等）時(shí)間和聚合操作（如歸約、

前綴運(yùn)算等）時(shí)間。

22

（0E■也/燈千入J

了解這些額外開(kāi)銷(xiāo)對(duì)開(kāi)發(fā)并行程序大有好處：例如,

要是并行開(kāi)銷(xiāo)Tpar。較小，則程序員可使用動(dòng)態(tài)并行程

序；否則使用靜態(tài)并行程序較好，因?yàn)檫M(jìn)程只在開(kāi)始

時(shí)生成而結(jié)束時(shí)消滅。又如，如果機(jī)器支持路障同步，

則可使用同步算法；如果路障操作太費(fèi)時(shí)，則可使用

異步算法。

下面讓我們使用異步PRAM模型（即APRAM）來(lái)估計(jì)

一下并行執(zhí)行時(shí)間。

23

簸群大號(hào)

卷在APRAM模型中，計(jì)算系由一系列用同步路障分開(kāi)的所

謂相(Phase)所組成。在每個(gè)相內(nèi)，各個(gè)處理器均異

步地執(zhí)行局部計(jì)算，每個(gè)相中最后一條指令是同步路

障指令。假定在第i相內(nèi)計(jì)算量(即工作負(fù)載)為W追

計(jì)算時(shí)間為T(mén)](i)。令DOP(DegreeofParalleiism)

表示能夠同時(shí)執(zhí)行的最大進(jìn)程數(shù)，稱(chēng)之為并行度。對(duì)

于n個(gè)處理器的并行系統(tǒng)，顯然14DOPi《n。而在

第i相中并行執(zhí)行時(shí)間為T(mén)0(i)=TNi)/n,所以在n個(gè)

處理器的系統(tǒng)中，其總的并行執(zhí)行時(shí)間為：

T_x1（，）______7+7

±±3.7

n-/.?/八八廠！\parocomm

24

11打號(hào)

令Ts代表在使用無(wú)限多的處理器（n-8）且不考慮

Tparo和Tc°mm時(shí)的應(yīng)用程序執(zhí)行時(shí)間，于是有：

T二丁T1⑴

00幺DOPj3.8

定義為了達(dá)到Tn=Too的最小n值為N啥，稱(chēng)其為最

大并行度，也就是能夠用來(lái)降低執(zhí)行時(shí)間的最大處理

器數(shù)，則有：

Nmax=max（。。尸J

IIIdX-J?XI/3.9

\<i<k

可能達(dá)到的最高性能之上界可定義為:

S———W340

8FTJ25

00

而n個(gè)處理器的執(zhí)行時(shí)間下界為：

TGmaxCTi/n,TQ(3.11)

Brent[1]已經(jīng)證明，不考慮丁。&1。和丁阿皿時(shí)，北滿足

下式：

工5占十兀(3.12)

nn

將(3.11)代入(3.12),則有:

(T、T

max△，兀工14二+圖(3.13)

\n)n

0■也

,TFTj、A￥入3

?2.存儲(chǔ)器性能

(1)存儲(chǔ)器的層次結(jié)構(gòu)：

在近代計(jì)算機(jī)中，為了加快處理器與存儲(chǔ)器之間的

數(shù)據(jù)移動(dòng)，存儲(chǔ)器通常按層次結(jié)構(gòu)進(jìn)行組織。如圖3.1

所示，對(duì)于每一層均可用三個(gè)參數(shù)表征之：①容量C:

表示各層的物理存儲(chǔ)器件能保存多少字節(jié)的數(shù)據(jù)；②

延遲L：表示讀取各層物理器件中一個(gè)字所需的時(shí)間；

③帶寬B：表示在1秒鐘內(nèi)各層的物理器件中能傳送多

少個(gè)字節(jié)。各層存儲(chǔ)器及其相應(yīng)的典型的C、L、B值示

于圖3.1中。

27

C<2KB4-256KB64KB-4MB16MB-16GB1-100GB

『0周期0-2周期2-10周期10-100周期100KTM周期

B=1-32GB/S1-16GB/S1-4GB/S0.4-2GB/S1-16MB/S

圖3.1各層存儲(chǔ)器的典型性能參數(shù)

28

0■也

?TFT夕A千八3

■BaBBBaaMMaMBasBsaBBBMBBMHaaaMBaaMBBHBaBBBaaMMaMBasaBaBHBMBBQflHaaaMBaaMBBHBaBBBaBMaaMBasaBaBHBMBBaaaaaaMBaaMBBHBas

(2)存儲(chǔ)器帶寬的估算：

假定字長(zhǎng)為64位，即8字節(jié)。對(duì)于RISC類(lèi)型機(jī)器中

的加法操作，它從寄存器中取2個(gè)64位的字相加后再回

送至寄存器。通常RISC加法指令可在單拍內(nèi)完成，如果

使用100MHZ的時(shí)鐘,那么存儲(chǔ)帶寬將是

3x8x100x106=2.4GB/S可見(jiàn)，較快的時(shí)鐘和處理器中

較高的并行操作,可獲得較寬的帶寬。

29

并行和通信開(kāi)銷(xiāo)分析

這一節(jié)主要討論由于并行而招致的時(shí)間開(kāi)銷(xiāo)Tparo

和多進(jìn)程相互作用所引起的通信開(kāi)銷(xiāo)Tcomni。這兩種時(shí)

間開(kāi)銷(xiāo)均比普通的計(jì)算時(shí)間要長(zhǎng)得多，而且隨系統(tǒng)不同

而變化很大。例如，一個(gè)P0WER2處理器每個(gè)時(shí)鐘周期

(15ns)能執(zhí)行4個(gè)浮點(diǎn)運(yùn)算，但生成一個(gè)Unix進(jìn)程

(1.4口s)可長(zhǎng)得足以執(zhí)行372000個(gè)浮點(diǎn)運(yùn)算!通常，這

么大的開(kāi)銷(xiāo)主要是由OS核和系統(tǒng)軟件所造成的。有了

這樣的數(shù)字印象后，在使用并行和通信操作時(shí)就要慎重。

30

0■也

1.開(kāi)銷(xiāo)的量化

既然這些額外開(kāi)銷(xiāo)如此之大，那么就應(yīng)該定量化它們。

但是,現(xiàn)實(shí)情況是計(jì)算機(jī)廠商們既很少提供數(shù)據(jù),也很

少提供開(kāi)銷(xiāo)的估計(jì)方法。Hockney曾針對(duì)點(diǎn)到點(diǎn)通信給

出了幾個(gè)有關(guān)開(kāi)銷(xiāo)的參數(shù)r8、nil/2、tO和兀0。下面

我們修介紹使用測(cè)量的方法來(lái)量化這些開(kāi)銷(xiāo)參數(shù)。開(kāi)

銷(xiāo)的測(cè)量與所使用的數(shù)據(jù)結(jié)構(gòu)、程序語(yǔ)言、通信硬件

與協(xié)議以及計(jì)時(shí)方法（掛鐘時(shí)間或CPU時(shí)間）等有關(guān)。為

了獲得精確的測(cè)量值并非易事，因?yàn)榻^大多數(shù)機(jī)器系統(tǒng)

只提供粗的時(shí)間分辯率（微秒級(jí)，甚至毫秒級(jí)）；并行機(jī)

中的各處理器常以異步方式操作，不合公共時(shí)鐘節(jié)拍；

測(cè)量結(jié)果離散性太大，所以比較普遍的方法是采用點(diǎn)

到點(diǎn)乒一乓測(cè)量法。

31

、靜0■也”"號(hào)

2.開(kāi)銷(xiāo)的測(cè)量

對(duì)于點(diǎn)到點(diǎn)的通信，測(cè)量開(kāi)銷(xiāo)使用使用乒一乓方法

(Ping-PongScheme)：節(jié)點(diǎn)0發(fā)送m個(gè)字節(jié)給節(jié)點(diǎn)1;節(jié)

點(diǎn)1從節(jié)點(diǎn)0接收m個(gè)字節(jié)后，立即將消息發(fā)回節(jié)點(diǎn)0?？?/p>

的時(shí)間除以2,即可得到點(diǎn)到點(diǎn)通信時(shí)間，也就是執(zhí)行單

一發(fā)送或接收操作的時(shí)間。用乒一乓方式測(cè)量延遲的

代碼段如下：

乒-乓方法可一般化為熱土豆法(Hot-Potato),也

稱(chēng)為救火隊(duì)法(Fire-Brigade)：節(jié)點(diǎn)。發(fā)送m個(gè)字節(jié)

點(diǎn)1,節(jié)點(diǎn)1在將其發(fā)送給接點(diǎn)2,依此類(lèi)堆，最后節(jié)點(diǎn)

n-1再將苴法回給節(jié)占0.最后時(shí)間再除以n即可一

32

//*乒_乓法測(cè)量延遲的代碼段*//

fori=0toRuns-1do/*發(fā)送者*/

if(my-node_id=0)then

temp=second()/*second()為時(shí)標(biāo)函數(shù)*/

start_time=second()

sendanm-bytemessagetonode1

receiveanm-bytemessagefromnode1

end-time=second()

timer-overhead=start-time-timer_overhead

tota1_time=end-time-start-time+timer.overhead

communication_time[i]=total.time/2

elseif(my_node_id=1)then/*接收者*/

receiveanm-bytemessagefromnode0

sendanm-bytemessagetonode0

endif

endif

33

）熏學(xué)大號(hào)

3.開(kāi)銷(xiāo)的表達(dá)式

通過(guò)測(cè)試方法所獲得的開(kāi)銷(xiāo)數(shù)據(jù)，通常有3種方法

進(jìn)行解釋?zhuān)?/p>

列表法

繪圖法

解析法

其中解析表示法是最通用的。

34

0■也

,TFTj、A￥入3

⑥⑴點(diǎn)到點(diǎn)的通信:Hockney對(duì)于點(diǎn)到點(diǎn)的通信,給出

了如下所示的通信開(kāi)銷(xiāo)t(ni)的解析表達(dá)式，它是消息

長(zhǎng)度m(字節(jié))的線性函數(shù)：

t(m)=t0+m/r0G(3.14)

其中，t0是啟動(dòng)時(shí)間(RS);一是漸近帶寬(MB/S),

表示傳送無(wú)限長(zhǎng)的消息時(shí)的通信速率。Hockney也同時(shí)

引入了兩個(gè)附加參數(shù)：半峰值長(zhǎng)度叫〃(字節(jié))，表示達(dá)

到一半漸近帶寬(即1/21)所需要的消息長(zhǎng)度；特定

性能?！?MB/S),表示短消息帶寬。4個(gè)參數(shù)t。、■、

叫/2和兀0中只有兩個(gè)是獨(dú)立的，其它兩個(gè)可使用如下關(guān)

系式推導(dǎo)出：

tO=ml/2/r°°=1/TTO(3.15)

35

0■也

?TFT夕A千八3

⑵整體通信：

幾種典型的整體通信有：

①播送(Broadcasting)：處理器。發(fā)送m個(gè)字節(jié)

給所有的n個(gè)處理器；

②收集(Gather)：處理。接收所有n個(gè)處理器發(fā)來(lái)

在消息，所以處理器。最終接收了mn個(gè)字節(jié)；

③散射(Scatter)：處理器0發(fā)送了m個(gè)字節(jié)的不同

消息給所有n個(gè)處理器，因此處理器。最終發(fā)送了nin個(gè)

字節(jié)；

④全交換(TotalExchange)：每個(gè)處理器均彼此

相互發(fā)送m個(gè)字節(jié)的不同消息給對(duì)方，所以總通信量為

nm2個(gè)字節(jié)；

36

)熏學(xué)大號(hào)

⑤循環(huán)移位(Circular-shift):處理器i發(fā)送m個(gè)

字節(jié)給處理器i+1,處理器n-1發(fā)送ni個(gè)字節(jié)給處理器0,

所以通信量為mn個(gè)字節(jié)。有文獻(xiàn)將公式(3.14)推廣之,

使得通信開(kāi)銷(xiāo)T(ni,n)是m和n的函數(shù)，但與1co只是n

的函數(shù)：

T(m,n)=t0(n)+m/1co(n)(3.16)

同時(shí),他們對(duì)SP2機(jī)器所測(cè)得的數(shù)據(jù)進(jìn)行擬合，推導(dǎo)

出如表3.2所示的整體通信和路障同步開(kāi)銷(xiāo)表達(dá)式。

注意，當(dāng)超過(guò)256個(gè)處理器時(shí)，路障開(kāi)銷(xiāo)為768RS,

等效于執(zhí)行768x266=204,288個(gè)浮點(diǎn)運(yùn)算?？梢?jiàn)只有

當(dāng)大的計(jì)算粒度時(shí)，才宜于使用路障操作。

37

0■也

表3.2SP?機(jī)器的整體通信和路障同步開(kāi)銷(xiāo)表達(dá)式一覽表

整體通信操作表達(dá)式

播送521ogn+(0.0291ogn)m

收集/散射(171ogn+15)+(0.025n-0.02)m

全交換801ogn+(0.03nL29)m

循環(huán)移位(61ogn+60)+(0.0031ogn+0.04)m

路障同步94logn+10

38

”紅號(hào)并行機(jī)的可用性與好用性

一個(gè)優(yōu)良的并行機(jī)系統(tǒng)，除了應(yīng)具有高的基本性能

指標(biāo)以及低的并行與通信開(kāi)銷(xiāo)外,還應(yīng)具有：

可用性(Availability):是指系統(tǒng)正常運(yùn)行時(shí)間

的百分比

好用性(Usability):是指用戶(hù)使用機(jī)器時(shí)的感受

程度

39

0■也

?TFT夕A千八3

L機(jī)器的可用性

人們常將機(jī)器的可靠性(Reiiabi1ity),可用性

(Availabi1ity),與服務(wù)性(Serviceabi1ity)合在一起

簡(jiǎn)稱(chēng)為機(jī)器的RAS性能，但有時(shí)候易將它們的概念相混

淆。事實(shí)上，可靠性是用平均無(wú)故障時(shí)間MTTF(Mean

TimeToFai1)來(lái)度量，系指系統(tǒng)失效前平均正常運(yùn)行

的時(shí)間;服務(wù)性是用平均修復(fù)時(shí)間MTTR(MeanTimeTo

Repair)來(lái)度量，系指系統(tǒng)失效后修理恢復(fù)正常工作的

時(shí)間；而可用性被定義為：

Availability=MTTF/(MTTF+MTTR)(2.18)

40

0■也

,TFTj、A￥入3

卷2.并行機(jī)的好用性

因?yàn)闄C(jī)器的好用性直接與用戶(hù)有關(guān)，所以機(jī)器的好

用性的討論是與并行機(jī)系統(tǒng)所提供的用戶(hù)環(huán)境分不開(kāi)

的。目前用戶(hù)使用并行機(jī)的環(huán)境主要有：

①遠(yuǎn)程登錄結(jié)合命令行：

這是早期并行機(jī)典型的用戶(hù)環(huán)境，用戶(hù)通過(guò)登錄到

并行機(jī)上，再調(diào)用系統(tǒng)命令來(lái)完成自己的工作。其優(yōu)點(diǎn)

是簡(jiǎn)單、通用，只要并行機(jī)提供Telnet服務(wù)既可；而缺

點(diǎn)是用戶(hù)必須熟悉機(jī)器的有關(guān)命令,且沒(méi)有圖形用戶(hù)界

面GUI(GraphicUserInterface),所以不夠直觀。

41

②GUI+X協(xié)議:

用戶(hù)從客戶(hù)端直接登錄到并行機(jī)上，利用X協(xié)議修

并行機(jī)上的用戶(hù)GUI窗口輸送到本地計(jì)算機(jī)，從而達(dá)到

遠(yuǎn)程使用并行機(jī)的目的。其優(yōu)點(diǎn)是用戶(hù)遠(yuǎn)程使用并行

機(jī)尤如在本地使用并行機(jī)一樣，所以很方便；而缺點(diǎn)

是由于用戶(hù)的圖形界面是在并行機(jī)上實(shí)現(xiàn)的，所以占

用了寶貴的并行計(jì)算資源。此外，本地機(jī)必須支持X協(xié)

議，否則窗口無(wú)法傳到本地計(jì)算機(jī)來(lái)。

③客戶(hù)GUI+服務(wù)器：

這種方式是由客戶(hù)端提供用戶(hù)環(huán)境的GUI,并行機(jī)

作為服務(wù)器解釋和執(zhí)行客戶(hù)端發(fā)來(lái)的請(qǐng)求。其優(yōu)點(diǎn)是

GUI不占用并行計(jì)算資源；而缺點(diǎn)是當(dāng)客戶(hù)端的機(jī)器平

臺(tái)發(fā)生變化時(shí)，用戶(hù)環(huán)境的GUI需要專(zhuān)門(mén)定制，所以通用

性較差。42

0■也

?TFT夕A千八3

■BaBBBaaMMaMBasBsaBBBMBBMHaaaMBaaMBBHBaBBBaaMMaMBasaBaBHBMBBQflHaaaMBaaMBBHBaBBBaBMaaMBasaBaBHBMBBaaaaaaMBaaMBBHBas

④Web月艮務(wù)器+瀏覽器：

以Web瀏覽器作為用戶(hù)環(huán)境界面，用戶(hù)通過(guò)統(tǒng)一資

源定位URL(UnifiedResourcesLocation)指定Web服

務(wù)器，提出服務(wù)請(qǐng)求；Web服務(wù)器分析用戶(hù)請(qǐng)求，再向并

行機(jī)發(fā)送命令，執(zhí)行用戶(hù)請(qǐng)求，并修結(jié)果傳回給用戶(hù)界

面。其優(yōu)點(diǎn)是由于Web的跨平臺(tái)特性,用戶(hù)可在任何機(jī)

器平臺(tái)上遠(yuǎn)程使用并行機(jī),所以通用性非常好；而缺點(diǎn)

是由于瀏覽器界面(如Applet、Form、Cookie)的表

達(dá)能力有限，所以難以修并行機(jī)的用戶(hù)環(huán)境全面地、動(dòng)

態(tài)地提供給用戶(hù)，速度也比較慢。

43

機(jī)器的成本、價(jià)格與性/價(jià)比

高的性能/價(jià)格比(Performance/CostRatio)是計(jì)

算機(jī)設(shè)計(jì)者和使用者一致的目標(biāo)。性/價(jià)比可定義為速

度/買(mǎi)價(jià)，系指用單位代價(jià)(通常以百萬(wàn)美元表示)所

獲取的性能(通常以MIPS或MFL0PS表示)。例如說(shuō),每百

萬(wàn)元能獲取多少個(gè)MIPS(每秒百萬(wàn)條指令)或多少個(gè)

MFL0PS(每秒百萬(wàn)次浮點(diǎn)運(yùn)算)。高的性/價(jià)比就意味著

是成本有效的(Cost-Effectively)。而成本有效性

(Cost-Effectiveness)可用利用率(Uti1ization)來(lái)指

示。利用率可定義為可達(dá)到的速度與峰值速度之比。

較高的利用率對(duì)應(yīng)著每美元較多的Gflops。

44

（蜘）熏學(xué)大號(hào)

SPP1000C916J916T916T3D8400SP2-WideSP2-ThinSX-4/16PCXL75

ConvexCrayCrayCrayCrayDECIBMIBMNECSGI

圖3.410臺(tái)并行機(jī)的性/價(jià)比（1995年）

45

332算法級(jí)的性能評(píng)測(cè)

算法級(jí)的性能評(píng)測(cè)方法，最初大都是為了評(píng)價(jià)并行

算法的性能提出的，后來(lái)這些評(píng)測(cè)方法也被推廣到并行

程序上。眾所周知,在并行機(jī)上進(jìn)行計(jì)算的主要目的就

是要加速整個(gè)計(jì)算過(guò)程,所以研究并行算法的加速(比)

性能是最根本的。它體現(xiàn)了對(duì)于一個(gè)給定的應(yīng)用，并行

算法相對(duì)于串行算法的執(zhí)行速度加快了多少倍。此外，

隨著計(jì)算負(fù)載的增加和機(jī)器規(guī)模的擴(kuò)大,研究并行算法

的性能是否能隨著處理器數(shù)目的增加而按比例的增加

也是很主要的，這就是所謂的并行算法的可擴(kuò)放性

(Scalabi1ity)問(wèn)題。由于可擴(kuò)放性是個(gè)很主要的概念,

所以后來(lái)推而廣之，就出現(xiàn)了諸如程序的可擴(kuò)放性、

體系結(jié)構(gòu)的可擴(kuò)放性、工藝技術(shù)的可擴(kuò)放性以及應(yīng)用

的可擴(kuò)放性等等。

46

加速比性能定律

簡(jiǎn)單地講,并行系統(tǒng)的加速（比）是指對(duì)于一個(gè)給定

的應(yīng)用，并行算法（或并行程序）的執(zhí)行速度相對(duì)于串行

算法（或串行程序）的執(zhí)行速度加快了多少倍。本節(jié)修

要討論三種加速比性能定律：適用于固定計(jì)算負(fù)載的

Amdahl定律；適用于可擴(kuò)放問(wèn)題的Gustafson定律和

受限于存儲(chǔ)器的Sun-Ni定律。為了以下討論方便，茲定

義如下參數(shù)：令p是并行系統(tǒng)中處理器數(shù)；W是問(wèn)題規(guī)

模（下文中也常叫作計(jì)算負(fù)載、工作負(fù)載，它定義為給

定問(wèn)題的總計(jì)算量），Ws是應(yīng)用程序中的串行分量,W中

可并行化部分為WP（顯然Ws+Wp=W）;f是串行分量比

例（f=Ws/W,Ws=Wl）,l-f為并行分量比例（顯然f+量-

f）=l）;Ts=Tl為串行執(zhí)行時(shí)間，Tp為并行執(zhí)行時(shí)間；S

為加速（比）,E為效率。

47

0■也

?TFT夕A千八3

1.Amdahl定律

Amdahl加速定律的基本出發(fā)點(diǎn)是：

①對(duì)于很多科學(xué)計(jì)算，實(shí)時(shí)性要求很高，即在此類(lèi)應(yīng)用

中時(shí)間是個(gè)關(guān)鍵因素，而計(jì)算負(fù)載是固定不變的。為此

在一定的計(jì)算負(fù)載下，為達(dá)到實(shí)時(shí)性可利用增加處理器

數(shù)來(lái)提高計(jì)算速度；

②因?yàn)楣潭ǖ挠?jì)算負(fù)載是可分布在多個(gè)處理器上的，這

樣增加了處理器就加快了執(zhí)行速度,從而達(dá)到了加速的

目的。

在此意義下，1967年Amdahl推導(dǎo)出了如下固定負(fù)載的加

速公式：

48

cWs+Wp

s=-------------(3.18)

Ws+Wp/p

為了歸一化,Ws+Wp可相應(yīng)地表示為f+(l-f),所以:

3二-------------------------二----------------------------(3.19)

y1X-f1+f(P-1)

P

當(dāng)PT8時(shí)，上式極限為：

S=1/f(3.20)

49

(9)熏學(xué)大號(hào)

這就是著名的Amdahl加速定律，它意味著處理器

數(shù)目的無(wú)限增大，并行系統(tǒng)所能達(dá)到的加速之上限為

1/f，此結(jié)論在歷史上曾對(duì)并行系統(tǒng)的發(fā)展起到了悲觀

的作用。Amdahl定律的幾何意義可清楚地表示在圖

3.5(a),(b)和(c)中。

J

叵

篇4

屋fe

壇fc

H第

50

(a)(b)(c)

實(shí)際上并行加速不僅受限于程序的串行分量，而且

也受并行程序運(yùn)行時(shí)的額外開(kāi)銷(xiāo)影響。令w。為額外開(kāi)

銷(xiāo)，則(3.18)式應(yīng)修改為：

W

S=p(3.21)

匕+%+畋57/1—7)Rl+/(2一1)+%2/%

fW+—+wo

Pp

當(dāng)p-8時(shí)，上式變?yōu)?

(3.22)

f+Wo!W

可見(jiàn)，串行分量越大和并行額外開(kāi)銷(xiāo)越大,則加速越

小。

51

?0T■FT也夕A千八3

2.Gustafson定律

Gustafson加速定律的基本出發(fā)點(diǎn)是：

①對(duì)于很多大型計(jì)算,精度要求很高，即在此類(lèi)應(yīng)用中

精度是個(gè)關(guān)鍵因素，而計(jì)算時(shí)間是固定不變的。此時(shí)為

了提高精度，必須加大計(jì)算量，相應(yīng)地亦必須增多處理

器數(shù)才能維持時(shí)間不變；

②除非學(xué)術(shù)研究，在實(shí)際應(yīng)用中沒(méi)有必要固定工作負(fù)載

而計(jì)算程序運(yùn)行在不同數(shù)目的處理器上,增多處理器必

須相應(yīng)地增大問(wèn)題規(guī)模才有實(shí)際意義。

按此意義，1987年Gustafson給出如下放大問(wèn)題規(guī)模的

加速公式：

52

S，=匕+2即=，+—即(323)

~Ws+p-Wp/p~WS+WPI,J

歸一化后可得

S'=7+夕(1-f)=p+/(l-p)=p-f(pi)(3.24)

當(dāng)p充分大時(shí)，S，與p幾乎成線性關(guān)系，其斜率為1-f。

這就是著名Gustafson加速定律,它意味著隨著處理器

數(shù)目的增多，加速幾乎與處理器數(shù)成比例的線性增加，

串行比例f不再是程序的瓶頸，這對(duì)并行系統(tǒng)的發(fā)展是

個(gè)非常樂(lè)觀的結(jié)論。

53

Gustafson定律的幾何意義可清楚地表示在圖3.6(a),⑹

和(c)中。

工

A1024x

w

1014x1004x993x983x

e-

HHS

面

MS'JO24=1O24TO23f

0%1%2%3%4%

123456123456

處理器數(shù)夕處理器數(shù)P程序中順序部分的百分比f(wàn)

(b)

(a)(c)

54

同樣，當(dāng)考慮到并行程序運(yùn)行時(shí)的額外開(kāi)銷(xiāo)w。時(shí)，

(3.23)式應(yīng)修改為:

S，=%+pWp=7）（325）

;

WS+WP+WO1+WO/WI.

注意，w。是P的函數(shù)，它可能隨P增大、減小或不變。

一般化的Gustafson定律欲達(dá)到線性加速必須使Wo

隨P減小，但這常常是困難的。

55

0■也

?TFT夕A千八3

3.Sun和Ni定律

Xian-HeSun和LionelNi于1993年將Amdahl定

律和Gustafson定律一般化，提出了存儲(chǔ)受限的加速定

律。其基本思想是只要存儲(chǔ)空間許可，應(yīng)盡量增大問(wèn)

題規(guī)模以產(chǎn)生更好和更精確的解（此時(shí)可能使執(zhí)行時(shí)

間略有增加）。換句話說(shuō)，假若有足夠的存儲(chǔ)容量，

并且規(guī)?？蓴U(kuò)放的問(wèn)題滿足Gustafson定律規(guī)定的時(shí)

間要求，那么就有可能進(jìn)一步增大問(wèn)題規(guī)模求得更好

或更精確的解。

56

-熏學(xué)大號(hào)

給定一個(gè)存儲(chǔ)受限問(wèn)題,假定在單節(jié)點(diǎn)上使用了全

部存儲(chǔ)容量M并在相應(yīng)于W的時(shí)間內(nèi)求解之，此時(shí)工作負(fù)

載川=fW+(l-f)Wo在p個(gè)節(jié)點(diǎn)的并行系統(tǒng)上，能夠

求解較大規(guī)模的問(wèn)題是因?yàn)榇鎯?chǔ)容量可增加到pM。令

因子G(p)反應(yīng)存儲(chǔ)容量增加到p倍時(shí)工作負(fù)載的增加量,

所以擴(kuò)大后的工作負(fù)載W=fW+(l-f)G(p)Wo對(duì)照

(3.23)式,存儲(chǔ)受限的加速公式及歸一化相應(yīng)為：

S”=”+(-/)G())少

(3.26)

"+(1-/)G()"/夕

(3.27)

/+(1—/)G(〃)/〃

>Sun和Ni定律的幾何意義可清楚地表示在圖3.7(a)

和⑹中。

叫

號(hào)

森

必

H世

必

5-------------?

123456123456

處理器數(shù)〃處理器數(shù)產(chǎn)

(a)⑹

58

N大號(hào)

⑥同樣，當(dāng)考慮到并行程序運(yùn)行時(shí)的額外開(kāi)銷(xiāo)W0時(shí),

(3.26)式和(3.27)式可修改為：

"+(1-"VG(p)=/+(1-/)G(p)

S=(3.28)

?+(l—/)G(p)少/2+%/+(1-/)G儲(chǔ))/p+%/%

由(3.27)可知，當(dāng)G(p)=l時(shí)，它變?yōu)?+(//)/.,這

就是Amdahl加速定律(3.19)式；當(dāng)G(p)=p時(shí)，它變

為f+為l-f),這就是Gustafson加速定律(3.24)式;

當(dāng)G(p)>p時(shí)，它相應(yīng)于計(jì)算機(jī)負(fù)載比存儲(chǔ)要求增加得快,

此時(shí)Sun和Ni加速均比Amdahl加速和Gustafson

加速為高。

59

0■也

?TFT夕A千八3

4.有關(guān)加速的討論

在實(shí)際應(yīng)用中，可供參考的加速經(jīng)驗(yàn)公式是：

p/logp<S<P(3.29)

可達(dá)線性加速的應(yīng)用問(wèn)題有諸如矩陣相加，內(nèi)積運(yùn)算等,

此類(lèi)問(wèn)題幾乎沒(méi)有通信開(kāi)銷(xiāo)；對(duì)于分治類(lèi)的應(yīng)用問(wèn)題，

它類(lèi)似于二叉樹(shù)，樹(shù)的同級(jí)可并行執(zhí)行,但向根逐級(jí)推

進(jìn)時(shí)，并行度將逐漸減少，此類(lèi)問(wèn)題可望達(dá)到p/logp的

加速；對(duì)于通信密集類(lèi)的應(yīng)用問(wèn)題,其加速經(jīng)驗(yàn)公式可

參考下式：

S=1/C(p)(3.30)

其中C(p)是p個(gè)處理器的某一通信函數(shù),或?yàn)榫€性的或

為對(duì)數(shù)的。

60

0■也

(E/燈千入J

嚴(yán)格的線性加速是難以達(dá)到的，更何況超線性加速

(SuperlinearSpeedup)o但在某些算法或程序中，可

能會(huì)出現(xiàn)超線性加速現(xiàn)象：例如,在某些并行搜索算法

中，允許不同的處理器在不同的分枝方向上同時(shí)搜索，

當(dāng)某一處理器一旦迅速地找到了解，它就向其余的處理

器發(fā)出中止搜索的信號(hào)，這就會(huì)提前取消那些在串行算

法中所作的無(wú)謂的搜索分枝，從而出現(xiàn)超線性加速現(xiàn)象;

又如,在絕大多數(shù)并行機(jī)中，每個(gè)處理器均有少量的高

速緩存，當(dāng)某一問(wèn)題執(zhí)行在大量的處理器上，而其大多

的數(shù)據(jù)均放在高速緩存中時(shí)，總的計(jì)算時(shí)間趨于減少，

如果由于這種高速緩存效應(yīng)所造成的計(jì)算時(shí)間下降補(bǔ)

償了由于通信等所造成的額外開(kāi)銷(xiāo)時(shí)間，則有可能造成

超線性加速現(xiàn)象。

61

0■也

(E/燈千入J

最后值得指出的是,加速的含意對(duì)科學(xué)研究者和工

程實(shí)用者可能有所不同：前者樂(lè)于使用絕對(duì)加速

(AbsoluteSpeedup)的定義，即對(duì)于給定的問(wèn)題，最佳

串行算法所用的時(shí)間除以同一問(wèn)題其并行算法所用的

時(shí)間；后者樂(lè)于使用相對(duì)加速(RelativeSpeedup)的

定義，即對(duì)于給定的問(wèn)題，同一算法在單處理器上運(yùn)行

的時(shí)間除以在多個(gè)處理器上運(yùn)行的時(shí)間。顯然相對(duì)加

速的定義是較寬松和實(shí)際的。

62

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

評(píng)價(jià)并行計(jì)算性能的指標(biāo)，除了上節(jié)所介紹的加速

比以外,并行計(jì)算的可擴(kuò)放性（Scalability）也是主要

性能指標(biāo)之一?？蓴U(kuò)放性最簡(jiǎn)樸的含意是在確定的應(yīng)

用背景下，計(jì)算機(jī)系統(tǒng)（或算法或程序等）性能隨處理器

數(shù)的增加而按比例提高的能力?，F(xiàn)今它已成為并行處

理中一個(gè)重要的研究問(wèn)題,被越來(lái)越廣泛地用來(lái)描述并

行算法（并行程序）能否有效利用可擴(kuò)充的處理器數(shù)的

能力。

63

?0T■FT也夕A千八3

1.并行計(jì)算的可擴(kuò)放性

從上節(jié)所介紹的三種加速定律可知，增加處理器和

求解問(wèn)題的規(guī)模都可能提高加速比，而影響加速的因素

有：

①求解問(wèn)題中的串行分量；

②并行處理所引起的額外開(kāi)銷(xiāo)（通信、等待、競(jìng)爭(zhēng)、

冗余操作和同步等）；

③加大的處理器數(shù)超過(guò)了算法中的并發(fā)程度。

64

0■也

?TFT夕A千八3

■BaBBBaaMMaMBasBsaBBBMBBMHaaaMBaaMBBHBaBBBaaMMaMBasaBaBHBMBBQflHaaaMBaaMBBHBaBBBaBMaaMBasaBaBHBMBBaaaaaaMBaaMBBHBM

增加問(wèn)題的規(guī)模有利于提高加速的因素是：

①較大的問(wèn)題規(guī)?？商峁┹^高的并發(fā)度；

②額外開(kāi)銷(xiāo)的增加可能慢于有效計(jì)算的增加；

③算法中的串行分量比例不是固定不變的（串行部

分所占的比例隨著問(wèn)題規(guī)模的增大而縮小）。

一般情況下，增加處理器數(shù),是會(huì)增大額外開(kāi)銷(xiāo)和

降低處理器利用率的，所以對(duì)于一個(gè)特定的并行系統(tǒng)，

并行算法或并行程序，它們能否有效利用不斷增加的處

理器的能力應(yīng)是受限的，而度量這種能力就是可擴(kuò)放性

這一指標(biāo)。

65

0■也

?TFT夕A千八3

按照Webster字典所作的定義（Scalabi1ityis

theabilitytoscale,i.e,theabilityto

adjustaccordingtoaproportion）,可擴(kuò)放性涉及

到調(diào)整什么和按什么比例兩方面的問(wèn)題。對(duì)于并行計(jì)

算而言，要調(diào)整的是處理數(shù)P和問(wèn)題規(guī)模W,兩者可按不

同比例進(jìn)行調(diào)整，此比例關(guān)系（可能是線性的，多項(xiàng)式的

或指數(shù)的等）就反映了可擴(kuò)放的程度。

當(dāng)研究可擴(kuò)放性時(shí)，總是將并行算法和體系結(jié)構(gòu)一

并考慮,也就是說(shuō)可擴(kuò)放性應(yīng)該是算法和結(jié)構(gòu)的組合。

所以當(dāng)談?wù)撍惴ǖ目蓴U(kuò)放性時(shí)，實(shí)際上是指該算法針對(duì)

某一特定機(jī)器結(jié)構(gòu)的可擴(kuò)放性；同樣當(dāng)談?wù)擉w系結(jié)構(gòu)

的可擴(kuò)放性時(shí)，實(shí)際上是指運(yùn)行于該體系結(jié)構(gòu)的機(jī)器上

的某一個(gè)（或某一類(lèi)）并行算法的可擴(kuò)放性。

66

0■也

(E/燈千入J

進(jìn)行可擴(kuò)放性研究的主要目的是：①確定解決某

類(lèi)問(wèn)題用何種并行算法與何種并行體系結(jié)構(gòu)的組合,可

以有效地利用大量的處理器；②對(duì)于運(yùn)行于某種體系

結(jié)構(gòu)的并行機(jī)上的某種算法當(dāng)移植到大規(guī)模處理機(jī)上

后運(yùn)行的性能；③對(duì)固定的問(wèn)題規(guī)模，確定在某類(lèi)并行

機(jī)上最優(yōu)的處理器數(shù)與可獲得的最大的加速比；④用

于指導(dǎo)改進(jìn)并行算法和并行機(jī)體系結(jié)構(gòu)，以使并行算法

盡可能地充分利用可擴(kuò)充的大量處理器。

盡管可擴(kuò)放性如此重要,并且已被廣泛的研究，但

目前仍無(wú)一個(gè)公認(rèn)的、標(biāo)準(zhǔn)的和被普遍接受的嚴(yán)格定

義和評(píng)判它的標(biāo)準(zhǔn)。下面從不同的角度,介紹三種典型

的可擴(kuò)放性度量方法，即等效率,等速度和平均延遲方

法。

67

康學(xué)大號(hào)

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

可擴(kuò)放性的概念是與加速和效率的概念緊密相關(guān)的,

為此必須先從加速S和效率E講起。令