計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)綜合題

計(jì)算機(jī)系統(tǒng)結(jié)構(gòu)綜合題1.一個(gè)處理機(jī)共有10條指令，各指令在程序中出現(xiàn)的概率如下表：(1)采用最優(yōu)Huffman編碼法（信息熵）計(jì)算這10條指令的操作碼最短平均長度。(2)采用Huffman編碼法編寫這10條指令的操作碼，并計(jì)算操作碼的平均長度，計(jì)算與最優(yōu)Huffman編碼法（信息熵）相比的操作碼信息冗余量。將得到的操作碼編碼和計(jì)算的結(jié)果填入上面的表中。(3)采用2/8擴(kuò)展編碼法編寫這10條指令的操作碼，并計(jì)算操作碼的平均長度，計(jì)算與最優(yōu)Huffman編碼法相比的操作碼信息冗余量。把得到的操作碼編碼和計(jì)算的結(jié)果填入上面的表中。(4)采用3/7擴(kuò)展編碼法編寫這10條指令的操作碼，并計(jì)算操作碼的平均長度，計(jì)算與最優(yōu)Huffman編碼法相比的操作碼信息冗余量。把得到的操作碼編碼和計(jì)算的結(jié)果填入上面的表中。[解答]0.020.030.020.030.040.050.080.080.10.150.200.250.050.090.130.170.230.320.430.571.0001000000011111111指令序號(hào)出現(xiàn)的概率Huffman編碼法2/8擴(kuò)展編碼法3/7擴(kuò)展編碼法I10.25000000I20.20100101I3040.10110100111000I50.080110101011001I60.081110101111010I70.051111110011011I80.0401110110111100I90.03011110111011101I100.02011111111111110操作碼的平均長度2.993.13.2操作碼的信息冗余量1.1%4.6%7.6%2.一個(gè)虛擬存儲(chǔ)器按字節(jié)編址，最多有128個(gè)用戶，每個(gè)用戶最多要用2048頁，每頁512字節(jié)。主存容量8M字節(jié)，快表按地址訪問，共16個(gè)存儲(chǔ)字，快表地址碼經(jīng)散列變換得到，為減少散列沖突，快表分為兩組，有兩套獨(dú)立的相等比較電路。試：寫出多用戶虛地址和主存地址的格式，并給出各字段的長度。散列變換部件的輸入、輸出位數(shù)各為多少？每個(gè)相等比較電路的位數(shù)是多少？快表每個(gè)存儲(chǔ)字的總長度為多少位？為哪幾個(gè)字段？各字段的長度為多少位？[解答]虛地址的長度為27位，格式如下：主存的地址需要23位：格式如下由于用戶號(hào)和虛頁號(hào)共有18位，所以，散列變換的輸入需要18位，而輸出的為快表的地址，如果我們假設(shè)快表是按照字尋址，那么是3位（快表分為兩組，每組8個(gè)存儲(chǔ)字）?；?位（16個(gè)存儲(chǔ)字，每字兩個(gè)入口）。相等比較電路需要比較多用戶虛頁號(hào)，以消除散列沖突，所以，相等比較電路需要18位?？毂碇行枰鎯?chǔ)兩項(xiàng)內(nèi)容：多用戶虛頁號(hào)和實(shí)頁號(hào)。多用戶虛頁號(hào)為18位，實(shí)頁號(hào)為14位，共有32位。3.用一條5個(gè)功能段的浮點(diǎn)加法器流水線計(jì)算。每個(gè)功能段的延遲時(shí)間均相等，流水線的輸出端和輸入端之間有直接數(shù)據(jù)通路，而且設(shè)置有足夠的緩沖寄存器。要求用盡可能短的時(shí)間完成計(jì)算，要求：列出進(jìn)行加法的次序；畫出流水線時(shí)空?qǐng)D；并計(jì)算流水線在此任務(wù)中的實(shí)際吞吐率、加速比和效率。 [解答]（1）首先需要考慮的是，8個(gè)數(shù)的的和最少需要做幾次加法。我們可以發(fā)現(xiàn)，加法的次數(shù)是不能減少的：7次；于是我們要盡可能快的完成任務(wù)，就只有考慮如何讓流水線盡可能充滿，這需要消除前后指令之間的相關(guān)。由于加法滿足交換率和結(jié)合率，我們可以調(diào)整運(yùn)算次序如以下的指令序列，我們把中間結(jié)果寄存器稱為R，源操作數(shù)寄存器稱為A，最后結(jié)果寄存器稱為F，并假設(shè)源操作數(shù)已經(jīng)在寄存器中，則指令如下：I1： R1←A1+A2I2： R2←A3+A4I3： R3←A5+A6I4： R4←A7+A8I5： R5←R1+R2I6： R6←R3+R4I7： R7←R5+R6（2）這并不是唯一可能的計(jì)算方法。假設(shè)功能段的延遲為Δt。時(shí)空?qǐng)D如下，圖中的數(shù)字是指令號(hào)： （3）整個(gè)計(jì)算過程需要18Δt，所以吞吐率為：加速比為：效率為：=0.394.一條3個(gè)功能段的非線性流水線及其預(yù)約表如下：SS1S2S3輸入輸出△t△t△t時(shí)間流水段12345S1××S2××S3××⑴寫出流水線的禁止向量和初始沖突向量，并畫出調(diào)度流水線的狀態(tài)圖。⑵求流水線的最小啟動(dòng)循環(huán)和最小平均啟動(dòng)距離。⑶通過插入非計(jì)算延遲功能段使該流水線達(dá)到最優(yōu)調(diào)度，確定該流水線的最佳啟動(dòng)循環(huán)及其最小平均啟動(dòng)距離。⑷畫出插入非計(jì)算延遲功能段后的流水線連接圖及其預(yù)約表。⑸畫出插入非計(jì)算延遲功能段后的流水線狀態(tài)圖。⑹在插入非計(jì)算延遲功能段前、后，分別計(jì)算流水線的最大吞吐率，并計(jì)算最大吞吐率改進(jìn)的百分比。[解答]改進(jìn)的百分比：5.在一臺(tái)單流水線多操作部件的處理機(jī)上執(zhí)行下面的程序，取指令、指令譯碼各需要一個(gè)時(shí)鐘周期，MOVE、ADD和MUL操作各需要2個(gè)、3個(gè)和4個(gè)時(shí)鐘周期。每個(gè)操作都在第一個(gè)時(shí)鐘周期從通用寄存器中讀操作數(shù)，在最后一個(gè)時(shí)鐘周期把運(yùn)算結(jié)果寫到通用寄存器中。k： MOVER1，R0 ；(R1)←(R0)k十1： MULR0，R2，R1 ；(R0)←(R2)×(R1)k十2： ADDR0，R2，R3 ；(R0)←(R2)十(R3)⑴就程序本身而言，可能有哪幾種數(shù)據(jù)相關(guān)?⑵在程序?qū)嶋H執(zhí)行過程中，有哪幾種數(shù)據(jù)相關(guān)會(huì)引起流水線停頓?⑶畫出指令執(zhí)行過程的流水線時(shí)空?qǐng)D，并計(jì)算執(zhí)行完這三條指令共使用了多少個(gè)時(shí)鐘周期。[解答]（1）k,k+1之間在R1上發(fā)生RAW，在R0上發(fā)生WAR；

