计算机系统结构__《张晨曦、王志英》课后习题参考答案 下载本文

TP?nTpipelinem?185(ns?1)

E?TP???tii?1m?TP?40010??58.82% 817? 重复设置部件

TP?nTpipeline?185(ns?1)

E?400?10

850?8?1017?58.82%

段 4_4 4_3 4_2 4_1 3_2 3_1 1 2 432 7658 10 4-1 9 2 6 8 10 3-1 1 3 5 7 9 2 1 2 3 4 5 6 7 8 9 10 3-2 1 1 2 3 4 5 6 7 8 9 10 1 4 4-2 4-3 4-4 850ns 时间 3.13有一个流水线由4段组成,其中每当流经第3

段时,总要在该段循环一次,然后才能流到第4段。如果每段经过一次所需要的时间都是?t,问:

(1) 当在流水线的输入端连续地每?t时间输入任务时,该流水线会发生什么情况? (2) 此流水线的最大吞吐率为多少?如果每2?t输入一个任务,连续处理10个任务时的实际吞吐率和效率是多

少? (3) 当每段时间不变时,如何提高该流水线的吞吐率?仍连续处理10个任务时,其吞吐率提高多少? 解:(1)会发生流水线阻塞情况。 第1个任务 第2个任务 第3个任务 第4个任务 S1 S2 S1 S3 S2 S1 S3 stall stall S4 S3 S2 S1 S3 stall stall S4 S3 S2 S3 stall S4 S3 S3 S4

(2)

段 4 2 6 7 3 4 5 8 9 10 3 1 1 2 2 3 3 4 4 5 5 6 6 7 7 8 8 9 9 10 10 2 5 1 2 3 4 6 7 8 9 10 时间 1 1 2 3 4 5 6 7 8 9 10 23 ? t 1

11

TPmax?TpipelineTp?n12?t?23?tTpipeline?1023?t

?E?TP?5?t?50?54.35I2

(3)重复设置部件

Δt 3_1 1 2 4 3_2 Δt Δt Δt Δt

段 4 3_2 3_1 2 1 111 24 34 46 56 68 78 8 9 10 1 1 2 3 245 3 56 5 67 5 78 7 89 7 9 9 1010 9 10 23 34 时间 21014 ?t

TP?nTpipeline?1014??t7?t23?t?57??t

5吞吐率提高倍数=

10=1.64

3.14 有一条静态多功能流水线由5段组成,加法用1、3、4、5段,乘法用1、2、5段,第3段的时间为2△t,其余各段的时间均为△t,而且流水线的输出可以直接返回输入端或 4暂存于相应的流水寄存器中。现要在该流水线上计算 ( A i ? B i ) ,画出其时空图,并计算其吞吐率、加速比和效率。

i?1

? 1 △t 加法 2△t △t △t 2 △t 3 乘法 4 5 解:首先,应选择适合于流水线工作的算法。对于本题,应先计算A1+B1、A2+B2、A3+B3和A4+B4;再计算(A1

+B1) ×(A2+B2)和(A3+B3) ×(A4+B4);然后求总的结果。

12

其次,画出完成该计算的时空图,如图所示,图中阴影部分表示该段在工作。

段 5 4 3 2 1 A B C D A×B C×D A×B×C×D A=A1+B1 B=A2+B2 C=A3+B3 D=A4+B4 输0 1 2 3 入4 5 6 7 8 9 A1 A2 A3 A4 B1 B2 B3 B4 10 11 12 13 14 15 16 17 18 A×B A C B D C×D 时间

由图可见,它在18个△t时间中,给出了7个结果。所以吞吐率为:

7 TP?

18?t如果不用流水线,由于一次求积需3△t,一次求和需5△t,则产生上述7个结果共需(4×5+3×3)△t =29△t。所以加速比为:

2 9 ? t

S??1.6118?t该流水线的效率可由阴影区的面积和5个段总时空区的面积的比值求得: 4 ? ? 53 ? 3E??0.3225?18

3.15 动态多功能流水线由6个功能段组成,如下图:

S1 S2 S3 加法 S4 乘法 S5 S6

其中,S1、S4、S5、S6组成乘法流水线,S1、S2、S3、S6组成加法流水线,各个功能段时间均为50ns,假设该流水线的输出结果可以直接返回输入端,而且设置有足够的缓冲寄存器,若以最快的方式用该流水计算:

(1) 画出时空图; (2) 计算实际的吞吐率、加速比和效率。 解:机器一共要做10次乘法,4次加法。

5?xyziii?1i

13

3.16 在MIPS流水线上运行如下代码序列:

LOOP: LW R1,0(R2) DADDIU R1,R1,#1 SW R1, 0(R2) DADDIU R2,R2,#4 DSUB R4,R3,R2 BNEZ R4,LOOP

其中:R3的初值是R2+396。假设:在整个代码序列的运行过程中,所有的存储器访问都是命中的,并且在一个时钟周期中对同一个寄存器的读操作和写操作可以通过寄存器文件“定向”。问:

(1) 在没有任何其它定向(或旁路)硬件的支持下,请画出该指令序列执行的流水线时空图。假设采用排空流

水线的策略处理分支指令,且所有的存储器访问都命中Cache,那么执行上述循环需要多少个时钟周期? (2) 假设该流水线有正常的定向路径,请画出该指令序列执行的流水线时空图。假设采用预测分支失败的策略

处理分支指令,且所有的存储器访问都命中Cache,那么执行上述循环需要多少个时钟周期? (3) 假设该流水线有正常的定向路径和一个单周期延迟分支,请对该循环中的指令进行调度,你可以重新组织

指令的顺序,也可以修改指令的操作数,但是注意不能增加指令的条数。请画出该指令序列执行的流水线时空图,并计算执行上述循环所需要的时钟周期数。

解:

寄存器读写可以定向,无其他旁路硬件支持。排空流水线。

指令LW DADDIUSWDADDIUDSUBBNEZLW 1IF345678910111213141516171819202122IDEXMWBIFSSIDEXMWBIFSSIDEXMWBIFIDEXMWBIFSSIDEXMWBIFSSIDEXMWBIFSSIFIDEXMWB 2第i次迭代(i=0..98)开始周期:1+(i×17) 总的时钟周期数:(98×17)+18=1684

有正常定向路径,预测分支失败。

14

指令LWDADDIUSWDADDIUDSUBBNEZLW1IFIDIF23456EXMWBIDSEXMIFSIDEXIFIDIF7WBMEXIDIF8910111131415WBMEXIDIFWBMWBEXMWBmissmissIFIDEXMWB

第i次迭代(i=0..98)开始周期:1+(i×10) 总的时钟周期数:(98×10)+11=991

有正常定向路径。单周期延迟分支。

LOOP: LW R1,0(R2)

DADDIU R2,R2,#4 DADDIU R1,R1,#1 DSUB R4,R3,R2 BNEZ R4,LOOP SW R1,-4(R2)

第i次迭代(i =0..98)开始周期:1+(i ×6 ) 总的时钟周期数:(98×6)+10=598

指令LW DADDIUDADDIUDSUBBNEZSWLW 1IFIDIF234EXMIDEXIFIDIF5WBMEXIDIF6WBMEXIDIF7891011WBMEXIDIFWBMWBEXMWBIDEXMWB

3.17 假设各种分支指令数占所有指令数的百分比如下:

条件分支 跳转和调用 20%(其中的60%是分支成功的) 5% 现有一条段数为4的流水线,无条件分支在第二个时钟周期结束时就被解析出来,而条件分支要到第三个时钟周期结束时才能够被解析出来。第一个流水段是完全独立于指令类型的,即所有类型的指令都必须经过第一个流水段的处理。请问在没有任何控制相关的情况下,该流水线相对于存在上述控制相关情况下的加速比是多少?

解:没有控制相关时流水线的平均CPI=1

存在控制相关时:由于无条件分支在第二个时钟周期结束时就被解析出来,而条件分支 要到第3个时钟周期结束时才能被解析出来。所以:

(1)若使用排空流水线的策略,则对于条件分支,有两个额外的stall,对无条件分支,有一个额外的stall:

CPI = 1+20%*2+5%*1 = 1.45 加速比S=CPI/1 = 1.45

(2) 若使用预测分支成功策略,则对于不成功的条件分支,有两个额外的stall,对无条件分支和成功的条件分支,有一个额外的stall 1:

CPI = 1+20%*(60%*1+40%*2) +5%*1 = 1.33 加速比S=CPI/1 = 1.33

(3)若使用预测分支失败策略,则对于成功的条件分支,有两个额外的stall;对无条件分支,有一个额外的stall;对不成功的条件分支,其目标地址已经由PC 值给出,不必等待,所以无延迟:

15