并行體系結(jié)構(gòu)(陳國(guó)良版)課后答案

1.指導(dǎo)思想

要求學(xué)生理解高端并行計(jì)算機(jī)系統(tǒng)設(shè)計(jì)技術(shù)，高端MPP、

DSM、CLUSTER等大規(guī)模并行計(jì)算機(jī)的關(guān)鍵設(shè)計(jì)理論和實(shí)現(xiàn)技

術(shù)，包括互連網(wǎng)絡(luò)技術(shù)、存儲(chǔ)架構(gòu)和高可用技術(shù)等。為此，必須

用適量的作業(yè)、習(xí)題，啟發(fā)學(xué)生獨(dú)立思考以及熟練掌握一些基礎(chǔ)

知識(shí)和基本技能。

習(xí)題設(shè)計(jì)

計(jì)劃

2.作業(yè)安排

本教材每一章都附有大量的習(xí)題，根據(jù)教學(xué)進(jìn)度和學(xué)時(shí)，合

理選擇書上習(xí)題，以達(dá)到進(jìn)一步加深理解課堂講授的內(nèi)容。每一

章講授結(jié)束，收一次作業(yè)，給出成績(jī)，并作一次集體答疑，講解

作業(yè)中的共性問題。作業(yè)成績(jī)記入總成績(jī)內(nèi)。

第一章緒論

1.1什么是并行計(jì)算機(jī)？

答：簡(jiǎn)單地講，并行計(jì)算機(jī)就是由多個(gè)處理單元組成的計(jì)算機(jī)系統(tǒng)，這些處理單元相互通信

和協(xié)作，能快速高效求解大型的復(fù)雜的問題。

1.2簡(jiǎn)述Flynn分類法：

答：根據(jù)指令流和數(shù)據(jù)流的多重性將計(jì)算機(jī)分為：

1）單指令單數(shù)據(jù)流SISD

2）單指令多數(shù)據(jù)流SIMD

3）多指令單數(shù)據(jù)流MISD

4）多指令多數(shù)據(jù)流MIMD

1.3簡(jiǎn)述當(dāng)代的并行機(jī)系統(tǒng)

答：當(dāng)代并行機(jī)系統(tǒng)主要有：

1）并行向量機(jī)（PVP）

2）對(duì)稱多處理機(jī)（SMP）

3）大規(guī)模并行處理機(jī)（MPP）

4）分布式共享存儲(chǔ)（DSM）處理機(jī)

5）工作站機(jī)群（COW）

1.4為什么需要并行計(jì)算機(jī)？

答：1）加快計(jì)算速度

2）提高計(jì)算精度

3）滿足快速時(shí)效要求

4）進(jìn)行無法替代的模擬計(jì)算

1.5簡(jiǎn)述處理器并行度的發(fā)展趨勢(shì)

答：1）位級(jí)并行

2）指令級(jí)并行

3）線程級(jí)并行

1.6簡(jiǎn)述SIMD陣列機(jī)的特點(diǎn)

答：1）它是使用資源重復(fù)的方法來開拓計(jì)算問題空間的并行性。

2）所有的處理單元（PE）必須是同步的。

3)陣列機(jī)的研究必須與并行算法緊密結(jié)合，這樣才能提高效率。

4)陣列機(jī)是一種專用的計(jì)算機(jī)，用于處理一些專門的問題。

1.7簡(jiǎn)述多計(jì)算機(jī)系統(tǒng)的演變

答：分為三個(gè)階段：

1)1983-1987年為第一代，代表機(jī)器有：Ipsc/1、Ameteks/14等。

2)1988-1992年為第二代，代表機(jī)器有：Paragon、Inteldelta等。

3)1993-1997年為第三代，代表機(jī)器有：MIT的J-machine。

1.8簡(jiǎn)述并行計(jì)算機(jī)的訪存模型

答：1)均勻存儲(chǔ)訪問模型(UMA)

2)非均勻存儲(chǔ)訪問模型(NUMA)

3)全高速緩存存儲(chǔ)訪問模型(COMA)

4)高速緩存一致性非均勻訪問模型(CC-NUMA)

1.9簡(jiǎn)述均勻存儲(chǔ)訪問模型的特點(diǎn)

答：1)物理存儲(chǔ)器被所有處理器均勻共享。

2)所有處理器訪問任何存儲(chǔ)字的時(shí)間相同。

3)每臺(tái)處理器可帶私有高速緩存。

4)外圍設(shè)備也可以一定的形式共享。

1.10簡(jiǎn)述非均勻存儲(chǔ)訪問模型的特點(diǎn)

答：1)被共享的存儲(chǔ)器在物理上分布在所有的處理器中，其所有的本地存儲(chǔ)器的集合構(gòu)成

了全局的地址空間。

2)處理器訪問存儲(chǔ)器的時(shí)間不一樣。

3)每臺(tái)處理器可帶私有高速緩存，外備也可以某種的形式共享。

第二章性能評(píng)測(cè)

2.1使用40MHz主頻的標(biāo)量處理器執(zhí)行一個(gè)典型測(cè)試程序，其所執(zhí)行的指令數(shù)及所需的周

期數(shù)如表2.13所示。試計(jì)算執(zhí)行該程序的有效CPI、MIPS速率及總的CPU執(zhí)行時(shí)間。

解：CPI=totalcycles/totalinstructions

=(45000*1+32000*2+15000*2+8000*2)/(45000+32000+15000+8000)

=1.55

乂氏$=時(shí)鐘頻率/(CPI*106)=(40*106)/(1.55*106)=25.8

CPU執(zhí)行時(shí)間=totalcycles/時(shí)鐘頻率=0.00375s

2.2欲在40M11Z主頻的標(biāo)量處理器上執(zhí)行20萬條目標(biāo)代碼指令程序。假定該程序中含有4

種主要類型之指令，各指令所占的比例及CPI數(shù)如表2.14所示，試計(jì)算：

①在單處理機(jī)上執(zhí)行該程序的平均CPI。

②由①所得結(jié)果，計(jì)算相應(yīng)的MIPS速率。

解：⑴CPI=1*60%+2*18%+4*12%+8*10%

=2.12

(2)乂氏5=時(shí)鐘頻率/(CPI*106)=(40*106)/(2.12*106)=18.9

2.12.3已知SP2并行計(jì)算機(jī)的通信開銷表達(dá)式為：t(m)=46+(0.035)in,試計(jì)算：

①漸近帶寬r~=?

②半峰值信息長(zhǎng)度飛=?[提示：546us]

解：⑴漸近帶寬rx=l/0.035=28.6MB/S

(2)半峰值消息長(zhǎng)度mi/2=to*rs=46us*28.6MB/S=1315.6B

2.4并行機(jī)性能評(píng)測(cè)的意義。

答：意義有：

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

2）減少用戶購機(jī)盲目性，降低投資風(fēng)險(xiǎn)。

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

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

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

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

2.5如何進(jìn)行并行機(jī)性能評(píng)測(cè)

答：1）機(jī)器級(jí)性能評(píng)測(cè)：CPU和存儲(chǔ)器的某些基本性能指標(biāo)；并行和通信開銷分析；并行

機(jī)的可用性與好用性以及機(jī)器成本、價(jià)格與性/價(jià)比。

2）算法級(jí)性能評(píng)測(cè)：加速比、效率、擴(kuò)展性。

3）程序級(jí)性能評(píng)測(cè)：Benchmark。

2.6簡(jiǎn)述Gustafson定律的出發(fā)點(diǎn)

答：1）對(duì)于很多大型計(jì)算，精度要求很高，即在此類應(yīng)用中精度是個(gè)關(guān)鍵因素，而計(jì)算時(shí)

間是固定不變的。此時(shí)為了提高精度，必須加大計(jì)算量，相應(yīng)地亦必須增多處理器數(shù)才能維

持時(shí)間不變。

2）除非學(xué)術(shù)研究，在實(shí)際應(yīng)用中沒有必要固定工作負(fù)載而計(jì)算程序運(yùn)行在不同數(shù)目的

