计算机体系结构-第二讲 流水线基础ppt课件

1、,北京邮电大学 计算机系科学与技术系 ,流水线基础 (Pipelining Basic) 王春露（Prof. Chunlu Wang） ,流水线技术 相关性分析技术 超标量处理机 超流水线处理机 超标量超流水线处理机,流水线技术,流水线是很自然的!,洗衣店的例子,A, B, C, D,均有一些衣务要清洗，甩干，折叠,清洗要花 30 分钟,甩干要用 30 分钟,叠衣物也需要 30 分钟,还要花费 30 分钟的时间,将衣物放在衣柜里,A,B,C,D,顺序操作,洗4 个人的衣物，顺序操作需要 8 个小时,如果使用流水线作业, 将需要多少时间呢?,30,任,务,顺,序,时间,30,30,30,30,3

2、0,30,30,30,30,30,30,30,30,30,30,6 下午,7,8,9,10,11,12,1,2 上午,流水线作业,流水线作业洗4个人的衣物只需要 3.5 个小时!,任,务,顺,序,12,2 上午,6 下午,7,8,9,10,11,1,时间,流水线,流水线无法帮助解决单个任务,的延迟, 有利于减少整个工作,全部时间,多个任务同时操作需要不同 的资源,可能的加速比 =,流水线的段数,流水线的速率受速度最慢,的流水段的限制,流水线各段长度不均会降低 加速比,充满流水线所需的时间和,排空流水线所需的时间影响,加速比,会由于依赖而造成阻塞,6 下午,7,8,9,时间,任,务,顺,序,传统

3、的流水线执行表示,程序流,时间轴,为什么采用流水线呢? 因为有资源空闲!,指,令,顺,序,时间 (时钟周期),Inst,0,Inst,1,Inst,2,Inst,4,Inst,3,单时钟周期, 多时钟周期,同流水线比较.,Clk,Cycle 1,多时钟周期的实现:,Cycle 2,Cycle 3,Cycle 4,Cycle 5,Cycle 6,Cycle 7,Cycle 8,Cycle 9,Cycle 10,Load,Load,Store,流水线的实现:,Store,Clk,单时钟周期的实现:,Load,Store,Waste,R-type,R-type,Cycle 1,Cycle 2,为什么

4、使用流水线?,设想我们要执行 100 条指令,单周期的机器,45,ns,/cycle x 1 CPI x 100,inst,= 4500,ns,多周期的机器,10,ns,/cycle x 4.2 CPI (due to,inst,mix) x 100,inst,= 4200,ns,理想的流水线机器,10,ns,/cycle x (1 CPI x 100,inst,+ 4 cycle drain) = 1040,ns,Load指令的五个阶段,Ifetch,: 获取指令,从指令存储器中获取指令,Reg,/Dec: 获取寄存器，指令译码,Exec: 计算内存地址,Mem,: 从数据存储器中读数据,W

5、r,: 向寄存器文件写回数据,Cycle 1,Cycle 2,Cycle 3,Cycle 4,Cycle 5,Load,Pipelining,通过增加指令的执行阶段增强性能,理想的加速比是流水线的段数. 我们能够获得这个加速比吗?,基本思想,我们要将数据通路分割成不同的阶段，需要增加些什么?,流水线数据通路,流水线技术,流水线是一种实现技术 空间并行性：设置多个独立的操作部件 如：多操作部件处理机、超标量处理机 时间并行性：采用流水线技术 不增加或只增加少量硬件就能使运算速度提高几倍， 如：流水线处理机、超流水线处理机 流水线工作原理 流水线的分类 线性流水线的性能分析 非线性流水线的调度技术

6、,流水线工作原理,1、流水线锁存器 流水线的每一个阶段称为流水步、流水步骤、流水段、流水 线阶段、流水功能段、功能段、流水级、流水节拍等。 在每一个流水段的末尾或开头必须设置一个(多个)寄存器，称为 流水寄存器、流水锁存器、流水闸门寄存器等。 流水锁存器会增加每条指令的执行时间，但采用流水线之 后整个程序的执行时间会缩短。 为了简化，在一般流水线中不画出流水锁存器。,2、流水线的表示方法 流水线的连接图表示方法 表示流水线的逻辑关系 流水线的时空图表示方法 表示流水线的时间关系 流水线的预约表表示方法 将在非线性流水线中介绍 一般处理机的指令流水线为 4 至 12 个级 指令流水线等于和大于8

