1.指導思想

要求學生理解高端并行計算機系統設計技術，高端MPP、

DSM、CLUSTER等大規模并行計算機的關鍵設計理論和實現技

術，包括互連網絡技術、存儲架構和高可用技術等。為此，必須

用適量的作業、習題，啟發學生獨立思考以及熟練掌握一些基礎

知識和基本技能。

習題設計

計劃

2.作業安排

本教材每一章都附有大量的習題，根據教學進度和學時，合

理選擇書上習題，以達到進一步加深理解課堂講授的內容。每一

章講授結束，收一次作業，給出成績，并作一次集體答疑，講解

作業中的共性問題。作業成績記入總成績內。

第一章緒論

1.1什么是并行計算機？

答：簡單地講，并行計算機就是由多個處理單元組成的計算機系統，這些處理單元相互通信

和協作，能快速高效求解大型的復雜的問題。

1.2簡述Flynn分類法：

答：根據指令流和數據流的多重性將計算機分為：

1）單指令單數據流SISD

2）單指令多數據流SIMD

3）多指令單數據流MISD

4）多指令多數據流MIMD

1.3簡述當代的并行機系統

答：當代并行機系統主要有：

1）并行向量機（PVP）

2）對稱多處理機（SMP）

3）大規模并行處理機（MPP）

4）分布式共享存儲（DSM）處理機

5）工作站機群（COW）

1.4為什么需要并行計算機？

答：1）加快計算速度

2）提高計算精度

3）滿足快速時效要求

4）進行無法替代的模擬計算

1.5簡述處理器并行度的發展趨勢

答：1）位級并行

2）指令級并行

3）線程級并行

1.6簡述SIMD陣列機的特點

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

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

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

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

1.7簡述多計算機系統的演變

答：分為三個階段：

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

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

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

1.8簡述并行計算機的訪存模型

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

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

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

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

1.9簡述均勻存儲訪問模型的特點

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

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

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

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

1.10簡述非均勻存儲訪問模型的特點

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

了全局的地址空間。

2)處理器訪問存儲器的時間不一樣。

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

第二章性能評測

2.1使用40MHz主頻的標量處理器執行一個典型測試程序，其所執行的指令數及所需的周

期數如表2.13所示。試計算執行該程序的有效CPI、MIPS速率及總的CPU執行時間。

解：CPI=totalcycles/totalinstructions

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

=1.55

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

CPU執行時間=totalcycles/時鐘頻率=0.00375s

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

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

①在單處理機上執行該程序的平均CPI。

②由①所得結果，計算相應的MIPS速率。

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

=2.12

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

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

①漸近帶寬r~=?

②半峰值信息長度飛=?[提示：546us]

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

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

2.4并行機性能評測的意義。

答：意義有：

1）發揮并行機長處，提高并行機的使用效率。

2）減少用戶購機盲目性，降低投資風險。

3）改進系統結構設計，提高機器的性能。

4）促進軟/硬件結合，合理功能劃分。

5）優化“結構-算法-應用”的最佳組合。

6）提供客觀、公正的評價并行機的標準。

2.5如何進行并行機性能評測

答：1）機器級性能評測：CPU和存儲器的某些基本性能指標；并行和通信開銷分析；并行

機的可用性與好用性以及機器成本、價格與性/價比。

2）算法級性能評測：加速比、效率、擴展性。

3）程序級性能評測：Benchmark。

2.6簡述Gustafson定律的出發點

答：1）對于很多大型計算，精度要求很高，即在此類應用中精度是個關鍵因素，而計算時

間是固定不變的。此時為了提高精度，必須加大計算量，相應地亦必須增多處理器數才能維

持時間不變。

2）除非學術研究，在實際應用中沒有必要固定工作負載而計算程序運行在不同數目的

處理器上，增多處理器必須相應地增大問題規模才有實際意義。

2.7已知一程序可并行代碼占比例為80%,將其在有10個處理器的系統中運行，求其加速

比？并求其極限加速比？并分析其結構帶來的影響

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

極限加速比，即處理器個數無窮大的時候呈現的加速比=1/20%=5。

