第7章多處理機(jī)

第7章多處理機(jī)

7?1多處理機(jī)的特點(diǎn)及主要技術(shù)問(wèn)題

7?2多處理機(jī)的硬件結(jié)構(gòu)

73程序并行性

7?4多處理機(jī)的性能

7.5多處理機(jī)的操作系統(tǒng)

第7章多處理機(jī)

7.1多處理機(jī)的特點(diǎn)及主要技術(shù)問(wèn)題

下面從幾個(gè)方面來(lái)概括說(shuō)明其主要差別O

1）結(jié)構(gòu)靈活性

2）程序并行性

3）并行任務(wù)派生

4）進(jìn)程同步

5）資源分配和任務(wù)調(diào)度

第7章,處理機(jī)

多處理機(jī)主要存在如下技術(shù)問(wèn)題:

(1)硬件結(jié)構(gòu)上如何解決好處理機(jī)、存貯器模塊及I/O子

系統(tǒng)之間的互連。

(2)如何最大限度地開(kāi)發(fā)系統(tǒng)的并行性，以實(shí)現(xiàn)多處理機(jī)

各級(jí)的全面并行。

(3)如何選擇分割任務(wù)和子任務(wù)的大小，即任務(wù)的粒度大

小，使并行度高，而輔助開(kāi)銷(xiāo)小。

(4)如何協(xié)調(diào)好多處理機(jī)中各并行執(zhí)行的任務(wù)和進(jìn)程間的

同步問(wèn)題。

(5)如何將各個(gè)任務(wù)分配到一個(gè)或多個(gè)處理機(jī)上，解決好

處理機(jī)調(diào)度、任務(wù)調(diào)度和資源分配問(wèn)題，防止死鎖。

(6)一旦某個(gè)處理機(jī)發(fā)生故障，如何對(duì)系統(tǒng)進(jìn)行重新組織

而不使其癱瘓。國(guó)

第7章多處理機(jī)

7.2多處理機(jī)的硬件結(jié)構(gòu)

7.2.1緊耦合和松耦合

1.緊耦合多處理機(jī)

緊耦合多處理機(jī)是通過(guò)共享主存來(lái)實(shí)現(xiàn)處理機(jī)間通信

的，其通信速率受限于主存的頻寬。但是，由于各處理機(jī)與

主存經(jīng)互連網(wǎng)絡(luò)連接，系統(tǒng)中處理機(jī)數(shù)就受限于互連網(wǎng)絡(luò)帶

寬及多臺(tái)處理機(jī)同時(shí)訪問(wèn)主存發(fā)生沖突的概率。

處理機(jī)

共享存貯器模塊

(a)處理機(jī)不帶專(zhuān)用Cache

圖7.1緊耦合多處理機(jī)的結(jié)構(gòu),

第7章多處理機(jī)

存貯器

處理機(jī)

I/O處理機(jī)

I/O通道

設(shè)備…設(shè)備設(shè)備

圖7.2帶非對(duì)稱(chēng)I/O子系統(tǒng)的多處理機(jī)

第7章多處理機(jī)

圖7.3采用冗余連接的非對(duì)稱(chēng)I/O子系統(tǒng)

第工章多處理機(jī)

2.松耦合多處理機(jī)

圖7.4通過(guò)消息傳送系統(tǒng)連接的松耦合多處理機(jī)結(jié)構(gòu)

第7章多處理機(jī)

圖7.5Cm*多處理機(jī)結(jié)構(gòu)

第7章多處理機(jī)

7.2.2機(jī)間互連形式

1.總線(xiàn)形式

多個(gè)處理機(jī)、存貯器模塊和外圍設(shè)備通過(guò)接口與公用總線(xiàn)

相連，采用分時(shí)或多路轉(zhuǎn)接技術(shù)傳送。其中，單總線(xiàn)方式結(jié)構(gòu)

簡(jiǎn)單、成本低，系統(tǒng)上增減模塊方便，但對(duì)總線(xiàn)的失效敏感。

而且，處理機(jī)數(shù)增加會(huì)增大訪問(wèn)總線(xiàn)沖突的概率而導(dǎo)致系統(tǒng)效

率急劇下降。雖然可以在處理機(jī)中設(shè)置局部存貯器和專(zhuān)用外圍

設(shè)備來(lái)減少訪問(wèn)總線(xiàn)的沖突，但這種單總線(xiàn)形式也只適用于處

理機(jī)數(shù)較少的場(chǎng)合。IBMStretch和UNIVACLarg多處理機(jī)采用

的就是單總線(xiàn)方式。

第7章多處理機(jī)

有兩種辦法可以用來(lái)提高總線(xiàn)形式的系統(tǒng)效率。一種辦

法是，采用優(yōu)質(zhì)高頻同軸電纜來(lái)提高總線(xiàn)的傳輸速率；進(jìn)一

步使用光纖通信，其信息速率可達(dá)109?101。b/s。另一種辦法

