第3章 流水线技术 曲冠南 qugnStu@live.com http://cc.jlu.edu.cn/ComputerArchitecture.html

先行控制（缓冲和预处理技术）（作为补充讲解内容） 小节 章节名 主要内容 3.0 重叠执行和先行控制  （第二版已删除）  顺序执行、一次重叠、两次重叠， 先行控制（缓冲和预处理技术）（作为补充讲解内容）  3.1  流水线的基本概念 什么是流水线，流水线的分类（静态流水线、动态流水线，单功能流水线、多功能流水线，部件级、处理机级、处理机间流水线，线性、非线性流水线，顺序、乱序流水线 ）  3.2  流水线的性能指标 吞吐率、加速比、效率，时空图，流水线中存在的问题   3.3  流水线的相关与冲突 （第二版将老教材的3.4.2和3.4.3合并，作为3.3.2）  5段流水线模型，指令间相关，流水线冲突及静态解决  3.4  流水线的实现  简单实现，基本实现（改进）  3.5  向量处理机  向量处理方式，向量处理机结构，提高性能，性能评价

3.0 重叠执行和先行控制 3.0.1 重叠执行 将一条指令的执行过程分为三个阶段 一条指令的执行过程

在指令的执行过程中还要更新PC值，为读取下一 条指令做好准备。 3.0 重叠执行和先行控制 取指令 按照指令计数器PC的内容访问主存，取出一条指令 送到指令寄存器。 指令分析 对指令的操作码进行译码，按照给定的寻址方式和 地址字段形成操作数的地址，并用这个地址读取操 作数。 指令执行 按照操作码的要求，完成指令规定的功能。 在指令的执行过程中还要更新PC值，为读取下一 条指令做好准备。

3.0 重叠执行和先行控制 三种执行方式 顺序执行方式 一次重叠执行方式 二次重叠执行方式

T=3nt 顺序执行方式 指令的执行过程 执行n条指令所花的时间 3.0 重叠执行和先行控制 假设取指令、指令分析和指令执行的时间相等，

执行第k条指令与取第k+l条指令同时进行。 3.0 重叠执行和先行控制 一次重叠执行方式 指令的执行过程 执行第k条指令与取第k+l条指令同时进行。 如果执行一条指令的3个阶段的时间相等，都是 t，则执行n条指令所花的时间为 T=(1+2n)t

如果执行一条指令的3个阶段的时间相等，都是 t，则执行n条指令所花的时间为 T= (2+n)t 3.0 重叠执行和先行控制 二次重叠执行方式 指令的执行过程 如果执行一条指令的3个阶段的时间相等，都是 t，则执行n条指令所花的时间为 T= (2+n)t

3.0 重叠执行和先行控制 执行时间比较 顺序 T=3nt 一次重叠 T=(1+2n)t 二次重叠 T= (2+n)t

3.0 重叠执行和先行控制 可能存在的问题？ 访存冲突 执行时间不等 分支和跳转 …

访问主存的冲突问题 - 4种解决方法 3.0 重叠执行和先行控制 设置两个独立编址的存储器： 指令存储器（存放指令）、数据存储器（存放数据） 程序空间和数据空间相互独立的系统结构被称为哈佛结构。 指令和数据仍然混合存放在同一个主存中，但设置 两个Cache： 指令Cache、数据Cache 指令和数据仍然混合存放在同一个主存中，但主存采用 多体交叉结构。 （有一定的局限性）

3.0 重叠执行和先行控制 在主存和指令分析部件之间增设指令缓冲站 （又被称为先行指令缓冲站 ） 主存不是满负荷工作的，插空从主存中预先把后面将 要执行的指令取出来，存放到指令缓冲站中。 在“取指令”阶段从指令缓冲站读取指令（如果指令 缓冲站不为空），而不用去访问主存。

3.0 重叠执行和先行控制 先行指令缓冲站 先行指令缓冲站的组成

若取指令阶段的时间很短，可以把这个操作合并 到分析指令中。 上述的二次重叠就演变成了一次重叠 3.0 重叠执行和先行控制 先行控制方式中的一次重叠执行 若取指令阶段的时间很短，可以把这个操作合并 到分析指令中。 上述的二次重叠就演变成了一次重叠 把一条指令的执行过程分为分析和执行两个阶段； 让前一条指令的执行与后一条指令的分析重叠进行。 T= (1+n)t

当指令分析和指令执行所需要的时间不相等时， 其执行过程为： 3.0 重叠执行和先行控制 当指令分析和指令执行所需要的时间不相等时， 其执行过程为： 指令分析部件和指令执行部件存在相互等待的时候，会出 现部件空闲的情况。

3.0.2 先行控制 先行控制技术：缓冲技术和预处理技术的结合 缓冲技术：在工作速度不固定的两个功能部件之间设置缓冲器，用以平滑它们的工作。 3.0 重叠执行和先行控制 3.0.2 先行控制 先行控制技术：缓冲技术和预处理技术的结合 缓冲技术：在工作速度不固定的两个功能部件之间设置缓冲器，用以平滑它们的工作。 预处理技术：预取指令、对指令进行加工以及预取操作数等。

2. 采用先行控制方式的处理机结构 3.0 重叠执行和先行控制 加工成RR指令 RR 指令 “读”访存指令 “写”访存指令 立即数指令 地址、数据、标志 地址、数据、标志

采用先行控制后的一次重叠执行 3.0 重叠执行和先行控制 指令分析部件在不间断地分析指令，而指令执行部件则在 不间断地执行指令，它们都始终处于忙碌状态。

理想情况下，指令执行部件应该是一直忙碌的。 处理机连续执行n条指令所需要的时间为 3.0 重叠执行和先行控制 理想情况下，指令执行部件应该是一直忙碌的。 处理机连续执行n条指令所需要的时间为

3.1 流水线的基本概念 3.1.1 什么是流水线 工业生产流水线 特点：单个产品时间不变，多产品总时间缩短。

把一个重复的过程分解为若干个子过程，每个子过程由专门的功能部件来实现。 3.1 流水线的基本概念 流水线技术 把一个重复的过程分解为若干个子过程，每个子过程由专门的功能部件来实现。 把多个处理过程在时间上错开，依次通过各功能段，这样，每个子过程就可以与其他的子过程并行进行。 流水线中的每个子过程及其功能部件称为流水线的级或段，段与段相互连接形成流水线。流水线的段数称为流水线的深度。

3. 流水线表示方法 - 时空图 时空图从时间和空间两个方面描述了流水线的工作过程。时空图中，横坐标代表时间，纵坐标代表流水线的各个段。 4段流水线的时空图

3.1.2 流水线的分类 从不同的角度和观点，把流水线分成多种不同的种类。 单功能流水线与多功能流水线 （按照流水线所完成的功能来分类） 3.1 流水线的基本概念 3.1.2 流水线的分类 从不同的角度和观点，把流水线分成多种不同的种类。 单功能流水线与多功能流水线 （按照流水线所完成的功能来分类） 单功能流水线：只能完成一种固定功能的流水线。 多功能流水线：流水线的各段可以进行不同的 连接，以实现不同的功能。 例： ASC的多功能流水线

静态流水线：在同一时间内，多功能流水线中的 各段只能按同一种功能的连接方式工作。 3.1 流水线的基本概念 静态流水线与动态流水线 （按照同一时间内各段之间的连接方式对多功能流水线做 进一步的分类） 静态流水线：在同一时间内，多功能流水线中的 各段只能按同一种功能的连接方式工作。 对于静态流水线来说，只有当输入的是一串相同的 运算任务时，流水的效率才能得到充分的发挥。 例如：ASC的8段流水线

动态流水线：在同一时间内，多功能流水线中的各段可以按照不同的方式连接，同时执行多种功能。 3.1 流水线的基本概念 动态流水线：在同一时间内，多功能流水线中的各段可以按照不同的方式连接，同时执行多种功能。 优点 灵活，能够提高流水线各段的使用率，从而 提高处理速度。 缺点 控制复杂。 静、动态流水线时空图的对比

部件级流水线（运算操作流水线）：把处理机的算术逻辑运算部件分段，使得各种类型的运算操作能够按流水方式进行。 3.1 流水线的基本概念 部件级、处理机级及处理机间流水线 （按照流水的级别来进行分类） 部件级流水线（运算操作流水线）：把处理机的算术逻辑运算部件分段，使得各种类型的运算操作能够按流水方式进行。 如： 把浮点加法的全过程分解为求阶差、对阶、尾数相加、规格化4个子过程。 理想情况：速度提高3倍

3.1 流水线的基本概念 处理机级流水线（指令流水线）：把指令的解释执行过程按照流水方式处理。把一条指令的执行过程分解为若干个子过程，每个子过程在独立的功能部件中执行。 如：

处理机间流水线（宏流水线）：它是由两个或者 两个以上的处理机串行连接起来，对同一数据流 进行处理，每个处理机完成整个任务中的一部 分。 3.1 流水线的基本概念 处理机间流水线（宏流水线）：它是由两个或者 两个以上的处理机串行连接起来，对同一数据流 进行处理，每个处理机完成整个任务中的一部 分。