這個極限加速比，換個角度說是，Amdahl定律在很長一段時間影響了人們對開發并行

計算機的信心，對于本例，因為就算你把處理器做到無窮也只能得到5倍的加速比，同時有

一點更明顯，就是處理器數目增加到一定程度后，加速比的增長非常緩慢。

2.8簡述影響加速的因素

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

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

3）加大的處理器數超過的算法的并發程度。

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

答：1）較大的問題規模可提高較大的并發度。

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

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

2.10進行可擴放行研究的主要意義

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

的處理器。

2）對于運行于某種體系結構的并行機的某種算法當移到大規模處理機上的性能。

3）對于某類固定規模的問題，確定在某類并行機上的最優處理器數目和最大的加速比。

4）用于指導改進并行算法和并行體系結構，以使并行算法能盡可能充分利用可擴充的。

大量的處理器。

第三章互連網絡

3.1對于一顆K級二叉樹（根為0級，葉為k-1級），共有N=2”-l個節點，當推廣至m-

元樹時（即每個非葉節點有m個子節點）時，試寫出總節點數N的表達式。

答:

推廣至M元樹時，k級M元樹總結點數N的表達式為：

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

3.2二元胖樹如圖3.46所示，此時所有非根節點均有2個父節點。如果將圖中的每個橢圓均

視為單個節點，并且成對節點間的多條邊視為一條邊，則他實際上就是一個二叉樹。試問：

如果不管橢圓，只把小方塊視為節點，則他從葉到根形成什么樣的多級互聯網絡？

答：8輸入的完全混洗三級互聯網絡。

3.3四元胖樹如圖3.47所示，試問：每個內節點有幾個子節點和幾個父節點？你知道那個機

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

答：每個內節點有4個子節點，2個父節點。CM-5使用了此類胖樹結構。

3.4試構造一個N=64的立方環網絡，并將其直徑和節點度與N=64的超立方比較之，你的

結論是什么？

答：AN=64的立方環網絡，為4立方環(將4維超立方每個頂點以4面體替代得到)，直徑

d=9,節點度n=4

BN=64的超立方網絡，為六維超立方(將一個立方體分為8個小立方，以每個小立

方作為簡單立方體的節點，互聯成6維超立方)，直徑d=6,節點度n=6

3.5一個N=2八k個節點的deBruijin網絡如圖3.48所示，令如〃-。一…“％,是一個

節點的二進制表示，則該節點可達如下兩個節點：830,出3、…8必1。

試問：該網絡的直徑和對剖寬度是多少？

答：N=24個節點的deBruijin網絡直徑d=k對剖寬帶w=2%k-l)

3.6一個N=2八n個節點的洗牌交換網絡如圖3.49所示?試問：此網絡節點度==?網絡直徑

==?網絡對剖寬度==?

答：N=2〃n個節點的洗牌交換網絡，網絡節點度為=2,網絡直徑=41,網絡對剖寬度=4

3.7一個N=(k+1)24個節點的蝶形網絡如圖3.50所示。試問：此網絡節點度=?網絡直

徑=?網絡對剖寬度=?

答：N=(k+1)2”個節點的蝶形網絡，網絡節點度=4,網絡直徑=2*k,網絡對剖寬度

=2Ak

3.9對于如下列舉的網絡技術，用體系結構描述，速率范圍，電纜長度等填充下表中的各

項。(提示：根據討論的時間年限，每項可能是一個范圍)

答：

網絡技術網絡結構市4H-寬tAx銅線距離光纖距離

Myrinet專用機群互聯網絡200MB/秒25m500m

HiPPI用于異構計算機和其外設的800Mbps-1.6G25m300m-10k

組網bpsm

SCI可擴展一致性接口，通常獨立250Mbps?8Gbp

于拓撲結構s

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

直連結構Mbps

ATM主要應用于因特網主干線中25Mbps-lOGbp

s

FDDI采用雙向光纖令牌環，所有結100-200Mbps100m2KM

點聯接在該環中

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

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

1）這將會發生什么現象？

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

答：1）通路中形成環，發生死鎖

2）如果采用X-Y策略則不會發生死鎖。因為采用X-Y策略時其實質是對資源（這里