是，采用多總線(xiàn)方式來(lái)減少訪問(wèn)總線(xiàn)的沖突概率。如美國(guó)的

Tandem-16和Pluribus就采用雙總線(xiàn)方式來(lái)提供一定的總線(xiàn)冗

余和增大系統(tǒng)總的信息傳送率。日本的實(shí)驗(yàn)多處理機(jī)EPOS

采用的是四總線(xiàn)方式。德國(guó)西門(mén)子公司的結(jié)構(gòu)式多處理機(jī)

SMS采用的是八總線(xiàn)方式。而上節(jié)介紹的Cm*多微處理機(jī)則

采用分級(jí)的多總線(xiàn)方式。

第二章J處理機(jī)

2.環(huán)形互連形式

圖7.6機(jī)間采用環(huán)形互連的多處理機(jī)

章」處理機(jī)

3.交叉開(kāi)關(guān)形式

圖7.7交叉開(kāi)關(guān)形式

第7章多處理機(jī)

自處理機(jī)

P?p

r0「15

請(qǐng)求0

請(qǐng)求1

請(qǐng)求15

圖7.8交叉開(kāi)關(guān)中結(jié)點(diǎn)開(kāi)關(guān)的結(jié)構(gòu)

第7章，處理機(jī)

圖7.9用4X4的交叉開(kāi)關(guān)模塊構(gòu)成

16X16的兩級(jí)交叉開(kāi)關(guān)網(wǎng)絡(luò)

第7章多處理機(jī)

4.多端口存貯器形式

圖7.10四端口存貯器形式的結(jié)構(gòu)

圖7.11X-TREE多處理機(jī)結(jié)構(gòu)框圖

第7章多處理機(jī)

7.2.3存貯器組織

1.并行主存貯器的構(gòu)成

模塊1

主存物理地址模塊內(nèi)部單元號(hào)j模塊號(hào)

log十位log尸位

圖7.12血個(gè)模塊的低位交叉編址

%7^處理機(jī)

塊內(nèi)地址模塊0模塊1

模塊號(hào)；模塊內(nèi)部單元號(hào)

主存物理地址

logm位logn位

?---2---AT------2-------*

圖7.13機(jī)個(gè)模塊的高位交叉編址

第7章多處理機(jī)

圖7.14本地存貯器的概念

第7章，處理機(jī)

P1處理機(jī)

Cache。Cache]Cache『[

縱橫交叉開(kāi)關(guān)

列控制列控制列控制

低

位

交Mi

叉

主存貯器

I--------

~jMhm-l

第1列第CT列

高位交叉

圖7.15多處理機(jī)的二維并行存貯器構(gòu)形

第7章多處理機(jī)

2.多Cache的一致性問(wèn)題

為解決多個(gè)Cache之間的不一致。主要有兩類(lèi)做法。一類(lèi)

是以硬件為基礎(chǔ)的做法，另一類(lèi)則主要是以軟件為基礎(chǔ)的做

法。

以硬件為基礎(chǔ)實(shí)現(xiàn)Cache一致性的辦法有多個(gè)。最普遍采

用的辦法叫監(jiān)視Cache協(xié)議(SnoopyProtocal)法，各個(gè)處理機(jī)中

的Cache控制器隨時(shí)都在監(jiān)視著其他Cache的行動(dòng)。對(duì)于采用

總線(xiàn)互連共享主存的多處理機(jī)，可利用總線(xiàn)的播送來(lái)實(shí)現(xiàn)。

第7章,處理機(jī)

目錄表的具體作法又可分3種。一種是全映象目錄表法。

表中每項(xiàng)有N個(gè)標(biāo)志位對(duì)應(yīng)于多處理機(jī)中全部N臺(tái)處理機(jī)的

Cache。系統(tǒng)中全部Cache均可同時(shí)存有同一個(gè)信息塊的副本。

不過(guò)，這樣的目錄表很龐大，硬件及控制均較復(fù)雜。另一種

是有限目錄表法。表中每項(xiàng)的標(biāo)志位少于N個(gè)。因此，限制了

一個(gè)數(shù)據(jù)塊在各Cache中能存放的副本數(shù)目。這兩種目錄表都

是集中地存入在共享的主存之中，因此需要由主存向各處理機(jī)

廣播。第三種是鏈?zhǔn)侥夸洷矸?。它把目錄分散存放在各個(gè)

Cache中，主存只存有一個(gè)指針，指向一臺(tái)處理機(jī)。要查找所

有放有同一個(gè)信息塊的Cache時(shí)，先找到一臺(tái)處理機(jī)的Cache,

然后順鏈逐臺(tái)查找，直到找到目錄表中的指針為空時(shí)為止。

第7章多處理機(jī)

以軟件為基礎(chǔ)解決Cache一致性的作法，主要優(yōu)點(diǎn)是可以

減少硬件的復(fù)雜性，降低對(duì)互連網(wǎng)絡(luò)通信量的要求，因而性能