處理器上，增多處理器必須相應(yīng)地增大問題規(guī)模才有實(shí)際意義。

2.7已知一程序可并行代碼占比例為80%,將其在有10個(gè)處理器的系統(tǒng)中運(yùn)行，求其加速

比？并求其極限加速比？并分析其結(jié)構(gòu)帶來的影響

解：加速比=1/（20%+80%/10）=1/（0.2+0.08）=3.57。

極限加速比，即處理器個(gè)數(shù)無窮大的時(shí)候呈現(xiàn)的加速比=1/20%=5。

這個(gè)極限加速比，換個(gè)角度說是，Amdahl定律在很長(zhǎng)一段時(shí)間影響了人們對(duì)開發(fā)并行

計(jì)算機(jī)的信心，對(duì)于本例，因?yàn)榫退隳惆烟幚砥髯龅綗o窮也只能得到5倍的加速比，同時(shí)有

一點(diǎn)更明顯，就是處理器數(shù)目增加到一定程度后，加速比的增長(zhǎng)非常緩慢。

2.8簡(jiǎn)述影響加速的因素

答：1）求解問題中的串行分量。

2）并行處理器所引起的額外開銷。

3）加大的處理器數(shù)超過的算法的并發(fā)程度。

2.9為什么增加問題規(guī)?？梢栽谝欢ǔ潭忍岣呒铀?/p>

答：1）較大的問題規(guī)模可提高較大的并發(fā)度。

2）額外開銷的增加可能慢于有效計(jì)算的增加。

3）算法中串行分量的比例不是固定不變的。

2.10進(jìn)行可擴(kuò)放行研究的主要意義

答：1）確定解決某類問題用某類并行算法和某類并行體系結(jié)構(gòu)結(jié)合，可以有效的利用大量

的處理器。

2）對(duì)于運(yùn)行于某種體系結(jié)構(gòu)的并行機(jī)的某種算法當(dāng)移到大規(guī)模處理機(jī)上的性能。

3）對(duì)于某類固定規(guī)模的問題，確定在某類并行機(jī)上的最優(yōu)處理器數(shù)目和最大的加速比。

4）用于指導(dǎo)改進(jìn)并行算法和并行體系結(jié)構(gòu)，以使并行算法能盡可能充分利用可擴(kuò)充的。

大量的處理器。

第三章互連網(wǎng)絡(luò)

3.1對(duì)于一顆K級(jí)二叉樹（根為0級(jí)，葉為k-1級(jí)），共有N=2”-l個(gè)節(jié)點(diǎn)，當(dāng)推廣至m-

元樹時(shí)（即每個(gè)非葉節(jié)點(diǎn)有m個(gè)子節(jié)點(diǎn)）時(shí)，試寫出總節(jié)點(diǎn)數(shù)N的表達(dá)式。

答:

推廣至M元樹時(shí)，k級(jí)M元樹總結(jié)點(diǎn)數(shù)N的表達(dá)式為：

N=l+mAl+mA2+...+mA(k-1)=(l-mAk)*l/(l-m);

3.2二元胖樹如圖3.46所示，此時(shí)所有非根節(jié)點(diǎn)均有2個(gè)父節(jié)點(diǎn)。如果將圖中的每個(gè)橢圓均

視為單個(gè)節(jié)點(diǎn)，并且成對(duì)節(jié)點(diǎn)間的多條邊視為一條邊，則他實(shí)際上就是一個(gè)二叉樹。試問：

如果不管橢圓，只把小方塊視為節(jié)點(diǎn)，則他從葉到根形成什么樣的多級(jí)互聯(lián)網(wǎng)絡(luò)？

答：8輸入的完全混洗三級(jí)互聯(lián)網(wǎng)絡(luò)。

3.3四元胖樹如圖3.47所示，試問：每個(gè)內(nèi)節(jié)點(diǎn)有幾個(gè)子節(jié)點(diǎn)和幾個(gè)父節(jié)點(diǎn)？你知道那個(gè)機(jī)

器使用了此種形式的胖樹？

答：每個(gè)內(nèi)節(jié)點(diǎn)有4個(gè)子節(jié)點(diǎn)，2個(gè)父節(jié)點(diǎn)。CM-5使用了此類胖樹結(jié)構(gòu)。

3.4試構(gòu)造一個(gè)N=64的立方環(huán)網(wǎng)絡(luò)，并將其直徑和節(jié)點(diǎn)度與N=64的超立方比較之，你的

結(jié)論是什么？

答：AN=64的立方環(huán)網(wǎng)絡(luò)，為4立方環(huán)(將4維超立方每個(gè)頂點(diǎn)以4面體替代得到)，直徑

d=9,節(jié)點(diǎn)度n=4

BN=64的超立方網(wǎng)絡(luò)，為六維超立方(將一個(gè)立方體分為8個(gè)小立方，以每個(gè)小立

方作為簡(jiǎn)單立方體的節(jié)點(diǎn)，互聯(lián)成6維超立方)，直徑d=6,節(jié)點(diǎn)度n=6

3.5一個(gè)N=2八k個(gè)節(jié)點(diǎn)的deBruijin網(wǎng)絡(luò)如圖3.48所示，令如〃-。一…“％,是一個(gè)

節(jié)點(diǎn)的二進(jìn)制表示，則該節(jié)點(diǎn)可達(dá)如下兩個(gè)節(jié)點(diǎn)：830,出3、…8必1。

試問：該網(wǎng)絡(luò)的直徑和對(duì)剖寬度是多少？

答：N=24個(gè)節(jié)點(diǎn)的deBruijin網(wǎng)絡(luò)直徑d=k對(duì)剖寬帶w=2%k-l)

3.6一個(gè)N=2八n個(gè)節(jié)點(diǎn)的洗牌交換網(wǎng)絡(luò)如圖3.49所示?試問：此網(wǎng)絡(luò)節(jié)點(diǎn)度==?網(wǎng)絡(luò)直徑

==?網(wǎng)絡(luò)對(duì)剖寬度==?

答：N=2〃n個(gè)節(jié)點(diǎn)的洗牌交換網(wǎng)絡(luò)，網(wǎng)絡(luò)節(jié)點(diǎn)度為=2,網(wǎng)絡(luò)直徑=41,網(wǎng)絡(luò)對(duì)剖寬度=4

3.7一個(gè)N=(k+1)24個(gè)節(jié)點(diǎn)的蝶形網(wǎng)絡(luò)如圖3.50所示。試問：此網(wǎng)絡(luò)節(jié)點(diǎn)度=?網(wǎng)絡(luò)直

徑=?網(wǎng)絡(luò)對(duì)剖寬度=?

答：N=(k+1)2”個(gè)節(jié)點(diǎn)的蝶形網(wǎng)絡(luò)，網(wǎng)絡(luò)節(jié)點(diǎn)度=4,網(wǎng)絡(luò)直徑=2*k,網(wǎng)絡(luò)對(duì)剖寬度

=2Ak

3.9對(duì)于如下列舉的網(wǎng)絡(luò)技術(shù)，用體系結(jié)構(gòu)描述，速率范圍，電纜長(zhǎng)度等填充下表中的各

項(xiàng)。(提示：根據(jù)討論的時(shí)間年限，每項(xiàng)可能是一個(gè)范圍)

答：

網(wǎng)絡(luò)技術(shù)網(wǎng)絡(luò)結(jié)構(gòu)市4H-寬tAx銅線距離光纖距離

Myrinet專用機(jī)群互聯(lián)網(wǎng)絡(luò)200MB/秒25m500m

HiPPI用于異構(gòu)計(jì)算機(jī)和其外設(shè)的800Mbps-1.6G25m300m-10k

組網(wǎng)bpsm

SCI可擴(kuò)展一致性接口，通常獨(dú)立250Mbps?8Gbp

于拓?fù)浣Y(jié)構(gòu)s

光纖通信多處理器和其外圍設(shè)備之間，100Mbps?80050m10km

直連結(jié)構(gòu)Mbps

