計算機系統(tǒng)結(jié)構(gòu)試題及答案

1、2009-2010學(xué)年度第一學(xué)期 2007級計算機系統(tǒng)結(jié)構(gòu)期末考試試卷（A）（閉卷）姓名：學(xué)號：專業(yè)：（注：考試時間為120分鐘；所有解答必須寫在答題紙上。）一、單項選擇題（每小題 3分，共30分）1 .在系列機中發(fā)展一種新型號機器，你認(rèn)為下列（）設(shè)想是不行的？AJ新增加字符數(shù)據(jù)類型和若干條字符處理指令【B】將中斷分級由原來的 4級增加到5級【Q在CPUO主存之間增設(shè) Cache存貯器【D】將浮點數(shù)的下溢處理法由原來的恒置“1”法，改為查表舍入法2 .對計算機系統(tǒng)結(jié)構(gòu)來說，不透明的是（）?！続1存儲器采用交叉存取還是并行存取B CPU內(nèi)部的數(shù)據(jù)通路的寬度是 8位還是16位【Q采用浮點數(shù)據(jù)表示還

2、是標(biāo)志符數(shù)據(jù)表示【D】指令采用硬聯(lián)邏輯實現(xiàn)還是微程序?qū)崿F(xiàn)3 . 一個平衡的計算機系統(tǒng)，應(yīng)該是（）。AJ 1MIPS的CPU®度【B】1MB的主存容量Cl 1Mb/s的I/O吞吐率【D】A、B和C4、（）設(shè)計是現(xiàn)代計算機系統(tǒng)設(shè)計所采用的方法?！続1由上往下【B】由下往上【Q由中間開始 【0上下同時開始5.當(dāng)今微型機中實現(xiàn)軟件移植最好的方法是（）。AJ系列機【B】兼容機【Q仿真技術(shù)10統(tǒng)一高級語言6、不能夠?qū)ο蛄繑?shù)據(jù)結(jié)構(gòu)提供直接支持的是（）數(shù)據(jù)表示?！続1向量【B】堆?！綫描述符【0A和C7、采用整數(shù)邊界存儲技術(shù)，其主要目的是（）。AJ節(jié)約主存空間【B】提高數(shù)據(jù)的訪問速度【Q 一個主存周

3、期可取多條指令【D】一個主存周期至少可取到一條指令8、在指令的操作碼編碼方式中，優(yōu)化實用的編碼是（）。A Hufman編碼 【B】等長編碼【Q Hufman擴展編碼 【D】BC加9、流水計算機中將指令Cache和數(shù)據(jù)Cache分開，主要是為了（）。AJ提高存儲系統(tǒng)的速度【B】增加主存容量【Q解決功能部件沖突【D】解決訪存沖突10、當(dāng)N=16時，能描述4組4元交換的函數(shù)是（）。A C1+C2B C0+C1Cl C0+C2D C2+C3二、（10分）在采用通用寄存器指令集結(jié)構(gòu)的計算機上得到了如下所示的數(shù)據(jù)：指令類型執(zhí)行頻率時鐘周期數(shù)ALU指令 一43%1LOAD旨令21%2STORE旨令12%2分

4、行令24%2假若編譯器優(yōu)化后能去掉50%勺ALU指令，但不能去掉其它三類指令。求優(yōu)化后的MIPS與優(yōu)化前的MIPS速率比。三、（10分）設(shè)某機器系統(tǒng)指令字長 12位，每個操作碼和地址均占 3位，試提出一種分配方案，使該指令系統(tǒng)有 4條三地址指令，8條二地址指令和180條單地址指令。四、（10分）設(shè)通道在數(shù)據(jù)傳送期中，選擇設(shè)備需4.9 S,傳送一個字節(jié)數(shù)據(jù)需 0.l So（1）其低速設(shè)備每隔 250科S發(fā)出一個字節(jié)數(shù)據(jù)傳送請求，問最多可接多少臺這種設(shè)備？（2）若有AE共5種高速設(shè)備，要求字節(jié)傳送的間隔時間如下表所示，其時間單位為 科So若一次通信傳送的字節(jié)數(shù)不少于1024個字節(jié)，問哪些設(shè)備可掛在

