第 3 章 流水线技术_标量.ppt

2020 1 31 1 第3章流水线技术 标量流水部分 2020 1 31 2 本章学习内容 标量流水的基本概念和工作原理标量流水的性能分析流水操作中存在的主要障碍和解决方法流水调度方法 2020 1 31 3 3 1重叠操作和先行控制 简述 1 顺序解释方式一条指令完全解释执行完毕后 才开始对下一条指令进行解释执行 设把一条指令解释分为取数 分析和执行三个阶段 则 若各阶段周期均为t0 则顺序解释n条指令 需时间T 3nt0 2020 1 31 4 2 重叠解释方式在两条相邻指令的解释过程中 某些不同解释阶段在时间上存在重叠部分 这样在一条指令解释执行完成之前就可以开始下一条指令的解释工作 重叠方式1设各阶段周期均为t0 则执行n条指令共需T 2nt0 t0 2n 1 t0 t0 t0 t0 t0 2020 1 31 5 重叠方式2设各阶段周期均为t0 则执行n条指令共需T nt0 2t0 n 2 t0重叠方式缩短了程序的执行时间 提高了功能部件的利用率 但需增加硬件支持 t0 t0 t0 2020 1 31 6 一次重叠工作方式 任何时候只允许上条指令的 执行 与下条指令的 分析 相重叠的工作方式称为 一次重叠 T n 1 t0 t0 t0 2020 1 31 7 采用一次重叠工作方式 完成n条指令所需的执行时间为 T n 1 t0 当取指和分析部件的执行时间不等时 执行时间短的部件 必须等待执行时间长的部件功能的完成 导致部件的空闲 使得完成n条指令所需的执行时间变为 2020 1 31 8 执行时间不等时的一次重叠工作方式 2020 1 31 9 3 先行控制方式 先行控制方式的基本思想 通过设置先行读数栈 先行操作栈 后行写数栈等 使分析部件和执行部件能够分别连续不断地分析和执行指令 2020 1 31 10 理想情况下 指令执行部件应该一直忙碌 连续执行n条指令的时间为 2020 1 31 11 先行控制的基本结构 主存 存储器控制器 先行指令栈 先行读数栈 指令分析器 后行写数栈 运算控制器 运算器 取指 读数 写数 先行操作栈 通用寄存器组 通道 2020 1 31 12 三个独立的控制器 存储控制器 指令控制器 运算控制器 四个缓冲栈 先行指令缓冲栈 先行读数缓冲栈 先行操作栈 后行写数栈 2020 1 31 13 3 2标量流水处理技术 3 2 1流水方式把一个重复的过程分为若干个子过程 每个子过程都可以有效地在其专用功能段上与其它子过程同时执行 例 把指令的执行过程分成取指 译码 执行 访存和写回寄存器五个子过程 并用五个子部件分别处理这五个子过程 取指 译码 执行 访存 写回 输入 输出 s1 s2 s3 s4 s5 IF ID EX MEM WB 2020 1 31 14 流水处理的时空图 2020 1 31 15 流水处理机的基本结构 2020 1 31 16 如果每个流水段的延迟时间 通过时间 均为 ts 锁定时间为 tl 则每功能段的处理时间 ti为 ti ts tl流水处理机的最高工作频率为 若每个流水段的延迟时间不等 则最高工作频率为 2020 1 31 17 一条流水线通常由若干个有联系的流水段组成 流水线中的段数也称为 流水深度 每个流水段有专门的功能部件对指令进行某种加工 各流水段所需时间应尽量相等 以减少流水线的瓶颈影响 流水线工作阶段可分为建立 装入 满载和排空三个阶段 在理想情况下 当流水线充满后 每隔 t时间将会有一个结果流出流水线 流水技术的特点 2020 1 31 18 1 按处理级别分 部件级 运算操作流水线将复杂的算逻运算分段组成流水工作方式 例 将浮点加法操作分成求阶差 对阶 尾数相加 结果规格化四个子过程 3 2 2标量流水分类 简述 求阶差 对阶 尾数相加 规格化 输入 输出 s1 s2 s3 s4 2020 1 31 19 浮点加法器流水线的时空图 2020 1 31 20 处理机级 指令流水线把一条指令解释过程分成多个子过程组成流水工作方式 如前面所提到的将指令执行过程分为取指 译码 执行 访存及写回五个子过程 系统级 处理机間流水线 宏流水线 将系统中多个处理机串联起来 对同一数据流进行不同的处理 每个处理机完成某一专门任务 2020 1 31 21 2 按功能分 单功能流水线只完成一种固定功能的流水线 如浮点加法或乘法流水线 多功能流水线同一流水线的各功能段可进行不同的连接 使流水线在不同时间或同一时间内完成不同的功能 2020 1 31 22 多功能流水线 2020 1 31 23 静态流水线在同一时间内 流水线只能以一种功能方式工作 静态流水线可以是单功能的 也可以是多功能的 当是多功能流水线时 则从一种功能方式变为另一种功能方式时 必须先排空流水线 然后为另一种功能设置初始条件后方可使用 3 按工作方式分 2020 1 31 24 静态流水线的时空图 2020 1 31 25 动态流水线 在同一时间内 可以将流水线中的不同功能段连接成不同的功能子集 前提条件是功能部件的使用不发生冲突 以完成不同的运算功能 动态流水线必是多功能流水线 而单功能流水线则必是静态的 2020 1 31 26 动态流水线的时空图 2020 1 31 27 4 按连接方式分 线性流水线从流水线的输入到输出 每个功能段只允许经过一次 流水线中不存在反馈回路 一般的流水线均属于线性流水线 非线性流水线流水线各功能段之间除了串行连接外 还存在反馈回路 因此从流水线的输入到输出过程中 某些功能段将被数次通过 非线性流水线适合于进行线性递归的运算 2020 1 31 28 非线性流水线 流水线的流动顺序 S1 S2 S3 S2 S3 S4 S1 S2 反馈回路 2020 1 31 29 为了防止两条或两条以上的指令对同一功能段的争用 非线性流水线需要对输入流水线的指令进行比较复杂的控制 非线性流水线通常使用预约表来进行分析 2020 1 31 30 5 按任务流动方式分 顺序流动流水线输出端的任务流出与输入端的任务流入顺序完全相同 乱序流动流水线输出端的任务流出与输入端的任务流入顺序不完全相同 在乱序流动流水线中 当某任务阻塞时 后面的任务可绕过它继续流动 2020 1 31 31 6 Pentium的流水技术 在PentiumCPU内部有两个ALU 分别对应两条流水线U和V 80486只有一条流水线 U流水线执行整数和浮点数指令 V流水线执行整数指令 以及交换寄存器的内容 所以 Pentium能在每个时钟周期内执行两条整数运算指令 或在每个时钟周期内执行一条浮点数运算指令 U V两条指令流水线的段数都含有如下所示的5段 PFD1D2EXWB即 预取指令 PF 段 译码1 D1 段 译码2 D2 段 执行 EX 段和写回寄存器 WB 段 2020 1 31 32 2020 1 31 33 3 3流水线性能分析 1 吞吐率Tp单位时间内流水线能处理的任务数量或输出的结果数 设任务数为n 流水线段数为m 完成n个任务的时间为Tm 则吞吐率 最大吞吐率Tpmax流水线达到稳定状态后可获得的吞吐率 2020 1 31 34 实际吞吐率Tp流水线实际工作时的吞吐率 Tp Tpmax设在m段流水线中 各段的延迟时间均为 t 可以利用时空图分析该流水线完成n个任务的实际吞吐率和流水线的最大吞吐率 2020 1 31 35 S1 S2 S3 S4 输入 输出 t t t t t m t Tm n 1 t S 2020 1 31 36 完成n个任务所需的总时间 Tm n m 1 t完成n个任务的实际吞吐率 最大吞吐率 最大吞吐率就是流水线满载时的吞吐率 因此实际吞吐率为 2020 1 31 37 可见 实际吞吐率小于最大吞吐率 Tp Tpmax 只有当n m时 Tp Tpmax设完成一个任务需要的时间为T 则 m 或 t 都可以增加流水线的吞吐率 2020 1 31 38 如果流水线各段的延迟时间不等 则吞吐率取决于最慢段所需的时间 设 t1 t2 t4 t t3 3 t S1 S2 S3 S4 输入 输出 t1 t2 t3 t4 2020 1 31 39 t Tm n 1 t3 S 2020 1 31 40 完成n个任务的实际吞吐率 最大吞吐率 本题中Tmax 1 3 t 2020 1 31 41 流水线瓶颈问题的解决方法 将瓶颈子过程进一步细分成若干个子子过程 使每一个子子过程与其他子过程时间相等 如将瓶颈段S3进一步分成S3a S3b和S3c三个时间上相当于 t的子子过程 便可消除S3瓶颈 使最大吞吐率由1 3 t恢复成1 t 2020 1 31 42 t Tm n 1 t S 6 t 2020 1 31 43 在瓶颈段 并联设置多套功能段部件 使它们轮流工作 如在瓶颈段S3并联设置3套功能部件 可使吞吐率恢复到1 t 2020 1 31 44 重复设置功能段的控制复杂 需要在流水线中设置数据分配器和数据收集器 T 2020 1 31 45 2 加速比Sp 加速比是指采用流水方式后的工作速度与等效的顺序串行方式的工作速度之比 对n个求解任务 若用串行方式完成工作需要时间为Tl 用m段流水线完成工作需要时间为Tm 每个功能段的延迟时间为 t 则流水线的加速比为 最大加速比 2020 1 31 46 由最大加速比Spmax m可知 增加流水线的深度m 可以提高流水线的最大加速比 但只有在任务数n很大的情况下 才能有效地发挥流水线的效率 2020 1 31 47 例 对于4段流水线 当n 1时 Sp 1 当n 64时 Sp 3 8 若流水线个功能段的延迟时间不等 则加速比为 2020 1 31 48 3 效率E 效率是指流水线中的各功能段的利用率 由于流水线有建立和排空时间 因此各功能段的设备不可能一直处于工作状态 总有一段空闲时间 一般用流水线各段处于工作时间的时空区与流水线中各段总的时空区之比来衡量流水线的效率 2020 1 31 49 m t Tm n 1 t S t 2020 1 31 50 流水线的最大效率 当n 时 流水线的效率最高 若流水线各段的延迟时间不同 则效率为 2020 1 31 51 吞吐率 加速比和效率的关系 E Tp t Sp m效率是实际加速比和最大加速比之比 只有E 1时 才能达到Sp m当 t不变时 效率与吞吐率成正比 所以为提高效率所采用的方法 对提高吞吐率也有好处 2020 1 31 52 例1 设有浮点加法器流水线 试分析算式Z A B C D E F G H在流水线中执行时的流水线的性能 为提高运算速度 可采用算法 Z A B C D E F G H 1 2 3 4 一 二 求阶差 对阶 尾数加 规格化 被加数 输出和 t0 t0 t0 t0 加数 2020 1 31 53 2020 1 31 54 吞吐率 加速比 效率 2020 1 31 55 例2 设有静态加 乘双功能流水线 其中段1 2 3 4 6组成乘法流水线 1 5 6组成加法流水线 各段的延迟时间均为 t 流水线的输出可直接返回输入端或暂存到相应的缓冲寄存器中 现有A B两个向量 每个向量有四个元素 要求在此流水线上计算 请适当安排操作顺序 在最短时间内完成计算工作 并求出流水线工作时的实际吞吐率 加速比和效率 2020 1 31 56 2020 1 31 57 从图中可见 在总共17 t时间内榆出7个结果 因此该流水线的实际吞吐率为 Tp 7 17 t流水线的效率 E 3 4 t 5 3 t 6 17 t 27 102 9 34 26 4 若用串行方法完成上述的加乘操作 则需要做4次加法和3次乘法 求一次和需3 t 求一次积需5 t 总共需要时间 Tl 4 3 t 3 5 t 27 t所以加速比为 Sp Tl Tm 27 t 17 t 1 88 2020 1 31 58 例3 如图为一个有功能5段的非线性流水线 且任务每次经过第4段都必须再返回执行一次3 4段 现假定输入8个任务 求流水线的吞吐率和效率 解 1 时空图 2 Tp 3 E S1 S2 S3 S4 输入 输出 t t t t S5 t 2020 1 31 59 流水线效率较低的原因 多功能流水线在按某种功能流水时 总有一些本功能不需要的段将处于空闲状态 静态流水线在功能切换时 要等待前一种运算全部排空 才能重新连接 切换功能 需要有排空和建立两种不同功能流水的额外开销 经常发生下一步要等待上一步计算结果反馈的情况 即出现数据相关问题 任务数少时 建立和排空时间所占的比例大 流水线较适合于求解的操作相同 且输入 输出间相互独立的一大串运算 此时 流水线的吞吐率可接近于最大吞吐率 流水线效率可接近于1 而加速比也可接近于流水线的段数值 2020 1 31 60 流水线段数的选择 简述 如果流水线段数过多 时钟周期很小 以至于与时钟偏移和锁存器的附加开销相当 会导致在一个时钟周期内没有足够时间用于有效工作 流水线也就失去了作用 假设在非流水线的机器上采用顺序执行方式完成一个任务所需要的时间为t 那么 在同等速度的有k段流水线的机器上执行一个任务需要的时间为 d t k d 锁存器的延迟时间 2020 1 31 61 这样 流水线的最大吞吐率可以表示为 流水线的总价格粗略地估计为 C a b k 其中 a为所有流水段本身的总价格 b为每个锁存器的价格 A G Larson把流水线的性能价格比PCR定义为 2020 1 31 62 通过对自变量k求导 得到性能价格比PCR的极值 由于大于零的极值只有一个 因此 这个极值就是最大值 如图所示 当性能价格比PCR取得最大值时 它所对应的流水线的段数就时最佳段数k0 2020 1 31 63 式中 t为流水线的总的延迟时间 2020 1 31 64 在设计一条流水线的时候 可以根据上述极限公式 在流水线的总延迟时间t一定的情况下 通过调整流水线本身的价格a 锁存器的延迟时间d和锁存器的价格b来选取最佳的流水线段数k0 目前 一般处理机中的流水线段数在2段至10段之间 极少有超过15段的流水线 一般把8段或超过8段的流水线称为超流水线 采用8段以上流水线的处理机称为超流水线处理机 注 早期定5段之内为普通流水 2020 1 31 65 3 4流水操作中的主要障碍 要使流水线具有良好的性能 必须设法使流水线能畅通流动 即必须能做到充分流水 不发生断流 使流水断流的相关问题局部相关 指令执行过程中的资源冲突 数据相关 全局相关 控制相关 如转移指令 中断的处理 B0 B1 B2 基本块内无分支 是局部相关 块間为2路分支 是全局相关 2020 1 31 66 2020 1 31 67 在RISC处理机中 指令的流水设为5段 即分为取指 译码 执行 访存及写回五个子过程 如上图所示 2020 1 31 68 流水线实现逻辑图 实现描述形式 2020 1 31 69 指令 流水段 不同类型的指令在各段完成的操作不一样 下表列出了有关指令的操作 2020 1 31 70 下面讨论经典的RISC机5段流水线首先讨论在非流水情况下是如何实现的 2020 1 31 71 1 一条指令的执行过程 5个周期 取指令周期 IF IR Mem PC PC值加4 假设每条指令占4个字节 指令译码 读寄存器周期 ID 译码 用IR中的寄存器编号去访问通用寄存器组 读出所需的操作数 2020 1 31 72 执行 有效地址计算周期 EX 不同指令所进行的操作不同 存储器访问指令 ALU把所指定的寄存器的内容与偏移量相加 形成用于访存的有效地址 寄存器 寄存器ALU指令 ALU按照操作码指定的操作对从通用寄存器组中读取的数据进行运算 2020 1 31 73 寄存器 立即数ALU指令 ALU按照操作码指定的操作对从通用寄存器组中读取的第一操作数和立即数进行运算 分支指令 ALU把偏移量与PC值相加 形成转移目标的地址 同时 对在前一个周期读出的操作数进行判断 确定分支是否成功 存储器访问 分支完成周期 MEM 该周期处理的指令只有load store和分支指令 其他类型的指令在此周期不做任何操作 2020 1 31 74 load和store指令load指令 用上一个周期计算出的有效地址从存储器中读出相应的数据 store指令 把指定的数据写入这个有效地址所指出的存储器单元 分支指令分支 成功 就把转移目标地址送入PC 分支指令执行完成 2020 1 31 75 写回周期 WB ALU运算指令和load指令在这个周期把结果数据写入通用寄存器组 ALU运算指令 结果数据来自ALU load指令 结果数据来自存储器系统 在这个实现方案中 分支指令需要4个时钟周期 如果把分支指令的执行提前到ID周期 则只需要2个周期 store指令需要4个周期 其他指令需要5个周期才能完成 2020 1 31 76 2 5段流水线的两种描述方式 第一种描述 类似于时空图 2020 1 31 77 第二种描述 按时间错开的数据通路序列 2020 1 31 78 3 采用流水线方式实现时 应解决的问题 要保证不会在同一时钟周期要求同一个功能段做两件不同的工作 例如 不能要求ALU同时做有效地址计算和算术运算 避免IF段的访存 取指令 与MEM段的访存 读 写数据 发生冲突 可以采用分离的指令存储器和数据存储器 一般采用分离的指令Cache和数据Cache ID段和WB段都要访问同一寄存器文件 ID段 读WB段 写 前后半拍 2020 1 31 79 考虑PC的问题流水线为了能够每个时钟周期启动一条新的指令 就必须在每个时钟周期进行PC值的加4操作 并保留新的PC值 这种操作必须在IF段完成 以便为取下一条指令做好准备 需设置一个专门的加法器 但分支指令也可能改变PC的值 而且是在MEM段进行 这会导致冲突 2020 1 31 80 3 4 1资源冲突 结构冲突 资源相关 当有多条指令进入流水线后在同一机器周期内争用同一功能部件所发生的冲突 通常 由于数据和指令存放在同一存储器中 且只有一个访问口 这样便会发生这两条指令争用存储器资源的相关冲突 2020 1 31 81 两条指令同时访存造成资源相关 冲突 取指译码执行访存写回 2020 1 31 82 2020 1 31 83 解决资源冲突的办法 停顿一拍流水线 通常是将后一条指令停顿一拍后再启动 插入 气泡 再重复设置 个存储器 使指令和数据分别存放在不同存储器中 2020 1 31 84 使i 3指令停顿一拍进入流水线 以解决访存相关或重复设置一个存储器 2020 1 31 85 2020 1 31 86 3 4 2数据相关冲突 数据相关 相邻指令的数据存在一定的关系 如果不对数据相关进行处理 则流水时会产生错误 在乱序流动方式中 可能发生三种数据相关k LOADF1 A F1 A k 1 FADDF2 F1 F2 F2 F1 k 2 FMULF1 F3 F1 F1 F3 k 3 STOREF1 B B F1 写写相关 写读相关 读写相关 2020 1 31 87 1 写读相关 指令k与指令k 1之间关于F1的相关 又称为数据相关 先写后读相关 流相关 WR相关 RAW相关等 2 读写相关 指令k 1与指令k 2之间关于F1的相关 变量名相关 先读后写相关 反相关 RW相关 WAR相关等 3 写写相关 指令k与指令k 2左边的F1之间的相关关系称为 输出相关 写写相关 WW相关 WAW相关或写后再写相关等 2020 1 31 88 三种数据相关可以用下列关系式来表示 对于写读 RAW 相关D i S j 对于读写 WAR 相关S i D j 对于写写 WAW 相关D i D j 2020 1 31 89 三种数据相关的重定向 内部定向原理 重定向之前 j只能在i之后执行 重定向之后 可以做到 1 写读相关 j与i可以同时执行即专用数据通路 2 写写相关 先后顺序无关 3 读写相关 先后顺序无关后两种情况又称为 变量换名技术 2020 1 31 90 2020 1 31 91 变量换名技术 用来自动消除读写数据相关和写写数据相关规则 一个变量只允许定值一次在三种数据相关中 实际上只有写读数据相关必须依靠硬件 或采用软硬件结合的方法来解决解决方法 推后处理或专用数据通路在上面的数据重定向图中 把B换成了B 并在以后的都引用B 读写数据相关和写写数据相关就不存在了 下面具体讨论三种数据相关的解决办法 2020 1 31 92 1 先写后读相关 RAW 后面指令对某单元或寄存器的读出先于前面指令对同一单元或寄存器的写入 例 设流水线要执行以下的两条指令 ADDR1 R2 R3 R2 R3 R1SUBR4 R1 R5 R1 R5 R4 2020 1 31 93 又如 DADDR1 R2 R3DSUBR4 R1 R5XORR6 R1 R7ANDR8 R1 R9ORR10 R1 R11 2020 1 31 94 2020 1 31 95 解决数据相关的办法 时间后推法遇到数据相关时 就停顿后继指令的运行 直至前面指令的结果生成并写入寄存器 时间后推法将使流水线有较长的停顿 2020 1 31 96 采用定向技术 旁路技术或相关专用通路技术 在执行过程中建立直接的专用通道 将执行结果直接送往需要的执行部件 2020 1 31 97 IF ID EX MEM WB IF ID EX MEM WB IF ID EX MEM WB IF ID EX MEM WB IF ID EX MEM WB DADDR1 R2 R3 DSUBR4 R1 R5 ANDR6 R1 R7 ORR8 R1 R9 XORR10 R1 R11 定向传递R1值 数据相关和定向传递指令 2020 1 31 98 DADDR1 R2 R3 DSUBR4 R1 R5 ANDR6 R1 R7 ORR8 R1 R9 XORR10 R1 R11 定向传递R1值 减少定向传送次数的方法 在ID段读寄存器堆操作安排在后半部分 在WB段写寄存器堆操作安排在前半部分 以减少定向传输操作 2020 1 31 99 2020 1 31 100 ALU运算结果 写RF RF 读RF ALU操作数寄存器 专用通路 旁路 寄存器堆RF 多路开关 多路开关 ALU R4 R1 缓冲寄存器 R1 R4 旁路 2020 1 31 101 乱序流动的流水线中的数据相关 简述 乱序流动的流水线允许后进入流水线的指令超过先进入流水线的指令先流出流水线 2 先读后写相关 WAR 后面指令对某单元或寄存器的写入先于前面指令对同一单元或寄存器的读出 例 MULR1 R2 R3 R2 R3 R1SUBR2 R3 R4 R3 R4 R2若因乱序流动使SUB指令提前执行 写入R2 则会使MUL指令读R2时读到错误的R2的数据 2020 1 31 102 3 写后写相关 WAW 后面指令对某单元或寄存器的写入先于前面指令对同一单元或寄存器的写入 例 iMULR0 R1 R4 R1 R4 R0i 1ADDR6 R5 1 R5 1 R6i 2MULR2 R0 R3 R0 R3 R2i 3SUBR3 R4 1 R4 1 R3i 4MOVR2 R5 R5 R2 R0先写后读相关 RAW R3先读后写相关 WAR R2写后写相关 WAW 2020 1 31 103 4 RISC机流水线中的装入延迟 LOADR1 32 R6 ADDR4 R1 R7SUBR5 R1 R8ANDR3 R1 R10 又称LOAD相关 LOAD操作的执行时间可能比较长 可能导致无法定向 2020 1 31 104 无法定向的问题 2020 1 31 105 装入延迟的解决方法 方法一 由编译器在LOAD之后插入不发生数据相关的指令 由于LOAD的执行时间不确定 不能根本解决问题 称为指令调度或流水线调度 例如请为下列表达式生成没有暂停的指令序列 A B C D E F 假设载入延迟为1个时钟周期 2020 1 31 106 2020 1 31 107 方法二 由硬件自动插入空操作 直到LOAD操作完成 在单条流水线处理机中 也可以停止节拍发生器 直到数据从存储器中读出为止 流水线互锁机制 2020 1 31 108 流水线互锁机制插入气泡后的执行过程 2020 1 31 109 插入停顿前后的流水线时空图 2020 1 31 110 3 4 3控制转移冲突 控制相关主要是由转移指令引起的 是一种全局性的相关 当转移发生时 将使流水线的连续流动受到破坏 因此比起数据相关来 控制相关会使流水线丧失更多的性能 使流水线的吞吐率和效率严重下降 2020 1 31 111 假定所有执行指令中有25 指令为转移指令 进一步假设其中有2 3是会发生转移的 由于这些转移发生的指令 使得完成一条指令平均需要 0 75 1 0 25 1 3 1 2 3 3 1 1 5周期 2020 1 31 112 正常程序的流水线吞吐率 有转移程序时的流水线吞吐率 使流水线的性能降低 2020 1 31 113 解决控制相关的方法 1 静态转移预测当流水线译码出某指令为条件转移指令时 在其所需的条件码建立之前 先将一个方向猜测为成功路径 通常是选取发生概率较高的路径 并在转移条件码生成之前只对这个方向上的若干条指令进行预取 译码和取操作数 按该方向继续流动 若猜测失败 必须返回原分支点重新执行另一分支方向 2020 1 31 114 2020 1 31 115 2 提前判别转移是否发生 尽早生成转移目标地址 加快方法 加快和提前形成条件码 如在乘除指令中 可以在乘除运算之前根据操作数的符号获得结果的符号 将转移指令中形成转移目标地址送PC的操作提前 2020 1 31 116 例如 将原来需在MEM段进行的目标地址的计算 以及当条件成立时将转移目标地址送往PC的动作提前到ID段完成 这样就可使因转移指令而造成的流水线的停顿时间由3个节拍减少到1个 2020 1 31 117 3 加快短循环程序的处理 短循环程序 循环段中的指令数目少于指令缓冲器长度 如果将短循环段全部放入指令缓冲器中 就可在整个短循环程序段执行过程中不必再访问主存 而只需重复执行这一循环段 从而可加快执行速度 2020 1 31 118 4 提高转移方向的猜准率 简述 动态转移预测 根据转移历史预测转移方向 静态转移预测方法不考虑转移历史 动态转移预测方法考虑了转移历史 因而有较高的猜准率 一种具有较高猜准率的动态方法是考虑以前两次转移的历史 2020 1 31 119 2020 1 31 120 TT 11 TN 10NT 01 NN 00这种方法仅当两次连续猜错时 预测状态才会发生改变 如从11状态变为10 再变为00 这种方法的猜准率经在RISC机上实际测试可高达83 2020 1 31 121 5 采用延迟转移技术 简述 在转移延迟槽中安排有用的指令 利用有效的软件手段减少由于控制相关而造成的流水线性能下降 将转移指令前的指令调入转移延迟槽内执行 当然转移指令必须与调入的指令不相关 例 ADDR0 R1 R2BRANCHLBRANCHLADDR0 R1 R2 2020 1 31 122 将转移目标处的指令调入转移延迟槽内执行 例 BRANCHLBRANCHLSUBR4 R5 R6 L SUBR4 R5 R6L SUBR4 R5 R6转移成功时 此方法有效且不破坏程序的正确性 当转移不发生时 指令L的执行结果应对其他指令没有影响 因为程序其余部分也有可能转移到L 所以一般仍需将指令L在原处保存 2020 1 31 123 将转移不发生时应该执行的指令调入转移延迟槽内执行 例 BRANCHLBRANCHLSUBR4 R5 R6SUBR4 R5 R6 L L 转移不成功时 此方法有效且不破坏程序的正确性 当转移发生时 该指令的执行结果应对其他指令没有影响 2020 1 31 124 2020 1 31 125 方法 的效果最好 总能使性能获得改善 但若转移指令中所用到的条件判别与转移指令前的那条指令相关时 则不能使用 方法 仅当转移发生时才会改进性能 由于要将该指令复制 造成存储空间占用的增加 此方法适于转移发生概率较高的场合 如循环程序段 方法 仅当转移不发生时才会改进性能 三种方法的比较 2020 1 31 126 方法 和方法 都要求 当转移按另一方向前进时 执行调入延迟槽中指令不会破坏程序的正确执行 实验表明 大约有一半以上的转移延迟槽中可调入指令 其余只能填入NOP空操作指令 其中的80 将做有用的工作 2020 1 31 127 3 5流水的实现和控制 3 5 1流水线的中断处理流水线中处理中断的关键问题 如何保护断点 现场以及中断后如何恢复运行 2020 1 31 128 1 不精确断点法 不论在第i条指令中的哪个流水功能段上发生中断请求 都不再允许此时未流入流水线的后继指令进入流水线 但已在流水线中的所有指令 允许它们继续流动到执行完毕 然后再去执行中断处理程序 2020 1 31 129 2020 1 31 130 2 精确断点法 不论在第i条指令的哪个流水功能段上发生的中断请求 流水线均停止流动 用大量后援寄存器保存所有现场 即中断处理程序对现场的处理是精确对应第i条指令的 在第i条之后已进入流水线的所有指令的原有现场 在中断处理完毕后都能恢复 2020 1 31 131 3 5 2非线性流水线的调度 例 分析以下非线性流水线完成5个任务时的性能 S1 S2 S3 S4 输入 输出 t0 t0 t0 t0 t S 2020 1 31 132 吞吐率 加速比 效率 2020 1 31 133 功能段的使用冲突 功能段的使用冲突 几个任务同时争用同一流水段 为了避免冲突 需要延迟输入新任务进入流水线 非线性流水线的调度 找出一个最小的循环周期 按此周期向流水线输入任务 既不产生功能冲突 又可以获得最高的吞吐率和效率 非线性流水线主要依据 预约表 来规划调度方案 2020 1 31 134 非线形流水线的连接图和预约表 2020 1 31 135 一张预约表可能与多个流水线连接图相对应 2020 1 31 136 一个流水线连接图对应与多张预约表 2020 1 31 137 非线性流水线的基本调度方法 2020 1 31 138 1 根据流水线的连接图和一个任务通过流水线的顺序列出预约表 2020 1 31 139 预约表中的冲突情况 1 2020 1 31 140 预约表中的冲突情况 2 2020 1 31 141 2020 1 31 142 启动距离 等待延迟时间 向一条非线性流水线的输入端连续输入两个任务之间的时间间隔称为非线性流水线的启动距离 InitiationInterval 或等待时间 Latency 启动距离通常用时钟周期数来表示 它是一个正整数 若启动距离是n 表示两次输入之间需隔n个时钟周期 2 根据预约表建立禁止表 2020 1 31 143 禁止启动距离当以某一个启动距离向一条非线性流水线连续输入任务时 可能在某一个流水段 或某几个流水段中发生有几个任务同时争用同一个流水段的情况 这种情况就是非线性流水线中的冲突 collision 引起功能部件冲突的启动距离为禁止启动距离 即预约表中同一行中两个 之间的距离 S1的冲突9 1 8 t9与t1的节拍差 S2的冲突3 2 1 8 2 6 8 3 5 2020 1 31 144 S4的冲突6 5 1 禁止表 所有禁止启动距离构成的集合 上图中 F 1 5 6 8 或称为禁止向量F 1 5 6 8 即要想避免冲突 相邻两个任务进入流水线的间隔拍数就一定不能为1 5 6 8拍 最大禁止启动距离 n K K是多个任务通过流水线争用同一个部件的最大时间间隔 2020 1 31 145 允许启动距离在非线性流水线中的所有功能段 任何时刻都不会引起部件功能冲突的启动距离 4 启动循环使非线性流水线的任何一个流水段在任何一个时钟周期都不发生冲突的循环数列称为非线性流水线的启动循环 只有一个启动距离的启动循环又称为恒定循环 2020 1 31 146 3 由禁止表形成原始冲突向量 冲突向量 一个n位的位向量C Cn Cn 1 C2 C1 Ci 0 允许输入 Ci 1 禁止输入n 最大禁止启动距离原始冲突向量 由禁止表直接形成的冲突向量 如根据禁止表F 1 5 6 8 得到的原始冲突向量为 C 10110001 注意 Cn总为1因为冲突向量中的C2 C3 C4和C7均为0 所以第二个任务可距第一个任务2拍 3拍 4拍或7拍后流入流水线 2020 1 31 147 根据原始冲突向量 按允许启动距离输入下一任务 当该任务进入流水线后 将形成新的冲突向量 再根据新的冲突向量中按允许启动距离输入下一任务 就可以形成新的冲突向量 以便确定后续任务何时可输入 新的冲突向量的形成方法 根据现行冲突向量 选择允许启动距离i 将现行冲突向量右移i位 再与原始冲突向量相或 即可得到新的冲突向量 i值可以大于最大禁止距离 Cj SHR m Ck VC0 4 形成新的冲突向量 2020 1 31 148 流水线状态图 按新冲突向量的形成方法依次重复 一直进行到不再产生新的冲突向量 并形成闭合回路为止 即可得到流水线状态图 例 按原始冲突向量C0 10110001 形成的流水线状态图 C1 SHR 3 C0 VC0 00010110V10110001 10110111 2020 1 31 149 C2 SHR 2 C0 VC0 00101100V10110001 10111101C3 SHR 4 C0 VC0 00001011V10110001 10111011C4 SHR 2 C2 VC0 00101111V10110001 10111111 2020 1 31 150 10110001 000101101011000110110111 001011001011000110111101 000010111011000110111011 001011111011000110111111 7 7 7 7 7 3 3 4 4 2 2 C1 C3 C2 C4 2020 1 31 151 5 根据流水线状态图选择调度方案 流水线状态图中的每一个闭合回路都是一种调度方案 其中平均延迟时间最小者为最佳调度方案 闭合回路按简单循环构造 状态图中各种冲突向量最多只经过一次的启动循环 最佳调度方案 3 4 3 4 2020 1 31 152 采用最佳调度方案 3 4完成5个任务时 流水线的性能评价 实际吞吐率 Tp 5 23 t效率 E 10 15 5 10 5 t 5 23 t 9 23最大吞吐率 Tpmax 1 平均延迟 1 3 5 t t S 2020 1 31 153 不等间隔的调度方案平均延迟时间短 但控制复杂 为了简化控制 可采用间隔为7的调度方案 成为等间隔调度方案 但平均延迟时间增加了 可见 这种调度是无冲突调度 关键在于合理安排时序与控制部件 它是一种不改变流水线结构的调度方法 这些理论最早是由E S Davidson及其学生们于1971年提出来的 2020 1 31 154 无冲突调度举例 例 一条4功能段的非线性流水线 每个功能段的延迟时间都相等 它的预约表如下 2020 1 31 155 1 写出流水线的禁止向量和初始冲突向量 2 画出调度流水线的状态图 3 求最小启动循环和最小平均启动距离 4 求平均启动距离最小的恒定循环 2020 1 31 156 解 1 禁止向量为 2 4 6 初始冲突向量 C 101010 2 构造状态图C逻辑右移2 4 6位时 不作任何处理 逻辑右移1 3 5和大于等于7时 C右移1位之后 010101 101010 111111 C右移3位之后 000101 101010 101111 C右移5位之后 000001 101010 101011 C右移7位或大于7位后 还原到它本身 2020 1 31 157 101111右移5位之后 000001 101010 101011 101011右移3位之后 000101 101010 101111 101011右移5位之后 000001 101010 101011 2020 1 31 158 按照状态图得出如下的各种调度组合 3 最小的启动循环为 1 7 和 3 5 平均启动距离为4 4 启动距离最小的恒定循环为 5 2020 1 31 159 根据所选择的调度策略 可以得到如下的流水线工作状态表 2020 1 31 160 这些工作状态表也可以用时空图方式描述 理解前面例子中 非线性流水线的时空图 2020 1 31 161 3 5 3采用非计算延迟功能段进行优化调度 无冲突调度的问题当采用最小启动循环启动非线性流水线 流水线中的许多流水段还有空闲 反映在预约表中还有空白的格子 即使是最繁忙的流水段也还