1、1計算機體系結構期末輔導計算機體系結構期末輔導主講：何志杰主講：何志杰2 1. 期末考試題題型期末考試題題型一、填空題（每空一、填空題（每空1分，共分，共14分）分） 二、名詞解釋（每題二、名詞解釋（每題2分，共分，共16分）分） 三、簡答題（每題三、簡答題（每題5分，共分，共30分）分） 四、問答與計算題四、問答與計算題(第第1題題10分分,第第2、3題每題題每題15分共分共40分分)2. 期末考試內容分布期末考試內容分布第第1章章 基礎知識基礎知識第第2章章 指令系統指令系統第第3章章 存儲系統設計存儲系統設計第第4章章 流水線計算機設計技術流水線計算機設計技術第第5章章 并行處理技術（互

2、連網絡部分）并行處理技術（互連網絡部分）第第8章章 非馮非馮.諾依曼計算機有關概念諾依曼計算機有關概念計算機體系結構期末輔導計算機體系結構期末輔導31. 按照弗林（Flynn）分類法，計算機系統可以分為4類：SISD計算機、（SIMDSIMD計算機）、（計算機）、（MISDMISD計算機）和（計算機）和（MIMDMIMD計算機）。計算機）。2. 早期馮諾依曼計算機的主要特點是（程序存儲）、（指令驅動）、程序存儲）、（指令驅動）、（集中控制）。（集中控制）。3. 目前向量處理機的系統結構有兩種：（存儲器存儲器型和寄存器寄存儲器存儲器型和寄存器寄存器型）。存器型）。4. 通用計算機基本指令分為5類

3、，它們分別是：（數據傳送類，運算類，數據傳送類，運算類，程序控制類，輸入輸出類，處理機控制和調試類）。程序控制類，輸入輸出類，處理機控制和調試類）。5. 傳統的馮諾依曼計算機是以控制驅動方式工作，以數據驅動方式工作的典型計算機是（數據流計算機），（數據流計算機），以需求驅動方式工作的典型計算機是（歸約機），（歸約機），以模式匹配驅動方式工作的典型計算機是（人工智能計算（人工智能計算機）。機）。3、填空題（舉例）、填空題（舉例）44、名詞解釋、名詞解釋(舉例舉例)計算機體系結構計算機體系結構 透明性透明性 系列機系列機 兼容機兼容機 模擬模擬 仿真仿真程序的局部性原理程序的局部性原理 MIPS

4、基準測試程序基準測試程序 高速緩沖存儲器高速緩沖存儲器 虛擬存儲器虛擬存儲器 快表快表程序定位程序定位 延遲轉移技術延遲轉移技術 窗口重疊技術窗口重疊技術流水線技術流水線技術 先行控制技術先行控制技術 動態流水線動態流水線靜態流水線靜態流水線 線性流水線線性流水線 非線性流水線非線性流水線 流水線的吞吐率流水線的吞吐率 超標量計算機超標量計算機向量的分段開采技術向量的分段開采技術 51、簡述馮、簡述馮.諾依曼計算機的特征諾依曼計算機的特征 。2、什么是存儲系統？、什么是存儲系統？3、簡述組相聯映象規則。、簡述組相聯映象規則。4、引起、引起Cache與主存內容不一致的原因是什么？為了保持與主存內

5、容不一致的原因是什么？為了保持Cache的一致的一致性，在單計算機系統中一般采取哪些措施？性，在單計算機系統中一般采取哪些措施？5、影響虛擬存儲器命中率的因素有哪些？它們是如何影響的？、影響虛擬存儲器命中率的因素有哪些？它們是如何影響的？6、在指令編碼中，縮短地址碼的方法很多，請列出三種縮短地址碼的、在指令編碼中，縮短地址碼的方法很多，請列出三種縮短地址碼的方法，并說明理由。方法，并說明理由。7、什么是指令的重疊解釋方式？重疊解釋方式有哪三種？、什么是指令的重疊解釋方式？重疊解釋方式有哪三種？8、試述頁式管理虛擬存儲器的工作過程、試述頁式管理虛擬存儲器的工作過程 。5、簡答題（舉例）、簡答題（