5、此通道上？哪些則不能？設(shè)備ABCDE時間間隔（科S）0.130.10.110.20.3五、（10分）有一非線線性流水線預(yù)約表如下。功能段123456S1VVS2VVVS3VVS4V（1）求平均延遲最小的最佳調(diào)度方案；（2）畫出按最佳方案之一連續(xù)輸入3個任務(wù)的時空圖。六、（10分）有一四段線性流水線，每功能段延時時間分別是：tkt3=4t4=4t0, At 2 = 3 tco若在這個流水線上執(zhí)行 40個任務(wù)。求實際吞吐率、效率和加速比。七、（10分）N=8結(jié)點的三級立方體網(wǎng)絡(luò)如下圖所示。當(dāng)K1=0時，試說明輸入4號結(jié)點不能實現(xiàn)和哪些輸出結(jié)點相連？01234567QK0G KC2& Gn八

6、、（10分）在8個PE構(gòu)成的雙向環(huán)互連的并行處理機中，計算點積S= Z ai黑bi （n=8）所需要的時間。設(shè)初始化時將 A,B各分量已分配到各 PE中，且設(shè)相鄰處理單元之間傳送一次數(shù)據(jù)需要時間 t,完成一次加法需要時間？ t ,完成一次乘法需要時間 4Ato（全部試題完）武漢大學(xué)計算機學(xué)院2009-2010學(xué)年度第二學(xué)期 2007級計算機系統(tǒng)結(jié)構(gòu)期末考試試卷（A）參考答案一、（每小題3分，共30分）解:1-10: BCDCA BDCDB二、（10 分）解:Rc CPICPInew 106old 106RcCPIoldCPInew1.57 “ 0.91.73解:000X XX XXXXXX01