线性流水线：流水线的各段串行连接，没有反馈回路。数据通过流水线中的各段时，每一个段最多只流过一次。 3.1 流水线的基本概念 线性流水线与非线性流水线 （按照流水线中是否有反馈回路来进行分类） 线性流水线：流水线的各段串行连接，没有反馈回路。数据通过流水线中的各段时，每一个段最多只流过一次。 非线性流水线：流水线中除了有串行的连接外，还有反馈回路。

确定什么时候向流水线引进新的任务，才能使该任务不会与先前进入流水线的任务发生冲突——争用流水段。 3.1 流水线的基本概念 非线性流水线的调度问题 确定什么时候向流水线引进新的任务，才能使该任务不会与先前进入流水线的任务发生冲突——争用流水段。

顺序流水线：流水线输出端任务流出的顺序与输 入端任务流入的顺序完全相同。每一个任务在流 水线的各段中是一个跟着一个顺序流动的。 3.1 流水线的基本概念 顺序流水线与乱序流水线 （根据任务流入和流出的顺序是否相同来进行分类） 顺序流水线：流水线输出端任务流出的顺序与输 入端任务流入的顺序完全相同。每一个任务在流 水线的各段中是一个跟着一个顺序流动的。 乱序流水线：流水线输出端任务流出的顺序与输 入端任务流入的顺序可以不同，允许后进入流水 线的任务先完成（从输出端流出）。 也称为无序流水线、错序流水线、异步流水线

3.2 流水线的性能指标 3.2.1 吞吐率 吞吐率：在单位时间内流水线所完成的任务数量或输 出结果的数量。 n：任务数 Tk：处理完成n个任务所用的时间

3.2 流水线的性能指标 各段时间均相等的流水线 假设k段，每段为时间为Δt。 求吞吐率 最大吞吐率 实际吞吐率和最大吞吐率之间的关系

3.2 流水线的性能指标 各段时间均相等的流水线时空图

Tk＝kΔt＋(n-1)Δt＝(k＋n-1)Δt 流水线的实际吞吐率 3.2 流水线的性能指标 流水线完成n个连续任务所需要的总时间为 （假设一条k段线性流水线） 　　　　Tk＝kΔt＋(n-1)Δt＝(k＋n-1)Δt 流水线的实际吞吐率 最大吞吐率

最大吞吐率与实际吞吐率的关系 3.2 流水线的性能指标 流水线的实际吞吐率小于最大吞吐率，它除了与每个段的时间有关外，还与流水线的段数k以及输入到流水线中的任务数n等有关。 只有当n>>k时，才有TP≈TPmax。

流水线中这种时间最长的段称为流水线的瓶颈段。 3.2 流水线的性能指标 各段时间不完全相等的流水线 各段时间不等的流水线及其时空图 举例（时空图） 一条4段的流水线 S1，S3，S4各段的时间：Δt S2的时间：3Δt （瓶颈段） 流水线中这种时间最长的段称为流水线的瓶颈段。

3.2 流水线的性能指标

3.2 流水线的性能指标 各段时间不等的流水线的实际吞吐率： （ Δti为第i段的时间，共有k个段 ） 流水线的最大吞吐率为

例如：一条4段的流水线中，S1，S2，S4各段的 时间都是Δt，唯有S3的时间是3Δt。 3.2 流水线的性能指标 例如：一条4段的流水线中，S1，S2，S4各段的 时间都是Δt，唯有S3的时间是3Δt。 最大吞吐率为

解决流水线瓶颈问题的常用方法 细分瓶颈段 改进后的流水线的吞吐率 ： 3.2 流水线的性能指标 例如：对前面的4段流水线 把瓶颈段S3细分为3个子流水线段：S3a，S3b，S3c 改进后的流水线的吞吐率 ：

重复设置瓶颈段 3.2 流水线的性能指标 举例：时空图 缺点：控制逻辑比较复杂，所需的硬件增加了。 例如：对前面的4段流水线 重复设置瓶颈段S3：S3a，S3b，S3c

3.2 流水线的性能指标 重复设置瓶颈段后的时空图

3.2.2 加速比 加速比：完成同样一批任务，不使用流水线所用的时间 与使用流水线所用的时间之比。 3.2 流水线的性能指标 3.2.2 加速比 加速比：完成同样一批任务，不使用流水线所用的时间 与使用流水线所用的时间之比。 假设：不使用流水线（即顺序执行）所用的间为Ts，使用流水线后所用的时间为Tk，则该流水线的加速比为

流水线各段时间相等（都是△t） 一条k段流水线完成n个连续任务 Tk = (k＋n-1)Δt 顺序执行n个任务 流水线的实际加速比为 3.2 流水线的性能指标 流水线各段时间相等（都是△t） 一条k段流水线完成n个连续任务 所需要的时间为 Tk = (k＋n-1)Δt 顺序执行n个任务 所需要的时间： Ts= nk△t （解释） 流水线的实际加速比为

当n>>k时，S ≈ k 思考：流水线的段数愈多愈好？ 3.2 流水线的性能指标 最大加速比 当n>>k时，S ≈ k 思考：流水线的段数愈多愈好？

一条k段流水线完成n个连续任务的实际加速比为 3.2 流水线的性能指标 流水线的各段时间不完全相等时 一条k段流水线完成n个连续任务的实际加速比为

3.2.3 效率 效率：流水线中的设备实际使用时间与整个运行时间 的比值，即流水线设备的利用率。 3.2 流水线的性能指标 3.2.3 效率 效率：流水线中的设备实际使用时间与整个运行时间 的比值，即流水线设备的利用率。 由于流水线有通过时间和排空时间，所以在连续 完成n个任务的时间内，各段并不是满负荷地工作。 从时空图上看，效率就是n个任务占用的时空面积和k个段总的时空面积之比。

3.2 流水线的性能指标 1. 各段时间相等时，整条流水线的效率为 最高效率为 当n>>k时，E≈1。

3.2 流水线的性能指标 2.各段时间不相等时，整条流水线的效率为

总结：当流水线各段时间相等时 流水线时间 Tk = (k+n-1)△t 吞吐率 TP = n/(k+n-1) △t 3.2 流水线的性能指标 总结：当流水线各段时间相等时 流水线时间 Tk = (k+n-1)△t 吞吐率 TP = n/(k+n-1) △t 加速比 S = nk/ (k+n-1) 效率 E = n/(k+n-1) 有 E = TP △t， 即 效率和吞吐率成正比。 E = S/k， 即当S = K时， E=1。

3.2.4 流水线的性能分析举例 流水线的输出可以直接返回输入端或暂存于相应的流水寄存器中，试计算其吞吐率、加速比和效率。 3.2 流水线的性能指标 3.2.4 流水线的性能分析举例 例3.1 设在下图所示的静态流水线上计算： 流水线的输出可以直接返回输入端或暂存于相应的流水寄存器中，试计算其吞吐率、加速比和效率。 (每段的时间都为△t)

解：（1）选择适合于流水线工作的算法 （2）画出时空图 3.2 流水线的性能指标 先计算A1+B1、A2+B2、A3+B3和A4+B4； 然后求总的乘积结果。 （2）画出时空图

3.2 流水线的性能指标

（3）计算性能 3.2 流水线的性能指标 在18个△t时间中，给出了7个结果。吞吐率为： 不用流水线，由于一次求和需6△t，一次求积需4△t， 则产生上述7个结果共需（4×6+3×4）△t = 36△t 加速比为

3.2 流水线的性能指标 流水线的效率 可以看出，在求解此问题时，该流水线的效率不高。 为什么？

主要原因 3.2 流水线的性能指标 流水线的工作过程有建立与排空部分。 静态流水线在进行功能切换时，要等前一种运算全部流出流水线后才能进行后面的运算。 运算之间存在关联，后面有些运算要用到前面运算的结果。

试计算其吞吐率、加速比和效率。 3.2 流水线的性能指标 例3.2 有一条动态多功能流水线由5段组成，加法用1、3、4、5段，乘法用1、2、5段，第2段的时间为2△t，其余各段时间均为△t，而且流水线的输出可以直接返回输入端或暂存于相应的流水寄存器中。若在该流水线上计算: 试计算其吞吐率、加速比和效率。

解: (1) 选择适合于流水线工作的算法 (2) 画出时空图 (3) 计算性能 3.2 流水线的性能指标 应先计算A1×B1、A2×B2、A3×B3和A4×B4； 再计算(A1×B1)＋(A2×B2) (A3×B3)＋(A4×B4)； 然后求总的累加结果。 (2) 画出时空图 (3) 计算性能

3.2 流水线的性能指标

3.2 流水线的性能指标 3.2.5 流水线中的若干问题 瓶颈问题 理想情况下，流水线在工作时其中的任务是同步地每个节拍往前流动一段。当流水线各段不均匀时，处理时间长的段成为瓶颈段，计算机的时钟周期取决于瓶颈段的延迟时间。 额外开销 流水寄存器延迟 – 建立时间、传输延迟 时钟偏移开销 冲突问题 指令之间存在关联性

