并行計算課后答案

1、第三章互連網(wǎng)絡(luò)對于一顆K 級二叉樹（根為0 級，葉為k-1 級），共有 N=2k-1 個節(jié)點(diǎn)，當(dāng)推廣至m-元樹時（即每個非葉節(jié)點(diǎn)有m個子節(jié)點(diǎn)）時，試寫出總節(jié)點(diǎn)數(shù)N的表達(dá)式。答：推廣至 M元樹時， k 級 M元樹總結(jié)點(diǎn)數(shù)N 的表達(dá)式為：N=1+m1+m2+.+m（k-1 ） =(1-mk)*1/(1-m);二元胖樹如圖所示，此時所有非根節(jié)點(diǎn)均有2 個父節(jié)點(diǎn)。 如果將圖中的每個橢圓均視為單個節(jié)點(diǎn)， 并且成對節(jié)點(diǎn)間的多條邊視為一條邊，則他實(shí)際上就是一個二叉樹。試問： 如果不管橢圓，只把小方塊視為節(jié)點(diǎn)，則他從葉到根形成什么樣的多級互聯(lián)網(wǎng)絡(luò)答： 8 輸入的完全混洗三級互聯(lián)網(wǎng)絡(luò)。四元胖樹如圖所示，試問：每

2、個內(nèi)節(jié)點(diǎn)有幾個子節(jié)點(diǎn)和幾個父節(jié)點(diǎn)你知道那個機(jī)器使用了此種形式的胖樹答：每個內(nèi)節(jié)點(diǎn)有4 個子節(jié)點(diǎn)， 2 個父節(jié)點(diǎn)。 CM-5使用了此類胖樹結(jié)構(gòu)。試構(gòu)造一個N=64 的立方環(huán)網(wǎng)絡(luò)，并將其直徑和節(jié)點(diǎn)度與N=64 的超立方比較之，你的結(jié)論是什么答： A N=64 的立方環(huán)網(wǎng)絡(luò), 為 4 立方環(huán)（將4 維超立方每個頂點(diǎn)以4 面體替代得到） ，直徑d=9，節(jié)點(diǎn)度n=4B N=64 的超立方網(wǎng)絡(luò)，為六維超立方（將一個立方體分為8 個小立方，以每個小立方作為簡單立方體的節(jié)點(diǎn)，互聯(lián)成6 維超立方），直徑 d=6，節(jié)點(diǎn)度n=6一個 N=2k 個節(jié)點(diǎn)的 de Bruijin網(wǎng)絡(luò)如圖所示，令 ak 1 ak 2ak

3、3 。 a1a0 ，是一個節(jié)點(diǎn)的二進(jìn)制表示，則該節(jié)點(diǎn)可達(dá)如下兩個節(jié)點(diǎn)：ak 2 ak 3 。 a1 a00， ak 2 ak 3。 a1 a0 1。試問：該網(wǎng)絡(luò)的直徑和對剖寬度是多少答： N=2k 個節(jié)點(diǎn)的 de Bruijin網(wǎng)絡(luò)直徑 d=k 對剖寬帶w=2(k-1)一個 N=2n 個節(jié)點(diǎn)的洗牌交換網(wǎng)絡(luò)如圖所示。寬度 =答： N=2n 個節(jié)點(diǎn)的洗牌交換網(wǎng)絡(luò)，網(wǎng)絡(luò)節(jié)點(diǎn)度為試問：此網(wǎng)絡(luò)節(jié)點(diǎn)度 =網(wǎng)絡(luò)直徑 =網(wǎng)絡(luò)對剖=2，網(wǎng)絡(luò)直徑 =n-1，網(wǎng)絡(luò)對剖寬度=4一個 N=（ k+1） 2k 個節(jié)點(diǎn)的蝶形網(wǎng)絡(luò)如圖所示。試問：此網(wǎng)絡(luò)節(jié)點(diǎn)度剖寬度 =答：N=（k+1）2k 個節(jié)點(diǎn)的蝶形網(wǎng)絡(luò)，網(wǎng)絡(luò)節(jié)點(diǎn)度 =4

4、，網(wǎng)絡(luò)直徑 =2*k=網(wǎng)絡(luò)直徑 =網(wǎng)絡(luò)對，網(wǎng)絡(luò)對剖寬度 =2k對于如下列舉的網(wǎng)絡(luò)技術(shù)，用體系結(jié)構(gòu)描述，速率范圍，電纜長度等填充下表中的各項。（提示：根據(jù)討論的時間年限，每項可能是一個范圍）答：網(wǎng)絡(luò)技術(shù)網(wǎng)絡(luò)結(jié)構(gòu)帶寬銅線距離光纖距離Myrinet專用機(jī)群互聯(lián)網(wǎng)絡(luò)200MB/秒25m500mHiPPI用于異構(gòu)計算機(jī)和其外設(shè)的800Mbps25m300m10km組網(wǎng)SCI可擴(kuò)展一致性接口， 通常獨(dú)立250Mbps8Gbps于拓?fù)浣Y(jié)構(gòu)光纖通信多處理器和其外圍設(shè)備之間，100Mbps800Mb50m10km直連結(jié)構(gòu)psATM主要應(yīng)用于因特網(wǎng)主干線中25Mbps10GbpsFDDI采用雙向光纖令牌環(huán)， 所有

5、結(jié)100-200Mbps100m2KM點(diǎn)聯(lián)接在該環(huán)中如圖所示，信包的片0， 1， 2， 3 要分別去向目的地A， B， C， D。此時片 0 占據(jù)信道CB，片 1 占據(jù)信道 DC，片 2 占據(jù)信道 AD，片 3 占據(jù)信道 BA。試問：1 ）這將會發(fā)生什么現(xiàn)象2 ）如果采用 X-Y 選路策略，可避免上述現(xiàn)象嗎為什么答： 1 ）通路中形成環(huán)，發(fā)生死鎖2 ）如果采用 X-Y 策略則不會發(fā)生死鎖。 因?yàn)椴捎?X-Y 策略時其實(shí)質(zhì)是對資源 （這里是通道）進(jìn)行按序分配（永遠(yuǎn)是x 方向優(yōu)先于y 方向，反方向路由是y 方向優(yōu)先于x 方向），因此根據(jù)死鎖避免的原則判斷，此時不會發(fā)生死鎖。在二維網(wǎng)孔中，試構(gòu)造一個