7、1X XX XXXXXX100000XXXXXX100111XXXXXX101000000XXX101111111XXX110000000XXX111110011XXX四、(10分）解:（1）低速設(shè)備應(yīng)接字節(jié)多路通道MIPSnewMIPSold三、（10分）64+116=1801-n -250fmax. byte TsTd4.9 0.1所以，nW 50臺，即最多可接50臺 （2）根據(jù)題意，此通道為選擇通道fmax. select其中，n> 1024,應(yīng)使 select *i< 加axwelect, 所以，只有 A、C、D、E可掛在此通道上，B由此可得出通道工作周期為：T= 0.10

8、14（us）則不行。五、（10分）解:（1）狀態(tài)圖略。最佳調(diào)度方案為（3）和（1, 5）（2）輸入3個任務(wù)時空圖略。六、（10分）解:tp-40一 40一上61 (40 -1). ：tj 6 ：t 39 3 ：t 123. ：t1_40 6 tE 二4 123 t48.8%c 40 6 4SP 二123. t1.95七、（103P4M8+3 35解:不能與輸出（5+才43 81 m5ns點才40、5ns= 175(MIPS )八、（10分）解:需要8次乘法，7次加法;共 14At計算機系統(tǒng)結(jié)構(gòu)姓名：學(xué)號：、名詞解釋（每題 3分，共15分）1. Cache 2:1經(jīng)驗規(guī)則3.同構(gòu)型多處理機5.堆

9、棧型機器2.計算機體系結(jié)構(gòu)4.通道處理機二、填空（每空1 分，共 20 分 ）1. 設(shè)計 I/O 系統(tǒng)的三個標(biāo)準(zhǔn)是（） （、 ） 和（ ） 。2. 存 儲 器 層 次 結(jié) 構(gòu) 設(shè) 計 技 術(shù) 的 基 本 依 據(jù) 是 程 序 的 （）。3. 相聯(lián)度越高， （ ）失效就越少； （ ）失效不受 Cache 容量的影響，但（ ）失效卻隨著容量的增加而減少。4. 在 虛 擬 存 儲 器 中 ， 一 般 采 用 （） 地 址 映 象 方 法 和（）更新策略。5. 計算機系統(tǒng)中提高并行性的技術(shù)途徑有（） 、 （）和（）三種。在高性能單處理機的發(fā)展中，起主導(dǎo)作用的是（）。6. 在處理機中，若指令序列完成的順序

10、總是與它們開始執(zhí)行的順序保持一致，則只可能出現(xiàn)（ ）相關(guān) , 否則就有可能出現(xiàn)（ ） 、 （ ）和（ ）相關(guān)。7. 對向量的處理有（） 方式、 （） 方式、 （）方式。6 分，共 24 分）1. 任寫出三種Cache 的優(yōu)化技術(shù)，并簡述其基本思想。2. 在指令集結(jié)構(gòu)設(shè)計中，應(yīng)該考慮哪些主要問題？3. 數(shù)據(jù)相關(guān)有哪幾種類型？解決數(shù)據(jù)相關(guān)有哪些主要方法？4. 試以系列機為例， 說明計算機體系結(jié)構(gòu)、 計算機組成和計算機實現(xiàn)三者之間的關(guān)系。四、計算題1. 給定以下的假設(shè)， 試計算直接映象Cache 和兩路組相聯(lián)Cache 的平均訪問時間以及CPU的性能。由計算結(jié)果能得出什么結(jié)論？（1） 理想Cache

11、情況下的CPI為2.0 ,時鐘周期為2 ns,平均每條 指令訪存 1.4 次。（2） 兩者Cache容量土勻為128 KB,塊大小都是 32字節(jié)。（3） 組相聯(lián)Cache中的多路選擇器使 CPU的時鐘周期增加了 10%（4） 這兩種Cache的失效開銷都是80 ns。（5） 5） 命中時間為 1 個時鐘周期。（6） 128 KB直接映象 Cache的失效率為1.0%, 128 KB兩路組相聯(lián)Cache 的失效率為0.7%。 （15 分）（7） 算機系統(tǒng)字長 64位，包含三個選擇通道和一個多路通道，每個 選擇通道上連接了兩臺磁盤機和三臺磁帶機，多路通道上連接了了兩臺行 式打印機，兩臺讀卡機、10

12、臺終端，假定各設(shè)備的傳輸率如下：磁盤機：600 KBps,磁帶機：200 KBps,行打機：6.6 KBps ,讀卡機：1.2 KBps , 終 端：1 KBps。計算該計算機系統(tǒng)的最大I/O數(shù)據(jù)傳輸率。（6分）（8） 計算機系統(tǒng)采用浮點運算部件后使浮點運算速度提高到原來的 20倍，而系統(tǒng)運行一程序的整體性能提高到原來的10倍，試計算該程序中浮點操作所占的比例。（5分）4.動態(tài)多功能流水線由 6個功能段組成，如下圖所示:其中，s1、s4、s5、s6組成乘法流水線，s1、s2、s3、s6組成加法流水線， 各個功能段時間為：s1、s3、s4、s6為At, s2、s5為？ t ,假設(shè)該流水 線的輸出

13、結(jié)果可以直接返回輸入端，而且設(shè)置有足夠地緩沖寄存器，若以最快的方式用該流水計算：n （ Ai + Bi）（其中i =1.4 , 口為連乘符號） （1）畫出其處理過程的時空圖。（2）計算其實際的吞吐率和效率。（15分）20032004學(xué)年度第2學(xué)期計算機系統(tǒng)結(jié)構(gòu)試題 A答案、填空題：（）1 .由軟件實現(xiàn)的機器稱為虛擬機器；由硬件和微程序（固件）實現(xiàn)的機器稱為實際機器。2 .軟件和硬件在邏輯上是等效的。3 .由于軟、硬件緊密相關(guān)，軟硬界面常常是模糊不清的。4 .計算機組成設(shè)計主要是圍繞：1.提高速度，2.提高操作的并行度、重疊流水，3.分散功能，4.設(shè)置專用功能部件來進(jìn)行。5 .具有相同“系統(tǒng)結(jié)構(gòu)

14、”(如指令系統(tǒng)相同)的計算機可以因為速度 要求等因素的不同而采用不同的組成。6 . 一種“計算機組成”可以采用多種不同的“計算機實現(xiàn)”。7 .“計算機組成”反過來也會影響“系統(tǒng)結(jié)構(gòu)” 。8 .計算機系統(tǒng)結(jié)構(gòu)設(shè)計的主要任務(wù)是：進(jìn)行軟、硬件的功能分配。9 .計算機系統(tǒng)設(shè)計，從多級層次結(jié)構(gòu)出發(fā)，可以分為：由上往上 由下往上和從中間開始三種不同的設(shè)計思路。10 .計算機應(yīng)用可以歸納為向上升級的四類它們分別是：(1) 數(shù)據(jù)處理(Data Processing )。(2) 2)信息處理 I Information Processing )。(3) 知識處理(Knowledge Processing )。(

15、4) 智能處理(Intelligence Processing )。二、簡答題：1 .計算機實現(xiàn)(Computer Implementation ) ?:是指計算機組成的 物理實現(xiàn)，包括：處理機、主存等部件的物理結(jié)構(gòu)，器件的集成度和速度，器件、模塊、插件、底板的劃分與連接，專用器件的設(shè)計，微組裝技術(shù)， 信號傳輸，電源、冷卻及整機裝配技術(shù)等。2 .計算機組成(Computer Organization ) ?:是指計算機系統(tǒng)結(jié)構(gòu) 的邏輯實現(xiàn)，包括：機器級內(nèi)的數(shù)據(jù)流和控制流的組成以及邏輯設(shè)計等。3 .軟件的可移植性？是指軟件不用修改或只需經(jīng)少量加工就能由一 臺機器搬到另一臺機器上運行，即同一軟件可

