計算機體系結(jié)構(gòu)期末輔導201303課件

計算機體系結(jié)構(gòu)期末輔導主講：何志杰1

1.期末考試題題型一、填空題（每空1分，共14分）

二、名詞解釋（每題2分，共16分）三、簡答題（每題5分，共30分）

四、問答與計算題(第1題10分,第2、3題每題15分共40分)2.期末考試內(nèi)容分布第1章基礎(chǔ)知識第2章指令系統(tǒng)第3章存儲系統(tǒng)設計第4章流水線計算機設計技術(shù)第5章并行處理技術(shù)（互連網(wǎng)絡部分）第8章非馮.諾依曼計算機有關(guān)概念計算機體系結(jié)構(gòu)期末輔導2按照弗林（Flynn）分類法，計算機系統(tǒng)可以分為4類：SISD計算機、（SIMD計算機）、（MISD計算機）和（MIMD計算機）。早期馮?諾依曼計算機的主要特點是（程序存儲）、（指令驅(qū)動）、（集中控制）。目前向量處理機的系統(tǒng)結(jié)構(gòu)有兩種：（存儲器－存儲器型和寄存器－寄存器型）。通用計算機基本指令分為5類，它們分別是：（數(shù)據(jù)傳送類，運算類，程序控制類，輸入輸出類，處理機控制和調(diào)試類）。傳統(tǒng)的馮?諾依曼計算機是以控制驅(qū)動方式工作，以數(shù)據(jù)驅(qū)動方式工作的典型計算機是（數(shù)據(jù)流計算機），以需求驅(qū)動方式工作的典型計算機是（歸約機），以模式匹配驅(qū)動方式工作的典型計算機是（人工智能計算機）。3、填空題（舉例）34、名詞解釋(舉例)計算機體系結(jié)構(gòu)透明性系列機兼容機模擬仿真程序的局部性原理MIPS基準測試程序高速緩沖存儲器虛擬存儲器快表程序定位延遲轉(zhuǎn)移技術(shù)窗口重疊技術(shù)流水線技術(shù)先行控制技術(shù)動態(tài)流水線靜態(tài)流水線線性流水線非線性流水線流水線的吞吐率超標量計算機向量的分段開采技術(shù)41、簡述馮.諾依曼計算機的特征。2、什么是存儲系統(tǒng)？3、簡述組相聯(lián)映象規(guī)則。4、引起Cache與主存內(nèi)容不一致的原因是什么？為了保持Cache的一致性，在單計算機系統(tǒng)中一般采取哪些措施？5、影響虛擬存儲器命中率的因素有哪些？它們是如何影響的？6、在指令編碼中，縮短地址碼的方法很多，請列出三種縮短地址碼的方法，并說明理由。7、什么是指令的重疊解釋方式？重疊解釋方式有哪三種？8、試述頁式管理虛擬存儲器的工作過程。5、簡答題（舉例）56、典型例題分析與解答[例1]如有一個經(jīng)解釋實現(xiàn)的計算機，可以按功能劃分成4級。每一級為了執(zhí)行一條指令需要下一級的N條指令解釋。若執(zhí)行第一級的一條指令需K(ns)時間，那么執(zhí)行第2、3、4級的一條指令各需要用多少時間(ns)?解：∵第二級的一條指令需第1級的N條指令解釋∴第二級的一條指令執(zhí)行時間為NKns；第三級的一條指令執(zhí)行時間為N2Kns；第四級的一條指令執(zhí)行時間為N3Kns。6本題有兩個問題應特別注意：第一個問題是“上一級”與“下一級”的關(guān)系，即哪是上一級，哪是下一級？在下圖中第3級是第2級的“上一級”，第1級又是第2級的“下一級”。第二個問題是該計算機是一個“經(jīng)解釋實現(xiàn)的計算機”，上一級的程序在下一級上實現(xiàn)不是經(jīng)翻譯完成，只能是解釋。第1級N3條指令解釋第2級N2條指令解釋第3級N條指令解釋