ATM主要應(yīng)用于因特網(wǎng)主干線中25Mbps-lOGbp

s

FDDI采用雙向光纖令牌環(huán)，所有結(jié)100-200Mbps100m2KM

點(diǎn)聯(lián)接在該環(huán)中

3.10如圖3.51所示，信包的片0,1,2,3要分別去向目的地A,B,C,D。此時(shí)片。占

據(jù)信道CB,片1占據(jù)信道DC,片2占據(jù)信道AD,片3占據(jù)信道BA。試問：

1）這將會(huì)發(fā)生什么現(xiàn)象？

2）如果采用X-Y選路策略，可避免上述現(xiàn)象嗎？為什么？

答：1）通路中形成環(huán)，發(fā)生死鎖

2）如果采用X-Y策略則不會(huì)發(fā)生死鎖。因?yàn)椴捎肵-Y策略時(shí)其實(shí)質(zhì)是對(duì)資源（這里

是通道）進(jìn)行按序分配（永遠(yuǎn)是x方向優(yōu)先于y方向，反方向路由是y方向優(yōu)先于x方向）,

因此根據(jù)死鎖避免的原則判斷，此時(shí)不會(huì)發(fā)生死鎖。

3.12在二維網(wǎng)孔中，試構(gòu)造一個(gè)與X-Y選路等價(jià)的查表路由。

答：所構(gòu)造路由表描述如下：

1）每個(gè)節(jié)點(diǎn)包括兩張路由表x表和y表

2）每個(gè)節(jié)點(diǎn)包含其以后節(jié)點(diǎn)信息，如節(jié)點(diǎn)【1,2】x表內(nèi)容為：[2,2][3,2】y表

內(nèi)容為：[1,3]

選路方法：

節(jié)點(diǎn)路由時(shí)進(jìn)行查表：先查x表即進(jìn)行x方向路由，如果查表能指明下一跳方向則直

接進(jìn)入下一跳。如果不能則繼續(xù)查y表，直到到達(dá)目的地。

第四章對(duì)稱多處理機(jī)系統(tǒng)

4.1參照?qǐng)D4.20,試解釋為什么采用WT策略進(jìn)程從尸2遷移到勺時(shí)，或采用WB策略將包

含共享變量X的進(jìn)程從片遷移到P2時(shí)，會(huì)造成高速緩存的不一致。

處理器

高速緩存

總線

共享

存儲(chǔ)器

遷移之前寫通過寫回

圖4.20進(jìn)程遷移所造成的不一致性

答：采用WT策略進(jìn)程從尸2遷移到R后，P2寫共享變量X為X',并且更新主存數(shù)據(jù)為X',

此時(shí)6共享變量值仍然為X,與P2和主存X，不一致。采用WB策略進(jìn)程從4遷移到P2后,

P｝寫共享變量X為X，，但此時(shí)P2緩存與主存變量值仍然為X,造車不一致。

4.2參照?qǐng)D4.21所示，試解釋為什么：①在采用WT策略的高速緩存中，當(dāng)I/O處理器將一

個(gè)新的數(shù)據(jù)X?寫回主存時(shí)會(huì)造成高速緩存和主存間的不一致；②在采用WB策略的高速緩

存中，當(dāng)直接從主存輸出數(shù)據(jù)時(shí)會(huì)造成不一致。

處理器

P.p2P,p2p2

VVVV

高速緩存XXXJL

*

尼?欽i*

▼▼▼▼▼li

I/O處理機(jī)XX'￡X*

存儲(chǔ)器I/O存儲(chǔ)器（輸入）存儲(chǔ)器（輸出）

（寫直達(dá)）（寫回）

圖4.21繞過高速緩存的I/O操作所造成的不一致性

答：①中I/O處理器將數(shù)據(jù)X，寫回主存，因?yàn)楦咚倬彺娌捎肗T策略，此時(shí)P1和P2相應(yīng)的

高速緩存值還是X,所以造成高速緩存與主存不一致。②直接從主存輸出數(shù)據(jù)X,因?yàn)楦咚?/p>

緩存采用WB策略，可能高速緩存中的數(shù)據(jù)已經(jīng)被修改過，所以造成不一致。

4.3試解釋采用WB策略的寫更新和寫無效協(xié)議的一致性維護(hù)過程。其中X為更新前高速

緩存中的拷貝，X'為修改后的高速緩存塊，I為無效的高速緩存塊。

EZI高速緩存行共享存儲(chǔ)器R江］

（a）寫操作前（b）處理器P1執(zhí)行寫無效操作后（C）處理器片執(zhí)行寫更新操作后

答：處理器P1寫共享變量X為X"寫更新協(xié)議如圖⑹所示，同時(shí)更新其他核中存在高速

緩存拷貝的值為X，;寫無效協(xié)議如圖（b）所示，無效其他核中存在高速緩存拷貝，從而維護(hù)了

一致性過程。

4.4兩種基于總線的共享內(nèi)存多處理機(jī)分別實(shí)現(xiàn)了IllinoisMESI協(xié)議和Dragon協(xié)議，對(duì)于

下面給定的每個(gè)內(nèi)存存取序列，試比較在這兩種多處理機(jī)上的執(zhí)行代價(jià)，并就序列及一

致性協(xié)議的特點(diǎn)來說明為什么有這樣的性能差別。序列①rlwlrlwlr2w2r2w2r3

w3r3w3；序列②rlr2r3wlw2w3rlr2r3w3wl；序列③rlr2r3r3wlwlwl

wlw2w3；所有的存取操作都針對(duì)同一個(gè)內(nèi)存位置，r/w代表讀/寫，數(shù)字代表發(fā)出該操

作的處理器。假設(shè)所有高速緩存在開始時(shí)是空的，并且使用下面的性能模型：讀/寫高

速緩存命中，代價(jià)1個(gè)時(shí)鐘周期；缺失引起簡(jiǎn)單的總線事務(wù)（如BusUpgr,BusUpd）,60

個(gè)時(shí)鐘周期；缺失引起整個(gè)高速緩存塊傳輸，90時(shí)鐘周期。假設(shè)所有高速緩存是寫回式。

答：讀寫命中、總線事務(wù)、塊傳輸分別簡(jiǎn)記為H、B、ToMESI協(xié)議：①BTHHHHBTHBHH

HBTHBHIIII共5B+12H+3T=582時(shí)鐘周期②BTHBTHBTHBHBTHBTHBTHBTHHBIIBTH共

10B+12H+8T=1330時(shí)鐘周期③BTHBTHBTHHBHHHHBTHBTH共6B+10H+4T=730時(shí)鐘周期。

Dragon協(xié)議：①BTHHHHBTHBTHHBTHBTHBTHHBTH共7B+12H+7T=882時(shí)鐘周期②

BTHBTHBTHBTHBTHBTHHHHHBTTHBTH8B+12H+8T=1212時(shí)鐘周期③BTHBTHBTHH

BTHBTHBTHBTHBTHBTH共9B+10H+9T=1360時(shí)鐘周期。由結(jié)果得出，①、③序列用MESI

協(xié)議時(shí)間更少，而②序列用Dragon協(xié)議時(shí)間更少。綜上可知，如果同一塊在寫操作之后頻

繁被多個(gè)核讀操作采用Dragon協(xié)議更好一些,因?yàn)镈ragon協(xié)議寫操作后會(huì)更新其它核副本。

如果一個(gè)同多次連續(xù)對(duì)同一塊進(jìn)行寫操作MESI協(xié)議更有效，因?yàn)樗恍枰缕渌烁北荆?/p>

只需要總線事務(wù)無效其它核即可。

4.5考慮以下代碼段，說明在順序一致性模型下，可能的結(jié)果是什么？假設(shè)在代碼開始執(zhí)行

時(shí)，所有變量初始化為0。

a.

PlP2P3

A=1U=AV=B

B=1W=A

b.

PlP2P3P4

A=1U=AB=1W=B

V=BX=A