k+1,k+2之間在R2上發(fā)生RAR，在R0上發(fā)生WAW；

k,k+2之間在R0上發(fā)生WAR（2）k,k+1之間在R1上發(fā)生RAW有沖突，在R0上發(fā)生WAR無沖突；

k+1,k+2之間在R2上發(fā)生RAR無沖突，在R0上發(fā)生WAW有沖突；

k,k+2之間在R0上發(fā)生WAR無沖突。（3）寫R1寫R0寫R0取R0取R1R2取R2，R3t1t2t3t4t5t6t7t8 流水線中使用了7個(gè)周期。加上取指令、指令譯碼各需要的一個(gè)時(shí)鐘周期，共使用了9個(gè)時(shí)鐘周期。6.某機(jī)有16個(gè)向量寄存器，其中V0→V5中分別存放有向量A、B、C、D、E、F，向量長度均為8，向量各元素均為浮點(diǎn)數(shù)；處理部件采用兩個(gè)單功能流水線，加法功能部件時(shí)間為2拍，乘法功能部件時(shí)間為3拍。采用鏈接技術(shù)，先計(jì)算(A＋B)×C。在流水線不停流的情況下，接著計(jì)算(D＋E)×F。求此鏈接流水線的流過時(shí)間為多少拍?(設(shè)寄存器入、出各需1拍)假如每拍時(shí)間為50ns，完成這些計(jì)算并把結(jié)果存進(jìn)相應(yīng)寄存器，此處理部件的實(shí)際吞吐率為多少M(fèi)FLOPS?[解答]（1）(A＋B)與×C鏈接，流水線流過時(shí)間：（1+2+1+1+3+1）=9拍；(D＋E)可以在（A+B）完成時(shí)進(jìn)入加法流水線，和×C并行工作，×F可以和（D+E）鏈接，但是必需在×C完成之后才能進(jìn)入乘法流水線。（D+E）得到第一個(gè)結(jié)果是在：（1+2+1）+（8-1）+（1+2+1）=15拍時(shí)；×C完成是在：（1+2+1+1+3+1）+（8-1）=16拍時(shí)。因此是在17拍時(shí)開始計(jì)算×F，第一個(gè)結(jié)果出現(xiàn)的時(shí)間是：16+（1+3+1）=21拍。（2）計(jì)算全部完成所化的時(shí)間是：21+（8-1）=28拍*50ns/拍=1400ns?？偣策M(jìn)行的浮點(diǎn)運(yùn)算是16次加法和16次乘法，實(shí)際吞吐率為：32/1400ns=32/1.4MFLOPS=22.85MFLOPS。7.畫出16臺(tái)處理器仿I11iacIV的模式進(jìn)行互連的互連結(jié)構(gòu)圖，列出PE0分別只經(jīng)一步、二步和三步傳送就能將信息傳送到的各處理器號(hào)。[解答]答：見下圖，其中0表示PE0，1表示PE1…PE0經(jīng)過一步可到達(dá)：1,4,12,15；經(jīng)過二步可到達(dá)：2，5，13，8，3，11，14；經(jīng)過三步可到達(dá)：6，