3.2 流水线的性能指标 课堂习题 请同学们做课后习题 3.12题 （新教材，即老教材的3.15题） 步骤：1. 选择合适的算法； 2. 画出时空图； 3. 求出流水线执行时间； 4. 求出吞吐率、加速比、效率。

参考答案

3.3 流水线的相关与冲突 3.3.1 一个经典的5段流水线 MIPS指令： LW R1， 20(R5) DADDU R3， R1，R2 DADDIU R4， R3，#3 SW R4， 300(R5) BEQZ R4， name 当任务源源不断流入流水线的时候，流水线的吞吐率最高，加速比最高，效率最高。 然而，愿望是美好的，任务不可能源源不断的流入流水线，那么为什么呢？ 当前一条指令的操作结果时候一条指令的操作数时，前一条指令未执行完，后一条指令不能开始执行； 前一条指令一旦判断出是分支指令，并且成功跳转，那么后一条指令就白放入流水线了。 因此，种种原因导致了流水线的断流。那么这节课，我们就来分析其原因。 在分析原因之前，我们先来介绍一个经典的5段流水线。

3.3 流水线的相关与冲突 3.3.1 一个经典的5段流水线 RR ALU R-立即数ALU 访存 分支 IF （IM） ID (REG) 取指令 IR， PC=PC+4 ID (REG) 译码，访问通用寄存器，取操作数 EX (ALU) 计算有效 地址 计算目标地址；判断分支是否成功 MEM(DM) 目标地址PC WB (REG) ALU运算结果 写通用寄存器 Load指令访存结果写通用寄存器

将上述实现方案修改为流水线实现 一个经典的5段流水线 每一个周期作为一个流水段。 在各段之间加上锁存器（流水寄存器）。

流水实现的数据通路

3.3 流水线的相关与冲突 5段流水线的两种描述方式 第一种描述（类似于时空图）

第二种描述（按时间错开的数据通路序列）

采用流水线方式实现时，可能存在的问题？ 同时加？ 同时访存？ 同时读写同一寄存器？ 控制流的改变 寄存器 立即数 访存 分支 IF （IM） 取指令 IR， PC=PC+4 ID (REG) 译码，访问通用寄存器，取操作数 EX (ALU) ALU 计算有效地址 计算目标地址；判断分支是否成功 MEM(DM) 目标地址PC WB (REG) ALU运算结果 写通用寄存器 Load指令访存结果写通用寄存器 同时加？ 同时访存？ 同时读写同一寄存器？ 控制流的改变

3.3.2 相关与流水线冲突 3.3.2.1 相关 相关：两条指令之间存在某种依赖关系。 相关有3种类型 3.3 流水线的相关与冲突 如果两条指令相关，则它们就有可能不能在流 水线中重叠执行或者只能部分重叠执行。 相关有3种类型 数据相关（也称真数据相关） 名相关 控制相关

对于两条指令i（在前，下同）和j（在后，下同），如果下述条件之一成立，则称指令j与指令i数据相关。 3.3 流水线的相关与冲突 数据相关 对于两条指令i（在前，下同）和j（在后，下同），如果下述条件之一成立，则称指令j与指令i数据相关。 指令j使用指令i产生的结果； 指令j与指令k数据相关，而指令k又与指令i数据相关。 数据相关具有传递性。 数据相关反映了数据的流动关系，即如何从其产 生者流动到其消费者。

Loop： L.D F0，0（R1） // F0为数组元素 3.3 流水线的相关与冲突 例如：下面这一段代码存在数据相关。 Loop： L.D F0，0（R1） // F0为数组元素 ADD.D F4，F0，F2 // 加上F2中的值 S.D F4，0（R1） // 保存结果 DADDIU R1，R1，－8 // 数组指针递减8个字节 BNE R1，R2，Loop // 如果R1≠R2，则分支

当数据的流动是经过寄存器时，相关的检测比较 直观和容易。 3.3 流水线的相关与冲突 如何检测相关： 当数据的流动是经过寄存器时，相关的检测比较 直观和容易。 L.D F0，0（R1） ADD.D F4，F0，F2 当数据的流动是经过存储器时，检测比较复杂。 形式不同的地址其有效地址却可能相同。 SW R4，300(R6) LW R1， 20(R5) 相同形式的地址其有效地址未必相同。 SW R4，300(R5) DADDU R5， R1，R2 LW R1， 300(R5)

名：指令所访问的寄存器或存储器单元的名称。 如果两条指令使用相同的名，但是它们之间并没有数据流动，则称这两条指令存在名相关。 3.3 流水线的相关与冲突 名相关 名：指令所访问的寄存器或存储器单元的名称。 如果两条指令使用相同的名，但是它们之间并没有数据流动，则称这两条指令存在名相关。 指令j与指令i之间的名相关有两种： 反相关：指令j写的名＝指令i读的名 DADDU R6， R5，R2 DADDU R5， R1，R2 输出相关：指令j写的名＝指令i写的名 DADDU R5， R3，R2 。。。

特 点： 名相关的两条指令之间并没有数据的传送。 消除方法： 换名技术 3.3 流水线的相关与冲突 特 点： 名相关的两条指令之间并没有数据的传送。 消除方法： 换名技术 换名技术：通过改变指令中操作数的名来消除名相关。 对于寄存器操作数进行换名称为寄存器换名。 DADDU R6， R5，R2 DADDU R5， R1，R2  DADDU R7， R1，R2 既可以用编译器静态实现，也可以用硬件动态完成。

? 例： DIV.D F2， F6， F4 ADD.D F6， F0， F12 SUB.D F8， F6， F14 3.3 流水线的相关与冲突 例： DIV.D F2， F6， F4 ADD.D F6， F0， F12 SUB.D F8， F6， F14 ?