6、與X-Y 選路等價的查表路由。答：所構(gòu)造路由表描述如下：1）每個節(jié)點(diǎn)包括兩張路由表x 表和 y 表2）每個節(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)路由時進(jìn)行查表：先查x 表即進(jìn)行x 方向路由，如果查表能指明下一跳方向則直接進(jìn)入下一跳。如果不能則繼續(xù)查y 表，直到到達(dá)目的地。第四章對稱多處理機(jī)系統(tǒng)參照圖，試解釋為什么采用WT策略進(jìn)程從P2 遷移到 P1 時，或采用WB策略將包含共享變量X 的進(jìn)程從P1遷移到 P2 時，會造成高速緩存的不一致。處理器P1P2P1P2P1P2高速緩存XXX'X'

7、;X總線共享X'XX存儲器遷移 之前寫通 過寫回圖 進(jìn)程遷移所造成的不一致性答：采用 WT策略進(jìn)程從 P2遷移到 P1 后， P2寫共享變量 X 為 X，并且更新主存數(shù)據(jù)為 X，此時 P1 共享變量值仍然為X，與 P2和主存 X不一致。采用WB策略進(jìn)程從 P1 遷移到 P2 后，P1 寫共享變量 X 為 X，但此時 P2 緩存與主存變量值仍然為X，造車不一致。參照圖所示，試解釋為什么：在采用WT策略的高速緩存中，當(dāng)I/O 處理器將一個新的數(shù)據(jù) X ' 寫回主存時會造成高速緩存和主存間的不一致； 在采用 WB策略的高速緩存中， 當(dāng)直接從主存輸出數(shù)據(jù)時會造成不一致。處理器P1P2P

8、1P2P1P2高速緩存XXXXX'X總線I/O處理機(jī)XX'X'XX存儲器I/O存儲器( 輸入)存儲器( 輸出 )（寫直達(dá)）（寫回）圖 繞過高速緩存的I/O 操作所造成的不一致性答：中I/O 處理器將數(shù)據(jù)X寫回主存，因?yàn)楦咚倬彺娌捎肳T策略，此時P1 和 P2 相應(yīng)的高速緩存值還是X，所以造成高速緩存與主存不一致。直接從主存輸出數(shù)據(jù)X，因?yàn)楦咚倬彺娌捎肳B策略，可能高速緩存中的數(shù)據(jù)已經(jīng)被修改過，所以造成不一致。4.3 試解釋采用WB策略的寫更新和寫無效協(xié)議的一致性維護(hù)過程。其中X 為更新前高速緩存中的拷貝，X ' 為修改后的高速緩存塊，I 為無效的高速緩存塊。x高

9、速緩存行共享存儲器II偵聽總線xxx 高速緩存拷貝xIIxxxP1P2處理器PnP1P2PnP1P2Pn（a）寫操作前（b）處理器P1執(zhí)行寫無效操作后（c）處理器P1執(zhí)行寫更新操作后答：處理器P1 寫共享變量X 為 X，寫更新協(xié)議如圖(c) 所示，同時更新其他核中存在高速緩存拷貝的值為X; 寫無效協(xié)議如圖(b) 所示，無效其他核中存在高速緩存拷貝，從而維護(hù)了一致性過程。4.4 兩種基于總線的共享內(nèi)存多處理機(jī)分別實(shí)現(xiàn)了Illinois MESI協(xié)議和 Dragon 協(xié)議，對于下面給定的每個內(nèi)存存取序列，試比較在這兩種多處理機(jī)上的執(zhí)行代價，并就序列及一致性協(xié)議的特點(diǎn)來說明為什么有這樣的性能差別。序

10、列r1 w1 r1 w1 r2 w2 r2 w2 r3w3 r3 w3 ；序列 r1 r2 r3 w1 w2 w3 r1 r2 r3 w3 w1；序列 r1 r2 r3 r3 w1 w1 w1w1 w2 w3；所有的存取操作都針對同一個內(nèi)存位置，r/w 代表讀 / 寫，數(shù)字代表發(fā)出該操作的處理器。假設(shè)所有高速緩存在開始時是空的，并且使用下面的性能模型：讀/ 寫高速緩存命中，代價1 個時鐘周期；缺失引起簡單的總線事務(wù)（如BusUpgr，BusUpd）， 60個時鐘周期； 缺失引起整個高速緩存塊傳輸，90 時鐘周期。 假設(shè)所有高速緩存是寫回式。答：讀寫命中、總線事務(wù)、塊傳輸分別簡記為H、B、 T。

11、 MESI協(xié)議： BTH H H H BTH BH HH BTH BH H H 共 5B+12H+3T=582時鐘周期 BTH BTH BTH BH BTH BTH BTH BTH H BH BTH共10B+12H+8T=1330時鐘周期 BTH BTH BTH H BH H H H BTH BTH共 6B+10H+4T=730時鐘周期。Dragon 協(xié)議： BTH H H H BTH BTH H BTH BTH BTH H BTH共 7B+12H+7T=882時鐘周期BTH BTH BTH BTH BTH BTH H H H H BTTH BTH共 8B+12H+8T=1212時鐘周期 BT