答：順序一致性模型性下，保護(hù)每個(gè)進(jìn)程都按程序序來發(fā)生內(nèi)存操作，這樣會(huì)有多種可能結(jié)

果，這里假設(shè)最簡(jiǎn)單情況，即P1、P2、P3依次進(jìn)行。則a中U=V=W=1,b中U=X=W=1,

V=0。

4.6參照461中討論多級(jí)高速緩存包含性的術(shù)語，假設(shè)L1和L2都是2-路組相聯(lián)，n2>ni,

bl=b2,且替換策略用FIFO來代替LRU,試問包含性是否還是自然滿足？如果替換策

略是隨機(jī)替換呢？

答：如果采用FIFO替換策略包含性自然滿足，因?yàn)長(zhǎng)1和L2都是2路組相聯(lián)，F(xiàn)IFO保證

了L1與L2在發(fā)生替換時(shí)會(huì)換出相同的緩存塊，維護(hù)了包含性。如果采取隨機(jī)替換策略，

存在L1與L2替換不是相同塊的情況，故不滿足包含性。

4.7針對(duì)以下高速緩存情況，試給出一個(gè)使得高速緩存的包含性不滿足的內(nèi)存存取序列？

L1高速緩存容量32字節(jié)，2-路組相聯(lián)，每個(gè)高速緩存塊8個(gè)字節(jié)，使用LRU替換算

法；L2高速緩存容量128字節(jié)，4-路組相聯(lián)，每個(gè)高速緩存塊8個(gè)字節(jié)，使用LRU替

換算法。

答：假設(shè)ml、m2、m3塊映射到一級(jí)Cache和二級(jí)Cache的同一組中，考慮如下內(nèi)存存取

序列Rm”Rm2,Rml.Rm3，由LRU替換算法知道，當(dāng)Rm3執(zhí)行后，L1中被替換出的是m2,

L2中被替換出的是ml,此時(shí)ml塊在L1卻不在L2中，不滿足包含性。

4.8在4.6中關(guān)于分事務(wù)總線的討論中，依賴于處理器與高速緩存的接口，下面情況有可能

發(fā)生：一個(gè)使無效請(qǐng)求緊跟在數(shù)據(jù)響應(yīng)之后，使得處理器還沒有真正存取這個(gè)高速緩存

塊之前，該高速緩存塊就被使無效了。為什么會(huì)發(fā)生這種情況，如何解決？

答：考慮如下情景：SMP目錄一致性協(xié)議中，核1讀缺失請(qǐng)求數(shù)據(jù)塊A,主存響應(yīng)請(qǐng)求傳

送數(shù)據(jù)塊A給核1,同時(shí)核2對(duì)數(shù)據(jù)塊A進(jìn)行寫操作，到主存中查得核1擁有副本，向核1

發(fā)使無效請(qǐng)求。如此，一個(gè)使無效請(qǐng)求緊跟在數(shù)據(jù)響應(yīng)之后。解決方法，可以使每個(gè)核真正

存取高速緩存塊后向主存發(fā)回應(yīng)，然后再允許其它對(duì)此塊操作的使無效或其它請(qǐng)求。

4.9利用LL-SC操作實(shí)現(xiàn)一個(gè)Test&Set操作。

答：Test&Set：11reg1,location/*Load-lockedthelocationtoregl*/

bnzregl,lock/*iflocatinwaslocked,tryagain*/

movreg2,1/*setreg21*/

sclocation,reg2/*storereg2conditionalintolocation*/

4.10在4.7.4部分描述具有感覺反轉(zhuǎn)的路障算法中，如果將Unlock語句不放在if條件語句

的每個(gè)分支中，而是緊接放在計(jì)數(shù)器增1語句后，會(huì)發(fā)生什么問題？為什么會(huì)發(fā)生這個(gè)

問題？

答：再進(jìn)入下一個(gè)路障時(shí)可能會(huì)發(fā)生計(jì)數(shù)器重新清0現(xiàn)象，導(dǎo)致無法越過路障?？紤]如

下情景：第一次進(jìn)入路障時(shí)，最后兩個(gè)進(jìn)入路障的進(jìn)程分別為1、2。假設(shè)最后進(jìn)入路障

的進(jìn)程為2進(jìn)程，2進(jìn)程執(zhí)行共享變量加一操作并解鎖。然后2進(jìn)程執(zhí)行一條if條件語

句，此時(shí)由于某種原因換出或睡眠，而此時(shí)共享變量的值已經(jīng)為p。如果1進(jìn)程此時(shí)正

執(zhí)行if條件語句，則清零計(jì)數(shù)器，設(shè)置標(biāo)志，其它進(jìn)程越過路障。到目前為止沒有出現(xiàn)

問題，問題出現(xiàn)在下一次進(jìn)入路障。進(jìn)程再一次進(jìn)入路障，此時(shí)會(huì)執(zhí)行共享變量加一操

作。如果此時(shí)2進(jìn)程被換入或被喚醒，會(huì)重新清零共享變量，使之前到達(dá)路障的進(jìn)程的

加一操作無效，導(dǎo)致無法越過路障。

第五章大規(guī)模并行處理機(jī)系統(tǒng)

5.1簡(jiǎn)述大規(guī)模并行處理機(jī)的定義，原理和優(yōu)點(diǎn)？

答：并行處理機(jī)有時(shí)也稱為陣列處理機(jī)，它使用按地址訪問的隨機(jī)存儲(chǔ)器，以單指令流多數(shù)

據(jù)流方式工作，主要用于要求大量高速進(jìn)行向量矩陣運(yùn)算的應(yīng)用領(lǐng)域。并行處理機(jī)的并行性

來源于資源重復(fù)，它把大量相同的處理單元（PE）通過互聯(lián)網(wǎng)絡(luò)（ICN）連接起來，在統(tǒng)一

的控制器（CU）控制下，對(duì)各自分配來的數(shù)據(jù)并行地完成同一條指令所規(guī)定的操作。PE是

不帶指令控制部件的算術(shù)邏輯運(yùn)算單元。并行處理機(jī)具有強(qiáng)大的向量運(yùn)算能力，具有向量化

功能的高級(jí)語言編譯程序有助于提高并行處理機(jī)的通用性，減少編譯時(shí)間。

5.2并行處理機(jī)有兩種基本結(jié)構(gòu)類型，請(qǐng)問是哪兩種？并作簡(jiǎn)單介紹。

答：采用分布存儲(chǔ)器的并行處理結(jié)構(gòu)和采用集中式共享存儲(chǔ)器的并行處理結(jié)構(gòu)。分布式存儲(chǔ)

器的并行處理結(jié)構(gòu)中，每一個(gè)處理機(jī)都有自己的存儲(chǔ)器，只要控制部件將并行處理的程序分

配至各處理機(jī)，它們便能并行處理，各自從自己的存儲(chǔ)器中取得信息。而共享存儲(chǔ)多處理機(jī)

結(jié)構(gòu)中的存儲(chǔ)器是集中共享的，由于多個(gè)處理機(jī)共享，在各處理機(jī)訪問共享存儲(chǔ)器時(shí)會(huì)發(fā)生

競(jìng)爭(zhēng)。因此，需采取措施盡可能避免競(jìng)爭(zhēng)的發(fā)生。

5.3簡(jiǎn)單說明多計(jì)算機(jī)系統(tǒng)和多處理機(jī)系統(tǒng)的區(qū)別。

答：他們雖然都屬于多機(jī)系統(tǒng)但是他們區(qū)別在于：（1）多處理機(jī)是多臺(tái)處理機(jī)組成的單機(jī)系

統(tǒng)，多計(jì)算機(jī)是多臺(tái)獨(dú)立的計(jì)算機(jī)。（2）多處理機(jī)中各處理機(jī)邏輯上受同一的OS控制，而

多計(jì)算機(jī)的OS邏輯上獨(dú)立.（3）多處理機(jī)間以單一數(shù)據(jù)，向量。數(shù)組和文件交互作用，多計(jì)

