第03章流水线技术

1、1 1193193张晨曦 编著华中科技大学 计算机学院2 0 1 3 年 3 月2 2193193作业：作业：P91P913.83.83.103.103.113.113 31931933.2MIPS 的基本流水线3.3流水线中的相关 MIPS MIPS 流水线流水线 流水线性能分析流水线性能分析 结构相关结构相关 数据相关数据相关 控制相关控制相关3.4MIPS R4000 流水线计算机3.1流水线(Pipeline)的基本概念第三章 流水线技术4 41931933.1流水线的基本概念3.1.1 基本概念 1. 产品生产流水线下面通过一个例子来说明流水线的好处下面通过一个例子来说明流水线的好处

2、: : 两种方案两种方案 两种方案的工作过程对比两种方案的工作过程对比第三章 流水线技术5 5193193一套机器一个工人一套机器一个工人 一套可分离工具一套可分离工具4 4个工人个工人6 6193193 流水线生产过程的抽象描述流水线生产过程的抽象描述 这种流水工作方式的主要特点：重叠这种流水工作方式的主要特点：重叠7 71931932. 指令流水线指令流水线（处理机级流水线）处理机级流水线）把指令的解释过程分解为把指令的解释过程分解为“分析分析”和和“执行执行”两个子过程，并让这两个子过程分别用独立的分两个子过程，并让这两个子过程分别用独立的分析部件和执行部件来实现。析部件和执行部件来实现