典型的程序结构是“if-then”结构。 3.3 流水线的相关与冲突 控制相关 控制相关是指由分支指令引起的相关。 为了保证程序应有的执行顺序，必须严格按控制相 关确定的顺序执行。 典型的程序结构是“if-then”结构。 if p1 { S1； }； S； if p2 { S2； BEQZ R1, name ADD.D F7, F3, F4 Name： ADD.D F4, F0, F2 DAADIU R1, R1, #-8

BEQZ R1, name ADD.D F7, F3, F4 Name： ADD.D F4, F0, F2 3.3 流水线的相关与冲突 控制相关带来了以下两个限制： 与一条分支指令控制相关的指令不能被移到该分支 之前，否则这些指令就不受该分支控制了。 如果一条指令与某分支指令不存在控制相关，就不 能把该指令移到该分支之后。 BEQZ R1, name ADD.D F7, F3, F4 Name： ADD.D F4, F0, F2 DAADIU R1, R1, #-8

流水线冲突是指对于具体的流水线来说，由于相关 的存在，使得指令流中的下一条指令不能在指定的时钟 周期执行。 流水线冲突有3种类型： 3.3 流水线的相关与冲突 3.3.2.2 流水线冲突 流水线冲突是指对于具体的流水线来说，由于相关 的存在，使得指令流中的下一条指令不能在指定的时钟 周期执行。 流水线冲突有3种类型： 结构冲突：因硬件资源满足不了指令重叠执行的要 求而发生的冲突。 数据冲突：当指令在流水线中重叠执行时，因需要 用到前面指令的执行结果而发生的冲突。 控制冲突：流水线遇到分支指令和其他会改变PC值 的指令所引起的冲突。

流水线可能会出现停顿，从而降低流水线的效率 和实际的加速比。 我们约定 3.3 流水线的相关与冲突 带来的几个问题： 导致错误的执行结果。 流水线可能会出现停顿，从而降低流水线的效率 和实际的加速比。 我们约定 当一条指令被暂停时，在该暂停指令之后流出的所 有指令都要被暂停，而在该暂停指令之前流出的指令则 继续进行（否则就永远无法消除冲突）。

如果某种指令组合因为资源冲突而不能正常执 行，则称该处理机有结构冲突。 常见的导致结构相关的原因： 3.3 流水线的相关与冲突 结构冲突 如果某种指令组合因为资源冲突而不能正常执 行，则称该处理机有结构冲突。 常见的导致结构相关的原因： 功能部件不是完全流水 资源份数不够 如何解决？

和指令放在一起，访存指令会导致访存冲突。 3.3 流水线的相关与冲突 结构冲突举例：访存冲突 有些流水线处理机只有一个存储器，将数据 和指令放在一起，访存指令会导致访存冲突。

3.3 流水线的相关与冲突 解决办法Ⅰ：插入暂停周期 （“流水线气泡”或“气泡”）

时钟周期 1 2 3 4 5 6 7 8 9 10 IF ID EX MEM WB stall 3.3 流水线的相关与冲突 引入暂停后的时空图 指令编号 时钟周期 1 2 3 4 5 6 7 8 9 10 指令i IF ID EX MEM WB 指令i+1 指令i+2 指令i+3 stall 指令i+4 指令i+5

如果把流水线中的所有功能单元完全流水化，或重复设置足够份数，那么所花费的成本将相当高。 3.3 流水线的相关与冲突 解决方法Ⅱ： 设置相互独立的指令存储器和数据存储器 或设置相互独立的指令Cache和数据Cache。 有时流水线设计者允许结构冲突的存在 主要原因：减少硬件成本 如果把流水线中的所有功能单元完全流水化，或重复设置足够份数，那么所花费的成本将相当高。

当相关的指令靠得足够近时，它们在流水线中 的重叠执行或者重新排序会改变指令读/写操作数 的顺序，使之不同于它们非流水实现时的顺序， 3.3 流水线的相关与冲突 数据冲突 当相关的指令靠得足够近时，它们在流水线中 的重叠执行或者重新排序会改变指令读/写操作数 的顺序，使之不同于它们非流水实现时的顺序， 则发生了数据冲突。

举例： DADD R1，R2，R3 DSUB R4，R1，R5 XOR R6，R1，R7 AND R8，R1，R9 3.3 流水线的相关与冲突 举例： DADD R1，R2，R3 DSUB R4，R1，R5 XOR R6，R1，R7 AND R8，R1，R9 OR R10，R1，R11

3.3 流水线的相关与冲突 流水线的数据冲突举例

根据指令读访问和写访问的顺序，可以将数据冲 突分为3种类型。 3.3 流水线的相关与冲突 根据指令读访问和写访问的顺序，可以将数据冲 突分为3种类型。 考虑两条指令i和j ，且i在j之前进入流水线， 可能发生的数据冲突有： 写后读冲突（RAW） 在 i 写入之前，j 先去读。 j 读出的内容是错误的。 这是最常见的一种数据冲突，它对应于真数据相关。

读后写冲突在前述5段流水线中不会发生。 这种冲突仅发生在这样的情况下： 3.3 流水线的相关与冲突 读后写冲突（WAR） 在 i 读之前，j 先写。i 读出的内容是错误的！ 由反相关引起。 DADDU R6， R5，R2 DADDU R5， R1，R2 读后写冲突在前述5段流水线中不会发生。 （读操作（在ID段）在写结果操作（在WB段）之前） 这种冲突仅发生在这样的情况下： 有些指令的写结果操作提前了，而且有些指令 的读操作滞后了。 指令在执行时被重新排序了。

写后写冲突在前述5段流水线中不会发生。 写后写冲突仅发生在这样的流水线中： 3.3 流水线的相关与冲突 写后写冲突（WAW） 在 i 写入之前，j 先写。最后写入的结果是 i 的。错误！ 这种冲突对应于输出相关。 DADDU R5， R3，R2 DADDU R5， R1，R2 写后写冲突在前述5段流水线中不会发生。 （只在WB段写寄存器） 写后写冲突仅发生在这样的流水线中： 流水线中不只一个段可以进行写操作。 指令未按顺序执行。

入手点：并不是所有的阶段都真正的需要读取数据。 3.3 流水线的相关与冲突 如何解决流水线数据冲突带来的影响？ 减少停顿  定向技术 入手点：并不是所有的阶段都真正的需要读取数据。 必须停顿  流水线互锁 入手点：冲突检测 消除冲突  编译器的力量 入手点：让指令之间的距离足够远

采用定向技术后的流水线数据通路 3.3 流水线的相关与冲突 情况I：当定向硬件检测到前一个ALU运算结果写入的寄存器就是当前ALU操作的源寄存器时，控制逻辑就选择定向数据作为ALU的输入，而不是采用从通用寄存器组中读取的值。

定向情况I：相邻指令 流水实现的数据通路

定向情况I：请观察左图中的粉色回路

定向情况II： 流水线中的指令所需要的定向结果可能不仅仅是前一条指令的计算结果，而且还有可能是前面不相邻指令的运算结果。 采用定向技术后的流水线数据通路 3.3 流水线的相关与冲突 定向情况II： 流水线中的指令所需要的定向结果可能不仅仅是前一条指令的计算结果，而且还有可能是前面不相邻指令的运算结果。

定向情况II：不相邻指令定向 流水实现的数据通路

定向情况II：请观察左图中的黄色回路

定向情况III：访存指令定向 流水实现的数据通路

定向情况III：请观察左图中的红色回路

定向技术 3.3 流水线的相关与冲突 （定向技术也称为旁路或短路） 关键思想：在某条指令产生计算结果之前，其他指 令并不真正立即需要该计算结果，如果能够将该计 算结果从其产生的地方直接送到其他指令需要它的 地方，那么就可以避免停顿。

并不是所有的数据冲突都可以用定向技术来解决。 3.3 流水线的相关与冲突 需要停顿的数据冲突 并不是所有的数据冲突都可以用定向技术来解决。 无法将LD指令的结果定向到DADD指令

作用：检测发现数据冲突，并使流水线停顿，直至 冲突消失。 3.3 流水线的相关与冲突 增加流水线互锁硬件，插入“暂停”。 作用：检测发现数据冲突，并使流水线停顿，直至 冲突消失。 流水线互锁机制插入气泡后的执行过程

LD R1，0（R2） IF ID EX MEM WB DADD R4，R1，R5 AND R6，R1，R7 XOR R8，R1，R9 3.3 流水线的相关与冲突 LD R1，0（R2） IF ID EX MEM WB DADD R4，R1，R5 AND R6，R1，R7 XOR R8，R1，R9 LD R1，0（R2） IF ID EX MEM WB DADD R4，R1，R5 stall AND R6，R1，R7 XOR R8，R1，R9 插入停顿前后的流水线时空图

依靠编译器解决数据冲突 称为指令调度或流水线调度。 例如：采用典型的代码生成方法， 表达式A＝B＋C的代码会导致暂停 LD Rb，B IF 3.3 流水线的相关与冲突 依靠编译器解决数据冲突 让编译器重新组织指令顺序来消除冲突，这种技术 称为指令调度或流水线调度。 例如：采用典型的代码生成方法， 表达式A＝B＋C的代码会导致暂停 LD Rb，B IF ID EX MEM WB LD Rc，C DADD Ra，Rb，Rc stall SD Ra ，A

A＝B＋C ； D＝E－F ； 题解 请为下列表达式生成没有暂停的指令序列: 调度前的代码 调度后的代码 LD Rb，B LD Rc，C 举例： 请为下列表达式生成没有暂停的指令序列: 　A＝B＋C ； 　D＝E－F ； 题解 调度前的代码 调度后的代码 LD Rb，B LD Rc，C DADD Ra，Rb，Rc SD Ra，A LD Re，E LD Rf，F DSUB Rd，Re，Rf SD Rd，D

结合如下的例子, 考虑流水线中处理控制冲突的方法： 3.3 流水线的相关与冲突 控制冲突 执行分支指令的结果有两种 分支成功：PC值改变为分支转移的目标地址。 在条件判定和转移地址计算都完成后，才改变PC值。 不成功或者失败：PC的值保持正常递增， 指向顺序的下一条指令。 结合如下的例子, 考虑流水线中处理控制冲突的方法： BEQZ R1, name ADD.D F7, F3, F4 Name： ADD.D F4, F0, F2 DAADIU R1, R1, #-8

处理分支指令最简单的方法： “冻结”或者“排空”流水线 。 优点：简单。 缺点：给流水线带来了3个时钟周期的延迟 前述5段流水线中，改变PC值是在MEM段进行的。 BEQZ R1, name ADD.D F7, F3, F4 Name： ADD.D F4, F0, F2 DAADIU R1, R1, #-8 分支成功？ 分支失败？

把由分支指令引起的延迟称为分支延迟。 分支指令在目标代码中出现的频度 如何减少分支延迟？ 3.3 流水线的相关与冲突 每3～4条指令就有一条是分支指令。 假设：分支指令出现的频度是30％， 流水线理想 CPI＝1， 那么：流水线的实际 CPI ＝ 1.9。 如何减少分支延迟？

这两步工作被提前到ID段完成，即分支指令是在ID段的末尾执行完成，所带来的分支延迟为一个时钟周期。 3.3 流水线的相关与冲突 可采取两种措施来减少分支延迟。 在流水线中尽早判断出分支转移是否成功； 尽早计算出分支目标地址。 下面的讨论中，我们假设： 这两步工作被提前到ID段完成，即分支指令是在ID段的末尾执行完成，所带来的分支延迟为一个时钟周期。

3种通过软件（编译器）来减少分支延迟的方法 共同点： 3.3 流水线的相关与冲突 3种通过软件（编译器）来减少分支延迟的方法 共同点： 对分支的处理方法在程序的执行过程中始终是 不变的，是静态的。（对应于第四章的动态预测） 要么总是预测分支成功，要么总是预测分支失败。

3.3 流水线的相关与冲突 预测分支失败 允许分支指令后的指令继续在流水线中流动，就 好象什么都没发生似的。 若确定分支失败，将分支指令看作是一条普通指 令，流水线正常流动。 若确定分支成功，流水线就把在分支指令之后 取出的所有指令转化为空操作，并按分支目地 重新取指令执行。 要保证：分支结果出来之前不会改变处理机的状态，以 便一旦猜错时，处理机能够回退到原先的状态。

3.3 流水线的相关与冲突 预测分支成功 假设分支转移成功，并从分支目标地址处取指令执行。 起作用的前题：先知道分支目标地址，后知道分支是否 成功。 前述5段流水线中，这种方法没有任何好处。

3.3 流水线的相关与冲突 延迟分支 主要思想： 从逻辑上“延长”分支指令的执行时间。把延迟分支看成是由原来的分支指令和若干个延迟槽构成，不管分支是否成功，都要按顺序执行延迟槽中的指令。

分支延迟槽中的指令“掩盖”了流水线原来必须插入的暂停周期。 具有一个分支延迟槽的流水线的执行过程 分 支 失 败 分支指令i IF ID EX MEM WB 延迟槽指令 i+1 指令 i+2 指令 i+3 指令 i+4 分 支 成 功 分支指令i IF ID EX MEM WB 延迟槽指令 i+1 分支目标指令j 分支目标指令j+1 分支目标指令j+2 分支延迟槽中的指令“掩盖”了流水线原来必须插入的暂停周期。

分支延迟指令的调度 3.3 流水线的相关与冲突 任务：在延迟槽中放入有用的指令。 由编译器完成。能否带来好处取决于编译器能否把有用 的指令调度到延迟槽中。 三种调度方法： 从前调度 从目标处调度 从失败处调度

调度前和调度后的代码

三种方法的要求及效果 3.3 流水线的相关与冲突 调 度 策 略 对调度的要求 什么情况下起作用 从 前 调 度 被调度的指令必须与分支无关 任何情况 必须保证在分支失败时执行被调度 的指令不会导致错误。有可能需要 复制指令 分支成功时 (但由于复制指令，有 可能会增大程序空间) 从目标处调度 必须保证在分支成功时执行被调度 的指令不会导致错误 从失败处调度 分支失败时

分支延迟受到两个方面的限制： 进一步改进：分支取消机制（取消分支） 3.3 流水线的相关与冲突 可以被放入延迟槽中的指令要满足一定的条件。 编译器预测分支转移方向的能力。 进一步改进：分支取消机制（取消分支） 当分支的实际执行方向和事先所预测的一样时， 执行分支延迟槽中的指令，否则就将分支延迟槽中的 指令转化成一个空操作。 “预测成功－取消”分支的执行过程

分 支 失 败 分支指令i IF ID EX MEM WB 延迟槽指令 i+1 idle 指令 i+2 指令 i+3 指令 i+4 分 支 成 功 分支指令i IF ID EX MEM WB 延迟槽指令 i+1 分支目标指令j 分支目标指令j+1 分支目标指令j+2 预测分支成功的情况下，分支取消机制的执行情况

3.4 流水线的实现 3.4.1 MIPS的一种简单实现 实现MIPS指令子集的一种简单数据通路。 该数据通路的操作分成5个时钟周期 取指令 指令译码/读寄存器 执行/有效地址计算 存储器访问/分支完成 写回 只讨论整数指令的实现（包括：load和store，等于0转移，整数ALU指令等。）

一条MIPS指令最多需要以下5个时钟周期： 取指令周期（IF） 操作 3.4 流水线的实现 一条MIPS指令最多需要以下5个时钟周期： 取指令周期（IF） 操作 IR←Mem[PC] NPC←PC+4 指令译码/读寄存器周期（ID） 操作 A ← Regs[rs] B ← Regs[rt] Imm ← （（IR16）16##IR16..31） 指令的译码操作和读寄存器操作是并行进行的。 原因：在MIPS指令格式中，操作码字段以及rs、rt 字段都是在固定的位置。 这种技术称为固定字段译码技术。

执行/有效地址计算周期（EX） 不同指令所进行的操作不同： 3.4 流水线的实现 存储器访问指令 操作 ALUo←A + Imm 存储器访问指令 操作 ALUo←A + Imm 寄存器－寄存器ALU指令 操作 ALUo←A func B 寄存器－立即值ALU指令 操作 ALUo←A op Imm 分支指令 操作 ALUo←NPC+（Imm<<2）； cond←（A = = 0）

存储器访问/分支完成周期（MEM） 3.4 流水线的实现 将有效地址计算周期和执行周期合并为一个时 钟周期，这是因为MIPS指令集采用load／store结 构，没有任何指令需要同时进行数据有效地址的计 算、转移目标地址的计算和对数据进行运算。 存储器访问/分支完成周期（MEM） 所有指令都要在该周期对PC进行更新。 除了分支指令，其他指令都是做PC←NPC 在该周期内处理的MIPS指令仅仅有load、store和分支三种指令。

写回周期（WB） 3.4 流水线的实现 存储器访问指令 操作 LMD←Mem[ALUo] 或者 Mem[ALUo]←B 分支指令 操作 存储器访问指令 操作 LMD←Mem[ALUo] 或者 Mem[ALUo]←B 分支指令 操作 if （cond） PC ←ALUo else PC←NPC 写回周期（WB） 不同的指令在写回周期完成的工作也不一样。 寄存器－寄存器ALU指令 操作 Regs[rd]← ALUo 寄存器－立即数ALU指令 操作 Regs[rt]← ALUo load指令 操作 Regs[rt]← LMD

对于大多数CPU来说，单周期实现效率很低，因为不同的指令所需完成的操作差别相当大，因而所需要的时钟周期时间也大不一样。 3.4 流水线的实现 不采用单周期实现方案的主要原因 对于大多数CPU来说，单周期实现效率很低，因为不同的指令所需完成的操作差别相当大，因而所需要的时钟周期时间也大不一样。 单周期实现时，需要重复设置某些功能部件，而在多周期实现方案中，这些部件是可以共享的。

3.4.2 基本的MIPS流水线 每一个时钟周期完成的工作看作是流水线的一段，每个时钟周期启动一条新的指令。 流水实现的数据通路 3.4 流水线的实现 3.4.2 基本的MIPS流水线 每一个时钟周期完成的工作看作是流水线的一段，每个时钟周期启动一条新的指令。 流水实现的数据通路 设置了流水寄存器 段与段之间设置流水寄存器 流水寄存器的命名 用其相邻的两个段的名称拼合而成。 例如：ID段与EX段之间的流水寄存器用ID/EX表示 每个流水寄存器是由若干个寄存器构成的

3.4 流水线的实现 流水实现的数据通路

3.4 流水线的实现 寄存器的命名形式为：x.y 所包含的字段的命名形式为：x.y[s] 其中：x：流水寄存器名称 y：具体寄存器名称 s：字段名称 例如： ID/EX.IR：流水寄存器ID/EX中的子寄存器IR IRID/EX.IR[op]：该寄存器的op字段（即操作码字段）

增加了向后传递IR和从MEM/WB.IR回送到通用寄存 器组的连接。 将对PC的修改移到了IF段，以便PC能及时地加 3.4 流水线的实现 流水寄存器的作用 将各段的工作隔开，使得它们不会互相干扰。 保存相应段的处理结果。 向后传递后面将要用到的数据或者控制信息 所有有用的数据和控制信息每个时钟周期 会随着指令在流水线中的流动往后流动一段。 增加了向后传递IR和从MEM/WB.IR回送到通用寄存 器组的连接。 将对PC的修改移到了IF段，以便PC能及时地加 4，为取下一条指令做好准备。

3.4 流水线的实现 每一个流水段进行的操作 IR[rs]＝IR6..10 IR[rt]＝IR11..15 IR[rd]＝IR16..20

流水线的每个流水段的操作 流水段 所有指令类型 IF/ID.IR ← Mem[PC] IF IF/ID.NPC, PC ← （if（（ EX/MEM.IR[op] == branch ）& EX/MEM.cond）{EX/MEM.ALUo} else {PC+4}）； (动画演示) ID/EX.A ← Regs[IF/ID.IR[rs]]；ID/EX.B ← Regs[IF/ID.IR[rt]]； ID/EX.NPC ← IF/ID.NPC；ID/EX.IR ←IF/ID.IR； ID ID/EX.Imm ← （IF/ID.IR16)16##IF/ID.IR16..31； (动画演示) ALU 指令 load/store 指令 分支指令 EX/MEM.IR ← ID/EX.IR； EX/MEM.ALUo ← ID/EX.A func ID/EX.B 或 ID/EX.A op ID/EX.Imm； EX/MEM.IR ← ID/EX.IR； EX/MEM.ALUo ← ID/EX.NPC + ID/EX.Imm<<2； EX/MEM.cond ← （ID/EX.A ==0）； EX/MEM.IR ← ID/EX.IR； EX/MEM.ALUo ← ID/EX.A + ID/EX.Imm； EX/MEM.B←ID/EX.B； EX (动画演示) (动画演示) (动画演示)

