【正文】 14(位)。 (1)若頁面大小為200字，主存容量為400字，采用FIFO替換算法，請按訪存的各個時刻，寫出其虛頁地址流，計算主存的命中率； (2)若頁面大小為100字，再做一遍； (3)若頁面大小為400字，再做一遍； (4)由(1)、(2)、(3)的結(jié)果可得出什么結(jié)論？ (5)若把主存容量增加到800字，按第(1)小題再做一遍，又可得出什么結(jié)論？ 解： 故命中率H=6/12=50% (2)方法同（1）H=25% (3)H=50% (4)由以上結(jié)論可得，F(xiàn)IFO算法的條件下，當(dāng)頁面大小發(fā)生變化時，其命中率變化是：一開始隨頁面大小增大命中率（第一步與第二步比較），但當(dāng)頁面大小增到一定時，命中率不再增加（第一步與第三步比較）。 10. 在一個頁式二級虛擬存儲器中，采用FIFO算法進行頁面替換，發(fā)現(xiàn)命中率H太低，因此有下列建議： (1)增大輔存容量。 (3)FIFO改為LRU。 (5)FIFO改為LRU，并增大頁面大小。 解答：(1)增大輔存容量，對命中率H無影響。 (3)FIFO改為LRU，一般可提高命中率。 (5)FIFO改為LRU，并增大頁面大小，如果原來頁面很小，則會使命中率顯著上升，如果原來頁面很大，則會使命中率下降。主存模4交叉，每個分體寬為32位，總?cè)萘繛?56KB。請設(shè)計此相聯(lián)目錄表，求出該表之行數(shù)、總位數(shù)及每個比較電路的位數(shù)。設(shè)Cache地址中的組內(nèi)塊號為s，相聯(lián)目錄表的行數(shù)是2^(13s)，總位數(shù)是(8+2s)*2^(15s)，每個比較電路的位數(shù)為8+s。在一個主存周期內(nèi)主存能訪問到的字節(jié)數(shù)為mW=4*32/8=16(Byte)。為了加速調(diào)塊，一般讓每塊的大小等于在一個主存周期內(nèi)主存能訪問到的字?jǐn)?shù)，即16Bytes。 主存塊數(shù)/Cache塊數(shù)=256=2*8，所以，主存地址中的區(qū)號nd=8。=nd+s=8+s。+s)*Q=4*(8+2s)*2^(6s)=(8+2s)*2^(8s)。 。 (1)畫出主存、Cache地址的各字段對應(yīng)關(guān)系(標(biāo)出位數(shù))圖。 (3)對于如下主存塊地址流：1,2,4,1,3,7,0,1,2,5,4,6,4,7,2,如主存中內(nèi)容一開始未裝入Cache中，請列出Cache中各塊隨時間的使用狀況。 (5)對于(3),求出此期間Cache的命中率。(1)主存地址、Cache地址的各字段的位數(shù)及其對應(yīng)關(guān)系如下圖所示 (2)主存塊、Cache塊的映象對應(yīng)關(guān)系如下圖所示 (3)Cache中各塊隨時間的使用狀況如下圖所示。R：替換。 (4)發(fā)生塊失效又發(fā)生塊爭用的時刻有11115。 剖析：主存的第7塊只能映象裝入或替換物理Cache的第3塊。 (2)增大Cache的塊數(shù)(塊的大小不變)。 (4)增大塊的大小(組的大小和Cache總?cè)萘坎蛔?。 解答：(1)增大主存容量對Cache的訪問時間ta基本不影響，從而對Cache的等效訪問速度基本不影響。 (3)增大組相聯(lián)組的大小(塊的大小不變)一般將使Cache的命中率Hc上升，從而使ta下降，從而提高Cache的等效訪問速度。 (5)提高Cache本身器件的訪問速度一般將縮短ta，從而提高Cache的等效訪問速度。而另有人建議你干脆去買更高速的Cache片子將現(xiàn)有的低速Cache片子全部換掉。如果對Cache存儲器的等效訪問速度不滿，需要改進的話，就要作具體分析，看看現(xiàn)在Cache存儲器的等效訪問速度是否已接近于Cache本身的速度。如果Cache存儲器的等效訪問速度已經(jīng)非常接近于Cache本身的速度還不能滿足需要，就應(yīng)該更換更高速的Cache片子。 “執(zhí)行k”與“取指k+1”重疊。 (2)分別在t取指=t分析=t執(zhí)行=1及t取指=t執(zhí)行=t分析=2兩種情況下，計算出上述各結(jié)果。(1)執(zhí)行完100條指令所需時間： *(t取指+t分析+t執(zhí)行)。 +max(t取指+t分析)+98*max(t取指+t分析+t執(zhí)行)+max(t分析+t執(zhí)行)+t執(zhí)行。 解： TP=10/14△t=5/7△t 時空圖：(a)所示，其乘積可直接返回輸入端或暫存于相應(yīng)緩沖寄存器中，畫出實現(xiàn)A*B*C*D的時空圖以及輸入端的變化，并求出該流水線的吞吐率和效率。 (a) (b) 解：(a)組織的流水線時，TP=3/13△t。 實現(xiàn)A*B*C*D的時空圖如圖0504所示： 圖0504 (a)組織的流水線時，TP=3/13△t。 實現(xiàn)A*B*C*D的時空圖如圖0504所示： 圖0505 剖析：為了減少運算過程中的操作數(shù)相關(guān)，A*B*C*D應(yīng)改為((A*B)*(C*D))進行運算。 答: 剖析： ？現(xiàn)有3段流水線，各段經(jīng)過時間依次為△t、3△t、△t， (1)分別計算在連續(xù)輸入3條指令時和30條指令時的吞吐率和效率。 (3)通過對(1)、(2)兩小題的計算比較可得出什么結(jié)論？ 解答: (1)連續(xù)輸入3條指令時的吞吐率TP3=3/11△t。 連續(xù)輸入30條指令時的吞吐率TP30=15/46△t。 (2)(a)(b)。效率η3=3/7。效率η3=15/17。 ，由經(jīng)過時間為△t、2△t、2△t,△t的4四個子過程構(gòu)成?，F(xiàn)要執(zhí)行A*(B+C*(D+E*F))+G*H的運算，請調(diào)整計算順序畫出能獲得盡量高的吞吐率的流水時空圖，標(biāo)出流水線入、出端數(shù)的變化情況，求出完成全部運算的時間及此期間流水線的效率。 若子過程3不能再細分，只能用并聯(lián)方法改進，則則時空圖如圖0509所示： 圖0509 這種情況下，流水線效率η=(24△t+12△t)/6*18△t=1/3 剖析：因為是雙功能靜態(tài)流水線，為了能有高的吞吐率，應(yīng)減少流水線的功能切換次數(shù)。原式展開成A*B+A*C*D+A*C*E*F+G*H，先進行乘法流水，為了減少因先寫后讀相關(guān)而等待的時間，應(yīng)盡量安排對計算式子項數(shù)最多的乘法先進行操作，即先計算A*C*E*F，再計算A*C*D，... ，請分別畫出下列4種結(jié)構(gòu)的處理器上求點積A*B的時空圖，并求完成全部結(jié)果的最少時鐘拍數(shù)。 (1)處理器有一個乘法部件和一個加法部件，不能同時工作，部件內(nèi)也只能以順序方式工作，完成一次加法或乘法均需5拍。 (3)處理器有一個乘、加法雙功能靜態(tài)流水線，乘、加法均由5個流水段構(gòu)成，各段經(jīng)過時間要1拍。 解答： (1)在這種結(jié)構(gòu)的處理器上求點積A*B的時空圖如圖0510所示： 圖0510 完成全部運算最少需要75拍。 (3)在這種結(jié)構(gòu)的處理器上求點積A*B的時空圖如圖0512所示： 圖0512 完成全部運算最少需要30拍。圖0513完成全部運算最少需要26拍。 360/91解決流水線控制的一般方法、途徑和特點。 ，其預(yù)約表為： t0t1t2t3t4t5t6t7t8s1∨∨s2∨∨s3∨∨∨s4∨∨s5∨∨分別寫出延遲禁止表F、沖突向量C。求出最小平均延遲及流水線的最大吞吐率及其高度方案。 解： 根據(jù)預(yù)約表，延遲禁止表F={1，3，4，8} 沖突向量為C:10001101 狀態(tài)轉(zhuǎn)移圖如圖0514所示 圖0514 各種方案的平均延遲表：調(diào)度方案(2,5)(2,7)5(5,6)(6)(6,7)(7)平均延遲567其調(diào)度方案為（2，5）。 剖析：求延遲禁止表F={1，3，4，8}，第一行間隔8，第二行間隔1，第三行間隔1，3，4，然后間隔都為1，合并。 由于初始沖突向量的c2,c5,c6,c7為0，所以第二個任務(wù)可以距第一個任務(wù)2，5，6或7拍流入流水線。 （2）1和2并行執(zhí)行完后，再執(zhí)行3。 解: （1）每條指令所需拍數(shù)為： 指令1：1（啟動訪存）+6（訪存）+1（存V3）+N1（第一個分量后每隔1拍出一個結(jié)果）=7+N 指令2：1（送浮加部件）+6（浮加）+1（存V2）+N1=7+N 指令3：1（送浮乘部件）+7（浮乘）+1（存V4）+N1=8+N 串行：7+N+7+N+8+N=22+3N （2）指令1和2并行執(zhí)行：1（啟動訪存，送浮加部件）+6（訪存，浮加）+1（存V3，存V2）+N1=7+N 1，2并行：7+N+8+N=15+2N （3）1+6+1+1++7+1+N1=16+N ，以CRAY1機上所用浮點功能部件的執(zhí)行時間分別為：相加6拍，相乘7拍，求倒數(shù)近似值14拍。問下列各指令組內(nèi)的哪些指令可以鏈接？哪些指令不能鏈接？不能鏈接的原因是什么？分別計算出各指令組全部完成所需的拍數(shù)。max{(1+6(訪存)+1+641),(1+6(浮加)+1+641),(1+(7浮乘)+1+641)}=72拍。 (2)3條向量指令之間沒有功能部件的使用沖突，但是在第2兩條向量指令與第3條向量指令之間有V2及V3的先寫后讀相關(guān)。max{(1+(7浮乘)+1+641),(1+6(訪存)+1+641)}+(1+6(浮加)+1+641)=80(拍)。第3條向量指令與第2條向量指令之間有源向量寄存器V0的沖突，它們之間只能串行。(1+6(訪存)+1+1+(7浮乘)+1+641)+(1+6(訪存)+1+641)(1+6(浮加)+1+641)=222(拍)。(1+6(訪存)+1)+(1+14(求倒數(shù))+1)+(1+(7浮乘)+1)+(1+6(浮加)+1)+641=104拍。每個子部件經(jīng)過時間為△t，連續(xù)執(zhí)行12條指令。 解： 常規(guī)標(biāo)量處理機的時空圖： 度m為4的超標(biāo)量處理機的時空圖： 其相對于常規(guī)標(biāo)量流水處理機的加速比Sp=14△t/5△t= 度m為4的超長指令字處理機的時空圖：其相對于常規(guī)標(biāo)量流水處理機的加速比Sp=14△t/5△t= 度m為4的超流水線處理機的時空圖： 其相對于常規(guī)標(biāo)量流水處理機的加速比Sp=14△t/△t=56/23≈ 第六章　陣列處理機 Ⅳ 的模式進行互連的互連結(jié)構(gòu)圖，列出PE0分別只經(jīng)一步、二步和三步傳送能將信息傳送到的各處理器號。:6臺處理器仿ILLIAC Ⅳ 處理單元的互連結(jié)構(gòu)如圖所示： 圖中第個PU中包含PE、PEM和MLU。 PE0(PU0)至少需經(jīng)二步才能將信息傳送至PUPUPUPUPU1PU1PU14。 、...、15的16個處理器，用單級互連網(wǎng)互連。 Cube3(13)=Cube3(1101)=0101=5 PM2+3(13)=(13+2^3)mod16=5 PM20(13)=(132^0)mod16=12 Shuffle(13)=Shuffle(1101)=1011=11 Shuffle(Shuffle)=Shuffle(11)=Shuffle(1011)=0111=7 、...、F的16個處理器之間要求按下列配對通信：(B、1)，(2)，(D)，(C)，(E、4)，(A、0)，(3)，(F)。 解答：采用4級立方體網(wǎng)絡(luò)，級控制。由于實現(xiàn)的都是交換函數(shù)的功能，采用成本最低的級控制多級立方體互聯(lián)網(wǎng)絡(luò)就可以實現(xiàn)。每一級均使用N/2=8個二功能交換開關(guān)。根據(jù)本題的要求，應(yīng)當(dāng)讓第3級的各交換單元處于“交換”狀態(tài)，第0、2級的各交換單元處于“直連”狀態(tài)。 9號處理器在經(jīng)過0級和1級交換開關(guān)后，連向哪第10個處理器。在經(jīng)過3級交換開關(guān)后，連向第9個處理器。例如，第0級為直連狀態(tài)時，入端號為0的處理器僅能與出端號為0的處理器進行數(shù)據(jù)傳送，不能與出端號為1的處理器進行數(shù)據(jù)傳送。 當(dāng)?shù)趇級為交換狀態(tài)時，不能實現(xiàn)入、出兩端的處理器二進制編碼的編號中，第Pi位相同的處理器之間的連接。因為交換開關(guān)的直連狀態(tài)被定義為i入連j出，j入連i出，所以，反映出實現(xiàn)互連的入、出端號的二進制碼中的Pi位必須變反，其它的各位可以不變，也可以變反。 剖析：每個元素的行坐標(biāo)和列坐標(biāo)均用3位表示，設(shè)b5b4b3為行下標(biāo)的二進制編號，b2b1b0為列下標(biāo)的二進制編號，經(jīng)過3次全混洗后，元素下標(biāo)號b5b4b3b2b1b0就變成了b2b1b0b5b4b3，即行下標(biāo)的二進制編號改成了b2b1b0，列下標(biāo)的二進制編號改成了b5b4b3，這樣，就實現(xiàn)了矩陣的行列轉(zhuǎn)置。 解答：8個處理器的三級混洗交換網(wǎng)絡(luò)及其交換開關(guān)控制狀態(tài)設(shè)置如下圖所示： ，然后是2組8元交換，再次是1組16元交換的交換函數(shù)功能，請寫出此時各處理器之間所實現(xiàn)的互連函數(shù)的一般式，畫出相應(yīng)多級網(wǎng)絡(luò)的拓撲結(jié)構(gòu)圖，標(biāo)出各組交換形狀的狀態(tài)。 多級立方體互連網(wǎng)絡(luò)的拓撲結(jié)構(gòu)圖和第3題的圖基本一致，不同之處在于，第0、3級的開關(guān)狀態(tài)為直連，第2級的開關(guān)狀態(tài)為交換。 (1)N個輸入總共可有多少種不同的排列； (2)該Omega網(wǎng)絡(luò)通過一次可以實現(xiàn)的置換可有多少種是不同的。 解答： (1)N個輸入總共可有N!種不同的排列。 (3)若N=8,通過Omega網(wǎng)絡(luò)一次可以實現(xiàn)的不重復(fù)置換有8^4=4096種。所以，一次通過能實現(xiàn)的置換數(shù)占全部排列數(shù)的百分比為4096/40320*100%≈% =8的立方體全排列多級網(wǎng)絡(luò)，標(biāo)出采用單元控制，實現(xiàn)0→3,1→7,2→4,3→0,4→2,5→6,6→1,7→5的同時傳送時的各交換開關(guān)的狀態(tài)。 解答： 16