3、。理想情况：理想情况：速度提高一倍速度提高一倍3.1 流水线的基本概念8 81931939 9193193分析分析执行执行时间时间 t t分析分析k k执行执行k kT=(p+qT=(p+q n n)t=2nt=2n t, p+q=2, p=0. p:t, p+q=2, p=0. p:重叠数重叠数T=(p+qT=(p+q n n)t=(1+n)t=(1+n) t, p+q=2, p=1t, p+q=2, p=1分析分析k+1k+1执行执行k+1k+13.1 流水线的基本概念10101931933. 浮点加法流水线浮点加法流水线（部件级流水线、部件级流水线、运算操作流水线）运算操作流水线）把浮点

4、加法的全过程分解为把浮点加法的全过程分解为“求阶差求阶差”、“对对阶阶”、“尾数相加尾数相加”、“规格化规格化”四个子过程，四个子过程，并让并让它们分别用各自独立的部件来实现。它们分别用各自独立的部件来实现。理想情况：理想情况：速度提高速度提高3 3倍倍 T=(p+qT=(p+q n n)t=(3+n)t=(3+n) t,p+q=4,p=3t,p+q=4,p=33.1 流水线的基本概念11111931933.1 流水线的基本概念12121931934. 时空图时空图时空图时空图从时间和空间两个方面描述了流水从时间和空间两个方面描述了流水线的工作过程。时空图中，横坐标代表时间，线的工作过程。时空

5、图中，横坐标代表时间，纵坐标代表流水线的各个段。纵坐标代表流水线的各个段。3.1 流水线的基本概念1313193193几个“123”与坐标解 流水线技术流水线技术流水线技术是指：将一个重复的时序过程分解是指：将一个重复的时序过程分解成为若干个子过程，而每个子过程都可有效地在成为若干个子过程，而每个子过程都可有效地在其专用功能段上与其他子过程同时执行其专用功能段上与其他子过程同时执行? ?6流水线技术的特点(1) (1) 流水过程由多个相联系的子过程组成，每个流水过程由多个相联系的子过程组成，每个子过程称为流水线的子过程称为流水线的“级级”或或“段段”。“段段”的数的数

6、目称为流水线的目称为流水线的“深度深度”。(2) (2) 每个子过程由专用的每个子过程由专用的功能段功能段实现；实现；3.1 流水线的基本概念1515193193(4) (4) 流水线需要有流水线需要有“通过时间通过时间”（第一个任务流出结果（第一个任务流出结果所所需的时间），在此之后流水过程才进入稳定工作状需的时间），在此之后流水过程才进入稳定工作状态，每一个时钟周期（拍）流出一个结果；态，每一个时钟周期（拍）流出一个结果；(3) (3) 各个功能段所需时间应尽量相等，否则，时间长各个功能段所需时间应尽量相等，否则，时间长的功能段将成为流水线的瓶颈，会造成流水线的的功能段将成为流水线的瓶颈，

7、会造成流水线的 “堵塞堵塞”和和“断流断流”。这个时间一般为一个时钟。这个时间一般为一个时钟周期周期（拍）；（拍）；(5) (5) 流水技术适合于大量重复的时序过程，只有输入流水技术适合于大量重复的时序过程，只有输入端能连续地提供任务，流水线的效率才能充分发端能连续地提供任务，流水线的效率才能充分发挥。挥。3.1 流水线的基本概念16161931933.1 流水线的基本概念分析分析k执行执行k分析分析k+1执行执行k+1分析分析k+2执行执行k+2为了尽量减少为了尽量减少瓶颈瓶颈损失，较好的办法是缓冲技术。设置先行指令缓损失，较好的办法是缓冲技术。设置先行指令缓冲栈，两个工作时间不相等的功能部

8、件可以各自独立地工作。这种冲栈，两个工作时间不相等的功能部件可以各自独立地工作。这种技术经常被采用。技术经常被采用。分析分析k执行执行k分析分析k+1执行执行k+1分析分析k+2执行执行k+2171719319318181931933.1.2 流水线的分类流水线可以按不同的观点进行分类。流水线可以按不同的观点进行分类。 单功能流水线：单功能流水线：只能完成一种固定功能的只能完成一种固定功能的 流水线。流水线。 多功能流水线：多功能流水线：流水线的各段可以进行不同的流水线的各段可以进行不同的 连接，从而实现不同的功能。连接，从而实现不同的功能。 例如：例如： TI ASCTI ASC的多功能流水

9、线的多功能流水线1按功能的多少来分3.1 流水线的基本概念19191931932020193193在静态流水线中，只有当输入是一串相同在静态流水线中，只有当输入是一串相同的运算操作时，流水的效率才能得到发挥。的运算操作时，流水的效率才能得到发挥。2按同一时间内各段之间的连接方式来分 静态流水线：静态流水线：在同一时刻，流水线的各段只能在同一时刻，流水线的各段只能 按同一种功能的连接方式工作。按同一种功能的连接方式工作。 3.1 流水线的基本概念2121193193 动态流水线：动态流水线：在同一时刻，流水线的各段可以在同一时刻，流水线的各段可以 按不同功能的连接方式工作。按不同功能的连接方式工

10、作。 这样就不是非得相同运算的一串操作才能这样就不是非得相同运算的一串操作才能 流水处理。流水处理。 优点：优点：能提高流水线的效率能提高流水线的效率 缺点：缺点：会使流水线的控制变得复杂会使流水线的控制变得复杂3.1 流水线的基本概念2222193193 静、动态流水线时空图的对比静、动态流水线时空图的对比23231931933按照流水线的级别来分 部件级流水线部件级流水线（运算操作流水线）：把处理机的（运算操作流水线）：把处理机的 算术逻辑部件分段，使得各种数据类型的操作能算术逻辑部件分段，使得各种数据类型的操作能 够进行流水够进行流水( (求阶差、对阶、尾数加、规格化求阶差、对阶、尾数加

11、、规格化) )。 处理机级流水线处理机级流水线（指令流水线）：把指令的（指令流水线）：把指令的解释解释 执行执行过程按照流水方式进行处理。过程按照流水方式进行处理。 例如：例如：前面把指令解释过程分解为：前面把指令解释过程分解为： 分析分析和和执行执行 MIPSMIPS的基本流水线把指令解释过程分解为：的基本流水线把指令解释过程分解为： 取指令、指令译码、取指令、指令译码、执行执行、访存、写回。、访存、写回。3.1 流水线的基本概念24241931933.1 流水线的基本概念2525193193 处理机间流水线处理机间流水线（宏流水线）：它是指由两个（宏流水线）：它是指由两个 以上的处理机串行

12、地对同一数据流进行处理，以上的处理机串行地对同一数据流进行处理， 每个处理机完成一项任务。每个处理机完成一项任务。3.1 流水线的基本概念2626193193顺序流动流水线：顺序流动流水线：流水线输出端任务流出的顺流水线输出端任务流出的顺 序与输入端任务流入的顺序序与输入端任务流入的顺序相同相同。 异步流动流水线异步流动流水线（乱序流水线）：流水线输出（乱序流水线）：流水线输出 端任务流出的顺序与输入端任务流入的顺序端任务流出的顺序与输入端任务流入的顺序 不同不同。4. 按照流动是否可以乱序来分3.1 流水线的基本概念2727193193S1S1S2S2S3S3S4S4S5S5S6S6寄存器寄

13、存器 R0R0读读写写专用路径专用路径k: R0(R1) k+1: k+2:R2(R0)+(R3)k+3:k+4:k+5:ti+4 k+4 k+3 k+2空闲空闲空闲空闲空闲空闲ti+3 k+3 k+2空闲空闲空闲空闲空闲空闲k+1ti+2 k+3 k+2空闲空闲空闲空闲k+1kti+1 k+3 k+2空闲空闲k+1kk-1tik+3 k+2 k+1kk-1k-2 正常流动正常流动k+5 k+4 k+3 k+2 k+1k功能段功能段S1S2S3S4S5S62828193193ti+5k+8(k+7) k+6k+2k+5k+4k+3ti+4k+7(k+6) k+2k+5k+4k+3k+1ti+3

14、k+6k+5 (k+2) k+4k+3k+1 k ti+2k+5k+4 (k+2)k+3k+1 k k-1ti+1k+4k+3 (k+2)k+1 k k-1k-2tik+3(k+2) k+1 k k-1k-1k-3 正常流动正常流动k+5k+4k+3k+2k+1K功能段功能段S1S2S3S4S5S629291931935按照数据表示来分 向量处理机：向量处理机：具有向量指令和向量数据表示的具有向量指令和向量数据表示的 处理机。处理机。 例如：例如：TI ASC, TI ASC, CRAY-ICRAY-I 等等 标量处理机：标量处理机：不具有向量指令和向量数据表示，不具有向量指令和向量数据表示，

15、 仅对标量进行流水处理的处理机。仅对标量进行流水处理的处理机。 例如：例如：IBM360/91, Amdahl 470V/6IBM360/91, Amdahl 470V/6 等等6. 按照是否有反馈回路来分 线性流水线：线性流水线：流水线中的各段串行连接，没流水线中的各段串行连接，没 有反馈回路。有反馈回路。 非线性流水线：非线性流水线：流水线中的各段除有串行连接流水线中的各段除有串行连接 外，还有反馈回路。外，还有反馈回路。3.1 流水线的基本概念30301931933.1 流水线的基本概念3131193193 流水线的调度问题流水线的调度问题什么是冲突如何避开？什么是冲突如何避开？3232

16、193193非线性流水线的连接图和预约表 P64-67 1 1 2 23 34 45 56 67 7S1S1 S2S2S3S3S4S4时间时间段段S1S2S3S4前馈线前馈线反馈线反馈线3333193193 1 1 2 23 34 45 56 67 78 89 910101111S1S11 11 1 2 2 1 1 2 2 3 32 2 3 3 4 4S2S21 11 1 2 22 2 3 33 3 4 4S3S31 12 21 13 32 24 4S4S41 12 23 3时间时间段段时间时间段段 1 1 2 23 34 45 56 67 78 89 910101111S1S11 12 21

17、 13 32 2 1 1 4 43 32 2 5 54 43 3 5 5S2S21 12 21 13 32 24 43 35 54 4S3S31 12 21 1 3 32 2 4 43 3 5 5S4S41 12 23 34 45 53434193193 1 1 2 23 34 45 56 67 78 89 910101111S1S11 11 1 2 2 1 1 2 2 3 32 2 3 3 4 4S2S21 11 1 2 22 2 3 33 3 4 4S3S31 12 21 13 32 24 4S4S41 12 23 3时间时间段段时间时间段段启动周期启动周期重复启动周期重复启动周期 1 1

18、 2 23 34 45 56 67 78 89 910101111S1S11 11 12 2 1 12 23 3S2S21 11 12 22 2S3S31 11 12 22 2S4S41 12 23535193193 1 1 2 23 34 45 56 67 78 89 9S1S1 S2S2 S3S3 S4S4 S5S5 时间时间段段1.1. 流水线的调度问题流水线的调度问题预约表与禁止表预约表与禁止表禁止表禁止表F (Forbidden)=1,5,6,8,F (Forbidden)=1,5,6,8, 同行相减同行相减, , 删除相同删除相同, , 无差不取无差不取3.1.3 非线性流水线的调

19、度3.1 流水线的基本概念36361931933.1 流水线的基本概念2.2. 流水线的调度问题流水线的调度问题禁止表与冲突向量禁止表与冲突向量C0C0C0=(Cn,Cn-1,C3,C2,C1)C0=(Cn,Cn-1,C3,C2,C1)Ci=1,Ci=1,若若i i属于属于F F，否则，否则Ci=0Ci=0由由F=F=1 1, ,5 5, 6 6, 8 得到冲突向量得到冲突向量CollisionCollision：C0=(C0=(1 10 01 11 10000001 1) )37371931933.1 流水线的基本概念3.3. 流水线的调度问题流水线的调度问题冲突向量与状态转换冲突向量与状态

20、转换假设启动周期为假设启动周期为j j，得到新的冲突向量，得到新的冲突向量SHRSHR(j)(j)(C0): (C0): 表示右移表示右移j j位位并使之与并使之与C0C0做做“或或”运算运算SHRSHR(j)(j)(C0)(C0) (C0)(C0)假设当前冲突向量是假设当前冲突向量是CkCk，j j是允许的时间间隔，是允许的时间间隔，则得到新的冲突向量：则得到新的冲突向量：SHRSHR(j)(j)(Ck)(Ck) (C0)(C0)38381931933.1 流水线的基本概念3.3. 流水线的调度问题流水线的调度问题状态转换与新的冲突向量状态转换与新的冲突向量由禁止表由禁止表F=1,5,6,8

21、F=1,5,6,8得到后续任务的可用时间得到后续任务的可用时间间隔为间隔为j=2j=2、3 3、4 4、7 7j=2j=2：(00101100)(00101100) (10110001)(10110001)=(10111101)=(10111101)，可用可用2 2、7 7j=3j=3：(00010110)(00010110) (10110001)(10110001)=(10110111)=(10110111)，可用可用4 4、7 7j=4j=4：(00001011)(00001011) (10110001)(10110001)=(10111011)=(10111011)，可用可用3 3、7

22、7j=7j=7：(00000001)(00000001) (10110001)(10110001)=(10110001)=(10110001)，可用可用2 2、3 3、4 4、7 739391931933.1 流水线的基本概念3.3. 流水线的调度问题流水线的调度问题状态转换图状态转换图40401931933.1 流水线的基本概念4.4. 流水线的调度问题流水线的调度问题平均延迟拍数与最优调度平均延迟拍数与最优调度调度策略平均延迟拍数调度策略平均延迟拍数(2,7)4.5(3,4,7)4.67(2,2,7)3.67(4,3,7)4.67(3,7)5(4,7)5.5(3,4)3.5(7)7(3,4

23、,3,7)4.254141193193 1 234567 S1 S1 S2 S2 S3 S3 S4 S4 时间时间段段3.1 流水线的基本概念补充练习题补充练习题已知如下预约表，已知如下预约表，求最优调度方案求最优调度方案42421931933.1 流水线的基本概念43431931933.2MIPS的基本流水线3.2.1 MIPS的一种简单实现首先讨论在不流水的情况下，如何实现首先讨论在不流水的情况下，如何实现MIPSMIPS。1. 实现MIPS指令的一种简单数据通路第三章 流水线技术444419319345451931932. 一条MIPS指令最多需要以下5个时钟周期：（1 1） 取指令周期

24、取指令周期（IFIF） IR MemPC NPC PC4操作：根据操作：根据PCPC值从存储器中取出指令，并送入值从存储器中取出指令，并送入指令寄存器指令寄存器IRIR；PCPC增值增值4 4，指向下一条指令，并将，指向下一条指令，并将下一条指令的地址放入临时寄存器下一条指令的地址放入临时寄存器NPCNPC3.2 MIPS的基本流水线46461931934747193193（2 2）指令译码）指令译码/ /读寄存器周期读寄存器周期（IDID） A RegsIR6 .10 B RegsIR11 .15 Imm (IR16)16 # IR16 .31 操作操作 指令译码和读寄存器是并行进行的。之所

25、指令译码和读寄存器是并行进行的。之所 以能做到这一点，是因为在以能做到这一点，是因为在MIPSMIPS指令格式中，指令格式中， 操作码在固定位置。这种技术也称为操作码在固定位置。这种技术也称为固定字段固定字段 译码。译码。A A、B B、ImmImm、LMD LMD 临时寄存器。临时寄存器。3.2 MIPS的基本流水线4848193193 I 类型指令 6 5 5 16 操作码 rs rt 立即值 字节、半字、字的载入和储存； rtrs op 立即值。分支指令: RegsrtRegsrs+immediate R 类型指令 6 5 5 5 5 6 操作码 rs rt rd shamt Func

26、寄存器寄存器 ALU 操作：rdrs func rt； 函数对数据的操作进行编码：加、减、； 对特殊寄存器的读/写和移动。 J 类型指令 6 26 操作码 与 PC 相加的偏移量 跳转，跳转并链接，从异常（exception）处自陷和返回。 图 2.10 MIPS 的指令格式布局 各种类型指令的格式ABAB49491931935050193193（3 3）执行执行/ /有效地址计算周期有效地址计算周期（EXEX） 在这个周期，不同的指令有不同的操作。在这个周期，不同的指令有不同的操作。3.2 MIPS的基本流水线5151193193 存储器访问存储器访问 ALUOutput AImm 操作操作

27、5252193193 寄存器寄存器寄存器寄存器 ALU ALU 操作操作 ALUOutput A op B 操作操作5353193193 寄存器寄存器立即值立即值 ALU ALU 操作操作 ALUOutput A op Imm 操作操作5454193193 分支操作分支操作(P63) (P63) BEQZ R4,nameBEQZ R4,name ALUOutput NPCImm Cond (A op 0) 操作操作?5555193193（4 4）存储器访问存储器访问/ /分支完成周期分支完成周期（MEMMEM） 在该周期处理的在该周期处理的MIPSMIPS指令只有指令只有LoadLoad、St

28、oreStore和和 分支指令。分支指令。这里，将有效地址计算周期和执行周期合并这里，将有效地址计算周期和执行周期合并为一个时钟周期，这是由为一个时钟周期，这是由 MIPSMIPS指令集结构本指令集结构本身的特点所允许的，因为在身的特点所允许的，因为在MIPSMIPS指令集结构指令集结构中，没有任何指令需要同时中，没有任何指令需要同时计算计算数据的存储数据的存储器地址器地址、计算计算分支指令的目标地址分支指令的目标地址和和进行进行数数据处理据处理。3.2 MIPS的基本流水线5656193193 存储器访问存储器访问 LMD MemALUOutput 或或 Mem ALUOutput B操作操

29、作SW 500(R4), SW 500(R4), R3R3LW LW R1R1, 30(R2), 30(R2) R1R1 MemALUOutput 能否，为什么能否，为什么? ?3.2 MIPS的基本流水线57571931935858193193 分支操作分支操作 if (cond) PC ALUOutput else PC NPC操作操作5959193193 BEQZ R4,nameBEQZ R4,name6060193193（5 5）写回周期）写回周期（WBWB） 不同指令在该周期完成的工作也不一样。不同指令在该周期完成的工作也不一样。 寄存器寄存器寄存器型寄存器型 ALU ALU 指令指

30、令 (R)(R) RegsIR16 .20 ALUOutput操作操作 寄存器寄存器立即值型立即值型 ALU ALU 指令指令 (I)(I) RegsIR11 .15 ALUOutput操作操作 LoadLoad 指令指令(I)(I) RegsIR11 .15 LMD 操作操作3.2 MIPS的基本流水线6161193193寄存器寄存器寄存器型寄存器型 ALU ALU 指令指令 ADD R1, R2, R3 (P60)ADD R1, R2, R3 (P60) RegsIR16 .20 ALUOutput6262193193寄存器寄存器立即值型立即值型 ALU ALU 指令指令 ADD R8,R

31、2,#3 (P62)ADD R8,R2,#3 (P62) RegsIR11 .15 ALUOutput6363193193LoadLoad 指令指令 RegsIR11 .15 LMD64641931933. 分支指令需要4个时钟周期, 其它指令需要5个时钟周期 假设分支指令占总指令数的假设分支指令占总指令数的1212, , 则则: : CPICPI4 4* *0.12+50.12+5* *0.88 = 4.880.88 = 4.88 上述实现无论在性能上，还是在硬件开销上，上述实现无论在性能上，还是在硬件开销上，都不是优化的。都不是优化的。3.2 MIPS的基本流水线65651931933.2

32、.2 基本的MIPS流水线我们可以把我们可以把3.2.13.2.1中的数据通路流水化：中的数据通路流水化：每个时钟周期启动一条新的指令。每个时钟周期启动一条新的指令。这样，该数据通路中的每一个周期就成这样，该数据通路中的每一个周期就成了一个流水段。了一个流水段。1. 一种简单的 MIPS 流水线2. 简单MIPS流水线的流水过程第一种描述第一种描述（类似于时空图）（类似于时空图）第二种描述第二种描述（按时间错开的数据通路序列）（按时间错开的数据通路序列）3.2 MIPS的基本流水线66661931933.2 MIPS的基本流水线类似于时空图类似于时空图6767193193按时间错开的数据通路序

33、列按时间错开的数据通路序列68681931933. 采用流水技术还应解决好以下几个问题：上述简单上述简单MIPSMIPS流水线中：流水线中： 指令存储器指令存储器（IMIM）和）和数据存储器数据存储器（DMDM）分）分 开，避免了访存冲突。开，避免了访存冲突。 IDID段和段和WBWB段都要访问同一寄存器文件。段都要访问同一寄存器文件。 IDID段：读段：读WBWB段：写段：写 如何解决对如何解决对同一寄存器同一寄存器的访问冲突？的访问冲突？（1 1）应保证不会在同一个时钟周期内在同一数据）应保证不会在同一个时钟周期内在同一数据 通路资源上做不同的操作。通路资源上做不同的操作。 例如，不能要求

34、一个例如，不能要求一个ALUALU同时既做有效同时既做有效 地址计算，又做减法操作。地址计算，又做减法操作。Add R1,30(R2)?Add R1,30(R2)?3.2 MIPS的基本流水线69691931933.2 MIPS的基本流水线读写读写寄存器冲突：寄存器冲突：R PC R PC NPCNPC等等7070193193 没有考虑没有考虑 PC PC 问题问题流水线为了能够每个时钟周期启动一条流水线为了能够每个时钟周期启动一条新的指令，就必须在每个时钟周期进行新的指令，就必须在每个时钟周期进行PCPC值值的加的加4 4操作，并保留新的操作，并保留新的PCPC值。这种值。这种操作必操作必须

35、在须在IFIF段段完成完成，以便为取下一条指令做好准，以便为取下一条指令做好准备。备。3.2 MIPS的基本流水线71711931937272193193但分支指令也可能改变但分支指令也可能改变PCPC的值，而且是的值，而且是在在MEMMEM段进行，这会导致段进行，这会导致( (PCPC) )冲突冲突。73731931937474193193为解决问题，我们为解决问题，我们重新组织数据通路重新组织数据通路，把所有改变，把所有改变PCPC值的值的操作都放在操作都放在IFIF段进行。段进行。但分支指令如何处理？但分支指令如何处理？ 7575193193（2 2）每一流水段内的操作都必须在一个时钟周

36、期）每一流水段内的操作都必须在一个时钟周期 内完成内完成 流水线各段之间需设置流水线寄存器流水线各段之间需设置流水线寄存器 （也称为（也称为锁存器锁存器） 流水线寄存器组及其所含寄存器的流水线寄存器组及其所含寄存器的命名命名 例如，例如，IDID段和段和EXEX段之间的流水线寄存段之间的流水线寄存 器组中的器组中的IRIR寄存器的名称为寄存器的名称为: :ID/EX.IRID/EX.IR 流水线寄存器的作用流水线寄存器的作用 把数据和控制信息从一个流水段传把数据和控制信息从一个流水段传 送到下一个流水段。送到下一个流水段。（3 3）流水线寄存器流水线寄存器（组）（组）3.2 MIPS的基本流水

37、线76761931937777193193 流水线寄存器的构成流水线寄存器的构成 LMDLMD作用，在第作用，在第5 5拍写回拍写回, , 避免相关？避免相关？78781931934. MIPS流水线的操作对于流水线中的指令来说，在任一时刻，它对于流水线中的指令来说，在任一时刻，它仅在流水线中的某一段内执行操作。仅在流水线中的某一段内执行操作。因此，只要知道因此，只要知道某条指令在某条指令在每一流水段进每一流水段进行何种操作，就知道了行何种操作，就知道了它在它在整个流水线的操作。整个流水线的操作。( (表表3.1)3.1)给出了给出了MIPSMIPS流水线各段的操作。流水线各段的操作。 3.2

38、 MIPS的基本流水线7979193193流水段流水段表3.1 MIPS流水线的每个流水段的操作任何指令类型任何指令类型ALU 指令指令Load/Store 指令指令分支指令分支指令IFIDEXIF/ID.IR MemPCIF/ID.NPC,PC (if EX/MEM.cond EX/MEM.ALUout else PC+4);ID/EX.A RegsIF/ID.IR6.10; ID/EX.B RegsIF/ID.IR11.15;ID/EX.NPC IF/ID.NPC; ID/EX.IR IF/ID.IR;ID/EX.Imm (IR16)16#IR16.31;EX/MEM.IR ID/EX.I

39、R; EX/MEM.ALUOutput ID/EX.A op ID/EX.B 或EX/MEM.ALUOutput ID/EX.A op ID/EX.Imm;EX/MEM.cond 0;EX/MEM.IR ID/EX.IR; EX/MEM.ALUOutput ID/EX.A + ID/EX.Imm;EX/MEM.ALUOutput ID/EX.NPC + ID/EX.Imm;EX/MEM.cond (ID/EX.A op 0);8080193193流水段流水段任何指令类型任何指令类型ALU 指令指令Load/Store 指令指令分支指令分支指令MEMWBMEM/WB.IR EX/MEM.IR;

40、MEM/WB.ALUOutput EX/MEM.ALUOutput;MEM/WB.IR EX/MEM.IR; MEM/WB.LMD MemEX/MEM.ALUOutput;或MemEX/MEM.ALUOutput EX/MEM.B;RegsMEM/WB.IR16.20 MEM/WB.ALUOutput;或RegsMEM/WB.IR11.15 MEM/WB.ALUOutput;I?RRegsMEM/WB.IR11.15 MEM/WB.LMD;MIPS流水线的每个流水段的操作81811931935MIPS流水线的控制主要是确定如何主要是确定如何控制那四个多路选择器控制那四个多路选择器。828219

41、31933.2.3 流水线性能分析吞吐率吞吐率是指单位时间内流水线所完成的任是指单位时间内流水线所完成的任务数或输出结果的数量。务数或输出结果的数量。1. 吞吐率(1) (1) 最大吞吐率最大吞吐率TPTPmaxmax 最大吞吐率最大吞吐率是指流水线在连续流动达到是指流水线在连续流动达到稳定稳定状态后所得到的吞吐率。状态后所得到的吞吐率。 若流水线各段的时间相等，均为若流水线各段的时间相等，均为t t0 0 ， 则：则： TPmax 1 /t0MIPS的基本流水线8383193193 若流水线各段的时间不等，则：若流水线各段的时间不等，则： 最大吞吐率取决于流水线中最慢的一段所最大吞吐率取决于

42、流水线中最慢的一段所 需的时间，这段就成了流水线的瓶颈。需的时间，这段就成了流水线的瓶颈。 消除瓶颈的方法消除瓶颈的方法l 细分瓶颈段细分瓶颈段 l 重复设置瓶颈段重复设置瓶颈段1 1maxmaxt ti i TPmax 3.2 MIPS的基本流水线8484193193白色表示空闲白色表示空闲8585193193重复设置瓶颈段重复设置瓶颈段( (时时- -空图举例空图举例) )8686193193 第一种情况：各段时间第一种情况：各段时间相等相等（设为（设为t t0 0） 假设流水线由假设流水线由 m m 段组成，完成段组成，完成 n n 个任务。个任务。l 时空图时空图l 完成完成 n n

43、个任务所需的时间个任务所需的时间 T T流水流水m mt t0 0( (n n1)1)t t0 0 ( (说明说明) )(2) (2) 实际吞吐率实际吞吐率TPTP 流水线的实际吞吐率小于最大吞吐率。流水线的实际吞吐率小于最大吞吐率。3.2 MIPS的基本流水线8787193193通过时间通过时间8888193193完成完成 n n 个任务所需的时间个任务所需的时间8989193193l 实际吞吐率实际吞吐率TP TP T T流水流水n nm mt t0 0( (n n) )t t0 0n n(1(1 ) )t t0 0 m m1 11 1TPTPmaxmaxn n 1 1n nm m1 1T

44、P TP TPTPmaxmax当当n n m m 时，时，TP TP TPTPmaxmax 第二种情况：各段时间第二种情况：各段时间不等不等l 时空图时空图3.2 MIPS的基本流水线90901931933.2 MIPS的基本流水线9191193193 l 完成完成 n n 个任务所需的时间个任务所需的时间 T T流水流水t ti i( (n n1)1)t tj j t tj jmaxmaxt ti i l 实际吞吐率实际吞吐率TP TP t ti i( (n n1)1)t tj jm mi=1i=1n ni=1i=1m m3.2 MIPS的基本流水线9292193193加速比加速比是指流水线

45、的速度与等功能非流水是指流水线的速度与等功能非流水线的速度之比。线的速度之比。2. 加速比S S ST T非流水非流水T T流水流水（其中（其中T T流水流水和和T T非流水非流水分别为按流水和按非流水分别为按流水和按非流水方式处理方式处理 n n 个任务所需的时间）个任务所需的时间） 若流水线为若流水线为 m m 段，且各段时间相等，均段，且各段时间相等，均为为t t0 0 ，则：，则： T T非流水非流水n mn mt t0 0 T T流水流水m mt t0 0( (n n1)1)t t0 0 3.2 MIPS的基本流水线93931931933.2 MIPS的基本流水线9494193193

46、可以看出：可以看出：当当n n m m 时，时，S S m m想一想：想一想：m m 越大越好？单周期指令？越大越好？单周期指令？效率效率是指流水线的设备是指流水线的设备( (空间空间) )利用率利用率(utility)(utility)。(1) (1) 由于流水线有由于流水线有通过时间和排空时间通过时间和排空时间，所以，所以 流水线的各段并不是一直满负荷地工作。流水线的各段并不是一直满负荷地工作。 故：故：E E 1 1S S T T非流水非流水T T流水流水nmnmt t0 0m mt t0 0( (n n1 1) )t t0 0mnmnm mn n1 1m mn n1 1 m m1 1

47、3效率 EMIPS的基本流水线9595193193MIPS的基本流水线9696193193(2) (2) 若各段时间相等，则各段的效率若各段时间相等，则各段的效率e ei i相等，即相等，即 e e1 1e e2 2 e e3 3 e em mn nt t0 0T T流水流水 ( (解释解释) ) 整个流水线的效率为整个流水线的效率为: :当当 n n m m 时，时，E E 1 1E E n nt t0 0T T流水流水n nm mn n1 11n n1 m1(3) (3) 从时空图上看，效率实际上就是从时空图上看，效率实际上就是 n n 个任务所个任务所占的时空区与占的时空区与 m m 个

48、段总的时空区个段总的时空区之比，即：之比，即： n n 个任务占用的时空区个任务占用的时空区E E ( (解释解释) ) m m 个段个段总的总的时空区时空区3.2 MIPS的基本流水线97971931939898193193(4) (4) 提高流水线效率所采取的措施对于提高提高流水线效率所采取的措施对于提高 吞吐率也有好处。吞吐率也有好处。TP=E/TP=E/t t0 04流水线性能分析举例 P62 先加再乘例例3.13.1 在在静态流水线静态流水线上计算上计算 A Ai iB Bi i ， 求：吞吐率，加速比，效率。求：吞吐率，加速比，效率。4 4i i=1=13.2 MIPS的基本流水线

49、99991931933.2 MIPS的基本流水线3 3次加法，次加法，4 4次乘法。非流水：次乘法。非流水：3 36+46+44=344=34100100193193解解：( (1) 1) 确定适合于流水处理的确定适合于流水处理的计算过程计算过程(2) (2) 画时空图画时空图 (3) (3) 计算性能计算性能 吞吐率吞吐率 TPTP7 7(20(20t t) ) 加速比加速比 S S(34(34t t) )(20(20t t) )1.71.7 效率效率 E E(4(44 43 36)6)(8(820)20)0.210.213.2 MIPS的基本流水线101101193193102102193

50、1931031031931933.2 MIPS的基本流水线nTPT流水104104193193可以看出，在求解此问题时，该流水线的效率可以看出，在求解此问题时，该流水线的效率不高。不高。( (原因原因) )动态流水线的时空图动态流水线的时空图 举例举例 3.2 MIPS的基本流水线105105193193举例举例 : : 这样行不行？正确答案这样行不行？正确答案3.2 MIPS基本流水线106106193193例例3.23.2 假设前面假设前面MIPSMIPS非流水线实现的时钟周期时为非流水线实现的时钟周期时为10ns10ns，ALUALU和分支指令需要和分支指令需要4 4个时钟周期，访问存个

51、时钟周期，访问存储器指令需储器指令需5 5个时钟周期，上述指令在程序中出现个时钟周期，上述指令在程序中出现的相对频率分别是：的相对频率分别是：40%40%、20%20%和和40%40%。在基本的。在基本的MIPSMIPS流水线中，假设由于时钟扭曲和寄存器建立流水线中，假设由于时钟扭曲和寄存器建立延迟等原因，流水线要在其时钟周期时间上附加延迟等原因，流水线要在其时钟周期时间上附加1ns1ns的额外开销。现忽略任何其他延迟因素的影响，的额外开销。现忽略任何其他延迟因素的影响，请问：相对于非流水实现而言，基本的请问：相对于非流水实现而言，基本的MIPSMIPS流水流水线执行指令的加速比是多少？线执行

52、指令的加速比是多少？3.2 MIPS的基本流水线107107193193解：解：当非流水执行指令时，指令的平均执行时当非流水执行指令时，指令的平均执行时 间为间为 TPITPI非流水非流水 = 10ns= 10ns(40%+20%)(40%+20%)4 440%40%5)5) = 10ns = 10ns4.4 = 44ns4.4 = 44ns 在流水实现中，指令执行的平均时间在流水实现中，指令执行的平均时间 是最慢一段的执行时间加上额外开销，即是最慢一段的执行时间加上额外开销，即 TPITPI流水流水 = 10ns+1ns = 11ns= 10ns+1ns = 11ns 所以基本的所以基本的M

53、IPSMIPS流水线执行指令的加速比为流水线执行指令的加速比为S S = =TPITPI非流水非流水TPITPI流水流水44ns44ns11ns11ns= = 4= 43.2 MIPS的基本流水线108108193193例例3.3 (bottleneck)3.3 (bottleneck) 假设在假设在MIPSMIPS的非流水实现和基本流水线中，的非流水实现和基本流水线中，5 5个个功能单元的时间为：功能单元的时间为：1010，8 8，1010，1010，7 7（nsns），流水），流水额外开销为：额外开销为：1ns1ns，求求加速比加速比S S。解解：T T非流水非流水10108 810101

54、0107 745 (ns)45 (ns) T T流水流水 10101 111 (ns)11 (ns) S S 454511114.14.13.2 MIPS的基本流水线109109193193例例3.4 3.4 用一条用一条4 4段浮点加法器流水线计算段浮点加法器流水线计算8 8个浮点数的和个浮点数的和Z=A+B+C+D+E+F+G+HZ=A+B+C+D+E+F+G+H，求流水线的吞吐率，加速比和效率。，求流水线的吞吐率，加速比和效率。TP=n/Tk=7/15t=0.47/t, S=T0/Tk=4TP=n/Tk=7/15t=0.47/t, S=T0/Tk=47t/15t=1.87, 7t/15t

55、=1.87, E=T0/(kE=T0/(kTk)=4Tk)=47t/(47t/(4 15T)=0.47 15T)=0.47周期周期12345678910 11 12 13 14 15规格化规格化1234567尾数加尾数加1234567对阶对阶1234567求阶差求阶差1234567加数加数A C E GA+BE+FX加数加数B D F HC+DG+HY结果结果A+BC+DE+FG+HXYZ1101101931935有关流水线性能的若干问题(1) (1) 流水线并不能减少流水线并不能减少( (而且一般是增加而且一般是增加) )单条指单条指 令的执行时间，但却能提高吞吐率。令的执行时间，但却能提高

56、吞吐率。(2) (2) 增加流水线的深度增加流水线的深度( (段数段数) )可以提高流水线的可以提高流水线的 性能。性能。(3) (3) 流水线的深度受限于流水线的延迟和流水线流水线的深度受限于流水线的延迟和流水线 的额外开销。的额外开销。(4) (4) 流水线的额外开销包括：流水线的额外开销包括： 流水寄存器的延迟流水寄存器的延迟( (建立时间和传输延迟建立时间和传输延迟) ) 时钟扭曲时钟扭曲3.2 MIPS的基本流水线111111193193(5) (5) 当时钟周期小到与额外开销相同时，流水已没意当时钟周期小到与额外开销相同时，流水已没意 义。因为这时在每一个时钟周期中已没有时间来义。

57、因为这时在每一个时钟周期中已没有时间来 做有用的工作。做有用的工作。(6) (6) 需用高速的锁存器来作为流水寄存器。需用高速的锁存器来作为流水寄存器。 EarleEarle锁存器锁存器(1965)(1965)的三个特点的三个特点: : 对时钟扭曲不太敏感（相对而言）对时钟扭曲不太敏感（相对而言） 其延迟为常数：其延迟为常数：2 2个门级延迟，避免了数据通个门级延迟，避免了数据通 过锁存器时的扭曲。过锁存器时的扭曲。3.2 MIPS的基本流水线112112193193(7) (7) 相关问题相关问题 如果流水线中的指令相互独立，则可以充分如果流水线中的指令相互独立，则可以充分 发挥流水线的性能

58、。但在实际中，指令间可能会发挥流水线的性能。但在实际中，指令间可能会 是相互依赖，这会降低流水线的性能。下一节介是相互依赖，这会降低流水线的性能。下一节介 绍如何解决相关问题。绍如何解决相关问题。 锁存器中可以进行两级逻辑运算而不增延迟时锁存器中可以进行两级逻辑运算而不增延迟时 间。这样每个流水段中的两级逻辑可以与锁存间。这样每个流水段中的两级逻辑可以与锁存 器重叠，从而能隐藏锁存器开销的绝大部分。器重叠，从而能隐藏锁存器开销的绝大部分。3.2 MIPS的基本流水线1131131931933.3流水线中的相关1相关的概念 流水线中的相关流水线中的相关是指相邻或相近的两条指是指相邻或相近的两条指

59、令因存在某种关联，后一条指令不能在原指定令因存在某种关联，后一条指令不能在原指定的时钟周期开始执行的时钟周期开始执行。 结构相关结构相关 当硬件资源满足不了同时重叠执行的指当硬件资源满足不了同时重叠执行的指 令的要求，而发生资源冲突时，就发生令的要求，而发生资源冲突时，就发生了结了结 构相关。构相关。2相关的分类第三章 流水线技术114114193193 数据相关数据相关 当一条指令需要用到前面某条指令的结当一条指令需要用到前面某条指令的结 果，从而不能重叠执行时，就发生了果，从而不能重叠执行时，就发生了数据相数据相 关关。 控制相关控制相关 当流水线遇到分支指令和其他能够改变当流水线遇到分支

60、指令和其他能够改变 PCPC值的指令时，就会发生值的指令时，就会发生控制相关控制相关。3几个问题 相关有可能会使流水线停顿。相关有可能会使流水线停顿。3.3 流水线中的相关115115193193在本章中，我们在本章中，我们约定：约定： 当一条指令被暂停时，暂停在其后发射（流出）的指令，但继续执行在其前发射的 指令。暂停期间，流水线不会取新指令。 消除相关的消除相关的基本方法：基本方法： 让流水线中的某些指令暂停，而让其它让流水线中的某些指令暂停，而让其它 指令继续执行。指令继续执行。3.3 流水线中的相关1161161931933.3.1 流水线中的结构相关2. 如果某种指令组合因资源冲突而