價(jià)格比可以較高，比較適用于處理機(jī)數(shù)多的多處理機(jī)。但應(yīng)當(dāng)

指出的是，現(xiàn)在以軟件為基礎(chǔ)的辦法雖已提出了好幾種方案，

但由于可靠性及編譯程序的編寫(xiě)困難，都還沒(méi)有真正在商品化

多處理機(jī)上使用，只在某些試驗(yàn)性系統(tǒng)上使用，如伊利諾大學(xué)

的Cedar機(jī)。

第7章多處理機(jī)

7.3程序并行性

7.3.1并行算法

1.算術(shù)表達(dá)式的并行運(yùn)算

算法必須適應(yīng)具體的計(jì)算機(jī)結(jié)構(gòu)。串行處理機(jī)上習(xí)慣采

用的循環(huán)和迭代算法往往不適合于多處理機(jī)，而采用直接解

法有時(shí)反倒能揭示更多的并行性。

例如，=〃+bx+cx2+dx3

利用霍納(Horner)法可得至U

￡[=Q+x(Z?+Mc+x(d)))

第7章多處理機(jī)

G)

圖7.16不同算法影響樹(shù)高的例子

第7章多處理機(jī)

首先從算術(shù)表達(dá)式的最直接形式出發(fā)，利用交換律把相

同的運(yùn)算集中在一起。再利用結(jié)合律把參加這些運(yùn)算的操作

數(shù)(稱(chēng)原子)配對(duì)，盡可能并行運(yùn)算，從而組成樹(shù)高最小的子

樹(shù)。最后，再把這些子樹(shù)結(jié)合起來(lái)。例如，給定表達(dá)式

E2=a+b(c+def+g)+h

需7級(jí)運(yùn)算，如圖7.17(〃)所示。利用交換律和結(jié)合律改寫(xiě)為

Eo=(a+h)+b((c+g)+def)

第7章多處理機(jī)

圖7.17利用交換律和結(jié)合律降低樹(shù)高

第7章多處理機(jī)

利用分配律進(jìn)一步降低樹(shù)高，在恰當(dāng)平衡各子樹(shù)的級(jí)數(shù)的

情況下，往往能收到較好的效果。例如上式，計(jì)算(c+g)的子

樹(shù)時(shí)只用一級(jí)，而計(jì)算慮/的子樹(shù)要用2級(jí)，相加乘。需再增加

2級(jí)。如果把匕寫(xiě)進(jìn)括號(hào)內(nèi)，則計(jì)算bdef仍用2級(jí)已夠，卻省去

了后來(lái)的一次乘兒使總級(jí)數(shù)由5減為4o因此，將上式改寫(xiě)

成

E2=(a+h)+(bc+bg)+bdef

第7章多處理機(jī)

P=3

7產(chǎn)4

圖7.18利用交換律、結(jié)合律和分配律降低樹(shù)高

第7章多處理機(jī)

表達(dá)式運(yùn)算并行性的識(shí)別，除了依靠算法以外，還可以

依靠編譯程序。有一些編譯算法可以經(jīng)過(guò)或不經(jīng)過(guò)逆波蘭后

綴表達(dá)式直接從給定的算術(shù)表達(dá)式產(chǎn)生能并行執(zhí)行的機(jī)器指

令。

例如，給定算術(shù)表達(dá)式

Z=E+A*B*C/D+F

第7章,處理機(jī)

利用普通的串行編譯算法，產(chǎn)生三元指令組為

1*AB

2*1C

3/2D

4+3E

5+4F

6=5Z

第7章多處理機(jī)

指令之間都是相關(guān)的，需5級(jí)運(yùn)算。如采用并行編譯

算法，則可得到能并行執(zhí)行的三元指令組為

1*AB

2/CD

3*12

4+EF

5+34

6=5Z

分配給兩個(gè)處理機(jī)，只需3級(jí)運(yùn)算。

第7章多處理機(jī)

2.遞歸程序的并行性

⑴給定向量

4=（。1，〃2,…,即）

Z?,

B=?2bn）

求歐幾里得內(nèi)積

1/?!+

A-B-aa2b2+...+anbn

這可歸結(jié)為下列遞歸關(guān)系：

JCQ=0

%.=x；1+z

ll—1IaIb.,l<i<n

第7章多處理機(jī)

(2)計(jì)算多項(xiàng)式

P,產(chǎn)Q*+〃1X〃-1+...+*_[X+%

寫(xiě)成霍納法則形式，歸結(jié)為下列遞歸關(guān)系:

A)=〃o

Pi=%+型—J<i<n

第7章多處理機(jī)

(3)計(jì)算菲波納西(Fibonacci)數(shù)列，可用下列遞歸關(guān)系:

九=于2=\

Z=Z-1+Z-23</<^

第7章多處理機(jī)

(4)計(jì)算八位二進(jìn)制數(shù)。二為…%和。=么..力1相加時(shí)的進(jìn)位,

