计算机组成与结构6利用流水线提高性能

1、2012,1,华东师范大学计算机科学技术系,6 利用流水线提高性能,2012,2,华东师范大学计算机科学技术系,6 利用流水线提高性能,6.1 流水线概述 6.2 流水线的数据通路 6.3 流水线中的控制 6.4 数据冒险与转发 6.5 数据冒险与阻塞 6.6 分支冒险 6.7 异常 6.8 提高性能 6.9 实例：pentium 4处理器的流水线,2012,3,华东师范大学计算机科学技术系,6 利用流水线提高性能,6.1 流水线概述,2012,4,华东师范大学计算机科学技术系,6.1 流水线概述,并行处理技术 早期的计算机基于冯诺伊曼的体系结构， 采用的是串行处理 计算机的各个操作只能串行地

2、完成，任一时刻只能进行一个操作,2012,5,华东师范大学计算机科学技术系,6.1 流水线概述,一、并行处理技术 并行性： 同时性：指两个以上事件在同一时刻发生 并发性：指两个以上事件在同一时间间隔 内发生 计算机的并行处理技术可贯穿于信息处理 的各个步骤和阶段 分三种形式： 时间并行 空间并行 时间并行空间并行,2012,6,华东师范大学计算机科学技术系,一、并行处理技术, 时间并行 时间重叠 让多个处理过程在时间上相互错开，轮流重叠地使用同一套硬件设备的各个部分，以赢得处理速度 时间并行性概念的实现方式就是采用流水处理部件,2012,7,华东师范大学计算机科学技术系,一、并行处理技术, 空

3、间并行 资源重复 在并行性概念中引入空间因素，以增加“数 量” 来大幅度提高计算机的处理速度 空间并行技术主要体现在多处理器系统和 多计算机系统,2012,8,华东师范大学计算机科学技术系,一、并行处理技术, 时间并行空间并行 时间重叠和资源重复的综合应用 既采用时间并行性又采用空间并行性 例：奔腾cpu采用超标量流水技术，在一 个机器周期中同时执行两条指令 具有时间并行性又具有空间并行性,2012,9,华东师范大学计算机科学技术系,6.1 流水线概述,流水线是一种可将多条指令的执行过程相互重叠的实现技巧。流水线技术是在计算机上实现时间并行性，提高处理器速度的一种非常经济的方法。 二、流水线工

4、作原理概述： 将任务分割为一系列子任务，使各子任务能在流水线的各个阶段并发地执行，即实现子任务级的并行操作。,2012,10,华东师范大学计算机科学技术系,二、流水线工作原理概述：,子任务的划分决定流水线性能的关键因素。,方法：将t任务划分为k个子任务 t = t1，t2，tk,要求：各子任务划分合理，处理时间相同，避 免空转 子任务任务数的划分取决于： 操作的效率 所期望的处理速度 成本价格等,关键： 每个子任务的处理时间一样 应取多少任务数,2012,11,华东师范大学计算机科学技术系,二、流水线工作原理概述：,效率： 子任务并行工作，提高了吞吐率 实际上整个任务处理的时间并没有缩短， 而

5、是因为各子任务并行工作，单位时间 内所完成的工作量就大大增加了。流水 线提高了整个系统的吞吐率。 子任务划分越细，流水线效率越高，但 硬件代价也越高,2012,12,华东师范大学计算机科学技术系,二、流水线工作原理概述：,1. 线性流水线 各子任务之间有一定的优先关系。若ij, 则必须在ti完成后，tj才开始工作，这种线性优先关系的流水线称为线性流水线。,时钟周期 i为执行si所需的时间，l为缓冲寄存器 的延时 maxilml 流水线时钟频率为： f1/,2012,13,华东师范大学计算机科学技术系,二、流水线工作原理概述：,2. 流水线加速比 当流水线任务饱满时，任务源源不断地输入流水线，不