12、H BTH BTH HBTH BTH BTH BTH BTH BTH共 9B+10H+9T=1360時鐘周期。由結(jié)果得出，、序列用MESI協(xié)議時間更少，而序列用Dragon 協(xié)議時間更少。綜上可知，如果同一塊在寫操作之后頻繁被多個核讀操作采用Dragon 協(xié)議更好一些， 因?yàn)?Dragon 協(xié)議寫操作后會更新其它核副本。如果一個同多次連續(xù)對同一塊進(jìn)行寫操作MESI 協(xié)議更有效，因?yàn)樗恍枰缕渌烁北?，只需要總線事務(wù)無效其它核即可。考慮以下代碼段，說明在順序一致性模型下，可能的結(jié)果是什么假設(shè)在代碼開始執(zhí)行時，所有變量初始化為0。a.P1P2P3A=1U=AV=BB=1W=Ab.P1P2P3P

13、4A=1U=AB=1W=BV=BX=A答：順序一致性模型性下，保護(hù)每個進(jìn)程都按程序序來發(fā)生內(nèi)存操作，這樣會有多種可能結(jié)果，這里假設(shè)最簡單情況，即P1、 P2、 P3 依次進(jìn)行。則a 中 U = V = W = 1 ， b 中 U=X=W=1，V=0。4.6 參照中討論多級高速緩存包含性的術(shù)語，假設(shè) L1 和 L2 都是 2- 路組相聯(lián)， n2>n1，b1=b2，且替換策略用FIFO 來代替 LRU，試問包含性是否還是自然滿足如果替換策略是隨機(jī)替換呢答：如果采用FIFO 替換策略包含性自然滿足，因?yàn)長1 和 L2 都是 2 路組相聯(lián)， FIFO 保證了L1 與 L2 在發(fā)生替換時會換出相同

14、的緩存塊，維護(hù)了包含性。如果采取隨機(jī)替換策略，存在L1 與 L2 替換不是相同塊的情況，故不滿足包含性。4.7 針對以下高速緩存情況，試給出一個使得高速緩存的包含性不滿足的內(nèi)存存取序列L1高速緩存容量32 字節(jié)， 2- 路組相聯(lián)， 每個高速緩存塊8 個字節(jié)， 使用 LRU替換算法；L2高速緩存容量128 字節(jié)， 4- 路組相聯(lián)，每個高速緩存塊8 個字節(jié)，使用LRU替換算法。答：假設(shè)m1、m2、 m3塊映射到一級Cache 和二級 Cache 的同一組中，考慮如下內(nèi)存存取序列 Rm1， Rm2，Rm1，Rm3，由 LRU替換算法知道，當(dāng) Rm3執(zhí)行后， L1 中被替換出的是 m2， L2 中被替

15、換出的是 m1，此時 m1塊在 L1 卻不在 L2 中，不滿足包含性。4.8 在中關(guān)于分事務(wù)總線的討論中，依賴于處理器與高速緩存的接口，下面情況有可能發(fā)生：一個使無效請求緊跟在數(shù)據(jù)響應(yīng)之后，使得處理器還沒有真正存取這個高速緩存塊之前，該高速緩存塊就被使無效了。為什么會發(fā)生這種情況，如何解決答：考慮如下情景：SMP目錄一致性協(xié)議中，核1 讀缺失請求數(shù)據(jù)塊A，主存響應(yīng)請求傳送數(shù)據(jù)塊 A 給核 1，同時核 2 對數(shù)據(jù)塊A進(jìn)行寫操作，到主存中查得核1 擁有副本，向核1 發(fā)使無效請求。如此，一個使無效請求緊跟在數(shù)據(jù)響應(yīng)之后。解決方法，可以使每個核真正存取高速緩存塊后向主存發(fā)回應(yīng)，然后再允許其它對此塊操作

16、的使無效或其它請求。4.9 利用LL-SC 操作實(shí)現(xiàn)一個Test&Set操作。答： Test&Set ： ll reg1,location /*Load-locked the location to reg1 */ bnz reg1,lock /* if locatin was locked,try again*/ mov reg2,1 /*set reg2 1*/sc location,reg2 /*store reg2 conditional into location*/4.10 在部分描述具有感覺反轉(zhuǎn)的路障算法中，如果將 Unlock 語句不放在if條件語句的每個分支中

17、，而是緊接放在計數(shù)器增1 語句后，會發(fā)生什么問題為什么會發(fā)生這個問題答：再進(jìn)入下一個路障時可能會發(fā)生計數(shù)器重新清0 現(xiàn)象，導(dǎo)致無法越過路障。考慮如下情景：第一次進(jìn)入路障時，最后兩個進(jìn)入路障的進(jìn)程分別為1、2。假設(shè)最后進(jìn)入路障的進(jìn)程為2 進(jìn)程， 2 進(jìn)程執(zhí)行共享變量加一操作并解鎖。然后2 進(jìn)程執(zhí)行一條if條件語句，此時由于某種原因換出或睡眠，而此時共享變量的值已經(jīng)為p。如果1 進(jìn)程此時正執(zhí)行 if條件語句，則清零計數(shù)器，設(shè)置標(biāo)志，其它進(jìn)程越過路障。到目前為止沒有出現(xiàn)問題，問題出現(xiàn)在下一次進(jìn)入路障。進(jìn)程再一次進(jìn)入路障，此時會執(zhí)行共享變量加一操作。如果此時2 進(jìn)程被換入或被喚醒，會重新清零共享變量，

18、使之前到達(dá)路障的進(jìn)程的加一操作無效，導(dǎo)致無法越過路障。第五章 大規(guī)模并行處理機(jī)系統(tǒng)簡述大規(guī)模并行處理機(jī)的定義，原理和優(yōu)點(diǎn)答：并行處理機(jī)有時也稱為陣列處理機(jī)，它使用按地址訪問的隨機(jī)存儲器，以單指令流多數(shù)據(jù)流方式工作， 主要用于要求大量高速進(jìn)行向量矩陣運(yùn)算的應(yīng)用領(lǐng)域。并行處理機(jī)的并行性來源于資源重復(fù)，它把大量相同的處理單元（PE）通過互聯(lián)網(wǎng)絡(luò)（ICN）連接起來，在統(tǒng)一的控制器（ CU）控制下，對各自分配來的數(shù)據(jù)并行地完成同一條指令所規(guī)定的操作。PE 是不帶指令控制部件的算術(shù)邏輯運(yùn)算單元。并行處理機(jī)具有強(qiáng)大的向量運(yùn)算能力，具有向量化功能的高級語言編譯程序有助于提高并行處理機(jī)的通用性，減少編譯時間。并