可利用下列遞歸關(guān)系：

4二0

》

g=QjA4V（QjVa）Ac、i，lWiW〃」

以上這些線(xiàn)性遞歸的例子，可以歸納為下列線(xiàn)性遞歸普遍式:

Xj=0,iWO

i-l

x；=c；+V。萬(wàn)'；』<i<n

iiijj7

j=i-n+l

第7章,處理機(jī)

也可用矩陣形式表示為

0-21

0%2

04

■.

■■

0_

或X=C+AX

式中，C=(q...c)稱(chēng)為常數(shù)向量；A是一個(gè)嚴(yán)格下三角矩陣,

稱(chēng)為系數(shù)矩陣；X=(xi...x/,稱(chēng)為結(jié)果向量；《表示向量轉(zhuǎn)置。

第7章多處理機(jī)

在多處理機(jī)上求解這個(gè)線(xiàn)性遞歸普遍式，可以采取下面的

方法。

第一種方法稱(chēng)為列掃算法，步驟如下：

、第一步，先算修=。1，并將士播送到其余各式，用M-1）個(gè)處理

機(jī)計(jì)算〃21/，43Ml，…，an\XV

第二步，用（小1）個(gè)處理機(jī)計(jì)算］2=。2+〃2內(nèi)，。3+。3內(nèi)，…，

內(nèi)；

第三步，把％播送到其余各式，用（小2）個(gè)處理機(jī)計(jì)算

第四步，用（〃-2）個(gè)處理機(jī)計(jì)算工3=。3+。3內(nèi)+。32元2，…,

，+%內(nèi)+即2工2；

馬=4+6

第7章多處理機(jī)

12=4+。2

4=亞+/

第二種較快的并行算法稱(chēng)為乘

14=%+，4

積形式遞歸算法，它是根據(jù)嚴(yán)格下

&=々+。5

三角系數(shù)矩陣A的性質(zhì)把線(xiàn)性遞歸%6=%5+。6

普遍式*=C+AX寫(xiě)成下列形式：…

式中x0=D(O)

X

2i-1=BG)

x2i=DCi)

c”i=QG)

a；=E(i)

第7章多處理機(jī)

例如，當(dāng)仁4時(shí)，式中右邊括號(hào)內(nèi)的值只有4種是不同

的，需用4個(gè)處理機(jī)經(jīng)2步同時(shí)算出，再用2個(gè)處理機(jī)經(jīng)3

步算出與、犬4的最后結(jié)果。總計(jì)起來(lái)，比上一算法少用了一步

的時(shí)間，但多用了一個(gè)處理機(jī)。當(dāng)〃較大時(shí)，這個(gè)算法與上面

的算法相比，快速性會(huì)更為明顯，但處理機(jī)的數(shù)目也會(huì)增加

較多。

第7章多處理機(jī)

給定程序段

DO41=1,N

1E(I)=3*F(I)+SIN(P(I))

2B(I)=D(I-1)+Q(I)

3D(I)=E(I)+B(I)

4CONTIUE

這個(gè)程序段的數(shù)據(jù)相關(guān)圖示于圖7.19中。實(shí)際上，語(yǔ)句1只是

為語(yǔ)句3提供數(shù)據(jù)E(I),而且可在進(jìn)入循環(huán)前全部算出，故可

認(rèn)為是一個(gè)單獨(dú)的數(shù)組運(yùn)算。真正構(gòu)成閉合循環(huán)的只是語(yǔ)句2

和語(yǔ)句3,展開(kāi)如下：

(￡)a+(￡)a=(￡)a￡

(￡)O+(z)a=(￡)az

(z)a+(z)a=(z)aE

(z)O+(i)a=(z)az

(i)a+(i)a=(i)a￡

(i)O+(o)a=d)0z

波鄙*￡害，常

第7章多處理機(jī)

這樣，就把原來(lái)的循環(huán)程序變成了包含2N個(gè)語(yǔ)句的線(xiàn)性

遞歸普遍形式：

X}=XQ^C]

式中xo=D（O）

X=XC

2X^'2-2匚1=3（'）

x=x+c

323孫二。（，）

+C4

x=x+c

545。2尸￡（。

X=XC

65^~6l<z<N

圖7.19線(xiàn)性遞歸程序數(shù)據(jù)相關(guān)圖的例子

第7章多處理機(jī)

7.3.2程序并行性的分析

假定一個(gè)程序包含P「P2、…、PP…、P/、…、P〃等〃個(gè)程

序段，其書(shū)寫(xiě)的順序反映了該程序正常執(zhí)行的順序。為了便于

分析，設(shè)P,.和P,?程序段都是一條語(yǔ)句，P,.在P,之前執(zhí)行，且只討

rJLJ

論P(yáng)j和P/之間數(shù)據(jù)的直接相關(guān)關(guān)系。實(shí)際上，P,和P,即使表面上

1JLJ