是通道）進行按序分配（永遠是x方向優先于y方向，反方向路由是y方向優先于x方向）,

因此根據死鎖避免的原則判斷，此時不會發生死鎖。

3.12在二維網孔中，試構造一個與X-Y選路等價的查表路由。

答：所構造路由表描述如下：

1）每個節點包括兩張路由表x表和y表

2）每個節點包含其以后節點信息，如節點【1,2】x表內容為：[2,2][3,2】y表

內容為：[1,3]

選路方法：

節點路由時進行查表：先查x表即進行x方向路由，如果查表能指明下一跳方向則直

接進入下一跳。如果不能則繼續查y表，直到到達目的地。

第四章對稱多處理機系統

4.1參照圖4.20,試解釋為什么采用WT策略進程從尸2遷移到勺時，或采用WB策略將包

含共享變量X的進程從片遷移到P2時，會造成高速緩存的不一致。

處理器

高速緩存

總線

共享

存儲器

遷移之前寫通過寫回

圖4.20進程遷移所造成的不一致性

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

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

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

4.2參照圖4.21所示，試解釋為什么：①在采用WT策略的高速緩存中，當I/O處理器將一

個新的數據X?寫回主存時會造成高速緩存和主存間的不一致；②在采用WB策略的高速緩

存中，當直接從主存輸出數據時會造成不一致。

處理器

P.p2P,p2p2

VVVV

高速緩存XXXJL

*

尼?欽i*

▼▼▼▼▼li

I/O處理機XX'￡X*

存儲器I/O存儲器（輸入）存儲器（輸出）

（寫直達）（寫回）

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

答：①中I/O處理器將數據X，寫回主存，因為高速緩存采用NT策略，此時P1和P2相應的

高速緩存值還是X,所以造成高速緩存與主存不一致。②直接從主存輸出數據X,因為高速

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

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

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

EZI高速緩存行共享存儲器R江］

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

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

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

一致性過程。

4.4兩種基于總線的共享內存多處理機分別實現了IllinoisMESI協議和Dragon協議，對于

下面給定的每個內存存取序列，試比較在這兩種多處理機上的執行代價，并就序列及一

致性協議的特點來說明為什么有這樣的性能差別。序列①rlwlrlwlr2w2r2w2r3

w3r3w3；序列②rlr2r3wlw2w3rlr2r3w3wl；序列③rlr2r3r3wlwlwl

wlw2w3；所有的存取操作都針對同一個內存位置，r/w代表讀/寫，數字代表發出該操

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

速緩存命中，代價1個時鐘周期；缺失引起簡單的總線事務（如BusUpgr,BusUpd）,60

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

答：讀寫命中、總線事務、塊傳輸分別簡記為H、B、ToMESI協議：①BTHHHHBTHBHH

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

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

Dragon協議：①BTHHHHBTHBTHHBTHBTHBTHHBTH共7B+12H+7T=882時鐘周期②

BTHBTHBTHBTHBTHBTHHHHHBTTHBTH8B+12H+8T=1212時鐘周期③BTHBTHBTHH

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

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

繁被多個核讀操作采用Dragon協議更好一些,因為Dragon協議寫操作后會更新其它核副本。

如果一個同多次連續對同一塊進行寫操作MESI協議更有效，因為它不需要更新其它核副本，

只需要總線事務無效其它核即可。

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

時，所有變量初始化為0。

a.

PlP2P3

A=1U=AV=B

B=1W=A

b.

PlP2P3P4

A=1U=AB=1W=B

V=BX=A

答：順序一致性模型性下，保護每個進程都按程序序來發生內存操作，這樣會有多種可能結

果，這里假設最簡單情況，即P1、P2、P3依次進行。則a中U=V=W=1,b中U=X=W=1,

V=0。

4.6參照461中討論多級高速緩存包含性的術語，假設L1和L2都是2-路組相聯，n2>ni,

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

略是隨機替換呢？

答：如果采用FIFO替換策略包含性自然滿足，因為L1和L2都是2路組相聯，FIFO保證

了L1與L2在發生替換時會換出相同的緩存塊，維護了包含性。如果采取隨機替換策略，

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

4.7針對以下高速緩存情況，試給出一個使得高速緩存的包含性不滿足的內存存取序列？

L1高速緩存容量32字節，2-路組相聯，每個高速緩存塊8個字節，使用LRU替換算

法；L2高速緩存容量128字節，4-路組相聯，每個高速緩存塊8個字節，使用LRU替

換算法。

答：假設ml、m2、m3塊映射到一級Cache和二級Cache的同一組中，考慮如下內存存取

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

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

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

發生：一個使無效請求緊跟在數據響應之后，使得處理器還沒有真正存取這個高速緩存

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

答：考慮如下情景：SMP目錄一致性協議中，核1讀缺失請求數據塊A,主存響應請求傳

送數據塊A給核1,同時核2對數據塊A進行寫操作，到主存中查得核1擁有副本，向核1

發使無效請求。如此，一個使無效請求緊跟在數據響應之后。解決方法，可以使每個核真正

存取高速緩存塊后向主存發回應，然后再允許其它對此塊操作的使無效或其它請求。

4.9利用LL-SC操作實現一個Test&Set操作。

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

bnzregl,lock/*iflocatinwaslocked,tryagain*/

movreg2,1/*setreg21*/

sclocation,reg2/*storereg2conditionalintolocation*/

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

的每個分支中，而是緊接放在計數器增1語句后，會發生什么問題？為什么會發生這個

問題？

答：再進入下一個路障時可能會發生計數器重新清0現象，導致無法越過路障?？紤]如