算機(jī)經(jīng)通道或者通信線路以數(shù)據(jù)傳輸?shù)姆绞竭M(jìn)行。（4）多處理機(jī)作業(yè)，任務(wù)，指令，數(shù)據(jù)各

級(jí)并行，多計(jì)算機(jī)多個(gè)作業(yè)并行。

5.4舉例說明MPP的應(yīng)用領(lǐng)域及其采用的關(guān)鍵技術(shù)。

答：全球氣候預(yù)報(bào)，基因工程，飛行動(dòng)力學(xué)，海洋環(huán)流，流體動(dòng)力學(xué)，超導(dǎo)建模，量子染色

動(dòng)力學(xué)，視覺。采用的關(guān)鍵技術(shù)有VLSI,可擴(kuò)張技術(shù)，共享虛擬存儲(chǔ)技術(shù)。

5.5多處理機(jī)的主要特點(diǎn)包括

答：

（1）結(jié)構(gòu)的靈活性。與SIMD計(jì)算機(jī)相比，多處理機(jī)的結(jié)構(gòu)具有較強(qiáng)的通用性，它可以同

時(shí)對(duì)多個(gè)數(shù)組或多個(gè)標(biāo)量數(shù)據(jù)進(jìn)行不同的處理，這要求多處理機(jī)能夠適應(yīng)更為多樣的算法，

具有靈活多變的系統(tǒng)結(jié)構(gòu)。2）程序并行性。并行處理機(jī)實(shí)現(xiàn)操作一級(jí)的并行，其并行性存

在于指令內(nèi)部，主要用來解決數(shù)組向量問題；而多處理機(jī)的并行性體現(xiàn)在指令外部，即表現(xiàn)

在多個(gè)任務(wù)之間。3）并行任務(wù)派生。多處理機(jī)是多指令流操作方式，一個(gè)程序中就存在多

個(gè)并發(fā)的程序段，需要專門的程序段來表示它們的并發(fā)關(guān)系以控制它們的并發(fā)執(zhí)行，這稱為

并行任務(wù)派生。

4）進(jìn)程同步。并行處理機(jī)實(shí)現(xiàn)操作級(jí)的并行，所有處于活動(dòng)狀態(tài)的處理單元受一個(gè)控制器

控制，同時(shí)執(zhí)行共同的指令，工作自然同步；而多處理機(jī)實(shí)現(xiàn)指令、任務(wù)、程序級(jí)的并行，

在同一時(shí)刻，不同的處理機(jī)執(zhí)行著不同的指令，進(jìn)程之間的數(shù)據(jù)相關(guān)和控制依賴決定了要采

取一定的進(jìn)程同步策略.

5.6在并行多處理機(jī)系統(tǒng)中的私有Cache會(huì)引起Cache中的內(nèi)容相互之間以及與共享存儲(chǔ)器

之間互不相同的問題，即多處理機(jī)的Cache一致性問題。請(qǐng)問有哪些原因?qū)е逻@個(gè)問題？

答：

1）出現(xiàn)Cache一致性問題的原因主要有三個(gè)：共享可寫的數(shù)據(jù)、進(jìn)程遷移、I/O傳輸。共

享可寫數(shù)據(jù)引起的不一致性。比如Pl、P2兩臺(tái)處理機(jī)各自的本地高速緩沖存儲(chǔ)器Cl、C2

中都有共享存儲(chǔ)器是M中某個(gè)數(shù)據(jù)X的拷貝，當(dāng)P1把X的值變成X/后，如果P1采用寫

通過策略，內(nèi)存中的數(shù)據(jù)也變?yōu)閄/,C2中還是X。如果通過寫回策略，這是內(nèi)存中還是X。

在這兩種情況下都會(huì)發(fā)生數(shù)據(jù)不一致性。2）進(jìn)程遷移引起的數(shù)據(jù)不一致性。P1中有共享

數(shù)據(jù)X的拷貝，某時(shí)刻P1進(jìn)程把它修改為X，并采用了寫回策略，由于某種原因進(jìn)程從P1

遷移到了P2上，它讀取數(shù)據(jù)時(shí)得到X,而這個(gè)X是“過時(shí)”的。3）I/O傳輸所造成的數(shù)據(jù)

不一致性。假設(shè)P1和P2的本地緩存Cl、C2中都有某數(shù)據(jù)X的拷貝，當(dāng)1/0處理機(jī)將一個(gè)

新的數(shù)據(jù)X/寫入內(nèi)存時(shí)，就導(dǎo)致了內(nèi)存和Cache之間的數(shù)據(jù)不一致性。

5.7分別確定在下列兩種計(jì)算機(jī)系統(tǒng)中，計(jì)算表達(dá)式所需的時(shí)間：s=Al*Bl+A2*B2+…A4*B4。

a）有4個(gè)處理器的SIMD系統(tǒng)；b）有4個(gè)處理機(jī)的MIMD系統(tǒng)。假設(shè)訪存取指和取數(shù)的時(shí)間

可以忽略不計(jì)；加法與乘法分別需要2拍和4拍；在SIMD和MIMD系統(tǒng)中處理器（機(jī)）之間

每進(jìn)行一次數(shù)據(jù)傳送的時(shí)間為1拍；在SIMD系統(tǒng)中，PE之間采用線性環(huán)形互連拓?fù)洌疵?/p>

個(gè)PE與其左右兩個(gè)相鄰的PE直接相連，而在MIMD中每個(gè)PE都可以和其它PE有直接的的

通路。

答：假設(shè)4個(gè)PE分別為PEO,PEI,PE2,PE3o利用SIMD計(jì)算機(jī)計(jì)算上述表達(dá)式，4個(gè)

乘法可以同時(shí)進(jìn)行，用時(shí)=4個(gè)時(shí)間單位；然后進(jìn)行PE0到PEI,PE2到PE3的數(shù)據(jù)傳送，

用時(shí)=1個(gè)時(shí)間單位。在PE1和PE3中形成部分和，用時(shí)=2個(gè)時(shí)間單位。接著進(jìn)行PE1到

PE3的部分和傳送，用時(shí)?=1*2=2個(gè)時(shí)間單位。最后，在PE3中形成最終結(jié)果，用時(shí)=2個(gè)時(shí)

間單位。因此，利用SIMD計(jì)算機(jī)計(jì)算上述表達(dá)式總共用時(shí)=4（乘法）+1（傳送）+2（加

法）+2（傳送）+2（加法）=11個(gè)時(shí)間單位。而利用MIMD計(jì)算機(jī)計(jì)算上述表達(dá)式，除了

在第二次傳送節(jié)省1個(gè)時(shí)間單位以外，其他與SIMD相同。因此用時(shí)=4（乘法）+1（傳送）

+2(加法)+1(傳送)+2(加法)=10個(gè)時(shí)間單位。

5.8假定有一個(gè)處理機(jī)臺(tái)數(shù)為p的共享存儲(chǔ)器多處理機(jī)系統(tǒng)。設(shè)m為典型處理機(jī)每條執(zhí)行執(zhí)

行時(shí)間對(duì)全局存儲(chǔ)器進(jìn)行訪問的平均次數(shù)。

設(shè)t為共享存儲(chǔ)器的平均存儲(chǔ)時(shí)間，x為使用本地存儲(chǔ)器的單處理機(jī)MIPS速率，再假

定在多處理機(jī)上執(zhí)行n條指令。

現(xiàn)在假設(shè)p=32,m=0.4,t=lus,要讓多處理機(jī)的有效性能達(dá)到56MIPS,需要每臺(tái)處理機(jī)

的MIPS效率是多少？

A.2

B.4

C.5.83

D.40

答：B

5.9試在含一個(gè)PE的SISD機(jī)和在含n個(gè)PE且連接成一線性環(huán)的SIMD機(jī)上計(jì)算下列求內(nèi)積

的表達(dá)式：其中n=2-

s=￡4?Bi

i=l

假設(shè)完成每次ADD操作需要2個(gè)單元時(shí)間，完成每次MULTIPLY操作需要4個(gè)單位時(shí)間，

沿雙向環(huán)在相鄰PE間移數(shù)需1個(gè)單位時(shí)間