沒(méi)有數(shù)據(jù)相關(guān)，也可能通過(guò)它們之間的其他語(yǔ)句形成間接的數(shù)

據(jù)相關(guān)關(guān)系.

第7章多處理機(jī)

⑴數(shù)據(jù)相關(guān)

如果P,的左部變量在P,?的右部變量集內(nèi)，且弓必須取出耳

運(yùn)算的結(jié)果來(lái)作為操作數(shù)，就稱(chēng)P/'、數(shù)據(jù)相關(guān)〃于丹。例如

P,A=5+D

P/C=A*E

相當(dāng)于流水中發(fā)生的''先寫(xiě)后讀〃相關(guān)。順序串行運(yùn)行的

正確結(jié)果應(yīng)當(dāng)是

P，A新=8原原

Pj。新二A新*E原=（5原+。原）*E原

第7章,處理機(jī)

如果讓匕和P,并行，P,的。新成了A原*￡原，顯然不是應(yīng)有的結(jié)

果，因此P,.和P,是不能并行的。如果將P,和P,.執(zhí)行順序顛倒，

交換串行，即先執(zhí)行P”而后再執(zhí)行P〃很明顯同樣也會(huì)得不到

JL

應(yīng)有的正確結(jié)果。如果能夠交換串行就可以讓空閑處理機(jī)先去

執(zhí)行P/,從而有利于宏觀上提高多個(gè)程序段間的并行，加快作

業(yè)執(zhí)行的速度，改進(jìn)系統(tǒng)的運(yùn)行效率。然而，有一種特殊情

形，即當(dāng)P,?和P度從交換律時(shí)，如

P,A=2*A

P.A=3*A

雖不能并行執(zhí)行，卻允許它們交換串行。最終A新為6*A原，和

順序串行的結(jié)果一致。

第7章,處理機(jī)

(2)數(shù)據(jù)反相關(guān)

如果P,的左部變量在P,的右部變量集內(nèi)，且當(dāng)P,未取用其

變量的值之前，是不允許被P,所改變的，就稱(chēng)PJ數(shù)據(jù)反相關(guān)〃

JC

于P/。例如

P,C=A+E

P/A=B+D

相當(dāng)于流水中發(fā)生的''先讀后寫(xiě)〃相關(guān)。順序串行運(yùn)行的

正確結(jié)果應(yīng)是

Pi。新二4原十石原

PjA新=5原原

第7章多處理機(jī)

可以看出，當(dāng)匕與P,并行時(shí)，只要硬件上能保證P,?對(duì)相關(guān)單元

A先讀出，就能得到正確的結(jié)果。然而若將匕和耳交換串行，

就成了

PjA新=8原原

P，。新二人新+石原―原+D原+石原

而發(fā)生錯(cuò)誤，所以，是不能交換串行的。

第7章,處理機(jī)

(3)數(shù)據(jù)輸出相關(guān)

如果P,的左部變量也是P,的左部變量，且P,存入其算得的

值必須在P,存入之后，則稱(chēng)Pf數(shù)據(jù)輸出相關(guān)〃于蚌。例如

PiA=B+D

PjA=C+E

按原執(zhí)行順序A新應(yīng)為可以看出，只要同步能保證巴

的先寫(xiě)入A之后，巴?的再寫(xiě)入A,這兩個(gè)程序段才可以并行。

當(dāng)然，交換串行是不行的，因?yàn)樽詈蠼Y(jié)果將使A新成了了。

第7章,處理機(jī)

除了上述3種相關(guān)外，如果兩個(gè)程序段的輸入變量互為

輸出變量，同時(shí)具有''先寫(xiě)后讀〃和'、先讀后寫(xiě)〃兩種相關(guān)，

以交換數(shù)據(jù)為目的，則兩者必須并行執(zhí)行，既不能順序串

行，也不能交換串行。例如，兩語(yǔ)句的左、右變量互相交

換，

P,A=B

P.B=A

第7章多處理機(jī)

圖7.20能保證讀-寫(xiě)次序的多處理機(jī)結(jié)構(gòu)

第7章多處理機(jī)

如果兩個(gè)程序段之間不存在任何一種數(shù)據(jù)相關(guān)，即無(wú)

共同變量，或共同變量都只出現(xiàn)在右邊的源操作數(shù)，則兩

個(gè)程序段可以無(wú)條件地并行執(zhí)行，也可以串行或交換串行。

例如

P,A=B+C

PjD=B*E

第7章多處理機(jī)

綜上所述：兩個(gè)程序段之間若有先寫(xiě)后讀的數(shù)據(jù)相關(guān)，

不能并行，只在特殊情況下可以交換串行；若有先讀后寫(xiě)的

數(shù)據(jù)反相關(guān)，可以并行執(zhí)行，但必須保證其寫(xiě)入共享主存時(shí)

的先讀后寫(xiě)次序，不能交換串行；若有寫(xiě)-寫(xiě)的數(shù)據(jù)輸出相

