03 计算机体系结构--流水线技术

1 .计算机体系结构 周学海 xhzhou@ustc.edu.cn 0551-63606864 中国科学技术大学 

2 . 第三章 流水线技术 3.1 流水线的基本概念 3.2 MIPS 基本流水线 3.3 MIPS 中多周期操作的处理 3.4 MIPS R4000 流水线 中国科学技术大学 chapter03.2 

3 .流水线的基本概念 • 一个任务可以分解为 k 个子任务 – K 个子任务在 K 个不同阶段（使用不同的资源）运行 – 每个子任务执行需要 1 个单位时间 – 整个任务的执行时间为 K 倍单位时间 • 流水线执行模式是重叠执行模式 – K 个流水段并行执行 K 个不同任务 – 每个单位时间进入 / 离开流水线一个任务 中国科学技术大学 chapter03.3 

4 . 同步流水线 • 流水段之间采用时钟控制的寄存器文件（ clocked registers) • 时钟上升沿到达时… – 所有寄存器同时保存前一流水段的结果 • 流水段是组合逻辑电路 • 流水线设计中希望各段相对平衡 – 即所有段的延迟时间大致相等 • 时钟周期取决于延迟最长的流水段 中国科学技术大学 chapter03.4 

5 . 流水线的性能 • 设 = time delay in stage Stime time delay in stage Sdelay time delay in stage Sin time delay in stage Sstage time delay in stage SSi • 时钟周期 = max( ) 为最长的流水段延迟 • 时钟频率 f = 1/ = 1/max( ) • 流水线可以在 k+n-1 个时钟周期内完成 n 个任务 – 完成第一个任务需要 k 个时钟周期 – 其他 n-1 个任务需要 n-1 个时钟周期完成 • K- 段流水线的理想加速比（相对于串行执行） 中国科学技术大学 chapter03.5 

6 . 简单的 5 段流水线 • 5 个流水段，每段的延迟为 1 个 cycle • IF: 取值阶段 – 选择地址：下一条指令地址、转移地址 • ID: 译码阶段 – 确定控制信号 并从寄存器文件中读取寄存器值 并从寄存器文件中读取寄存器值 • EX: 执行 – Load time delay in stage S 、 Store ：计算有效地址 – Branch ：计算转移地址并确定转移方向 • MEM: 存储器访问（仅 Load 和 Store) • WB: 结果写回 中国科学技术大学 chapter03.6 

7 . 流水线的可视化表示 • 多条指令执行多个时钟周期 – 指令按程序序从上到下排列 – 图中展示了每一时钟周期资源的使用情况 – 不同指令相邻阶段之间没有干扰 中国科学技术大学 chapter03.7 

8 . 03/19-review • 编译技术与计算机体系结构设计 – 有利于编译器的 ISA ： » 规整性、正交性、完整性 » 帮助编译器设计者了解各种代码序列的执行效率 和代价，有助于 编译器的优化 » 对于在编译时就已经可确定的量，提供能够将其变为常数的指令 – 寄存器分配是关键问题 » 寄存器数目多有利于编译器的设计与实现 » 提供至少 16 个通用寄存器和独立的浮点寄存器 – 保证所有的寻址方式可用于各种数据传送指令 – 最小指令集 • MIPS 指令集 18/9/22 中国科学技术大学 8 

9 . 03/19-review (MIPS) • Use general purpose registers with a load-store architecture: YES • Provide at least 16 general purpose registers plus separate floating- point registers: 31 GPR & 32 FPR • Support basic addressing modes: displacement (with an address offset size of 12 to 16 bits), immediate (size 8 to 16 bits), and register deferred; : YES: 16 bits for immediate, displacement (disp=0 => register deferred) • All addressing modes apply to all data transfer instructions : YES • Use fixed instruction encoding if interested in performance and use variable instruction encoding if interested in code size : Fixed • Support these data sizes and types: 8-bit, 16-bit, 32-bit integers and 32-bit and 64-bit IEEE 754 floating point numbers: YES • Support these simple instructions, since they will dominate the number of instructions executed: load, store, add, subtract, move register-register, and, shift, compare equal, compare not equal, branch (with a PC-relative address at least 8-bits long), jump, call, and return: YES, 16b • Aim for a minimalist instruction set: YES 18/9/22 中国科学技术大学 Chapter2.9 

10 . 03/19-review 流水线技术要 点 • 流水线技术并不能提高单个任务的执行效率 ，它可以 提高整个系统的吞吐率 • 流水线中的瓶颈——最慢的那一段 • 多个任务同时执行，但使用不同的资源 • 其潜在的加速比＝流水线的级数 • 流水段所需时间不均衡将降低加速比 • 流水线存在装入时间和排空时间，使得加速比降低 • 由于存在相关问题，会导致流水线停顿 中国科学技术大学 chapter3.10 

11 . 指令流时序 • 时序图展示： – 每个时钟周期指令所使用的流水段情况 • 指令流在采用 5 段流水线执行模式的执行情况 中国科学技术大学 chapter03.11 

12 . 单周期、多周期、流水线控制性能比较 • 假设 5 段指令执行流水线 • 某一程序段假设： – 20% time delay in stage Sload, time delay in stage S10% time delay in stage Sstore, time delay in stage S40% time delay in stage SALU, time delay in stage Sand time delay in stage S30% time delay in stage Sbranch • 比较三种执行模式的性能 中国科学技术大学 chapter03.12 

13 . 流水线的性能分析 基本度量参数：吞吐率 ，加速比，效率 吞吐率 ：在单位时间内流水线所完成的任务数量或输 出结果的数量。 n TP  TK n ：任务数 Tk ：处理完成 n 个任务所用的时间 中国科学技术大学 chapter03.13 

