清华大学2001年硕士入学计算机原理试题

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

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

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

指令类型
使用频率
CPI ideal

ALU操作
43％
1

Loads
21％
2

Stores
12％
2

Branches
24％
2

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

指令（字长）
使用频度f
CPI

I1（8位）
35%
1

I2（8位）
25%
2

I3（8位）
20%
2

I4（16位）
10%
2

I5（16位）
5%
1

I6（16位）
3%
2

I7（16位）
2%
2

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

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

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

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

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

B1，B4，B6，B3，B0，B4，B6，B2，B4，B5

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

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

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

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

四、（15分）有4个中断源D1、D2、D3、D4，它们的中断优先级和中断屏蔽码见下表，表中，“1”表示该中断源被屏蔽，“0”表示该中断源开放。假设从处理机响应中断源的中断服务请求到运行中断服务程序中第一次开中断所用的时间为1微秒，其它中断服务时间为10微秒。

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

（2） 处理机在0时刻开始响应中断请求，这时中断源D3和D4已经申请中断服务，在6微秒时中断源D1和D2同时申请中断服务，写出处理机开始响应各中断源的中断请求和处理机为各中断源完成中断服务的时刻。（8分）

中断源
中断优先级
中断屏蔽码

D1 D2 D3 D4

D1
1（最高）
1 1 0 0

D2
2（第二）
0 1 0 1

D3
3（第三）
1 0 1 0

D4
4（最低）
1 0 1 1

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

六、（10分）在下列单级互连网络中，将信息从一个PE播送给所有其它PE要用多少步（N＝2n个PE）？

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

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

七、（15分）在一台单流水线处理机上执行下面的程序。每条指令都要经过“取指令”、“译码”、“执行”和“写结果”4个流水段，每个流水段的延迟时间都是5ns。在“执行”流水段，LS部件完成LOAD和STORE操作，其他操作都在ALU部件中完成，两个操作部件的输出端有直接数据通路与任意一个操作部件的输入端相连接，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分）

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

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

（2） 一台有8个PE（PE0，PE1，···，PE7）的SIMD计算机，8个PE连成单向环结构。每个PE用一个单位时间可以把数据直接送给它的相邻PE。操作数Ai和Bi最初存放在PEi mod 8 中，其中i＝0，2，···，35。（6分）

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

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