19、行處理機(jī)有兩種基本結(jié)構(gòu)類型，請問是哪兩種并作簡單介紹。答：采用分布存儲器的并行處理結(jié)構(gòu)和采用集中式共享存儲器的并行處理結(jié)構(gòu)。分布式存儲器的并行處理結(jié)構(gòu)中， 每一個處理機(jī)都有自己的存儲器，只要控制部件將并行處理的程序分配至各處理機(jī)， 它們便能并行處理， 各自從自己的存儲器中取得信息。而共享存儲多處理機(jī)結(jié)構(gòu)中的存儲器是集中共享的，由于多個處理機(jī)共享，在各處理機(jī)訪問共享存儲器時會發(fā)生競爭。因此，需采取措施盡可能避免競爭的發(fā)生。簡單說明多計算機(jī)系統(tǒng)和多處理機(jī)系統(tǒng)的區(qū)別。答：他們雖然都屬于多機(jī)系統(tǒng)但是他們區(qū)別在于：（1）多處理機(jī)是多臺處理機(jī)組成的單機(jī)系統(tǒng)，多計算機(jī)是多臺獨(dú)立的計算機(jī)。 （ 2）多處理機(jī)中

20、各處理機(jī)邏輯上受同一的 OS控制，而多計算機(jī)的 OS邏輯上獨(dú)立 .(3) 多處理機(jī)間以單一數(shù)據(jù)，向量。數(shù)組和文件交互作用，多計算機(jī)經(jīng)通道或者通信線路以數(shù)據(jù)傳輸?shù)姆绞竭M(jìn)行。 （ 4）多處理機(jī)作業(yè)，任務(wù)，指令，數(shù)據(jù)各級并行，多計算機(jī)多個作業(yè)并行。舉例說明MPP的應(yīng)用領(lǐng)域及其采用的關(guān)鍵技術(shù)。答：全球氣候預(yù)報，基因工程，飛行動力學(xué)，海洋環(huán)流，流體動力學(xué)，超導(dǎo)建模，量子染色動力學(xué)，視覺。采用的關(guān)鍵技術(shù)有VLSI，可擴(kuò)張技術(shù)，共享虛擬存儲技術(shù)。多處理機(jī)的主要特點(diǎn)包括答：（ 1） 結(jié)構(gòu)的靈活性。與 SIMD計算機(jī)相比，多處理機(jī)的結(jié)構(gòu)具有較強(qiáng)的通用性，它可以同時對多個數(shù)組或多個標(biāo)量數(shù)據(jù)進(jìn)行不同的處理，這要求多

21、處理機(jī)能夠適應(yīng)更為多樣的算法，具有靈活多變的系統(tǒng)結(jié)構(gòu)。 2） 程序并行性。并行處理機(jī)實(shí)現(xiàn)操作一級的并行，其并行性存在于指令內(nèi)部， 主要用來解決數(shù)組向量問題； 而多處理機(jī)的并行性體現(xiàn)在指令外部，即表現(xiàn)在多個任務(wù)之間。3） 并行任務(wù)派生。多處理機(jī)是多指令流操作方式，一個程序中就存在多個并發(fā)的程序段， 需要專門的程序段來表示它們的并發(fā)關(guān)系以控制它們的并發(fā)執(zhí)行，這稱為并行任務(wù)派生。4） 進(jìn)程同步。 并行處理機(jī)實(shí)現(xiàn)操作級的并行，所有處于活動狀態(tài)的處理單元受一個控制器控制，同時執(zhí)行共同的指令，工作自然同步；而多處理機(jī)實(shí)現(xiàn)指令、任務(wù)、程序級的并行，在同一時刻， 不同的處理機(jī)執(zhí)行著不同的指令， 進(jìn)程之間的數(shù)據(jù)

22、相關(guān)和控制依賴決定了要采取一定的進(jìn)程同步策略。在并行多處理機(jī)系統(tǒng)中的私有Cache會引起 Cache中的內(nèi)容相互之間以及與共享存儲器之間互不相同的問題，即多處理機(jī)的Cache 一致性問題。請問有哪些原因?qū)е逻@個問題答：1） 出現(xiàn) Cache 一致性問題的原因主要有三個：共享可寫的數(shù)據(jù)、進(jìn)程遷移、I/O傳輸。共享可寫數(shù)據(jù)引起的不一致性。比如P1、 P2 兩臺處理機(jī)各自的本地高速緩沖存儲器C1、 C2中都有共享存儲器是 M中某個數(shù)據(jù) X 的拷貝，當(dāng) P1 把 X 的值變成 X/ 后，如果 P1 采用寫通過策略，內(nèi)存中的數(shù)據(jù)也變?yōu)閄/ ，C2 中還是 X。如果通過寫回策略，這是內(nèi)存中還是X。在這兩種