第4級一條指令上級下級7[例2]假設將某系統(tǒng)的某一部件的處理速度加快到10倍，但該部件的原處理時間僅為整個運行時間的40%，則采用加快措施后能使整個系統(tǒng)的性能提高多少？解：由題意可知fe=0.4,re=10,根據(jù)Amdahl定律8[例3]用一臺4OMHz處理機執(zhí)行標準測試程序，它含的混合指令數(shù)和相應所需的時鐘周期數(shù)如下：指令類型指令條數(shù)時鐘周期數(shù)整數(shù)運算450001數(shù)據(jù)傳送320002浮點運算

150002控制傳送

80002求有效CPI、MIPS速率和程序的執(zhí)行時間。9解：依題意可知IN=105條，n=410[例4]若某機要求有：三地址指令4條，單地址指令192條，零地址指令16條。設指令字長為12位，每個地址碼長3位。問能否以擴展操作碼為其編碼？11解：

三種指令格式字如下：OPCA1A2A3

OPCA1

OPC000xxxxxxxxx

?011xxxxxxxxx000000xxx

?

?111101xxx111111110000

?111111111111三地址4條一地址192條零地址16條3333三地址指令4條單地址指令192條零地址指令16條12[例5]假設一臺模型計算機共有10種不同的操作碼，如果采用固定長操作碼需要4位。已知各種操作碼在程序中出現(xiàn)的概率如下表所示，計算采用Huffman編碼法的操作碼平均長度，并計算固定長操作碼和Huffman操作碼的信息冗余量（假設最短平均長度H＝3.1位）指令序號指令使用頻度Pi指令序號指令使用頻度PiI10.17I60.09I20.15I70.08I30.15I80.07I40.13I90.03I50.12I100.0113答：構(gòu)造Huffman樹如下：

14Huffman編碼如下表：

指令號指令使用頻度PiHuffman編碼碼長指令號指令使用頻度PiHuffman碼碼長I10.17102I60.0901104I20.150003I70.0801114I30.150013I80.0711104I40.130103I90.03111105I50.121103I100.0111111515Huffman編碼的平均碼長為：冗余量＝（3.15－3.10）/3.15＝1.59%固定碼長：log210＝4冗余量＝（4－3.10）/4＝22.5%16[例6]設某用戶虛存共有8頁,主存有4頁,每頁大小為1KB.試根據(jù)頁表計算出虛地址1023和6800的主存實地址。提示：注意頁表中虛、實頁對應關(guān)系頁表虛頁號實頁號裝入位03111122033042151060170017每頁首地址=頁號X每頁大小第0頁0—1023第1頁1024—2047第2頁2048—3071第3頁3072—4095第4頁4096—5119第5頁5120—6143第6頁6144—7167第7頁7168--8191解：頁號與地址對應關(guān)系虛地址1023，虛頁號為0，頁內(nèi)位移為1023；根據(jù)虛頁號查頁表得知實頁號為3，且裝入位為1。主存實地址PA=3072+1023=4095虛地址6800，虛頁號為6，頁內(nèi)位移為656；根據(jù)虛頁號查頁表得知實頁號為0，且裝入位為1。主存實地址PA=0+656=656虛頁號＝虛地址％102418[例7]某機主存容量為512KB，Cache的容量為32KB，每塊的大小為16個字（或字節(jié)）。劃出全相聯(lián)方式主、緩存的地址格式、目錄表格式及其容量。

答：全相聯(lián)映象方式：

主存與緩存分成相同大小的數(shù)據(jù)塊，主存的某一數(shù)據(jù)塊可以裝入緩存的任意一塊空間中。根據(jù)已知條件可以求得：主存塊數(shù)：512K/16＝32K＝215；緩存塊數(shù)：32K/16＝2K＝211；塊內(nèi)地址：16＝2419

