計(jì)算機(jī)體系結(jié)構(gòu)期末輔導(dǎo)201303課件

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

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

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

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

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

150002控制傳送

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

三種指令格式字如下：OPCA1A2A3

OPCA1

OPC000xxxxxxxxx

?011xxxxxxxxx000000xxx

?

?111101xxx111111110000

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

14Huffman編碼如下表：

指令號(hào)指令使用頻度PiHuffman編碼碼長指令號(hào)指令使用頻度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]設(shè)某用戶虛存共有8頁,主存有4頁,每頁大小為1KB.試根據(jù)頁表計(jì)算出虛地址1023和6800的主存實(shí)地址。提示：注意頁表中虛、實(shí)頁對(duì)應(yīng)關(guān)系頁表虛頁號(hào)實(shí)頁號(hào)裝入位03111122033042151060170017每頁首地址=頁號(hào)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解：頁號(hào)與地址對(duì)應(yīng)關(guān)系虛地址1023，虛頁號(hào)為0，頁內(nèi)位移為1023；根據(jù)虛頁號(hào)查頁表得知實(shí)頁號(hào)為3，且裝入位為1。主存實(shí)地址PA=3072+1023=4095虛地址6800，虛頁號(hào)為6，頁內(nèi)位移為656；根據(jù)虛頁號(hào)查頁表得知實(shí)頁號(hào)為0，且裝入位為1。主存實(shí)地址PA=0+656=656虛頁號(hào)＝虛地址％102418[例7]某機(jī)主存容量為512KB，Cache的容量為32KB，每塊的大小為16個(gè)字（或字節(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)。主存塊號(hào)Bi塊內(nèi)地址18430主存地址緩存塊號(hào)Bi塊內(nèi)地址14430緩存地址主存塊地址緩存塊地址有效位26121110目錄表20圖2.6全相聯(lián)地址轉(zhuǎn)換

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

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

22容量：與緩沖塊數(shù)量相同即211＝2048(或32K/16＝2048)。主存區(qū)號(hào)有效位410目錄表緩存塊號(hào)塊內(nèi)地址14430緩存地址區(qū)號(hào)區(qū)內(nèi)塊號(hào)塊內(nèi)地址181514430主存地址23高速緩沖存儲(chǔ)器圖2.8直接相聯(lián)地址轉(zhuǎn)換24[例9]主存容量為512KB，Cache的容量為32KB，每塊為64個(gè)字（或字節(jié)），緩存共分128組。劃出組相聯(lián)方式主、緩存的地址格式、目錄表格式及其容量。答：組相聯(lián)映象方式：主存與緩存分成相同大小的數(shù)據(jù)塊，主存和Cache按同樣大小劃分成組，將主存空間按緩存的容量分成區(qū)，當(dāng)主存的數(shù)據(jù)調(diào)入緩存時(shí)，主存與緩存的組號(hào)應(yīng)相等，但組內(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ū)號(hào)塊號(hào)緩存塊號(hào)有效位8543210目錄表組號(hào)緩存塊號(hào)塊內(nèi)地址1487650緩存地址區(qū)號(hào)組號(hào)塊號(hào)塊內(nèi)地存地址26高速緩沖存儲(chǔ)器圖2.10組相聯(lián)映象地址轉(zhuǎn)換27[例10]一個(gè)有快表和慢表的頁式虛擬存儲(chǔ)器，最多有64個(gè)用戶，每個(gè)用戶最多要用1024個(gè)頁面，每頁4K字節(jié)，主存容量8M字節(jié)。（1）寫出多用戶虛地址的格式，并標(biāo)出各字段的長度。（2）寫出主存地址的格式，并標(biāo)出各字段的長度。（3）快表的字長為多少位？分幾個(gè)字段？各字段的長度為多少位？（4）慢表的容量是多少個(gè)存儲(chǔ)字？每個(gè)存儲(chǔ)字的長度為多少位？28答：用戶號(hào)：64＝26，虛頁號(hào)：1024＝210，頁內(nèi)地址：4K＝212，主存頁數(shù)：8M/4K＝211（1）多用戶虛地址：用戶號(hào)（6位）＋虛頁號(hào)（10位）＋頁內(nèi)地址（12位）共28位（2）主存地址：主存實(shí)頁號(hào)（11位）＋頁內(nèi)地址（12位）共23位（3）快表字長27位；分3個(gè)字段：用戶號(hào)6位，虛頁號(hào)10位，實(shí)頁號(hào)11位（4）慢表容量為2(6+10)，每個(gè)存儲(chǔ)字長為：主存頁號(hào)＋1＝12位。29[例11]為在頁式虛擬存儲(chǔ)器中，一個(gè)程序由P1～P5共5個(gè)頁面組成。在程序執(zhí)行過程中依次訪問的頁面如下：P2，P3，P2，P1，P5，P2，P4，P5，P3，P2，P5，P2假設(shè)系統(tǒng)分配給這個(gè)程序的主存有3個(gè)頁面，分別采用FIFO、LFU和OPT三種頁面替換算法對(duì)這3頁主存進(jìn)行調(diào)度。(1)畫出主存頁面調(diào)入、替換和命中的情況表。(2)統(tǒng)計(jì)三種頁面替換算法的頁命中率。解：三種替換算法的替換過程：30頁地址流232152453252

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

流水線的加速比為：

流水線的效率為：

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

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

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

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

由圖可見，總共在15個(gè)△t的時(shí)間內(nèi)流出7個(gè)結(jié)果，所以在這段時(shí)間里，流水線的實(shí)際吞吐率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個(gè)段的總時(shí)空?qǐng)D面積之比求得，即38[例14]什么是方體置換？寫出方體置換函數(shù)的表達(dá)式，假設(shè)互聯(lián)網(wǎng)有16個(gè)結(jié)點(diǎn)，請(qǐng)畫出4個(gè)方體置換函數(shù)（即C0，C1，C2，C3）的輸入端與輸出端的連接關(guān)系。

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

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