關(guān)，可以并行執(zhí)行，但同樣需保證其寫(xiě)入的先后次序，不能

交換串行；若同時(shí)有先寫(xiě)后讀和先讀后寫(xiě)兩種相關(guān)，以交換

數(shù)據(jù)為目的時(shí)，則必須并行執(zhí)行，且要求讀寫(xiě)完全同步，不

許順序串行和交換串行；若沒(méi)有任何相關(guān)，或僅有源數(shù)據(jù)相

同時(shí)，可以并行、順序串行和交換串行。

第7章,處理機(jī)

7.3.3并行程序設(shè)計(jì)語(yǔ)言

FORK語(yǔ)句的形式為FORKm,其中，加為一個(gè)新進(jìn)程開(kāi)

始的標(biāo)號(hào)。執(zhí)行一個(gè)FORK加語(yǔ)句時(shí)，派生出標(biāo)號(hào)為加開(kāi)始的

新進(jìn)程，具體來(lái)說(shuō)，就是準(zhǔn)備好這個(gè)新進(jìn)程啟動(dòng)和繼續(xù)執(zhí)行

所必需的有關(guān)信息；如果是共享主存，則應(yīng)為它產(chǎn)生存貯器

指針、映象函數(shù)和訪問(wèn)權(quán)數(shù)據(jù)；將空閑的處理機(jī)分配給被

FORK語(yǔ)句派生的新進(jìn)程，如果沒(méi)有可用的空閑處理機(jī)，則

應(yīng)讓它們排隊(duì)等待；繼續(xù)在原分配給它的處理機(jī)上執(zhí)行

FORK語(yǔ)句的原進(jìn)程。

第7章多處理機(jī)

與FORK語(yǔ)句相配合，作為每個(gè)并發(fā)進(jìn)程的終端語(yǔ)句JOIN

的形式為JOIN?其中，〃為已派生出的并發(fā)進(jìn)程個(gè)數(shù)。JOIN語(yǔ)

句附有一個(gè)計(jì)數(shù)器，其初始值置為0。每當(dāng)執(zhí)行JOIN〃語(yǔ)句時(shí)，

計(jì)數(shù)器的值加1,并與〃比較。若比較相等，表明這是執(zhí)行中的

第〃個(gè)并發(fā)進(jìn)程經(jīng)過(guò)JOIN語(yǔ)句，于是允許該進(jìn)程通過(guò)JOIN語(yǔ)

句，將計(jì)數(shù)器清0,在其所在的處理機(jī)上繼續(xù)執(zhí)行后續(xù)語(yǔ)句。

若比較結(jié)果，計(jì)數(shù)器的值仍小于〃,則表明此進(jìn)程不是并發(fā)

進(jìn)程中的最后一個(gè)，可讓現(xiàn)在執(zhí)行JOIN語(yǔ)句的這個(gè)進(jìn)程先結(jié)

束，把它所占用的處理機(jī)釋放出來(lái)，分配給正在排隊(duì)等待的其

他任務(wù)。如沒(méi)有排隊(duì)等待的任務(wù)，則讓該處理機(jī)空閑。

第7章多處理機(jī)

下面仍以731節(jié)引用過(guò)的算術(shù)表達(dá)式

Z=E+A*B*C/D+F

的計(jì)算為例，經(jīng)并行編譯得到如下程序:

S[G=A*B

S2H=C/D

S3I=G*H

S4J=E+F

S5Z=I+J

第7章多處理機(jī)

圖7.21計(jì)算Z=E+A*5*C/D+/的并行程序數(shù)據(jù)相關(guān)圖

第7章多處理機(jī)

利用FORK和JOIN語(yǔ)句實(shí)現(xiàn)這種派生和匯合關(guān)系，將程

序改寫(xiě)為：FORK20

10G=A*B（進(jìn)程SO

JOIN2

GOTO30

20H=C/D（進(jìn)程S2）

JOIN2

30FORK40

I=G*H（進(jìn)程S3）

JOIN2

GOTO50

40J=E+F（進(jìn)程S4）

JOIN2

50Z=I+J（進(jìn)程S5）

第7章多處理機(jī)

處理機(jī)

J0IN2FORK40J0IN2

S?

2釋放

IJ0IN2

GOTO50

1舞放

FORK20'釋放'J01N2

時(shí)間

圖7.22圖7.21的計(jì)算程序在多處理

機(jī)上運(yùn)行的資源時(shí)間圖

第7章多處理機(jī)

仍假定A、5兩個(gè)8X8矩陣相乘，需要在多處理機(jī)上實(shí)現(xiàn)

任務(wù)一級(jí)即外循環(huán)的并行。用FORTRAN語(yǔ)言書(shū)寫(xiě)的程序如下:

DO10J=0,6

10FORK20

J=7

20DO301=0,7

C(I,J)=O

DO40K=0,7

40C(I,J)=C(I,J)+A(I,K)*B(K,J)

30CONTINUE

JOIN8

第7章,處理機(jī)

處理機(jī)

J01N8J0IN8J0IN8

3J=11J=31J=6匕~

IJ0IN8J0IN8J0IN8

2JJ=0/J=2(J=g八

||JOIN8.ldlN8

]JI?，-jJ=7(J=4八

FORK7次

時(shí)間

圖7.23矩陣乘程序在多處理機(jī)上

第7章多處理機(jī)

從表面上看，為了求解同一矩陣乘的題目，多處理機(jī)的每

一個(gè)處理機(jī)和并行處理機(jī)的每一個(gè)處理單元完成的工作是一樣

的，但是這兩種處理方式是有根本區(qū)別的。第一，并行處理

機(jī)的每一條指令要求8個(gè)處理單元完全同步地對(duì)J=0,1,…,7的

不同數(shù)組進(jìn)行運(yùn)算；而在多處理機(jī)中，即使有8個(gè)處理機(jī)執(zhí)行

同一程序段，并不需要、也不會(huì)完全同步，何況一般說(shuō)來(lái)，

不同處理機(jī)所執(zhí)行的程序段可以是毫不相同的。這就是操作

級(jí)并行與任務(wù)級(jí)并行的差別。第二，多處理機(jī)中可用的處理機(jī)

數(shù)目對(duì)程序的書(shū)寫(xiě)沒(méi)有影響，換言之，程序?qū)捎玫奶幚頇C(jī)數(shù)

目并無(wú)固定的要求。這是因?yàn)樘幚頇C(jī)的分配和釋放都是由操作

