段 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
吞吐率提高倍数=
510=1.64
3.14 有一条静态多功能流水线由5段组成,加法用1、3、4、5段,乘法用1、2、5段,第3段的时间为2△t,其余各段的时间均为△t,而且流水线的输出可以直接返回输入端或 4暂存于相应的流水寄存器中。现要在该流水线上计算 ( A B i ?) ,画出其时空图,并计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);然后求总的结果。
其次,画出完成该计算的时空图,如图所示,图中阴影部分表示该段在工作。
段 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个结果。所以吞吐率为:
TP?7 18?t如果不用流水线,由于一次求积需3△t,一次求和需5△t,则产生上述7个结果共需(4×5+3×3)△t =29△t。所以加速比为: 2 9?tS??1.61 18?t该流水线的效率可由阴影区的面积和5个段总时空区的面积的比值求得: 4 ? 5 ?3 ? 3E??0.322 5?18
3.15 动态多功能流水线由6个功能段组成,如下图:
加法 S1 S2 S3 乘法 S4 S5 S6
其中,S1、S4、S5、S6组成乘法流水线,S1、S2、S3、S6组成加法流水线,各个功能
段时间均为50ns,假设该流水线的输出结果可以直接返回输入端,而且设置有足够的缓冲寄存器,若以最快的方式用该流水计算:
?xyziii?15i
(1) 画出时空图; (2) 计算实际的吞吐率、加速比和效率。 解:机器一共要做10次乘法,4次加法。
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 1IF345678910111213141516171819202122IDEXMWBIFSSIDEXMWBIFSSIDEXMWBIFIDEXMWBIFSSIDEXMWBIFSSIDEXMWBIFSSIFIDEXMWB2
第i次迭代(i=0..98)开始周期:1+(i×17) 总的时钟周期数:(98×17)+18=1684
有正常定向路径,预测分支失败。
指令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 值给出,不必等待,所以无延迟:
CPI = 1+20%*(60%*2 + 40%*0) +5%*1 = 1.29 加速比S=CPI/1 = 1.29
3.18 在CRAY-1机器上,按照链接方式执行下述4条向量指令(括号中给出了相应功
能部件的执行时间),如果向量寄存器和功能部件之间的数据传送需要1拍,试求此链接流水线的通过时间是多少拍?如果向量长度为64,则需多少拍才能得到全部结果? V0←存储器 (从存储器中取数:7拍) V2←V0+V1 (向量加:3拍)
V3←V2 解:通过时间就是每条向量指令的第一个操作数执行完毕需要的时间,也就是各功能流水线由空到满的时间,具体过程如下图所示。要得到全部结果,在流水线充满之后,向量中后继操作数继续以流水方式执行,直到整组向量执行完毕。 访存存储器V0V1V2V3V4V5向量加左移向量逻辑乘A3 T通过=(7+1)+(1+3+1)+(1+4+1)+(1+2+1)=23(拍)T总共?T通过+(64-1)=23+63=86(拍) 3.19 某向量处理机有16个向量寄存器,其中V0~V5中分别放有向量A、B、C、D、E、F,向量长度均为8,向量各元素均为浮点数;处理部件采用两条单功能流水线,加法功能部件时间为2拍,乘法功能部件时间为3拍。采用类似于CARY-1的链接技术,先计算(A+B)*C,在流水线不停流的情况下,接着计算(D+E)*F。 (1) 求此链接流水线的通过时间?(设寄存器入、出各需1拍) (2) 假如每拍时间为50ns,完成这些计算并把结果存进相应寄存器,此处理部件的实 际吞吐率为多少MFLOPS? 解:(1)我们在这里假设A+B的中间结果放在V6中,(A+B)×C地最后结果放在V7中,D+E地中间结果放在V8中,(D+E)×F的最后结果放在V9中。具体实现参考下图: V0AV1BV6V2CV7向量加向量乘V3DV4EV8V5FV9 通过时间应该为前者((A+B)×C)通过的时间: T通过= (1+2+1)+(1+3+1) =9(拍) (2)在做完(A+B)×C之后,作(C+D)×E就不需要通过时间了。