23、情況下都會發(fā)生數(shù)據(jù)不一致性。2） 進(jìn)程遷移引起的數(shù)據(jù)不一致性。P1 中有共享數(shù)據(jù) X 的拷貝，某時刻 P1 進(jìn)程把它修改為 X/ 并采用了寫回策略， 由于某種原因進(jìn)程從 P1 遷移到了 P2 上，它讀取數(shù)據(jù)時得到 X，而這個 X 是“過時”的。 3） I/O 傳輸所造成的數(shù)據(jù)不一致性。假設(shè)P1 和 P2 的本地緩存C1、 C2 中都有某數(shù)據(jù)X 的拷貝，當(dāng)I/O 處理機(jī)將一個新的數(shù)據(jù) X/ 寫入內(nèi)存時，就導(dǎo)致了內(nèi)存和Cache 之間的數(shù)據(jù)不一致性。分別確定在下列兩種計算機(jī)系統(tǒng)中，計算表達(dá)式所需的時間：s=A1*B1+A2*B2+A4*B4。 a)有 4 個處理器的SIMD系統(tǒng)； b)有 4 個處

24、理機(jī)的MIMD系統(tǒng)。假設(shè)訪存取指和取數(shù)的時間可以忽略不計；加法與乘法分別需要2 拍和 4 拍；在 SIMD和 MIMD系統(tǒng)中處理器 （機(jī)）之間每進(jìn)行一次數(shù)據(jù)傳送的時間為1 拍；在 SIMD系統(tǒng)中， PE之間采用線性環(huán)形互連拓?fù)?，即每個PE與其左右兩個相鄰的PE 直接相連，而在MIMD中每個 PE都可以和其它PE有直接的的通路。答：假設(shè) 4 個 PE 分別為 PE0，PE1，PE2，PE3。利用 SIMD計算機(jī)計算上述表達(dá)式，4 個乘法可以同時進(jìn)行，用時=4 個時間單位；然后進(jìn)行PE0到 PE1，PE2到 PE3 的數(shù)據(jù)傳送，用時=1個時間單位。在PE1 和 PE3 中形成部分和，用時=2 個時

25、間單位。接著進(jìn)行PE1 到 PE3 的部分和傳送，用時=1*2=2 個時間單位。最后，在PE3 中形成最終結(jié)果，用時=2 個時間單位。因此，利用SIMD計算機(jī)計算上述表達(dá)式總共用時=4（乘法） +1（傳送） +2（加法） +2（傳送） +2（加法） =11 個時間單位。而利用MIMD計算機(jī)計算上述表達(dá)式，除了在第二次傳送節(jié)省 1 個時間單位以外，其他與SIMD相同。因此用時=4（乘法） +1（傳送） +2（加法） +1（傳送） +2（加法） =10 個時間單位。假定有一個處理機(jī)臺數(shù)為p 的共享存儲器多處理機(jī)系統(tǒng)。設(shè) m為典型處理機(jī)每條執(zhí)行執(zhí)行時間對全局存儲器進(jìn)行訪問的平均次數(shù)。設(shè) t 為共享存

26、儲器的平均存儲時間，x 為使用本地存儲器的單處理機(jī)MIPS 速率，再假定在多處理機(jī)上執(zhí)行n 條指令。現(xiàn)在假設(shè)p=32,m=,t=1 s, 要讓多處理機(jī)的有效性能達(dá)到56MIPS，需要每臺處理機(jī)的MIPS效率是多少答： B試在含一個 PE的 SISD 機(jī)和在含 n 個 PE且連接成一線性環(huán)的 SIMD機(jī)上計算下列求內(nèi)積的表達(dá)式：其中 n=2kns Ai ? Bii 1假設(shè)完成每次ADD操作需要2 個單元時間，完成每次MULTIPLY操作需要 4 個單位時間，沿雙向環(huán)在相鄰PE間移數(shù)需1 個單位時間(1) SISD 計算機(jī)上計算 s 需要多少時間(2) SIMD計算機(jī)上計算 s 需要多少時間(3)

27、 SIMD機(jī)計算 s 相對于 SISD 計算的加速比是多少答：(1) 4n+2(n-1)(2) 4 2k n 1(3)4n2 n132kn如果一臺 SIMD計算機(jī)和一臺流水線處理機(jī)具有相同的計算性能，對構(gòu)成它們的主要部件分別有什么要求答：一臺具有n 個處理單元的SIMD計算機(jī)與一臺具有一條n 級流水線并且時鐘周期為前者1/n 的流水線處理機(jī)的計算性能相當(dāng)，兩者均是每個時鐘周期產(chǎn)生 n 個計算結(jié)果。但是，SIMD計算機(jī)需要n 倍的硬件（ n 個處理單元），而流水線處理機(jī)中流水線部件的時鐘速率要求比前者快n 倍，同時還需要存儲器的帶寬也是前者的n 倍。第六章機(jī)群系統(tǒng)試區(qū)分和例示下列關(guān)于機(jī)群的術(shù)語：

28、1）專用機(jī)群和非專用機(jī)群；2）同構(gòu)機(jī)群和異構(gòu)機(jī)群；3）專用型機(jī)群和企業(yè)型機(jī)群。答：1） 根據(jù)節(jié)點(diǎn)的擁有情況，分為專用機(jī)群和非專用機(jī)群，在專用機(jī)群中所有的資源是共享的，并行應(yīng)用可以在整個機(jī)群上運(yùn)行，而在非專用機(jī)群中，全局應(yīng)用通過竊取CPU時間獲得運(yùn)行，非專用機(jī)群中由于存在本地用戶和遠(yuǎn)地用戶對處理器的競爭，帶來了進(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)的，通過一個前端系統(tǒng)進(jìn)行集中式管理，常用來代替?zhèn)鹘y(tǒng)的大型超級計算機(jī)

