2009-2010學(xué)年度第一學(xué)期2007級(jí)《計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)》期末考試試卷（A）（閉卷）姓名：學(xué)號(hào)：專(zhuān)業(yè)：（注：①考試時(shí)間為120分鐘；②所有解答必須寫(xiě)在答題紙上。）一、單項(xiàng)選擇題（每小題3分，共30分）1、在系列機(jī)中發(fā)展一種新型號(hào)機(jī)器，你認(rèn)為下列（）設(shè)想是不行的？【A】新增加字符數(shù)據(jù)類(lèi)型和若干條字符處理指令【B】將中斷分級(jí)由原來(lái)的4級(jí)增加到5級(jí)【C】在CPU和主存之間增設(shè)Cache存貯器【D】將浮點(diǎn)數(shù)的下溢處理法由原來(lái)的恒置“1”法，改為查表舍入法2、對(duì)計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)來(lái)說(shuō)，不透明的是（）?！続】存儲(chǔ)器采用交叉存取還是并行存取【B】CPU內(nèi)部的數(shù)據(jù)通路的寬度是8位還是16位【C】采用浮點(diǎn)數(shù)據(jù)表示還是標(biāo)志符數(shù)據(jù)表示【D】指令采用硬聯(lián)邏輯實(shí)現(xiàn)還是微程序?qū)崿F(xiàn)3、一個(gè)平衡的計(jì)算機(jī)系統(tǒng)，應(yīng)該是（）?！続】1MIPS的CPU速度【B】1MB的主存容量【C】1Mb/s的I/O吞吐率【D】A、B和C4、（）設(shè)計(jì)是現(xiàn)代計(jì)算機(jī)系統(tǒng)設(shè)計(jì)所采用的方法。【A】由上往下【B】由下往上【C】由中間開(kāi)始【D】上下同時(shí)開(kāi)始5、當(dāng)今微型機(jī)中實(shí)現(xiàn)軟件移植最好的方法是（）?！続】系列機(jī)【B】兼容機(jī)【C】仿真技術(shù)【D】統(tǒng)一高級(jí)語(yǔ)言6、不能夠?qū)ο蛄繑?shù)據(jù)結(jié)構(gòu)提供直接支持的是（）數(shù)據(jù)表示?！続】向量【B】堆?！綜】描述符【D】A和C7、采用整數(shù)邊界存儲(chǔ)技術(shù)，其主要目的是（）。【A】節(jié)約主存空間【B】提高數(shù)據(jù)的訪(fǎng)問(wèn)速度【C】一個(gè)主存周期可取多條指令【D】一個(gè)主存周期至少可取到一條指令8、在指令的操作碼編碼方式中，優(yōu)化實(shí)用的編碼是（）。[A]Huffman編碼【B】等長(zhǎng)編碼【C】Huffman擴(kuò)展編碼【D】BCD碼9、流水計(jì)算機(jī)中將指令Cache和數(shù)據(jù)Cache分開(kāi)，主要是為了（）?！続】提高存儲(chǔ)系統(tǒng)的速度【B】增加主存容量[C]解決功能部件沖突【D】解決訪(fǎng)存沖突10、當(dāng)N=16時(shí)，能描述4組4元交換的函數(shù)是（）。[A]C1+C2[B]C0+C1[C]C0+C2[D]C2+C3二、（10分）在采用通用寄存器指令集結(jié)構(gòu)的計(jì)算機(jī)上得到了如下所示的數(shù)據(jù):指令類(lèi)型執(zhí)行頻率時(shí)鐘周期數(shù)ALU指令43%1LOAD指令21%2STORE指令12%2分支指令24%2三、（10分）設(shè)某機(jī)器系統(tǒng)指令字長(zhǎng)12位，每個(gè)操作碼和地址均占3位，試提出一種分配方案，使該指令系統(tǒng)有4條三地址指令，8條二地址指令和180條單地址指令。四、（10分）設(shè)通道在數(shù)據(jù)傳送期中，選擇設(shè)備需4.9uS，傳送一個(gè)字節(jié)數(shù)據(jù)需0.1US。（1）其低速設(shè)備每隔250US發(fā)出一個(gè)字節(jié)數(shù)據(jù)傳送請(qǐng)求，問(wèn)最多可接多少臺(tái)這種設(shè)備？（2）若有A?E共5種高速設(shè)備，要求字節(jié)傳送的間隔時(shí)間如下表所示，其時(shí)間單位為uS。若一次通信傳送的字節(jié)數(shù)不少于1024個(gè)字節(jié)，問(wèn)哪些設(shè)備可掛在此通道上？哪些則不能？設(shè)備ABCDE時(shí)間間隔（uS）0.130.10.110.20.3五、（10分）有一非線(xiàn)線(xiàn)性流水線(xiàn)預(yù)約表如下。功能段123456S1VVS2VVVS3VVS4V（1）求平均延遲最小的最佳調(diào)度方案；（2）畫(huà)出按最佳方案之一連續(xù)輸入3個(gè)任務(wù)的時(shí)空?qǐng)D。六、（10分）有一四段線(xiàn)性流水線(xiàn)，每功能段延時(shí)時(shí)間分別是：At1=At3=At4=At0,△t「3△t°。若在這個(gè)流水線(xiàn)上執(zhí)行40個(gè)任務(wù)。求實(shí)際吞吐率、效率和加速比。4°2七、（10分）N=8個(gè)結(jié)點(diǎn)的三級(jí)立方體網(wǎng)絡(luò)如下圖所示。當(dāng)K1=0時(shí)，試說(shuō)明輸入4號(hào)結(jié)點(diǎn)不能實(shí)現(xiàn)和哪些輸出結(jié)點(diǎn)相連？1輸出端輸出端八、（10分）在8個(gè)PE構(gòu)成的雙向環(huán)互連的并行處理機(jī)中，計(jì)算點(diǎn)積S=才axb（n=8）ii（全部試題完）武漢大學(xué)計(jì)算機(jī)學(xué)院2009-2010學(xué)年度第二學(xué)期2007級(jí)《計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)》期末考試試卷（A）參考答案一、（每小題3分，共30分）［解］:1-10：BCDCABDCDB二、（10分）［解］:MIPS_RCPIx106xoldCPI1.57??—q09—c?.MIPSCPIX106RCPI1.73oldnewcnew三、（10分）［解］:000XXXXXXXXX011XXXXXXXXX100000XXXXXX100111XXXXXX101000000XXX［101111111XXXF64+116=180110000000XXX111110011XXXJ四、（10分）［解］：（1）低速設(shè)備應(yīng)接字節(jié)多路通道11>1f==>nxmax.byteT+TD4.9+0.1—250所以，nW50臺(tái)，即最多可接50臺(tái)（2）根據(jù)題意，此通道為選擇通道f=1=1max.selectt+ts0.1+4.9dnn其中，nN1024，應(yīng)使/select?iW/max?select，由此可得出通道工作周期為：T%0.1014（us）所以，只有A、C、D、E可掛在此通道上，B則不行。五、（10分）［解］：（1）狀態(tài)圖略。最佳調(diào)度方案為（3）和（1.5）六、（10分）［解］:TP===6At+(40-1)At6At+39x3At123Atj40404040x6AtE=w48.8%4x123AtSP40x6At123Atw1.95七、(10分"=4x8+3=35=175(MIPS)［解］：不能與輸出5的務(wù)+4x8)x5結(jié)點(diǎn)帷。5ns八、（10分）［解］：需要8次乘法，7次加法;共14At計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)SP40x6At123Atw1.95姓名：學(xué)號(hào)：、名詞解釋?zhuān)款}3分，共15分）Cache2:1經(jīng)驗(yàn)規(guī)則同構(gòu)型多處理機(jī)堆棧型機(jī)器計(jì)算機(jī)體系結(jié)構(gòu)通道處理機(jī)二、填空（每空1分，共20分）設(shè)計(jì)I/O系統(tǒng)的三個(gè)標(biāo)準(zhǔn)是（）、（）和（）。存儲(chǔ)器層次結(jié)構(gòu)設(shè)計(jì)技術(shù)的基本依據(jù)是程序的（）。相聯(lián)度越高，（）失效就越少；（）失效不受Cache容量的影響，但、）失效卻隨著容量的增加而減少。在虛擬存儲(chǔ)器中，一般采用（）地址映象方法和（）更新策略。TOC\o"1-5"\h\z計(jì)算機(jī)系統(tǒng)中提高并行性的技術(shù)途徑有（）、（）和、）三種。在高性能單處理機(jī)的發(fā)展中，起主導(dǎo)作用的是（）。在處理機(jī)中，若指令序列完成的順序總是與它們開(kāi)始執(zhí)行的順序保持一致，則只可能出現(xiàn)、）相關(guān),否則就有可能出現(xiàn)、）、（）和（）相關(guān)。對(duì)向量的處理有（）方式、、）方式、、）方式。三、簡(jiǎn)答題（每題6分，共24分）任寫(xiě)出三種Cache的優(yōu)化技術(shù)，并簡(jiǎn)述其基本思想。在指令集結(jié)構(gòu)設(shè)計(jì)中，應(yīng)該考慮哪些主要問(wèn)題？數(shù)據(jù)相關(guān)有哪幾種類(lèi)型？解決數(shù)據(jù)相關(guān)有哪些主要方法？試以系列機(jī)為例，說(shuō)明計(jì)算機(jī)體系結(jié)構(gòu)、計(jì)算機(jī)組成和計(jì)算機(jī)實(shí)現(xiàn)三者之間的關(guān)系。四、計(jì)算題給定以下的假設(shè)，試計(jì)算直接映象Cache和兩路組相聯(lián)Cache的平均訪(fǎng)問(wèn)時(shí)間以及CPU的性能。由計(jì)算結(jié)果能得出什么結(jié)論？（1）理想Cache情況下的CPI為2.0，時(shí)鐘周期為2ns，平均每條指令訪(fǎng)存1.4次。（2）兩者Cache容量均為128KB，塊大小都是32字節(jié)。（3）組相聯(lián)Cache中的多路選擇器使CPU的時(shí)鐘周期增加了10%。（4）這兩種Cache的失效開(kāi)銷(xiāo)都是80ns。（5）命中時(shí)間為1個(gè)時(shí)鐘周期。（6）128KB直接映象Cache的失效率為1.0%，128KB兩路組相聯(lián)Cache的失效率為0.7%。（15分）計(jì)算機(jī)系統(tǒng)字長(zhǎng)64位，包含三個(gè)選擇通道和一個(gè)多路通道，每個(gè)選擇通道上連接了兩臺(tái)磁盤(pán)機(jī)和三臺(tái)磁帶機(jī)，多路通道上連接了了兩臺(tái)行式打印機(jī)，兩臺(tái)讀卡機(jī)、10臺(tái)終端，假定各設(shè)備的傳輸率如下：磁盤(pán)機(jī)：600KBps，磁帶機(jī)：200KBps，行打機(jī)：6.6KBps，讀卡機(jī)：1.2KBps，終端：1KBps。計(jì)算該計(jì)算機(jī)系統(tǒng)的最大I/O數(shù)據(jù)傳輸率。（6分）某計(jì)算機(jī)系統(tǒng)采用浮點(diǎn)運(yùn)算部件后使浮點(diǎn)運(yùn)算速度提高到原來(lái)的20倍，而系統(tǒng)運(yùn)行一程序的整體性能提高到原來(lái)的10倍，試計(jì)算該程序中浮點(diǎn)操作所占的比例。（5分）4.動(dòng)態(tài)多功能流水線(xiàn)由6個(gè)功能段組成，如下圖所示:其中，s1、s4、s5、s6組成乘法流水線(xiàn)，s1、s2、s3、s6組成加法流水線(xiàn)，各個(gè)功能段時(shí)間為：s1、s3、s4、s6為△《，s2、s5為2^t，假設(shè)該流水線(xiàn)的輸出結(jié)果可以直接返回輸入端，而且設(shè)置有足夠地緩沖寄存器，若以最快的方式用該流水計(jì)算：n（Ai+Bi）（其中i=1..4，n為連乘符號(hào)）（1）畫(huà)出其處理過(guò)程的時(shí)空?qǐng)D。（2）計(jì)算其實(shí)際的吞吐率和效率。（15分）2003?2004學(xué)年度第2學(xué)期《計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)》試題A答案、填空題：（）由軟件實(shí)現(xiàn)的機(jī)器稱(chēng)為虛擬機(jī)器；由硬件和微程序（固件）實(shí)現(xiàn)的機(jī)器稱(chēng)為實(shí)際機(jī)器。軟件和硬件在邏輯上是等效的。由于軟、硬件緊密相關(guān)，軟硬界面常常是模糊不清的。計(jì)算機(jī)組成設(shè)計(jì)主要是圍繞：1.提高速度，2.提高操作的并行度、重疊流水，3.分散功能，4.設(shè)置專(zhuān)用功能部件來(lái)進(jìn)行。具有相同“系統(tǒng)結(jié)構(gòu)”(如指令系統(tǒng)相同)的計(jì)算機(jī)可以因?yàn)樗俣纫蟮纫蛩氐牟煌捎貌煌慕M成。一種“計(jì)算機(jī)組成”可以采用多種不同的“計(jì)算機(jī)實(shí)現(xiàn)”。“計(jì)算機(jī)組成”反過(guò)來(lái)也會(huì)影響“系統(tǒng)結(jié)構(gòu)”。計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)設(shè)計(jì)的主要任務(wù)是：進(jìn)行軟、硬件的功能分配。計(jì)算機(jī)系統(tǒng)設(shè)計(jì)，從多級(jí)層次結(jié)構(gòu)出發(fā)，可以分為：由上往下、中下往上和從中間開(kāi)始三種不同的設(shè)計(jì)思路。計(jì)算機(jī)應(yīng)用可以歸納為向上升級(jí)的四類(lèi)它們分別是：數(shù)據(jù)處理(DataProcessing)。信息處理(InformationProcessing)。知識(shí)處理(KnowledgeProcessing)。智能處理(IntelligenceProcessing)。二、簡(jiǎn)答題：.計(jì)算機(jī)實(shí)現(xiàn)(ComputerImplementation)?:是指計(jì)算機(jī)組成的物理實(shí)現(xiàn)，包括：處理機(jī)、主存等部件的物理結(jié)構(gòu)，器件的集成度和速度，器件、模塊、插件、底板的劃分與連接，專(zhuān)用器件的設(shè)計(jì)，微組裝技術(shù)，信號(hào)傳輸，電源、冷卻及整機(jī)裝配技術(shù)等。.計(jì)算機(jī)組成(ComputerOrganization)?:是指計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)的邏輯實(shí)現(xiàn)，包括：機(jī)器級(jí)內(nèi)的數(shù)據(jù)流和控制流的組成以及邏輯設(shè)計(jì)等。軟件的可移植性？是指軟件不用修改或只需經(jīng)少量加工就能由一臺(tái)機(jī)器搬到另一臺(tái)機(jī)器上運(yùn)行，即同一軟件可以不同的系統(tǒng)環(huán)境。向上(下)兼容？：是指按某檔機(jī)器編制的軟件，不加修改就能運(yùn)行于比它高(低)檔的機(jī)器上。向前(后)兼容？：指的是，在按某個(gè)時(shí)期投入市場(chǎng)的該型號(hào)機(jī)器上編制的軟件，不加修改就能運(yùn)行在它之前(后)投入市場(chǎng)的機(jī)器上。兼容機(jī)(CompatibleMachine)?：具有同一系統(tǒng)結(jié)構(gòu)的計(jì)算機(jī)稱(chēng)為~。采用兼容機(jī)的思想與采用系列機(jī)的思想實(shí)際上是一致的。模擬(Simulation)：用機(jī)器語(yǔ)言程序解釋實(shí)現(xiàn)軟件移植的方法稱(chēng)為~。仿真(Emulation)：用微程序直接解釋另一種機(jī)器指令系統(tǒng)的方法稱(chēng)為~。現(xiàn)場(chǎng)片：使用戶(hù)可根據(jù)需要改變器件內(nèi)部的功能或內(nèi)容，以適應(yīng)結(jié)構(gòu)和組成變化的需要。全用戶(hù)片：完全按用戶(hù)要求設(shè)計(jì)的用戶(hù)片稱(chēng)為全用戶(hù)片。三、簡(jiǎn)述題：算機(jī)系統(tǒng)結(jié)構(gòu)研究的是什么？答：軟、硬件之間的功能分配以及對(duì)傳統(tǒng)機(jī)器級(jí)界面的確定。計(jì)算機(jī)組成設(shè)計(jì)要解決的問(wèn)題是什么？答：在所希望能達(dá)到的性能和價(jià)格比的前提下，怎樣最佳、最合理地把各種設(shè)備和部件組織成為一臺(tái)計(jì)算機(jī)，以實(shí)現(xiàn)所確定的系統(tǒng)結(jié)構(gòu)。器件的發(fā)展對(duì)系統(tǒng)結(jié)構(gòu)的影響？器件的發(fā)展改變了邏輯設(shè)計(jì)的傳統(tǒng)方法。器件的發(fā)展也使系統(tǒng)結(jié)構(gòu)的“下移”速度加快。器件的發(fā)展還促進(jìn)了算法、語(yǔ)言和軟件的發(fā)展。什么是并行性？只要在同一時(shí)刻或是在同一時(shí)間間隔內(nèi)完成兩種或兩種以上性質(zhì)相同或不同的工作，它們?cè)跁r(shí)間上能相互重疊，都體現(xiàn)了并行性。CISC指令系統(tǒng)的含義？復(fù)雜指令系統(tǒng)計(jì)算機(jī)，即機(jī)器指令系統(tǒng)變得越來(lái)越龐雜，這就是所謂的CISC指令系統(tǒng)。什么是頁(yè)式存貯管理？頁(yè)式存貯管理是把主存空間和程序空間都機(jī)械地等分成固定大小的頁(yè)，按頁(yè)順序編號(hào)。(頁(yè)面大小隨機(jī)器而異，一般在512到幾KB)。什么是向量流水處理機(jī)？向量流水處理機(jī)是將向量數(shù)據(jù)表示和流水線(xiàn)技術(shù)結(jié)合在一起，構(gòu)成向量流水處理機(jī)，簡(jiǎn)稱(chēng)向量流水處理機(jī)。什么是相聯(lián)處理機(jī)？相聯(lián)處理機(jī)是以相聯(lián)存貯器為核心，配上必要的中央處理部件、指令存貯器、控制器和I/O接口，就構(gòu)成一臺(tái)以存貯器操作并行為特點(diǎn)的相聯(lián)處理機(jī)。

四、計(jì)算題：設(shè)一臺(tái)模型機(jī)有7條指令，其使用頻度為:指令使用頻度I指令使用頻度I10.03II40.05I20.03|I50.15I30.04|I60.3II70.4求出：（1）利用哈夫曼（Huffman）壓縮技術(shù)，構(gòu)造哈夫曼樹(shù)；（2）.操作碼平均碼長(zhǎng)和擴(kuò)展碼長(zhǎng)。要求：哈夫曼樹(shù)節(jié)點(diǎn)為H=2.2如果設(shè)一個(gè)系統(tǒng)有四個(gè)中斷級(jí)，個(gè)級(jí)中斷響應(yīng)次序?yàn)?->2->3->4。見(jiàn)中斷級(jí)屏蔽位表

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