下情景：第一次進入路障時，最后兩個進入路障的進程分別為1、2。假設最后進入路障

的進程為2進程，2進程執行共享變量加一操作并解鎖。然后2進程執行一條if條件語

句，此時由于某種原因換出或睡眠，而此時共享變量的值已經為p。如果1進程此時正

執行if條件語句，則清零計數器，設置標志，其它進程越過路障。到目前為止沒有出現

問題，問題出現在下一次進入路障。進程再一次進入路障，此時會執行共享變量加一操

作。如果此時2進程被換入或被喚醒，會重新清零共享變量，使之前到達路障的進程的

加一操作無效，導致無法越過路障。

第五章大規模并行處理機系統

5.1簡述大規模并行處理機的定義，原理和優點？

答：并行處理機有時也稱為陣列處理機，它使用按地址訪問的隨機存儲器，以單指令流多數

據流方式工作，主要用于要求大量高速進行向量矩陣運算的應用領域。并行處理機的并行性

來源于資源重復，它把大量相同的處理單元（PE）通過互聯網絡（ICN）連接起來，在統一

的控制器（CU）控制下，對各自分配來的數據并行地完成同一條指令所規定的操作。PE是

不帶指令控制部件的算術邏輯運算單元。并行處理機具有強大的向量運算能力，具有向量化

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

5.2并行處理機有兩種基本結構類型，請問是哪兩種？并作簡單介紹。

答：采用分布存儲器的并行處理結構和采用集中式共享存儲器的并行處理結構。分布式存儲

器的并行處理結構中，每一個處理機都有自己的存儲器，只要控制部件將并行處理的程序分

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

結構中的存儲器是集中共享的，由于多個處理機共享，在各處理機訪問共享存儲器時會發生

競爭。因此，需采取措施盡可能避免競爭的發生。

5.3簡單說明多計算機系統和多處理機系統的區別。

答：他們雖然都屬于多機系統但是他們區別在于：（1）多處理機是多臺處理機組成的單機系

統，多計算機是多臺獨立的計算機。（2）多處理機中各處理機邏輯上受同一的OS控制，而

多計算機的OS邏輯上獨立.（3）多處理機間以單一數據，向量。數組和文件交互作用，多計

算機經通道或者通信線路以數據傳輸的方式進行。（4）多處理機作業，任務，指令，數據各

級并行，多計算機多個作業并行。

5.4舉例說明MPP的應用領域及其采用的關鍵技術。

答：全球氣候預報，基因工程，飛行動力學，海洋環流，流體動力學，超導建模，量子染色

