计算机体系结构之流水线工作原理与分类(ppt 96页).ppt

北京邮电大学计算机系科学与技术系 流水线基础 PipeliningBasic 王春露 Prof ChunluWang wangcl 流水线技术相关性分析技术超标量处理机超流水线处理机超标量超流水线处理机 流水线技术 流水线是很自然的 洗衣店的例子 A B C D 均有一些衣务要清洗 甩干 折叠 清洗要花30分钟 甩干要用30分钟 叠衣物也需要30分钟 还要花费30分钟的时间 将衣物放在衣柜里 A B C D 顺序操作 洗4个人的衣物 顺序操作需要8个小时 如果使用流水线作业 将需要多少时间呢 30 任 务 顺 序 时间 30 30 30 30 30 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 时间 任 务 顺 序 传统的流水线执行表示 程序流 时间轴 为什么采用流水线呢 因为有资源空闲 指 令 顺 序 时间 时钟周期 Inst 0 Inst 1 Inst 2 Inst 4 Inst 3 单时钟周期 多时钟周期 同流水线比较 Clk Cycle1 多时钟周期的实现 Cycle2 Cycle3 Cycle4 Cycle5 Cycle6 Cycle7 Cycle8 Cycle9 Cycle10 Load Load Store 流水线的实现 Store Clk 单时钟周期的实现 Load Store Waste R type R type Cycle1 Cycle2 为什么使用流水线 设想我们要执行100条指令 单周期的机器 45 ns cyclex1CPIx100 inst 4500 ns 多周期的机器 10 ns cyclex4 2CPI dueto inst mix x100 inst 4200 ns 理想的流水线机器 10 ns cyclex 1CPIx100 inst 4cycledrain 1040 ns Load指令的五个阶段 Ifetch 获取指令 从指令存储器中获取指令 Reg Dec 获取寄存器 指令译码 Exec 计算内存地址 Mem 从数据存储器中读数据 Wr 向寄存器文件写回数据 Cycle1 Cycle2 Cycle3 Cycle4 Cycle5 Load Pipelining 通过增加指令的执行阶段增强性能 理想的加速比是流水线的段数 我们能够获得这个加速比吗 基本思想 我们要将数据通路分割成不同的阶段 需要增加些什么 流水线数据通路 流水线技术 流水线是一种实现技术空间并行性 设置多个独立的操作部件如 多操作部件处理机 超标量处理机时间并行性 采用流水线技术不增加或只增加少量硬件就能使运算速度提高几倍 如 流水线处理机 超流水线处理机流水线工作原理流水线的分类线性流水线的性能分析非线性流水线的调度技术 流水线工作原理 1 流水线锁存器流水线的每一个阶段称为流水步 流水步骤 流水段 流水线阶段 流水功能段 功能段 流水级 流水节拍等 在每一个流水段的末尾或开头必须设置一个 多个 寄存器 称为流水寄存器 流水锁存器 流水闸门寄存器等 流水锁存器会增加每条指令的执行时间 但采用流水线之后整个程序的执行时间会缩短 为了简化 在一般流水线中不画出流水锁存器 2 流水线的表示方法流水线的连接图表示方法表示流水线的逻辑关系流水线的时空图表示方法表示流水线的时间关系流水线的预约表表示方法将在非线性流水线中介绍一般处理机的指令流水线为4至12个级指令流水线等于和大于8级的称为超流水线处理机 3 流水线时空图 一条简单流水线的时空图 一个浮点加法器流水线的时空图由求阶差 对阶 尾数加和规格化4个流水段组成 4 流水线的主要特点只有连续提供同类任务才能充分发挥流水线的效率 对于指令流水线 要尽量减少因条件分支造成的 断流 对于操作部件 主要通过编译技术 尽量提供连续的相同类型的操作 在流水线的每一个流水线段中都要设置一个流水锁存器 时间开销 流水线的执行时间加长 是流水线中需要增加的主要硬件之一 各流水段的时间应尽量相等 流水线处理机的基本时钟周期等于时间最长的流水段的时间长度 流水线需要有 装入时间 和 排空时间 Latency throughput 流水线技术 流水线技术在50年代后期被应用于处理器设计IBMStretch firstgeneral purposepipelinedcomputerCDC6600useload storedesigntoachieveefficientpipelining 流水线工作原理流水线的分类线性流水线的性能分析非线性流水线的调度技术 流水线技术 流水线的分类1 线性流水线与非线性流水线流水线的各个流水段之间是否有反馈信号线性流水线 LinearPipelining 每一个流水段都流过一次 而且仅流过一次 非线性流水线 NonlinearPipelining 在流水线的某些流水段之间有反馈回路或前馈回路 线性流水线能够用流水线连接图唯一表示非线性流水线必须用流水线连接图流水线预约表等共同表示 2 按照流水线的级别来分处理机级流水线 又称为指令流水线 例如 在采用先行控制器的处理机中 各功能部件之间的流水线部件级流水线 操作流水线 如浮点加法器流水线 处理机之间的流水线称为宏流水线 MacroPipelining 每个处理机对同一个数据流的不同部分分别进行处理 3 单功能流水线与多功能流水线单功能流水线 只能完成一种固定功能的流水线 Cray 1计算机种有12条YH 1计算机有18条Pentium有一条5段的定点和一条8段的浮点流水线 Pentium 有两条定点指令流水线 一条浮点指令流水线 多功能流水线 流水线的各段通过不同的连接实现不同的功能 Texas公司的ASC计算机中的8段流水线 能够实现 定点加减法 定点乘法 浮点加法 浮点乘法 逻辑运算 移位操作 数据转换 向量运算等 4 静态流水线与动态流水线静态流水线 同一段时间内 多功能流水线中的各个功能段只能按照一种固定的方式连接 实现一种固定的功能 只有连续出现同一种运算时 流水线的效率才能得到充分的发挥 动态流水线 在同一段时间内 多功能流水线中的各段可以按照不同的方式连接 同时执行多种功能 5 流水线的其他分类方法按照数据表示方式 标量流水线和向量流水线按照控制方式 同步流水线和异步流水线顺序流水线与乱序流水线 乱序流水线又称为无序流水线 错序流水线或异步流水线等 outoforder 流水线工作原理流水线的分类线性流水线的性能分析非线性流水线的调度技术 标量处理机流水线技术 线性流水线的性能分析衡量流水线性能的主要指标有 吞吐率 加速比和效率 1 吞吐率 ThoughPut 计算流水线吞吐率的最基本公式 其中 n为任务数 k为完成n个任务所用的时间 各段执行时间相等 输入连续任务情况下 完成n个连续任务需要的总时间为 Tk k n 1 t其中 k为流水线的段数 t为时钟周期 吞吐率为 最大吞吐率为 各段执行时间不相等 输入连续任务情况下 吞吐率为 最大吞吐率为 流水线各段执行时间不相等的解决办法 1 将流水线的 瓶颈 部分再细分 如果可分的话 2 加速比 Speedup 计算流水线加速比的基本公式 各段执行时间相等 输入连续任务情况下 加速比为 最大加速比为 各段执行时间不相等 输入连续任务情况下 实际加速比为 当流水线段数增加时 需要连续输入的任务数也必须增加 4 流水线最佳段数的选择采用顺序执行方式完成一个任务的时间为t在同等速度的k段流水线上执行一个任务的时间为 t k d其中 d为流水锁存器的延迟时间流水线的最大吞吐率为 流水线的总价格估计为 C a bk 其中 a为所有功能段本身的总价格 b为每个锁存器的价格A G Larson把流水线的性能价格比PCR定义为 求得到PCR的最大值为 5 流水线性能分析举例对于单功能线性流水线 输入连续任务的情况 通过上面给出的公式很容易计算出流水线的吞吐率 加速比和效率 例 用一条4段浮点加法器流水线求8个浮点数的和 Z A B C D E F G H解 Z A B C D E F G H 流水线工作原理流水线的分类线性流水线的性能分析非线性流水线的调度技术 流水线技术 非线性流水线的调度技术非线性流水线调度的任务是要找出一个最小的循环周期 按照这周期向流水线输入新任务 流水线的各个功能段都不会发生冲突 而且流水线的吞吐率和效率最高 1 非线性流水线的表示线性流水线能够用流水线连接图唯一表示 连接图不能用唯一表示非线性流水线的工作流程 因此 引入流水线预约表 与流水线预约表对应的流水线连接图 一张预约表可能与多个流水线连接图相对应 一个流水线连接图对应与多张预约表 2 非线性流水线的冲突流水线的启动距离 连续输入两个任务之间的时间间隔流水线的冲突 几个任务争用同一个流水段 3 无冲突调度方法 由E S Davidson及其学生于1971年提出 非线性流水线的禁止启动集合 预约表中每一行任意两个 之间的距离都计算出来 去掉重复的 上例中为 3 4 6 由禁止启动集合得到冲突向量 C CmCm 1 C2C1 其中 m是禁止向量中的最大值 如果i在禁止向量中 则Ci 1 否则Ci 0 上例中C 101100 由冲突向量构造状态图 把冲突向量送入一个m位逻辑右移移位器 如果移位器移出0 用移位器中的值与初始冲突向量作 按位或 运算 得到一个新的冲突向量 否则不作任何处理 如此重复m次 对于中间形成的每一个新的冲突向量 也要按照这一方法进行处理 在初始冲突向量和所有的新形成的冲突向量之间用带箭头的线连接 当新形成的冲突向量出现重复时可以合并到一起 例 一条有4个功能段的非线性流水线 每个功能段的延迟时间都相等 它的预约表如下 1 写出流水线的禁止集合和初始冲突向量 2 画出调度流水线的状态图 3 求流水线的最小启动循环和最小平均启动距离 4 求平均启动距离最小的恒定循环 解 1 禁止集合为 2 4 6 初始冲突向量 101010 2 初始冲突向量逻辑右移2 4 6位时 不作任何处理 逻辑右移1 3 5和大于等于7时 要进行处理 初始冲突向量右移1位之后 010101 101010 111111 初始冲突向量右移3位之后 000101 101010 101111 初始冲突向量右移5位之后 000001 101010 101011 初始冲突向量右移7位或大于7位后 还原到它本身 中间冲突向量101111右移5位之后 000001 101010 101011 中间冲突向量101011右移3位之后 000101 101010 101111 中间冲突向量101011右移5位之后 000001 101010 101011 预约表与状态图是唯一对应 但不同的预约表也可能有相同的状态图 简单循环 状态图中各种冲突向量只经过一次的启动循环 简单循环的个数是有限的 由简单循环计算平均启动距离 3 最小的启动循环为 1 7 和 3 5 平均启动距离为4 4 启动距离最小的恒定循环是 5 4 优化调度方法L E Shar于1972年提出流水线最小平均启动距离的限制范围 1 下限是预约表中任意一行里 的最多个数 2 小于或等于状态图中任意一个简单循环的平均启动距离 3 最小平均启动距离的上限是冲突向量中1的个数再加上1 1992年 L E Shar又证明了上述限制范围 最有用的是第1条 预约表中 最多的行一定是瓶颈流水段采用预留算法来调度非线性流水线 可以达到最优调度 1 确定最小平均启动距离 MAL 预约表任一行中 的最多个数 2 确定最小启动循环 一般恒定循环作为最小启动循环 3 通过插入非计算延迟段 修改预约表实现最小启动循环 对于上面的例子 最小平均启动距离为2 最小启动循环为恒定循环 2 任一行中与第1个 的距离为2的倍数的周期都要预留出来 每一行中与第1个 的距离为2的倍数的位置都要预留出来 S3行的第2个 从周期5延迟到周期6 为此 S2行的第2个 要向后延迟一个周期 从周期6延迟到周期7 S1行的第2个 要向后延迟一个周期 从周期7延迟到周期8 实际上 只要在流水段S4的输出端到流水段S3的输入端中间插入一个非计算延迟D1 在非线性流水线中 最多的流水段一定是 瓶颈 流水段 实现最优调度的目标是使 瓶颈 流水段处于忙碌状态 没有空闲周期 最优调度方法能够使非线性流水线的吞吐率 加速比和效率达到最优 动态调度方法 一个启动循环C 从C推导出各个起始之间所有可能的时间间隔集合Gc 称为启动间隔集合C 2 3 2 5 Gc 2 3 5 7 9 10 14 15 17 19 21 22 24 26 间隔并不限于两个相邻的起始取Gc modp p为循环周期 P 12的循环C 2 3 2 5 Gc mod12 0 2 3 5 7 9 10 在禁止起动集合为F的流水线中 iff F modp Gc modp 时周期为p和启动间隔集合Gc的启动循环C才是可以允许的 高级流水线技术 超标量流水线超流水线超标量超流水线 超标量处理机 基本结构单发射与多发射多流水线调度资源冲突超标量处理机性能 三种主流处理机 超标量处理机 Intel公司的i860 i960 Pentium处理机 Motolora公司的MC88110 IBM公司的Power6000 SUN公司的SPARC SuperSPARC UltraSPARC等 超流水线处理机 SGI公司的MIPSR4000 R5000 R10000等 超标量超流水线处理机 DEC公司的Alpha等 基本结构一般流水线处理机 一条指令流水线 一个多功能操作部件 每个时钟周期平均执行指令的条数小于1 多操作部件处理机 一条指令流水线 多个独立的操作部件 可以采用流水线 也可以不流水 多操作部件处理机的指令级并行度小于1 超标量处理机典型结构 多条指令流水线 先进的超标量处理机有 定点处理部件CPU 浮点处理部件FPU 图形加速部件GPU 大量的通用寄存器 两个一级Cache 超标量处理机的指令级并行度 ILP 大于1 Motorola公司的MC88110 有10个操作部件 两个寄存器堆 整数部件通用寄存器堆 32个32位寄存器 浮点部件扩展寄存器堆 32个80位寄存器 缓冲深度为4的先行读数栈 缓冲深度为3的后行写数栈 两个独立的高速Cache中 各为8KB 采用两路组相联方式 转移目标指令Cache 存放一条分支上的指令 单发射与多发射单发射处理机 每个周期只取一条指令 只译码一条指令 只执行一条指令 只写回一个运算结果 取指令部件和指令译码部件各设置一套 只设置一个多功能操作部件或设置多个独立的操作部件 操作部件中可以采用流水线结构 也可以不采用流水线结构 目标是每个时钟周期平均执行一条指令 ILP的期望值为1 多发射处理机 每个周期同时取多条指令 同时译码多条指令 同时执行多条指令 同时写回多个运算结果 需要多个取指令部件 多个指令译码部件和多个写结果部件 设置多个指令执行部件 有些指令执行部件采用流水线结构 目标是每个时钟周期平均执行多条指令 ILP的期望值大于1 超标量处理机 一个时钟周期能同时发射多条指令的处理机必须有两条或两条以上能够同时工作的指令流水线 先行指令窗口 能够从指令Cache中预取多条指令 能够对窗口内的指令进行数据相关性分析和功能部件冲突检测 先行指令窗口的大小 一般为2至8条指令 目前的指令调度技术 每个周期发射2至4条指令比较合理 例如 Intel公司的i860 i960 Pentium Motolora公司的MC88110 IBM公司的Power6000等每个周期都发射两条指令 TI公司生产SuperSPARC PentiumIII每个周期发射三条指令 操作部件的个数一般多于每个周期发射的指令条数 通常为4个至16个操作部件 超标量处理机的指令级并行度 1 ILP m m为每个周期发射的指令条数 多流水线调度多条流水线的调度问题是一个NP完全问题 顺序发射 in orderissue 与乱序发射 out orderissue 指令发射顺序是按照程序中指令排列顺序进行的称为顺序发射顺序完成 in ordercompletion 与乱序完成 out ordercompletion 指令完成顺序是按照程序中指令排列顺序进行的称为顺序完成多流水线的调度主要有三种方法 顺序发射顺序完成 顺序发射乱序完成 乱序发射乱序完成 I1 LOADR1 A R1 A I2 FADDR2 R1 R2 R2 R1 I3 FMULR3 R4 R3 R3 R4 I4 FADDR4 R5 R4 R4 R5 I5 DECR6 R6 R6 1I6 FMULR6 R7 R6 R6 R7 1 顺序发射顺序完成6条指令按顺序分三个时钟周期发射 共用10个时钟周期完成 除了流水线的装入和排空部分之外 还有8个空闲的时钟周期 2 顺序发射乱序完成与顺序发射顺序完成调度方法相比 少了5个空闲时钟周期 6条指令总的执行时间为9个时钟周期 与顺序发射顺序完成调度方法相比节省了一个时钟周期 3 乱序发射乱序完成 必须使用先行指令窗口 除了装入和排空之外 没有空闲周期 功能部件得到充分利用6条指令总的执行时间缩短为8个周期 比顺序发射顺序完成方法节省2个周期 比顺序发射乱序完成方法相比节省一个周期 资源冲突如果操作部件采用流水线结构 发生资源冲突的可能性很小 如果不采用流水线结构 发生资源冲突的可能性就大 下面是一个由4条指令程序的程序 I1 FADDR0 R1 R0 R0 R1 I2 FMULR2 R3 R2 R2 R3 I3 FADDR4 R5 R4 R4 R5 I4 FMULR6 R7 R6 R6 R7 操作部件不采用流水线 做完4条指令总共用了11个周期 有5个空闲周期 操作部件采用流水线 做完4条指令共用8个周期 少用3个周期 在超标量处理机中 操作部件采用流水线结构的原因分析假每个周期发射m条指令 操作部件的延迟时间为k个周期 如果操作部件不采用流水线结构 则使用同一个操作部件的两条指令的序号应该至少相差m k 如果操作部件采用k个功能段的流水线结构 则使用同一个操作部件的两条指令的序号只需要相差m或m以上 指令流水线的段数k一般在4至10之间 每个时钟周期发射的指令条数m在2至4之间 取中间值 k 7 m 3 为了不发生资源冲突 如果操作部件不采用流水线结构 两条使用同一个功能部件的指令序号必须相差21或21以上 如果操作部件采用流水线结构 两条使用同一个功能部件的指令序号只需要相差3或3以上 因此 在超标量处理机中 操作部件一般要采用流水线结构如果由于某种原因 操作部件不能采用流水线结构 则必须设置多个相同种类的操作部件 普通标量处理机 希望相同操作连续出现 只有连续出现相同操作的指令序列时 流水线才能不 断流 功能部件的效率才能得到充分发挥 超标量处理机则正好相反 希望相同操作不要连续出现 相同操作的指令序列连续出现时 会发生资源冲突 要求相同操作的指令能够相对均匀地分布在程序中 超标量处理机的这种要求正好符合一般标量程序的特点 超标量处理机性能单流水线普通标量处理机的指令级并行度记作 1 1 超标量处理机的指令级并行度记作 m 1 超流水线处理机的指令级并行度记作 1 n 而超标量超流水线处理机的指令级并行度记作 m n 在理想情况下 N条指令在单流水线标量处理机上的执行时间为 T 1 1 k N 1 t在每个周期发射m条指令的超标量处理机上执行的时间为 T m 1 k t超标量处理机相对于单流水线标量处理机的加速比为 S m 1 超标量处理机的加速比的最大值为 S m 1 MAX m 超流水线处理机 两种定义 在一个周期内能够分时发射多条指令的处理机指令流水线的功能段数为8段或超过8段的流水线处理机提高处理机性能的不同方法 超标量处理机 通过增加硬件资源来提高处理机性能超流水线处理机 通过各部分硬件的重叠工作来提高处理机性能 两种不同并行性 超标量处理机采用的是空间并行性 超流水线处理机采用的是时间并行性 指令执行时序每隔1 n个时钟周期发射一条指令 即处理机的流水线周期为1 n个时钟周期 在超标量处理机中 流水线的有些功能段还可以进一步细分 例如 ID功能段 可以再细分为 译码 读第一操作数和读第二操作数三个流水段 典型处理机结构MIPSR4000处理机 每个时钟周期包含两个流水段 是一种很标准的超流水线处理机结构 指令流水线有8个流水段 有两个Cache 指令Cache和数据Cache的容量各8KB 每个时钟周期可以访问Cache两次 因此在一个时钟周期内可以从指令Cache中读出两条指令 从数据Cache中读出或写入两个数据 主要运算部件有整数部件和浮点部件 如果在LOAD指令之后的两条指令中 任何一条指令要在它的EX流水级使用这个数据