流水线的每个流水段的操作 流水段 任何指令类型 ALU 指令 load/store 指令 分支指令 MEM/WB.IR ←EX/MEM.IR； MEM/WB.ALUo ← EX/MEM.ALUo； MEM/WB.IR ← EX/MEM.IR； MEM/WB.LMD ← Mem[EX/MEM.ALUo]； 或 Mem[EX/MEM.ALUo] ← EX/MEM.B； MEM (动画演示) (动画演示) Regs[MEM/WB.IR[rd]] ← MEM/WB.ALUo； 或 Regs[MEM/WB.IR[rt]] ← Regs[MEM/WB.IR[rt]] ← MEM/WB.LMD； WB (动画演示) (动画演示)

流水线的控制 主要是如何控制4个多路选择器。 3.4 流水线的实现 MUX2：若ID/EX.IR中的指令是分支指令，则选择ID/EX.NPC，否则选ID/EX.A。 MUX3：若ID/EX.IR中的指令是寄存器－寄存器型ALU指令，则选ID/EX.B，否则选ID/EX.Imm。 MUX1：若EX/MEM.IR中的指令是分支指令，而且EX/MEM.cond为真，则选EX/MEM.ALUo，即分支目标地址，否则选PC+4。 MUX4：若MEM/WB.IR中的指令是load指令，则选MEM/WB.LMD，否则选MEM/WB.ALUo。

