并行計算(陳國良版)課后答案解析

.PAGE第三章互連網絡3.1對于一顆K級二叉樹（根為0級，葉為k-1級），共有N=2^k-1個節(jié)點，當推廣至m-元樹時（即每個非葉節(jié)點有m個子節(jié)點）時，試寫出總節(jié)點數N的表達式。答：推廣至M元樹時，k級M元樹總結點數N的表達式為：N=1+m^1+m^2+...+m^（k-1）=(1-m^k)*1/(1-m);3.2二元胖樹如圖3.46所示，此時所有非根節(jié)點均有2個父節(jié)點。如果將圖中的每個橢圓均視為單個節(jié)點，并且成對節(jié)點間的多條邊視為一條邊，則他實際上就是一個二叉樹。試問：如果不管橢圓，只把小方塊視為節(jié)點，則他從葉到根形成什么樣的多級互聯網絡？答：8輸入的完全混洗三級互聯網絡。3.3四元胖樹如圖3.47所示，試問：每個內節(jié)點有幾個子節(jié)點和幾個父節(jié)點？你知道那個機器使用了此種形式的胖樹？答：每個內節(jié)點有4個子節(jié)點，2個父節(jié)點。CM-5使用了此類胖樹結構。3.4試構造一個N=64的立方環(huán)網絡，并將其直徑和節(jié)點度與N=64的超立方比較之，你的結論是什么？答：AN=64的立方環(huán)網絡,為4立方環(huán)（將4維超立方每個頂點以4面體替代得到），直徑d=9，節(jié)點度n=4BN=64的超立方網絡，為六維超立方（將一個立方體分為8個小立方，以每個小立方作為簡單立方體的節(jié)點，互聯成6維超立方），直徑d=6，節(jié)點度n=63.5一個N=2^k個節(jié)點的deBruijin網絡如圖3.48所示，令。。。，是一個節(jié)點的二進制表示，則該節(jié)點可達如下兩個節(jié)點：。。。0，。。。1。試問：該網絡的直徑和對剖寬度是多少？答：N=2^k個節(jié)點的deBruijin網絡直徑d=k對剖寬帶w=2^(k-1)3.6一個N=2^n個節(jié)點的洗牌交換網絡如圖3.49所示。試問：此網絡節(jié)點度==？網絡直徑==？網絡對剖寬度==？答：N=2^n個節(jié)點的洗牌交換網絡，網絡節(jié)點度為=2，網絡直徑=n-1，網絡對剖寬度=43.7一個N=（k+1）2^k個節(jié)點的蝶形網絡如圖3.50所示。試問：此網絡節(jié)點度=？網絡直徑=？網絡對剖寬度=？答：N=（k+1）2^k個節(jié)點的蝶形網絡，網絡節(jié)點度=4，網絡直徑=2*k，網絡對剖寬度=2^k3.9對于如下列舉的網絡技術，用體系結構描述，速率范圍，電纜長度等填充下表中的各項。（提示：根據討論的時間年限，每項可能是一個范圍）答：網絡技術網絡結構帶寬銅線距離光纖距離Myrinet專用機群互聯網絡200MB/秒25m500mHiPPI用于異構計算機和其外設的組網800Mbps~1.6Gbps25m300m~10kmSCI可擴展一致性接口，通常獨立于拓撲結構250Mbps~8Gbps光纖通信多處理器和其外圍設備之間，直連結構100Mbps~800Mbps50m10kmATM主要應用于因特網主干線中25Mbps~10GbpsFDDI采用雙向光纖令牌環(huán)，所有結點聯接在該環(huán)中100-200Mbps100m2KM3.10如圖3.51所示，信包的片0，1，2，3要分別去向目的地A，B，C，D。此時片0占據信道CB，片1占據信道DC，片2占據信道AD，片3占據信道BA。試問：1）這將會發(fā)生什么現象？2）如果采用X-Y選路策略，可避免上述現象嗎？為什么？答：1）通路中形成環(huán)，發(fā)生死鎖2）如果采用X-Y策略則不會發(fā)生死鎖。因為采用X-Y策略時其實質是對資源（這里是通道）進行按序分配（永遠是x方向優(yōu)先于y方向，反方向路由是y方向優(yōu)先于x方向），因此根據死鎖避免的原則判斷，此時不會發(fā)生死鎖。3.12在二維網孔中，試構造一個與X-Y選路等價的查表路由。答：所構造路由表描述如下：1）每個節(jié)點包括兩張路由表x表和y表2）每個節(jié)點包含其以后節(jié)點信息，如節(jié)點【1，2】x表內容為:【2，2】【3，2】y表內容為：【1，3】選路方法：節(jié)點路由時進行查表：先查x表即進行x方向路由，如果查表能指明下一跳方向則直接進入下一跳。如果不能則繼續(xù)查y表，直到到達目的地。第四章對稱多處理機系統4.1參照圖4.20，試解釋為什么采用WT策略進程從遷移到時，或采用WB策略將包含共享變量X的進程從遷移到時，會造成高速緩存的不一致。圖4.20進程遷移所造成的不一致性答：采用WT策略進程從遷移到后，寫共享變量X為X’，并且更新主存數據為X’，此時共享變量值仍然為X，與和主存X’不一致。采用WB策略進程從遷移到后，寫共享變量X為X’，但此時緩存與主存變量值仍然為X，造車不一致。4.2參照圖4.21所示，試解釋為什么：①在采用WT策略的高速緩存中，當I/O處理器將一個新的數據寫回主存時會造成高速緩存和主存間的不一致；②在采用WB策略的高速緩存中，當直接從主存輸出數據時會造成不一致。圖4.21繞過高速緩存的I/O操作所造成的不一致性答：①中I/O處理器將數據X’寫回主存，因為高速緩存采用WT策略，此時P1和P2相應的高速緩存值還是X，所以造成高速緩存與主存不一致。②直接從主存輸出數據X，因為高速緩存采用WB策略，可能高速緩存中的數據已經被修改過，所以造成不一致。試解釋采用WB策略的寫更新和寫無效協議的一致性維護過程。其中為更新前高速緩存中的拷貝，為修改后的高速緩存塊，I為無效的高速緩存塊。答：處理器P1寫共享變量X為X’，寫更新協議如圖(c)所示，同時更新其他核中存在高速緩存拷貝的值為X’;寫無效協議如圖(b)所示，無效其他核中存在高速緩存拷貝，從而維護了一致性過程。兩種基于總線的共享內存多處理機分別實現了IllinoisMESI協議和Dragon協議，對于下面給定的每個內存存取序列，試比較在這兩種多處理機上的執(zhí)行代價，并就序列及一致性協議的特點來說明為什么有這樣的性能差別。序列①r1w1r1w1r2w2r2w2r3w3r3w3；序列②r1r2r3w1w2w3r1r2r3w3w1；序列③r1r2r3r3w1w1w1w1w2w3；所有的存取操作都針對同一個內存位置，r/w代表讀/寫，數字代表發(fā)出該操作的處理器。假設所有高速緩存在開始時是空的，并且使用下面的性能模型：讀/寫高速緩存命中，代價1個時鐘周期；缺失引起簡單的總線事務（如BusUpgr，BusUpd），60個時鐘周期；缺失引起整個高速緩存塊傳輸，90時鐘周期。假設所有高速緩存是寫回式。答：讀寫命中、總線事務、塊傳輸分別簡記為H、B、T。MESI協議：①BTHHHHBTHBHHHBTHBHHH共5B+12H+3T=582時鐘周期②BTHBTHBTHBHBTHBTHBTHBTHHBHBTH共10B+12H+8T=1330時鐘周期③BTHBTHBTHHBHHHHBTHBTH共6B+10H+4T=730時鐘周期。Dragon協議：①BTHHHHBTHBTHHBTHBTHBTHHBTH共7B+12H+7T=882時鐘周期②BTHBTHBTHBTHBTHBTHHHHHBTTHBTH共8B+12H+8T=1212時鐘周期③BTHBTHBTHHBTHBTHBTHBTHBTHBTH共9B+10H+9T=1360時鐘周期。由結果得出，①、③序列用MESI協議時間更少，而②序列用Dragon協議時間更少。綜上可知，如果同一塊在寫操作之后頻繁被多個核讀操作采用Dragon協議更好一些，因為Dragon協議寫操作后會更新其它核副本。如果一個同多次連續(xù)對同一塊進行寫操作MESI協議更有效，因為它不需要更新其它核副本，只需要總線事務無效其它核即可。4.5考慮以下代碼段，說明在順序一致性模型下，可能的結果是什么？假設在代碼開始執(zhí)行時，所有變量初始化為0。a.P1P2P3A=1U=AV=BB=1W=Ab.P1P2P3P4A=1U=AB=1W=BV=BX=A答：順序一致性模型性下，保護每個進程都按程序序來發(fā)生內存操作，這樣會有多種可能結果，這里假設最簡單情況，即P1、P2、P3依次進行。則a中U=V=W=1，b中U=X=W=1，V=0。參照4.6.1中討論多級高速緩存包含性的術語，假設L1和L2都是2-路組相聯，n2>n1，b1=b2，且替換策略用FIFO來代替LRU，試問包含性是否還是自然滿足？如果替換策略是隨機替換呢？答：如果采用FIFO替換策略包含性自然滿足，因為L1和L2都是2路組相聯，FIFO保證了L1與L2在發(fā)生替換時會換出相同的緩存塊，維護了包含性。如果采取隨機替換策略，存在L1與L2替換不是相同塊的情況，故不滿足包含性。針對以下高速緩存情況，試給出一個使得高速緩存的包含性不滿足的內存存取序列？L1高速緩存容量32字節(jié)，2-路組相聯，每個高速緩存塊8個字節(jié)，使用LRU替換算法；L2高速緩存容量128字節(jié)，4-路組相聯，每個高速緩存塊8個字節(jié)，使用LRU替換算法。答：假設m1、m2、m3塊映射到一級Cache和二級Cache的同一組中，考慮如下內存存取序列Rm1，Rm2，Rm1，Rm3，由LRU替換算法知道，當Rm3執(zhí)行后，L1中被替換出的是m2，L2中被替換出的是m1，此時m1塊在L1卻不在L2中，不滿足包含性。在4.6中關于分事務總線的討論中，依賴于處理器與高速緩存的接口，下面情況有可能發(fā)生：一個使無效請求緊跟在數據響應之后，使得處理器還沒有真正存取這個高速緩存塊之前，該高速緩存塊就被使無效了。為什么會發(fā)生這種情況，如何解決?答：考慮如下情景：SMP目錄一致性協議中，核1讀缺失請求數據塊A，主存響應請求傳送數據塊A給核1，同時核2對數據塊A進行寫操作，到主存中查得核1擁有副本，向核1發(fā)使無效請求。如此，一個使無效請求緊跟在數據響應之后。解決方法，可以使每個核真正存取高速緩存塊后向主存發(fā)回應，然后再允許其它對此塊操作的使無效或其它請求。利用LL-SC操作實現一個Test&Set操作。答：Test&Set：llreg1,location/*Load-lockedthelocationtoreg1*/bnzreg1,lock/*iflocatinwaslocked,tryagain*/movreg2,1/*setreg21*/sclocation,reg2/*storereg2conditionalintolocation*/在4.7.4部分描述具有感覺反轉的路障算法中，如果將Unlock語句不放在if條件語句的每個分支中，而是緊接放在計數器增1語句后，會發(fā)生什么問題？為什么會發(fā)生這個問題？答：再進入下一個路障時可能會發(fā)生計數器重新清0現象，導致無法越過路障。考慮如下情景：第一次進入路障時，最后兩個進入路障的進程分別為1、2。假設最后進入路障的進程為2進程，2進程執(zhí)行共享變量加一操作并解鎖。然后2進程執(zhí)行一條if條件語句，此時由于某種原因換出或睡眠，而此時共享變量的值已經為p。如果1進程此時正執(zhí)行if條件語句，則清零計數器，設置標志，其它進程越過路障。到目前為止沒有出現問題，問題出現在下一次進入路障。進程再一次進入路障，此時會執(zhí)行共享變量加一操作。如果此時2進程被換入或被喚醒，會重新清零共享變量，使之前到達路障的進程的加一操作無效，導致無法越過路障。第五章大規(guī)模并行處理機系統5.1簡述大規(guī)模并行處理機的定義，原理和優(yōu)點？答：并行處理機有時也稱為陣列處理機，它使用按地址訪問的隨機存儲器，以單指令流多數據流方式工作，主要用于要求大量高速進行向量矩陣運算的應用領域。并行處理機的并行性來源于資源重復，它把大量相同的處理單元（PE）通過互聯網絡（ICN）連接起來，在統一的控制器（CU）控制下，對各自分配來的數據并行地完成同一條指令所規(guī)定的操作。PE是不帶指令控制部件的算術邏輯運算單元。并行處理機具有強大的向量運算能力，具有向量化功能的高級語言編譯程序有助于提高并行處理機的通用性，減少編譯時間。5.2并行處理機有兩種基本結構類型，請問是哪兩種？并作簡單介紹。答：采用分布存儲器的并行處理結構和采用集中式共享存儲器的并行處理結構。分布式存儲器的并行處理結構中，每一個處理機都有自己的存儲器，只要控制部件將并行處理的程序分配至各處理機，它們便能并行處理，各自從自己的存儲器中取得信息。而共享存儲多處理機結構中的存儲器是集中共享的，由于多個處理機共享，在各處理機訪問共享存儲器時會發(fā)生競爭。因此，需采取措施盡可能避免競爭的發(fā)生。5.3簡單說明多計算機系統和多處理機系統的區(qū)別。答：他們雖然都屬于多機系統但是他們區(qū)別在于：（1）多處理機是多臺處理機組成的單機系統，多計算機是多臺獨立的計算機。（2）多處理機中各處理機邏輯上受同一的OS控制，而多計算機的OS邏輯上獨立.(3)多處理機間以單一數據，向量。數組和文件交互作用，多計算機經通道或者通信線路以數據傳輸的方式進行。（4）多處理機作業(yè)，任務，指令，數據各級并行，多計算機多個作業(yè)并行。5.4舉例說明MPP的應用領域及其采用的關鍵技術。答：全球氣候預報，基因工程，飛行動力學，海洋環(huán)流，流體動力學，超導建模，量子染色動力學，視覺。采用的關鍵技術有VLSI，可擴張技術，共享虛擬存儲技術。5.5多處理機的主要特點包括答：（1）結構的靈活性。與SIMD計算機相比，多處理機的結構具有較強的通用性，它可以同時對多個數組或多個標量數據進行不同的處理，這要求多處理機能夠適應更為多樣的算法，具有靈活多變的系統結構。2）程序并行性。并行處理機實現操作一級的并行，其并行性存在于指令內部，主要用來解決數組向量問題；而多處理機的并行性體現在指令外部，即表現在多個任務之間。3）并行任務派生。多處理機是多指令流操作方式，一個程序中就存在多個并發(fā)的程序段，需要專門的程序段來表示它們的并發(fā)關系以控制它們的并發(fā)執(zhí)行，這稱為并行任務派生。4）進程同步。并行處理機實現操作級的并行，所有處于活動狀態(tài)的處理單元受一個控制器控制，同時執(zhí)行共同的指令，工作自然同步；而多處理機實現指令、任務、程序級的并行，在同一時刻，不同的處理機執(zhí)行著不同的指令，進程之間的數據相關和控制依賴決定了要采取一定的進程同步策略。5.6在并行多處理機系統中的私有Cache會引起Cache中的內容相互之間以及與共享存儲器之間互不相同的問題，即多處理機的Cache一致性問題。請問有哪些原因導致這個問題？答：出現Cache一致性問題的原因主要有三個：共享可寫的數據、進程遷移、I/O傳輸。共享可寫數據引起的不一致性。比如P1、P2兩臺處理機各自的本地高速緩沖存儲器C1、C2中都有共享存儲器是M中某個數據X的拷貝，當P1把X的值變成X/后，如果P1采用寫通過策略，內存中的數據也變?yōu)閄/，C2中還是X。如果通過寫回策略，這是內存中還是X。在這兩種情況下都會發(fā)生數據不一致性。2）進程遷移引起的數據不一致性。P1中有共享數據X的拷貝，某時刻P1進程把它修改為X/并采用了寫回策略，由于某種原因進程從P1遷移到了P2上，它讀取數據時得到X，而這個X是“過時”的。3）I/O傳輸所造成的數據不一致性。假設P1和P2的本地緩存C1、C2中都有某數據X的拷貝，當I/O處理機將一個新的數據X/寫入內存時，就導致了內存和Cache之間的數據不一致性。5.7分別確定在下列兩種計算機系統中，計算表達式所需的時間：s=A1*B1+A2*B2+…A4*B4。a)有4個處理器的SIMD系統；b)有4個處理機的MIMD系統。假設訪存取指和取數的時間可以忽略不計；加法與乘法分別需要2拍和4拍；在SIMD和MIMD系統中處理器（機）之間每進行一次數據傳送的時間為1拍；在SIMD系統中，PE之間采用線性環(huán)形互連拓撲，即每個PE與其左右兩個相鄰的PE直接相連，而在MIMD中每個PE都可以和其它PE有直接的的通路。答：假設4個PE分別為PE0，PE1，PE2，PE3。利用SIMD計算機計算上述表達式，4個乘法可以同時進行，用時=4個時間單位；然后進行PE0到PE1，PE2到PE3的數據傳送，用時=1個時間單位。在PE1和PE3中形成部分和，用時=2個時間單位。接著進行PE1到PE3的部分和傳送，用時=1*2=2個時間單位。最后，在PE3中形成最終結果，用時=2個時間單位。因此，利用SIMD計算機計算上述表達式總共用時=4（乘法）+1（傳送）+2（加法）+2（傳送）+2（加法）=11個時間單位。而利用MIMD計算機計算上述表達式，除了在第二次傳送節(jié)省1個時間單位以外，其他與SIMD相同。因此用時=4（乘法）+1（傳送）+2（加法）+1（傳送）+2（加法）=10個時間單位。5.8假定有一個處理機臺數為p的共享存儲器多處理機系統。設m為典型處理機每條執(zhí)行執(zhí)行時間對全局存儲器進行訪問的平均次數。 設t為共享存儲器的平均存儲時間，x為使用本地存儲器的單處理機MIPS速率，再假定在多處理機上執(zhí)行n條指令。現在假設p=32,m=0.4,t=1μs,要讓多處理機的有效性能達到56MIPS，需要每臺處理機的MIPS效率是多少？A.2B.4C.5.83D.40答：B5.9試在含一個PE的SISD機和在含n個PE且連接成一線性環(huán)的SIMD機上計算下列求內積的表達式：其中n=2k假設完成每次ADD操作需要2個單元時間，完成每次MULTIPLY操作需要4個單位時間，沿雙向環(huán)在相鄰PE間移數需1個單位時間SISD計算機上計算s需要多少時間SIMD計算機上計算s需要多少時間SIMD機計算s相對于SISD計算的加速比是多少？答：4n+2(n-1)5.10如果一臺SIMD計算機和一臺流水線處理機具有相同的計算性能，對構成它們的主要部件分別有什么要求？答：一臺具有n個處理單元的SIMD計算機與一臺具有一條n級流水線并且時鐘周期為前者1/n的流水線處理機的計算性能相當，兩者均是每個時鐘周期產生n個計算結果。但是，SIMD計算機需要n倍的硬件（n個處理單元），而流水線處理機中流水線部件的時鐘速率要求比前者快n倍，同時還需要存儲器的帶寬也是前者的n倍。第六章機群系統6.1試區(qū)分和例示下列關于機群的術語：1）專用機群和非專用機群；2）同構機群和異構機群；3）專用型機群和企業(yè)型機群。答：根據節(jié)點的擁有情況，分為專用機群和非專用機群，在專用機群中所有的資源是共享的，并行應用可以在整個機群上運行，而在非專用機群中，全局應用通過竊取CPU時間獲得運行，非專用機群中由于存在本地用戶和遠地用戶對處理器的競爭，帶來了進程遷移和負載平衡問題。根據節(jié)點的配置分為同構機群和異構機群，同構機群中各節(jié)點有相似的的體系，并且使用相同的操作系統，而異構機群中節(jié)點可以有不同的體系，運行的操作系統也可以不同。專用型機群的特點是緊耦合的、同構的，通過一個前端系統進行集中式管理，常用來代替?zhèn)鹘y的大型超級計算機系統；而企業(yè)型機群是松耦合的，一般由異構節(jié)點構成，節(jié)點可以有多個屬主，機群管理者對節(jié)點有有限的管理權。6.2試解釋和例示一下有關單一系統映像的術語：1）單一文件層次結構；2）單一控制點；3）單一存儲空間；4）單一進程空間；5）單一輸入/輸出和網絡。答：用戶進入系統后所見的文件系統是一個單一的文件和目錄層次結構，該系統透明的將本地磁盤、全局磁盤和其他文件設備結合起來。整個機群可以從一個單一的節(jié)點對整個機群或某一單一的節(jié)點進行管理和控制。將機群中分布于各個節(jié)點的本地存儲器實現為一個大的、集中式的存儲器。所有的用戶進程，不管它們駐留在哪個節(jié)點上，都屬于一個單一的進程空間，并且共享一個統一的進程識別方案。單一輸入/輸出意味著任何節(jié)點均可訪問多個外設。單一網絡是任一節(jié)點能訪問機群中的任一網絡連接。6.3就SolarisMC系統回答下列問題：1）SolarisMC支持習題6.2中單一系統映像的哪些特征？不支持哪些特征？2）對那些SolarisMC支持的特征，解釋一下SolarisMC是如何解決的。答：支持單一文件層次結構、單一進程空間、單一網絡和單一I/O空間。不支持單一控制點和單一的存儲空間。Solaris使用了一個叫PXFS的全局文件系統GFS。PXFS文件系統的主要特點包括：單一系統映像、一致的語義及高性能。PXFS通過在VFS/vnode接口上截取文件訪問操作實現單一系統映像，保證了單一文件層次結構。SolarisMC提供了一個全局進程標示符pid可定位系統所有進程，一個進程可以遷移到其他節(jié)點，但它的宿主節(jié)點中總記錄有進程的當前位置，它通過在Solaris核心層上面增加一個全局進程以實現單一進程空間，每個節(jié)點有一個節(jié)點管理程序，每個本地進程有一個虛擬進程對象vproc，vproc保留每個父進程和子進程的信息，實現了全局進程的管理。單一網絡和I/O空間通過一致設備命名技術和單一網絡技術實現。6.4舉例解釋并比較以下有關機群作業(yè)管理系統的術語：1）串行作業(yè)與并行作業(yè)；2）批處理作業(yè)與交互式作業(yè)；3）機群作業(yè)和外來作業(yè)；4）專用模式、空間共享模式、時間共享模式；5）獨立調度與組調度。答：串行作業(yè)在單節(jié)點上運行，并行作業(yè)使用多個節(jié)點。批處理作業(yè)通常需要較多的資源，如大量的內存和較長的CPU時間，但不需要迅速的反應；交互式作業(yè)要求較快的周轉時間，其輸入輸出直接指向終端設備，這些工作一般不需要大量資源，用戶期望它們迅速得到執(zhí)行而不必放入隊列中。機群作業(yè)時通過使用JMS功能分布實現的用戶作業(yè)，用戶服務器位于任一主機節(jié)點，資源管理器跨越所有的機群節(jié)點。外來作業(yè)在JMS之外生成的，如NOW上的一個工作站擁有者啟動的外部作業(yè)，它不提交給JMS。專用模式：任一時候只有一個作業(yè)在機群上運行，任一時候也只有一個作業(yè)進程分配給一個節(jié)點。空間共享模式：多個作業(yè)可以在不重疊的節(jié)點區(qū)域上運行。時間共享模式：在專用模式和空間共享模式下，只有一個用戶進程分配給一個節(jié)點，但是所有的系統進程或監(jiān)護程序仍在同一個節(jié)點上運行。獨立調度：各節(jié)點OS進行自己的調度，但這會顯著損壞并行作業(yè)的性能，因為并行作業(yè)的進程間需要交互。組調度：將并行作業(yè)的所有進程一起調度。一個進程激活時，所有進程都被激活。6.5針對LSF回答下列問題：1）對LSF的四種作業(yè)類型各舉一個例子；2）舉一個例子說明外來作業(yè)；3）對一個有1000個服務器的機群，為什么LSF負載分配機制優(yōu)于：1整個機群只有一個LIM或者2所有LIM都是主機？說明原因。答：交互式：用戶使用lshosts命令就可以列出每個服務器節(jié)點的靜態(tài)資源，實現交互。批處理：lsbatch實用程序允許通過LSF提交、監(jiān)控和執(zhí)行批處理作業(yè)。串行：用戶一旦進入lstcshshell，發(fā)送的每條命令自動在最適合的節(jié)點上執(zhí)行。并行：lsmake實用程序是UNIXmake實用程序時一個并行版本，允許在多個節(jié)點同時處理一個Makefile。不通過LSF執(zhí)行的稱為外來作業(yè)。例如執(zhí)行一些本地作業(yè)：字處理，web網絡瀏覽等。機群的服務器數目太多，如果只采用一個LIM會導致LIM的負責過重，不能及時的處理響應所有服務器的請求和分派所有機群作業(yè)；如果采用2會導致LIM之間相互交換負載信息過多，導致網絡通信量過大。6.6為什么在分布式文件系統中，UNIX語義難以實現？有哪些放松的文件共享語義？采用放松的文件共享語義會有一些什么缺點？答：在UNIX語義中，一個修改過的塊應該立刻被所有其他應用程序見到。然而分布式的文件系統中，多個節(jié)點可能存放了同一文件塊的拷貝，當其中一個節(jié)點修改文件可的拷貝時，其他節(jié)點不能立刻就知道，這就使得UNIX語義難以實現。放松的文件共享語義有：對話語義、類事物語義、不可改變的共享文件語義等。采用放松的文件共享語義要求應用程序員修改程序代碼，以適用這種新的語義，這就增加了程序員的負擔。6.7試解釋在機群并行文件系統中，為什么采用軟件RAID、高速緩存機制和預取能夠提高文件系統性能。答：軟件RAID是文件系統負責分布數據和維護容錯級別，能夠和RAID5有一樣的性能，實現機群磁盤間的數據分布，提高了I/O系統的傳輸帶寬。高速緩存是將應用程序要取的塊放在CACHE中，根據局部性原理，應用程序可以基本上從CACHE中讀取數據塊，而不要通過讀取內存或硬盤，提高了讀取速度。預取是在真正讀取數據塊之前就將這些數據塊讀入內存，這也提高了I/O性能，改善了文件系統性能。6.8討論并行文件系統協作化高速緩存的基本技術前提是什么？這個前提有什么意義？答：基本技術前提是互聯網絡的速度很快，一個節(jié)點需要的文件塊在其他節(jié)點的緩存中，那么就不需要從磁盤讀，而是直接從其他節(jié)點的緩存中讀出。這個前提的意義是可以提高系統的性能，使得節(jié)點間的協作化緩存變得更有意義。6.9回答以下關于BerkeleyNOW項目的問題：1）BerkeleyNOW項目支持單一系統映像的哪幾個方面？即單入口點、單文件層次結構、單控制點、單存儲空間、單進程空間哪個的哪幾項？并解釋如何支持。2）解釋BerkeleyNOW項目用來提高性能的四個結構特征。3）解釋BerkeleyNOW項目和SP機群四個體系結構的差異，并討論各自的優(yōu)點。答：通過用戶級整個機群軟件GLUNIX，提供單一系統映像。開發(fā)了一種新的無服務器網絡文件系統xFS，以支持單一文件層次結構。主動消息通信協議，支持有效的通信；機群軟件GLUNIX提供單一的系統映像、資源管理和可用性；xFS支持可擴放性和單一文件層次結構的高可用性；軟件框架WebOS構筑高可用性、漸增可擴放性。SP機群的體系結構特征：每個節(jié)點都是RS/600工作站，并有自己的局部磁盤；每個節(jié)點內駐留一個完整的AIX；各節(jié)點通過其I/O總線連接到專門設計的多級高速網絡；盡量使用標準工作站部件。這樣的優(yōu)點是簡單性和靈活性。6.10考慮xFS，并回答下列問題：1）解釋xFS和集中式文件服務器的兩個不同點，并討論各自的優(yōu)點；2）解釋xFS用來提高可用性的主要技術；3）解釋xFS用來減輕小—寫問題的主要技術。答：無服務器文件系統xFS將文件服務的功能分布到機器的所有節(jié)點上，xFS中所有的服務器和客戶的功能由分散的所有節(jié)點實現之。這與集中文件服務器的中央存儲、中央緩存、中央管理不同。xFS的優(yōu)點是采用分布式管理和協同文件緩存以及冗余磁盤陣列，這提高了系統的可用性以及I/O的性能和吞吐量。集中式文件服務器會減少緩存的不一致性，管理簡單。xFS提高可用性的主要技術是采用廉價冗余磁盤陣列RAID。無工作站文件系統能用來生成軟件RAID，以提高性能和高可用性。現在xFS使用單奇偶校驗磁盤條。一個文件數據塊在多個存儲服務器節(jié)點上按條劃分，在另一個節(jié)點上有奇偶校驗塊。如果一個節(jié)點失效，失效磁盤的內容，可利用其余盤和奇偶盤之異或操作重建之。xFS使用日志條的方法解決小—寫問題：每個用戶首先將寫接合到各用戶的日志上；然后此日志采用日志段提交給磁盤，每個段系由K-1個日志片組成，它與奇偶校驗片以道送給K個存儲服務器。第七章分布式共享存儲系統7.1什么是分布式共享存儲系統，它相對于共享存儲系統與分布式系統有哪些優(yōu)點？答：分布式共享存儲系統，是把共享存儲器分成許多模塊并分布于各處理機之中。分布式系統中采用消息傳遞通信，性能提高了，但多地址空間不利于程序員編程。共享存儲系統支持傳統的單地址空間，但共享必然引起沖突，形成瓶頸，于是分布式共享存儲系統結合兩者的優(yōu)點。7.2釋放一致性模型(RC)把處理器一致性(PC)和弱一致性模型(WC)的優(yōu)點結合在一起了。試回答下面有關這些一致性模型的問題：比較這三種一致性模型的實現要求。b)評論每種一致性模型的優(yōu)缺點。答：a)處理器一致性要求：①在任一取數操作LOAD允許被執(zhí)行之前，所有在同一處理器中先于這一LOAD的取數操作都已完成；②在任一存數操作STORE允許執(zhí)行之前，所有在同一處理器中先于這一STORE的訪存操作（包括取數操作和存數操作）都已完成。弱一致性模型要求：①同步操作的執(zhí)行滿足順序一致性條件；②在任一普通訪存操作允許被執(zhí)行之前，所有在同一處理器中先于這一訪存操作的同步操作都已完成；③在任一同步操作允許被執(zhí)行之前，所有在同一處理器中先于這一同步操作的普通訪存操作都已完成。釋放一致性模型要求：①在任一普通訪存操作允許被執(zhí)行之前，所有在同一處理器中先于這一訪存操作的獲取操作acquire都已完成；②在任一釋放操作release允許被執(zhí)行之前，所有在同一處理器中先于這一release的普通訪存操作都已完成；③同步操作的執(zhí)行滿足順序一致性條件。 b)三種模型對存儲順序要求逐漸降低，可優(yōu)化程度逐漸增加，但是對程序員的要求也越來越高，所以釋放性一致性是性能與復雜度的折中。7.3在DSM系統的順序一致性存儲模型下，有三個并行執(zhí)行的進程如下所示，試問001110是不是一個合法的輸出？并加以解釋。P1P2P3A=1;B=1;C=1;Print(b,c);Print(a,c);Print(a,b);答：不是一個合法輸出?？紤]順序一致性存儲模型，每個進程的程序序會被維護，那么無論哪個進程最后執(zhí)行Print語句，則之前的A=1，B=1,C=1都已經完成，所以輸出的兩后兩項必為11，所以001110不是合法輸出。7.4試分類下面來自三個處理器的引用流的高速緩存缺失。假設每一個處理器的高速緩存只有一個4個字的高速緩存行，字W0到W3、W4到W7分別處于同一個高速緩存行。如果一行有多個引用，我們假設P1在P2之前發(fā)射、P2在P3之前發(fā)射內存引用，符號LD/STWi表示LOAD/STORE字i。操作序號P1P2P31STW0STW72LDW6LDW23LDW74LDW2LDW05STW26LDW27STW2LDW5LDW58STW59LDW3LDW710LDW6LDW211LDW2STW712LDW713LDW214LDW515LDW2答：操作序號3、6、8、12-15都是單操作。操作序號1、2、9-11為無關存儲操作，由于不在同一塊中。操作序號4、7為對同一緩存塊的連續(xù)兩次LD，需要按序進行。7.5假設系統中共有512個處理器和1GB主存，每個節(jié)點內有8個處理器對目錄可見，一個高速緩存行的大小為64字節(jié)，那么在(a)滿位向量方案和(b)DriB(i=3)模型下目錄的存儲成本各是多少？答：分別為總容量的12.%和5.47%。7.6細數一下中心目錄與分布式目錄方案的實現方法與各自的使用情況。答：中心目錄是用一個中心目錄存放所有高速緩存目錄的拷貝，中心目錄能提供為保證一致性所需要的全部信息。因此，其容量非常大且必須采用聯想方法進行檢索，這和單個高速緩存的目錄類似。大型多處理機系統采用中心目錄會有沖突和檢索時間過長兩個缺點。分布式目錄方案是由Censier和Feautrier提出來。在分布式目錄中每個存儲器模塊維護各自的目錄，目錄中記錄著每個存儲器塊的狀態(tài)和當前的信息，其中狀態(tài)信息是本地的，而當前信息指明哪些高速緩存中有該存儲器塊的拷貝。一般來說，在共享存儲上實現中心目錄，而在分布式系統上實現分布式目錄方案更為合適一些，但這也并不是絕對的。7.7在研究DSM的讀寫代價和實現問題時有這樣兩種算法，即中央服務器算法和遷移算法：中央服務器算法是指使用一個中央服務器，負責為所有對共享數據的訪問提供服務并保持共享數據唯一的副本；遷移算法是指要訪問的數據總是被遷移到訪問它的節(jié)點中。兩種算法圖示如下：中央服務器算法顧客中央服務器發(fā)送數據請求接收請求執(zhí)行數據訪問，發(fā)送應答接收應答遷移算法顧客遠程主機如果高速緩存行不在本地，則確定位置，發(fā)送請求接收請求，發(fā)送高速緩存行接收回答，訪問數據現假設報文數量不會導致網絡阻塞，服務員的阻塞沒有嚴重到能夠極大地延遲遠程進程訪問，訪問本地數據的代價與遠程訪問代價相比微不足道，報文傳遞也是可靠的。試分析兩種算法的適合情況。答：中央服務器算法，每次顧客發(fā)送數據請求到中央服務器，地址計算簡單，適合多個顧客頻繁輪流讀寫。遷移算法每次確定位置需要一定開銷，適用于單個顧客頻繁對數據讀寫，因為訪問數據總是被遷移到訪