7、级的称为超流水线处理机,3、流水线时空图 一条简单流水线的时空图 一个浮点加法器流水线的时空图 由求阶差、对阶、尾数加和规格化4个流水段组成,4、流水线的主要特点 只有连续提供同类任务才能充分发挥流水线的效率。 对于指令流水线：要尽量减少因条件分支造成的“断流” 对于操作部件：主要通过编译技术，尽量提供连续的相同类型的操作。 在流水线的每一个流水线段中都要设置一个流水锁存器。 时间开销：流水线的执行时间加长， 是流水线中需要增加的主要硬件之一。 各流水段的时间应尽量相等。 流水线处理机的基本时钟周期等于时间最长的流水段的时间长度。 流水线需要有“装入时间”和“排空时间”。 Latency &

8、throughput?,流水线技术,流水线技术在50年代后期被应用于处理器设计 IBM Stretch-first general-purpose pipelined computer CDC 6600 use load/store design to achieve efficient pipelining.,流水线工作原理 流水线的分类 线性流水线的性能分析 非线性流水线的调度技术,流水线技术,流水线的分类 1、线性流水线与非线性流水线 流水线的各个流水段之间是否有反馈信号 线性流水线（Linear Pipelining）： 每一个流水段都流过一次，而且仅流过一次。 非线性流水线（Nonl

9、inear Pipelining）： 在流水线的某些流水段之间有反馈回路或前馈回路。 线性流水线能够用流水线连接图唯一表示 非线性流水线必须用流水线连接图流水线预约表等共同表示,2、按照流水线的级别来分 处理机级流水线，又称为指令流水线。 例如：在采用先行控制器的处理机中，各功能部件之间的流水线 部件级流水线（操作流水线），如浮点加法器流水线。,处理机之间的流水线称为宏流水线（Macro Pipelining） 每个处理机对同一个数据流的不同部分分别进行处理。,3、单功能流水线与多功能流水线 单功能流水线：只能完成一种固定功能的流水线。 Cray-1计算机种有12条 YH-1计算机有18条 P

10、entium有一条5段的定点和一条8段的浮点流水线。 Pentium有两条定点指令流水线，一条浮点指令流水线。 多功能流水线： 流水线的各段通过不同的连接实现不同的功能。 Texas公司的ASC计算机中的8段流水线，能够实现： 定点加减法、定点乘法、 浮点加法、浮点乘法， 逻辑运算、移位操作、 数据转换、向量运算等。,4、静态流水线与动态流水线 静态流水线：同一段时间内，多功能流水线中的各个功能段只能按照一种固定的方式连接，实现一种固定的功能。 只有连续出现同一种运算时，流水线的效率才能得到充分的发挥。,动态流水线：在同一段时间内，多功能流水线中的各段可以按照不同的方式连接，同时执行多种功能。

11、,5、流水线的其他分类方法 按照数据表示方式：标量流水线和向量流水线 按照控制方式：同步流水线和异步流水线 顺序流水线与乱序流水线，乱序流水线又称为无序流水线、 错序流水线或异步流水线等。(out of order),流水线工作原理 流水线的分类 线性流水线的性能分析 非线性流水线的调度技术,标量处理机流水线技术,线性流水线的性能分析 衡量流水线性能的主要指标有：吞吐率、加速比和效率。 1、吞吐率（Though Put） 计算流水线吞吐率的最基本公式： 其中：n为任务数，k为完成n个任务所用的时间。 各段执行时间相等，输入连续任务情况下： 完成n个连续任务需要的总时间为：Tk（kn1）t 其中

12、：k 为流水线的段数，t为时钟周期。,吞吐率为： 最大吞吐率为： 各段执行时间不相等，输入连续任务情况下： 吞吐率为： 最大吞吐率为： 流水线各段执行时间不相等的解决办法,(1)将流水线的“瓶颈”部分再细分（如果可分的话）。,2、加速比（Speedup） 计算流水线加速比的基本公式： 各段执行时间相等，输入连续任务情况下： 加速比为： 最大加速比为： 各段执行时间不相等，输入连续任务情况下, 实际加速比为：,当流水线段数增加时，需要连续输入的任务数也必须增加,4、流水线最佳段数的选择 采用顺序执行方式完成一个任务的时间为t 在同等速度的k段流水线上执行一个任务的时间为：tkd 其中：d为流水锁

13、存器的延迟时间 流水线的最大吞吐率为： 流水线的总价格估计为：Cab k， 其中：a为所有功能段本身的总价格，b为每个锁存器的价格 A.G.Larson把流水线的性 能价格比PCR定义为： 求得到PCR的最大值为：,5、流水线性能分析举例 对于单功能线性流水线，输入连续任务的情况，通过上面给出的公式很容易计算出流水线的吞吐率、加速比和效率。 例：用一条4段浮点加法器流水线求8个浮点数的和： ZABCDEFGH 解：Z（AB）（CD）（EF）（GH）,流水线工作原理 流水线的分类 线性流水线的性能分析 非线性流水线的调度技术,流水线技术,非线性流水线的调度技术 非线性流水线调度的任务是要找出一个