14 . 流水线技术提高系统的任务吞吐率 1. 各段时间均相等的流水线 – 各段时间均相等的流水线时空图 空间 S4 1 2 3 … … n-1 n S3 1 2 3 … … n-1 n S2 1 2 3 … … n-1 n S1 1 2 3 … … n-1 n k· △t (n-1)· △t 时间 （单位：△t） Tk 中国科学技术大学 chapter03.14 

15 . 吞吐率 – 流水线完成 n 个连续任务所需要 的总时间为 （假设一条 k段线性流水线） 　　　　 Tk ＝ kΔt ＋ (n-1)ΔΔt ＝ (k ＋ n-1)ΔΔt – 流水线的实际吞吐率 TP  n (k  n  1)t  最大吞吐率 : 流水线在连续流动达到稳定状态后 所得到的吞吐率 。 TP  lim n 1  n    k  n  1 t max t S4 1 2 3 4 5 .. .. .. n-1 n S3 1 2 3 4 5 .. .. .. n-1 n n S2 1 2 3 4 5 .. .. .. n-1 n TP  TPmax S1 1 2 3 4 5 .. .. .. n-1 n k n 1 中国科学技术大学 15 

16 . TP 与 Tpmax 的关系 – 最大吞吐率 与实际吞吐率 的关系 n TP  TPmax k n 1  流水线的实际吞吐率 小于最大吞吐率 ，它除了与 每个段的时间有关外，还与流水线的段数 k 以及 输入到流水线中的任务数 n等有关。  只有当 n>>k时，才有 TP≈TPmax 。 中国科学技术大学 chapter03.16 

17 . 流水线中的瓶颈——最慢的段 2. 各段时间不完全相等的流水线 – 各段时间不等的流水线及其时空图 » 一条 4段的流水线 » S1 ， S3 ， S4 各段的时间： Δt » S2 的时间： 3Δt （瓶颈段） 流水线中这种时间最长的段称为流水线的瓶颈段。 中国科学技术大学 chapter03.17 

18 .中国科学技术大学 chapter03.18 

19 .– 各段时间不等的流水线的实际吞吐率 ： （ Δti 为第 i 段的时间，共有 k 个段 ） n TP  k  t i 1 i  (n  1) max(t1 , t 2 ,, t k )  流水线的最大吞吐率为 1 TPmax  max(t1 , t 2 , t k ) 中国科学技术大学 19 

20 . 例如：一条 4 段的流水线中， S1 ， S2 ， S4 各 段的 时间都是 Δt ，唯有 S3 的时间是 3ΔΔt 。 △t △t 3△t △t 入 S1 S2 S3 S4 出 最大吞吐率为 1 TPmax  3t 中国科学技术大学 20 

21 .3Δ. 解决流水线瓶颈问题的常用方法 – 细分瓶颈段 例如：对前面的 4段流水线 把瓶颈段 S3细分为 3个子流水线段： S3a ， S3b ， S3c △t △t △t △t △t △t 入 S1 S2 S3a S3b S3c S4 出 改进后的流水线的吞吐率 ： TP 1 max  t 中国科学技术大学 21 

22 .– 重复设置瓶颈段 » 缺点：控制逻辑比较复杂，所需的硬件增加了 。 例如：对前面的 4段流水线 重复设置瓶颈段 S3： S3a ， S3b ， S3c 3△t S3a △t △t △t 入 S1 S2 S3b S4 出 S3c 中国科学技术大学 chapter03.22 

23 .段 S4 1 2 3 4 5 6 7 8 9 S3c 3 6 9 S3b 2 5 8 S3a 1 4 7 S2 1 2 3 4 5 6 7 8 9 S1 1 2 3 4 5 6 7 8 9 时间 重复设置瓶颈段后的时空图 中国科学技术大学 chapter03.23 

24 . 加速比 加速比：完成同样一批任务，不使用流水线所用的时间 与使用流水线所用的时间之比。 假设：不使用流水线（即顺序执行）所用的间 为 Ts ，使用流水线后所用的时间为 Tk，则该流 水线的加速比为 Ts S Tk 中国科学技术大学 chapter03.24 

25 .1. 流水线各段时间相等（都是△ t ） – 一条 k 段流水线完成 n 个连续任务 所需要的时间为 Tk = (k ＋ n-1)Δt – 顺序执行 n 个任务 所需要的时间： Ts= nk△t 流水线的实际加速比为 nk S k n 1 中国科学技术大学 chapter03.25 

26 .– 最大加速比 nk S max  lim k n  k  n  1 当 n>>k时， S ≈ k 思考：流水线的段数愈多愈好？ 中国科学技术大学 chapter03.26 

27 .2 .流水线的各段时间不完全相等时 – 一条 k 段流水线完成 n 个连续任务的实际加速比 为 k n ti S k i 1  t i 1 i  (n  1) max(t1 , t 2 , , t k ) 中国科学技术大学 chapter03.27 

28 . 效率 效率 ：流水线中的设备实际使用时间与整个运行时间 的比值，即流水线设备的利用率 。 由于流水线有通过时间和排空时间，所以在连续 完成 n个任务的时间内，各段并不是满负荷地工作。 • 各段时间相等 – 各段的效率 ei 相同 nt n e1 e2  ek   Tk k n 1 中国科学技术大学 chapter03.28 

29 .– 整条流水线的效率 为 e1  e2    ek ke1 knt E   k k kTk  可以写成 n E k n 1  最高效率为 n Emax  lim 1 n  k  n  1 当 n>>k时， E≈1 。 中国科学技术大学 29