16、以不同的系統(tǒng)環(huán)境。4 .向上(下)兼容？：是指按某檔機器編制的軟件，不加修改就能 運行于比它高(低)檔的機器上。5 .向前(后)兼容？：指的是，在按某個時期投入市場的該型號機 器上編制的軟件，不加修改就能運行在它之前(后)投入市場的機器上。6 .兼容機(Compatible Machine ) ?:具有同一系統(tǒng)結(jié)構(gòu)的計算機 稱為。采用兼容機的思想與采用系列機的思想實際上是一致的。7 .模擬(Simulation )：用機器語言程序解釋實現(xiàn)軟件移植的方法稱 為。8 .仿真(Emulation )：用微程序直接解釋另一種機器指令系統(tǒng)的方法 稱為。9 .現(xiàn)場片：使用戶可根據(jù)需要改變器件內(nèi)部的功能或內(nèi)

17、容，以適應(yīng)結(jié) 構(gòu)和組成變化的需要。10全用戶片：完全按用戶要求設(shè)計的用戶片稱為全用戶片。三、簡述題：1 算機系統(tǒng)結(jié)構(gòu)研究的是什么？答：軟、硬件之間的功能分配以及對傳統(tǒng)機器級界面的確定。2 計算機組成設(shè)計要解決的問題是什么？答：在所希望能達(dá)到的性能和價格比的前提下，怎樣最佳、最合理地把各種設(shè)備和部件組織成為一臺計算機，以實現(xiàn)所確定的系統(tǒng)結(jié)構(gòu)。3器件的發(fā)展對系統(tǒng)結(jié)構(gòu)的影響？（ 1）器件的發(fā)展改變了邏輯設(shè)計的傳統(tǒng)方法。（ 2）器件的發(fā)展也使系統(tǒng)結(jié)構(gòu)的“下移”速度加快。（ 3）器件的發(fā)展還促進(jìn)了算法、語言和軟件的發(fā)展。（ . 什么是并行性？只要在同一時刻或是在同一時間間隔內(nèi)完成兩種或兩種以上性質(zhì)相同或

18、不同的工作，它們在時間上能相互重疊，都體現(xiàn)了并行性。（ .CISC 指令系統(tǒng)的含義?復(fù)雜指令系統(tǒng)計算機，即機器指令系統(tǒng)變得越來越龐雜，這就是所謂的CISC指令系統(tǒng)。6. 什么是頁式存貯管理？頁式存貯管理是把主存空間和程序空間都機械地等分成固定大小的頁，按頁順序編號。 （頁面大小隨機器而異，一般在 512 到幾KB） 。7. 什么是向量流水處理機？向量流水處理機是將向量數(shù)據(jù)表示和流水線技術(shù)結(jié)合在一起，構(gòu)成向量流水處理機，簡稱向量流水處理機。8. 什么是相聯(lián)處理機？相聯(lián)處理機是以相聯(lián)存貯器為核心，配上必要的中央處理部件、指令存貯器、控制器和I/O 接口，就構(gòu)成一臺以存貯器操作并行為特點的相聯(lián)處理機

19、。18四、計算題：1.設(shè)一臺模型機有7條指令，其使用頻度為:指令I(lǐng)1使用頻度I0.05指令使用頻度0.03I I4I20.03I I50.15I30.04I I60.3II70.4求出：（1）利用哈夫曼（Huffman）壓縮技術(shù)，構(gòu)造哈夫曼樹；（2）.操作碼平均碼長和擴展碼長。要求:）1與10.6 00.030.030.040.05（2） H=2.17H=2.22.如果設(shè)一個系統(tǒng)后四個中斷級，個級中斷響應(yīng)次序為 中斷級屏蔽位表哈夫曼樹節(jié)點為0.150.30.41->2->3->4 。見中斷處理 程序級別中斷級屏敝位1級2級3級4級第1級0000第2級1000第3級1100第4