6、舉例）66、典型例題分析與解答、典型例題分析與解答例例1如有一個經解釋實現的計算機，可以按功能劃分成4級。每一級為了執行一條指令需要下一級的N條指令解釋。若執行第一級的一條指令需K(ns)時間，那么執行第2、3、4級的一條指令各需要用多少時間(ns)?解：解：第二級的一條指令需第第二級的一條指令需第1級的級的N條指令解釋條指令解釋 第二級的一條指令執行時間為第二級的一條指令執行時間為NKns； 第三級的一條指令執行時間為第三級的一條指令執行時間為N2Kns； 第四級的一條指令執行時間為第四級的一條指令執行時間為N3Kns。7本題有兩個問題應特別注意：第一個問題是“上一級”與“下一級”的關系，即

7、哪是上一級，哪是下一級？在下圖中第3級是第2級的“上一級”，第1級又是第2級的“下一級”。第二個問題是該計算機是一個“經解釋實現的計算機”，上一級的程序在下一級上實現不是經翻譯完成，只能是解釋。 第第1級級 N3條指令解釋條指令解釋第第2級級 N2條指令解釋條指令解釋第第3級級 N條指令解釋條指令解釋 第第4級級 一條指令一條指令上級上級下級下級8例例2假設將某系統的某一部件的處理速度加快到10倍，但該部件的原處理時間僅為整個運行時間的40%，則采用加快措施后能使整個系統的性能提高多少？解：由題意可知解：由題意可知 fe=0.4, re=10, 根據根據Amdahl定律定律111.56(1 0

8、.4)0.4/100.64ePoTST9例例3用一臺4OMHz處理機執行標準測試程序，它含的混合指令數和相應所需的時鐘周期數如下：指令類型 指令條數指令條數 時鐘周期數整數運算 45000 1 1數據傳送 32000 2浮點運算 15000 2控制傳送 8000 2求有效CPI、MIPS速率和程序的執行時間。10解：依題意可知解：依題意可知 I IN N=10=105 5條，條，n=4n=4141()(1 0.4520.3220.1520.08)1.55niiiNiICPICPII666401025.8101.5510CfMIPSCPI56101.551 / 40103.875()CPUNCT

9、ICPITms11例例4若某機要求有：三地址指令4條，單地址指令192條，零地址指令16條。設指令字長為12位，每個地址碼長3位。問能否以擴展操作碼為其編碼？12解：解： 三種指令格式字如下：三種指令格式字如下：OPC A1 A2 A3 OPC A1 OPC 000 xxx xxx xxx 011 xxx xxx xxx100 000 000 xxx 111 111 101 xxx111 111 110 000 111 111 111 111三地址4條一地址192條零地址16條3333三地址指令4條單地址指令192條零地址指令16條13例例5假設一臺模型計算機共有10種不同的操作碼，如果采用固

10、定長操作碼需要4位。已知各種操作碼在程序中出現的概率如下表所示，計算采用Huffman編碼法的操作碼平均長度，并計算固定長操作碼和Huffman操作碼的信息冗余量（假設最短平均長度H3.1位） 指令序號指令使用頻度Pi指令序號指令使用頻度PiI10.17I60.09I20.15I70.08I30.15I80.07I40.13I90.03I50.12I100.0114答：構造答：構造Huffman樹如下：樹如下： 1.000.400.230.110.040.010.030.070.120.170.080.090.130.150.150.600.300.300.171111111110000000

