計(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條指令的操作碼最短平均長(zhǎng)度。(2)采用Huffman編碼法編寫這10條指令的操作碼，并計(jì)算操作碼的平均長(zhǎng)度，計(jì)算與最優(yōu)Huffman編碼法（信息熵）相比的操作碼信息冗余量。將得到的操作碼編碼和計(jì)算的結(jié)果填入上面的表中。(3)采用2/8擴(kuò)展編碼法編寫這10條指令的操作碼，并計(jì)算操作碼的平均長(zhǎng)度，計(jì)算與最優(yōu)Huffman編碼法相比的操作碼信息冗余量。把得到的操作碼編碼和計(jì)算的結(jié)果填入上面的表中。(4)采用3/7擴(kuò)展編碼法編寫這10條指令的操作碼，并計(jì)算操作碼的平均長(zhǎng)度，計(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.20100101改進(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í)行過(guò)程中，有哪幾種數(shù)據(jù)相關(guān)會(huì)引起流水線停頓?⑶畫出指令執(zhí)行過(guò)程的流水線時(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無(wú)沖突；

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

k,k+2之間在R0上發(fā)生WAR無(wú)沖突。（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，向量長(zhǎng)度均為8，向量各元素均為浮點(diǎn)數(shù)；處理部件采用兩個(gè)單功能流水線，加法功能部件時(shí)間為2拍，乘法功能部件時(shí)間為3拍。采用鏈接技術(shù)，先計(jì)算(A＋B)×C。在流水線不停流的情況下，接著計(jì)算(D＋E)×F。求此鏈接流水線的流過(guò)時(shí)間為多少拍?(設(shè)寄存器入、出各需1拍)假如每拍時(shí)間為50ns，完成這些計(jì)算并把結(jié)果存進(jìn)相應(yīng)寄存器，此處理部件的實(shí)際吞吐率為多少M(fèi)FLOPS?[解答]（1）(A＋B)與×C鏈接，流水線流過(guò)時(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。總共進(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)過(guò)一步可到達(dá)：1,4,12,15；經(jīng)過(guò)二步可到達(dá)：2，5，13，8，3，11，14；經(jīng)過(guò)三步可到達(dá)：6，7，9，10。8.畫出用2×4交叉開關(guān)組成一個(gè)2級(jí)的4×16交叉開關(guān)網(wǎng)絡(luò)，其設(shè)備量比單級(jí)4×16的交叉開關(guān)節(jié)省多少設(shè)備？并說(shuō)明它是一個(gè)阻塞型