武漢大學計算機學院2023級系統(tǒng)結(jié)構(gòu)試卷

《計算機系統(tǒng)結(jié)構(gòu)》期末考試試卷（A）（閉卷）一、詞語辯析：（每小題5分、共20分）1．系列機與兼容機2．模擬與仿真3．RAW與WAR4．CISC與RISC二、（15分）一模型機有10條指令，各指令的使用頻度分別為：0.25,0.20,0.15,0.10,0.08,0.08,0.05,0.04,0.03,0.02。（H=2.96）(1)寫出這些指令操作碼的哈夫曼編碼，并求其平均碼長和信息冗余量。(2)寫出這些指令的3/7和2/8兩種擴展編碼，并計算其平均碼長和信息冗余量。三、（15分）在三種類型的通道上各接有5臺設備。請分別寫出這三種通道上每個設備完成1024B數(shù)據(jù)傳輸?shù)目倳r間，并畫簡圖來示意傳送過程。(設TS=9.8us,TD=0.2us,K=512B)四、（15分）有一四段線性流水線，每功能段延時時間分別是：△t1=△t3=△t4=△t，△t2=3△t。現(xiàn)在這個流水線上分別執(zhí)行4個任務（要求畫出時空圖）和40個任務，求實際吞吐率、效率和加速比。五、（15分）對于采用級控制的三級立方體網(wǎng)絡，當?shù)?級為直連狀態(tài)時，PE5不能實現(xiàn)與哪些結(jié)點之間的通信？當?shù)?級為交換狀態(tài)時，又不能實現(xiàn)與哪些結(jié)點之間的通信？六、（10分）對于算術(shù)表達式Z=A1+A2+…+A8，分析其數(shù)據(jù)相關(guān)性，并用FORK、JOIN語句，編寫可在多處理機上并行執(zhí)行的程序。七、（10分）對于一非線性流水線，其4行6列的預約表如下：功能段123456S1√√S2√√√S3√√S4√求出該流水線的最佳調(diào)度方案?！队嬎銠C系統(tǒng)結(jié)構(gòu)》期末考試試卷（B）（閉卷）一、填空題：（每小題4分、共20分）1、CISC的含義是，RISC的含義是。2．程序訪問的局部性包含兩方面的含義，其中時間局部性是指________________________，空間局部性是指______________________。3．流水線中經(jīng)過時間最長的子過程（子部件）稱為流水線中的______________。4．Flynn分類將計算機系統(tǒng)分為四類，這四類是指單指令流單數(shù)據(jù)流、、和。5．二元交換開關(guān)的四種狀態(tài)是________、________、________、________。應用題（共5題，共80分）二．（15分）設一模型機有7條指令，它們的使用頻度如下表所示。請設計出指令的Huffman編碼和只有兩種碼長的擴展操作碼編碼，求其平均碼長和信息冗余量。（已知H=1.95）指令I(lǐng)1I2I3I4I5I6I7使用頻度0.450.300.150.050.030.010.01三．（15分）為提高流水線的效率可采用哪兩種主要技術(shù)途徑來克服速度瓶頸？現(xiàn)有3段流水線，各段經(jīng)過時間依次為Δt、3Δt、Δt。（1）分別計算在連續(xù)輸入3條指令時和30條指令時的吞吐率和效率；（2）按兩種途徑之一改進，畫出你的流水線結(jié)構(gòu)示意圖。四．（15分）在一個5功能段非線性流水線處理機上需經(jīng)9△t才能完成一個任務，預約表如下：時間t123456789K=1∨∨K=2∨∨∨K=3∨K=4∨∨K=5∨∨求出流水線的最優(yōu)調(diào)度方案及最小平均延遲時間和流水線的最大吞吐率。五．（15分）畫出N=8（0---7）個處理單元的間接二進制n方體多級互連網(wǎng)絡圖。并指當K2K1K0=100時，輸入端的第5號處理單元與輸出端的哪一個處理單元相連？六、（20分）在CRAY-1型向量處理機上，V為向量寄存器，長度為32；S為標量寄存器。所用浮點功能部件的執(zhí)行時間分別為：加法需6拍，乘法需7拍，從存儲器讀數(shù)需6拍，打入寄存器需1拍，啟動功能部件（包括存儲器）需1拍。問下列各指令組中的哪些指令可以鏈接？哪些可以并行執(zhí)行？說明原因并分別計算各指令組全部完成所需的拍數(shù)。（1）V0←存儲器，V1←V2+V3，V4←V5×V6；（2）V3←存儲器，V2←V0×V1，V4←V2+V3；《計算機系統(tǒng)結(jié)構(gòu)》期末考試試卷（A）參考答案一、詞語辯析：（每小題5分、共20分）1．系列機與兼容機答：系列機：是指同一廠商生產(chǎn)的系統(tǒng)結(jié)構(gòu)同、組成和實現(xiàn)不同的不同檔次的機器；兼容機：是指不同廠商生產(chǎn)的系統(tǒng)結(jié)構(gòu)相同、組成和實現(xiàn)不同的不同檔次的機器。2．模擬與仿真答：模擬：用一臺機器的指令系統(tǒng)去解釋另一臺系統(tǒng)結(jié)構(gòu)不同的機器的指令系統(tǒng)，以實現(xiàn)軟件的移植；仿真：直接用微程序去解釋另一臺機器的指令系統(tǒng)，以實現(xiàn)軟件的移植。模擬靈活性好，速度慢；仿真速度快，靈活性差。3．RAW與WAR答：RAW是指讀與寫相關(guān)；WAR是指寫與讀相關(guān)。它們都是流水線中的寄存器中的數(shù)據(jù)相關(guān)，對流水線性有影響。4．CISC與RISC答：CISC是指復雜指令系統(tǒng)結(jié)構(gòu)的計算機；RISC是指精簡指令系統(tǒng)結(jié)構(gòu)的計算機。它們代表著計算機指令系統(tǒng)的兩種設計風格。二、應用題：（共6題、共80分）1．（15分）解：（1）L哈=2.99(位)，R哈=(2.99-2.96)/2.99=1%（7分）（2）L3/7=3.2(位)，R3/7=7.5%；L2/8=3.1(位)，R2/8=4.5%（8分）2、（15分）解：（每小步5分）Tbyte=np(TS+TD)=1024×5×(9.8+0.2)=51200(us)Tblock=2×5×(9.8+512×0.2)=1122(us)Tselect=5×(9.8+1024×0.2)=1073(us)3、（15分）解：執(zhí)行4個任務時：TP=4/15Δt，E=40%，SP=1.6（7分）執(zhí)行40個任務時：TP=40/123Δt，E=48.8%，SP=1.95（8分）4、（15分）解：當?shù)?級為直連時，PE5不能與輸出2、3、6、7結(jié)點相連；（7分）當?shù)?級為交換時，PE5不能與輸出0、1、4、5結(jié)點相連。（8分）5、（10分）spanstyle=";z-index:1;left:0px;margin-left:180.0000px;margin-top:0.0000px;width:183.0000px;height:159.0000px;"解：S1:A1=A1+A2S2:A3=A3+A4S3:A5=A5+A6S4:A7=A7+A8S5:A1=A1+A3S6:A5=A5+A7S7:A1=A1+A5（5分）FORK20FORK30FORK4010A1=A1+A2JOIN4GOTO5020A3=A3+A4JOIN4GOTO5030A5=A5+A6JOIN4GOTO5040A7=A7+A8JOIN450FORK7060A1=A1+A3JOIN2GOTO8070A5=A5+A7JOIN280A1=A1+A3（5分）6、（10分）解：狀態(tài)圖如下：（5分）最佳調(diào)度方案為（1，5）或（3），平均延時為3。（5分）《計算機系統(tǒng)結(jié)構(gòu)》期末考試試卷（B）參考答案一、填空題：（每小題4分、共20分）1、復雜指系統(tǒng)計算機、精簡指令系統(tǒng)計算機2．兩個事件在同一時刻發(fā)生、兩個事件在同一時間間隔內(nèi)發(fā)生3．瓶頸4．單指令流單數(shù)據(jù)流、單指令流多數(shù)據(jù)流、多指令流單數(shù)據(jù)流、多指令流多數(shù)據(jù)流5．直通、交叉、上播和下播應用題（共5題，共80分）二．（15分）（已知H=1.95）解：由各條指令的使用頻度構(gòu)造Huffman樹圖略。由此可求出Huffman編碼和只有兩種碼長的擴展編碼以及它們的碼長如下表所示：指令使用頻度Huffman編碼碼長擴展編碼碼長I10.4511002I20.30012012I30.15O013102I40.050001411004I50.0300001511014I60.01000001611104I70.01000000611114spanstyle=";z-index:1;left:0px;margin-left:21.0000px;margin-top:17.7333px;width:484.0000px;height:56.0000px;"Huffman編碼平均碼長為：信息冗余量為：(1.97-1.95)/1.97≈1.02%spanstyle=";z-index:1;left:0px;margin-left:21.0000px;margin-top:8.3333px;width:400.0000px;height:56.0000px;"擴展編碼的平均碼長為：信息冗余量為：（2.2-1.95）/2.2≈11.36%三．（15分）解：（1）連續(xù)輸入3條指令時，吞吐率和效率分別為當連續(xù)輸入30條指令時，流水線的吞吐率和效率分別為（2）按方法一改進后的流水線示意圖如下所示：spanstyle=";z-index:1;left:0px;margin-left:46.0000px;margin-top:0.0000px;width:333.0000px;height:44.0000px;"spanstyle=";z-index:1;left:0px;margin-left:240.0000px;margin-top:2.4000px;width:289.0000px;height:219.0000px;"四．（15分）解：（1）初始沖突向量為C0=（10110001）。（2）狀態(tài)圖如圖所示。（3）平均延遲最小的調(diào)度方案（3，4）。最大吞吐率為五．（15分）解：網(wǎng)絡圖如圖所示。輸入5號與輸出1號相連。spanstyle=";z-index:1