【正文】 在一到的映射時，交換開關(guān)的狀。實現(xiàn)N=8的立方體全排列多級網(wǎng)絡(luò)及交換形狀狀態(tài)如下圖所示 說明為什么不會發(fā)生阻塞。8個輸入總共可實現(xiàn)的不重復(fù)排列有8!=40320種。(2)該Omega網(wǎng)絡(luò)通過一次可以實現(xiàn)的置換可有2^((N/2)log2(N))=N^(N/2)種是不同的。 (3)若N=8,計算出一次通過能實現(xiàn)的置換數(shù)占全部排列數(shù)的百分比。 =2^n個輸入端的Omega網(wǎng)絡(luò)，采用單元控制。 解答：互連函數(shù)的一般式為：Cubei(P3P2P1P0)=(￣P3P2￣P1￣P0)。 ~7號共8個處理器的三級混洗交換網(wǎng)絡(luò)，在該圖上實現(xiàn)將6號處理器數(shù)據(jù)播送給0~4號，同時將3號處理器數(shù)據(jù)播送給其余3個處理器時的各有關(guān)交換開關(guān)的控制狀態(tài)。8*8矩陣中任一元素aij，它在存儲器中所占的位置是i*8+j(即i*2^3+j)。 *8矩陣A=(aij)，順序存放在存儲器的64個單元中，用什么機關(guān)報單級互連網(wǎng)絡(luò)可實現(xiàn)對該矩陣的轉(zhuǎn)置變換？總共需要傳送多少步？ 解答： 采用單級混洗互連網(wǎng)絡(luò)可實現(xiàn)對8*8矩陣的轉(zhuǎn)置變換，共需傳送3步。例如，第0級為交換狀態(tài)時，入端號為0的處理器僅能與出端號為1的處理器進行數(shù)據(jù)傳送，不能與出端號為0的處理器進行數(shù)據(jù)傳送。因為交換開關(guān)的直連狀態(tài)被定義為i入連i出，j入連j出，所以，反映出實現(xiàn)互連的入、出端號的二進制碼中的Pi位是不能變反的，其它的各位可以不變，也可以變反。 ，當(dāng)?shù)趇級(0=i=2)為直連狀態(tài)時，不能實現(xiàn)哪些結(jié)點之間的通信？為什么？反之，當(dāng)?shù)趇級為交換狀態(tài)呢？ 解答：當(dāng)?shù)趇級為直連狀態(tài)時，不能實現(xiàn)入、出兩端的處理器二進制編碼的編號中，第Pi位取反的處理器之間的連接。在經(jīng)過2級交換開關(guān)后，連向第4個處理器。 、...、F共16個處理器之間實現(xiàn)多級立方體互連的互連網(wǎng)絡(luò)，采用級控制信號為1100(從右至左分別控制第0級至第3級)時，9號處理器連向哪個處理器？ 解答：多級立方體互連網(wǎng)絡(luò)的圖和第3題的圖基本一致，不同之處在于，第0、1級的開關(guān)狀態(tài)為直連，第3級的開關(guān)狀態(tài)為交換。多級網(wǎng)絡(luò)各級的級號由入端到出端依次為0、(P3...Pi...P0)=P3...(￣Pi)...P0函數(shù)。N=16的多級立方體網(wǎng)絡(luò)，由n=log2(16)=4組成。 不難得出其一般規(guī)律是：二進制編號為P3P2P1P0的處理器與(￣P3)P2(￣P1)P0的處理器配對交換數(shù)據(jù)。(5,F) (0101,1111) (9,3) (1001,0011) (A,0) (1010,0000) (E,4) (1110,0100) (6,C) (0110,1100) (7,D) (0111,1101) (8,2) (1000,0010) (B,1) (1011,0001) 該互連網(wǎng)絡(luò)的拓補結(jié)構(gòu)和各級交換開關(guān)狀態(tài)圖如下圖所示： 剖析：從處理器號的配對傳送關(guān)系可以轉(zhuǎn)成處理器二進制編號的配對傳送關(guān)系： 試選擇所用互連網(wǎng)絡(luò)類型、控制方式，并畫出該互連網(wǎng)絡(luò)的拓補結(jié)構(gòu)和各級交換開關(guān)狀態(tài)圖。(5)7號處理器 剖析：由題意知，有16個處理器，即N=16,n=log2(N)=log2(16)=4。(4)11號處理器 (3)12號處理器 (2)5號處理器 當(dāng)互連函數(shù)分別為 (1)Cube3 (2)PM2+3 (3)PM20 (4)Shuffle (5)Shuffle(Shuffle) 時，第13號處理器各連至哪一個處理器？ 解答：(1)5號處理器 PE0(PU0)至少需經(jīng)三步步才能將信息傳送至PUPUPUPU10。 PE0(PU0)經(jīng)一步可將信息傳送至PUPUPU1PU15。 答請分別畫出在常規(guī)標(biāo)量流水處理機及度m均為4的超標(biāo)量處理機、超長指令字處理機、超流水線處理機上工作的時空圖，分別計算它們相對常規(guī)標(biāo)量流水處理機的加速比Sp。 、分析、執(zhí)行三個子部件組成。(4)4條向量指令均依次有Vi的先寫后讀相關(guān)，但無源Vi沖突，也無功能部件的使用沖突，所以，這4條向量指令可以全部鏈接在一直，進行流水。 第3條向量指令與第4條向量指令之間有加法功能部件的使用沖突，它們之間也只能串行。(3)第1條向量指令與第2條向量指令之間有V0的先寫后讀相關(guān)，兩者可以鏈接。 只要讓第1條向量指令較第2條向量指令提前1拍啟動，則第1,2兩條向量指令的第1個結(jié)果元素就可以被同時鏈接到第3條向量指令中。所以向量指令組全部完成需要72(拍)。 (1)(2)(3)(4)V0←存儲器V1←V2+V3V4←V5*V6V2←V0*V1V3←存儲器V4←V2+V3V0←存儲器V2←V0*V1V3←V2+V0V5←V3+V4V0←存儲器V1←1/V0V3←V1*V2V5←V3+V4解：(1)3條向量指令之間既沒有發(fā)生源Vi沖突，也沒有Vi的先寫后讀相關(guān)，又不存在功能部件的使用沖突，所以這3條向量指令可以同時并行流水。從存儲器讀數(shù)6拍，打入寄存器及啟動功能部件各1拍。 （3）采用鏈接技術(shù)。 =A*(B+C)，各向量元素均為N，參照CRAY－1方式分解為3條向量指令： 1：V3＜存儲器｛訪存取A送入V3寄存器組｝ 2：V2＜V0＋V1｛B＋C＞K｝ 3：V4＜V2＋V3｛K＊A＞D｝ 當(dāng)采用下列3種方式工作時需多少拍才能得到全部結(jié)果？ （1）串行執(zhí)行。求沖突向量，寫一個8位兩進制數(shù)，根據(jù)禁止表倒著寫。 實際吞吐率TP=6/25(任務(wù)/拍)。圖0515 按調(diào)度方案（2，5）輸入6個任務(wù)時的時空圖如圖0515所示： 按此流水高度方案輸入6個任務(wù)，求實際吞吐率。畫出流水線狀態(tài)轉(zhuǎn)移圖。 在流水線中設(shè)置相關(guān)直接通路解決局部相關(guān)； 用猜測法解決全局相關(guān)； 設(shè)置向后8條檢查，加快短循環(huán)程序的處理； 對流水線的中斷處理用不精確斷點法。向量A*B的點積為A*B=(8)∑(i=1)ai*bi=a1*b1+a2*b2+a3*b3+a4*b4+a5*b*+a6*b*+a7*b7+a8*b8,共需8次乘法和7次加法。 剖析：(4)在這種結(jié)構(gòu)的處理器上求點積A*B的時空圖如圖0513所示： 完成全部運算最少需要45拍。圖0511 (2)在這種結(jié)構(gòu)的處理器上求點積A*B的時空圖如圖0511所示： (4)處理器有乘、加法兩條流水線，可同時工作，各由5段構(gòu)成，每段經(jīng)過時間為1拍。 (2)與(1)基本相同，只是乘法部件和加法部件可并行。設(shè)處理器中每個部件的輸出均可直接送到任何部件的輸入或存入緩沖器中去，其間的傳送延時不計，指令和源操作數(shù)均能連續(xù)提供。因此，應(yīng)將算法調(diào)整成先作一連串的乘，然后再切換成一連串的加。由圖可見，完成全部運算最少需要18△t。圖0508 如果將瓶頸子過程2和3均細分成兩個子過程，則時空圖如圖0508所示： 在此期間的流水線效率η=(6*4△t+3*4△t)/4*24△t=3/8 圖0507 如對流水線瓶頸子過程再細分，最少只需多少時間可完成全部運算？若子過程3不能再細分，只能用并聯(lián)方法改進，問流水線的效率為多少？ 解: 根據(jù)題意，畫出流水線吞吐率盡可能高的時空圖如圖0507： 加按124連接，乘按134連接，流水線輸出設(shè)有數(shù)據(jù)緩沖器，也可將數(shù)據(jù)直接返回輸入。(3)只有當(dāng)連續(xù)輸入流水線的指令足夠多時，流水線的實際吞吐率和效率才會提高。 連續(xù)輸入30條指令時的吞吐率TP30=15/17△t。 連續(xù)輸入3條指令時的吞吐率TP3=3/7△t。 效率η3=25/46。效率η3=5/11。為提高流水線效率可采用瓶頸希再細分和瓶頸段并聯(lián)兩種主要途徑來克服速度瓶頸。 (2)按兩種途徑之一改進，畫出你的流水線結(jié)構(gòu)示意圖，同時計算連續(xù)輸入3條指令和30條指令時的吞吐率。為了避免先寫后讀相關(guān)，使流水線性能盡可能高，需將(10)∑(i=1)Ai調(diào)整成((((A1+A2)+(A3+A4))+(A9+A10))+((A5+A6)+(A7+A8)))。求(10)∑(i=1)Ai需要的最知時間是170ns。時空圖如下： ，每段經(jīng)過時間10ns,輸出可直接返回輸入或?qū)⒔Y(jié)果暫存于相應(yīng)緩沖器中，問最少需經(jīng)多少時間能求(10)∑(i=1)Ai，并畫出時空圖。η=3/11。η=3/11。(b)形式實現(xiàn)同一計算時，求該流水線的效率及吞吐率。 ，每個功能部件的延遲時間為△t，當(dāng)輸入10個數(shù)據(jù)后間歇5△t又輸入10個數(shù)據(jù)，如此周期性地工作，求此時流水線的吞吐率，并畫出時空圖。 在t取指=t執(zhí)行=t分析=2的情況下，執(zhí)行完100條指令所需時間： (2)在t取指=t分析=t執(zhí)行=1的情況下，執(zhí)行完100條指令所需時間： +100*t分析+99*max(t取指+t執(zhí)行)+t執(zhí)行。 解： “執(zhí)行k”、“分析k+1”、“取指k+2”重疊。 第五章　重疊、流水和向量處理機、分析與執(zhí)行3步，每步的時間相應(yīng)為t取指、t分析、t執(zhí)行, (1)分別計算下列幾種情況下，執(zhí)行完100條指令所需時間的一般關(guān)系式： 。如果差得較遠，說明Cache的命中率低，應(yīng)從提高Cache命中率著手，包括調(diào)整組的大小、塊的大小、替換算法以及增大Cache容量等。你認為哪種建議可??？你如何做決定？為什么？ 解答：Cache本身的速度與容量都會影響Cache存儲器的等效訪問速度。 ，于是申請到一批有限的經(jīng)費，為能發(fā)揮其最大經(jīng)濟效益，有人建議你再買一些同樣速度的Cache片子以擴充其容量。(4)增大塊的大小(組的大小和Cache總?cè)萘坎蛔?一般將使ta下降，從而提高Cache的等效訪問速度。 (2)增大Cache的塊數(shù)(塊的大小不變)一般將使Cache的命中率Hc上升，從而使ta下降，從而提高Cache的等效訪問速度。 (5)提高Cache本身器件的訪問速度。 (3)增大組相聯(lián)組的大小(塊的大小不變)。 ，LRU替換算法的Cache存儲器，發(fā)現(xiàn)等效訪問速度不高，為此建議： (1)增大主存容量。由于主存塊、Cache塊之間存在上述的映象對應(yīng)關(guān)系，主存的第0、5塊只能映象裝入或替換物理Cache的第0、1塊。(5)Cache的塊命中率Hc=3/15=。 L：失效。圖中標(biāo)*號的是候選替換塊的塊號，H：命中。 解答： (4)對于(3),指出塊失效又發(fā)生塊爭用的時刻。 (2)畫出主存、Cache空間塊的映象對應(yīng)關(guān)系示意圖。主存共分8個塊(0~7),Cache為4個塊(0~3),采用組相聯(lián)映象，組內(nèi)塊數(shù)為2塊，替換算法為近期最少使用算法(LRU)。若認為相等比較電路的個數(shù)=組內(nèi)塊數(shù)，則相聯(lián)目錄表的行數(shù)=2^4，每個比較電路的位數(shù)=10，相聯(lián)目錄表的總位數(shù)=12*2^6。 note： 相聯(lián)目錄表的總位數(shù)=表中子目錄表的個數(shù)*每個子目錄表的位數(shù)*相聯(lián)目錄表的行數(shù)=4*(nd+s39。 每個比較電路的位數(shù)=nd+s39。設(shè)Cache地址中的組內(nèi)塊號為s，相聯(lián)目錄表的行數(shù)=Cache地址內(nèi)的組數(shù)Q=Cache容量/(每組塊數(shù)*每塊大小)=1KB/(S*4*32)=2^13/(2^s*2^7)=2^(6s)。 要求Cache的每一塊在一個主存周期內(nèi)能從主存取得，所以，Cache中每塊的塊內(nèi)字數(shù)不能大于16Bytes。 剖析： 解答：用按地址訪問存儲器構(gòu)成相聯(lián)目錄表實現(xiàn)主存地址到Cache地址的變換，并約定用4個外相等比較電路。 ，Cache為1KB，要求Cache的每一塊在一個主存周期內(nèi)能從主存取得。(4)FIFO改為LRU，并增大主存容量(頁數(shù))，一般可使命中率有較大提高。 (2)增大主存容量(頁數(shù))，可普遍提高命中率。 試分析上述各建議對命中率的影響情況。 (4)FIFO改為LRU，并增大主存容量(頁數(shù))。 (2)增大主存容量(頁數(shù))。(5)命中率為58%，結(jié)論是如果分配給主存容量增加時可以搞高命中率。 按FIFO算法得出替換過程為：0（調(diào)入），0（命中），1（調(diào)入），1（命中），0（命中），3（替換0，0比1先入隊，所以被替換，下同），1（命中），2（替換1），2（命中），4（替換3），4（命中），3（替換2），所以總共命中6次。把地址流轉(zhuǎn)換為頁地址流，以第一個虛地址流轉(zhuǎn)換為頁地址流為例說明：求模公式為：INT（地址/頁面大?。褪前训刂氛陧撁娲笮?，得INT（20/200）=0，下同，所以頁地址流為：0,0,1,1,0,3,1,2,2,4,4,3 (1)主存容量400字，頁面大小200字，所以主存實頁數(shù)為2； (6)快表的總?cè)萘浚?2行*（14(輸入位數(shù))+8（輸出位數(shù)））*2=32*22*2 ，其訪問虛存的地址流為20，22，208，214，146，618，370，490，492，868，916，728。 (5)每個相等比較器的位數(shù)=ID+用戶虛頁號nv39。(4)散列變換硬件的輸入位數(shù)為14位（虛頁號寬度+相聯(lián)寄存器中ID的寬度），輸出位數(shù)為8位（與主存中的實頁號寬度對應(yīng)） (3)相聯(lián)寄存器組中每個寄存器的總數(shù)為12（用戶號寬度+ID寬度） (2)相聯(lián)寄存器組中每個寄存器的相聯(lián)比較位數(shù)為10（與虛地址中的用戶號寬度對應(yīng)） 但又有所簡化（原因是如果用用戶號和虛頁號與實頁號對應(yīng)，前者就有22位，現(xiàn)改進后虛頁號只有14位了） 相聯(lián)寄存器的作用：把10位的用戶號轉(zhuǎn)換為2位的ID（因為一般只有4個任務(wù)在使用），并把ID與虛地址的虛頁號合并到快表中查實頁號。實地