6、论有多少级过程段，每隔一个时钟周期都能输出一个任务 从理论上说，一个具有k级过程段的流水线处理n个任务需要的时钟周期数为： tkk(n1),k个时钟周期用于处理第一个任务，流水线正常流动 后，剩下的n-1个任务，每个时钟周期就能完成一个。,而用非流水线的硬件来处理这n个任务，时间上只能串行进行,则所需时钟周期数为： tlnk,2012,14,华东师范大学计算机科学技术系,2. 流水线加速比,k级过程段的流水线处理n个任务需要的时钟周期数为： tkk(n1) 非流水线的硬件处理所需时钟周期数为： tlnk,流水线加速比 ck=tl/tk= n k /(k+(n-1)k,当nk时，ckk,理论上k

7、级线性流水线可提高k倍速度， 但实际上由于存在结构冒险、数据 冒险等，并达不到理想的值。,流水线所带来的性能提升是通过提高指令的吞吐率来实现 的，而不是通过减少单条指令的执行时间来实现。,2012,15,华东师范大学计算机科学技术系,二、流水线工作原理概述：,3. 流水线时空图 为了实现流水，首先把输入的任务(或过程)分割为一系列子任务，并使各子任务能在流水线的各个阶段并发地执行 当任务连续不断地输入流水线时，在流水线的输出端便连续不断地吐出执行结果，从而实现了子任务级的并行性,2012,16,华东师范大学计算机科学技术系,3. 流水线时空图,设指令执行的流水线过程段：,一条流水线由一系列串联

8、的过程段组成 各过程段之间设有高速缓冲寄存器，以暂时保存上一过 程段子任务处理的结果 在统一的时钟信号控制下，数据从一个过程段流向相邻 的过程段,例：一条指令的执行分为四个子过程段（si） 每个子过程段处理时间均为t 分析对比： 非流水线、流水线、超标量流水线执行5条指令所需 时间,2012,17,华东师范大学计算机科学技术系,3. 流水线时空图, 非流水线时空图,上一条指令的四个子过程全部被执行完毕后才能 开始下一条指令 每隔4个机器时钟周期才有一个输出结果 执行5条指令所需时间： t45=20t,时间t,2012,18,华东师范大学计算机科学技术系,3. 流水线时空图, 标量流水线时空图,

9、上一条指令与下一条指令的子过程在时间上可以 重叠执行 当流水线满载时，每一个时钟周期就可以输出一 个结果 执行5条指令所需时间： t4+(5-1)t=8t,与前者比较： 流水计算机在8个t时间中执行了5条指令 非流水线计算机在8个t时间中仅执行了2条指令,2012,19,华东师范大学计算机科学技术系,3. 流水线时空图, 超标量流水线时空图,所谓超标量流水是指它具有两条以上的指令流水线 下图中的超标量流水线中，流水线满载时，每一个 时钟周期可以执行2条指令 执行5条指令所需时间： t4+(5-2)/2=6t,wb,ex,id,if,空间s,i6,i5,时间t,1,2,3,4,5,6,7,8,i

10、2,i3,i4,i1,i7,i8,i9,i10,三者比较： 非流水线计算机在8个t时间中执行了2条指令 流水计算机在8个t时间中执行了5条指令 超标量流水线计算机在8个t时间中执行了10条指令,2012,20,华东师范大学计算机科学技术系,6.1 流水线概述,三、针对流水线结构的指令集设计 指令流水线指令级并行（ilp） 利用执行指令所需的操作之间的并行，实 现多条指令重叠执行的一种技术 目前，几乎所有的高性能计算机都采用了 指令流水线,2012,21,华东师范大学计算机科学技术系,三、针对流水线结构的指令集设计,开发方法： 依赖于硬件，动态地发现和开发指令级并行,可将指令流的处理过程划分为取

11、指令、译码、执行、写回等几个并行处理的过程段 例：intel的pentium系列 占市场主导地位 依赖于软件技术，在编译阶段静态地发现并行 例：intel的itanium系列 特定应用环境,2012,22,华东师范大学计算机科学技术系,三、针对流水线结构的指令集设计,针对流水线结构的指令集设计： mips指令集就是专为指令执行的流水线化 而设计的 特点： 所有的mips指令等长 简化了流水线的取指和译码阶段设计 ia-32指令长度为1-17字节，为适合流水线, 首先将指令转为简单的微操作，送入流水线处 理的实际上是微操作，而不是原始指令。,2012,23,华东师范大学计算机科学技术系,三、针对

12、流水线结构的指令集设计, mips指令格式简单，形式固定 简化了流水线的译码阶段设计， 同时可减少流水线级数 mips指令对内存的操作仅允许在存取操作中 计算有效地址可放在执行阶段进行 mips指令具有数据规整性，保证存取数据一次完成 传输数据可保证在一个流水线级中完成,2012,24,华东师范大学计算机科学技术系,6.1 流水线概述,四、流水线冒险 流水线中的主要问题 希望流水线充分发挥作用 关键：不断流 但实际情况通常会出现相关冲突，使流水 线发生断流，称为冒险 流水线cpi=理想流水线cpi+结构停顿+数据停顿+控制停顿 主要相关冲突： 资源相关结构冒险 数据相关数据冒险 控制相关控制冒

13、险,2012,25,华东师范大学计算机科学技术系,四、流水线冒险,1. 结构冒险 指多条指令进入流水线后在同一机器时钟周期内争用同一个功能部件所发生的冲突,结构冒险实例：两条指令同时访问内存发生 资源相关冲突,在时钟t4时： i1指令执行访存操作：读操作数 i4指令执行访存操作：读指令 若数据、指令放在同一存储器中（单端输出），则发生资源相关冲突（结构冒险）,五个子过程段：if： 取指 id： 指令译码、寄存器堆读取 ex： 指令执行(alu) mem：内存访问 wb： 结果写寄存器堆,解决冲突的办法： 在不改变程序正确执行的前提下，尽力开发并行度 延迟i4指令的执行，停顿一拍后再启动(引入气

14、泡) 增设一个存储器，将指令和数据分别放在两个存储 器中,2012,26,华东师范大学计算机科学技术系,四、流水线冒险,2. 数据冒险 在一个程序中，如果必须等前一条指令执行完毕后，才能执行后一条指令，那么这两条指令就是数据相关的。 在流水线计算机中，由于多条指令的重叠处理，当后继指令所需的操作数，刚好是前一指令的运算结果时，便发生数据相关冲突 可能存在数据冒险,是否存在相关取决于程序的性质，而一个给定的相关是否会引起数据冒险则取决于流水线的结构。,2012,27,华东师范大学计算机科学技术系,2. 数据冒险,数据相关实例 add $t1,$t2,$t3 ;($t2)+($t3)$t1 sub

15、 $t4,$t1,$t5 ;($t1)-($t5)$t4 and $t6,$t1,$t7 ;($t1)($t7)$t6,这一数据冒险将严重阻碍流水线，流水线阻塞（产生气泡）,解决冲突的办法： 通过编译优化，将相关指令和不相关指令恰当混合， 但很难得到令人满意的效果 采用定向传送技术（数据定向或数据旁路） 设置专用定向通路，将运算结果直接作为输入项，供 后继指令直接使用，而不必等待下一时钟周期，以尽 量减少延迟时间,2012,28,华东师范大学计算机科学技术系,2. 数据冒险,例1）两条指令间的数据转发 顺序执行： add $s0,$t0,$t1 sub $t2,$s0,$t3 不采取措施，su

16、b指令的id子过程必须延迟到 第6拍进行 采用数据定向传送通道 图6-5 sub指令执行可不断流。当add指令完成ex步 骤，运算结果将通过定向传送通道直接作为 sub指令的操作数。,2012,29,华东师范大学计算机科学技术系,2. 数据冒险,数据定向技术并不能完全解决流水线阻塞问题,但能尽量减少阻塞时间。 例2）顺序执行： lw $s0,20($t1) sub $t2,$s0,$t3 即使采用数据定向技术，但由于lw指令得到$s0的结果要等到第4拍（mem）结束，而理想状况sub指令的执行就在第4拍，所以，流水线仍然不得不阻塞一步。 图6-6 要获知是否发生阻塞，需相应的技术，后面讨论。,

17、2012,30,华东师范大学计算机科学技术系,2. 数据冒险,例3）重新排列代码以避免流水线阻塞 c语言： a=b+e c=b+f mips指令： i1: lw $t1,0($t0) i2: lw $t2,4($t0) i3: add $t3,$t1,$t2 i4: sw $t3,12($t0) i5: lw $t4,8($t0) i6: add $t5,$t1,$t4 i7: sw $t5,16($t0),内存,基址+0 +4 +8 +12 +16,例3）,i1: lw $t1,0($t0) i2: lw $t2,4($t0) i3: add $t3,$t1,$t2 i4: sw $t3,1

18、2($t0) i5: lw $t4,8($t0) i6: add $t5,$t1,$t4 i7: sw $t5,16($t0),不采取任何措施 需23个周期完成,i1 i2 i3 i4 i5 i6 i7,t1 t2 t3 t4 t5 t6 t7 t8 t9 t10 t12 t14 t16 t18 t20 t22,例3）,i1: lw $t1,0($t0) i2: lw $t2,4($t0) i3: add $t3,$t1,$t2 i4: sw $t3,12($t0) i5: lw $t4,8($t0) i6: add $t5,$t1,$t4 i7: sw $t5,16($t0), 采取数据定向

19、技术 只需13个周期完成，但不能完全解决阻塞问题。,i1 i2 i3 i4 i5 i6 i7,t1 t2 t3 t4 t5 t6 t7 t8 t9 t10 t12 t14 t16 t18,例3）,i1: lw $t1,0($t0) i2: lw $t2,4($t0) i3：lw $t4,8($t0) i4: add $t3,$t1,$t2 i5: add $t5,$t1,$t4 i6: sw $t3,12($t0) i7: sw $t5,16($t0), 对程序重新排序，调整 原指令序列，现只需 11个周期完成，又提前 2个周期。,i1 i2 i3 i4 i5 i6 i7,t1 t2 t3 t

20、4 t5 t6 t7 t8 t9 t10 t12 t14 t16 t18,2012,34,华东师范大学计算机科学技术系,2. 数据冒险,由此引出mips结构设计的另一特点： 每条mips指令最多输出一个结果，并在接近流水线的末端完成对这个结果的回写。 按序完成 若每条指令的转发结果多于一个，或采用较早写回策略的话，实现数据转发将更困难。,2012,35,华东师范大学计算机科学技术系,四、流水线冒险,3. 控制冒险 控制相关冲突是由分支指令（包括中断）引起的。当执行分支指令时，依据分支条件产生结果，可能为顺序执行下一条指令；也可能转移到新的目标地址执行指令，原流水线前期操作的内容全部作废，从而使

21、流水线发生断流。 原因： 判断结果在最后阶段才能产生,2012,36,华东师范大学计算机科学技术系,3. 控制冒险,解决冲突的方法： 常用以下分支处理技术： 延迟转移法（编译优化） 基本思想是“先执行再转移”，即发生转移取时并不排空指令流水线，而是让紧跟在分支指令之后已进入流水线的少数几条指令继续完成。 如果这些指令是与分支结果无关的有用指令，那么延迟损失时间片正好得到了有效的利用。,2012,37,华东师范大学计算机科学技术系,3. 控制冒险, 增加硬件电路，缩短分支延迟 ） 默认分支不发生 默认执行顺序指令，分支发生时清除 已执行指令。 ）将分支判断提前到id阶段完成，缩短 分支的延迟,2

22、012,38,华东师范大学计算机科学技术系,3. 控制冒险, 分支预测法 保存每个分支执行情况的历史记录，根据近期执行的情况，来预测将来的行为，用硬件方法来实现分支预测。 一旦预测错误，流水线控制机制必须保证错误执行的指令失效，重新进入正确的分支。 mips采用延迟分支法，分支指令后的下一条指令总是被执行，分支则发生在这条指令执行完后。 对程序员透明，由汇编器完成,2012,39,华东师范大学计算机科学技术系,四、流水线冒险,小结： 流水线增加了同时执行的指令的数目（并行性），提高了处理器的吞吐率，但并没有减少单条指令的执行时间或时延； 理论上k级线性流水线可提高k倍速度，但较长的流水线会恶化

23、预测的性能，增加错误预测的代价； 流水线技术对程序员透明； 流水线设计者必须解决：结构冒险、数据冒险和控制冒险问题，以提高计算机的性能。,2012,40,华东师范大学计算机科学技术系,四、流水线冒险,例4）下列指令序列在5级流水线执行中是否会 发生阻塞？通过数据定向技术能否解决冒 险问题？ addi $t1,$t0,#1 addi $t2,$t0,#2 addi $t3,$t0,#3 addi $t3,$t0,#4 addi $t5,$t0,#5 程序执行时，数据不会发生冲突冒险，所以流水线不会阻塞,2012,41,华东师范大学计算机科学技术系,例4）,2. lw $t0,0($t0) add

24、i $t2,$t0,#2,lw add,程序执行时，$t0数据产生冲突冒险，流水线发生阻塞。 即使采用数据定向技术也不能完全解决阻塞问题，但add指令执行可提前1个时钟周期。,2012,42,华东师范大学计算机科学技术系,例4）,3. add $t1,$t0,$t0 addi $t2,$t0,#5 addi $t4,$t1,#5,add addi addi,程序执行时，$t1数据相关，流水线有可能发生阻塞。 采用数据定向技术能完全解决阻塞问题，使流水线不断流。,2012,43,华东师范大学计算机科学技术系,6 利用流水线提高性能,6.1 流水线概述 6.2 流水线的数据通路,2012,44,华

25、东师范大学计算机科学技术系,6.2 流水线的数据通路,级单时钟周期流水线的数据通路 p248图6-9 分析： 一般执行步骤：从左到右 例外（从右到左）： 写回数据到寄存器堆 引起结构冒险 选择pc的值（后继地址） 引起控制冒险,2012,45,华东师范大学计算机科学技术系,6.2 流水线的数据通路,解决方法： 将子过程段分为两部分： 例：寄存器堆读（前半周期）和寄存器堆写 （后半周期） 图6-10 增加子过程段缓冲寄存器，存储后级需要使 用的数据 图6-11,2012,46,华东师范大学计算机科学技术系,6.2 流水线的数据通路,一、流水线工作原理 例5）lw指令的流水执行过程 取指令 图6-

26、12 m（pc） if/id流水线缓冲寄存器（32位） 相当于读出指令送ir pc+4 if/id流水线缓冲寄存器（32位） pc指向下一条指令地址 if/id流水线缓冲寄存器共64位,2012,47,华东师范大学计算机科学技术系,例5）,2. 指令译码与读取寄存器堆 图6-12 读rs寄存器值id/ex流水线缓冲寄存器（32位） 读rt寄存器值id/ex流水线缓冲寄存器（32位） 指令的16位立即数符号扩展后id/ex流水线缓冲寄存器（32位） if/id缓冲寄存器中的pc增值id/ex流水线缓冲寄存器（32位） id/ex流水线缓冲寄存器共128位,2012,48,华东师范大学计算机科学技

27、术系,例5）,3. 指令执行或地址计算 图6-13 id/ex流水线缓冲寄存器中的rt内容ex/mem流水线缓冲寄存器（32位） 有效地址运算结果（或指令操作运算结果）+标志位ex/mem流水线缓冲寄存器（32+1位） pc分支目标地址的计算结果ex/mem流水线缓冲寄存器（32位） ex/mem流水线缓冲寄存器共97位,2012,49,华东师范大学计算机科学技术系,例5）,4. 内存访问 图6-14 数据存储器读出内容mem/wb流水线缓冲寄存器（32位） 指令操作运算结果mem/wb流水线缓冲寄存器（32位） mem/wb流水线缓冲寄存器共64位 5. 写回 图6-14 从mem/wb流水

28、线缓冲寄存器中读出数据写入寄存器堆。,2012,50,华东师范大学计算机科学技术系,一、流水线工作原理,例6）sw指令的流水执行过程 取指令 图6-12 同lw指令 2. 指令译码与读寄存器堆 图6-12 读rs寄存器值id/ex流水线缓冲寄存器（32位） 读rt寄存器值id/ex流水线缓冲寄存器（32位） 指令的16位立即数符号扩展后id/ex流水线缓冲寄存器（32位） if/id缓冲寄存器中的pc增值id/ex流水线缓冲寄存器（32位）,2012,51,华东师范大学计算机科学技术系,例6）,3. 指令执行或地址计算 图6-15 id/ex流水线缓冲寄存器中的rt内容ex/mem流水线缓冲寄

29、存器（32位） 数据 有效地址运算结果（或指令操作运算结果）+标志位ex/mem流水线缓冲寄存器（32+1位） 地址 pc分支目标地址的计算结果ex/mem流水线缓冲寄存器（32位）,2012,52,华东师范大学计算机科学技术系,例6）,4. 内存访问 图6-16 读取ex/mem缓冲器保存的数据和有效地址，写入数据存储器 数据存储器读出内容mem/wb流水线缓冲寄存器（32位） 有效地址运算结果（或指令操作运算结果） mem/wb流水线缓冲寄存器（32位） 5. 写回 图6-16 空操作,2012,53,华东师范大学计算机科学技术系,一、流水线工作原理,重要特性： 增加流水线缓冲寄存器，保证

30、上一级向下一 级传递信息的正确性； 数据通路中的每一个逻辑元件都只能在流水 线的单级中使用，否则将产生结构冒险。,2012,54,华东师范大学计算机科学技术系,一、流水线工作原理,例5 lw指令流水线中的bug： t5节拍产生回写数据，但写入寄存器堆的 地址此时已发生改变（因已多次取指）。 修改措施： 将if/id中的rt内容（包括rd,算术运算指 令需要）逐级通过流水线缓冲器传递并保存， 直至写入寄存器堆时使用 p256图6-17,2012,55,华东师范大学计算机科学技术系,6.2 流水线的数据通路,二、用图形的方式表示流水线 1. 多时钟周期的流水线图 图6-19：描述每步所使用的实际资

31、源 图6-20：也称流水线时空图，描述每个步 骤的名称 简单但忽略细节 2. 单时钟周期的流水线图 图6-21 描述同一时钟节拍内各条指令使用各个逻辑部件的情况,2012,56,华东师范大学计算机科学技术系,6 利用流水线提高性能,6.1 流水线概述 6.2 流水线的数据通路 6.3 流水线中的控制,2012,57,华东师范大学计算机科学技术系,6.3 流水线中的控制,在基于流水线的简单数据通路中加入控制电路 1. 加入所需的操作控制信号 图6-22 说明： pc及流水线缓冲寄存器利用流水线时钟信 号打入（每个节拍打入一次），所以不需 要另外的控制信号。 6位的指令功能码不必单独保存，同id/

32、ex 中符号扩展后的立即数的低6位。,2012,58,华东师范大学计算机科学技术系,6.3 流水线中的控制,2. 在每个流水线步骤中设定相应的操作控制信 号 取指令：读指令存储器 pcsrc：选择pc写入内容 写pc 写if/id 指令译码/读取寄存器堆：读寄存器堆 写id/ex 以上步骤在每个时钟周期内执行，不需设置控 制（不考虑冒险等问题）,2012,59,华东师范大学计算机科学技术系,2. 在每个流水线步骤中设定相应的操作控制信号, 指令执行/有效地址计算： regdst：选择结果寄存器 aluop： 确定alu操作 alusrc：选择第2操作数（rt/或符号扩展 后的立即数） 写ex/

33、mem 内存访问： branch memread 由指令操作码决定 memwrite 写mem/wb,2012,60,华东师范大学计算机科学技术系,2. 在每个流水线步骤中设定相应的操作控制信号, 写回： memtoreg：选择写回寄存器堆结果（运算 结果/数据存储器读出内容） regwrite：寄存器堆写入信号 操作控制信号设计同p201图5-18 区别：加入流水线子过程段控制信号 流水线t3，t4，t5阶段操作控制信号：图6-25,2012,61,华东师范大学计算机科学技术系,6.3 流水线中的控制,实施方法： 简单的方法是扩展流水线缓冲寄存器内容, 使之包含这些操作控制信号 图6-26

34、后级使用的操作控制信号要逐级通过流水线缓 冲寄存器传送 带有控制的流水线数据通路 图6-27 if/id： 64位 id/ex： 147位 ex/mem：107位 mem/wb：71位,2012,62,华东师范大学计算机科学技术系,6 利用流水线提高性能,6.1 流水线概述 6.2 流水线的数据通路 6.3 流水线中的控制 6.4 数据冒险与转发,2012,63,华东师范大学计算机科学技术系,6.4 数据冒险与转发,数据冒险是影响流水线性能的主要障碍 分析下列程序： sub $2,$1,$3 and $12,$2,$5 or $13,$6,$2 add $14,$2,$2 sw $15,100

35、($2) sub-and,sub-or,sub-add,sub-sw存在数据相关性,2012,64,华东师范大学计算机科学技术系,6.4 数据冒险与转发,多时钟周期的流水线图： 图6-28 and,or指令由于数据冒险，产生错误结果； add,sw指令无数据冒险，执行结果正确。 增加数据定向技术，sub指令在ex段产生运算 结果直接作为and指令ex段的执行输入，则流 水线不会产生气泡。,2012,65,华东师范大学计算机科学技术系,6.4 数据冒险与转发, 描述冒险关系 1a: ex/mem.registerrd=id/ex.registerrs 1b: ex/mem.registerrd=

36、id/ex.registerrt 2a: mem/wb.registerrd=id/ex.registerrs 2b: mem/b.registerrd=id/ex.registerrt,2012,66,华东师范大学计算机科学技术系,6.4 数据冒险与转发,相关性检测： sub-and是1a类冒险 ex/mem.registerrd=id/ex.registerrs=$2 sub-or是2b类冒险 mem/wb.registerrd=id/ex.registerrt=$2 sub-add和sub-sw不存在数据冒险,2012,67,华东师范大学计算机科学技术系,6.4 数据冒险与转发,数据转发

37、需受到控制： 仅当回写执行时转发： 检测ex、mem阶段的流水线缓冲寄存器wb域的regwrite是否有效。 当rd=$0，mips规定操作数必为0 增加冒险控制条件 将ex/mem.registerrd0加入第一种冒险条件 mem/wb.registerrd0加入第二种冒险条件 相关性可能来自指令流水线的多个阶段（图6-29），可在alu输入端增加mux和正确的控制策略 图6-30,（$0）= 0,2012,68,华东师范大学计算机科学技术系,6.4 数据冒险与转发,检测冒险的条件以及解决冒险的控制信号： p266图6-30 mux控制信号含义 图6-31 1.ex冒险： if(ex/mem

38、.regwrite and(ex/mem.registerrd0） and(ex/mem.registerrd=id/ex.registerrs)forwarda=10 if(ex/mem.regwrite and(ex/mem.registerrd0） and(ex/mem.registerrd=id/ex.registerrt)forwardb=10,2012,69,华东师范大学计算机科学技术系,6.4 数据冒险与转发,2.mem冒险： if(mem/wb.regwrite and(mem/wb.registerrd0） and(mem/wb.registerrd=id/ex.regist

39、errs)forwarda=01 if(mem/wb.regwrite and(mem/wb.registerrd0） and(mem/wb.registerrd=id/ex.registerrt)forwardb=01,2012,70,华东师范大学计算机科学技术系,6.4 数据冒险与转发,3. 复杂的潜在数据冒险 例：add $1,$1,$2 add $1,$1,$3 add $1,$1,$4 一系列连续的指令读写同一个寄存器，mem 阶段中的结果更新，其更新的结果是由mem步骤 转发得到的，所以修改mem冒险的控制策略： if(mem/wb.regwrite and(mem/wb.regi

40、sterrd0） and(ex/mem.registerrdid/ex.registerrs) and(mem/wb.registerrd=id/ex.registerrs)forwarda=01 if(mem/wb.regwrite and(mem/wb.registerrd0） and(ex/mem.registerrdid/ex.registerrt) and(mem/wb.registerrd=id/ex.registerrt)forwardb=01,2012,71,华东师范大学计算机科学技术系,6.4 数据冒险与转发,图6-32：支持数据转发的硬件电路（不具有完 整的数据通路） 图6

41、-33：增加mux，以选择符号扩展后的立即数,2012,72,华东师范大学计算机科学技术系,6 利用流水线提高性能,6.1 流水线概述 6.2 流水线的数据通路 6.3 流水线中的控制 6.4 数据冒险与转发 6.5 数据冒险与阻塞,2012,73,华东师范大学计算机科学技术系,6.5 数据冒险与阻塞,数据定向技术并不能完全解决流水线断流问题,一旦发生，必须有相应的机制阻塞流水线。 例：图6-34 lw-and 数据相关 lw: 在cc4从内存读出数据，cc5送$2 and: 在cc4需要$2操作数执行，阻塞一拍 因此为解决数据冒险问题，除转发控制外，还需一个冒险检测单元。,2012,74,华

42、东师范大学计算机科学技术系,6.5 数据冒险与阻塞,冒险检测单元： 在id阶段检测lw指令，控制条件： if(id/ex.memread and (id/ex.registerrd= if/id.registerrs) or (id/ex.registerrd = if/id.registerrt) stall the pipeline,lw是唯一一条读数据存储器指令，因此用memread判断是否lw指令。,检测lw的目的寄存器与下一条指令的源寄存器是否相同,如果条件成立，下条指令(and)将阻塞一个 时钟周期。 若没有采用数据定向机制，则将阻塞二个 时钟周期。,2012,75,华东师范大学计

43、算机科学技术系,6.5 数据冒险与阻塞,阻塞： id和if阶段一起被阻塞（防止预取指令丢失） 方法： 保持pc寄存器和if/id流水线缓冲寄存器不变。,读同一条指令,相当于ir不变,阻塞就相当于执行nop指令，通过将9个操作控制信号清0实现。 图6-35,2012,76,华东师范大学计算机科学技术系,6.5 数据冒险与阻塞,图6-36：加入冒险检测单元和转发单元 lw指令冒险条件满足，冒险检测单元就阻塞并 清除所有的控制字段。 保持pc和if/id流水线缓冲寄存器不变 写信号pcwrite和if/idwrite无效 流水线执行nop指令 增加mux选择0送id/ex.wb,id/ex.m,id

44、/ex.ex （也可只将regwrite和memwrite置0）,2012,77,华东师范大学计算机科学技术系,6 利用流水线提高性能,6.1 流水线概述 6.2 流水线的数据通路 6.3 流水线中的控制 6.4 数据冒险与转发 6.5 数据冒险与阻塞 6.6 分支冒险,2012,78,华东师范大学计算机科学技术系,6.6 分支冒险,分支冒险也称控制冒险 例：图6-37分支指令对流水线的影响 现象分析： beq指令决定是否分支发生在mem阶段（cc4），当产生比较结果标志后在第4个时钟周期转移地址送pc。若不加干涉的话，后续三条指令在程序转移之前已进入流水线执行。 发生控制相关错误,2012,

45、79,华东师范大学计算机科学技术系,6.6 分支冒险,解决方案： 一、假定分支不发生 默认分支不发生，继续执行顺序的指令流。 若分支发生，则丢弃已执行的指令，转分支目 标地址执行。 效率：设分支不发生的可能性为50%，丢弃指令 的代价很少的话，这种方法可将控制冒 险的代价减半。,2012,80,华东师范大学计算机科学技术系,一、假定分支不发生,丢弃指令的方法： 同前述lw指令，将操作控制信号置0。但所 不同的是：必须将流水线if、id、ex阶段的指 令操作控制码都清除掉。前者只需将id阶段的 操作控制码清0。,2012,81,华东师范大学计算机科学技术系,解决方案：,二、减少分支的延迟 尽可能

46、早的完成分支判断，降低执行分支的 代价。 提前决策需提前完成两个操作： 计算分支的目标地址 判断分支的跳转条件,2012,82,华东师范大学计算机科学技术系,二、减少分支的延迟,1.计算分支的目标地址 图6-27 在id阶段已得到pc+4和if/id流水线缓冲寄 存器中的指令立即数。 可将分支地址加法器从ex阶段移到id阶段。 这种设计将使id阶段的操作：立即数符号 扩展、左移和分支地址加法时间更加紧凑。,2012,83,华东师范大学计算机科学技术系,二、减少分支的延迟,2.判断分支的跳转条件 图6-27 需增加电路，并提供数据旁路，以提早产 生判断结果。 例：要判断是否相等，可在id阶段将读

47、取的寄 存器值按位异或，产生判断结果。,2012,84,华东师范大学计算机科学技术系,2.判断分支的跳转条件,主要困难： 首先完成指令译码，以决定是否要将数据旁路送给比较电路进行比较判断。数据旁路原由alu相关电路负责，这里须在id阶段另外设计数据旁路电路。id阶段工作比较繁重，可能增加流水线子过程段的时间。 由于数据比较工作提前到id阶段，当指令序列存在数据冒险时，可能引发流水线停顿。 例：分支指令的前一条指令是alu指令，且alu 的运算结果用于分支指令的比较操作，而 alu指令的ex阶段发生在分支指令的id阶段 之后，流水线断流。,2012,85,华东师范大学计算机科学技术系,2.判断分

48、支的跳转条件,将分支指令的执行过程提前到id阶段对流水线 性能还是有一定的改善。在分支跳转时只要清 除取指令的那条指令。 图6-37 为了在if阶段清除一条指令，加入if.flush控 制线，清空if/id流水线缓冲寄存器（相当于执 行nop指令） 图6-38,2012,86,华东师范大学计算机科学技术系,6.6 分支冒险,例6）流水线分支 p273 图6-38 beq指令在id阶段产生分支结果 pc+4、28加法器，运算结果72pc $1，$3数据旁路送比较器，相等则if.flush信号有 效，清if/id流水线缓冲寄存器内容（插入一条nop 指令） pc=72，取转移目标地址指令lw,20

49、12,87,华东师范大学计算机科学技术系,6.6 分支冒险,三、动态分支预测 转移预测可在编译阶段静态完成，也可由 硬件在执行阶段动态完成。 简单的分支预测: 假定分支不发生 预测错误，排空流水线 对于较深的流水线分支开销大 多发射处理器分支开销大 静态预测 简单的分支技术会对性能造成过多的浪费,2012,88,华东师范大学计算机科学技术系,三、动态分支预测,动态分支预测 在运行时根据运行时的信息，并通过分析 转移的历史表现来进行转移预测。 部件：分支预测缓存（分支历史表） 一个用分支指令地址的低位寻址的 小型存储器，记录了分支最近是否执行。 可有以下两种形式： 专用cache，取指时由指令地

50、址访问 指令cache的一部分，随指令一起读出,2012,89,华东师范大学计算机科学技术系,三、动态分支预测,策略：上次执行该指令，分支是否发生？ 是，转移取 若预测错误，不正确的指令被删除，预 测位取反，返回原处继续执行正确指令。 缺点：即使该指令执行时，分支多次发生，也 有可能有不发生的时候预测错误,2012,90,华东师范大学计算机科学技术系,三、动态分支预测,例7）循环与预测 设一循环分支执行时，发生9次分支转移，该分支的预测位（1位）保存在预测缓存中，问这种分支预测的正确率是多少？ 解： 第一次预测错误，因上次循环退出时，分支 未发生 最后一次预测错误，因循环时分支已发生9次 二次

51、错误预测，8次正确预测，正确率80%,2012,91,华东师范大学计算机科学技术系,三、动态分支预测,1. 预测器技术： 1bit预测器：仅考虑局部信息 局部2bit预测器：仅考虑局部信息 2位预测位方案： 图6-39 采用两位计数器，预测正确时递增，错误时递减，中心点（10）作为判断是否跳转的分水岭。,2012,92,华东师范大学计算机科学技术系,三、动态分支预测, 相关预测器：还考虑其他转移行为的影响 使用分支指令的局部行为特性和最近执行的分支的全局信息进行预测判断。 tourenament预测器：整体局部自适应预测器 使用多个预测器 例：一个基于全局信息 一个基于局部信息 2005年：使

52、用30k bit的tounament预测器 例：power 5、pentium 4,2012,93,华东师范大学计算机科学技术系,三、动态分支预测, 锦标赛预测 使用多种分支预测器，并记录它们谁产生的结果最好。预测时选择某个行为最好的预测器的预测结果。 选择子可选1位或2位机制。 先进的预测器：alpha 21264中的预测器 复杂分支预测再加上推理和动态执行共同保证了指令执行的并行化。,2012,94,华东师范大学计算机科学技术系,三、动态分支预测,2. 分支延时 分支延时时间片调度的方法： 图6-40 用来自于分支指令前的指令填充 用跳转目标指令填充 用顺序指令填充 延迟分支调度的约束：

53、可调度指令的限制（与转移无关指令） 编译时对分支发生与否的预测能力,2012,95,华东师范大学计算机科学技术系,三、动态分支预测,mips采用延迟分支法，分支指令后的下一 条指令总是被执行，分支则发生在这条指令执 行完后。 因为分支跳转将计算目标地址，需消耗一 个时钟周期，所以采用延迟分支法是一种消除 这种开销的方法。 另一种方法是采用分支目标缓存，记录分 支目标地址或目标指令。,2012,96,华东师范大学计算机科学技术系,6.6 分支冒险,四、比较几种控制方案的性能 使用specint2000混合指令程序： 25%取数（1%取字节+24%取字） 10%存数（1%存字节+9%存字） 11%

54、分支（6%beq，5%bne） 2%跳转（1%jal+1%jr） 52%alu,2012,97,华东师范大学计算机科学技术系,四、比较几种控制方案的性能,单周期处理器执行一条指令的时间 设： 访存时间：200ps alu操作时间：100ps 寄存器读写延时：50ps 单周期数据通路所需时间： if+id+ex+mem+wb 200+50+100+200+50=600ps,2012,98,华东师范大学计算机科学技术系,四、比较几种控制方案的性能,2. 多周期处理器的cpi 各类指令所需cpu周期数： 图5-30 取数：5 存数：4 alu：4 分支：3 跳转：3 cpi= （指令数i / 指令数

55、）cpii cpi=0.255+0.14+0.524+0.113+0.023 = 4.12 时钟周期必须与功能部件最长的时间延时相 同，为200ps.,2012,99,华东师范大学计算机科学技术系,四、比较几种控制方案的性能,3. 流水线cpi 设：流水线方式中，一半的lw指令紧跟使用该取数结果的指令（数据相关）；分支错误预测开销为1个周期；设发生1/4预测错误；跳转指令消耗2个时钟周期 解： 无数据相关的lw执行需1个时钟周期，相关的 为2个周期，平均1.5个时钟周期； sw和alu指令1个时钟周期； 分支正确预测1个周期，错误预测2个周期，平 均为1.25个周期； 跳转指令2个周期,cpi

56、=1.525%+110%+152%+1.2511%+22%=1.17 时钟周期为200ps,2012,100,华东师范大学计算机科学技术系,四、比较几种控制方案的性能,比较： 单周期设计：600ps 多周期设计：2004.12=824ps 流水线设计：2001.17=234ps 最快 分析： 访存消耗了较长的时钟周期，可分解为2个 时钟周期。这样时钟周期就降低为100ps，对 多周期设计和流水线设计都将有性能上的提高。 完整的5级流水线数据通路和控制电路 图6-41,2012,101,华东师范大学计算机科学技术系,6 利用流水线提高性能,6.1 流水线概述 6.2 流水线的数据通路 6.3 流

57、水线中的控制 6.4 数据冒险与转发 6.5 数据冒险与阻塞 6.6 分支冒险 6.7 异常,2012,102,华东师范大学计算机科学技术系,6.7 异常,异常将引起程序转移 控制冒险 导致异常的原因： 运算溢出 i/o设备请求 用户程序调用操作系统服务 使用未定义指令 硬件错误 等,2012,103,华东师范大学计算机科学技术系,6.7 异常,例：执行指令add $1,$2,%1发生溢出 操作： 清空流水线 增加id.flush信号，清“0”id/ex流水线 缓冲寄存器（与原冒险检测有效信号相或） 增加ex.flush信号，清“0”ex/mem流水线 缓冲寄存器 溢出的中断矢量地址8000

58、0180pc pc mux改为3to1，建立送入8000 0180的 通路。,2012,104,华东师范大学计算机科学技术系,操作：, 保留断点 增加epc寄存器保留被打断指令的地址 记录引起异常的原因 增加cause寄存器记录异常类型 异常响应优先级 增加优先级判断电路，当多个异常同时发生时，由优先级判断电路决定响应的优先级。,2012,105,华东师范大学计算机科学技术系,6.7 异常,溢出处理的两种方法： 保持源寄存器内容不被目的数覆盖。溢出检 测发生在ex阶段，如前述，增加ex.flush信号，清“0”ex/mem流水线寄存器，阻止写入。 溢出指令照常执行 消除该条指令，在异常处理程序

59、中重新执行。 带有异常控制的数据通路 p280图6-42,2012,106,华东师范大学计算机科学技术系,6.7 异常, 清空流水线 增加id.flush信号，清“0”id/ex流水线缓冲寄存器, 清空流水线 增加ex.flush信号，清“0”ex/mem流水线缓冲寄存器,id.flush, 溢出的中断矢量地址8000 0180pc, 保留断点 增加epc寄存器保留被打断指令的地址, 记录引起异常的原因 增加cause寄存器记录异常类型,cause,2012,107,华东师范大学计算机科学技术系,6.7 异常,例8）主程序： 异常处理程序： 40h sub $11,$2,$4 40000004

60、0h sw $25,1000($0) 44h and $12,$2,$5 400000044h sw $26,1004($0) 48h or $13,$2,$6 4ch add $1, $2,$1 50h slt $15,$6,$7 54h lw $16,50($7) ,在异常处理程序的开始处要保护现场,发生运算溢出异常,2012,108,华东师范大学计算机科学技术系,6.7 异常,图6-43描述了发生异常的处理过程： 清空流水线 在cc7：指令add及以后指令被清除 保留断点和状态 50hepc 异常状态cause 转异常处理入口 80000180h pc 在中断处理程序中根据cause 内