武汉大学计算机学院2023级系统结构试卷

《计算机系统结构》期末考试试卷（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数据传输的总时间，并画简图来示意传送过程。(设TS=9.8us,TD=0.2us,K=512B)四、（15分）有一四段线性流水线，每功能段延时时间分别是：△t1=△t3=△t4=△t，△t2=3△t。现在这个流水线上分别执行4个任务（要求画出时空图）和40个任务，求实际吞吐率、效率和加速比。五、（15分）对于采用级控制的三级立方体网络，当第2级为直连状态时，PE5不能实现与哪些结点之间的通信？当第2级为交换状态时，又不能实现与哪些结点之间的通信？六、（10分）对于算术表达式Z=A1+A2+…+A8，分析其数据相关性，并用FORK、JOIN语句，编写可在多处理机上并行执行的程序。七、（10分）对于一非线性流水线，其4行6列的预约表如下：功能段123456S1√√S2√√√S3√√S4√求出该流水线的最佳调度方案。《计算机系统结构》期末考试试卷（B）（闭卷）一、填空题：（每小题4分、共20分）1、CISC的含义是，RISC的含义是。2．程序访问的局部性包含两方面的含义，其中时间局部性是指________________________，空间局部性是指______________________。3．流水线中经过时间最长的子过程（子部件）称为流水线中的______________。4．Flynn分类将计算机系统分为四类，这四类是指单指令流单数据流、、和。5．二元交换开关的四种状态是________、________、________、________。应用题（共5题，共80分）二．（15分）设一模型机有7条指令，它们的使用频度如下表所示。请设计出指令的Huffman编码和只有两种码长的扩展操作码编码，求其平均码长和信息冗余量。（已知H=1.95）指令I1I2I3I4I5I6I7使用频度0.450.300.150.050.030.010.01三．（15分）为提高流水线的效率可采用哪两种主要技术途径来克服速度瓶颈？现有3段流水线，各段经过时间依次为Δt、3Δt、Δt。（1）分别计算在连续输入3条指令时和30条指令时的吞吐率和效率；（2）按两种途径之一改进，画出你的流水线结构示意图。四．（15分）在一个5功能段非线性流水线处理机上需经9△t才能完成一个任务，预约表如下：时间t123456789K=1∨∨K=2∨∨∨K=3∨K=4∨∨K=5∨∨求出流水线的最优调度方案及最小平均延迟时间和流水线的最大吞吐率。五．（15分）画出N=8（0---7）个处理单元的间接二进制n方体多级互连网络图。并指当K2K1K0=100时，输入端的第5号处理单元与输出端的哪一个处理单元相连？六、（20分）在CRAY-1型向量处理机上，V为向量寄存器，长度为32；S为标量寄存器。所用浮点功能部件的执行时间分别为：加法需6拍，乘法需7拍，从存储器读数需6拍，打入寄存器需1拍，启动功能部件（包括存储器）需1拍。问下列各指令组中的哪些指令可以链接？哪些可以并行执行？说明原因并分别计算各指令组全部完成所需的拍数。（1）V0←存储器，V1←V2+V3，V4←V5×V6；（2）V3←存储器，V2←V0×V1，V4←V2+V3；《计算机系统结构》期末考试试卷（A）参考答案一、词语辩析：（每小题5分、共20分）1．系列机与兼容机答：系列机：是指同一厂商生产的系统结构同、组成和实现不同的不同档次的机器；兼容机：是指不同厂商生产的系统结构相同、组成和实现不同的不同档次的机器。2．模拟与仿真答：模拟：用一台机器的指令系统去解释另一台系统结构不同的机器的指令系统，以实现软件的移植；仿真：直接用微程序去解释另一台机器的指令系统，以实现软件的移植。模拟灵活性好，速度慢；仿真速度快，灵活性差。3．RAW与WAR答：RAW是指读与写相关；WAR是指写与读相关。它们都是流水线中的寄存器中的数据相关，对流水线性有影响。4．CISC与RISC答：CISC是指复杂指令系统结构的计算机；RISC是指精简指令系统结构的计算机。它们代表着计算机指令系统的两种设计风格。二、应用题：（共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分）解：执行4个任务时：TP=4/15Δt，E=40%，SP=1.6（7分）执行40个任务时：TP=40/123Δt，E=48.8%，SP=1.95（8分）4、（15分）解：当第2级为直连时，PE5不能与输出2、3、6、7结点相连；（7分）当第2级为交换时，PE5不能与输出0、1、4、5结点相连。（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分）解：状态图如下：（5分）最佳调度方案为（1，5）或（3），平均延时为3。（5分）《计算机系统结构》期末考试试卷（B）参考答案一、填空题：（每小题4分、共20分）1、复杂指系统计算机、精简指令系统计算机2．两个事件在同一时刻发生、两个事件在同一时间间隔内发生3．瓶颈4．单指令流单数据流、单指令流多数据流、多指令流单数据流、多指令流多数据流5．直通、交叉、上播和下播应用题（共5题，共80分）二．（15分）（已知H=1.95）解：由各条指令的使用频度构造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）连续输入3条指令时，吞吐率和效率分别为当连续输入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）状态图如图所示。（3）平均延迟最小的调度方案（3，4）。最大吞吐率为五．（15分）解：网络图如图所示。输入5号与输出1号相连。spanstyle=";z-index:1