29、系統(tǒng)；而企業(yè)型機(jī)群是松耦合的，一般由異構(gòu)節(jié)點(diǎn)構(gòu)成，節(jié)點(diǎn)可以有多個屬主，機(jī)群管理者對節(jié)點(diǎn)有有限的管理權(quán)。試解釋和例示一下有關(guān)單一系統(tǒng)映像的術(shù)語：1）單一文件層次結(jié)構(gòu)；2）單一控制點(diǎn)；3）單一存儲空間；4）單一進(jìn)程空間；5）單一輸入 / 輸出和網(wǎng)絡(luò)。答：1） 用戶進(jìn)入系統(tǒng)后所見的文件系統(tǒng)是一個單一的文件和目錄層次結(jié)構(gòu)，該系統(tǒng)透明的將本地磁盤、全局磁盤和其他文件設(shè)備結(jié)合起來。2） 整個機(jī)群可以從一個單一的節(jié)點(diǎn)對整個機(jī)群或某一單一的節(jié)點(diǎn)進(jìn)行管理和控制。3） 將機(jī)群中分布于各個節(jié)點(diǎn)的本地存儲器實(shí)現(xiàn)為一個大的、集中式的存儲器。4） 所有的用戶進(jìn)程，不管它們駐留在哪個節(jié)點(diǎn)上，都屬于一個單一的進(jìn)程空間，并且共

30、享一個統(tǒng)一的進(jìn)程識別方案。5） 單一輸入 / 輸出意味著任何節(jié)點(diǎn)均可訪問多個外設(shè)。單一網(wǎng)絡(luò)是任一節(jié)點(diǎn)能訪問機(jī)群中的任一網(wǎng)絡(luò)連接。就 Solaris MC 系統(tǒng)回答下列問題：1） Solaris MC支持習(xí)題中單一系統(tǒng)映像的哪些特征不支持哪些特征2）對那些Solaris MC支持的特征，解釋一下Solaris MC是如何解決的。答：1） 支持單一文件層次結(jié)構(gòu)、單一進(jìn)程空間、單一網(wǎng)絡(luò)和單一I/O 空間。不支持單一控制點(diǎn)和單一的存儲空間。2） Solaris使用了一個叫PXFS的全局文件系統(tǒng)GFS。PXFS文件系統(tǒng)的主要特點(diǎn)包括：單一系統(tǒng)映像、 一致的語義及高性能。PXFS通過在 VFS/vnode

31、 接口上截取文件訪問操作實(shí)現(xiàn)單一系統(tǒng)映像，保證了單一文件層次結(jié)構(gòu)。SolarisMC提供了一個全局進(jìn)程標(biāo)示符pid 可定位系統(tǒng)所有進(jìn)程，一個進(jìn)程可以遷移到其他節(jié)點(diǎn)，但它的宿主節(jié)點(diǎn)中總記錄有進(jìn)程的當(dāng)前位置，它通過在Solaris核心層上面增加一個全局進(jìn)程以實(shí)現(xiàn)單一進(jìn)程空間，每個節(jié)點(diǎn)有一個節(jié)點(diǎn)管理程序，每個本地進(jìn)程有一個虛擬進(jìn)程對象vproc ， vproc保留每個父進(jìn)程和子進(jìn)程的信息，實(shí)現(xiàn)了全局進(jìn)程的管理。單一網(wǎng)絡(luò)和I/O 空間通過一致設(shè)備命名技術(shù)和單一網(wǎng)絡(luò)技術(shù)實(shí)現(xiàn)。舉例解釋并比較以下有關(guān)機(jī)群作業(yè)管理系統(tǒng)的術(shù)語：1）串行作業(yè)與并行作業(yè)；2）批處理作業(yè)與交互式作業(yè)；3）機(jī)群作業(yè)和外來作業(yè)；4）專用

32、模式、空間共享模式、時間共享模式；5）獨(dú)立調(diào)度與組調(diào)度。答：1） 串行作業(yè)在單節(jié)點(diǎn)上運(yùn)行，并行作業(yè)使用多個節(jié)點(diǎn)。2） 批處理作業(yè)通常需要較多的資源，如大量的內(nèi)存和較長的CPU時間，但不需要迅速的反應(yīng)；交互式作業(yè)要求較快的周轉(zhuǎn)時間，其輸入輸出直接指向終端設(shè)備，這些工作一般不需要大量資源，用戶期望它們迅速得到執(zhí)行而不必放入隊列中。3） 機(jī)群作業(yè)時通過使用JMS功能分布實(shí)現(xiàn)的用戶作業(yè)，用戶服務(wù)器位于任一主機(jī)節(jié)點(diǎn)，資源管理器跨越所有的機(jī)群節(jié)點(diǎn)。外來作業(yè)在JMS之外生成的，如NOW上的一個工作站擁有者啟動的外部作業(yè)，它不提交給JMS。4） 專用模式：任一時候只有一個作業(yè)在機(jī)群上運(yùn)行，任一時候也只有一個作

33、業(yè)進(jìn)程分配給一個節(jié)點(diǎn)?？臻g共享模式：多個作業(yè)可以在不重疊的節(jié)點(diǎn)區(qū)域上運(yùn)行。時間共享模式：在專用模式和空間共享模式下，只有一個用戶進(jìn)程分配給一個節(jié)點(diǎn)，但是所有的系統(tǒng)進(jìn)程或監(jiān)護(hù)程序仍在同一個節(jié)點(diǎn)上運(yùn)行。5） 獨(dú)立調(diào)度：各節(jié)點(diǎn)OS 進(jìn)行自己的調(diào)度，但這會顯著損壞并行作業(yè)的性能，因?yàn)椴⑿凶鳂I(yè)的進(jìn)程間需要交互。組調(diào)度：將并行作業(yè)的所有進(jìn)程一起調(diào)度。一個進(jìn)程激活時，所有進(jìn)程都被激活。針對 LSF回答下列問題：1）對 LSF的四種作業(yè)類型各舉一個例子；2）舉一個例子說明外來作業(yè)；3）對一個有1000 個服務(wù)器的機(jī)群， 為什么 LSF負(fù)載分配機(jī)制優(yōu)于：1 整個機(jī)群只有一個LIM或者 2 所有 LIM 都是主機(jī)

