高级计算机系统结构2015年复习题

1. 假设有一条长流水线，仅仅对条件转移指令使用分支目标缓冲。假设分支预测错误的开销为4个时钟周期，缓冲不命中的开销为3个时钟周期。假设：命中率为90%，预测精度为90%，分支频率为15%，没有分支的基本CPI 为1。 ①求程序执行的CPI 。

②相对于采用固定的2个时钟周期延迟的分支处理，哪种方法程序执行速度更快？ 参考答案：

解：（1）程序执行的CPI = 没有分支的基本CPI （1） + 分支带来的额外开销 分支带来的额外开销是指在分支指令中，缓冲命中但预测错误带来的开销与缓冲没有命中带来的开销之和。

分支带来的额外开销= 15% * (90%命中×10%预测错误×4 + 10％没命中×3)= 0.099 所以，程序执行的CPI ＝ 1 ＋ 0.099 = 1.099

（2）采用固定的2 个时钟周期延迟的分支处理CPI = 1 + 15%×2 = 1.3 由（1）（2）可知分支目标缓冲方法执行速度快。

2. 计算机系统中有三个部件可以改进，这三个部件的部件加速比为： 部件加速比1=30； 部件加速比2=20 部件加速比3=10 ① 如果部件2和部件3的可改进比例均为30%，那么当部件 1的可改进比例为多少时，系统加速比才可以达到10？

②如果三个部件的可改进比例分别为20%、10%和30%，三个部件同时改进，那么系统中不可加速部分的执行时间在总执行时间中占的比例是多少？ 参考答案：

解：（1）在多个部件可改进情况下，Amdahl 定理的扩展：

∑∑

+-

=

i

i