動力學，視覺。采用的關鍵技術有VLSI,可擴張技術，共享虛擬存儲技術。

5.5多處理機的主要特點包括

答：

（1）結構的靈活性。與SIMD計算機相比，多處理機的結構具有較強的通用性，它可以同

時對多個數組或多個標量數據進行不同的處理，這要求多處理機能夠適應更為多樣的算法，

具有靈活多變的系統結構。2）程序并行性。并行處理機實現操作一級的并行，其并行性存

在于指令內部，主要用來解決數組向量問題；而多處理機的并行性體現在指令外部，即表現

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

個并發的程序段，需要專門的程序段來表示它們的并發關系以控制它們的并發執行，這稱為

并行任務派生。

4）進程同步。并行處理機實現操作級的并行，所有處于活動狀態的處理單元受一個控制器

控制，同時執行共同的指令，工作自然同步；而多處理機實現指令、任務、程序級的并行，

在同一時刻，不同的處理機執行著不同的指令，進程之間的數據相關和控制依賴決定了要采

取一定的進程同步策略.

5.6在并行多處理機系統中的私有Cache會引起Cache中的內容相互之間以及與共享存儲器

之間互不相同的問題，即多處理機的Cache一致性問題。請問有哪些原因導致這個問題？

答：

1）出現Cache一致性問題的原因主要有三個：共享可寫的數據、進程遷移、I/O傳輸。共

享可寫數據引起的不一致性。比如Pl、P2兩臺處理機各自的本地高速緩沖存儲器Cl、C2

中都有共享存儲器是M中某個數據X的拷貝，當P1把X的值變成X/后，如果P1采用寫

通過策略，內存中的數據也變為X/,C2中還是X。如果通過寫回策略，這是內存中還是X。

在這兩種情況下都會發生數據不一致性。2）進程遷移引起的數據不一致性。P1中有共享

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

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

不一致性。假設P1和P2的本地緩存Cl、C2中都有某數據X的拷貝，當1/0處理機將一個

新的數據X/寫入內存時，就導致了內存和Cache之間的數據不一致性。

5.7分別確定在下列兩種計算機系統中，計算表達式所需的時間：s=Al*Bl+A2*B2+…A4*B4。

a）有4個處理器的SIMD系統；b）有4個處理機的MIMD系統。假設訪存取指和取數的時間

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

每進行一次數據傳送的時間為1拍；在SIMD系統中，PE之間采用線性環形互連拓撲，即每

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

通路。

答：假設4個PE分別為PEO,PEI,PE2,PE3o利用SIMD計算機計算上述表達式，4個

乘法可以同時進行，用時=4個時間單位；然后進行PE0到PEI,PE2到PE3的數據傳送，

用時=1個時間單位。在PE1和PE3中形成部分和，用時=2個時間單位。接著進行PE1到

PE3的部分和傳送，用時?=1*2=2個時間單位。最后，在PE3中形成最終結果，用時=2個時

間單位。因此，利用SIMD計算機計算上述表達式總共用時=4（乘法）+1（傳送）+2（加

法）+2（傳送）+2（加法）=11個時間單位。而利用MIMD計算機計算上述表達式，除了

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

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

5.8假定有一個處理機臺數為p的共享存儲器多處理機系統。設m為典型處理機每條執行執

行時間對全局存儲器進行訪問的平均次數。

設t為共享存儲器的平均存儲時間，x為使用本地存儲器的單處理機MIPS速率，再假

定在多處理機上執行n條指令。

現在假設p=32,m=0.4,t=lus,要讓多處理機的有效性能達到56MIPS,需要每臺處理機

的MIPS效率是多少？

A.2

B.4

C.5.83

D.40

答：B

5.9試在含一個PE的SISD機和在含n個PE且連接成一線性環的SIMD機上計算下列求內積

的表達式：其中n=2-

s=￡4?Bi

i=l

假設完成每次ADD操作需要2個單元時間，完成每次MULTIPLY操作需要4個單位時間，

沿雙向環在相鄰PE間移數需1個單位時間

(1)SISD計算機上計算s需要多少時間