(1)SISD計(jì)算機(jī)上計(jì)算s需要多少時(shí)間

(2)SIMD計(jì)算機(jī)上計(jì)算s需要多少時(shí)間

(3)SIMD機(jī)計(jì)算s相對(duì)于SISD計(jì)算的加速比是多少？

答：

(1)4n+2(nT)

(2)4+2k+n—1

(3)4"+2(〃-1)

3+2k+n

5.10如果一臺(tái)SIMD計(jì)算機(jī)和一臺(tái)流水線處理機(jī)具有相同的計(jì)算性能，對(duì)構(gòu)成它們的主要部

件分別有什么要求？

答：一臺(tái)具有n個(gè)處理單元的SIMD計(jì)算機(jī)與一臺(tái)具有一條n級(jí)流水線并且時(shí)鐘周期為前者

1/n的流水線處理機(jī)的計(jì)算性能相當(dāng)，兩者均是每個(gè)時(shí)鐘周

期產(chǎn)生n個(gè)計(jì)算結(jié)果。但是，SIMD計(jì)算機(jī)需要n倍的硬件(n個(gè)處理單元)，而流水線處理

機(jī)中流水線部件的時(shí)鐘速率要求比前者快n倍，同時(shí)還需要存儲(chǔ)器的帶寬也是前者的n倍。

第六章機(jī)群系統(tǒng)

6.1試區(qū)分和例示下列關(guān)于機(jī)群的術(shù)語：

1)專用機(jī)群和非專用機(jī)群；

2)同構(gòu)機(jī)群和異構(gòu)機(jī)群；

3)專用型機(jī)群和企業(yè)型機(jī)群。

答：

1)根據(jù)節(jié)點(diǎn)的擁有情況，分為專用機(jī)群和非專用機(jī)群，在專用機(jī)群中所有的資源是共享的，

并行應(yīng)用可以在整個(gè)機(jī)群上運(yùn)行，而在非專用機(jī)群中，全局應(yīng)用通過竊取CPU時(shí)間獲

得運(yùn)行，非專用機(jī)群中由于存在本地用戶和遠(yuǎn)地用戶對(duì)處理器的競(jìng)爭(zhēng)，帶來了進(jìn)程遷移

和負(fù)載平衡問題。

2）根據(jù)節(jié)點(diǎn)的配置分為同構(gòu)機(jī)群和異構(gòu)機(jī)群，同構(gòu)機(jī)群中各節(jié)點(diǎn)有相似的的體系，并且使

用相同的操作系統(tǒng)，而異構(gòu)機(jī)群中節(jié)點(diǎn)可以有不同的體系，運(yùn)行的操作系統(tǒng)也可以不同。

3）專用型機(jī)群的特點(diǎn)是緊耦合的、同構(gòu)的，通過一個(gè)前端系統(tǒng)進(jìn)行集中式管理，常用來代

替?zhèn)鹘y(tǒng)的大型超級(jí)計(jì)算機(jī)系統(tǒng)；而企業(yè)型機(jī)群是松耦合的，一般由異構(gòu)節(jié)點(diǎn)構(gòu)成，節(jié)點(diǎn)

可以有多個(gè)屬主，機(jī)群管理者對(duì)節(jié)點(diǎn)有有限的管理權(quán)。

6.2試解釋和例示一下有關(guān)單一系統(tǒng)映像的術(shù)語：

I）單一文件層次結(jié)構(gòu)；

2）單一控制點(diǎn)：

3）單一存儲(chǔ)空間；

4）單一進(jìn)程空間：

5）單一輸入/輸出和網(wǎng)絡(luò)。

答：

1）用戶進(jìn)入系統(tǒng)后所見的文件系統(tǒng)是一個(gè)單一的文件和目錄層次結(jié)構(gòu)，該系統(tǒng)透明的將本

地磁盤、全局磁盤和其他文件設(shè)備結(jié)合起來。

2）整個(gè)機(jī)群可以從一個(gè)單一的節(jié)點(diǎn)對(duì)整個(gè)機(jī)群或某一單一的節(jié)點(diǎn)進(jìn)行管理和控制。

3）將機(jī)群中分布于各個(gè)節(jié)點(diǎn)的本地存儲(chǔ)器實(shí)現(xiàn)為一個(gè)大的、集中式的存儲(chǔ)器。

4）所有的用戶進(jìn)程，不管它們駐留在哪個(gè)節(jié)點(diǎn)上，都屬于一個(gè)單一的進(jìn)程空間，并且共享

一個(gè)統(tǒng)一的進(jìn)程識(shí)別方案。

5）單一輸入/輸出意味著任何節(jié)點(diǎn)均可訪問多個(gè)外設(shè)。單一網(wǎng)絡(luò)是任一節(jié)點(diǎn)能訪問機(jī)群中

的任一網(wǎng)絡(luò)連接。

6.3就SolarisMC系統(tǒng)回答下列問題：

I）SolarisMC支持習(xí)題6.2中單一系統(tǒng)映像的哪些特征？不支持哪些特征？

2）對(duì)那些SolarisMC支持的特征，解釋一下SolarisMC是如何解決的。

答：

1）支持單一文件層次結(jié)構(gòu)、單一進(jìn)程空間、單一網(wǎng)絡(luò)和單一I/O空間。不支持單一控制點(diǎn)

和單一的存儲(chǔ)空間。

2）Solaris使用了一個(gè)叫PXFS的全局文件系統(tǒng)GFS。PXFS文件系統(tǒng)的主要特點(diǎn)包括：?jiǎn)?/p>

一系統(tǒng)映像、一致的語義及高性能。PXFS通過在VFS/vnode接口上截取文件訪問操作

實(shí)現(xiàn)單一系統(tǒng)映像，保證了單一文件層次結(jié)構(gòu)。

SolarisMC提供了一個(gè)全局進(jìn)程標(biāo)示符pid可定位系統(tǒng)所有進(jìn)程，一個(gè)進(jìn)程可以遷移到

其他節(jié)點(diǎn)，但它的宿主節(jié)點(diǎn)中總記錄有進(jìn)程的當(dāng)前位置，它通過在Solaris核心層上面增

加一個(gè)全局進(jìn)程以實(shí)現(xiàn)單一進(jìn)程空間，每個(gè)節(jié)點(diǎn)有一個(gè)節(jié)點(diǎn)管理程序，每個(gè)本地進(jìn)程有

一個(gè)虛擬進(jìn)程對(duì)象vproc,vproc保留每個(gè)父進(jìn)程和子進(jìn)程的信息，實(shí)現(xiàn)了全局進(jìn)程的管

理。

單一網(wǎng)絡(luò)和I/O空間通過一致設(shè)備命名技術(shù)和單一網(wǎng)絡(luò)技術(shù)實(shí)現(xiàn)。

6.4舉例解釋并比較以下有關(guān)機(jī)群作業(yè)管理系統(tǒng)的術(shù)語:

1）串行作業(yè)與并行作業(yè)；

2）批處理作業(yè)與交互式作業(yè)；

3）機(jī)群作業(yè)和外來作業(yè)；

4）專用模式、空間共享模式、時(shí)間共享模式：

5）獨(dú)立調(diào)度與組調(diào)度。

答：

1）串行作業(yè)在單節(jié)點(diǎn)上運(yùn)行，并行作業(yè)使用多個(gè)節(jié)點(diǎn)。

2）批處理作業(yè)通常需要較多的資源，如大量的內(nèi)存和較長(zhǎng)的CPU時(shí)間，但不需要迅速的

反應(yīng)；交互式作業(yè)要求較快的周轉(zhuǎn)時(shí)間，其輸入輸出直接指向終端設(shè)備，這些工作一般

不需要大量資源，用戶期望它們迅速得到執(zhí)行而不必放入隊(duì)列中。

3）機(jī)群作業(yè)時(shí)通過使用JMS功能分布實(shí)現(xiàn)的用戶作業(yè)，用戶服務(wù)器位于任一主機(jī)節(jié)點(diǎn)，資