20、級1110求當(dāng)把中斷次序改為 1->4->3->2時，畫出中斷級屏蔽位表。中斷處理 程序級別中斷級屏敝位1級2級3級4級第1級0000第2級1011第3級1001第4級10003 .計算流水線實際吞吐率 TP和效率y o設(shè)有兩個向量 C和D,各有4個 元素，在圖中的靜態(tài)雙功能流水線上工作。其中，1->2->3->5組成加法流水線，1->4->5組成乘法流水線。設(shè)每個流水線所經(jīng)過的時間均為At,而且流水線的輸出結(jié)果可以直接返回到輸入或暫存于相應(yīng)的緩沖寄存器中， 其延遲時間和功能切換所需要的時間都可以忽略不計。求：該流水線的實 際吞吐率TP和效率Y。

21、實際吞吐率 TP=7/ (15At) r =32%4 .計算多級立方體互連網(wǎng)絡(luò)。見圖N=8多級立方體互連網(wǎng)絡(luò)，求當(dāng)輸入端級控制信號為 S2S1S0=010時，輸入端為0 1 2 3 4 5 6 7時，輸出端為:23016745。0 f 1 -2 >3 f4 >5 6 fs0sis2輸入輸出5.由表達(dá)式：E= a +bx+cx 2+dx3,利用減少樹高的辦法來加速運算，要求7 p=3 , T p =4, Sp =3/2, E p =1/2計算機系統(tǒng)結(jié)構(gòu)試題第一部分選擇題一、單項選擇題（每小題1分，共10分）在每小題的四個備答案中有一個正 確的答案，將正確答案的序號寫在題干后的括號內(nèi)）

22、1 .計算機使用的語言是（）A.專屬軟件范疇，與計算機體系結(jié)構(gòu)無關(guān)B.分屬于計算機系統(tǒng)各個層次C.屬于用以建立一個用戶的應(yīng)用環(huán)境D.屬于符號化的機器指令2 .動態(tài)數(shù)據(jù)流機最突出的特點是使（）A.數(shù)據(jù)流令牌無標(biāo)號B.需要程序記數(shù)器來實現(xiàn)C.令牌帶上標(biāo)號D.同步由門（Latch）寄存器來實現(xiàn)3 .多處理機上兩個程序段之間若有先寫后讀的數(shù)據(jù)相關(guān)，則 （）A.可以并行執(zhí)行B.不可能并行C.任何情況均可交換串行D.必須并行執(zhí)行4 .多處理機的各自獨立型操作系統(tǒng)（）A.要求管理程序不必是可再入的B.適合于緊耦合多處理機C.工作負(fù)荷較平衡D.有較高的可靠性5 .輸入輸出系統(tǒng)硬件的功能對（）是透明的。A.操作

23、系統(tǒng)程序員B.應(yīng)用程序員C.系統(tǒng)結(jié)構(gòu)設(shè)計人員D.機器語言程序設(shè)計員6 .“啟動I/O”指令是主要的輸入輸出指令，是屬于 ()A. 目態(tài)指令B. 管態(tài)指令C. 目態(tài)、管態(tài)都能用的指令D. 編譯程序只能用的指令7 .全相聯(lián)地址映象是指()A. 任何虛頁都可裝入主存中任何實頁的位置B. 一個虛頁只裝進(jìn)固定的主存實頁位置C. 組之間是固定的，而組內(nèi)任何虛頁可以裝入任何實頁位置D. 組間可任意裝入，組內(nèi)是固定裝入8 .()屬于MIMD 系統(tǒng)結(jié)構(gòu)。A. 各處理單元同時受同一個控制單元的管理B. 各處理單元同時接受同一個控制單元送來的指令C. 松耦合多處理機和多計算機D. 陣列處理機9 .設(shè)16個處理器編號

24、分別為 0, 1,2,，15用Cube3互聯(lián)函數(shù)時，第10 號處理機與第 () 號處理機相聯(lián)。A.11B.8C.14D.210 . 若輸入流水線的指令既無局部性相關(guān)，也不存在全局性相關(guān)，則 ()A. 可獲得高的吞吐率和效率B. 流水線的效率和吞吐率惡化C. 出現(xiàn)瓶頸D. 可靠性提高第二部分 非選擇題二、填空題(每空1 分，共20 分)11 . 標(biāo)志符與每個數(shù)據(jù)相連， 合存于 ， 用于描述單個數(shù)據(jù)的 。12 . 總線仲裁算法有：靜態(tài)優(yōu)先級算法、固定時間片算法、 算法和算法。13 . 計算機仿真用 解釋，計算機模擬用 解釋。14 . 按弗林 (Michael J.Flynn) 的觀點，計算機系統(tǒng)可