(2)SIMD計算機上計算s需要多少時間

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

答：

(1)4n+2(nT)

(2)4+2k+n—1

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

3+2k+n

5.10如果一臺SIMD計算機和一臺流水線處理機具有相同的計算性能，對構成它們的主要部

件分別有什么要求？

答：一臺具有n個處理單元的SIMD計算機與一臺具有一條n級流水線并且時鐘周期為前者

1/n的流水線處理機的計算性能相當，兩者均是每個時鐘周

期產生n個計算結果。但是，SIMD計算機需要n倍的硬件(n個處理單元)，而流水線處理

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

第六章機群系統

6.1試區分和例示下列關于機群的術語：

1)專用機群和非專用機群；

2)同構機群和異構機群；

3)專用型機群和企業型機群。

答：

1)根據節點的擁有情況，分為專用機群和非專用機群，在專用機群中所有的資源是共享的，

并行應用可以在整個機群上運行，而在非專用機群中，全局應用通過竊取CPU時間獲

得運行，非專用機群中由于存在本地用戶和遠地用戶對處理器的競爭，帶來了進程遷移

和負載平衡問題。

2）根據節點的配置分為同構機群和異構機群，同構機群中各節點有相似的的體系，并且使

用相同的操作系統，而異構機群中節點可以有不同的體系，運行的操作系統也可以不同。

3）專用型機群的特點是緊耦合的、同構的，通過一個前端系統進行集中式管理，常用來代

替傳統的大型超級計算機系統；而企業型機群是松耦合的，一般由異構節點構成，節點

可以有多個屬主，機群管理者對節點有有限的管理權。

6.2試解釋和例示一下有關單一系統映像的術語：

I）單一文件層次結構；

2）單一控制點：

3）單一存儲空間；

4）單一進程空間：

5）單一輸入/輸出和網絡。

答：

1）用戶進入系統后所見的文件系統是一個單一的文件和目錄層次結構，該系統透明的將本

地磁盤、全局磁盤和其他文件設備結合起來。

2）整個機群可以從一個單一的節點對整個機群或某一單一的節點進行管理和控制。

3）將機群中分布于各個節點的本地存儲器實現為一個大的、集中式的存儲器。

4）所有的用戶進程，不管它們駐留在哪個節點上，都屬于一個單一的進程空間，并且共享

一個統一的進程識別方案。

5）單一輸入/輸出意味著任何節點均可訪問多個外設。單一網絡是任一節點能訪問機群中

的任一網絡連接。

6.3就SolarisMC系統回答下列問題：

I）SolarisMC支持習題6.2中單一系統映像的哪些特征？不支持哪些特征？

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

答：

1）支持單一文件層次結構、單一進程空間、單一網絡和單一I/O空間。不支持單一控制點

和單一的存儲空間。

2）Solaris使用了一個叫PXFS的全局文件系統GFS。PXFS文件系統的主要特點包括：單

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

實現單一系統映像，保證了單一文件層次結構。

SolarisMC提供了一個全局進程標示符pid可定位系統所有進程，一個進程可以遷移到

其他節點，但它的宿主節點中總記錄有進程的當前位置，它通過在Solaris核心層上面增

加一個全局進程以實現單一進程空間，每個節點有一個節點管理程序，每個本地進程有

一個虛擬進程對象vproc,vproc保留每個父進程和子進程的信息，實現了全局進程的管

理。

單一網絡和I/O空間通過一致設備命名技術和單一網絡技術實現。

6.4舉例解釋并比較以下有關機群作業管理系統的術語:

1）串行作業與并行作業；

2）批處理作業與交互式作業；

3）機群作業和外來作業；

4）專用模式、空間共享模式、時間共享模式：

5）獨立調度與組調度。

答：

1）串行作業在單節點上運行，并行作業使用多個節點。

2）批處理作業通常需要較多的資源，如大量的內存和較長的CPU時間，但不需要迅速的

反應；交互式作業要求較快的周轉時間，其輸入輸出直接指向終端設備，這些工作一般

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

3）機群作業時通過使用JMS功能分布實現的用戶作業，用戶服務器位于任一主機節點，資