解决数据冲突的问题 3.4 流水线的实现 第5个多路器：从MEM/WB回传至通用寄存器组的写入 地址应该是从MEM/WB.IR[rd] 和MEM/WB.IR[rt]中选 一个。 寄存器－寄存器型ALU指令：选择MEM/WB.IR[rd] ； 寄存器－立即数型ALU指令和load指令：选择MEM/WB.IR[rt] 。 解决数据冲突的问题 所有的数据冲突均可以在ID段检测到。 如果存在数据冲突，就在相应的指令流出ID段之 前将之暂停。 完成该工作的硬件称为流水线的互锁机制。

3.4 流水线的实现 在ID段确定需要什么样的定向，并设置相应的控制。 降低流水线的硬件复杂度。不必挂起已经改变 了机器状态的指令） 也可以在使用操作数的那个时钟周期的开始检测冲突 和确定必需的定向。 检测冲突是通过比较寄存器地址是否相等来实现的。 举例： load互锁 由于使用load的结果而引起的流水线互锁称为load互锁。

ID/EX中的操作码 （ID/EX.IR[op]） 3.4 流水线的实现 在ID段检测是否存在RAW冲突 （这时load指令在EX段） ID/EX中的操作码 （ID/EX.IR[op]） IF/ID中的操作码 （IF/ID.IR[op]） 比较的操作数字段 load RR ALU ID/EX.IR[rt]=IF/ID.IR[rs] ID/EX.IR[rt]=IF/ID.IR[rt] load、store ALU立即数或分支

定向逻辑 3.4 流水线的实现 若检测到RAW冲突，流水线互锁机制必须在流水线中 插入停顿，并使当前正处于IF段和ID段的指令不再 前进。 将ID/EX.IR中的操作码改为全0 （全0表示空操作） IF/ID寄存器的内容回送到自己的入口 定向逻辑 要考虑的情况更多 通过比较流水寄存器中的寄存器地址来确定

3.4 流水线的实现 例如： 若 (ID/EX.IR.op==RR ALU)&（EX/MEM.IR.op==RR ALU）&（ID/EX.IR[rt]==EX/MEM.IR[rd]）， 则 EX/MEM.ALUo定向到ALU的下面一个输入。 若（ID/EX.IR[op]==RR ALU）&（MEM/WB.IR[op]==load）& （ID/EX.IR[rt]==MEM/WB.IR[rt]）， 则 把MEM/WB.LMD定向到ALU的下面一个输入。

流水线增设的定向路径

分支指令的条件测试和分支目标地址计算在EX段完成，对PC的修改在MEM段完成。 它所带来的分支延迟是3个时钟周期。 减少分支延迟：做如下改进 3.4 流水线的实现 控制冲突 分支指令的条件测试和分支目标地址计算在EX段完成，对PC的修改在MEM段完成。 它所带来的分支延迟是3个时钟周期。 减少分支延迟：做如下改进 （把上述工作提前到ID段进行） 在ID段增设一个加法器，用于计算分支目标地址。 把条件测试“=0？”的逻辑电路移到ID段。 这些结果直接回送到IF段的MUX1。 改进后的流水线对分支指令的处理。

3.4 流水线的实现