25、分為單指令流單數(shù)據(jù)流、 、多指令流單數(shù)據(jù)流和 四大類。15 . 要實現(xiàn)兩條指令在時間上重疊解釋，首先需要付出 ，其次，要處理好指令之間可能存在的 。16 . 與重疊機器一樣， 流水機器在遇到 指令， 尤其是 指令時，效率也會顯著下降。17 .超長指令字(VLIW) 結(jié)構(gòu)是將 和兩者相結(jié)合。18 . 互連網(wǎng)絡(luò)的交換方法主要有線路交換、包交換、線路/包交換，SIMD 互連網(wǎng)絡(luò)多采用 交換，多處理機常采用 交換。19 .數(shù)據(jù)流機采用 ,執(zhí)行的操作序列取決于輸入數(shù)據(jù)的可用性；歸 約機則采用 ,執(zhí)行的操作序列取決于對數(shù)據(jù)的要求，對數(shù)據(jù)的 需求又來源于函數(shù)式程序設(shè)計語言對表達(dá)式的歸納。20 .輸入輸出系統(tǒng)

26、包括輸入輸出設(shè)備、設(shè)備 及與輸入輸出操作有關(guān) 的 件。三、改錯題(每小題2分，共10分)(下列每小題劃線部分 A、B、C中有一 處錯誤，請先寫出錯處，并在括號中寫出正確文字)21 .對操作碼進(jìn)行優(yōu)化編碼時，在了解每種指令在程序中出現(xiàn)的概率后，使用 Huffman 算AB法構(gòu)造Huffman樹，這樣獲得的 Huffman編碼是唯一的。()C22 .多處理機中，兩個程序段之間若同時有先寫后讀和先讀后寫2種相關(guān)，以交換數(shù)據(jù)為目的時，則必須并行執(zhí)行，讀寫要完全同步，允許順序串行和交換串行。()ABC23 .計算機仿真適合在兩種結(jié)構(gòu)差距大的機器間運用。 ()ABC24 .豐存空間數(shù)相關(guān)是相間隔的兩條指令

27、之間出現(xiàn)對豐存同一單元要求先ABC()25 .由于Cache存貯器的地址變換和塊替換算法是用軟件實現(xiàn)的,因此 Cache存貯器對應(yīng)用A程序員是透明的，而且 Cache對處理機和主存間的信息交往也是透明的。()BC四、簡答題(每小題6分，共30分)26 .簡述標(biāo)志符數(shù)據(jù)表示的主要優(yōu)點。27 .簡述設(shè)計RISC結(jié)構(gòu)用了哪些基本技術(shù) ？28 .設(shè)Pi和Pj程序段都是一條語句，且 Pi在Pj之前執(zhí)行，試舉出 Pi和Pj間 存在3種可能的數(shù)據(jù)相關(guān)。29 .簡述控制驅(qū)動的控制流方式的特點？30 .模擬與仿真的主要區(qū)別和適合場合是什么？五、應(yīng)用題（共30分）31 .（12分）假設(shè)某模型機共有 7條指令，7條

28、指令I(lǐng)i17使用的頻度分別為：0.35,0.25,0.20,0.10,0.04,0.03,0.03。（1）利用Huffman算法，構(gòu)造Huffman樹，并給出Huffman編碼和平均 碼長。（2）給出Huffman擴展碼編碼。32 .（10分）多級混洗交換網(wǎng)絡(luò)是如何組成的？它與間接二進(jìn)制n立方體網(wǎng)絡(luò)有何差異？并畫出N=8時的多級混洗交換網(wǎng)絡(luò)圖。33 .（8分）設(shè)向量A和B各有4個元素在下圖所示的靜態(tài)雙功能流水線上計4算向量點積 AB=£ aibi ,其中1 一2一3一5組成加法流水線，1一41 =1一5組成乘法流水線。若假定流水線的各段所經(jīng)過的時間均為t=2.5,流水線輸出可直接送回

