z7流水线

第七章 流水线技术概述 计算机组成设计的基本任务之一是加快机器语言的解释和提高处理机执行指令的处理 速度，上述任务可以从三个方面实现：第一，通过对器件自身特性的改善，提高运算能力； 第二，采取更好的运算方法，提高指令内各微操作执行的并行程度，减少解释过程中所需要 的拍数等多项来加快整个机器指令的解释；第三，通过采用流水或多操作部件等处理技 术同时解释两条或多条指令的控制方式来加快整个机器语言程序的解释，提高指令的执行速 度。本章介绍指令流水线技术的基本知识，包括流水线的概念、示方法、流水线的特点、 流水线的分类、实例分析、线性流水线的性能分析以及指令级高度并行技术。 7.1 流水线的基本概念 1.流水线的概念 流水线处理技术并不是计算机领域所特有的技术。在计算机出现之前，流水线技术已经 在工业领域得到广泛应用，如空调装配生产流水线等。 计算机中的流水线技术是把一个复杂的任务分解为若干个子过程，每个子过程与其它子 过程并行运行。由于其运行方式和工业领域中的流水线处理技术十分类似，因此被称为流水 线技术。一般而言，从计算机自身特性出发，可以从两个方面来提高计算机内部的并行性： 一个是采用时间上的并行性，通过将一个任务能划分成几个不同的子过程，并且各子过程在 不同的功能部件上并行执行，使得在同一个时钟周期内同时解释多条机器语言指令，提高程 序的执行速度，这种方法即为流水线处理技术；另一个是采用空间上的并行性处理技术，即 在一个处理机内设置多个执行相同功能的独立操作部件，并且让这些操作部件并行工作，这 种处理机被称为多操作部件处理机或超标量处理机。 把流水线技术应用于指令的解释执行过程，就形成了指令流水线，如图 7.1 所示，指令 的执行过程分为取指、译码、执行、存储器访问、写回等 5个子过程，在每个子过程的后面 都需要有一个锁存器，以保证该子过程的执行结果给下一个子过程使用。把流水线技术应用 于运算的执行过程，就形成了运算操作流水线，也称为部件级流水线，如浮点数加法运算过 程可分解为求阶差、对阶、尾数加和规格化 4个子过程。 图 7.1 指令流水线 2.流水线的时空图表示方法 以指令流水线为例，其执行过程分为取指、译码、执行、存储器访问、写回 5 个子过程， 分别用 S1、S2、S3、S4 和 S5 表示。图 7.2 给出了指令流水线的时空图，图中，横坐标表示 时间，也就是连续任务输入到流水线到输出流水线所经过的时间，当流水线中各子过程的执 行时间相等时，横坐标被分割成相等长度的时间段；纵坐标表示空间，即流水线的各子过程 或对应的功能部件。在时空图中，流水线的每个子过程常被称为一个“功能段”。 图 7.2 指令流水线的时空图 从图 7.2 可以看出，流水线具有如下特点： (1) 流水线把一条指令的执行划分成若干个子过程，每个子过程由一个独立的专用功能 部件来执行，依靠执行不同功能的功能部件并行工作来提高系统的吞吐率和处理速 度。 (2) 流水线并不能改变单条指令的执行时间，但提高了系统整体吞吐率。因此只有大量 连续的任务不断输入到流水线中，保证在流水线的输出端有任务不断的从流水线中 输出，才能充分发挥流水线的性能； (3) 流水线需要有通过时间和排空时间。通过时间是指第一条指令从输入流水线到输出 流水线所经过的时间，排空时间是指最后一条指令流出流水线所花费的时间。 7.2流水线的分类 流水线可以从不同的角度，按照不同的观点进行多种不同的分类。 1.线性流水线和非线性流水线 根据流水线的结构，按照流水线中是否有反馈回路进行分类。线性流水线是将流水线的 各个段逐个串接起来，每个功能段有且只有一个输入和一个输出，没有反馈回路。非线性流 水线是指流水线中除了有串行连接外，还有反馈回路，允许流水线的某些功能段通过反馈回 路在一个任务的执行过程中被使用多次。如图 7.3 所示的非线性流水线，尽管其结构中仅包 含 S1、S2、S3、S4 功能段，但由于存在反馈回路，任务从输入到输出依次要流经 S1、S2、 S4、S3、S4、S1 各段，其中⊗代表多路选择开关。在非线性流水线中，一个重要的问题是 非线性流水线的调度问题，即如何确定两个或两个以上的连续任务最少相隔多少个时钟周期 连续的输入到流水线中，不会引起功能段的争用现象。 图 7.3 非线性流水线 2.单功能流水线和多功能流水线 按流水线的功能划分，可把流水线分为单功能流水线和多功能流水线。单功能流水线是 指流水线各段之间的连接是固定的，只能完成某种固定的功能，如 Cray-1 巨型机有 12 条单 功能流水线；多功能流水线是指流水线的各段在不同的时间或同一时间里按照不同的连接方 通过时间 排空时间 m⊿t (n-1)⊿t S1 S2 S3 S4输入 输出 式可以实现两种或两种以上的不同的功能，如美国 TI 公司的 ASC 处理机多功能流水线如图 7.4 所示，通过不同的连接方法可以实现定点乘、浮点加两种功能的运算。 （a）功能段 （b）浮点加 （c）定点乘 图 7.4 TI-ASC 的多功能流水线 3.静态流水线和动态流水线 按照工作方式划分，可把多功能流水线分为静态流水线和动态流水线。静态流水线是指 在同一时间内，多功能流水线的各段之间只能按照一种固定的方式连接，当流水线要切换到 另外一种功能的时候，必须等到执行前一种功能的任务全部流出流水线后，才能改变其连接 方式，如图 7.5 所示，多功能流水线必须等到浮点加任务全部流出流水线后，才能切换到执 行定点乘的流水线功能段的连接方式上。因此在静态流水线中，只有执行的是多个相同的任 务时，流水线的效率才能得到发挥。动态流水线是指在同一时间内，多功能流水线中的各段 可以按照不同的方式进行连接，同时执行多种不同的功能，前提是多功能流水线中的任何一 个功能段在同一时间仅能连接到执行一种功能的流水线中。如图 7.6 所示。显然，动态流水 线的效率比静态流水线的效率要高，但是由于动态流水线的调度策略和控制回路的耦合复杂 度很高，目前绝大多数的流水线均采用静态流水线的调度策略。 图 7.5 静态流水线时空图 输 入 求阶差 对 阶 尾数加 规格化 尾数乘 累 加 输 出 输 入 求阶差 对 阶 尾数加 规格化 尾数乘 累 加 输 出 输 入 求阶差 对 阶 尾数加 规格化 尾数乘 累 加 输 出 浮点加 定点乘 1 2 3 … … n-1 n 1 2 3 … … n-1 n 1 2 3 … … n-1 n 1 2 3 … n-1 n 1 2 3 … … n-1 n 1 2 3 … … n-1 n 1 2 3 4 1 2 3 1 2 1 输 入 求阶差 对 阶 尾数加 规格化 尾数乘 累 加 输 出 时间 空间 图 7.6 动态流水线时空图 4．顺序流水线和乱序流水线 按照流水线中任务输入和输出的顺序是否相同，可把流水线分为顺序流水线和乱序流水 线。顺序流水线是指任务输入到流水线的顺序与从流水线中输出的顺序完全一致；乱序流水 线是指任务输入到流水线的顺序与从流水线中输出的顺序可以不同，允许后流入到流水线的 任务先从流水线中输出。例如，在指令流水线中，有的指令需要到主存中读取操作数，有的 指令不需要到主存中读取操作数。由于到主存中读取操作数需要等待较长的周期，在没有数 据相关且指令的执行部件处于空闲状态的时候，可以让后序不需要在主存中读取操作数的指 令先执行，从而导致后流入到流水线中的指令先从流水线中输出。 5．功能部件级、处理机级及系统级流水线 按照流水线使用的不同级别，可把流水线分为功能部件级、处理机级、系统级等。功能 部件级流水线又称运算操作流水线，它是把复杂的算术运算操作按照流水的方式执行，如浮 点加法运算可被分为求阶差、对阶、尾数加和规格化 4 个子过程；处理机级流水线又称指令 流水线，它是把指令的执行过程按照流水的方式进行处理，即把一条指令的执行过程分解为 若干个子过程，每个子过程在独立的功能部件中执行，下一节将详细介绍指令流水线；系统 级流水线又称宏流水线，它是把多台处理机串接起来，构成流水线的各个功能段，对同一数 据流进行处理，每台处理机完成整个任务的一部分。前一台处理机的输出结果作为后一台处 理机的输入。 7.3流水线的性能分析 衡量线性流水线的主要技术指标是吞吐率、加速比和效率。 1．吞吐率 吞吐率是指单位时间内流水线所完成的任务数或输出结果的数量。 …………………………………………………（7-1） 其中，n 为任务数，Tk是处理 n 个任务所用的时间。 对于线性流水线，假定各功能部件执行子过程所花费的时间均相等，如图 7.7 所示，对 于一条 m 段流水线来说，在不考虑数据相关、部件相关、控制相关的提前条件下，连续输入 n 个任务，可以从两个方面来分析流水线执行 n个任务所需要的时间。从流水线的输出端看， 用 m 个时钟周期完成第一个任务，其余 n-1 个时钟周期，每隔一个时钟周期有一个任务从流 浮点加 定点乘 1 2 3 … … n-1 n 1 2 3 … … n-1 n 1 2 3 … … n-1 n 1 2 3 … n-1 n 1 2 3 … … n-1 n 1 2 3 … … n-1 n 1 2 3 4输 入 求阶差 对 阶 尾数加 规格化 尾数乘 累 加 输 出 时间 空间 1 2 3 4 5 6 7 1 2 3 4 5 6 1 2 3 4 5 水线中输出，即用 n-1 个时钟周期完成了后续的 n-1 个任务；从流水线的输入端看，用 n 个时钟周期完成任务的输入，另外的 m-1 个时钟周期作为流水线的排空时间。因此，流水线 执行 n 个连续任务所需要的时间为： ……………………………………………（7-2） 其中，⊿t 为时钟周期。 图 7.7 各段执行时间均相等的流水线时空图 将式（7-2）代入到式（7-1）中，可计算流水线的实际吞吐率为： ……………………………………（7-3） 这种情况下的最大吞吐率为： …………………………7-4） 从式（7-3）和（7-4）分析可知，流水线的实际吞吐率小于最大吞吐率，主要原因在于 任务有输入时间和排空时间，执行子任务的功能段不可避免的存在着“空闲”状态，所以只 有当 的时候，才有 。 当流水线的各段执行任务所花费的时间不相等的情况下，流水线中就存在着“瓶颈”段， 其情况就复杂多了。如图 7.8（a）所示，一个 5 段流水线中，其中第三段（S3）的执行时 间是其余各段执行时间的 3 倍，即第三段的执行时间是 3⊿t，其余各段的执行时间是⊿t。 由于流水线中第三段的执行时间最长，导致其它各段出现“阻塞”和“断流”的现象，我们 将该段称之为“瓶颈”段。图 7.8（b）所示的是该种情况下所对应的流水线时空图，其中 阴影部分表示流水线的功能段在这一时间内处于空闲状态。 （a）流水线 S1 S2 S3 S4输入 输出 S5 1 2 3 4 … n-1 n 1 2 3 … … n-1 n 1 2 3 … … n-1 n 1 2 3 … n-1 n 1 2 3 … … n-1 n S1 S2 S3 S4 S5 时间 空间 … 4 4 4 4 m⊿t (n-1)⊿t n⊿t (m-1)⊿t Tk (b) 时空图 图 7.8 各段执行时间不相等的流水线及其时空图 根据图 7.8 分析可知，流水线各段执行时间不相等时，其实际吞吐率为： …………………(7-5) 其中，⊿ti为流水线第 i 段执行任务所用时间，流水线共有 m 段，分母中第一部分为流 水线完成第一个任务所用的时间，第二部分为完成剩余的 n-1 个任务所用的时间。 在这种情况下，流水线的最大吞吐率为： ……………………………(7-6) 对于图 7.8 所示的案例，流水线的最大吞吐率为： …………………………………………(7-7) 依据式(7-6) 和 (7-7) 分析可知，当流水线各段执行时间不相等时，流水线的实际吞 吐和最大吞吐率的大小受限于流水线中执行时间最长的那个功能段，该功能段成为整个流水 线的“瓶颈”段。对图 7.8(b)的分析可知，除了瓶颈段一直处于满“负荷”工作状态外， 其余各段在许多时间都处于空闲状态，导致硬件资源利用率很低。 为了有效的解决流水线中存在的“瓶颈”段问题，主要有如下两种方法： (1) 细分瓶颈段 如图 7.9（a）所示，由于瓶颈段的执行时间是其余各段的执行时间的 3 倍，将瓶颈段 s3 细分为 3 个子流水线功能段 S3a、S3b、S3c，这样每个功能段或子功能段的执行时间均为⊿t， 流水线转换为各段执行时间均相等的流水线，其时空图如图 7.9（b）所示，流水线各段都 处于满“负荷”工作状态，流水线的最大吞吐率为 1/⊿t。 (a)细分瓶颈段的流水线 S1 S2 S3 S4 S5 时间 空间 Tk 1 2 3 n-1 n 1 2 3 … n-1 n (n-1)⊿t3 S1 S2 S3a S4输入 输出 S5 S3b S3c S3 1 2 3 … n-1 n … 1 2 3 … n-1 n 1 2 3 … n-1 n (b)时空图 图 7.9 细分瓶颈段的流水线及时空图 (2) 重复设置瓶颈功能段 如果由于结构等原因，流水线中的瓶颈段不能按照图 7.9（a）的方法进行细分，则可以 通过设置多个执行相同功能的瓶颈段的方法以消除瓶颈。重复设置的瓶颈段并行工作，交替 的为不同的任务所使用，如图 7.10（a）所示。从功能段 S2 输出到并列瓶颈段 S3a、S3b、S3c 输入之间，需要设置一个数据分配器，保证从功能段 S2 中输出的第一个任务分配给功能段 S3a，输出的第二个任务分配给功能段 S3b，第三个任务分配给功能段 S3c，之后以此类推。而 在瓶颈段 S3a、S3b、S3c的输出到功能 S4 的输入之间，需要设置一个数据收集器，依次分时地 将 S3a、S3b、S3c的输出收集到功能段 S4 的输入，改进后的流水线的最大吞吐率为 1/⊿t，其 时空图如图 7.10（b）所示。 （a） 重复设置瓶颈段流水线 （b）时空图 图 7.10 重复设置瓶颈段流水线及时空图 2.加速比 流水线的加速比是不使用流水线技术执行任务所用的时间与使用流水线技术执行相同 任务所用的时间之比。如果不使用流水线，即串行执行所使用的时间为 T0，使用流水线执行 1 2 3 4 … n-1 n 1 2 3 … … n-1 n 1 2 3 … … n-1 n 1 2 3 … n-1 n 1 2 3 … … n-1 n S1 S2 S3a S4 S5 时间 空间 … 4 4 4 4 1 2 3 n-1 n 1 2 3 … … n-1 n 4 4 S3b S3c S2 S3a S4输入 输出 S5 S3b S3c 1 2 3 4 5 7 8 1 S1 S2 S3a S4 S5 时间 空间 6 S3b S3c 9 1 2 3 4 5 7 86 9 4 7 2 5 8 3 6 9 1 2 3 4 5 7 86 9 S1 ∇t ∇t 3∇t ∇t ∇t 1 2 3 4 5 7 86 9 任务的时间为 Tk，则流水线的加速比为： KT TS 0= ……………………………………………（7-8） 如果流水线各功能段的执行时间都相等，则一条 m 段的流水线完成 n个任务所需的时间 如（7-2）式所示。而这 n 个任务如果串行执行，由于每个任务的执行时间为：m⊿t，则 n 个任务串行执行所需的总时间为：nm⊿t，故流水的实际加速比为： …………7-9） 这种情况下的最大加速比为： …………………………(7-10) 从式（7-10）分析可知，流水线的最大加速比等于流水线的功能段段数。从这个意义上 看，流水线的功能段段数越多越好。然而随着流水线段数的增多，要求连续输入的任务数也 会增加，由于程序中一般都存在着转移、跳转指令或中断、数据相关等情况，使得能够连续 输入的任务数 n 受到很大的限制，同时当功能段的段数增多的时候，流水线的控制复杂度、 电路实现的难度都呈耦合性增加，因而流水线的功能段的段数并非越多越好。 当流水线的各段执行时间不完全相等时，一条 m段线性流水线完成 n 个连续任务的实际 加速比为： …………………（7-11） 3.效率 效率是指流水线各段设备的利用率，即流水线中设备的实际使用时间与整个系统运行时 间的比值。由于流水线有通过时间和排空时间，因此各功能段的设备不可能一直处于满负荷 工作状态，总有一段空闲时间。从时空图上看，效率就是 n 个任务所占用的时空区与 m 个功 能段总的时空区之比，因此流水线的效率包括时间和空间两个方面的因素。 当流水线的各段执行时间都相等时，如图 7.7 所示，则流水线的效率为： ……………（7-12） 这种情况下的最大效率为： ………………………………………(7-13) 在各段执行时间不完全相等时，连续执行 n个任务，流水线的效率为： …………………………(7-14) 通常情况下，当我们需要去评估流水线的吞吐率、加速比和效率等性能指标时，可先画 出时空图，然后根据流水线性能指标的基本定义去计算，这种方法对于线性流水线、非线性 流水线、多功能流水线和任务不连续、各段执行时间不相等等情况均适用，是一种通用、直 观的方法。 7.4 流水线的性能分析举例 例 7.1 在图 7.8（a）所示的流水线上计算 ，假定流水线的输出可直接返回到流 水线的输入端或暂存于相应的流水线寄存器中，试计算流水线的吞吐率、加速比和效率。 解：首先，为了保证流水线的性能达到最优，应使流水线的各功能段尽可能处于满负荷工作 状态，并使求流水线的相关最少。采用“二叉树”算法分配任务的执行顺序，可保证任务之 间的相关性降为最小，即如图 7.11 所示。在本题中，由于元数据 Ai 之间没有任何的数据相 关性，故应先计算 A1+A2、A3+A4、A5+A6，作为前 3个任务输入到流水线中，而第 4 个任务的 源操作数之一为第 1 个任务的结果，必须等到第 1 个任务流出流水线以后，才能将第 4个任 务流入到流水线中，同理，第 5 个任务必须等到第 2、3 任务流出流水线以后才能流入到流 水线中，第 6 个任务须等到第 4、5 个任务流出流水线后才能流水到流水线中。在进行任务 分配时，为了尽快将新的任务输入到流水线中，第 4 个任务的两个源操作数应设置为任务 1 的执行结果和 A7，而不能是任务 1 的结果和任务 2 的结果进行相加，因为如果按照后一种方 法进行任务分配，任务 4为了等待任务 2 的输出结果，须延迟一个时钟周期才能输入到流水 线中。 图 7.11 任务调度图 其次，画出完成该计算的流水线时空图，如图 7.12 所示，图中阴影部分表示该功能段处 于空闲状态。 图 7.12 完成加运算流水线时空图 由图 7.12 可见，完成 6个任务，共花费了 17⊿t 的时间，故吞吐率为： A1 A2 A3 A4 A5 A6 A7 1 2 3 4 5 6 1 2 3 5 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 S1 S2 S3 S4 S5 时间 空间 4 6 6 6 6 6 1 2 3 4 5 7 86 9 10 11 12 130 14 15 16 17 AI AII AIII AIV AV A2 A4 A6 A7 AIII AV A1 A3 A5 AI AII AIV AVI 如果不采用流水线处理技术，每个任务的执行时间为 5⊿t，则完成 6个任务所需要的 总时间为 6×5⊿t=30⊿t，故加速比为： 而流水线的效率为： 例 7.2 设在图 7.4 所示的多功能流水线上，分别采用静态流水线的调度策略和动态流水线 的调度策略，计算 , 流水线的输出可直接返回到流水线的输入端或暂存于 相应的流水线寄存器中，试计算流水线的吞吐率、加速比和效率。 解：多功能静态流水线的调度策略：为了尽量减少任务切换次数和数据相关性，充分发挥流 水线的作用，计算的顺序应该是先做 5 个加法：A1+B1、A2+B2、A3+B3、A4+B4、A5+B5，然后再 做乘法。流水线的任务调度图如图 7.13 所示。 图 7.13 流水线任务调度图 依题意，元数据 Ai、Bi之间没有任何数据相关性，故 A1+B1、A2+B2、A3+B3、A4+B4、A5+B5， 可以作为前 5 个任务依次输入到流水线中，由于多功能静态流水线切换到另外一种功能的时 候，必须等到执行前一种功能的任务全部流出流水线后，才能改变其连接方式，因此只有等 前 5 个任务均流出流水线后，流水线才能切换到乘法功能，并依次启动任务 6、7流入到流 水线，而第 8 个任务的操作数是第 6个任务的结果，必须等到第 6 个任务流出流水线以后， 才能将第 8个任务流入到流水线中，同理，第 9 个任务必须等到第 7、8任务流出流水线以 后才能流入到流水线中。在进行任务分配的时候，为了尽快将新的任务输入到流水线中，第 8 个任务的两个源操作数应设置为任务 5 和任务 6 的执行结果，而不能是任务 6 的结果和任 务 7 的结果进行相乘，因为如果按照后一种方法进行任务分配，任务 8 为了等待任务 7 的输 出结果，须延迟一个时钟周期才能输入到流水线中。 画出完成该功能的流水线时空图，如图 7.14。 7 4 6 A1 B1 A2 B2 A3 B3 A4 1 2 3 8 B4 A5 B5 5 9 图 7.14 静态流水线时空图 由图 7.14 可见，完成 9个任务，共花费了 22⊿t 的时间，故吞吐率为： 如果不采用静态流水线处理技术，完成前五个加法任务需要时间 5×6⊿t，完成后 4 个 乘法任务需要时间 4×4⊿t，则完成 9 个任务所需要的总时间（5×6⊿t）＋（4×4⊿t） =46 ⊿t，故加速比为： 而流水线的效率为： 多功能动态流水线的调度策略：动态流水线在同一时间内，多功能流水线中的各段可以 按照不同的方式进行连接，同时执行多种不同的功能，所以不但要考虑数据相关，还要考虑 结构相关。动态流水线时空图如图 7.15。 CIX CVIIICVIICVICVCIVCIIICII CI B4 A4 B1 B2 B3 A1 A2 A3 1 2 3 4 5 7 86 9 10 11 12 130 14 15 16 17 浮点加 定点乘 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 6 7 8 9 6 7 7 6 7 6 输 入 求阶差 对 阶 尾数加 规格化 尾数乘 累 加 输 出 时间 空间 B5 A5 8 8 8 CV CIV CIII CII CI CVI 18 19 20 9 9 9 21 22 CVIII CVII CIX CVIIICVIICVICVCIVCIIICIICI B4 A4 B1 B2 B3 A1 A2 A3 1 2 3 4 5 7 86 9 10 11 12 130 14 15 16 17 浮点加 定点乘 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 1 2 3 4 5 6 7 8 9 6 7 7 6 7 6 输 入 求阶差 对 阶 尾数加 规格化 尾数乘 累 加 输 出 时间 空间 B5 A5 8 8 8 CV CIV CIII CII CI CVI 18 19 9 9 9 CVIII CVII 图 7.15 动态流水线的时空图 图 7.15 中,任务 6 最早只能在第 7个⊿t 时输入到流水线,因为任务 6 要处理的数据 CII 在第 6 个⊿t时结束时才流出流水线。图 7.15 中，完成 9 个任务，共花费了 19⊿t 的时间， 故吞吐率为： 如果不采用动态流水线处理技术，完成前五个加法任务需要时间 5×6⊿t，完成后 4 个 乘法任务需要时间 4×4⊿t，则完成 9 个任务所需要的总时间（5×6⊿t）＋（4×4⊿t） =46 ⊿t，故加速比为： 而流水线的效率为： 7.5流水线中的相关和冲突问题 要使流水线处于理想的运行状态，必须使流水线中不出现“阻塞”和“断流”的现象， 但由于流水线中存在着结构相关、数据相关和控制相关，导致流水线中不可避免的存在着“阻 塞”和“断流”的现象。相关是指两条指令之间存在着某种依赖关系，如前一条指令的执行 结果是后一条指令的源操作数。下面我们以经典的 5 段指令流水线为例，来描述流水线中存 在的相关和冲突问题以及解决方法。 7.5.1 经典 5 段 MIPS 指令流水线 一条指令的执行过程分为 5 个周期，分别为取指令周期（IF）、指令译码/读寄存器周期 （ID）、执行/有效地址计算周期（EX）、存储器访问/分支完成周期（MEM）、写回周期（WB）， 如图 7.16 所示。 图 7.16 经典 5段 MIPS 指令流水线 具体每个周期的功能如下： (1)取指令周期（IF） 根据程序计数器（PC）中存放的内容作为指令存放的地址从存储器中取出指令并存入指 令寄存器（IR），同时将 PC 中的值自动加“逻辑 1”，即如果指令的长度是 8 位，则 PC+1→ PC；如果指令的长度是 16 位，则 PC+2→PC；如果指令的长度是 32 位，则 PC+4→PC，以此 类推，指向下一条要执行指令的首地址； (2)指令译码/读寄存器周期（ID） 对于 MPIS 指令而言，由于采用固定字段译码方式，指令译码和读寄存器操作是并行执 行的。对指令进行译码，以指令中地址码的译码结果作为地址访问通用寄存器组，把读出的 Mem REG ALU Mem REG 锁 存 器 锁 存 器 锁 存 器 锁 存 器 IF ID EX MEM WB 操作数分别送入 ALU 的左路操作数寄存器和右路操作数寄存器。 (3)执行/有效地址计算周期（EX） 在这个周期，ALU 对 ID 周期准备好的操作数进行算术运算或逻辑运算，不同种类的指 令执行不同的操作： a) 存储器访问指令：ALU 把所指定的寄存器的内容与偏移量相加，形成访存的有效地 址； b) 寄存器-寄存器/立即数 ALU 指令：ALU 按照操作码指定的操作对从通用寄存器组读 出的数据或立即数进行有效运算； c) 分支指令：ALU 把偏移量与 PC 值相加，形成转移目标地址。同时，对在前一个周期 读出的操作数进行判断，确定分支转移是否成功。 (4)存储器访问/分支完成周期（MEM） 在这个周期，只有 load/store 指令和分支指令需要进行操作，其他指令不做任何操作。 对于 load/store 指令，就是用上一个周期计算出来的有效地址从存储器中读出相应的数据 或将指定的数据写入有效地址指定的存储单元；对于分支指令，如果前一个周期判断分支或 转移“成功”，就把目标地址送入 PC。 (5)写回周期（WB） 在这个周期，只有 ALU 运算指令和 load 指令需要进行写操作，将运算结果写入通用寄 存器组，其他指令不做任何操作。 分析上面的指令执行过程，IF 段和 MEM 段分别要对存储器进行读操作和写操作，ID 段和 WB 段分别要对通用寄存器组进行读操作和写操作，如果按照每隔一个时钟周期将一个新的 任务流入到流水线中，由于结构相关，不可避免的导致流水线中产生冲突，我们将在 7.5.2 节进行具体分析。 为了有效地描述任务的执行过程和由此导致的相关、冲突，我们采用另外一种时空图描 述，如图 7.17 所示。其中，横坐标依然表示时间，纵坐标是将所要执行的指令按序列出， 时空区所描述的是各流水段的名称。图 7.18 是以数据通路的快照形式所展现的时空图描述。 图 7.17 5 段流水线时间---指令时空图 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 1 2 3 4 5 6 7 8 9 时间 指令 指令 k 指令 k+1 指令 k+2 指令 k+3 指令 k+4 图 7.18 5 段流水线时间---指令数据通路时空图 7.5.2 流水线的冲突和相关 流水线相关是指两条指令之间存在着某种依赖关系。如果两条指令相关，则两条指令在 流水线中执行时，就不能重叠执行或只能部分重叠。相关包括数据相关、结构相关和控制相 关。流水线冲突是指流水线中由于相关的存在，导致流水线中出现“断流”或“阻塞”，后 一条指令不能在预期的时钟周期流入到流水线中。冲突包括结构冲突、数据冲突和控制冲突。 1.结构冲突 由于多条指令在同一时钟周期都需使用同一操作部件而引起的冲突被称为结构冲突。如 流水线只有一个存储器，数据和指令都放在这个存储器中。在这种情况下，当执行 load 指 令需要访存取数时，而同时又要完成其后某条指令的“取指令”操作，此时就发生访存冲突， 如图 7.19 所示。为了消除这一冲突，在流水线中插入一个“气泡”，停顿一个时钟周期，等 到 load 指令访问存储器操作结束以后，后一条指令再启动，如图 7.20 所示。在这种情况下， 在第 4 个时钟周期没有新的指令流入到流水线中，第 3 条指令等到第 5 个时钟周期再启动。 图 7.19 访存冲突而引起的结构冲突的时空图 Reg Reg 图 7.20 为消除结构冲突而插入的气泡流水线 由图 7.20 可知，为消除结构相关，而插入的气泡导致流水线的吞吐率、加速比降低， 影响了流水线的性能。为了更高效消除结构冲突，可在流水线处理机中设置独立的数据存储 器和指令存储器或将 cache 分成独立的数据 cache 和指令 cache。 2.数据冲突 后续指令要用到前面指令的操作结果，而这个结果尚未产生或尚未送到指定的位置，从 而造成后序指令无法继续执行的状况，称为数据冲突或数据相关。根据指令读访问和写访问 的顺序，常见的数据冲突包括先写后读冲突（Read after write，RAW）、先读后写冲突（Write after read，WAR）、写后写冲突（Write after write，WAW）。假定连续的两条指令 i 和 j， 其中第 i 条指令在第 j条指令之前流入到流水线，两条指令之间可能引起的数据冲突如下： (1)先写后读冲突 RAW 如果第 j 条指令的源操作数是第 i条指令的结果操作数，这种数据冲突被称之为先写后 读冲突（RAW）。当指令按照流水的方式执行的时候，由于指令 j 要用到指令 i 的结果，而指 令 j 在指令 i 将结果写入寄存器之前就去读取了该寄存器，导致读取数据出错。 (2)先读后写冲突 WAR 如果第 j 条指令的结果操作数是第 i 条指令的源操作数，这种数据冲突被称之为先读后 写冲突（WAR）。当指令 j去写该寄存器的时候，指令 i 已经读取过该寄存器，所以这种数据 相关对指令的执行不构成任何影响。。 (3)写后写冲突 WAW 如果第 j 条指令和第 i条指令的结果操作数是相同的，这种数据冲突被称之为写后写冲 突（WAW）。当指令按照流水的方式执行的时候，如果第 j 条指令的写操作发生在第 i 条指令 的写操作之后，这种 WAW 冲突对指令的执行没有影响；如果第 j 条指令的写操作发生在第 i 条指令的写操作之前，如采用乱序调度策略，这种冲突导致写入顺序错误，结果单元中留下 的第 i 条指令的执行结果，而不是第 j 条指令的执行结果。 从上面的分析可知，当遇到数据相关时，为了有效的避免结果出错，最简单的处理方法， 就是推后执行与其相关的指令，来保证指令或程序执行的正确性。 例 7.3 设在图 7.16 所示的指令流水线，执行如下指令序列： DADD R1, R2, R3 ；R1← (R1) + (R2) Reg LW R4, 20(R1) ；R1← Mem[(R1) +20] AND R5, R1, R6 ；R5← (R1) AND (R6) DSUB R7, R1, R2 ；R7← (R1) − (R2) OR R8, R1, R4 ；R8← (R1) OR (R4) 画出流水线指令数据通路时空图，并分析存在哪些数据相关；为了有效的避免数据冲突， 采用推后执行法，计算吞吐率、加速比和效率。 解：指令数据通路时空图如图 7.21 所示。由指令序列分析可知，第一条 DADD 指令在第 5 个时钟周期（WB 段）才将计算结果写入寄存器 R1，但是第二条 LW 指令在第 3 个时钟周期（ID 段）要从寄存器 R1 中读取该计算结果，则第一条指令和第二条指令之间就存在着一个先写 后读的数据冲突；同理分析可知，第 3 条 AND 指令和第 4 条 DSUB 指令分别在第 4 个时钟周 期和第 5 个时钟周期（ID 段）要从寄存器 R1 中读取该计算结果，则第一条指令和第三条、 第四条指令之间也存在着一个先写后读的数据冲突；而第 5 条指令在第 6 个时钟周期（ID 段）才从寄存器 R1 中读取该计算结果，故与第一条指令之间不存在着数据冲突，但由于此 时会存在结构相关，第 3和 4 条指令分别在第 6个时钟周期和第 7 个时钟周期要用到 ID 段， 为了有效避免结构相关，采用推后执行法，第 5 条指令在 IF 段和 ID 段之间也插入了两个气 泡。为防止以上情况出现，流水线只好暂停 DADD 指令后的所有指令，防止 LW 在 ID 段读到 错误的结果。 图 7.21 指令数据通路时空图 如图 7.21 指令数据通路时空图所示：完成 5 条指令所用时间为 11⊿t，故吞吐率为； 如不采用流水线技术，每条指令所用时间为 5⊿t，总用时为 5×5⊿t=25⊿t，故加速比为： 而流水线的效率为： Reg 3.控制相关 当流水线遇到分支指令或其它会改变 PC 值的指令时，由于分支指令跳转是否成功或改 变后的 PC 值要等到存储器访问/分支完成（MEM）段才能确定或计算出来，导致在指令执行 阶段，无法确定应该去执行哪一段程序所造成的相关被称之为控制相关。解决控制相关最简 单的办法，依然是采用推后指令执行的方式，当遇到跳转指令的时候，如 JMP 指令，等到上 一条指令的 MEM 段执行完毕以后，再去执行下一条指令的 EX 段，可有效避免控制相关所引 起的指令执行出错。另外，还可以采用基于软件或硬件方法的分支预测，提前取指令，以尽 量减少由于控制相关所导致的对流水线性能的影响。 7.6指令级高度并行技术 自从上世纪 80 年代兴起 RISC 之后，又出现了提高指令级并行的一些新的技术，让单 处理机在每个时钟周期里可以解释更多的指令。目前主要有超标量技术、超流水线技术、超 长指令字技术等。 1.超标量技术 超标量技术是指在 CPU 内部包含两条或两条以上的可并行执行的指令流水线，使得在一 个时钟节拍内能同时执行多条指令。通过采用空间上的并行性，来提高系统的处理速度。 2.超流水线技术 在流水线中，将指令的执行过程分为取指、译码、执行、写回 4个子过程，如果将 这些子过程进一步细划分出更多的子过程，更大程度上提高任务处理过程中时间上的并行性 的处理技术称为超流水线技术。 3.超长指令字技术 把多条无相关关系的常规指令储存在一个超长的指令字中，让它们同时被处理，分别 控制多个功能部件并行工作的技术称为超长指令字技术。这种技术的实质，是把超标量技术 中的相关性识别任务，由 CPU 硬件转移给程序员或编译程序去实现。 本 章 小 结 采用流水线处理技术是提高计算机处理性能最基本的方法。本章在介绍指令流水线技术 基本概念的基础上，重点分析了如何对流水线的性能进行评估以及流水线的冲突问题和解决 方法，涉及到流水线的概念、表示方法、流水线的特点、流水线的分类、实例分析、线性流 水线的性能分析、流水线的中存在的冲突和解决方法等内容，并对指令级高度并行技术进行 简单的说明。 本章的学习目标包括： 1)熟悉流水线和时空图的基本概念； 2)掌握线性流水线的性能分析方法和评价指标； 3)掌握流水线中对冲突问题的分析方法和处理方法； 4)了解指令级高度并行处理技术的基本概念 具体内容小结如下： 1． 流水线基本概念 1）定义：将一个任务划分成几个不同的子过程，并且各子过程在不同的功能部件上并 行执行，使得在同一个时钟周期内同时解释多个机器语言，这种方法即为流水线处理技 术。 2)流水线的分类 流水线可从多个不同的角度进行分类。常见的分类包括线性流水线和非线性流水线；单 功能流水线和多功能流水线；静态流水线和动态流水线；顺序流水线和乱序流水线；功能部 件级、处理机级及系统级流水线等。 3)流水线的性能指标 •吞吐率：它是指单位时间内流水线所完成的任务数或输出结果的数量。 •加速比：不使用流水线技术执行任务所用的时间与使用流水线技术执行任务所用的时 间之比。 •效率：指流水线各段设备的利用率，即流水线中设备的实际使用时间与整个系统运行 时间的比值。 为了计算机流水线的性能,一般先画出流水线的时空图。 2．流水线的冲突和相关 1)结构冲突 由于多条指令在同一时钟周期使用同一操作部件而引起的冲突； 2)数据冲突 后续指令要用到前面指令的操作结果，而这个结果尚未产生或尚未送到指定的位置，从 而造成后序指令无法继续执行的状况，被称为数据冲突； 3)控制相关 当流水线遇到分支指令或其它会改变 PC 值的指令时，由于分支指令跳转是否成功或改 变后的 PC 值要等到存储器访问/分支完成（MEM）段才能确定或计算出来，导致在指令执行 阶段，无法确定应该去执行哪一段程序所造成的相关被称之为控制相关 4)解决各类相关的方法 •解决结构冲突的方法：使用分离的数据 Cache 和指令 Cache、插入气泡推后后续指令 的执行、通过编译调整指令的执行顺序等。 •解决数据相关的方法：推后后续指令的执行、采用旁路技术将前一条指令的数据直接 送后面的指令使用等。 •解决控制相关的方法：推后后续指令的执行、采用分支预测技术等。 3．指令级高度并行技术 主要包括超标量技术、超流水线技术、超长指令字技术等。 习题七 1.解释下列名词 流水线技术 通过时间 排空时间部件级流水线 指令级流水线 静态流水线 动态 流水线 多功能流水线 顺序流水线 乱序流水线 流水线加速比 流水线吞吐率 流水线吞吐率效率 数据冲突 结构冲突 控制相关 写后读冲突 先读后写冲突 写后写冲突 超标量技术 超流水线技术 超长指令字技术 气泡 2.简述流水线的特点. 3.在流水线方式是缩短了指令的执行时间还是程序的执行时间? 4.简述流水线的分类. 5.某动态多功能流水线有 6 个功能段，其中 1,2,3,6 为乘法功能所用，1,4,5,6 为加法功能 所用，在该流水线上计算∑ = 7 1i ii BA （1）画出描述算法的任务分布图； （2）画出任务执行的时空图； （3）计算吞吐率、加速比、效率。 6．有一条 5 段(S1-S5)组成的数据处理流水线如图 7.22 所示：其中，S1、S2、S3 和 S4 的 执行时间为△t，S5 的执行时间为 3△t 图 7.22 某 5 段数据处理流水线结构 (1)画出连续处理 5 个数据的处理过程的时空图，并求出流水线的实际吞吐率和效率。 (2)采用瓶颈段细分方法对瓶颈段 S5 进行改造，画出改造后的流水线和连续处理 5 个数据的 时空图，并求出流水线的实际吞吐率和效率。 7.某非线性流水线由四段组成，其中每当流经第 3 段时，总要在该段循环一次，然后才能流 到第四段。如果每段的时间都是△t，问： 1)当在该流水线输入端连续地每隔△t 时间输入一个任务时，该流水线会发生什么情况？ 2)此流水线的最大吞吐率为多少?如果每隔离2△t输入一个任务,连续处理10个任务时的实 际吞吐率和效率是多少? 3)当每段时间不变时,如何提高该流水线的吞吐率?仍连续处理 10 个任务时,其吞吐率提高 到多少? 课外实践 1 ． 利 用 WinDLX 模 拟 器 对 流 水 线 的 功 能 进 行 仿 真 。 仿 真 软 件 下 载 地 址 ： http://www.Gotoschool.net S1 S2 S3 S4输入 输出 S5