2001年清华大学硕士研究生入学试题及答案

 

1．（10分） 某RISC处理机各类指令使用频率和理想CPI（指令和数据访问Cache命中率为100％时的CPI）如表1所示。而实际测得的指令访问Cache缺失率（miss rate）为5％，数据访问的Cache缺失率为10％，而Cache的缺失损失（miss penalty）为40个时钟周期。

   (1) 该机器在无Cache缺失（理想情况）时的CPI是多少？（3分）

   (2) 该机器在无Cache缺失（理想情况）时的加速比有Cache缺失时快多少倍？（7分）。

 

2．（13分） 一台模型机共有7条指令，主频25MHz。各指令的使用频度与CPI如表4所示。该模型机有8位和16位2种指令字长，采用2-4扩展操作码。8位字长指令为寄存器-寄存器（R-R）二地址类型，16位字长指令为寄存器-存储器（R-M）二地址变址寻址（-128≤变址范围≤127）类型。

   (1) 计算该机的MIPS速率。（4分）

   (2) 计算操作码的平均码长。（3分）

   (3) 该机允许使用多少个可编址的通用寄存器，多少变址寄存器？（3分）

   (4) 设计该机的两种指令格式，标出各字段位数并给出操作码编码。（3分）

 

3．（12分） 假设在1个采用组相联映像方式的Cache中，主存有B₀～B₇共8块组成，Cache有C₀～C₃共4块，组内块数为2块。每块的大小为32个字节，采用FIFO块替换算法。在一个程序执行过程中依次访问块地址流如下：

B₁，B₄，B₆，B₃，B₀，B₄，B₆，B₂，B₄，B₅

   (1) 写出主存地址的格式，并标出各字段的长度。（3分）

   (2) 写出Caehe地址的格式，并标出各字段的长度。（3分）

   (3) 画出主存与Caehe之间各个块的映像对应关系。（3分）

   (4) 列出程序执行过程中Caehe的块地址流情况，并计算Cache的块命中率。（3分）

 

4．（15分） 有4个中断源D₁、D₂、D₃、D₄，它们的中断优先级和中断屏蔽码见表6，表中“1”表示该中断源被屏蔽，“0”表示该中断源开放。假设从处理机响应中断源的中断服务请求到运行中断服务程序中第一次开中断所用的时间为1μs，其他中断服务时间为10μs。

   (1) 处理机在0时刻开始响应中断请求，这时4个中断源都已经申请中断服务，写出处理机开始响应各中断源的中断请求和处理机为各中断源完成中断服务的时刻。（7分）

   (2) 处理机在0时刻开始响应中断请求，这时中断源D₃和D₄已经申请中断服务，在6μs时中断源D₁和D₂同时申请中断服务，写出处理机开始响应各中断源的中断请求和处理机为各中断源完成中断服务的时刻。（8分）

 

5．（10分） 假定将某一执行部件性能改进后速度提高10倍。改进后被改进部件执行时间占系统总运行时间的50％。则改进后获得的加速比S_p是多少？

 

6．（10分） 在下列单级互连网络中，将信息从一个PE播送给所有其他PE要用多少步（N = 2ⁿ个PE）？

   (1) 混洗交换网络，每步只能做一次混洗或一次交换。（5分）

   (2) 超立方体网络，每步i（0≤i≤n-1）可实现寻径函数C_i。（5分）

 