14、最小的循环周期，按照这周期向流水线输入新任务，流水线的各个功能段都不会发生冲突，而且流水线的吞吐率和效率最高。 1、非线性流水线的表示 线性流水线能够用流水线连接图唯一表示 连接图不能用唯一表示非线性流水线的工作流程，因此，引入流水线预约表,与流水线预约表对应的流水线连接图,一张预约表可能与多个流水线连接图相对应,一个流水线连接图对应与多张预约表,2、非线性流水线的冲突 流水线的启动距离：连续输入两个任务之间的时间间隔 流水线的冲突：几个任务争用同一个流水段,3、无冲突调度方法,由E.S.Davidson及其学生于1971年提出 非线性流水线的禁止启动集合：预约表中每一行任意两个“” 之间的距

15、离都计算出来，去掉重复的。上例中为（3，4，6） 由禁止启动集合得到冲突向量：C（CmCm-1C2C1） 其中：m是禁止向量中的最大值。如果i在禁止向量中， 则Ci1，否则Ci0。上例中 C（101100）。 由冲突向量构造状态图： 把冲突向量送入一个m位逻辑右移移位器；如果移位器移出0，用移位器中的值与初始冲突向量作“按位或”运算，得到一个新的冲突向量；否则不作任何处理；如此重复m次。 对于中间形成的每一个新的冲突向量，也要按照这一方法进行处理。 在初始冲突向量和所有的新形成的冲突向量之间用带箭头的线连接，当新形成的冲突向量出现重复时可以合并到一起。,例：一条有4个功能段的非线性流水线，每个

16、功能段的延迟 时间都相等，它的预约表如下： (1) 写出流水线的禁止集合和初始冲突向量。 (2) 画出调度流水线的状态图。 (3) 求流水线的最小启动循环和最小平均启动距离。 (4) 求平均启动距离最小的恒定循环。 解：(1)禁止集合为：（2，4，6） 初始冲突向量：101010 (2)初始冲突向量逻辑右移2、4、6位时，不作任何处理， 逻辑右移1、3、5和大于等于7时，要进行处理。,初始冲突向量右移1位之后：010101101010111111， 初始冲突向量右移3位之后：000101101010101111， 初始冲突向量右移5位之后：000001101010101011， 初始冲突向量右

17、移7位或大于7位后：还原到它本身。 中间冲突向量101111右移5位之后：000001101010101011， 中间冲突向量101011右移3位之后：000101101010101111， 中间冲突向量101011右移5位之后：000001101010101011。,预约表与状态图是唯一对应， 但不同的预约表也可能有相同的状态图。 简单循环：状态图中各种冲突向量只经过一次的启动循环。 简单循环的个数是有限的,由简单循环计算平均启动距离。 (3)最小的启动循环为（1，7）和（3，5）,平均启动距离为 4。 (4)启动距离最小的恒定循环是（5）。,4、优化调度方法 L.E.Shar于1972年提

18、出流水线最小平均启动距离的限制范围 (1)下限是预约表中任意一行里“”的最多个数。 (2)小于或等于状态图中任意一个简单循环的平均启动距离。 (3)最小平均启动距离的上限是冲突向量中1的个数再加上1。 1992年，L.E.Shar又证明了上述限制范围。 最有用的是第1条。预约表中“”最多的行一定是瓶颈流水段 采用预留算法来调度非线性流水线，可以达到最优调度： (1)确定最小平均启动距离（MAL）。预约表任一行中“”的最多个数 (2)确定最小启动循环。一般恒定循环作为最小启动循环。 (3)通过插入非计算延迟段-修改预约表实现最小启动循环。 对于上面的例子：最小平均启动距离为2。 最小启动循环为恒

19、定循环（2）。 任一行中与第1个“”的距离为2的倍数的周期都要预留出来。,每一行中与第1个“”的距离为2的倍数的位置都要预留出来。 S3行的第2个“”从周期5延迟到周期6。为此， S2行的第2个“”要向后延迟一个周期，从周期6延迟到周期7； S1行的第2个“”要向后延迟一个周期，从周期7延迟到周期8。 实际上，只要在流水段S4的输出端到流水段S3的输入端中间插入一个非计算延迟D1。,在非线性流水线中，“”最多的流水段一定是“瓶颈“流水段。 实现最优调度的目标是使“瓶颈”流水段处于忙碌状态，没有空闲周期。 最优调度方法能够使非线性流水线的吞吐率、加速比和效率达到最优。,动态调度方法,一个启动循环