源管理器跨越所有的機(jī)群節(jié)點(diǎn)。外來作業(yè)在JMS之外生成的，如NOW上的一個(gè)工作站

擁有者啟動(dòng)的外部作業(yè)，它不提交給JMS。

4）專用模式：任一時(shí)候只有一個(gè)作業(yè)在機(jī)群上運(yùn)行，任一時(shí)候也只有一個(gè)作業(yè)進(jìn)程分配給

一個(gè)節(jié)點(diǎn)。空間共享模式：多個(gè)作業(yè)可以在不重疊的節(jié)點(diǎn)區(qū)域上運(yùn)行。時(shí)間共享模式：

在專用模式和空間共享模式下，只有一個(gè)用戶進(jìn)程分配給一個(gè)節(jié)點(diǎn)，但是所有的系統(tǒng)進(jìn)

程或監(jiān)護(hù)程序仍在同一個(gè)節(jié)點(diǎn)上運(yùn)行。

5）獨(dú)立調(diào)度：各節(jié)點(diǎn)OS進(jìn)行自己的調(diào)度，但這會(huì)顯著損壞并行作業(yè)的性能，因?yàn)椴⑿凶?/p>

業(yè)的進(jìn)程間需要交互。組調(diào)度：將并行作業(yè)的所有進(jìn)程一起調(diào)度。一個(gè)進(jìn)程激活時(shí)，所

有進(jìn)程都被激活。

6.5針對(duì)LSF回答下列問題：

1）對(duì)LSF的四種作業(yè)類型各舉一個(gè)例子；

2）舉一個(gè)例子說明外來作業(yè)；

3）對(duì)一個(gè)有1000個(gè)服務(wù)器的機(jī)群，為什么LSF負(fù)載分配機(jī)制優(yōu)于：1整個(gè)機(jī)群只有一個(gè)

L1M或者2所有LIM都是主機(jī)？說明原因。

答：

1）交互式：用戶使用Ishosts命令就可以列出每個(gè)服務(wù)器節(jié)點(diǎn)的靜態(tài)資源，實(shí)現(xiàn)交互。批處

理：Isbatch實(shí)用程序允許通過LSF提交、監(jiān)控和執(zhí)行批處理作業(yè)。串行：用戶一旦進(jìn)入

Istcshshell,發(fā)送的每條命令自動(dòng)在最適合的節(jié)點(diǎn)上執(zhí)行。并行：Ismake實(shí)用程序是UNIX

make實(shí)用程序時(shí)一個(gè)并行版本，允許在多個(gè)節(jié)點(diǎn)同時(shí)處理一個(gè)Makefile0

2）不通過LSF執(zhí)行的稱為外來作業(yè)。例如執(zhí)行一些本地作業(yè)：字處理，web網(wǎng)絡(luò)瀏覽等。

3）機(jī)群的服務(wù)器數(shù)目太多，如果只采用一個(gè)LIM會(huì)導(dǎo)致LIM的負(fù)責(zé)過重，不能及時(shí)的處

理響應(yīng)所有服務(wù)器的請(qǐng)求和分派所有機(jī)群作業(yè);如果采用2會(huì)導(dǎo)致LIM之間相互交換負(fù)

載信息過多，導(dǎo)致網(wǎng)絡(luò)通信量過大。

6.6為什么在分布式文件系統(tǒng)中，UNIX語義難以實(shí)現(xiàn)？有哪些放松的文件共享語義？采用

放松的文件共享語義會(huì)有一些什么缺點(diǎn)？

答：

在UNIX語義中，一個(gè)修改過的塊應(yīng)該立刻被所有其他應(yīng)用程序見到。然而分布式的文件系

統(tǒng)中，多個(gè)節(jié)點(diǎn)可能存放了同一文件塊的拷貝，當(dāng)其中一個(gè)節(jié)點(diǎn)修改文件可的拷貝時(shí).，其他

節(jié)點(diǎn)不能立刻就知道，這就使得UNIX語義難以實(shí)現(xiàn)。放松的文件共享語義有：對(duì)話語義、

類事物語義、不可改變的共享文件語義等。采用放松的文件共享語義要求應(yīng)用程序員修改程

序代碼，以適用這種新的語義，這就增加了程序員的負(fù)擔(dān)。

6.7試解釋在機(jī)群并行文件系統(tǒng)中，為什么采用軟件RAID、高速緩存機(jī)制和預(yù)取能夠提高

文件系統(tǒng)性能。

答：

軟件RAID是文件系統(tǒng)負(fù)責(zé)分布數(shù)據(jù)和維護(hù)容錯(cuò)級(jí)別，能夠和RA1D5有一樣的性能，實(shí)現(xiàn)

機(jī)群磁盤間的數(shù)據(jù)分布，提高了I/O系統(tǒng)的傳輸帶寬。高速緩存是將應(yīng)用程序要取的塊放在

CACHE中，根據(jù)局部性原理，應(yīng)用程序可以基本上從CACHE中讀取數(shù)據(jù)塊，而不要通過

讀取內(nèi)存或硬盤，提高了讀取速度。預(yù)取是在真正讀取數(shù)據(jù)塊之前就將這些數(shù)據(jù)塊讀入內(nèi)存,

這也提高了I/O性能，改善了文件系統(tǒng)性能。

6.8討論并行文件系統(tǒng)協(xié)作化高速緩存的基本技術(shù)前提是什么？這個(gè)前提有什么意義？

答：

基本技術(shù)前提是互聯(lián)網(wǎng)絡(luò)的速度很快，一個(gè)節(jié)點(diǎn)需要的文件塊在其他節(jié)點(diǎn)的緩存中，那么就

不需要從磁盤讀，而是直接從其他節(jié)點(diǎn)的緩存中讀出。這個(gè)前提的意義是可以提高系統(tǒng)的性

能，使得節(jié)點(diǎn)間的協(xié)作化緩存變得更有意義。

6.9回答以下關(guān)于BerkeleyNOW項(xiàng)目的問題：

1）BerkeleyNOW項(xiàng)目支持單一系統(tǒng)映像的哪幾個(gè)方面？即單入口點(diǎn)、單文件層次結(jié)構(gòu)、單

控制點(diǎn)、單存儲(chǔ)空間、單進(jìn)程空間哪個(gè)的哪幾項(xiàng)？并解釋如何支持。

2）解釋BerkeleyNOW項(xiàng)目用來提高性能的四個(gè)結(jié)構(gòu)特征。

3）解釋BerkeleyNOW項(xiàng)目和SP機(jī)群四個(gè)體系結(jié)構(gòu)的差異，并討論各自的優(yōu)點(diǎn)。

答：

1）通過用戶級(jí)整個(gè)機(jī)群軟件GLUNIX,提供單一系統(tǒng)映像。開發(fā)了一種新的無服務(wù)器網(wǎng)絡(luò)

文件系統(tǒng)xFS,以支持單一文件層次結(jié)構(gòu)。

2）主動(dòng)消息通信協(xié)議，支持有效的通信；機(jī)群軟件GLUNIX提供單一的系統(tǒng)映像、資源管

理和可用性；xFS支持可擴(kuò)放性和單一文件層次結(jié)構(gòu)的高可用性；軟件框架WebOS構(gòu)

筑高可用性、漸增可擴(kuò)放性。

3）SP機(jī)群的體系結(jié)構(gòu)特征：每個(gè)節(jié)點(diǎn)都是RS/600工作站，并有自己的局部磁盤；每個(gè)節(jié)

點(diǎn)內(nèi)駐留一個(gè)完整的AIX；各節(jié)點(diǎn)通過其I/O總線連接到專門設(shè)計(jì)的多級(jí)高速網(wǎng)絡(luò)；盡

量使用標(biāo)準(zhǔn)工作站部件。這樣的優(yōu)點(diǎn)是簡(jiǎn)單性和靈活性。

6.10考慮xFS,并回答下列問題：

1）解釋xFS和集中式文件服務(wù)器的兩個(gè)不同點(diǎn)，并討論各自的優(yōu)點(diǎn)；