系統(tǒng)自動(dòng)控制的，它們已經(jīng)反映在FORK和JOIN語(yǔ)句的功能中。

這是多處理機(jī)相對(duì)于并行處理機(jī)的重要優(yōu)點(diǎn)之一。

第7章多處理機(jī)

E.W.Dijkstra將FORK-JOIN概念進(jìn)一步發(fā)展，提出一種

新的等價(jià)的塊結(jié)構(gòu)式語(yǔ)言。在這種語(yǔ)言中，把所有可并行執(zhí)

行的語(yǔ)句或進(jìn)程S1,S2,用cobegin-coend(或parbegin-

parend)前后括起來(lái)，如下所示：

begin

So；

cobeginSpS2；S〃；coend

?

?Q+1，

end

多處理機(jī)

圖7.24并行程序執(zhí)行優(yōu)先過(guò)程圖

第7章多處理機(jī)

’并行語(yǔ)句也可以任意嵌套。例如

begin

So；

cobegin

Si；

begin

S2；

cobeginS3;S4;S5;coend

S6；

end

S7；

coend

S&；

end

第7章多處理機(jī)

圖7.25嵌套并行進(jìn)程的優(yōu)先執(zhí)行過(guò)程圖

第7章多處理機(jī)

7.4多處理機(jī)的性能

7.4.1任務(wù)粒度與系統(tǒng)性能

衡量任務(wù)粒度大小的一個(gè)依據(jù)是程序用于有效計(jì)算的執(zhí)行

時(shí)間￡與處理機(jī)間的通信等輔助開(kāi)銷(xiāo)時(shí)間。的比值。只有

的值較大時(shí)，開(kāi)發(fā)并行性才能得到好處。如果最大并行度會(huì)帶

來(lái)最大的通信等輔助開(kāi)銷(xiāo)，倒不如增大任務(wù)粒度，降低并行

度，來(lái)減少輔助開(kāi)銷(xiāo)。因此，為獲得最佳的性能，必須對(duì)并行

性和額外開(kāi)銷(xiāo)進(jìn)行綜合平衡。

第7章多處理機(jī)

7.4.2性能模型與分析

1.N=2且計(jì)算與通信不能重疊

一個(gè)程序在雙處理機(jī)上運(yùn)行，如果將全部任務(wù)都分配給一

臺(tái)處理機(jī)而讓另一臺(tái)處理機(jī)空閑，雖然沒(méi)有并行，卻不需要機(jī)

間通信。程序總的運(yùn)行時(shí)間尺=7?￡。如果將其中/個(gè)任務(wù)分配

給一臺(tái)處理機(jī)，而將余下的T-/個(gè)任務(wù)分配給另一臺(tái)處理機(jī)，

則

^=Emax{T-Zj}+C(T-Z)Z

第7章,處理機(jī)

Q）不同E/C的執(zhí)行時(shí)間、通信時(shí)間與，的關(guān)系Q）不同E/C的總運(yùn)行時(shí)間R與I的關(guān)系

圖7.26不同￡/C時(shí)，執(zhí)行時(shí)間、通信時(shí)間和

總運(yùn)行時(shí)間火與任務(wù)分配數(shù)/的關(guān)系

第7章多處理機(jī)

2.N>2且計(jì)算與通信不能重疊

若將4個(gè)任務(wù)分配給第k臺(tái)處理機(jī)，則

N「N