20、C，从C推导出各个起始之间所有可能的时间间隔集合Gc，称为启动间隔集合 C=（2，3，2，5） Gc=（2，3，5，7，9，10，14，15，17，19，21，22，24，26，。） 间隔并不限于两个相邻的起始 取Gc（mod p），p为循环周期,P=12的循环C=（2，3，2，5） Gc（mod12）=0，2，3，5，7，9，10 在禁止起动集合为F的流水线中，iff ： F（mod p）Gc（mod p）=时 周期为p和启动间隔集合Gc的启动循环C才是可以允许的。,高级流水线技术,超标量流水线 超流水线 超标量超流水线,超标量处理机,基本结构 单发射与多发射 多流水线调度 资源冲突 超标量

21、处理机性能,三种主流处理机： 超标量处理机：Intel公司的i860、i960、Pentium处理机， Motolora公司的MC88110，IBM公司的Power 6000， SUN公司的SPARC、 SuperSPARC、 UltraSPARC等。 超流水线处理机：SGI公司的MIPS R4000、R5000、R10000等。 超标量超流水线处理机：DEC公司的Alpha等。,基本结构 一般流水线处理机： 一条指令流水线， 一个多功能操作部件， 每个时钟周期平均执行指令的条数小于1。 多操作部件处理机： 一条指令流水线， 多个独立的操作部件，可以采用流水线，也可以不流水。 多操作部件处理机

22、的指令级并行度小于1。 超标量处理机典型结构： 多条指令流水线。 先进的超标量处理机有：定点处理部件CPU，浮点处理部件FPU,图形加速部件GPU，大量的通用寄存器，两个一级Cache。 超标量处理机的指令级并行度（ILP）大于1。,Motorola公司的MC88110。有10个操作部件。 两个寄存器堆：整数部件通用寄存器堆，32个32位寄存器； 浮点部件扩展寄存器堆，32个80位寄存器。 缓冲深度为4的先行读数栈，缓冲深度为3的后行写数栈。 两个独立的高速Cache中，各为8KB，采用两路组相联方式， 转移目标指令Cache，存放一条分支上的指令。,单发射与多发射 单发射处理机： 每个周期只

23、取一条指令、只译码一条指令，只执行一条指令，只写回一个运算结果。 取指令部件和指令译码部件各设置一套； 只设置一个多功能操作部件或设置多个独立的操作部件； 操作部件中可以采用流水线结构，也可以不采用流水线结构。 目标是每个时钟周期平均执行一条指令，ILP的期望值为1。 多发射处理机： 每个周期同时取多条指令、同时译码多条指令，同时执行多条指令，同时写回多个运算结果。 需要多个取指令部件，多个指令译码部件和多个写结果部件。 设置多个指令执行部件，有些指令执行部件采用流水线结构。 目标是每个时钟周期平均执行多条指令，ILP的期望值大于1。,超标量处理机：一个时钟周期能同时发射多条指令的处理机 必须

24、有两条或两条以上能够同时工作的指令流水线。 先行指令窗口：能够从指令Cache中预取多条指令， 能够对窗口内的指令进行数据相关性分析和功能部件冲突检测。 先行指令窗口的大小：一般为2至8条指令。 目前的指令调度技术，每个周期发射2至4条指令比较合理。 例如：Intel公司的i860、i960、Pentium，Motolora公司的MC88110，IBM公司的Power 6000等每个周期都发射两条指令； TI公司生产SuperSPARC，Pentium III每个周期发射三条指令。 操作部件的个数一般多于每个周期发射的指令条数。通常为4 个至16个操作部件。 超标量处理机的指令级并行度：1IL

25、Pm。 m为每个周期发射的指令条数。,多流水线调度 多条流水线的调度问题是一个NP完全问题， 顺序发射（in-order issue）与乱序发射（out-order issue）： 指令发射顺序是按照程序中指令排列顺序进行的称为顺序发射 顺序完成(in-order completion)与乱序完成(out-order completion) 指令完成顺序是按照程序中指令排列顺序进行的称为顺序完成 多流水线的调度主要有三种方法： 顺序发射顺序完成，顺序发射乱序完成，乱序发射乱序完成。 I1：LOAD R1, A ；R1（A） I2：FADD R2, R1 ；R2（R2）（R1） I3：FMUL