實(shí)際吞吐率TP=7/(15At)n=32%計(jì)算多級(jí)立方體互連網(wǎng)絡(luò)。見(jiàn)圖N=8多級(jí)立方體互連網(wǎng)絡(luò)，求當(dāng)輸入端級(jí)控制信號(hào)為S2S1S0=010時(shí)，輸入端為01234567時(shí)，輸出端為:23016745。*0123456s0sis2*0123456輸輸出5.由表達(dá)式：E=a+bx+cx2+dx3，利用減少樹(shù)高的辦法來(lái)加速運(yùn)算，要求p=3,Tp=4Sp=3/2,Ep=1/2計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)試題

第一部分選擇題一、單項(xiàng)選擇題（每小題1分，共10分）在每小題的四個(gè)備答案中有一個(gè)正確的答案，將正確答案的序號(hào)寫(xiě)在題干后的括號(hào)內(nèi)）計(jì)算機(jī)使用的語(yǔ)言是（）專(zhuān)屬軟件范疇，與計(jì)算機(jī)體系結(jié)構(gòu)無(wú)關(guān)分屬于計(jì)算機(jī)系統(tǒng)各個(gè)層次屬于用以建立一個(gè)用戶(hù)的應(yīng)用環(huán)境屬于符號(hào)化的機(jī)器指令動(dòng)態(tài)數(shù)據(jù)流機(jī)最突出的特點(diǎn)是使（）數(shù)據(jù)流令牌無(wú)標(biāo)號(hào)需要程序記數(shù)器來(lái)實(shí)現(xiàn)令牌帶上標(biāo)號(hào)同步由門(mén)（Latch）寄存器來(lái)實(shí)現(xiàn)多處理機(jī)上兩個(gè)程序段之間若有先寫(xiě)后讀的數(shù)據(jù)相關(guān)，貝火）可以并行執(zhí)行不可能并行任何情況均可交換串行必須并行執(zhí)行多處理機(jī)的各自獨(dú)立型操作系統(tǒng)（）要求管理程序不必是可再入的適合于緊耦合多處理機(jī)工作負(fù)荷較平衡有較高的可靠性輸入輸出系統(tǒng)硬件的功能對(duì)（）是透明的。操作系統(tǒng)程序員應(yīng)用程序員系統(tǒng)結(jié)構(gòu)設(shè)計(jì)人員機(jī)器語(yǔ)言程序設(shè)計(jì)員“啟動(dòng)I/O”指令是主要的輸入輸出指令，是屬于（）目態(tài)指令管態(tài)指令。.目態(tài)、管態(tài)都能用的指令D.編譯程序只能用的指令全相聯(lián)地址映象是指（）任何虛頁(yè)都可裝入主存中任何實(shí)頁(yè)的位置一個(gè)虛頁(yè)只裝進(jìn)固定的主存實(shí)頁(yè)位置組之間是固定的，而組內(nèi)任何虛頁(yè)可以裝入任何實(shí)頁(yè)位置組間可任意裝入，組內(nèi)是固定裝入（）屬于MIMD系統(tǒng)結(jié)構(gòu)。各處理單元同時(shí)受同一個(gè)控制單元的管理各處理單元同時(shí)接受同一個(gè)控制單元送來(lái)的指令松耦合多處理機(jī)和多計(jì)算機(jī)陣列處理機(jī)設(shè)16個(gè)處理器編號(hào)分別為0，1，2,…，15用Cube3互聯(lián)函數(shù)時(shí)，第10號(hào)處理機(jī)與第（）號(hào)處理機(jī)相聯(lián)。A,11B.8C.14D.2若輸入流水線(xiàn)的指令既無(wú)局部性相關(guān)，也不存在全局性相關(guān)，則（）可獲得高的吞吐率和效率流水線(xiàn)的效率和吞吐率惡化出現(xiàn)瓶頸可靠性提高第二部分非選擇題二、填空題（每空1分，共20分）標(biāo)志符與每個(gè)數(shù)據(jù)相連，合存于，用于描述單個(gè)數(shù)據(jù)的?？偩€(xiàn)仲裁算法有：靜態(tài)優(yōu)先級(jí)算法、固定時(shí)間片算法、算法和算法。計(jì)算機(jī)仿真用解釋?zhuān)?jì)算機(jī)模擬用釋。按弗林（MichaelJ.Flynn^觀點(diǎn)，計(jì)算機(jī)系統(tǒng)可分為單指令流單數(shù)據(jù)流、、多指令流單數(shù)據(jù)流和四大類(lèi)。要實(shí)現(xiàn)兩條指令在時(shí)間上重疊解釋?zhuān)紫刃枰冻?，其次，要處理好指令之間可能存在的。與重疊機(jī)器一樣，流水機(jī)器在遇到指令，尤其是指令時(shí)，效率也會(huì)顯著下降。超長(zhǎng)指令字（VLIW）結(jié)構(gòu)是將和兩者相結(jié)合?；ミB網(wǎng)絡(luò)的交換方法主要有線(xiàn)路交換、包交換、線(xiàn)路包交換，SIMD互連網(wǎng)絡(luò)多采用交換，多處理機(jī)常采用交換。數(shù)據(jù)流機(jī)采用，執(zhí)行的操作序列取決于輸入數(shù)據(jù)的可用性；歸約機(jī)則采用，執(zhí)行的操作序列取決于對(duì)數(shù)據(jù)的要求，對(duì)數(shù)據(jù)的需求又來(lái)源于函數(shù)式程序設(shè)計(jì)語(yǔ)言對(duì)表達(dá)式的歸納。輸入輸出系統(tǒng)包括輸入輸出設(shè)備、設(shè)備及與輸入輸出操作有關(guān)的件。三、改錯(cuò)題(每小題2分，共10分)(下列每小題劃線(xiàn)部分A、B、C中有一處錯(cuò)誤，請(qǐng)先寫(xiě)出錯(cuò)處，并在括號(hào)中寫(xiě)出正確文字)對(duì)操作碼進(jìn)行優(yōu)化編碼時(shí)，在了解每種指令在程序中出現(xiàn)的概率后，使用Huffman算ABTOC\o"1-5"\h\z\o"CurrentDocument"法構(gòu)造Huffman樹(shù)，這樣獲得的Huffman編碼是唯一的。()C多處理機(jī)中，兩個(gè)程序段之間若同時(shí)有先寫(xiě)后讀和先讀后寫(xiě)2種相關(guān)，以交換數(shù)據(jù)為目的時(shí)，則必須并行執(zhí)行，讀寫(xiě)要完全同步，允許順序串行和交換串行。()ABC計(jì)算機(jī)仿真適合在兩種結(jié)構(gòu)差距大的機(jī)器間運(yùn)用。()ABC主存空間數(shù)相關(guān)是相間隔的兩條指令之間出現(xiàn)對(duì)主存同一單元要求先寫(xiě)而后讀的關(guān)聯(lián)。ABC()由于Cache存貯器的地址變換和塊替換算法是用軟件實(shí)現(xiàn)的，因此Cache存貯器對(duì)應(yīng)用A程序員是透明的，而且Cache對(duì)處理機(jī)和主存間的信息交往也是透明的。()BC四、簡(jiǎn)答題(每小題6分，共30分)簡(jiǎn)述標(biāo)志符數(shù)據(jù)表示的主要優(yōu)點(diǎn)。簡(jiǎn)述設(shè)計(jì)RISC結(jié)構(gòu)用了哪些基本技術(shù)？設(shè)4和馬程序段都是一條語(yǔ)句，且4在馬之前執(zhí)行，試舉出當(dāng)和馬間存在3種可能的數(shù)據(jù)相關(guān)。簡(jiǎn)述控制驅(qū)動(dòng)的控制流方式的特點(diǎn)？模擬與仿真的主要區(qū)別和適合場(chǎng)合是什么？五、應(yīng)用題（共30分）（12分）假設(shè)某模型機(jī)共有7條指令，7條指令I(lǐng)1—17使用的頻度分別為:0.35,0.25,0.20,0.10,0.04,0.03,0.03。（1）利用Huffman算法，構(gòu)造Huffman樹(shù)，并給出Huffman編碼和平均碼長(zhǎng)。（2）給出Huffman擴(kuò)展碼編碼。（10分）多級(jí)混洗交換網(wǎng)絡(luò)是如何組成的？它與間接二進(jìn)制n立方體網(wǎng)絡(luò)有何差異?并畫(huà)出N=8時(shí)的多級(jí)混洗交換網(wǎng)絡(luò)圖。（8分）設(shè)向量A和B各有4個(gè)元素在下圖所示的靜態(tài)雙功能流水線(xiàn)上計(jì)4算向量點(diǎn)積A?B=￡aQi，其中1—2—3—5組成加法流水線(xiàn)，1—4i=1—5組成乘法流水線(xiàn)。若假定流水線(xiàn)的各段所經(jīng)過(guò)的時(shí)間均為△t=2.5,流水線(xiàn)輸出可直接送回輸入或暫存于相應(yīng)緩沖寄存器中，其延遲時(shí)間Y和功能切換所需的時(shí)間都可忽略。求出吞吐率和加速比。計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)試題參考答案一、單項(xiàng)選擇題（每小題1分，共10分）B2.C3.B4.D5.B6.B7.A8.C9.D10.A二、填空題（每空1分，共20分）同一存儲(chǔ)單元類(lèi)型特征12.動(dòng)態(tài)優(yōu)先級(jí)先來(lái)先服務(wù)微程序機(jī)器語(yǔ)言單指令流多數(shù)據(jù)流多指令流多數(shù)據(jù)流空間代價(jià)關(guān)聯(lián)轉(zhuǎn)移條件轉(zhuǎn)移17.水平型微碼超標(biāo)量處理線(xiàn)路包數(shù)據(jù)驅(qū)動(dòng)需求驅(qū)動(dòng)控制器軟硬三、改錯(cuò)題（每小題2分，共10分）（C錯(cuò)改為“不是唯一的”）(C錯(cuò)改為“不允許順序串行和交換串行”)(B錯(cuò)改為“差距不大”)(A錯(cuò)改為“相鄰”)(A錯(cuò)改為“硬件”)四、簡(jiǎn)答題(每小題6分，共30分)(1)簡(jiǎn)化了指令系統(tǒng)和程序設(shè)計(jì)；簡(jiǎn)化了編譯程序；(3)便于實(shí)現(xiàn)一致性校驗(yàn)；能由硬件自動(dòng)變換數(shù)據(jù)類(lèi)型；支持?jǐn)?shù)據(jù)庫(kù)系統(tǒng)的實(shí)現(xiàn)與數(shù)據(jù)類(lèi)型無(wú)關(guān)的要求；為軟件調(diào)試和應(yīng)用軟件開(kāi)發(fā)提供了支持。(1)按RISC一般原則設(shè)計(jì)；(2)邏輯實(shí)現(xiàn)用硬聯(lián)和微程序結(jié)合；(3)用重疊寄存器窗口(4)指令用流水和延遲轉(zhuǎn)移；(5)優(yōu)化設(shè)計(jì)編譯系統(tǒng)。(1)若P.的左部變量在P.的右部變量集內(nèi)，且與必須取出［運(yùn)算的結(jié)果來(lái)作為操作數(shù)，則稱(chēng)P.“數(shù)據(jù)相關(guān)”于P.O1若P.的左部變量在P.的右部變量集內(nèi)，且當(dāng)P.未取用其變量的值之前，是不允許被P.所改變，則稱(chēng)P.“數(shù)據(jù)反相關(guān)”于PjO若P.的左部變量也是P.的右部變量，且P.存入其算得的值必須在P.存入之后，則稱(chēng)P.“數(shù)據(jù)輸出相關(guān)”于P.O控制驅(qū)動(dòng)的控制流方式的特點(diǎn)是：通過(guò)訪(fǎng)問(wèn)共享存儲(chǔ)單元讓數(shù)據(jù)在指令之間傳遞；指令的執(zhí)行順序隱含于控制流中，可以顯式地使用專(zhuān)門(mén)的控制操作符來(lái)實(shí)現(xiàn)并行處理，指令執(zhí)行順序受程度計(jì)數(shù)器的控制，即受控制令牌所支配。模擬與仿真的主要區(qū)別在于解釋用的語(yǔ)言。仿真是用微程序解釋?zhuān)浣忉尦绦虼嬖诳刂拼鎯?chǔ)器中，而模擬是用機(jī)器語(yǔ)言程序解釋?zhuān)浣忉尦绦虼嬖谥鞔嬷?。模擬靈活，可實(shí)現(xiàn)不同系統(tǒng)間的軟件移植，但結(jié)構(gòu)差異太大時(shí)，效率、速度會(huì)急劇下降。仿真在速度上損失小，但不靈活，只能在差別不大的系統(tǒng)之間使用，否則效率也會(huì)過(guò)低且難以仿真，需與模擬結(jié)合才行。五、應(yīng)用題(共30分)31.表操作碼的Huffman碼及擴(kuò)展操作碼的編碼指令頻度（Pi）操作碼使用Huffman編碼OP長(zhǎng)度（Li）利用Huffman概念的擴(kuò)展操作碼OP長(zhǎng)度（Li）I——10.3501002I——20.25102012I——30.201103102I40.1011100511004I50.0411101511014I0.0311110511104I10.031111151111432.多級(jí)混洗交換網(wǎng)絡(luò)由n級(jí)相同的網(wǎng)絡(luò)組成，每一級(jí)都包含一個(gè)全混拓?fù)浜碗S后一列2n-1個(gè)四功能交換單元，采用單元控制方式。多級(jí)混洗交換網(wǎng)絡(luò)與間接二進(jìn)制n方體網(wǎng)絡(luò)只有兩點(diǎn)差別：前者數(shù)據(jù)流向的級(jí)號(hào)順序n-1,n-2,???，1，0，用四功能交換單元，后者數(shù)據(jù)流向相反，其級(jí)號(hào)順序0，1,…,n-1,用二功能交換單元。33.實(shí)際吞吐率為=33.實(shí)際吞吐率為=7——=18.7%15At15x2.5因順序方式所需時(shí)間為4x3At+3x4At=24At，因此加速比S=24At/15At=1.6P(30分)解釋下列術(shù)語(yǔ)馮■諾依曼結(jié)構(gòu)：馮■諾依曼等人于1946年提出了一個(gè)完整的現(xiàn)代計(jì)算機(jī)雛型，它由運(yùn)算器、控制器、存儲(chǔ)器和輸入輸出設(shè)備組成，這種結(jié)構(gòu)稱(chēng)為馮■諾依曼結(jié)構(gòu)。數(shù)據(jù)表示：數(shù)據(jù)表示研究的是計(jì)算機(jī)硬件能夠直接識(shí)別，可以被指令系統(tǒng)直接調(diào)用的那些數(shù)據(jù)類(lèi)型。數(shù)據(jù)表示是數(shù)據(jù)類(lèi)型中最常用，也是相對(duì)比較簡(jiǎn)單，用硬件實(shí)現(xiàn)相對(duì)比較容易的幾種。如定點(diǎn)數(shù)(整數(shù))、邏輯數(shù)(布爾數(shù))、浮點(diǎn)數(shù)(實(shí)數(shù))、十進(jìn)制數(shù)、字符、字符串、堆棧和向量等。CISC:復(fù)雜指令系統(tǒng)計(jì)算機(jī)存儲(chǔ)系統(tǒng)：兩個(gè)或兩個(gè)以上速度、容量和價(jià)格各不相同的存儲(chǔ)器用硬件、軟件、或軟件與硬件相結(jié)合的方法連接起來(lái)成為一個(gè)系統(tǒng)，這就是存儲(chǔ)系統(tǒng)。時(shí)空?qǐng)D：描述流水線(xiàn)的工作，最常用的方法是采用'時(shí)空?qǐng)D〃。在時(shí)空?qǐng)D中，橫坐標(biāo)表示時(shí)間，也就是輸入到流水線(xiàn)中的各個(gè)任務(wù)在流水線(xiàn)中所經(jīng)過(guò)的時(shí)間。當(dāng)流水線(xiàn)中的各個(gè)功能部件的執(zhí)行時(shí)間都相等時(shí)，橫坐標(biāo)被分割成相等長(zhǎng)度的時(shí)間段?？v坐標(biāo)表示空間，即流水線(xiàn)的各個(gè)子過(guò)程。在時(shí)空?qǐng)D中，流水線(xiàn)的一個(gè)子過(guò)程通常稱(chēng)為、'功能段〃。多功能流水線(xiàn)：多功能流水線(xiàn)(MultifunctionPipelining)是指流水線(xiàn)的各段可以進(jìn)行不同的連接。在不同時(shí)間內(nèi)，或在同一時(shí)間內(nèi)，通過(guò)不同的連接方式實(shí)現(xiàn)不同的功能。加速比：完成一批任務(wù)，不使用流水線(xiàn)所用的時(shí)間與使用流水線(xiàn)所用的時(shí)間之比稱(chēng)為流水線(xiàn)的加速比(Speedupratio)。鏈接技術(shù)：鏈接是當(dāng)從一個(gè)流水線(xiàn)部件得到的結(jié)果直接送入另一個(gè)功能流水線(xiàn)的操作數(shù)寄存器時(shí)所發(fā)生的連接過(guò)程。換句話(huà)說(shuō)，中間結(jié)果不必送回存儲(chǔ)器，而且甚至在向量操作完成以前就使用。鏈接允許當(dāng)?shù)谝粋€(gè)結(jié)果一變成可用的操作數(shù)時(shí)就馬上發(fā)出相繼的操作。存儲(chǔ)轉(zhuǎn)發(fā)尋徑：存儲(chǔ)轉(zhuǎn)發(fā)尋徑(storeandforward)在存儲(chǔ)轉(zhuǎn)發(fā)網(wǎng)絡(luò)中包是信息流的基本單位。每個(gè)結(jié)點(diǎn)有一個(gè)包緩沖區(qū)。包從源結(jié)點(diǎn)經(jīng)過(guò)一系列中間結(jié)點(diǎn)到達(dá)目的結(jié)點(diǎn)。蟲(chóng)蝕尋徑(wormhole):新型的多計(jì)算機(jī)系統(tǒng)很多采用的是蟲(chóng)蝕尋徑方式，把包進(jìn)一步分成更小的片。與結(jié)點(diǎn)相連的硬件尋徑器中有片緩沖區(qū)。消息從源結(jié)點(diǎn)傳送到目的結(jié)點(diǎn)要經(jīng)過(guò)一系列尋徑器。(20分，每空一分)填空衡量流水線(xiàn)性能通常有三種主要指標(biāo)，它們是吞吐率、加速比和效率。按照Flynn分類(lèi)法，根據(jù)指令流和數(shù)據(jù)流的不同組織方式，