2009—2010學年度第一學期2007級《計算機系統結構》期末考試試卷（A）（閉卷）姓名：學號：專業：（注：①考試時間為120分鐘；②所有解答必須寫在答題紙上。）一、單項選擇題（每小題3分,共30分)1．在系列機中發展一種新型號機器，你認為下列（)設想是不行的?【A】新增加字符數據類型和若干條字符處理指令【B】將中斷分級由原來的4級增加到5級【C】在CPU和主存之間增設Cache存貯器【D】將浮點數的下溢處理法由原來的恒置“1"法，改為查表舍入法2。對計算機系統結構來說，不透明的是（）.【A】存儲器采用交叉存取還是并行存取【B】CPU內部的數據通路的寬度是8位還是16位【C】采用浮點數據表示還是標志符數據表示【D】指令采用硬聯邏輯實現還是微程序實現3．一個平衡的計算機系統，應該是（）。【A】1MIPS的CPU速度【B】1MB的主存容量【C】1Mb/s的I/O吞吐率【D】A、B和C4、（）設計是現代計算機系統設計所采用的方法。【A】由上往下【B】由下往上【C】由中間開始【D】上下同時開始5．當今微型機中實現軟件移植最好的方法是()。【A】系列機【B】兼容機【C】仿真技術【D】統一高級語言6、不能夠對向量數據結構提供直接支持的是()數據表示。【A】向量【B】堆棧【C】描述符【D】A和C7、采用整數邊界存儲技術，其主要目的是(）.【A】節約主存空間【B】提高數據的訪問速度【C】一個主存周期可取多條指令【D】一個主存周期至少可取到一條指令8、在指令的操作碼編碼方式中，優化實用的編碼是（).【A】Huffman編碼【B】等長編碼【C】Huffman擴展編碼【D】BCD碼9、流水計算機中將指令Cache和數據Cache分開，主要是為了()。【A】提高存儲系統的速度【B】增加主存容量【C】解決功能部件沖突【D】解決訪存沖突10、當N=16時,能描述4組4元交換的函數是（).【A】C1+C2【B】C0+C1【C】C0+C2【D】C2+C3二、（10分）在采用通用寄存器指令集結構的計算機上得到了如下所示的數據：指令類型執行頻率時鐘周期數ALU指令43%1LOAD指令21％2STORE指令12%2分支指令24%2假若編譯器優化后能去掉50%的ALU指令,但不能去掉其它三類指令。求優化后的MIPS與優化前的MIPS速率比。三、（10分）設某機器系統指令字長12位，每個操作碼和地址均占3位，試提出一種分配方案，使該指令系統有4條三地址指令，8條二地址指令和180條單地址指令。四、（10分）設通道在數據傳送期中,選擇設備需4。9μS,傳送一個字節數據需0.lμS。（1）其低速設備每隔250μS發出一個字節數據傳送請求，問最多可接多少臺這種設備？（2）若有A~E共5種高速設備，要求字節傳送的間隔時間如下表所示，其時間單位為μS.若一次通信傳送的字節數不少于1024個字節，問哪些設備可掛在此通道上？哪些則不能？設備ABCDE時間間隔（μS)0.130。10.110.20。3五、（10分）有一非線線性流水線預約表如下.功能段123456S1√√S2√√√S3√√S4√（1)求平均延遲最小的最佳調度方案;（2)畫出按最佳方案之一連續輸入3個任務的時空圖。六、（10分）有一四段線性流水線,每功能段延時時間分別是：△t1=△t3=△t4=△t0，△t2=3△t0.若在這個流水線上執行40個任務。求實際吞吐率、效率和加速比。01234567輸01234567輸出端01234567輸入端AABCDK0EFGHK1IJKLK2C0C2C1C3八、（10分）在8個PE構成的雙向環互連的并行處理機中，計算點積S=(n=8)所需要的時間。設初始化時將A，B各分量已分配到各PE中,且設相鄰處理單元之間傳送一次數據需要時間△t，完成一次加法需要時間2△t，完成一次乘法需要時間4△t。（全部試題完）武漢大學計算機學院2009—2010學年度第二學期2007級《計算機系統結構》期末考試試卷(A）參考答案一、（每小題3分，共30分)[解]：1-10：BCDCABDCDB二、（10分）［解]：三、（10分)［解］：000×××××××××011×××××××××100000××××××100111××××××101000000×××64+116=180101111111×××64+116=180110000000×××111110011×××四、（10分）[解］：（1）低速設備應接字節多路通道所以，n≤50臺,即最多可接50臺（2）根據題意，此通道為選擇通道其中，n≥1024，應使|select·i≤|max·select，由此可得出通道工作周期為：T≈0.1014(us)所以，只有A、C、D、E可掛在此通道上,B則不行。五、（10分）［解]:(1)狀態圖略。最佳調度方案為(3）和(1，5）（2）輸入3個任務時空圖略。六、（10分）[解]：七、（10分）[解]：不能與輸出的2、3、6、7結點相連。八、(10分）［解]：需要8次乘法，7次加法；共14△t計算機系統結構姓名：學號:一、名詞解釋(每題3分,共15分）1。Cache2：1經驗規則 3.同構型多處理機5.堆棧型機器2。計算機體系結構4。通道處理機PAGEPAGE17二、填空(每空1分,共20分)設計I/O系統的三個標準是（）、(）和（).存儲器層次結構設計技術的基本依據是程序的（).相聯度越高,（）失效就越少;（）失效不受Cache容量的影響，但（）失效卻隨著容量的增加而減少。在虛擬存儲器中，一般采用(）地址映象方法和（）更新策略。計算機系統中提高并行性的技術途徑有（）、（）和（）三種。在高性能單處理機的發展中,起主導作用的是(）.在處理機中，若指令序列完成的順序總是與它們開始執行的順序保持一致，則只可能出現（）相關,否則就有可能出現（）、（）和（）相關。對向量的處理有（)方式、(）方式、（)方式。三、簡答題（每題6分，共24分）任寫出三種Cache的優化技術，并簡述其基本思想.在指令集結構設計中,應該考慮哪些主要問題？數據相關有哪幾種類型？解決數據相關有哪些主要方法？試以系列機為例，說明計算機體系結構、計算機組成和計算機實現三者之間的關系。四、計算題1。給定以下的假設,試計算直接映象Cache和兩路組相聯Cache的平均訪問時間以及CPU的性能。由計算結果能得出什么結論?理想Cache情況下的CPI為2。0，時鐘周期為2ns，平均每條指令訪存1.4次。兩者Cache容量均為128KB,塊大小都是32字節。組相聯Cache中的多路選擇器使CPU的時鐘周期增加了10%。這兩種Cache的失效開銷都是80ns。命中時間為1個時鐘周期。128KB直接映象Cache的失效率為1。0％，128KB兩路組相聯Cache的失效率為0.7%。（15分)2。計算機系統字長64位，包含三個選擇通道和一個多路通道，每個選擇通道上連接了兩臺磁盤機和三臺磁帶機，多路通道上連接了了兩臺行式打印機，兩臺讀卡機、10臺終端，假定各設備的傳輸率如下：磁盤機：600KBps，磁帶機：200KBps，行打機:6.6KBps，讀卡機：1。2KBps，終端：1KBps。計算該計算機系統的最大I/O數據傳輸率。(6分）3。某計算機系統采用浮點運算部件后使浮點運算速度提高到原來的20倍,而系統運行一程序的整體性能提高到原來的10倍，試計算該程序中浮點操作所占的比例。(5分)4。動態多功能流水線由6個功能段組成，如下圖所示：其中,s1、s4、s5、s6組成乘法流水線，s1、s2、s3、s6組成加法流水線，各個功能段時間為：s1、s3、s4、s6為△t，s2、s5為2△t，假設該流水線的輸出結果可以直接返回輸入端，而且設置有足夠地緩沖寄存器,若以最快的方式用該流水計算:∏（Ai＋Bi)（其中i＝1。.4，∏為連乘符號)(1）畫出其處理過程的時空圖.（2）計算其實際的吞吐率和效率.（15分)2003～2004學年度第2學期《計算機系統結構》試題A答案填空題:（）由軟件實現的機器稱為虛擬機器;由硬件和微程序（固件）實現的機器稱為實際機器。軟件和硬件在邏輯上是等效的.由于軟、硬件緊密相關,軟硬界面常常是模糊不清的。計算機組成設計主要是圍繞：1.提高速度，2.提高操作的并行度、重疊流水,3.分散功能，4.設置專用功能部件來進行。具有相同“系統結構”（如指令系統相同）的計算機可以因為速度要求等因素的不同而采用不同的組成。一種“計算機組成”可以采用多種不同的“計算機實現”。“計算機組成"反過來也會影響“系統結構”。計算機系統結構設計的主要任務是：進行軟、硬件的功能分配。計算機系統設計，從多級層次結構出發，可以分為：由上往下、由下往上和從中間開始三種不同的設計思路。10．計算機應用可以歸納為向上升級的四類它們分別是：數據處理（DataProcessing）.信息處理(InformationProcessing）。知識處理（KnowledgeProcessing）.智能處理(IntelligenceProcessing）.簡答題：1．計算機實現（ComputerImplementation）？:是指計算機組成的物理實現，包括:處理機、主存等部件的物理結構，器件的集成度和速度,器件、模塊、插件、底板的劃分與連接，專用器件的設計,微組裝技術，信號傳輸，電源、冷卻及整機裝配技術等.2．計算機組成（ComputerOrganization)?：是指計算機系統結構的邏輯實現,包括:機器級內的數據流和控制流的組成以及邏輯設計等。3．軟件的可移植性？是指軟件不用修改或只需經少量加工就能由一臺機器搬到另一臺機器上運行，即同一軟件可以不同的系統環境.4．向上（下）兼容？：是指按某檔機器編制的軟件,不加修改就能運行于比它高（低)檔的機器上。5．向前（后）兼容？:指的是，在按某個時期投入市場的該型號機器上編制的軟件，不加修改就能運行在它之前（后)投入市場的機器上.6．兼容機(CompatibleMachine）？：具有同一系統結構的計算機稱為～。采用兼容機的思想與采用系列機的思想實際上是一致的.7．模擬（Simulation)：用機器語言程序解釋實現軟件移植的方法稱為~。8．仿真（Emulation）：用微程序直接解釋另一種機器指令系統的方法稱為～。9．現場片：使用戶可根據需要改變器件內部的功能或內容，以適應結構和組成變化的需要。10．全用戶片：完全按用戶要求設計的用戶片稱為全用戶片。簡述題：算機系統結構研究的是什么?答：軟、硬件之間的功能分配以及對傳統機器級界面的確定.計算機組成設計要解決的問題是什么？答:在所希望能達到的性能和價格比的前提下，怎樣最佳、最合理地把各種設備和部件組織成為一臺計算機,以實現所確定的系統結構。3．器件的發展對系統結構的影響？（1）器件的發展改變了邏輯設計的傳統方法。（2）器件的發展也使系統結構的“下移”速度加快.（3）器件的發展還促進了算法、語言和軟件的發展.4。什么是并行性?只要在同一時刻或是在同一時間間隔內完成兩種或兩種以上性質相同或不同的工作，它們在時間上能相互重疊，都體現了并行性.5。CISC指令系統的含義?復雜指令系統計算機，即機器指令系統變得越來越龐雜,這就是所謂的CISC指令系統.6。什么是頁式存貯管理？頁式存貯管理是把主存空間和程序空間都機械地等分成固定大小的頁，按頁順序編號.（頁面大小隨機器而異,一般在512到幾KB）。7.什么是向量流水處理機？向量流水處理機是將向量數據表示和流水線技術結合在一起，構成向量流水處理機,簡稱向量流水處理機.8.什么是相聯處理機？相聯處理機是以相聯存貯器為核心，配上必要的中央處理部件、指令存貯器、控制器和I/O接口,就構成一臺以存貯器操作并行為特點的相聯處理機.計算題：設一臺模型機有7條指令，其使用頻度為：____________________________________________________指令使用頻度|指令使用頻度I10。03｜I40。05I20.03｜I50。15I30.04｜I60。3|I70。4_____________________________________________________求出：（1）利用哈夫曼(Huffman）壓縮技術，構造哈夫曼樹;（2）.操作碼平均碼長和擴展碼長。要求：哈夫曼樹節點為1.0（1)1.010.60.610.30.310.150.15100000.090.060.090.0610100.030.040.050.150.30.40.030.030.040.050.150.30.40.03（2）H=2.17H=2。22。如果設一個系統有四個中斷級，個級中斷響應次序為1-〉2-〉3—〉4。見中斷級屏蔽位表中斷處理程序級別中斷級屏蔽位1級2級3級4級第1級第2級第3級第4級0111001100010000求當把中斷次序改為1—>4->3-〉2時，畫出中斷級屏蔽位表.中斷處理程序級別中斷級屏蔽位1級2級3級4級第1級第2級第3級第4級01110000010001103.計算流水線實際吞吐率TP和效率η.設有兩個向量C和D,各有4個元素，在圖中的靜態雙功能流水線上工作。其中,1-〉2—〉3->5組成加法流水線，1—>4—>5組成乘法流水線。設每個流水線所經過的時間均為Δt，而且流水線的輸出結果可以直接返回到輸入或暫存于相應的緩沖寄存器中,其延遲時間和功能切換所需要的時間都可以忽略不計。求：該流水線的實際吞吐率TP和效率η.空間54321012345678910111213141516時間Δt實際吞吐率TP=7/（15Δt)η=32%4。計算多級立方體互連網絡。見圖N=8多級立方體互連網絡，求當輸入端級控制信號為S2S1S0=010時，輸入端為01234567時，輸出端為：23016745。輸入輸出5。由表達式：E=a+bx+cx2+dx3,利用減少樹高的辦法來加速運算，要求（1)畫出樹形流程圖；（2)確定TP、P、SP、EP諸值++*+*+d**+**+*acx*****bxxxxxp=3,TP=4,SP=3/2,EP=1/2計算機系統結構試題第一部分選擇題一、單項選擇題(每小題1分,共10分)在每小題的四個備答案中有一個正確的答案，將正確答案的序號寫在題干后的括號內)1。計算機使用的語言是(）A.專屬軟件范疇，與計算機體系結構無關B.分屬于計算機系統各個層次C。屬于用以建立一個用戶的應用環境D.屬于符號化的機器指令2.動態數據流機最突出的特點是使(）A.數據流令牌無標號B。需要程序記數器來實現C。令牌帶上標號D。同步由門（Latch）寄存器來實現3。多處理機上兩個程序段之間若有先寫后讀的數據相關，則（)A。可以并行執行B。不可能并行C。任何情況均可交換串行D。必須并行執行4.多處理機的各自獨立型操作系統(）A。要求管理程序不必是可再入的B.適合于緊耦合多處理機C。工作負荷較平衡D。有較高的可靠性5。輸入輸出系統硬件的功能對（）是透明的。A.操作系統程序員B.應用程序員C。系統結構設計人員D.機器語言程序設計員6。“啟動I/O”指令是主要的輸入輸出指令，是屬于()A。目態指令B.管態指令C。目態、管態都能用的指令D。編譯程序只能用的指令7。全相聯地址映象是指（）A.任何虛頁都可裝入主存中任何實頁的位置B.一個虛頁只裝進固定的主存實頁位置C.組之間是固定的，而組內任何虛頁可以裝入任何實頁位置D。組間可任意裝入,組內是固定裝入8.（）屬于MIMD系統結構.A.各處理單元同時受同一個控制單元的管理B。各處理單元同時接受同一個控制單元送來的指令C.松耦合多處理機和多計算機D.陣列處理機9。設16個處理器編號分別為0，1，2，…，15用Cube3互聯函數時,第10號處理機與第（）號處理機相聯。A。11B.8C.14D.210.若輸入流水線的指令既無局部性相關,也不存在全局性相關，則(）A。可獲得高的吞吐率和效率B。流水線的效率和吞吐率惡化C。出現瓶頸D.可靠性提高第二部分非選擇題二、填空題（每空1分，共20分）11。標志符與每個數據相連，合存于_______，用于描述單個數據的_______。12.總線仲裁算法有：靜態優先級算法、固定時間片算法、_______算法和_______算法。13。計算機仿真用_______解釋，計算機模擬用_______解釋.14.按弗林（MichaelJ.Flynn）的觀點，計算機系統可分為單指令流單數據流、_______、多指令流單數據流和_______四大類。15。要實現兩條指令在時間上重疊解釋，首先需要付出_______，其次，要處理好指令之間可能存在的_______。16。與重疊機器一樣，流水機器在遇到_______指令，尤其是_______指令時，效率也會顯著下降。17。超長指令字(VLIW)結構是將_______和_______兩者相結合。18.互連網絡的交換方法主要有線路交換、包交換、線路/包交換，SIMD互連網絡多采用_______交換，多處理機常采用_______交換。19。數據流機采用_______,執行的操作序列取決于輸入數據的可用性；歸約機則采用_______，執行的操作序列取決于對數據的要求，對數據的需求又來源于函數式程序設計語言對表達式的歸納。20.輸入輸出系統包括輸入輸出設備、設備_______及與輸入輸出操作有關的_______件.三、改錯題（每小題2分，共10分）（下列每小題劃線部分A、B、C中有一處錯誤，請先寫出錯處，并在括號中寫出正確文字)21。對操作碼進行優化編碼時，在了解每種指令在程序中出現的概率后，使用Huffman算AB法構造Huffman樹,這樣獲得的Huffman編碼是唯一的。（）C22.多處理機中,兩個程序段之間若同時有先寫后讀和先讀后寫2種相關，以交換數據為目的時,則必須并行執行，讀寫要完全同步，允許順序串行和交換串行.()ABC23.計算機仿真適合在兩種結構差距大的機器間運用.（）ABC24.主存空間數相關是相間隔的兩條指令之間出現對主存同一單元要求先寫而后讀的關聯。ABC()25.由于Cache存貯器的地址變換和塊替換算法是用軟件實現的，因此Cache存貯器對應用A程序員是透明的，而且Cache對處理機和主存間的信息交往也是透明的。(）BC四、簡答題（每小題6分,共30分)26。簡述標志符數據表示的主要優點。27。簡述設計RISC結構用了哪些基本技術?28。設Pi和Pj程序段都是一條語句，且Pi在Pj之前執行,試舉出Pi和Pj間存在3種可能的數據相關。29.簡述控制驅動的控制流方式的特點?30。模擬與仿真的主要區別和適合場合是什么？五、應用題（共30分）31。(12分）假設某模型機共有7條指令,7條指令I1—I7使用的頻度分別為:0.35,0。25，0.20，0。10，0。04,0。03,0.03。(1）利用Huffman算法，構造Huffman樹，并給出Huffman編碼和平均碼長。（2)給出Huffman擴展碼編碼。32。(10分）多級混洗交換網絡是如何組成的？它與間接二進制n立方體網絡有何差異?并畫出N=8時的多級混洗交換網絡圖。33。（8分）設向量A和B各有4個元素在下圖所示的靜態雙功能流水線上計算向量點積A·B=，其中1→2→3→5組成加法流水線,1→4→5組成乘法流水線。若假定流水線的各段所經過的時間均為△t=2。5,流水線輸出可直接送回輸入或暫存于相應緩沖寄存器中，其延遲時間和功能切換所需的時間都可忽略.求出吞吐率和加速比.計算機系統結構試題參考答案一、單項選擇題(每小題1分，共10分）1。B2.C3。B4。D5。B6。B7.A8.C9。D10。A二、填空題（每空1分，共20分)11.同一存儲單元類型特征12。動態優先級先來先服務13。微程序機器語言14。單指令流多數據流多指令流多數據流15。空間代價關聯16.轉移條件轉移17.水平型微碼超標量處理18.線路包19.數據驅動需求驅動20。控制器軟硬三、改錯題(每小題2分，共10分)21.(C錯改為“不是唯一的”）22.(C錯改為“不允許順序串行和交換串行”)23.（B錯改為“差距不大")24。（A錯改為“相鄰”）25.（A錯改為“硬件”)四、簡答題（每小題6分，共30分）

26。(1）簡化了指令系統和程序設計；（2）簡化了編譯程序；（3）便于實現一致性校驗；（4)能由硬件自動變換數據類型；(5)支持數據庫系統的實現與數據類型無關的要求；(6)為軟件調試和應用軟件開發提供了支持。27。（1）按RISC一般原則設計；(2）邏輯實現用硬聯和微程序結合；(3)用重疊寄存器窗口（4)指令用流水和延遲轉移;(5)優化設計編譯系統。28.（1）若Pi的左部變量在Pj的右部變量集內，且Pi必須取出Pi運算的結果來作為操作數，則稱Pi“數據相關"于Pi.（2）若Pj的左部變量在Pi的右部變量集內，且當Pi未取用其變量的值之前，是不允許被Pj所改變，則稱Pi“數據反相關”于Pj.（3)若Pi的左部變量也是Pj的右部變量，且Pj存入其算得的值必須在Pi存入之后，則稱Pj“數據輸出相關"于Pi。29.控制驅動的控制流方式的特點是：通過訪問共享存儲單元讓數據在指令之間傳遞;指令的執行順序隱含于控制流中，可以顯式地使用專門的控制操作符來實現并行處理，指令執行順序受程度計數器的控制，即受控制令牌所支配.30.模擬與仿真的主要區別在于解釋用的語言。仿真是用微程序解釋，其解釋程序存在控制存儲器中，而模擬是用機器語言程序解釋，其解釋程序存在主存中。模擬靈活,可實現不同系統間的軟件移植，但結構差異太大時，效率、速度會急劇下降。仿真在速度上損失小，但不靈活，只能在差別不大的系統之間使用，否則效率也會過低且難以仿真，需與模擬結合才行.五、應用題（共30分)31.表操作碼的Huffman碼及擴展操作碼的編碼指令頻度（Pi）操作碼使用Huffman編碼OP長度(Li)利用Huffman概念的擴展操作碼OP長度（Li）I10．3501002I20．25102012I30.201103102I40。1011100511004I50.0411101511014I60。0311110511104I70.031111151111432。多級混洗交換網絡由n級相同的網絡組成，每一級都包含一個全混拓撲和隨后一列2n—1個四功能交換單元,采用單元控制方式.多級混洗交換網絡與間接二進制n方體網絡只有兩點差別：前者數據流向的級號順序n—1,n—2，…，1，0，用四功能交換單元，后者數據流向相反,其級號順序0,1，…，n—1,用二功能交換單元。33．實際吞吐率為=因順序方式所需時間為4，因此加速比SP=24=1。61。（30分）解釋下列術語

（1）馮·諾依曼結構:馮·諾依曼等人于１９４６年提出了一個完整的現代計算機雛型,它由運算器、控制器、存儲器和輸入輸出設備組成，這種結構稱為馮·諾依曼結構。

(2）數據表示:數據表示研究的是計算機硬件能夠直接識別，可以被指令系統直接調用的那些數據類型。數據表示是數據類型中最常用,也是相對比較簡單，用硬件實現相對比較容易的幾種。如定點數（整數）、邏輯數（布爾數）、浮點數（實數)、十進制數、字符、字符串、堆棧和向量等.

(3）CISC：復雜指令系統計算機

(4）存儲系統：兩個或兩個以上速度、容量和價格各不相同的存儲器用硬件、軟件、或軟件與硬件相結合的方法連接起來成為一個系統,這就是存儲系統。

(5)時空圖：描述流水線的工作，最常用的方法是采用“時空圖”。在時空圖中，橫坐標表示時間，也就是輸入到流水線中的各個任務在流水線中所經過的時間。當流水線中的各個功能部件的執行時間都相等時，橫坐標被分割成相等長度的時間段。縱坐標表示空間，即流水線的各個子過程。在時空圖中，流水線的一個子過程通常稱為“功能段”。

(6)多功能流水線:多功能流水線（MultifunctionPipelining)是指流水線的各段可以進行不同的連接.在不同時間內，或在同一時間內，通過不同的連接方式實現不同的功能.

（7)加速比：完成一批任務，不使用流水線所用的時間與使用流水線所用的時間之比稱為流水線的加速比(Speedupratio）。

(8）鏈接技術：鏈接是當從一個流水線部件得到的結果直接送入另一個功能流水線的操作數寄存器時所發生的連接過程。換句話說，中間結果不必送回存儲器,而且甚至在向量操作完成以前就使用。鏈接允許當第一個結果一變成可用的操作數時就馬上發出相繼的操作。

（9)存儲轉發尋徑：存儲轉發尋徑（storeandforward）在存儲轉發網絡中包是信息流的基本單位。每個結點有一個包緩沖區.包從源結點經過一系列中間結點到達目的結點.

（