第2章 流水线技术
流水线是计算机体系结构设计中普遍应用的技术。本章介绍流水线的基本概念、表示方法、和分类，讨论流水线实现的基本结构、线性流水线的性能与非线性流水线的调度策略，分析流水线的相关及其处理方法。
2.1 流水线的基本概念
2.1.1 多条指令的执行方式
一条指令的执行过程可以分为多个阶段，通常分为三个阶段，执行过程如图2-1所示。第一阶段是取指令，按照程序计数器的内容访问主存储器，取出是一条指令送到指令寄存器。第二阶段是分析指令，对指令寄存器中的指令进行译码分析，即对指令操作码进行译码，分析指令的功能，依据给定的寻址方式和地址码字段的内容形成操作数地址，并读取操作数（立即数寻址除外）；同时，程序计数器自动产生一个增量，指到下一条指令。第三阶段是执行指令，根据操作码的要求，对操作数进行运算和处理，完成指令规定的功能，并把运算结果送到指定的地址中。指令执行过程中的第一阶段，一定要访问主存（指令一定在主存中），而在后两个阶段，也可能要访问主存（当操作数在主存中时）。当有多条指令要在一个处理机中完成时，可以有多种执行方式。现假设3个阶段所需要的时间均为△t 。
取 指 令 分析指令 执行指令 图2-1 指令的完成过程 时间 2.1.1.1 顺序执行方式
顺序执行方式是指在任何时刻，处理机中只有一条指令在执行，指令之间是顺序串行执行的，即第k条指令执行完成后，再执行完成第k+1条指令，依次类推。多条指令执行过程如图2-2（a）所示，执行n条指令所需要的时间为T = 3n△t。
顺序执行方式的优点是控制简单，节省设备。主要缺点有两个，一是处理机执行指令的速度慢。只有当上一条指令执行完毕后，下一条指令才能开始执行。二是功能部件的利用率低。如取指令时主存是忙碌的，而指令执行部件是空闲的。
2.1.1.2 一次重叠执行方式
一次重叠执行方式是指在任何时刻，处理机中至多只有两条指令在同时执行，即使第k条指令的执行阶段与第k+1条指令的取指令同时进行。多条指令执行过程如图2-2（b）所示，执行n条指令所需要的时间为T = (2n+1)△t。
一次重叠执行方式的主要优点有两个，一是执行n条指令所需要的时间缩短了近一半，二是功能部件的利用率明显提高，如主存可以基本上处于忙碌状态。但是为此需要付出一定的代
4 计算机体系结构
价，即需要增加一些硬件，控制过程也复杂一些。例如，为了能够在执行第k条指令的同时取第k+1条指令，必须再增加一个指令寄存器，用原来的指令寄存器存放第k条指令，而新增加的指令寄存器存放第k+1条指令。
2.1.1.3 二次重叠执行方式
二次重叠执行方式是指在任何时刻，处理机中至多可以有3条指令在同时执行，使第k-1条指令的执行阶段与第k条指令的分析阶段、第k+1条指令的取指令同时进行。多条指令执行过程如图2-2（c）所示，执行n条指令所需要的时间为T = (n+2)△t。
取指k
分析k 执行k 取指k+1 分析k+1 执行k+1 （a）顺序执行方式
取指k 分析k 执行k 取指k+1 分析k+1 执行k+1 取指k+2 分析k+2 执行k+2 （b）一次重叠执行方式
取指k 分析k 执行k 取指k+1 分析k+1 执行k+1 取指k+2 分析k+2 执行k+2 （c）二次重叠执行方式 图2-2 多条指令的几种执行方式
二次重叠执行方式进一步提高了指令的执行速度，相对顺序执行方式执行n条指令所需要的时间缩短了近2/3，当然也需要付出更高的代价。
可见，实现多条指令重叠执行，使程序运行如同生产流水线一样源源不断地执行指令，就能有效地提高处理执行指令的速度。当然，同时也会带来许多新的问题，就需要RISC、先行控制、相关转移处理等许多新技术来支持。
2.1.2 什么是流水线
计算机中的流水线与工厂中的生产流水线十分相似。例如汽车装配生产流水线，整个装配分为多道工序（子过程），每道工序由一个或多个人完成，各道工序所花时间也差不多。当整条流水线流动起来之后，每隔一定的时间间隔（即是一道工序的时间）就有一辆汽车下线。如果跟踪一辆汽车装配的全过程，就会发现一辆汽车装配的总时间并没有缩短，但采用装配流水线后，由于多辆汽车时间上重叠装配，使得总体的装配速度得到极大的提高。
一般说来，流水线技术（Pipelining）是指把一个重复的处理过程分解为若干个子过程，当每个子过程都设置一个功能部件来实现时，一个过程的子过程可以与其他过程的不同的子过程同时进行，实现多个不同过程在时间上重叠进行的工作方式。过程中所有子过程或实现子过程的所有功能部件按一定的次序连接在一起，即是流水线（Pipelining）。从本质上讲，流水
第2章 流水线技术 5
线技术是一种时间并行技术，是通过时间重叠的技术途径实现并行处理（时间并发性）。
流水线中的子过程或功能部件称为称为流水段（Stage），或称流水节拍、流水步、流水步骤、流水阶段或功能段等，流水线中的段数称为流水线的深度（Pipelining Depth）。过程从流水线的一端进入，经过流水线的处理，从流水线的另一端排出。流水线技术是一种非常经济而又有效的技术，已成为计算机中普遍使用的一种并行处理技术。采用流水线技术只需要增加少量的硬件，就能够把处理机的运算速度提高几倍。
2.1.3 流水线的表示方法
流水线的表示方法有3种：连接图、时空图和预约表，其中时空图用于表示线性流水线，预约表用于表示非线性流水线，而连接图则均可表示。现假设一条指令的执行过程分为取指、译码、执行、保存结果四个子过程，相应的指令流水线也要分为取指令、译码、执行、保存结果四个流水段，且对某些指令的执行流水段要重复使用一次。相应的指令流水线可用连接图、时空图和预约表来表示。
2.1.3.1 连接图
四个流水段的指令流水线的连接图如图2-3所示，其实质是将带执行时间的各流水段按照流水线的执行顺序从左到右排列，并用带箭头的直线把它们连接起来。
取指令 执行 保存结果 译码 △ t 1 △ t2 △ t 3 △t4
（a）线性指令流水线的连接图
取指令 △t1 译码 △t2 执行 △t3 保存结果 △t4
（b） 非线性指令流水线的连接图 图2-3 四功能段指令流水线连接图
2.1.3.2 时空图
I1 I2 I3 I4 I5 空间 1 2 3 4 5 保存结果
1 2 3 4 5 执行
1 2 3 4 5 译码
取指令 1 2 3 4 5 t0 t1 t2 t3 t4 t5 t6 t7 t8
图2-4 四功能段指令流水线时空图
时间
时空图是一种最常用、能直观描述线性流水线工作过程的表示方法。四个流水段的指令流水的时空图如图2-4所示。其实质是利用平面直角坐标系的第一象限。横坐标表示时间，即是输入到流水线的各个任务在流水线中所经过的时间。当流水线中各个流水段的执行时间都相等时，横坐标被分割成相等长度的时间段。纵坐标表示空间，即流水线的每一
4 计算机体系结构
个流水段。
从图中横坐标可以清楚看出，五条指令依次分别在t0、t1、t2、t3、t4时刻进入流水线，在t4、t5、t6、t7、t8时刻排出流水线。在t4 时刻以前，每经过一个时间间隔就有一条指令进入流水线。从t4 时刻开始，每经过一个时间间隔就有一条指令排出流水线。
从图中纵坐标也可清楚看出，在同一时间段内有多个流水段在同时执行指令。例如，在t4到t5时间段，取指令、译码、执行、保存结果四个流水段分别在执行第5、4、3、2条指令的相应的子过程。
2.1.3.3 预约表
预约表是一种最常用、能直观描述某过程非线性流水线工作状态的表示方法，如图2-3所示的四个流水段的指令流水线的预约表如图2-5所示。其实质是利用一张表，行表示时间，列表示空间，表中用“×”表示行对应流水段在列对应时间段要被使用。从预约表中可以看出，完成这条指令要五个时间段，且第3、4时间段均使用执行流水段。
时间 1 2 3 4 5 取指 ×
译码 ×
执行 × × 保存 × 空间 图2-5 四功能段非线性指令流水线预约表
2.1.4 流水线的分类
从不同的角度，可以把流水线分成多种不同类型，以反映流水线在某一方面的结构、特点或性能。
2.1.4.1 按流水线的功能多寡分
1．单功能流水线（Unifunction Pipelining）
单功能流水线是指流水线各段之间的连接固定不变，只能完成一种固定功能的流水线。例如：流水线浮点加法器专门完成浮点加法运算、流水线浮点乘法器专门完成浮点乘法运算。如图2-6所示为浮点加法器的流水线的连接图，共有6个功能段，6个功能段间仅能以一种固定的形式连接在一起，实现惟一的浮点加法运算。
输入 示阶差 对阶 尾数加 规格化 输出 图2-6 六功能段线性单功能流水线的连接图
2．多功能流水线（Multifunction Pipelining）
多功能流水线是指流水线的各段可以实现不同的连接，在不同的时间内或在同一时间内，通过不同的连接方式实现不同的处理功能。多功能流水线的典型代表是texas仪器公司的高级科学计算机ASC中采用的8段流水线，且功能段依次为输入、求阶差、对阶、尾数加、规格化、尾数乘、累加和输出。在一台ASC处理机内有4条相同的流水线，每条流水线都可通过不同的
第2章 流水线技术 5
连接方式分别完成整数加减法运算、整数乘法运算、浮点加法运算、浮点乘法运算和实现逻辑运算、移位操作和数据转换功能等。它除了支持标量运算之外，还支持向量运算，即可以构成非线性流水线。如图2-7所示是TI－ASC计算机的功能流水线的部分连接关系，实现不同的运算要求使用流水线中的不同功能段，并在功能段之间建立不同的连接。其中图2-7（c）是对两个浮点向量求点积的流水线的连接，它实际上是一个带有反馈回路的非线性流水线。
A B A B A B
输入 尾数乘 累加 输出 输入 求阶差 对阶 尾数加 规格化 输入 求阶差 对阶 尾数加 规格化 尾数乘 累加 输出 输出 （a）定点乘法 （b）浮点加法 （c）浮点点积
图2-7 TI-ASC计算机的多功能流水线
2.1.4.2 按多功能流水线在同一时间内各段连接是否固定分 在多功能流水线中，按照在同一时间内是否可以实现多种连接，来同时执行多种功能的要求，把多功能流水线分为静态流水线和动态流水线。
1．静态流水线（Static Pipelining）
静态流水线是指在同一段时间内，多功能流水线只能按一种方式连接，实现一种功能。只有当按照这种连接流入的所有处理的对象都流出流水线之后，多功能流水线才能重新进行连接以实现其他功能。如图2-7所示的8段多功能流水线如果按照图2-8所示的时空图工作，那么就是一种静态流水线。开始时，流水线按照实现浮点加减法的要求连接，当n个浮点加减法全部执行完成，最后一个浮点加减法运算的排空做完之后，多功能流水线才能实现定点乘法的连接，并开始做定点乘法运算。
2．动态流水线（Dynamic Pipelining） 动态流水线是指在同一段时间内，多功能流水线中的各段可以实现多种连接，同时实现多种功能，当然任何一个功能段只能参加到一种连接中。如图2-9所示是8段流水线的动态流水线的时空图。由图可见，浮点加减运算尚未排空，流水线就已实现定点乘法的连接，并开始定点乘法运算。在这一个时间段内，两种运算同时在同一条多功能流水线中分别使用不同的功能
第3章流水线技术