34、說明原因。答：1） 交互式：用戶使用lshosts命令就可以列出每個服務(wù)器節(jié)點(diǎn)的靜態(tài)資源，實(shí)現(xiàn)交互。批處理： lsbatch實(shí)用程序允許通過LSF 提交、監(jiān)控和執(zhí)行批處理作業(yè)。串行：用戶一旦進(jìn)入 lstcsh shell，發(fā)送的每條命令自動在最適合的節(jié)點(diǎn)上執(zhí)行。并行：lsmake 實(shí)用程序是 UNIX make 實(shí)用程序時一個并行版本，允許在多個節(jié)點(diǎn)同時處理一個Makefile。2） 不通過 LSF執(zhí)行的稱為外來作業(yè)。例如執(zhí)行一些本地作業(yè)：字處理，web 網(wǎng)絡(luò)瀏覽等。3） 機(jī)群的服務(wù)器數(shù)目太多，如果只采用一個LIM 會導(dǎo)致 LIM 的負(fù)責(zé)過重，不能及時的處理響應(yīng)所有服務(wù)器的請求和分派所有機(jī)群作

35、業(yè)；如果采用2 會導(dǎo)致 LIM 之間相互交換負(fù)載信息過多，導(dǎo)致網(wǎng)絡(luò)通信量過大。為什么在分布式文件系統(tǒng)中，UNIX 語義難以實(shí)現(xiàn)有哪些放松的文件共享語義采用放松的文件共享語義會有一些什么缺點(diǎn)答：在 UNIX 語義中，一個修改過的塊應(yīng)該立刻被所有其他應(yīng)用程序見到。然而分布式的文件系統(tǒng)中， 多個節(jié)點(diǎn)可能存放了同一文件塊的拷貝，當(dāng)其中一個節(jié)點(diǎn)修改文件可的拷貝時，其他節(jié)點(diǎn)不能立刻就知道，這就使得UNIX語義難以實(shí)現(xiàn)。放松的文件共享語義有：對話語義、類事物語義、 不可改變的共享文件語義等。采用放松的文件共享語義要求應(yīng)用程序員修改程序代碼，以適用這種新的語義，這就增加了程序員的負(fù)擔(dān)。試解釋在機(jī)群并行文件系統(tǒng)

36、中，為什么采用軟件RAID、高速緩存機(jī)制和預(yù)取能夠提高文件系統(tǒng)性能。答：軟件 RAID 是文件系統(tǒng)負(fù)責(zé)分布數(shù)據(jù)和維護(hù)容錯級別，能夠和RAID5 有一樣的性能，實(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)性能。這討論并行文件系統(tǒng)協(xié)作化高速緩存的基本技術(shù)前提是什么這個前提有什么意義答：基本技術(shù)前提是互聯(lián)網(wǎng)絡(luò)的速度很快，一個節(jié)點(diǎn)需要的文件塊在其他節(jié)點(diǎn)的緩存中

37、，那么就不需要從磁盤讀， 而是直接從其他節(jié)點(diǎn)的緩存中讀出。這個前提的意義是可以提高系統(tǒng)的性能，使得節(jié)點(diǎn)間的協(xié)作化緩存變得更有意義?；卮鹨韵玛P(guān)于Berkeley NOW 項目的問題：1） BerkeleyNOW項目支持單一系統(tǒng)映像的哪幾個方面即單入口點(diǎn)、單文件層次結(jié)構(gòu)、單控制點(diǎn)、單存儲空間、單進(jìn)程空間哪個的哪幾項并解釋如何支持。2）解釋 Berkeley NOW 項目用來提高性能的四個結(jié)構(gòu)特征。3）解釋 Berkeley NOW 項目和 SP機(jī)群四個體系結(jié)構(gòu)的差異，并討論各自的優(yōu)點(diǎn)。答：1） 通過用戶級整個機(jī)群軟件GLUNIX，提供單一系統(tǒng)映像。開發(fā)了一種新的無服務(wù)器網(wǎng)絡(luò)文件系統(tǒng) xFS，以支持

38、單一文件層次結(jié)構(gòu)。2） 主動消息通信協(xié)議，支持有效的通信；機(jī)群軟件GLUNIX 提供單一的系統(tǒng)映像、資源管理和可用性； xFS 支持可擴(kuò)放性和單一文件層次結(jié)構(gòu)的高可用性；軟件框架WebOS構(gòu)筑高可用性、漸增可擴(kuò)放性。3） SP 機(jī)群的體系結(jié)構(gòu)特征：每個節(jié)點(diǎn)都是RS/600 工作站，并有自己的局部磁盤；每個節(jié)點(diǎn)內(nèi)駐留一個完整的AIX；各節(jié)點(diǎn)通過其I/O 總線連接到專門設(shè)計的多級高速網(wǎng)絡(luò)；盡量使用標(biāo)準(zhǔn)工作站部件。這樣的優(yōu)點(diǎn)是簡單性和靈活性?？紤] xFS，并回答下列問題：1）解釋 xFS 和集中式文件服務(wù)器的兩個不同點(diǎn)，并討論各自的優(yōu)點(diǎn)；2）解釋 xFS 用來提高可用性的主要技術(shù)；3）解釋 xFS

39、用來減輕小寫問題的主要技術(shù)。答：1） 無服務(wù)器文件系統(tǒng)xFS 將文件服務(wù)的功能分布到機(jī)器的所有節(jié)點(diǎn)上，xFS 中所有的服務(wù)器和客戶的功能由分散的所有節(jié)點(diǎn)實(shí)現(xiàn)之。這與集中文件服務(wù)器的中央存儲、中央緩存、中央管理不同。xFS 的優(yōu)點(diǎn)是采用分布式管理和協(xié)同文件緩存以及冗余磁盤陣列，這提高了系統(tǒng)的可用性以及I/O 的性能和吞吐量。 集中式文件服務(wù)器會減少緩存的不一致性，管理簡單。2） xFS 提高可用性的主要技術(shù)是采用廉價冗余磁盤陣列RAID。無工作站文件系統(tǒng)能用來生成軟件 RAID，以提高性能和高可用性?，F(xiàn)在 xFS 使用單奇偶校驗(yàn)磁盤條。一個文件數(shù)據(jù)塊在多個存儲服務(wù)器節(jié)點(diǎn)上按條劃分，在另一個節(jié)點(diǎn)上