i n S F F S )1(1

已知S 1＝30，S 2＝15，S 3＝15，S n ＝10，F 1＝0.3，F 2＝0.3，得：

）

（）（10/20/0.330/0.30.30.3-11

1033F F +++++=

得F 3＝0.36，即部件3的可改进比例为36%。

（2）设系统改进前的执行时间为T ，则3个部件改进前的执行时间为：（0.3+0.3+0.2）T = 0.8T ，不可改进部分的执行时间为0.2T 。

已知3个部件改进后的加速比分别为S 1＝30，S 2＝20，S 3＝10，因此3个部件改进后的执行时间为：

T T

T T T n 045.010

2.020

3.0303.0'=++=

改进后整个系统的执行时间为：Tn = 0.045T+0.2T = 0.245T

那么系统中不可改进部分的执行时间在总执行时间中占的比例是：

82.0245.02.0=T

T

3. 设指令流水线由取指令、分析指令和执行指令3个部件构成，每个部件经过的时间为△t ，连续流入12条指令。分别画出标量流水处理机以及ILP 均为4的超标量处理机、超长指令字处理机、超流水处理机的时空图，并分别计算它们相对于标量流水处理机的加速比。 参考答案：

解：标量流水处理机的时空图：

执行完12条指令需T 1＝14△t 。

超标量流水处理机与超长指令字处理机的时空图：

超标量流水处理机中，每一个时钟周期同时启动4条指令。执行完12条指令需T 2＝5

△t ，相对于标量流水处理机的加速比为：

8.2514212=?Λ==t

t T T S

超长指令字处理机中，每4条指令组成一条长指令，共形成3条长指令。执行完12条

指令需T 3＝5△t ，相对于标量流水处理机的加速比为：

8.2514313=?Λ==t

t T T S

超流水处理机的时空图：

超标量处理机时空图

超长指令字处理机时空图

超流水处理机中，每1/4个时钟周期启动一条指令。执行完12条指令需T4＝5.75△t，相对于标量流水处理机的加速比为：

435

.2

.75

5

14

4

1

4=

?

Λ

=

=

t

t

T

T

S

4. 设一条指令的执行过程分成取指令、分析指令和执行指令三个阶段，每个阶段所需的时间分别为△t、△t和2△t 。分别求出下列各种情况下，连续执行N条指令所需的时间。

①只有“取指令”与“执行指令”重叠；

②“取指令”、“分析指令”与“执行指令”重叠。

参考答案：

①连续执行N条指令所需的时间为：4△t＋3（N-1）△t＝（3N＋1）△t

③连续执行N条指令所需的时间为：4△t＋2（N-1）△t＝（2N＋2）△t

5.有一指令流水线如下所示

②求连续输入10条指令，该流水线的实际吞吐率和效率；

②该流水线的“瓶颈”在哪一段？请采取两种不同的措施消

除此“瓶颈”。对于你所给出的两种新的流水线，连续输入10条指令时，其实际吞吐率和效率各是多少？

参考答案：

（1）

取指

时间

分析

执行

4 5 5.75

2200(ns)2009200)10050(50t )1n (t T max

m

1

i i pipeline =?++++=?-+?=∑= )(ns 220

1

T n

TP 1pipeline

-==

45.45%11

5

4400TP m

t

TP E m

1

i i

≈=?

=??

=∑= （2）瓶颈在3、4段。

? 变成八级流水线（细分）

850(ns)50

9850t 1)(n t T max

m

1

i i pipeline =?+?=?-+?=∑=

)(ns 85

1

T n

TP 1pipeline

-==

58.82%17

10

8400TP m

ti

TP E m

1

i ≈=?

=??

=∑= ? 重复设置部件

)(ns 85

1

T n

TP 1pipeline

-==

1

2

3-1 3-2

4-1

4-2 4-3 4-4

1

2

3_1

3_2

4_1

4_4

入

出

1 1

1 1

2 2 2

2

3 3 3

3

4 4 4

4

5 5 5

5 6 6 6

6

7 7 7

7

8 8 9 9 10

10 8

9

10

8

9

10 时间

段

58.82%17

10

8

85010

400E ≈=??=

6. 动态多功能流水线由6个功能段组成，如下图：

其中，S1、S4、S5、S6组成乘法流水线，S1、S2、S3、S6组成加法流水线，各个功能段时间均为50ns ，假设该流水线的输出结果可以

直接返回输入端，而且设置有足够的缓冲寄存器，若以最快的方式用该流水计算：∑=51i i i i z y x

① 画出时空图；

② 计算实际的吞吐率、加速比和效率。 参考答案：

7. 某向量处理机有16个向量寄存器，其中V0~V5中分别放有向量A 、B 、C 、D 、E 、F ，向量长度均为8，向量各元素均为浮点数；处理部件采用两条单功能流水线，加法功能部件时间为2拍，乘法功能部件时间为3拍。采用类似于CARY-1的技术，先计算（A+B ）*C ，在流水线不停流的情况下，接着计算（D+E ）*F 。

加法

①求此流水线的通过时间？（设寄存器入、出各需1拍） ②假如每拍时间为50ns ，完成这些计算并把结果存进相应寄存器，此处理部件的实际吞吐率为多少MFLOPS ？ 参考答案：

解：（1）在这里假设A ＋B 的中间结果放在V6中，（A ＋B ）×C 地最后结果放在V7中，D ＋E 地中间结果放在V8中，（D ＋E ）×F 的最后结果放在V9中。具体实现参考下图：

通过时间应该为前者（（A ＋B ）×C ）通过的时间：

T 通过= (1+2+1)+(1+3+1) =9（拍）

（2）在做完（A ＋B ）×C 之后，作（C ＋D ）×E 就不需要通过时间了。 V6←A＋B

V7←V6×C V8←D＋E

V9←V8×F

8. 假设分支目标缓冲的命中率为90%，程序中无条件转移指令的比

例为5%，没有无条件转移指令的程序CPI 值为1。假设分支目标缓冲中包含分支目标指令，允许无条件转移指令进入分支目标缓冲，则程序的CPI 值为多少？ 参考答案：

解：设每条无条件转移指令的延迟为x ，则有：

1＋5%×x ＝1.1

x ＝2

当分支目标缓冲命中时，无条件转移指令的延迟为0。 所以 程序的CPI ＝ 1 ＋ 2 × 5% ×(1 －90%) ＝1.01

9. 一台32个处理器的计算机，对远程存储器访问时间为400ns 。除

了通信以外，假设计算中的访问均命中局部存储器。当发出一个远程请求时，本处理器挂起。处理器时钟时间为1GHz ，如果指令基本的IPC 为2(设所有访存均命中Cache)，求在没有远程访

S

26.67MFLOP T

32TP 1200(ns)

24818T T ====+=（拍））－＋（通过

问的状态下与有0.2%的指令需要远程访问的状态下，前者比后者快多少?

参考答案：

解:没有远程访问时，机器的CPI为 1/基本IPC=1/2=0.5

有0.2%远程访问的机器的实际CPI为

CPI＝基本CPI＋远程访问率×远程访问开销

＝0.5＋0.2%×远程访问开销

远程访问开销为：

远程访问时间/时钟周期时间＝400 ns/1 ns＝400个时钟周期

∴ CPI＝0.5＋0.2%×400＝1.3

因此在没有远程访问的情况下的计算机速度是有0.2%远程访问的计算机速度的1.3/0.5=2.6倍。

10. 简述Tomasulo算法的基本思想。

参考答案：

答：核心思想是：①记录和检测指令相关，操作数一旦就绪就立即执行，把发生RAW 冲突的可能性减小到最少；②通过寄存器换名来消除WAR冲突和WAW冲突。寄存器换名是通过保留站来实现，它保存等待流出和正在流出指令所需要的操作数。

基本思想：只要操作数有效，就将其取到保留站，避免指令流出时才到寄存器中取数据，这就使得即将执行的指令从相应的保留站中取得操作数，而不是从寄存器中。指令的执行结果也是直接送到等待数据的其它保留站中去。因而，对于连续的寄存器写，只有最后一个才真正更新寄存器中的容。一条指令流出时，存放操作数的寄存器名被换成为对应于该寄存器保留站的名称（编号）。

11. 假定有一个处理机台数为p的共享存储器多处理机系统。设m为

典型处理机每条指令执行时对全局存储器进行访问的平均次数。设t为共享存储器的平均存取时间，x为使用本地存储器的单处理机MIPS速率。再假定在多处理机的每台处理机上执行n条指令。

①根据参数m，t，x，n和p，确定多处理机的有效MIPS速率。

②假设一台多处理机有p=32台RISC处理机，m=0.4，t=1us，要使多处理机的有效性能达到56MIPS，需要每台处理机的MIPS速率是多少（即x=？）？

③假设有p=32台CISC处理机用在上述多处理机系统中，每台处理机的x=2MIPS、m=1.6、t=1us，试问多处理机系统的有效MIPS 速率是多少？

参考答案：

解：（1）有效MIPS速率=p*x/(1+m*x*t)

（2）32*x/(1－0.4*x*1)=56，得x=5.83

（3）有效MIPS速率=p*x/(1+m*x*t)=32*2/(1+1.6*2*1)=15.24

12. 假设对指令Cache的访问占全部访问的75%；而对数据Cache的