26、R3, R4 ；R3（R3）（R4） I4：FADD R4, R5 ；R4（R4）（R5） I5：DEC R6 ；R6（R6）1 I6：FMUL R6, R7 ；R6（R6）（R7）,1、顺序发射顺序完成 6条指令按顺序分三个时钟周期发射，共用10个时钟周期完成。 除了流水线的装入和排空部分之外，还有8个空闲的时钟周期。,2、顺序发射乱序完成 与顺序发射顺序完成调度方法相比，少了5个空闲时钟周期。 6条指令总的执行时间为9个时钟周期，与顺序发射顺序完成调度方法相比节省了一个时钟周期。,3、乱序发射乱序完成，必须使用先行指令窗口。除了装入和排空之外，没有空闲周期，功能部件得到充分利用 6条指令总

27、的执行时间缩短为8个周期，比顺序发射顺序完成方法节省2个周期，比顺序发射乱序完成方法相比节省一个周期。,资源冲突 如果操作部件采用流水线结构，发生资源冲突的可能性很小； 如果不采用流水线结构，发生资源冲突的可能性就大。 下面是一个由4条指令程序的程序： I1：FADD R0, R1 ；R0（R0）（R1） I2：FMUL R2, R3 ；R2（R2）（R3） I3：FADD R4, R5 ；R4（R4）（R5） I4：FMUL R6, R7 ；R6（R6）（R7）,操作部件不采用流水线： 做完4条指令总共用了11个周期，有5个空闲周期。 操作部件采用流水线： 做完4条指令共用8个周期，少用3个

28、周期。,在超标量处理机中，操作部件采用流水线结构的原因分析 假每个周期发射m条指令，操作部件的延迟时间为k个周期， 如果操作部件不采用流水线结构，则使用同一个操作部件的两条指令的序号应该至少相差mk。 如果操作部件采用k个功能段的流水线结构，则使用同一个操作部件的两条指令的序号只需要相差m或m以上。 指令流水线的段数k一般在4至10之间，每个时钟周期发射的指令条数m在2至4之间。取中间值，k7，m3； 为了不发生资源冲突，如果操作部件不采用流水线结构， 两条使用同一个功能部件的指令序号必须相差21或21以上； 如果操作部件采用流水线结构， 两条使用同一个功能部件的指令序号只需要相差3或3以上。

29、 因此，在超标量处理机中，操作部件一般要采用流水线结构 如果由于某种原因，操作部件不能采用流水线结构，则必须设置多个相同种类的操作部件,普通标量处理机，希望相同操作连续出现。 只有连续出现相同操作的指令序列时，流水线才能不“断流”，功能部件的效率才能得到充分发挥。 超标量处理机则正好相反，希望相同操作不要连续出现。 相同操作的指令序列连续出现时，会发生资源冲突； 要求相同操作的指令能够相对均匀地分布在程序中。 超标量处理机的这种要求正好符合一般标量程序的特点。,超标量处理机性能 单流水线普通标量处理机的指令级并行度记作(1,1)， 超标量处理机的指令级并行度记作(m,1)， 超流水线处理机的指

30、令级并行度记作(1,n)， 而超标量超流水线处理机的指令级并行度记作(m,n)。 在理想情况下，N条指令在单流水线标量处理机上的执行时间为：T(1,1)（kN1）t 在每个周期发射m条指令的超标量处理机上执行的时间为： T(m,1)（k ）t 超标量处理机相对于单流水线标量处理机的加速比为： S(m,1) 超标量处理机的加速比的最大值为：S(m,1)MAXm,超流水线处理机,两种定义： 在一个周期内能够分时发射多条指令的处理机 指令流水线的功能段数为8段或超过8段的流水线处理机 提高处理机性能的不同方法： 超标量处理机：通过增加硬件资源来提高处理机性能 超流水线处理机：通过各部分硬件的重叠工作

31、来提高 处理机性能。 两种不同并行性： 超标量处理机采用的是空间并行性。 超流水线处理机采用的是时间并行性。,指令执行时序 每隔1/n个时钟周期发射一条指令， 即处理机的流水线周期为1/n个时钟周期。 在超标量处理机中，流水线的有些功能段还可以进一步细分， 例如：ID功能段，可以再细分为：译码、读第一操作数和读 第二操作数三个流水段。,典型处理机结构 MIPS R4000处理机，每个时钟周期包含两个流水段， 是一种很标准的超流水线处理机结构。 指令流水线有8个流水段。 有两个Cache，指令Cache和数据Cache的容量各8KB， 每个时钟周期可以访问Cache两次， 因此在一个时钟周期内可以从指令Cache中读出两条指令， 从数据Cache中读出或写入两个数据。 主要运算部件有整数部件和浮点部件。,如果在LOAD指令之后的两条指令中，任何一条指令要在它的EX流水级使