容量：與緩沖塊數(shù)量相同即211＝2048(或32K/16＝2048)。主存塊號Bi塊內(nèi)地址18430主存地址緩存塊號Bi塊內(nèi)地址14430緩存地址主存塊地址緩存塊地址有效位26121110目錄表20圖2.6全相聯(lián)地址轉(zhuǎn)換

21[例8]某機主存容量為512KB，Cache的容量為32KB，每塊的大小為16個字（或字節(jié)）。劃出直接相聯(lián)方式主、緩存的地址格式、目錄表格式及其容量。

答：直接相聯(lián)映象方式：主存與緩存分成相同大小的數(shù)據(jù)塊，將主存空間按緩存的容量分成區(qū)，主存中某區(qū)的一塊存入緩存時只能存入緩存中塊號相同的位置。根據(jù)已知條件可以求得：主存區(qū)數(shù)：512K/32K＝16＝24；緩存塊數(shù)：32K/16＝2K＝211；塊內(nèi)地址：16＝24

22容量：與緩沖塊數(shù)量相同即211＝2048(或32K/16＝2048)。主存區(qū)號有效位410目錄表緩存塊號塊內(nèi)地址14430緩存地址區(qū)號區(qū)內(nèi)塊號塊內(nèi)地址181514430主存地址23高速緩沖存儲器圖2.8直接相聯(lián)地址轉(zhuǎn)換24[例9]主存容量為512KB，Cache的容量為32KB，每塊為64個字（或字節(jié)），緩存共分128組。劃出組相聯(lián)方式主、緩存的地址格式、目錄表格式及其容量。答：組相聯(lián)映象方式：主存與緩存分成相同大小的數(shù)據(jù)塊，主存和Cache按同樣大小劃分成組，將主存空間按緩存的容量分成區(qū)，當主存的數(shù)據(jù)調(diào)入緩存時，主存與緩存的組號應相等，但組內(nèi)各塊地址之間則可以任意存放。根據(jù)已知條件可以求得：

主存區(qū)數(shù)：512K/32K＝16＝24；緩存組數(shù)：128＝27；緩存塊數(shù)：32K/64＝512＝29；組內(nèi)塊數(shù)：512/128＝4＝22塊內(nèi)地址：64＝2625容量：29＝512(或32K/64＝512)。區(qū)號塊號緩存塊號有效位8543210目錄表組號緩存塊號塊內(nèi)地址1487650緩存地址區(qū)號組號塊號塊內(nèi)地存地址26高速緩沖存儲器圖2.10組相聯(lián)映象地址轉(zhuǎn)換27[例10]一個有快表和慢表的頁式虛擬存儲器，最多有64個用戶，每個用戶最多要用1024個頁面，每頁4K字節(jié)，主存容量8M字節(jié)。（1）寫出多用戶虛地址的格式，并標出各字段的長度。（2）寫出主存地址的格式，并標出各字段的長度。（3）快表的字長為多少位？分幾個字段？各字段的長度為多少位？（4）慢表的容量是多少個存儲字？每個存儲字的長度為多少位？28答：用戶號：64＝26，虛頁號：1024＝210，頁內(nèi)地址：4K＝212，主存頁數(shù)：8M/4K＝211（1）多用戶虛地址：用戶號（6位）＋虛頁號（10位）＋頁內(nèi)地址（12位）共28位（2）主存地址：主存實頁號（11位）＋頁內(nèi)地址（12位）共23位（3）快表字長27位；分3個字段：用戶號6位，虛頁號10位，實頁號11位（4）慢表容量為2(6+10)，每個存儲字長為：主存頁號＋1＝12位。29[例11]為在頁式虛擬存儲器中，一個程序由P1～P5共5個頁面組成。在程序執(zhí)行過程中依次訪問的頁面如下：P2，P3，P2，P1，P5，P2，P4，P5，P3，P2，P5，P2假設系統(tǒng)分配給這個程序的主存有3個頁面，分別采用FIFO、LFU和OPT三種頁面替換算法對這3頁主存進行調(diào)度。(1)畫出主存頁面調(diào)入、替換和命中的情況表。(2)統(tǒng)計三種頁面替換算法的頁命中率。解：三種替換算法的替換過程：30頁地址流232152453252