2）解釋xFS用來提高可用性的主要技術(shù)；

3）解釋xFS用來減輕小一寫問題的主要技術(shù)。

答：

1）無服務(wù)器文件系統(tǒng)xFS將文件服務(wù)的功能分布到機(jī)器的所有節(jié)點(diǎn)上，xFS中所有的服務(wù)

器和客戶的功能由分散的所有節(jié)點(diǎn)實(shí)現(xiàn)之。這與集中文件服務(wù)器的中央存儲(chǔ)、中央緩存、

中央管理不同。xFS的優(yōu)點(diǎn)是采用分布式管理和協(xié)同文件緩存以及冗余磁盤陣列，這提

高了系統(tǒng)的可用性以及I/O的性能和吞吐量。集中式文件服務(wù)器會(huì)減少緩存的不一致性,

管理簡(jiǎn)單。

2）xFS提高可用性的主要技術(shù)是采用廉價(jià)冗余磁盤陣列RAID。無工作站文件系統(tǒng)能用來

生成軟件RAID,以提高性能和高可用性?，F(xiàn)在xFS使用單奇偶校驗(yàn)磁盤條。一個(gè)文件

數(shù)據(jù)塊在多個(gè)存儲(chǔ)服務(wù)器節(jié)點(diǎn)上按條劃分，在另一個(gè)節(jié)點(diǎn)上有奇偶校驗(yàn)塊。如果一個(gè)節(jié)

點(diǎn)失效，失效磁盤的內(nèi)容，可利用其余盤和奇偶盤之異或操作重建之。

3）xFS使用日志條的方法解決小一寫問題：每個(gè)用戶首先將寫接合到各用戶的日志上；然

后此日志采用日志段提交給磁盤，每個(gè)段系由K-1個(gè)日志片組成，它與奇偶校驗(yàn)片以道

送給K個(gè)存儲(chǔ)服務(wù)器。

第七章分布式共享存儲(chǔ)系統(tǒng)

7.1什么是分布式共享存儲(chǔ)系統(tǒng)，它相對(duì)于共享存儲(chǔ)系統(tǒng)與分布式系統(tǒng)有哪些優(yōu)點(diǎn)？

答：分布式共享存儲(chǔ)系統(tǒng)，是把共享存儲(chǔ)器分成許多模塊并分布于各處理機(jī)之中。分布式系

統(tǒng)中采用消息傳遞通信，性能提高了，但多地址空間不利于程序員編程。共享存儲(chǔ)系統(tǒng)支持

傳統(tǒng)的單地址空間，但共享必然引起沖突，形成瓶頸，于是分布式共享存儲(chǔ)系統(tǒng)結(jié)合兩者的

優(yōu)點(diǎn)。

7.2釋放一致性模型(RC)把處理器一致性(PC)和弱一致性模型(WC)的優(yōu)點(diǎn)結(jié)合在一起了。

試回答下面有關(guān)這些一致性模型的問題：

a)比較這三種一致性模型的實(shí)現(xiàn)要求。

b)評(píng)論每種一致性模型的優(yōu)缺點(diǎn)。

答：a)處理器一致性要求：①在任一取數(shù)操作LOAD允許被執(zhí)行之前，所有在同一處理器中

先于這一LOAD的取數(shù)操作都已完成；②在任一存數(shù)操作STORE允許執(zhí)行之前，所有在同一

處理器中先于這一STORE的訪存操作(包括取數(shù)操作和存數(shù)操作)都己完成。弱一致性模

型要求：①同步操作的執(zhí)行滿足順序一致性條件：②在任一普通訪存操作允許被執(zhí)行之前，

所有在同一處理器中先于這一訪存操作的同步操作都已完成;③在任一同步操作允許被執(zhí)行

之前，所有在同一處理器中先于這一同步操作的普通訪存操作都已完成。釋放一致性模型要

求：①在任一普通訪存操作允許被執(zhí)行之前，所有在同一處理器中先于這一訪存操作的獲取

操作acquire都已完成；②在任一釋放操作release允許被執(zhí)行之前，所有在同一處理器中先于

這一release的普通訪存操作都已完成；③同步操作的執(zhí)行滿足順序一致性條件。

b)三種模型對(duì)存儲(chǔ)順序要求逐漸降低，可優(yōu)化程度逐漸增加，但是對(duì)程序員的要求也越

來越高，所以釋放性一致性是性能與復(fù)雜度的折中。

7.3在DSM系統(tǒng)的順序一致性存儲(chǔ)模型下，有三個(gè)并行執(zhí)行的進(jìn)程如下所示，試問001110

是不是一個(gè)合法的輸出？并加以解釋。

PlP2P3

A=l;B=l;C=l;

Print(b,c);Print(a,c);Print(a,b);

答：不是一個(gè)合法輸出?？紤]順序一致性存儲(chǔ)模型，每個(gè)進(jìn)程的程序序會(huì)被維護(hù)，那么無論

哪個(gè)進(jìn)程最后執(zhí)行Print語句，則之前的A=l,B=1,C=1都已經(jīng)完成，所以輸出的兩后兩項(xiàng)

必為11,所以001110不是合法輸出。

7.4試分類下面來自三個(gè)處理器的引用流的高速緩存缺失。假設(shè)每一個(gè)處理器的高速緩存只

有一個(gè)4個(gè)字的高速緩存行，字W0到W3、W4到W7分別處于同一個(gè)高速緩存行。

如果一行有多個(gè)引用，我們假設(shè)P1在P2之前發(fā)射、P2在P3之前發(fā)射內(nèi)存引用，符號(hào)

LD/STWi表示LOAD/STORE字i。

操作序號(hào)P1P2P3

1STW0STW7

2LDW6LDW2

3LDW7

4LDW2LDWO

5STW2

6LDW2

7STW2LDW5LDW5

8STW5

9LDW3LDW7

10LDW6LDW2

11LDW2STW7

12LDW7

13LDW2

14LDW5

15LDW2

答：操作序號(hào)3、6、8、12-15都是單操作。操作序號(hào)1、2、9-11為無關(guān)存儲(chǔ)操作，由于不

在同一塊中。操作序號(hào)4、7為對(duì)同一緩存塊的連續(xù)兩次LD,需要按序進(jìn)行。

7.5假設(shè)系統(tǒng)中共有512個(gè)處理器和1GB主存，每個(gè)節(jié)點(diǎn)內(nèi)有8個(gè)處理器對(duì)目錄可見，一個(gè)

高速緩存行的大小為64字節(jié)，那么在(a)滿位向量方案和(b)DnB(i=3)模型下目錄的存儲(chǔ)成

本各是多少？

答：分別為總?cè)萘康?2.%和5.47%。

7.6細(xì)數(shù)一下中心目錄與分布式目錄方案的實(shí)現(xiàn)方法與各自的使用情況。

答：中心目錄是用一個(gè)中心目錄存放所有高速緩存目錄的拷貝，中心目錄能提供為保證一致

性所需要的全部信息。因此，其容量非常大且必須采用聯(lián)想方法進(jìn)行檢索，這和單個(gè)高速緩

存的目錄類似。大型多處理機(jī)系統(tǒng)采用中心目錄會(huì)有沖突和檢索時(shí)間過長(zhǎng)兩個(gè)跳點(diǎn)。

分布式目錄方案是由Censier和Feautrier提出來。在分布式目錄中每個(gè)存儲(chǔ)器模塊維護(hù)

各自的目錄，目錄中記錄著每個(gè)存儲(chǔ)器塊的狀態(tài)和當(dāng)前的信息，其中狀態(tài)信息是本地的，而

當(dāng)前信息指明哪些高速緩存中有該存儲(chǔ)器塊的拷貝。

一般來說，在共享存儲(chǔ)上實(shí)現(xiàn)中心目錄，而在分布式系統(tǒng)上實(shí)現(xiàn)分布式目錄方案更為合

適一些，但這也并不是絕對(duì)的。

7.7在研究DS