29、輸入或暫存于相應(yīng)緩沖寄存器中，其延遲時間和功能切換所需的時間都可忽略。求出吞吐率和加速比。 計算機系統(tǒng)結(jié)構(gòu)試題參考答案一、單項選擇題（每小題1分，共10分）5.B10.A1.B2.C3.B4.D6.B7.A8.C9.D二、填空題（每空1分，共20分）11 .同一存儲單元 類型特征12 .動態(tài)優(yōu)先級 先來先服務(wù)13 .微程序機器語言14 .單指令流多數(shù)據(jù)流多指令流多數(shù)據(jù)流15 .空間代價關(guān)聯(lián)16 .轉(zhuǎn)移條件轉(zhuǎn)移17 .水平型微碼超標(biāo)量處理18 .線路包19 .數(shù)據(jù)驅(qū)動需求驅(qū)動20 .控制器軟硬三、改錯題（每小題2分，共10分）21 .（C錯改為“不是唯一的”）22 .(C錯改為“不允許順序串行和

30、交換串行”)23 .(B錯改為“差距不大”)24 .(A錯改為“相鄰”)25 .(A錯改為“硬件”)四、簡答題(每小題6分，共30分)26 .(1)簡化了指令系統(tǒng)和程序設(shè)計；(2)簡化了編譯程序；(3)便于實現(xiàn)一致性校驗；(4)能由硬件自動變換數(shù)據(jù)類型；(5)支持?jǐn)?shù)據(jù)庫系統(tǒng)的實現(xiàn)與數(shù)據(jù)類型無關(guān)的要求；(6)為軟件調(diào)試和應(yīng)用軟件開發(fā)提供了支持。27 .(1)按RISC 一般原則設(shè)計；(2)邏輯實現(xiàn)用硬聯(lián)和微程序結(jié)合；(3)用重疊寄存器窗口 (4)指令用流水和延遲轉(zhuǎn)移；(5)優(yōu)化設(shè)計編 譯系統(tǒng)。28 .(1)若Pi的左部變量在 Pj的右部變量集內(nèi)，且Pi必須取出R運算的結(jié)果來作為操作數(shù)，則稱Pi

31、“數(shù)據(jù)相關(guān)”于 R。(2)若Pj的左部變量在 Pi的右部變量集內(nèi)，且當(dāng)Pi未取用其變量的值之前，是不允許被Pj所改變，則稱 Pi “數(shù)據(jù)反相關(guān)”于Pj。(3)若Pi的左部變量也是 Pj的右部變量，且 Pj存入其算得的值必 須在Pi存入之后，則稱Pj “數(shù)據(jù)輸出相關(guān)”于 Pi。29 .控制驅(qū)動的控制流方式的特點是：通過訪問共享存儲單元讓數(shù)據(jù)在指令之間傳遞；指令的執(zhí)行順序隱含于控制流中， 可以顯式 地使用專門的控制操作符來實現(xiàn)并行處理，指令執(zhí)行順序受程度計數(shù)器的控制，即受控制令牌所支配。30 .模擬與仿真的主要區(qū)別在于解釋用的語言。仿真是用微程序解釋，其解釋程序存在控制存儲器中，而模擬是用機器語言

32、程序解釋， 其解釋程序存在主存中。模擬靈活，可實現(xiàn)不同系統(tǒng)間的軟件移 植，但結(jié)構(gòu)差異太大時，效率、速度會急劇下降。仿真在速度上 損失小，但不靈活，只能在差別不大的系統(tǒng)之間使用，否則效率 也會過低且難以仿真，需與模擬結(jié)合才行。五、應(yīng)用題(共30分)平均碼性=亢P/$ 與a- L國 Huffman 樹4 T一步 ,31.表操作碼的Huffman碼及擴展操作碼的編碼指令頻度（Pi）操作碼使用Huffman 編碼OP長度(Li )利用 Huffman 概念的擴展操作碼OP長度(Li )I 10. 35010 02I 20. 251 020 12I 30.201 1 031 02I 40.101 1 1

33、 0 051 1 0 04I 50.041 1 1 0 151 1 0 14I 60.031 1 1 1 051 1 1 04I 70.031 1 1 1 151 1 1 1432.多級混洗交換網(wǎng)絡(luò)由 n級相同的網(wǎng)絡(luò)組成，每一級都包含一個全混拓?fù)浜碗S后一列 2n-1個四功能交換單元，采用單元控制方式。多級混洗交換網(wǎng)絡(luò)與間接二進(jìn)制n方體網(wǎng)絡(luò)只有兩點差別：前者數(shù)據(jù)流向的級號順序n-1,n-2,，1, 0,用四功能交換單元，后者數(shù)據(jù)流向相反，其級號順序0, 1，,n-1,用二功能交換單元。33.實際吞吐率為 =-7=18.7%15.：t15 25因順序方式所需時間為4父3& +3父4氏 =2