FIFO命中3次223232*3153*1521*5*245*2432*432*4354*3*52調(diào)進調(diào)進命中調(diào)進替換替換替換命中替換命中替換替換LRU命中5次22323123*512*251*425*542*354*235*523*253*調(diào)進調(diào)進命中調(diào)進替換命中替換命中替換替換命中命中OPT命中6次22323231*23*52*354*354*354*3523*5235235調(diào)進調(diào)進命中調(diào)進替換命中替換命中命中替換命中命中31[例12]用一條4段浮點加法器流水線求8個浮點數(shù)的和:Z＝A＋B＋C＋D＋E＋F＋G＋H,求流水線的吞吐率、加速比和效率,其中△t1=△t2=△t3=△t4=△t。解：由于存在數(shù)據(jù)相關(guān)，A+B的運算結(jié)果要在第5時鐘周期才能繼續(xù)做加C運算，這樣，每個功能部件都要空閑3個時鐘周期，為此，可對原式作一簡單變化，得到：Z＝[（A＋B）＋（C＋D）]＋[（E＋F）＋（G＋H）]327個加法8個數(shù)的流水線時空圖如下：33從流水線的時空圖中可以很清楚地看到，7個浮點加法共用了15個時鐘周期。流水線的吞吐率為：

流水線的加速比為：

流水線的效率為：

34[例13]設有兩個向量A，B，各有4個元素，若在如圖5-2-16a所示的靜態(tài)雙功能流水線上，計算向量點積：

其中，1→2→3→5組成加法流水線，1→4→5

組成乘法流水線。35又設每個流水線所經(jīng)過的時間均為△t，而且流水線的輸出結(jié)果可以直接返回到輸入或暫存于相應的緩沖寄存器中，其延遲時間和功能切換所需的時間都可以忽略不計。請使用合理的算法，能使完成向量點積A*B所用的時間最短，并求出流水線在此期間實際的吞吐率TP和效率E。

解：首先，應選擇適合于靜態(tài)流水線工作的算法。對于本題，應先連續(xù)計算al*bl、a2*b2、a3*b3和a4*b4共4次乘法，然后功能切換，按((albl+a2b2)+(a3b3+a4b4))經(jīng)3次加法來求得最后的結(jié)果。按此算法可畫出流水線工作時的時空圖。如圖5-2-16b所示。3637

由圖可見，總共在15個△t的時間內(nèi)流出7個結(jié)果，所以在這段時間里，流水線的實際吞吐率TP為7/15△t。

若不用流水線，由于一次求積需3△t,一次加法需

4△t,產(chǎn)生上述結(jié)果就需要43△t+34△t=24△t。因此,加速比為S=24△t/(15△t)=1.6。

該流水線的效率可用陰影區(qū)面積和全部5個段的總時空圖面積之比求得，即38[例14]什么是方體置換？寫出方體置換函數(shù)的表達式，假設互聯(lián)網(wǎng)有16個結(jié)點，請畫出4個方體置換函數(shù)（即C0，C1，C2，C3）的輸入端與輸出端的連接關(guān)系。

答：方體置換是實現(xiàn)二進制地址編號中第k位位值不同的輸入端輸出端之間的連接。其表達式為：

3900000001001000110100010101100111000000010010001101000101011001111000100110101011110011011110111110001001101010111100110111101111C0立方置換函數(shù)：40C1立方置換函數(shù)：00010010001101000101011001110001001000110100010101100111100110101011110011011110111110011010101111001101111011110000