7．（15分） 在1台单流水线处理机上执行下面的程序。每条指令都要经过“取指令”、“译码”、“执行”和“写结果”4个流水段，每个流水段的延迟时间都是5ns。在“执行”流水段，LS部件完成LOAD和STORE操作，其他操作都在ALU部件中完成，2个操作部件的输出端有直接数据通路与任意1个操作部件的输入端相连接，ALU部件产生的条件码也能够直接送入控制器。

   1：                  SUB  R0，  R0                 ；R0←0

   2：                  LOAD  R1， #8                 ；R1←向量长度8

   3：LOOP：     LOAD  R2，A（R1）         ；R2←A向量的一个元素

   4：                  MUL  R2，  R1                 ；R2←（R2）×（R1）

   5：                  ADD  R0，  R2                ；R0←（R0）+（R2）

   6：                  DNE  R1，  LOOP            ；R1←（R1）-1，若（R1）≠0转向LOOP

   7：                  STORE R0，S                     ；保存结果

   (1) 采用静态分支预测技术，每次都预测转移不成功。画出指令流水线的时空图（中间部分可以省略，图中可用指令序号表示），计算流水线的吞吐率和加速比，并分别计算译码部件和ALU部件的使用效率。（8分）

   (2) 采用静态分支预测技术，每次都预测转移成功。计算指令流水线的吞吐率和加速比，并分别计算译码部件和ALU部件的使用效率。（7分）

 

   8．（15分） 分别在下面3种计算机系统上用最短的时间来计算表达式 。假设加法和乘法分别需要2个和4个单位时间，从存储器取指令、取数据、译码的时间忽略不计，所有的指令和数据已装入有关的PE或处理机中。PE或处理机中有一个加法器和一个乘法器，同一时刻只有其中一个可以使用，试确定下列每种情况的最小计算时间。

   (1) 1台串行计算机，这种单处理机系统不需要数据寻径操作。（3分）

   (2) 1台有8个PE（PE₀，PE₁，…，PE₇）的SIMD计算机，8个PE连成单向环结构。每个PE用1个单位时间可以把数据直接送给它的相邻PE。操作数A_i和B_i最初存放在PE_{i mod 8}中，其中i=0，2，…，35。（6分）

   (3) 分布存储器的MIMD多处理机，8个CPU用立方体网连接。在相邻CPU之间传送一个数据需要一个单位时间。操作数A_i和B_i最初存放在CPU_{i mod 8}中，其中i=0，1，…，35。最终结果s可以放在任意CPU的寄存器中。（6分）

 

 

1．（10分）

   (1) 由于是RISC计算机，只有LOAD和STORE可以进行数据访问。而所有指令的执行都需要取指操作。所以，可得表2。

   由

   可得CPI_ideal =（1×43%）+（2×21%）++（2×12%）+（2×24%）= 1.6

   (2) 由于

   可得表3。

CPI_real =（3×43%）+（8×21%）+（8×12%）+（4×24%）= 4.9

（或CPI_real = CPI_ideal + 40×5% + 40×10%×（21%+12%）= 4.9）

所以得加速比= = =3.1

2．（13分）

   (1)

   (2) 由于采用2-4扩展操作码，对使用频度高的3条指令用2位编码(00，01，10)，其余的4条指令采用4位编码(1100，1101，1110，1111)。所以，平均操作码长为

   2×(0.35+0.25+0.20)+4×(0.1+0.05+0.03+0.02)=2.4

   (3) 对于8位字长的寄存器一寄存器型变址寻址方式指令，操作码长为2，所以寄存器最多只能用3位表示。所以，最多只能有8个通用寄存器。

   对于16位字长的寄存器一存储器型变址寻址方式，操作码占4位，通用寄存器占3位。根据题意，偏移地址需要占用8位。所以只能有1位用来表示变址寄存器，变址寄存器个数为2。

   (4) 8位字长指令格式为

3条指令的操作码分别为00，01，10。

16位字长指令格式为：

   4条指令的操作码分别为1100，1101，1110，1111。

 

   3．(12分)

   (1) 主存地址：

   (2) Cache地址：

   (3) 略。

   (4) 程序执行过程中Cache的地址流情况如表5所示。

 

所以，块命中率为：3/10=30%。

 

   4．(15分)

   (1) 实际的中断过程如图1所示。

 

                          中断请求  主程序      中断服务程序

图1  实际的中断服务过程

 

   处理机开始响应D₁中断源中断请求的时刻为：0µs

   处理机开始响应D₂中断源中断请求的时刻为：2µs

   处理机开始响应D₃中断源中断请求的时刻为：1µs

   处理机开始响应D₄中断源中断请求的时刻为：13µs

   处理机为D₁中断源完成中断服务的时刻为：44µs

   处理机为D₂中断源完成中断服务的时刻为：13µs

   处理机为D₃中断源完成中断服务的时刻为：34µS

   处理机为D₄中断源完成中断服务的时刻为：24µs

 

   (2) 实际的中断服务过程如图2所示。

 

                          中断请求  主程序      中断服务程序

图2  实际的中断服务过程

 

   处理机开始响应D₁中断源的中断请求的时刻为：7µs

   处理机开始响应D₂中断源的中断请求的时刻为：6µs

   处理机开始响应D₃中断源的中断请求的时刻为：0µs

   处理机开始响应D₄中断源的中断请求的时刻为：1µs

   处理机为D₁中断源完成中断服务的时刻为：18µs

   处理机为D₂中断源完成中断服务的时刻为：28µs

   处理机为D₃中断源完成中断服务的时刻为：44µs

   处理机为D₄中断源完成中断服务的时刻为：34µs

 

   5．(10分)

   假设系统在改进前后的执行时间分别为T_before和T_after

                                    (1)

由(1)式可得

                                  (2)