34、4& ,因此加速比 Sp=24：t/15.4=1.6(1) 30 分)解釋下列術(shù)語(1)馮 諾依曼結(jié)構(gòu)：馮 諾依曼等人于1 9 4 6年提出了一個完整的現(xiàn)代計算機雛型，它由運算器、控制器、存儲器和輸入輸出設(shè)備組成，這種結(jié)構(gòu)稱為馮諾依曼結(jié)構(gòu)。(2) 數(shù)據(jù)表示：數(shù)據(jù)表示研究的是計算機硬件能夠直接識別，可以被指令系統(tǒng)直接調(diào)用的那些數(shù)據(jù)類型。數(shù)據(jù)表示是數(shù)據(jù)類型中最常用，也是相對比較簡單，用硬件實現(xiàn)相對比較容易的幾種。如定點數(shù)(整數(shù))、邏輯數(shù)(布爾數(shù))、浮點數(shù)(實數(shù))、十進(jìn)制數(shù)、字符、字符串、堆棧和向量等。(3)CISC ：復(fù)雜指令系統(tǒng)計算機(4) 存儲系統(tǒng)：兩個或兩個以上速度、容量和價格各不相

35、同的存儲器用硬件、軟件、或軟件與硬件相結(jié)合的方法連接起來成為一個系統(tǒng)，這就是存儲系統(tǒng)。(5) 時空圖：描述流水線的工作，最常用的方法是采用 “時空圖 ”。在時空圖中，橫坐標(biāo)表示時間，也就是輸入到流水線中的各個任務(wù)在流水線中所經(jīng)過的時間。當(dāng)流水線中的各個功能部件的執(zhí)行時間都相等時，橫坐標(biāo)被分割成相等長度的時間段?？v坐標(biāo)表示空間，即流水線的各個子過程。在時空圖中，流水線的一個子過程通常稱為 “功能段 ” 。(6) 多功能流水線：多功能流水線( Multifunction Pipelining )是指流水線的各段可以進(jìn)行不同的連接。在不同時間內(nèi)，或在同一時間內(nèi)，通過不同的連接方式實現(xiàn)不同的功能。(7

36、) 加速比：完成一批任務(wù)，不使用流水線所用的時間與使用流水線所用的時間之比稱為流水線的加速比( Speedup ratio )。(8) 鏈接技術(shù)：鏈接是當(dāng)從一個流水線部件得到的結(jié)果直接送入另一個功能流水線的操作數(shù)寄存器時所發(fā)生的連接過程。換句話說，中間結(jié)果不必送回存儲器，而且甚至在向量操作完成以前就使用。鏈接允許當(dāng)?shù)谝粋€結(jié)果一變成可用的操作數(shù)時就馬上發(fā)出相繼的操作。(9) 存儲轉(zhuǎn)發(fā)尋徑：存儲轉(zhuǎn)發(fā)尋徑(store and forward) 在存儲轉(zhuǎn)發(fā)網(wǎng)絡(luò)中包是信息流的基本單位。每個結(jié)點有一個包緩沖區(qū)。包從源結(jié)點經(jīng)過一系列中間結(jié)點到達(dá)目的結(jié)點。(10) 蟲蝕尋徑 (wormhole) ： 新型的多計算機系統(tǒng)很多采用的是蟲蝕尋徑方式， 把包進(jìn)一步分成更小的片。 與結(jié)點相連的硬件尋徑器中有片緩沖區(qū)。消息從源結(jié)點傳送到目的結(jié)點要經(jīng)過一系列尋徑器。2 .(20 分，每空一分)填空(1) 衡量流水線性能通常有三種主要指標(biāo)， 它們是吞吐率、 加速比和效率。(2) 按照 Flynn 分類法 ,根據(jù)指令流和數(shù)據(jù)流的不同組織方式,計算機系統(tǒng)的結(jié)構(gòu)可以分為SISD( 單指令流單數(shù)據(jù)流) 、 _ SIMD MISD MIMD 或者單指令流多數(shù)據(jù)流 多指令流單數(shù)據(jù)流 多指令流多數(shù)據(jù)流