11、0015Huffman編碼如下表： 指令號指令使用頻度PiHuffman編碼碼長指令號指令使用頻度PiHuffman碼碼長I10.17102I60.0901104I20.150003I70.0801114I30.150013I80.0711104I40.130103I90.03111105I50.121103I100.0111111516Huffman編碼的平均碼長為：冗余量（3.153.10）/3.151.59%固定碼長：log2104冗余量（43.10）/422.5%15. 35)01. 003. 0(4)07. 008. 009. 0(3)12. 013. 015. 015. 0(217

12、. 0101iiilP17 例例66設某用戶虛存共有8頁, 主存有4頁, 每頁大小為1KB. 試根據頁表計算出虛地址1023和6800的主存實地址。提示：注意頁表中虛、 實頁對應關系頁表虛頁號虛頁號 實頁號實頁號 裝入位裝入位 0 3 1 1 1 1 2 2 0 3 3 0 4 2 1 5 1 0 6 0 1 7 0 018每頁首地址=頁號X每頁大小第第0 0頁頁0102301023第第1 1頁頁1024204710242047第第2 2頁頁2048307120483071第第3 3頁頁3072409530724095第第4 4頁頁4096511940965119第第5 5頁頁51206143

13、51206143第第6 6頁頁6144716761447167第第7 7頁頁7168-81917168-8191解：頁號與地址對應關系解：頁號與地址對應關系虛地址虛地址1023，虛頁號為，虛頁號為0，頁內位移，頁內位移為為1023；根據虛頁號查頁表得知實；根據虛頁號查頁表得知實頁號為頁號為3，且裝入位為，且裝入位為1。主存實地址主存實地址PA=3072+1023=4095虛地址虛地址6800，虛頁號為，虛頁號為6，頁內位移，頁內位移為為656；根據虛頁號查頁表得知實頁；根據虛頁號查頁表得知實頁號為號為0，且裝入位為，且裝入位為1。主存實地址主存實地址PA=0+656=656虛頁號虛地址虛頁號虛

14、地址102419例例7某機主存容量為512KB，Cache的容量為32KB，每塊的大小為16個字（或字節）。劃出全相聯方式主、緩存的地址格式、目錄表格式及其容量。 答：全相聯映象方式：答：全相聯映象方式： 主存與緩存分成相同大小的數據塊，主存的某主存與緩存分成相同大小的數據塊，主存的某 一數據塊可以裝入緩存的任意一塊空間中。一數據塊可以裝入緩存的任意一塊空間中。 根據已知條件可以求得：根據已知條件可以求得： 主存塊數：主存塊數：512K/1632K215； 緩存塊數：緩存塊數：32K/162K211； 塊內地址：塊內地址：162420 容量：與緩沖塊數量相同即2112048(或32K/1620

15、48)。 主存塊號Bi 塊內地址18 4 3 0主存地址緩存塊號Bi 塊內地址14 4 3 0緩存地址主存塊地址 緩存塊地址 有效位26 12 11 1 0目錄表21圖圖2.6 全相聯地址轉換全相聯地址轉換 22例例8某機主存容量為512KB，Cache的容量為32KB，每塊的大小為16個字（或字節）。劃出直接相聯方式主、緩存的地址格式、目錄表格式及其容量。 答：直接相聯映象方式：答：直接相聯映象方式： 主存與緩存分成相同大小的數據塊，將主存空間按緩主存與緩存分成相同大小的數據塊，將主存空間按緩存的容量分成區，主存中某區的一塊存入緩存時只能存存的容量分成區，主存中某區的一塊存入緩存時只能存入緩

16、存中塊號相同的位置。入緩存中塊號相同的位置。 根據已知條件可以求得：根據已知條件可以求得： 主存區數：主存區數：512K/32K1624；緩存塊數：；緩存塊數：32K/162K211；塊內地址：；塊內地址：1624 23容量：與緩沖塊數量相同即2112048(或32K/162048)。 主存區號 有效位4 1 0目錄表 緩存塊號 塊內地址14 4 3 0緩存地址區號 區內塊號 塊內地址18 15 14 4 3 0主存地址24高速緩沖存儲器高速緩沖存儲器主主 存存 地地址址區區 號號 E塊塊 號號 B塊塊 內內 地地 址址WCache 地地 址址塊塊 號號 b塊塊 內內 地地 址址 w 塊塊 失

17、失 效效相相 等等 比比 較較比比 較較 相相 等等 且且 有有 效效 為為 1 E1訪訪 問問 Cache區區 號號 E（ 按按 地地 址址 訪訪 問問 ）有有 效效 位位區區 表表 存存 儲儲 器器圖圖2.8 直接相聯地址轉換直接相聯地址轉換25例例9主存容量為512KB，Cache的容量為32KB，每塊為64個字（或字節），緩存共分128組。劃出組相聯方式主、緩存的地址格式、目錄表格式及其容量。 答：組相聯映象方式：答：組相聯映象方式： 主存與緩存分成相同大小的數據塊，主存和主存與緩存分成相同大小的數據塊，主存和Cache按同按同樣大小劃分成組，將主存空間按緩存的容量分成區，樣大小劃分成

18、組，將主存空間按緩存的容量分成區，當主存的數據調入緩存時，主存與緩存的組號應相等當主存的數據調入緩存時，主存與緩存的組號應相等，但組內各塊地址之間則可以任意存放。，但組內各塊地址之間則可以任意存放。 根據已知條件可以求得：根據已知條件可以求得： 主存區數：主存區數：512K/32K1624；緩存組數：；緩存組數：12827； 緩存塊數：緩存塊數：32K/6451229；組內塊數：；組內塊數：512/128422 塊內地址：塊內地址：642626容量：29512(或32K/64512)。 區號 塊號 緩存塊號 有效位8 5 4 3 2 1 0 目錄表 組號 緩存塊號 塊內地址14 8 7 6 5

19、 0 緩存地址區號 組號 塊號 塊內地址18 15 14 8 7 6 5 0主存地址27高速緩沖存儲器高速緩沖存儲器圖圖2.10 組相聯映象地址轉換組相聯映象地址轉換區區 號號 E組組 號號 G組組 內內 塊塊 號號 B塊塊 內內 地地 址址 W 主主 存存 地地 址址組組 號號 g組組 內內 塊塊 號號 b塊塊 內內 地地 址址 wC ache 地地 址址 不不 等等相相 聯聯 比比 較較 相相 等等相相 聯聯 比比 較較 (Gb個個 塊塊 )區區 號號 E ,組組 內內 塊塊 號號 B組組 內內 塊塊 號號 b塊塊 表表28例例10一個有快表和慢表的頁式虛擬存儲器，最多有64個用戶，每個用

20、戶最多要用1024個頁面，每頁4K字節，主存容量8M字節。（1）寫出多用戶虛地址的格式，并標出各字段的長度。（2）寫出主存地址的格式，并標出各字段的長度。（3）快表的字長為多少位？分幾個字段？各字段的長度為多少位？（4）慢表的容量是多少個存儲字？每個存儲字的長度為多少位？ 29答：用戶號：答：用戶號：6426，虛頁號：，虛頁號：1024210，頁內地址：，頁內地址：4K212，主存頁數：，主存頁數：8M/4K211（1）多用戶虛地址：）多用戶虛地址： 用戶號（用戶號（6位）虛頁號（位）虛頁號（10位）頁內地址（位）頁內地址（12位）位） 共共28位位（2）主存地址：）主存地址： 主存實頁號（主

21、存實頁號（11位）頁內地址（位）頁內地址（12位）位） 共共23位位（3）快表字長）快表字長27位；分位；分3個字段：用戶號個字段：用戶號6位，虛頁號位，虛頁號10位，位，實頁號實頁號11位位（4）慢表容量為）慢表容量為2(6+10)，每個存儲字長為：，每個存儲字長為： 主存頁號主存頁號112位。位。30例例11為在頁式虛擬存儲器中，一個程序由P1P5共5個頁面組成。在程序執行過程中依次訪問的頁面如下：P2，P3，P2，P1，P5，P2，P4，P5，P3，P2，P5，P2 假設系統分配給這個程序的主存有3個頁面，分別采用FIFO、LFU和OPT三種頁面替換算法對這3頁主存進行調度。 (1) 畫

22、出主存頁面調入、替換和命中的情況表。 (2) 統計三種頁面替換算法的頁命中率。 解：解：三種替換算法的替換過程： 31頁地址流頁地址流2 23 32 21 15 52 24 45 53 32 25 52 2 FIFO FIFO命中命中3 3次次2 22 23 32 23 32 2* *3 31 15 53 3* *1 15 52 21 1* *5 5* *2 24 45 5* *2 24 43 32 2* *4 43 32 2* *4 43 35 54 4* *3 3* *5 52 2調調進進調調進進命命中中調調進進替替換換替替換換替替換換命命中中替替換換命命中中替替換換替替換換LRULRU命

23、中命中5 5次次2 22 23 32 23 31 12 23 3* *5 51 12 2* *2 25 51 1* *4 42 25 5* *5 54 42 2* *3 35 54 4* *2 23 35 5* *5 52 23 3* *2 25 53 3* *調調進進調調進進命命中中調調進進替替換換命命中中替替換換命命中中替替換換替替換換命命中中命命中中OPTOPT命中命中6 6次次2 22 23 32 23 32 23 31 1* *2 23 3* *5 52 2* *3 35 54 4* *3 35 54 4* *3 35 54 4* *3 35 52 23 3* *5 52 23 35

24、 52 23 35 5調調進進調調進進命命中中調調進進替替換換命命中中替替換換命命中中命命中中替替換換命命中中命命中中32例例12用一條4段浮點加法器流水線求8個浮點數的和: ZABCDEFGH,求流水線的吞吐率、加速比和效率,其中t1=t2=t3=t4=t。 輸輸入入 求求階階差差 對對階階 尾尾數數加加 規規格格化化 輸輸出出 t t1 t t2 t t3 t t4 解：由于存在數據相關，A+B的運算結果要在第5時鐘周期才能繼續做加C運算，這樣，每個功能部件都要空閑3個時鐘周期，為此，可對原式作一簡單變化，得到： Z（AB）（CD）（EF）（GH）337個加法8個數的流水線時空圖如下： 空

25、間空間 周期周期 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 1010 1111 1212 1313 1414 1515 規格化規格化 1 1 2 2 3 3 4 4 5 5 6 6 7 7 尾數加尾數加 1 1 2 2 3 3 4 4 5 5 6 6 7 7 對階對階 1 1 2 2 3 3 4 4 5 5 6 6 7 7 求階差求階差 1 1 2 2 3 3 4 4 5 5 6 6 7 7 時間時間 加數加數 A C E G A+B E+F A+B+C+DA C E G A+B E+F A+B+C+D 加數加數 B D F H B D F H C+D G+H E

26、+F+G+H C+D G+H E+F+G+H 結果結果 A+B A+B C+D E+F C+D E+F G G+H +H A+B+C+D E+F+G+H A+B+C+D E+F+G+H Z Z 用一條用一條 4 4 段浮點加法器流水線求段浮點加法器流水線求 8 8 個數之和的流水線時空圖個數之和的流水線時空圖 34從流水線的時空圖中可以很清楚地看到，7個浮點加法共用了15個時鐘周期。 TPnTttk 7150 471STTttk 04 7151 87ETk Tttk 04 74 150 47流水線的吞吐率為： 流水線的加速比為： 流水線的效率為： 35例例13設有兩個向量A，B，各有4個元素，

27、若在如圖5-2-16a所示的靜態雙功能流水線上，計算向量點積： 其中，1235組成加法流水線，145組成乘法流水線。41iiibaBA36又設每個流水線所經過的時間均為t，而且流水線的輸出結果可以直接返回到輸入或暫存于相應的緩沖寄存器中，其延遲時間和功能切換所需的時間都可以忽略不計。請使用合理的算法，能使完成向量點積A*B所用的時間最短，并求出流水線在此期間實際的吞吐率TP和效率E。解：首先，應選擇適合于靜態流水線工作的算法。對于本題，應先連續計算al*bl、a2*b2、a3*b3和a4*b4共4次乘法，然后功能切換，按(albl+a2b2)+(a3b3+a4b4)經3次加法來求得最后的結果。

28、按此算法可畫出流水線工作時的時空圖。如圖5-2-16b所示。3738 由圖可見，總共在15個t的時間內流出7個結果，所以在這段時間里，流水線的實際吞吐率TP為7/15t。 若不用流水線，由于一次求積需3t,一次加法需 4 t,產生上述結果就需要43t+34t=24t。因此,加速比為S=24t/(15t)=1.6。 該流水線的效率可用陰影區面積和全部5個段的總時空圖面積之比求得，即%3275241553443tttE39例例14什么是方體置換？寫出方體置換函數的表達式，假設互聯網有16個結點，請畫出4個方體置換函數（即C0，C1，C2，C3）的輸入端與輸出端的連接關系。 答：方體置換是實現二進制

29、地址編號中第答：方體置換是實現二進制地址編號中第k位位值不同的輸位位值不同的輸入端輸出端之間的連接。其表達式為：入端輸出端之間的連接。其表達式為： )()(0112101121XXXXXXXXXXXXCkkknnkkknnk4000000001001000110100010101100111000000010010001101000101011001111000100110101011110011011110111110001001101010111100110111101111C0立方置換函數：立方置換函數：)()(012301230XXXXXXXXC41C1立方置換函數：立方置換函數：)()(012301231XXXXXXXXC0001001000110100010101100111000100100011010001