由题意

                                                        (3)

(2)-(3)得

                                           (4)

                                                             (5)

由(4)、(5)可得

 

   6．(10分)

   根据题义：N个PE可用n位二进制数表示，计算信息从一个PE播送给所有其他PE所需的步数，只需计算距离最长的2个PE间信息传送的步数即可。不失一般性，计算从PE(000...000)_n到PE(111...111)_n的距离。

   (1) 只需执行一系列交换——混洗——交换的操作即可。

   PE(000...000)_n PE(000...001)_n PE(000...010)_n.….. PE(111...110)_n PE(111...111)_n。因此，需要n次交换，n-1次混洗操作。总共需要2n-1步。

   (2) 由于立方体网络，每步i(0≤i≤n-1)可实现寻径函数 。所以，只需n步（每步执行寻径函数C_i(0≤i≤n-1)）即可。

 

   7．(15分)

   (1) 采用静态分支预测技术，每次都预测转移不成功，指令流水线时空图如图3所示。

 

图3  流水线时空图

 

   吞吐率：

   加速比：

   译码部件的效率：

   ALU部件的效率：

   (2) 采用静态分支预测技术，每次都预测转移成功，指令流水线时空图如图4所示。

 

图4  流水线时空图

 

  

  

  

  

 

   8．(15分)

   (1) 在SISD计算机中计算s需要串行计算36次加法和35次乘法。共需要时间

T = 2×36 + 4×35 = 212单位时间

   (2) 在SIMD计算机上计算过程如下：

   根据题意，向量中的36对元素平均地分配到了8个PE中，其中PE₀～PE₃各分配5对元素，其他PE各分配4对元素。

   第一步：在各个PE中形成部分积。

   用时t₁ = 5次加法 + 4次乘法 = 2×5 + 4×4 = 26单位时间

   第二步：模2为1的PE将部分积送到前续PE中。即PE_i → PE_i-1 (i mod 2 = 1)，屏蔽其他PE。在PE_i中(i mod 2 = 1)进行乘法运算，形成部分积，屏蔽其他的PE。

   用时t₂ = 1次传送 + 1次乘法 = 1 + 4 = 5单位时间

   第三步：Pe_i → PE_i-2 (i mod 4 = 2)，即PE₆ → PE₄，PE₂ → PE₀，屏蔽其他的PE。在PE₀和PE₄进行乘法运算，形成部分积。屏蔽其他的PE。

   用时t₃ = 2次传送 + 1次乘法 = 2 + 4 = 6单位时间。

   第四步：PE₄ → PE₀，屏蔽其他的PE。在PE₀中形成最终结果，屏蔽其他的PE。

   用时t₄ = 4次传送 + 1次乘法 = 4 + 4 = 8单位时间

   所以，总共用时：t₁ + t₂ + t₃ + t₄ = 45单位时间。

   (3) MIMD计算机上计算过程如下：

   根据题意，向量中的36对元素平均地分配到了8个CPU中，其中CPU₀～CPU₃各分配5对元素，其他CPU各分配4对元素，如图5所示。

   第一步：在各个CPU中形成部分积。

   CPU₀～CPU₃用时 = 5次加法 + 4次乘法 = 2×5 + 4×4 = 26单位时间

   CPU₄～CPU₇用时 = 4次加法 + 3次乘法 = 2×4 + 4×3 = 20单位时间

   第二步：

   CPU₄→CPU₅，CPU₆→CPU₇，在CPU₅，CPU₇中形成部分积。到此，CPU₅和CPU₇分别用时 = 20 + 1次传送 + 1次乘法 = 20 + 1 + 4 = 25单位时间。

   CPU₀→CPU₁，CPU₂→CPU₃在CPU₁，CPU₃中形成部分积。到此，CPU₁和CPU₃分别用时 = 26 + 1次传送 + 1次乘法 = 26 + 1 + 4 = 31单位时间。

   与此同时，CPU₅→CPU₇，在CPU₇中形成部分积。到此CPU₇共用时 = 25 + 1次传送 + 1次乘法 = 25 + 1 + 4 = 30单位时间。

   CPU₇→CPU₃，到此共用时 = 30 + 1次传送 = 31单位时间。

   第三步：在CPU₃中形成部分积（ = CPU₃的部分积×CPU₇送来的部分积），到此，共用时 = 31 + 1次乘法 = 35。与此同时，CPU₁在第二步（第31单位时间）形成的部分积已经送到，在CPU₃中形成最终结果。

   总共用时 = 35 + 1次乘法 = 39单位时间。

 

图5  8个CPU与36对元素的对应关系