7?=Emax{4}+--^4(T-/J

k=lZTT"

乙%二1

N

由于，4=T，所以有

k=l

N「(N、

C

R=E^x{lk}+-片—立；

y21k=ij

第7章多處理機(jī)

究竟是采用平均分配還是集中分配，可以通過(guò)計(jì)算這兩

種任務(wù)分配策略的總運(yùn)行時(shí)間差來(lái)決定。為簡(jiǎn)單起見(jiàn)，設(shè)T是

N的整數(shù)倍，則平均分配與集中分配二者總運(yùn)行時(shí)間差為

(ETCT2CT2}

--------1-----------------E----T-

IN22N)

若令其等于0,可得￡/。=772。這說(shuō)明，當(dāng)￡/?！?72時(shí)，應(yīng)采

用平均分配策略；而當(dāng)￡/。＜772時(shí)，因?yàn)轭~外開(kāi)銷(xiāo)。較大，

應(yīng)采用集中分配策略，否則并行執(zhí)行的總運(yùn)行時(shí)間反而會(huì)延

長(zhǎng)。

第7章多處理機(jī)

進(jìn)一步，可求得采用平均分配時(shí)，并行系統(tǒng)的加速比

EN

二集中分配的尺二ET二三

「一平均分配的R―ET喬""CF—E(N-1)T

----1-----------?

N22NC2

由此得到一個(gè)重要的結(jié)論是，如果E/C〉〉T匚NL，加速比可接

2

近于N。即當(dāng)任務(wù)數(shù)T及處理機(jī)數(shù)N均較少，E/C又較大時(shí)，并行

系統(tǒng)的加速比是隨處理機(jī)機(jī)數(shù)N的增加而接近線(xiàn)性地提高的。

但當(dāng)機(jī)數(shù)N增大到較大后，3〃就趨近于2￡/(CT),只與E/C及任務(wù)

數(shù)7W關(guān)，而與機(jī)數(shù)N基本無(wú)關(guān)了。

第7章多處理機(jī)

加

速

比

^

12345678910

處理機(jī)數(shù)N

圖7.27,隨N的變化趨勢(shì)

第7章多處理機(jī)

表7.17=20、￡=100、不同。時(shí)?與N的關(guān)系

N12345678910

5P(C=1)11.822.53.083.5744.374.7155.26

SP(C=2)11,672.132.52.7833.183.333.463.57

第7章多處理機(jī)

在多處理機(jī)上并不是每個(gè)任務(wù)均需要與其他任務(wù)通信的。

較常見(jiàn)的情況是，一個(gè)任務(wù)與其他任務(wù)通信且通信內(nèi)容相同

時(shí)，只需向每臺(tái)處理機(jī)通信一次即可。這樣，任務(wù)分配給N臺(tái)

處理機(jī)后，系統(tǒng)總運(yùn)行時(shí)間為

R=E?max"J+CN

表7?27=20、￡=10、不同。時(shí)Sp與N的關(guān)系

N12345678910

5P(C=1)0.9951.9612.8713.7044.445.0825,6226.0616.4066.667

SP(C=10)0.9521.6672.0692.2222.2222.1432.0291.9051.7821.667

第7章多處理機(jī)

當(dāng)機(jī)數(shù)由N臺(tái)增加到N+1臺(tái)時(shí)，總運(yùn)行時(shí)間的減少量為

(11)

ET----------------C=—------C

(NN+1)N(N+1)

令其大于等于3有N氣pO可見(jiàn)，多處理機(jī)性能最

佳時(shí)的機(jī)數(shù)N是E/C的函數(shù)，當(dāng)N>后，增大機(jī)數(shù)N,

反而會(huì)使總運(yùn)行時(shí)間延長(zhǎng)。

第，章,處理機(jī)

3,額外開(kāi)銷(xiāo)與計(jì)算工作可以重疊

假定額外工作被計(jì)算工作完全覆蓋，則總運(yùn)行時(shí)間為

NCN

R=max{E?吧x{/Z4(7一4)>

、-2人0J

當(dāng)E/C與772時(shí)，虛直線(xiàn)與實(shí)曲線(xiàn)沒(méi)有交點(diǎn)或僅在/=772處有一

個(gè)交點(diǎn)，執(zhí)行時(shí)間完全覆蓋了額外開(kāi)銷(xiāo)。當(dāng)E/CVT/2時(shí)，虛直線(xiàn)

與實(shí)曲線(xiàn)有兩個(gè)交點(diǎn)。交點(diǎn)之縱坐標(biāo)為最短總運(yùn)行時(shí)間，橫坐標(biāo)

為此時(shí)任務(wù)分配數(shù)I的最佳取值。在交點(diǎn)、處為E(T-I)=C(T-I)I,即

I=E/C,其中1二o此時(shí)，總運(yùn)行時(shí)間R=C[T—3白=后上—3；

加速比Sp=T石//3號(hào)=14_m。Sp肯定處于lf/寵間，用

/=772時(shí)，有意上值2?如艮小至1,