计算机系统结构综合题

计算机系统结构综合题1.一个处理机共有10条指令，各指令在程序中出现的概率如下表：(1)采用最优Huffman编码法（信息熵）计算这10条指令的操作码最短平均长度。(2)采用Huffman编码法编写这10条指令的操作码，并计算操作码的平均长度，计算与最优Huffman编码法（信息熵）相比的操作码信息冗余量。将得到的操作码编码和计算的结果填入上面的表中。(3)采用2/8扩展编码法编写这10条指令的操作码，并计算操作码的平均长度，计算与最优Huffman编码法相比的操作码信息冗余量。把得到的操作码编码和计算的结果填入上面的表中。(4)采用3/7扩展编码法编写这10条指令的操作码，并计算操作码的平均长度，计算与最优Huffman编码法相比的操作码信息冗余量。把得到的操作码编码和计算的结果填入上面的表中。[解答]0.020.030.020.030.040.050.080.080.10.150.200.250.050.090.130.170.230.320.430.571.0001000000011111111指令序号出现的概率Huffman编码法2/8扩展编码法3/7扩展编码法I10.25000000I20.20100101I3040.10110100111000I50.080110101011001I60.081110101111010I70.051111110011011I80.0401110110111100I90.03011110111011101I100.02011111111111110操作码的平均长度2.993.13.2操作码的信息冗余量1.1%4.6%7.6%2.一个虚拟存储器按字节编址，最多有128个用户，每个用户最多要用2048页，每页512字节。主存容量8M字节，快表按地址访问，共16个存储字，快表地址码经散列变换得到，为减少散列冲突，快表分为两组，有两套独立的相等比较电路。试：写出多用户虚地址和主存地址的格式，并给出各字段的长度。散列变换部件的输入、输出位数各为多少？每个相等比较电路的位数是多少？快表每个存储字的总长度为多少位？为哪几个字段？各字段的长度为多少位？[解答]虚地址的长度为27位，格式如下：主存的地址需要23位：格式如下由于用户号和虚页号共有18位，所以，散列变换的输入需要18位，而输出的为快表的地址，如果我们假设快表是按照字寻址，那么是3位（快表分为两组，每组8个存储字）。或4位（16个存储字，每字两个入口）。相等比较电路需要比较多用户虚页号，以消除散列冲突，所以，相等比较电路需要18位。快表中需要存储两项内容：多用户虚页号和实页号。多用户虚页号为18位，实页号为14位，共有32位。3.用一条5个功能段的浮点加法器流水线计算。每个功能段的延迟时间均相等，流水线的输出端和输入端之间有直接数据通路，而且设置有足够的缓冲寄存器。要求用尽可能短的时间完成计算，要求：列出进行加法的次序；画出流水线时空图；并计算流水线在此任务中的实际吞吐率、加速比和效率。 [解答]（1）首先需要考虑的是，8个数的的和最少需要做几次加法。我们可以发现，加法的次数是不能减少的：7次；于是我们要尽可能快的完成任务，就只有考虑如何让流水线尽可能充满，这需要消除前后指令之间的相关。由于加法满足交换率和结合率，我们可以调整运算次序如以下的指令序列，我们把中间结果寄存器称为R，源操作数寄存器称为A，最后结果寄存器称为F，并假设源操作数已经在寄存器中，则指令如下：I1： R1←A1+A2I2： R2←A3+A4I3： R3←A5+A6I4： R4←A7+A8I5： R5←R1+R2I6： R6←R3+R4I7： R7←R5+R6（2）这并不是唯一可能的计算方法。假设功能段的延迟为Δt。时空图如下，图中的数字是指令号： （3）整个计算过程需要18Δt，所以吞吐率为：加速比为：效率为：=0.394.一条3个功能段的非线性流水线及其预约表如下：SS1S2S3输入输出△t△t△t时间流水段12345S1××S2××S3××⑴写出流水线的禁止向量和初始冲突向量，并画出调度流水线的状态图。⑵求流水线的最小启动循环和最小平均启动距离。⑶通过插入非计算延迟功能段使该流水线达到最优调度，确定该流水线的最佳启动循环及其最小平均启动距离。⑷画出插入非计算延迟功能段后的流水线连接图及其预约表。⑸画出插入非计算延迟功能段后的流水线状态图。⑹在插入非计算延迟功能段前、后，分别计算流水线的最大吞吐率，并计算最大吞吐率改进的百分比。[解答]改进的百分比：5.在一台单流水线多操作部件的处理机上执行下面的程序，取指令、指令译码各需要一个时钟周期，MOVE、ADD和MUL操作各需要2个、3个和4个时钟周期。每个操作都在第一个时钟周期从通用寄存器中读操作数，在最后一个时钟周期把运算结果写到通用寄存器中。k： MOVER1，R0 ；(R1)←(R0)k十1： MULR0，R2，R1 ；(R0)←(R2)×(R1)k十2： ADDR0，R2，R3 ；(R0)←(R2)十(R3)⑴就程序本身而言，可能有哪几种数据相关?⑵在程序实际执行过程中，有哪几种数据相关会引起流水线停顿?⑶画出指令执行过程的流水线时空图，并计算执行完这三条指令共使用了多少个时钟周期。[解答]（1）k,k+1之间在R1上发生RAW，在R0上发生WAR；

k+1,k+2之间在R2上发生RAR，在R0上发生WAW；

k,k+2之间在R0上发生WAR（2）k,k+1之间在R1上发生RAW有冲突，在R0上发生WAR无冲突；

k+1,k+2之间在R2上发生RAR无冲突，在R0上发生WAW有冲突；

k,k+2之间在R0上发生WAR无冲突。（3）写R1写R0写R0取R0取R1R2取R2，R3t1t2t3t4t5t6t7t8 流水线中使用了7个周期。加上取指令、指令译码各需要的一个时钟周期，共使用了9个时钟周期。6.某机有16个向量寄存器，其中V0→V5中分别存放有向量A、B、C、D、E、F，向量长度均为8，向量各元素均为浮点数；处理部件采用两个单功能流水线，加法功能部件时间为2拍，乘法功能部件时间为3拍。采用链接技术，先计算(A＋B)×C。在流水线不停流的情况下，接着计算(D＋E)×F。求此链接流水线的流过时间为多少拍?(设寄存器入、出各需1拍)假如每拍时间为50ns，完成这些计算并把结果存进相应寄存器，此处理部件的实际吞吐率为多少MFLOPS?[解答]（1）(A＋B)与×C链接，流水线流过时间：（1+2+1+1+3+1）=9拍；(D＋E)可以在（A+B）完成时进入加法流水线，和×C并行工作，×F可以和（D+E）链接，但是必需在×C完成之后才能进入乘法流水线。（D+E）得到第一个结果是在：（1+2+1）+（8-1）+（1+2+1）=15拍时；×C完成是在：（1+2+1+1+3+1）+（8-1）=16拍时。因此是在17拍时开始计算×F，第一个结果出现的时间是：16+（1+3+1）=21拍。（2）计算全部完成所化的时间是：21+（8-1）=28拍*50ns/拍=1400ns。总共进行的浮点运算是16次加法和16次乘法，实际吞吐率为：32/1400ns=32/1.4MFLOPS=22.85MFLOPS。7.画出16台处理器仿I11iacIV的模式进行互连的互连结构图，列出PE0分别只经一步、二步和三步传送就能将信息传送到的各处理器号。[解答]答：见下图，其中0表示PE0，1表示PE1…PE0经过一步可到达：1,4,12,15；经过二步可到达：2，5，13，8，3，11，14；经过三步可到达：6，