40、有奇偶校驗(yàn)塊。如果一個節(jié)點(diǎn)失效，失效磁盤的內(nèi)容，可利用其余盤和奇偶盤之異或操作重建之。3） xFS 使用日志條的方法解決小寫問題：每個用戶首先將寫接合到各用戶的日志上；然后此日志采用日志段提交給磁盤，每個段系由K-1 個日志片組成，它與奇偶校驗(yàn)片以道送給 K 個存儲服務(wù)器。第七章分布式共享存儲系統(tǒng)什么是分布式共享存儲系統(tǒng)，它相對于共享存儲系統(tǒng)與分布式系統(tǒng)有哪些優(yōu)點(diǎn)答：分布式共享存儲系統(tǒng)，是把共享存儲器分成許多模塊并分布于各處理機(jī)之中。分布式系統(tǒng)中采用消息傳遞通信，性能提高了， 但多地址空間不利于程序員編程。共享存儲系統(tǒng)支持傳統(tǒng)的單地址空間，但共享必然引起沖突，形成瓶頸， 于是分布式共享存儲系統(tǒng)

41、結(jié)合兩者的優(yōu)點(diǎn)。釋放一致性模型(RC) 把處理器一致性(PC) 和弱一致性模型(WC)的優(yōu)點(diǎn)結(jié)合在一起了。試回答下面有關(guān)這些一致性模型的問題：a) 比較這三種一致性模型的實(shí)現(xiàn)要求。b) 評論每種一致性模型的優(yōu)缺點(diǎn)。答：a) 處理器一致性要求：在任一取數(shù)操作LOAD允許被執(zhí)行之前，所有在同一處理器中先于這一 LOAD的取數(shù)操作都已完成；在任一存數(shù)操作STORE允許執(zhí)行之前，所有在同一處理器中先于這一 STORE的訪存操作 （包括取數(shù)操作和存數(shù)操作）都已完成。 弱一致性模型要求：同步操作的執(zhí)行滿足順序一致性條件；在任一普通訪存操作允許被執(zhí)行之前，所有在同一處理器中先于這一訪存操作的同步操作都已完成

42、；在任一同步操作允許被執(zhí)行之前，所有在同一處理器中先于這一同步操作的普通訪存操作都已完成。 釋放一致性模型要求： 在任一普通訪存操作允許被執(zhí)行之前，所有在同一處理器中先于這一訪存操作的獲取操作acquire 都已完成； 在任一釋放操作release 允許被執(zhí)行之前，所有在同一處理器中先于這一 release 的普通訪存操作都已完成；同步操作的執(zhí)行滿足順序一致性條件。b) 三種模型對存儲順序要求逐漸降低， 可優(yōu)化程度逐漸增加， 但是對程序員的要求也越來越高，所以釋放性一致性是性能與復(fù)雜度的折中。在 DSM系統(tǒng)的順序一致性存儲模型下，有三個并行執(zhí)行的進(jìn)程如下所示，試問001110 是不是一個合法的

43、輸出并加以解釋。P1P2P3A=1;B=1;C=1;Print(b,c);Print(a,c);Print(a,b);答：不是一個合法輸出?？紤]順序一致性存儲模型，每個進(jìn)程的程序序會被維護(hù)，那么無論哪個進(jìn)程最后執(zhí)行Print語句，則之前的A=1， B=1,C=1 都已經(jīng)完成，所以輸出的兩后兩項必為 11，所以 001110 不是合法輸出。試分類下面來自三個處理器的引用流的高速緩存缺失。假設(shè)每一個處理器的高速緩存只有一個 4 個字的高速緩存行，字 W0到 W3、 W4到 W7分別處于同一個高速緩存行。如果一行有多個引用，我們假設(shè)P1 在 P2 之前發(fā)射、 P2 在 P3 之前發(fā)射內(nèi)存引用，符號L

44、D/ST Wi表示 LOAD/STORE字 i 。操作序號P1P2P31ST W0ST W72LD W6LD W23LD W74LD W2LD W05ST W26LD W27ST W2LD W5LDW58ST W59LD W3LD W710LD W6LD W211LD W2ST W712LD W713LD W214LD W515LD W2答：操作序號3、6、8、12-15 都是單操作。操作序號 1、2、 9-11 為無關(guān)存儲操作，由于不在同一塊中。操作序號4、 7 為對同一緩存塊的連續(xù)兩次LD，需要按序進(jìn)行。假設(shè)系統(tǒng)中共有緩存行的大小為512 個處理器和64 字節(jié)，那么在1GB主存，每個節(jié)點(diǎn)內(nèi)

45、有8 個處理器對目錄可見，一個高速(a)滿位向量方案和(b)Dri B(i=3) 模型下目錄的存儲成本各是多少答：分別為總?cè)萘康?2.%和 %。細(xì)數(shù)一下中心目錄與分布式目錄方案的實(shí)現(xiàn)方法與各自的使用情況。答：中心目錄是用一個中心目錄存放所有高速緩存目錄的拷貝，中心目錄能提供為保證一致性所需要的全部信息。因此，其容量非常大且必須采用聯(lián)想方法進(jìn)行檢索，這和單個高速緩存的目錄類似。大型多處理機(jī)系統(tǒng)采用中心目錄會有沖突和檢索時間過長兩個缺點(diǎn)。分布式目錄方案是由Censier和 Feautrier提出來。在分布式目錄中每個存儲器模塊維護(hù)各自的目錄，目錄中記錄著每個存儲器塊的狀態(tài)和當(dāng)前的信息，其中狀態(tài)信息是本