3.4 流水线的实现 改进后流水线的分支操作 流 水 段 分 支 指 令 操 作 IF/ID.IR ← Mem[PC]； IF/ID.NPC, PC ← (if(( IF/ID.IR[op]= =branch)&((Regs[IF/ID.IR[rs]] = = 0)) {IF/ID.NPC + (IF/ID.IR16)16 ## （IF/ID.IR16..31 << 2）} else {PC+4})； IF ID ID/EX.A ←Regs[IF/ID.IR[rs]]； ID/EX.B← Regs[IF/ID.IR[rt]]； ID/EX.IR ← IF/ID.IR； ID/EX.Imm ← （ IF/ID.IR16 ）16 ## IF/ID. IR16..31； EX MEM WB

流水技术适合于大量重复的时序过程，只有在输入端不断地提供任务，才能充分发挥流水线的效率。 总结 - 流水技术 流水技术适合于大量重复的时序过程，只有在输入端不断地提供任务，才能充分发挥流水线的效率。 流水线并不能减少（而且一般是增加）单条指令的执行时间，但却能提高吞吐率。 增加流水线的深度（段数）可以提高流水线的性能。 流水线的深度受限于流水线的额外开销。 当时钟周期小到与额外开销相同时，流水已没意义。因为这时在每一个时钟周期中已没有时间来做有用的工作。

流水线中各段的时间应尽可能相等，否则将引起流水线堵塞、断流。 总结 - 流水技术（续） 流水线需要有通过时间和排空时间。 通过时间：第一个任务从进入流水线到流出结果 所需的时间。 排空时间：最后一个任务从进入流水线到流出结 果所需的时间。 流水线中各段的时间应尽可能相等，否则将引起流水线堵塞、断流。 时间长的段将成为流水线的瓶颈。 流水线每一个功能部件的后面都要有一个缓冲寄存器（锁存器），称为流水寄存器。 作用：在相邻的两段之间传送数据，以保证提供后 面要用到的数据，并把各段的处理工作相互隔离。

总结 - 流水技术（续） 冲突问题 数据相关/名相关  数据冲突 控制相关  控制冲突 共享资源  结构冲突

3.5 向量处理机 3.5.1 向量处理方式 在流水线处理机中，设置向量数据表示和相应的向量指令，称为向量处理机。 不具有向量数据表示和相应的向量指令的流水线处理机，称为标量处理机。 3.5.1 向量处理方式 以计算表达式 D=A×（B＋C）为例 A、B、C、D ── 长度为N的向量

向量计算是按行的方式从左到右横向地进行。 3.5 向量处理机 横向(水平)处理方式 向量计算是按行的方式从左到右横向地进行。 先计算： d1←a1×(b1＋c1) 再计算： d2←a2×(b2＋c2) …… 最后计算： dN←aN×(bN＋cN) 组成循环程序进行处理。 ki←bi＋ci di←ki×ai 数据相关：N次 功能切换：2N次 不适合于向量处理机的并行处理。

向量计算是按列的方式从上到下纵向地进行。 3.5 向量处理机 纵向 (垂直)处理方式 向量计算是按列的方式从上到下纵向地进行。 k1←b1＋c1 d1←k1×a1 先计算 …… 再计算 …… kN←bN＋cN dN←kN×aN 表示成向量指令： K＝B＋C D＝K×A 两条向量指令之间： 数据相关：1次 功能切换：1次 受N大小的限制

对处理机结构的要求：存储器－存储器结构 3.5 向量处理机 向量指令的源向量和目的向量都存放在存储器 中，运算的中间结果需要送回存储器。 存储器－存储器型操作的运算流水线 例如：STAR-100、CYBER-205

把向量分成若干组，组内纵向处理，依次处理各组。 对于上述的例子，设： 3.5 向量处理机 纵横 (分组)处理方式 又称为分组处理方式。 把向量分成若干组，组内纵向处理，依次处理各组。 对于上述的例子，设： N=S×n＋r 其中N为向量长度，S为组数，n为每组的长度，r为余数。 若余下的r个数也作为一组处理，则共有S+1组。 运算过程为：

3.5 向量处理机 先算第1组： k1～n←b1～n＋c1～n d1～n←k1～n×a1～n 再算第2组： k(n+1)～2n←b(n+1)～2n＋c(n+1)～2n d(n+1)～2n←k(n+1)～2n×a(n+1)～2n 依次进行下去，直到最后一组：第S+1组。 每组内各用两条向量指令。 数据相关：1次 功能切换：2次

对处理机结构的要求：寄存器－寄存器结构 3.5 向量处理机 设置能快速访问的向量寄存器，用于存放源向量、 目的向量及中间结果，让运算部件的输入、输出端 都与向量寄存器相联，构成寄存器－寄存器型操作 的运算流水线。 典型的寄存器－寄存器结构的向量处理机 美国的CRAY-1、我国的YH-1巨型机

3.5.2 向量处理机的结构 以CRAY-1机为例 CRAY-1的基本结构 功能部件 3.5 向量处理机 美国CRAY公司 1976年 每秒1亿次浮点运算 时钟周期：12.5 ns CRAY-1的基本结构 功能部件 共有12条可并行工作的单功能流水线，可分别流 水地进行地址、向量、标量的各种运算。

3.5 向量处理机 6个单功能流水部件：进行向量运算 整数加（3拍） 逻辑运算（2拍） 移位（4拍） 浮点加（6拍） 浮点乘（7拍） 浮点迭代求倒数（14拍） 括号中的数字为其流水经过的时间，每拍为一个 时钟周期，即12.5 ns。

向量寄存组V 标量寄存器S和快速暂存器T 3.5 向量处理机 由512个64位的寄存器组成，分成8块。 编号：V0～V7 每一个块称为一个向量寄存器，可存放一个长度 （即元素个数）不超过64的向量。 每个向量寄存器可以每拍向功能部件提供一个数据元素，或者每拍接收一个从功能部件来的结果元素。 标量寄存器S和快速暂存器T 标量寄存器有8个：S0～S7 64位 快速暂存器T用于在标量寄存器和存储器之间提供缓 冲。

每个向量寄存器Vi都有连到6个向量功能部件的单独总线。 每个向量功能部件也都有把运算结果送回向量寄存器组的总线。 3.5 向量处理机 向量屏蔽寄存器VM 64位，每一位对应于向量寄存器的一个单元。 作用：用于向量的归并、压缩、还原和测试操作、 对向量某些元素的单独运算等。 CRAY-1向量处理的一个显著特点 每个向量寄存器Vi都有连到6个向量功能部件的单独总线。 每个向量功能部件也都有把运算结果送回向量寄存器组的总线。

只要不出现Vi冲突和功能部件冲突，各Vi之间和各 功能部件之间都能并行工作，大大加快了向量指 令的处理。 3.5 向量处理机 只要不出现Vi冲突和功能部件冲突，各Vi之间和各 功能部件之间都能并行工作，大大加快了向量指 令的处理。 Vi冲突：并行工作的各向量指令的源向量或结果向量使用了相同的Vi。 例如：源向量相同 V3←V1＋V2 V5←V4∧V1 功能部件冲突：并行工作的各向量指令要使用同一个功能部件。 例如：都需使用乘法功能部件 V3←V1×V2 V5←V4×V6

3.5 向量处理机 CRAY-1向量指令类型 Vk ← Vi op Vj Vk ← Si op Vj Vk ← 主存 主存 ← Vi

3.5.3 提高向量处理机性能的方法 提高向量处理机性能的方法 设置多个功能部件，使它们并行工作。 采用链接技术，加快一串向量指令的执行。 3.5 向量处理机 3.5.3 提高向量处理机性能的方法 提高向量处理机性能的方法 设置多个功能部件，使它们并行工作。 采用链接技术，加快一串向量指令的执行。 采用分段开采技术，处理大向量。 采用多处理机系统，进一步提高性能。

设置多个独立的功能部件。这些部件能并行工作，并各自按流水方式工作，从而形成了多条并行工作的运算操作流水线。 3.5 向量处理机 设置多个功能部件 设置多个独立的功能部件。这些部件能并行工作，并各自按流水方式工作，从而形成了多条并行工作的运算操作流水线。 例如：CRAY-1向量处理机有4组12个单功能流水部件： 向量部件：向量加，移位，逻辑运算 浮点部件：浮点加，浮点乘，浮点求倒数 标量部件：标量加，移位，逻辑运算， 数“1”/计数 地址运算部件：整数加，整数乘

链接特征：具有先写后读相关的两条指令，在不出现功能部件冲突和源向量冲突的情况下，可以把功能部件链接起来进行流水处理，以达到加快执行的目的。 3.5 向量处理机 链接技术 链接特征：具有先写后读相关的两条指令，在不出现功能部件冲突和源向量冲突的情况下，可以把功能部件链接起来进行流水处理，以达到加快执行的目的。 链接特性的实质 把流水线定向的思想引入到向量执行过程的结果。

例3.2 在CRAY-1上用链接技术进行向量运算 3.5 向量处理机 D=A×（B+C） 假设向量长度N≤64，向量元素为浮点数，且向量B、C已存放在V0和V1中。 画出链接示意图，并分析非链接执行和链接执行两种情况下的执行时间。 解 用以下三条向量完成上述运算： V3 ← 存储器 // 访存取向量A V2 ← V0 ＋ V1 // 向量B和向量C进行浮点加 V4 ← V2 × V3 // 浮点乘，结果存入V4

假设：把向量数据元素送往向量功能部件以及把结果存入向量寄存器需要一拍时间，从存储器中把数据送入访存功能部件需要一拍时间。 3.5 向量处理机 假设：把向量数据元素送往向量功能部件以及把结果存入向量寄存器需要一拍时间，从存储器中把数据送入访存功能部件需要一拍时间。

3条指令全部用串行方法执行，则执行时间为： [（1＋6＋1）＋N－1]＋[（1＋6＋1）＋N－1] 3.5 向量处理机 3条指令全部用串行方法执行，则执行时间为： [（1＋6＋1）＋N－1]＋[（1＋6＋1）＋N－1] ＋[（1＋7＋1）＋N－1] = 3N ＋22 （拍） 前两条指令并行执行，然后再串行执行第3条指令，则执行时间为： [（1＋6＋1）＋N－1]＋[（1＋7＋1）＋N－1] = 2N ＋15 （拍） 第1、2条向量指令并行执行，并与第3条指令链接执行。

[（1＋6＋1）] ＋[（1＋7＋1）] = 17 （拍） [（1＋6＋1）]＋ [（1＋7＋1）] ＋（N－1） 3.5 向量处理机 从访存开始到把第一个结果元素存入V4所需的拍数 （亦称为链接流水线的建立时间）为： [（1＋6＋1）] ＋[（1＋7＋1）] = 17 （拍） 3条指令的执行时间为： [（1＋6＋1）]＋ [（1＋7＋1）] ＋（N－1） = N＋16 （拍）

进行向量链接的要求 3.5 向量处理机 保证：无向量寄存器使用冲突和无功能部件使用冲突 只有在前一条指令的第一个结果元素送入结果向量 寄存器的那一个时钟周期才可以进行链接。 当一条向量指令的两个源操作数分别是两条先行指 令的结果寄存器时，要求先行的两条指令产生运算结果 的时间必须相等，即要求有关功能部件的通过时间相 等。 要进行链接执行的向量指令的向量长度必须相等， 否则无法进行链接。

当向量的长度大于向量寄存器的长度时，必须把长向量分成长度固定的段，然后循环分段处理，每一次循环只处理一个向量段。 3.5 向量处理机 分段开采技术 如果向量的长度大于向量寄存器的长度， 该如何处理呢？ 当向量的长度大于向量寄存器的长度时，必须把长向量分成长度固定的段，然后循环分段处理，每一次循环只处理一个向量段。 这种技术称为分段开采技术。 由系统硬件和软件控制完成，对程序员是透明的。

3.5 向量处理机 例3.3 设A和B是长度为N的向量，考虑在Cray-1向量处理器上实现以下的循环操作： DO 10 I = 1，N 10 A（I）= 5.0 * B（I） + C

3.5 向量处理机 当N ≤64时，可以用以下指令序列： S1 ← 5.0 ；将常数5.0送入标量寄存器S1 S2 ← C ；将常数1.0送入标量寄存器S2 VL ← N ；在向量长度寄存器VL中设置向量长度N V0 ← B ；从存储器中将向量B读入向量寄存器V0 V1 ← S1 × V0 ；向量B中的每个元素分别和常数S1相乘 V2 ← S2 + V1 ；向量V1中的每个元素分别和常数S2 相加 A ← V2 ；将计算结果从向量寄存器V2存入存储 器的向量A

3.5 向量处理机 当N ＞64时，就需要进行分段开采。 循环次数K ： 余数L：

3.5 向量处理机 S1 ← 5.0 ；将常数5.0送入标量寄存器S1 S2 ← 1.0 ；将常数1.0送入标量寄存器S2 VL ← L ；在向量长度寄存器VL中设置向量长度L V0 ← B ；从存储器中将向量B[0..L-1]读入向量 ； 寄存器V0 V1 ← S1 * V0 ；向量B中的每个元素分别和常数S1相乘 V2 ← S2 + V1 ；向量V1中的每个元素分别和常数S2相加 A ← V2 ；将计算结果从向量寄存器V2存入存储器 ；的向量A[0..L-1] 处理余 数部分, 计算L 个元素

3.5 向量处理机 For (I=0 to K-1) { V0 ← B ；从存储器中将向量B[L+I*64..L+I*64+63] ；读入向量寄存器V0 V1 ← S1 * V0 ；向量B中的每个元素分别和常数S1 ；相乘； V2 ← S2 + V1 ；向量V1中的每个元素分别和常数S2 ；相加 A ← V2 ；将计算结果V2存入存储器的向量 ； A[L+I*64… L+I*64+63] } 循环 K次, 分段 处理

许多新型向量处理机系统采用了多处理机系统结构。例如： 3.5 向量处理机 采用多处理机系统 许多新型向量处理机系统采用了多处理机系统结构。例如： CRAY-2 包含了4个向量处理机 浮点运算速度最高可达1800MFLOPS CRAY Y-MP、C90 最多可包含16个向量处理机

3.5.4 向量处理机的性能评价 衡量向量处理机性能的主要参数 ： 向量指令的处理时间 执行一条向量长度为n的向量指令所需的时间为 3.5 向量处理机 3.5.4 向量处理机的性能评价 衡量向量处理机性能的主要参数 ： 向量指令的处理时间 执行一条向量长度为n的向量指令所需的时间为 Ts ：向量流水线的建立时间，包括向量起始地址的设置、计数器加1等。 Tvf ：向量流水线的流过时间，它是从向量指令开始译码算起，到第一对向量元素流过流水线直到产生第一个结果元素所需的时间。 Tc ：流水线瓶颈段的执行时间

如果流水线不存在“瓶颈”，每段的执行时间等于一个时钟周期，则上式可以写为： 3.5 向量处理机 如果流水线不存在“瓶颈”，每段的执行时间等于一个时钟周期，则上式可以写为： s：向量流水线的建立时间所对应的时钟周期数 e：向量流水线的流过时间所对应的时钟周期数 Tclk：时钟周期时间 也可以将上式改写为： Tstart：向量功能部件启动所需的时钟周期数

对于一组向量指令而言，其执行时间主要取决于三个因素： 3.5 向量处理机 对于一组向量指令而言，其执行时间主要取决于三个因素： 向量的长度 向量操作之间是否链接 向量功能部件的冲突和数据的冲突性 把几条能在同一个时钟周期内一起开始执行的向量指令集合称为一个编队。 可以看出，同一个编队中的向量指令之间一定不存在流水向量功能部件的冲突和数据的冲突。

解：分为4个编队 3.5 向量处理机 例3.4 假设每种向量功能部件只有一个，那么下面的一组向量指令能分成几个编队？ LV V1，Rx MULTSV V2，R0，V1 LV V3，Ry ADDV V4，V2，V3 SV Ry，V4 解：分为4个编队 第一编队：LV 第二编队：MULTSV； LV 第三编队：ADDV 第四编队：SV

一个编队内所有向量指令执行完毕所要的时间为： 3.5 向量处理机 一个编队内所有向量指令执行完毕所要的时间为： （假设第i个编队中所有向量指令处理的向量元素个数均为n） Tci：第i个编队的执行时间 Tstartij ：第i个编队中第j条指令所使用向量功能部件的启动时钟周期数

3.5 向量处理机 编队后的向量指令序列总的执行时间为： m：向量指令序列编队的个数 Tstart：向量指令序列编队总的启动时钟周期数

编队并采用分段开采技术后，向量指令序列执行所需的总的时钟周期数为： 3.5 向量处理机 编队并采用分段开采技术后，向量指令序列执行所需的总的时钟周期数为： Tloop：分段开采所需的额外的时间开销 MVL：向量处理机的向量寄存器长度

例3.5 在某向量处理机上执行DAXPY的向量指令序列，也即计算双精度浮点向量表达式。 3.5 向量处理机 例3.5 在某向量处理机上执行DAXPY的向量指令序列，也即计算双精度浮点向量表达式。 其中X和Y是双精度浮点向量，最初保存在外部存储器中，α是一个双精度浮点常数，已存放在浮点寄存器F0中。计算该表达式的向量指令序列如下： LV V1，Rx MULTFV V2，F0，V1 LV V3，Ry ADDV V4，V2，V3 SV Ry，V4

3.5 向量处理机 解：可以把上述5条向量指令按如下方式进行编队： 第一编队：LV V1，Rx； 第二编队：MULTFV V2，F0，V1；LV V3，Ry； 第三编队：ADDV V4，V2，V3； 第四编队：SV Ry，V4。 假设： Tloop＝15 向量存储部件的启动：12个时钟周期 向量乘法部件的启动：7个时钟周期 向量加法部件的启动：6个时钟周期 向量寄存器长度：MVL

对n个向量元素进行计算所需的时钟周期数为 3.5 向量处理机 对n个向量元素进行计算所需的时钟周期数为 采用向量链接技术，那么指令序列可以编队为 第一编队：LV V1,Rx；MULTFV V2,F0,V1； 第二编队：LV V3,Ry；ADDV V4,V2,V3； 第三编队：SV Ry,V4。

对n个向量元素进行计算所需的时钟周期数为 3.5 向量处理机 第一编队启动需要12+7=19个时钟周期 第二个编队启动需要12+6=18个时钟周期 第三个编队启动仍然需要12个时钟周期 对n个向量元素进行计算所需的时钟周期数为

R ∞表示当向量长度为无穷大时，向量处理机的最高性能，也称为峰值性能。 3.5 向量处理机 向量处理机的峰值性能 R∞ R ∞表示当向量长度为无穷大时，向量处理机的最高性能，也称为峰值性能。 对于上述例题3.5向量指令序列中的操作而言，只有“MULTFV V2,F0,V1”和“ADDV V4,V2,V3”两条浮点操作向量指令。 假设该向量处理机的时钟频率为200 MHz，那么： 向量运算次数/周期时间

3.5 向量处理机 向量指令序列中浮点运 算次数 × 时钟频率 R = lim MFLOPS 向量指令序列执行所需 的时钟周期数  ∞ = lim MFLOPS n  ∞ 向量指令序列执行所需 的时钟周期数 2× n × 200 = lim MFLOPS n n  ∞ ×64＋ 3 n 64 2× n × 200 = lim MFLOPS n  ∞ 4 n = 100 MFLOPS

半性能向量长度n1/2是指向量处理机的运行性能达到其峰值性能的一半时所必须满足的向量长度。 3.5 向量处理机 半性能向量长度n1/2 半性能向量长度n1/2是指向量处理机的运行性能达到其峰值性能的一半时所必须满足的向量长度。 对于上面的例子 由于该向量处理机的峰值性能R∞＝100 MFLOPS， 所以根据半性能向量长度的定义有：

2×n1/2 ×200 ＝ 50 n1/2 ×64＋3n1/2 64 假设 ≤64，那么有： n1/2 2×n1/2 ×200 3.5 向量处理机 2×n1/2 ×200 ＝ 50 n1/2 ×64＋3n1/2 64 假设 ≤64，那么有： n1/2 64＋3n1/2 ＝ 2×n1/2 ×200 50 ＝ 8n1/2 5n1/2 ＝ 64，n1/2 ＝12.8 n1/2 ＝ 13

向量长度临界值nv是指：对于某一计算任务而言，向量方式的处理速度优于标量串行方式处理速度时所需的最小向量长度。 3.5 向量处理机 向量长度临界值nv 向量长度临界值nv是指：对于某一计算任务而言，向量方式的处理速度优于标量串行方式处理速度时所需的最小向量长度。 对于上述DAXPY的例子 假设，在标量串行工作方式下实现DAXPY循环的开 销为10个时钟周期。那么在标量串行方式下，计算 DAXPY循环所需要的时钟周期数为： Ts =( 10＋12＋12＋7＋6＋12 )×nv = 59nv

Tv = Ts 64＋3nv = 59nv 64 nv = = 2 56 3.5 向量处理机 在向量方式下，计算DAXPY循环所需要的时钟周期数为： Tv = 64＋3nv 根据向量长度临界值的定义，有： Tv = Ts 64＋3nv = 59nv 64 nv = = 2 56

习 题 设向量长度均为64，在CRAY-1机上所有浮点功能部件的执行时间分别为：乘法7拍，加法6拍，求倒数近似值14拍，从存储器中把数据送入访存功能部件需要一拍，把向量数据元素送往向量功能部件以及把结果存入向量寄存器需要一拍时间。请问下列各指令组，组内哪些指令可以链接？哪些不能链接？不能链接的原因是什么？分别计算出各指令组全部完成所需要的拍数。 （1）V0←存储器 （2）V2←V0*V1 V1←V2+V3 V3←存储器 V4←V5*V6 V4←V2+V3 （2）V0←存储器 （4）V0←存储器 V2←V0*V1 V1←1/V0 V3←V2+V0 V3←V1*V2 V5←V3+V4 V5←V3+V4