源管理器跨越所有的機群節點。外來作業在JMS之外生成的，如NOW上的一個工作站

擁有者啟動的外部作業，它不提交給JMS。

4）專用模式：任一時候只有一個作業在機群上運行，任一時候也只有一個作業進程分配給

一個節點?？臻g共享模式：多個作業可以在不重疊的節點區域上運行。時間共享模式：

在專用模式和空間共享模式下，只有一個用戶進程分配給一個節點，但是所有的系統進

程或監護程序仍在同一個節點上運行。

5）獨立調度：各節點OS進行自己的調度，但這會顯著損壞并行作業的性能，因為并行作

業的進程間需要交互。組調度：將并行作業的所有進程一起調度。一個進程激活時，所

有進程都被激活。

6.5針對LSF回答下列問題：

1）對LSF的四種作業類型各舉一個例子；

2）舉一個例子說明外來作業；

3）對一個有1000個服務器的機群，為什么LSF負載分配機制優于：1整個機群只有一個

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

答：

1）交互式：用戶使用Ishosts命令就可以列出每個服務器節點的靜態資源，實現交互。批處

理：Isbatch實用程序允許通過LSF提交、監控和執行批處理作業。串行：用戶一旦進入

Istcshshell,發送的每條命令自動在最適合的節點上執行。并行：Ismake實用程序是UNIX

make實用程序時一個并行版本，允許在多個節點同時處理一個Makefile0

2）不通過LSF執行的稱為外來作業。例如執行一些本地作業：字處理，web網絡瀏覽等。

3）機群的服務器數目太多，如果只采用一個LIM會導致LIM的負責過重，不能及時的處

理響應所有服務器的請求和分派所有機群作業;如果采用2會導致LIM之間相互交換負

載信息過多，導致網絡通信量過大。

6.6為什么在分布式文件系統中，UNIX語義難以實現？有哪些放松的文件共享語義？采用

放松的文件共享語義會有一些什么缺點？

答：

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

統中，多個節點可能存放了同一文件塊的拷貝，當其中一個節點修改文件可的拷貝時.，其他

節點不能立刻就知道，這就使得UNIX語義難以實現。放松的文件共享語義有：對話語義、

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

序代碼，以適用這種新的語義，這就增加了程序員的負擔。

6.7試解釋在機群并行文件系統中，為什么采用軟件RAID、高速緩存機制和預取能夠提高

文件系統性能。

答：

軟件RAID是文件系統負責分布數據和維護容錯級別，能夠和RA1D5有一樣的性能，實現

機群磁盤間的數據分布，提高了I/O系統的傳輸帶寬。高速緩存是將應用程序要取的塊放在

CACHE中，根據局部性原理，應用程序可以基本上從CACHE中讀取數據塊，而不要通過

讀取內存或硬盤，提高了讀取速度。預取是在真正讀取數據塊之前就將這些數據塊讀入內存,

這也提高了I/O性能，改善了文件系統性能。

6.8討論并行文件系統協作化高速緩存的基本技術前提是什么？這個前提有什么意義？

答：

基本技術前提是互聯網絡的速度很快，一個節點需要的文件塊在其他節點的緩存中，那么就

不需要從磁盤讀，而是直接從其他節點的緩存中讀出。這個前提的意義是可以提高系統的性

能，使得節點間的協作化緩存變得更有意義。

6.9回答以下關于BerkeleyNOW項目的問題：

1）BerkeleyNOW項目支持單一系統映像的哪幾個方面？即單入口點、單文件層次結構、單

控制點、單存儲空間、單進程空間哪個的哪幾項？并解釋如何支持。

2）解釋BerkeleyNOW項目用來提高性能的四個結構特征。

3）解釋BerkeleyNOW項目和SP機群四個體系結構的差異，并討論各自的優點。

答：

1）通過用戶級整個機群軟件GLUNIX,提供單一系統映像。開發了一種新的無服務器網絡

文件系統xFS,以支持單一文件層次結構。

2）主動消息通信協議，支持有效的通信；機群軟件GLUNIX提供單一的系統映像、資源管

理和可用性；xFS支持可擴放性和單一文件層次結構的高可用性；軟件框架WebOS構

筑高可用性、漸增可擴放性。

3）SP機群的體系結構特征：每個節點都是RS/600工作站，并有自己的局部磁盤；每個節

點內駐留一個完整的AIX；各節點通過其I/O總線連接到專門設計的多級高速網絡；盡

量使用標準工作站部件。這樣的優點是簡單性和靈活性。

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

1）解釋xFS和集中式文件服務器的兩個不同點，并討論各自的優點；

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

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

答：

1）無服務器文件系統xFS將文件服務的功能分布到機器的所有節點上，xFS中所有的服務

器和客戶的功能由分散的所有節點實現之。這與集中文件服務器的中央存儲、中央緩存、

中央管理不同。xFS的優點是采用分布式管理和協同文件緩存以及冗余磁盤陣列，這提

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

管理簡單。

2）xFS提高可用性的主要技術是采用廉價冗余磁盤陣列RAID。無工作站文件系統能用來

生成軟件RAID,以提高性能和高可用性。現在xFS使用單奇偶校驗磁盤條。一個文件

數據塊在多個存儲服務器節點上按條劃分，在另一個節點上有奇偶校驗塊。如果一個節

點失效，失效磁盤的內容，可利用其余盤和奇偶盤之異或操作重建之。

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

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

送給K個存儲服務器。

第七章分布式共享存儲系統

7.1什么是分布式共享存儲系統，它相對于共享存儲系統與分布式系統有哪些優點？

答：分布式共享存儲系統，是把共享存儲器分成許多模塊并分布于各處理機之中。分布式系

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

傳統的單地址空間，但共享必然引起沖突，形成瓶頸，于是分布式共享存儲系統結合兩者的

優點。

7.2釋放一致性模型(RC)把處理器一致性(PC)和弱一致性模型(WC)的優點結合在一起了。

試回答下面有關這些一致性模型的問題：

a)比較這三種一致性模型的實現要求。

b)評論每種一致性模型的優缺點。

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

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

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

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

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

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

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

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

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

b)三種模型對存儲順序要求逐漸降低，可優化程度逐漸增加，但是對程序員的要求也越

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

7.3在DSM系統的順序一致性存儲模型下，有三個并行執行的進程如下所示，試問001110

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

PlP2P3

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

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

答：不是一個合法輸出?？紤]順序一致性存儲模型，每個進程的程序序會被維護，那么無論

哪個進程最后執行Print語句，則之前的A=l,B=1,C=1都已經完成，所以輸出的兩后兩項

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

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

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

如果一行有多個引用，我們假設P1在P2之前發射、P2在P3之前發射內存引用，符號

LD/STWi表示LOAD/STORE字i。

操作序號P1P2P3

1STW0STW7

2LDW6LDW2

3LDW7

4LDW2LDWO

5STW2

6LDW2

7STW2LDW5LDW5

8STW5

9LDW3LDW7

10LDW6LDW2

11LDW2STW7

12LDW7

13LDW2

14LDW5

15LDW2

答：操作序號3、6、8、12-15都是單操作。操作序號1、2、9-11為無關存儲操作，由于不

在同一塊中。操作序號4、7為對同一緩存塊的連續兩次LD,需要按序進行。

7.5假設系統中共有512個處理器和1GB主存，每個節點內有8個處理器對目錄可見，一個

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

本各是多少？

答：分別為總容量的12.%和5.47%。

7.6細數一下中心目錄與分布式目錄方案的實現方法與各自的使用情況。

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

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

存的目錄類似。大型多處理機系統采用中心目錄會有沖突和檢索時間過長兩個跳點。

分布式目錄方案是由Censier和Feautrier提出來。在分布式目錄中每個存儲器模塊維護

各自的目錄，目錄中記錄著每個存儲器塊的狀態和當前的信息，其中狀態信息是本地的，而

當前信息指明哪些高速緩存中有該存儲器塊的拷貝。

一般來說，在共享存儲上實現中心目錄，而在分布式系統上實現分布式目錄方案更為合

適一些，但這也并不是絕對的。

7.7在研究DS