--------------------以下为1页的内容----------------------------------

第12章　流水线技术

12.1 流水线的基本概念

12.2 流水线的性能指标

12.3 DLX指令集和DLX流水线

12.4 流水线中的相关问题

12.5 指令级并行技术

--------------------以下为2页的内容----------------------------------

12.1 流水线的基本概念

流水线的作用是提高硬件部件的使用率，减少指令的平

均执行时间。

12.1.1　流水线的基本概念

1 什么是流水线

流水线（pipeline）是指在程序执行时多条指令重叠进行操作的一种准并行处理实现技术。

--------------------以下为3页的内容----------------------------------

1、顺序执行方式

顺序执行方式：一条指令接一条指令的执行方式。

特点：

·就整个程序而言，指令间是顺序串行执行。

·就每条指令而言，其内部各处操作也是顺序串行执行。

优点：控制简单

缺点：执行速度慢

--------------------以下为4页的内容----------------------------------

2、重叠执行方式

重叠执行方式：在第k条指令执行完成之前，开始执行第k+1条指令。

特点：

·就整个程序而言，相邻指令间是同时执行的。

·就每条指令而言，其内部各部操作也是顺序串行执行。

优点：就程序来看，提高了执行速度

--------------------以下为5页的内容----------------------------------

3、流水执行方式

流水执行方式：把指令的执行过程 分为若干个子过程，分别由不同的硬件装置去执行的方式。

如把指令的执行过程分为：取指、指令译码、取操作数和执行四个子过程 。

--------------------以下为6页的内容----------------------------------

--------------------以下为7页的内容----------------------------------

指令流水线是将指令执行分成几个子过程，每一个子过程对应一个工位，我们称为流水级或流水节拍，这个工位在计算机里就是可以重叠工作的功能部件，称为流水部件。

统水线要求所有的流水级部件必须在相同的时间内完成各自的子过程，在流水线中指令流动一步是一个机器周期。机器周期的长度必须由最慢的流水级部件处理子过程所需的时间决定。通常取1个时钟周期。

--------------------以下为8页的内容----------------------------------

流水线设计最难的任务是确定每个流水级功能部件处理事件的时间，平衡各流水级处理部件的处理时间。流水线计算机每条指令的平均执行时间是：

非流水线计算机上指令执行时间

每条指令平均执行时间=----------------------------------------------

流水线深度

流水线深度是指流水线中总的流水线级的数目。在这种条件下，流水线计算机的加速比就等于流水级的深度。

流水线只能减少每条指令的平均执行时间，一条指令的实际执行时间有可能比未流水时的时间还要长。流水线减少指令平均执行时间就是减少了指令的平均CPI。

--------------------以下为9页的内容----------------------------------

12.1.2 流水线的表示方法

流水线处理器的基本结构形式如图4-1所示（同步）。其中Si 为各流水部件，Li为锁存器， C为每个流水部件处理结果进入下一级的控制时钟。各流水级的处理时间Δti为一个流水部件处理子过程的时间 Δtsi 加上延迟时间Δtd。流水线机器周期应为：

T=max{Δ tsi}+ Δ td

--------------------以下为10页的内容----------------------------------

采用时空图来描述流水线，纵标为空间（各流水级），横标为时间（流水节拍），方格中的数字说明了该时间、空间的任务号。

时空图

--------------------以下为11页的内容----------------------------------

另外在分析流水线指令的执行过程中，用指令流水状态图表来描述，如表4-1（假定分五级流水线）

流水状态图表

--------------------以下为12页的内容----------------------------------

采用流水级中所用的主要功能部件来代替指令流水状态图表中的执行状态，如图4-3：

n=5

K=5

K+(n-1)

=5+4 = 9

完成五个任务需9个时钟

--------------------以下为13页的内容----------------------------------

1、把一个任务（一条指令｜操作）分成几个有连续的子任务，每个子任务为一个流水级。每个子任务由专门的硬件功能部件来完成。

2、每个功能部件后都要有锁存器。

3、每个流水功能部件的工作时间是不相同的，流水节拍时间由最长的流水功能部件处理时间决定。

4、只有连续不断地提供同一种任务才能发挥流水线的效率。

5、流水线工作一般有三个阶段，即装入、稳态和排空阶段。

12.1.3　流水线的特点：

装入：第1个任务入到出的时间。

排空：最后个任务一入到出的时间。

--------------------以下为14页的内容----------------------------------

由图4-2流水线时空图，我们可以得出K级流水线完成n个任务（指令）需K+(n-1)个时钟。如果非流水线计算机完成同样任务需nK个时钟，则它们的加速比是：

当n?∞ 时，加速比趋向于K。

6、流水线适用于大量重复性的、可分离的处理过程。

--------------------以下为15页的内容----------------------------------

12.1.4 流水线的分类

1、按处理级别分：

功能部件级：在实现较为复杂的运算时采用

指令级：将一条指令执行过程分为多个阶段

处理器间级：每个处理器完成其专门的任务。

例P1用于计算，P2用于图形，P3用于音频

--------------------以下为16页的内容----------------------------------

求阶差　

对阶　

尾数加　

规格化　

入

出

取指令　

译码　

执行　

存结果　

入

出

指令级流水线

浮点加法器流水线

--------------------以下为17页的内容----------------------------------

2、按完成的功能分类：

单功能流水线：只完成一种如乘法或浮点运算等，多用于数字信号处理器（DSP），各处理器可并行完成各自的功能，加快整机处理速度。

多功能流水线：在不同情况下可完成不同功能

--------------------以下为18页的内容----------------------------------

--------------------以下为19页的内容----------------------------------

3、按连接的方式分类：（多功能流水线）

静态流水线：同一时间内，多功能结构只能按一种功能的连接方式工作。

动态流水线：同一时间内，可以有多种功能的连接方式同时工作。

4、按处理的数据类型分类：

标量流水线：一般数据

向量流水线：矢量数据。X+Y=Z每一个代表一维数据。

--------------------以下为20页的内容----------------------------------

5、流水线结构上分类：

线性流水线：指各功能模块顺序串行连接，无反馈回路，如前面介绍的。

非线性流水线：带有反馈回路的流水线，如下：

调度预约表：P135 图4-6

--------------------以下为21页的内容----------------------------------

S1

S2

S3

S1

S2

S3

t0 t1 t2 t3 t4 t5 t6 t7

--------------------以下为22页的内容----------------------------------

12. 2 流水线的性能指标

吞吐率(throughput rate)：

　　　　　单位时间内流出流水线的任务数。

　　TP＝ n /Tk

n ：任务数

Tk：完成n个任务所用的时间

--------------------以下为23页的内容----------------------------------

Tk=k?t+(n-1) ?t

TP=n/Tk=n/k?t+(n-1) ?t

N ∞时:　TPmax=1/ ?t

--------------------以下为24页的内容----------------------------------

各段执行时间不相等的流水线

s1　

s2　

s3　

s4　

出

?t1= ?t ?t2= 3?t ?t3= ?t ?t4= ?t

入

TPmax=1/ max(?ti)=1/ 3?t

如何改进？

　1）瓶颈细分

　2）重复设置

--------------------以下为25页的内容----------------------------------

2　流水线的加速比（speedup ratio）

加速比：完成一批任务，不使用流水线与使用流水

线所用时间之比。

由图4-2流水线时空图，我们可以得出K级流水线完成n个任务（指令）需K+(n-1)个时钟。如果非流水线计算机完成同样任务需nK个时钟，则它们的加速比是：

S=

当n?∞ 时，加速比趋向于K。

nK ?t

K+(n-1) ?t

nK

K+(n-1)

=

--------------------以下为26页的内容----------------------------------

3　流水线的效率（efficiency）

=

n个任务占用的时空区有效面积

n个任务所用的时间与k个流水段所围的时空区域总面积

E=

kn?t

k(k+n-1) ?t

=

n

(k+n-1)

--------------------以下为27页的内容----------------------------------

4　流水线的最佳段数

段数增加，加速比提高，锁存器数增加，延迟时间和价格增加。

一般3－12段

段数≥8 为超流水线

--------------------以下为28页的内容----------------------------------

12. 3 DLX指令集与流水线

指令集介绍：p303

寄存器

数据类型

寻址方式和数据传输

指令格式

--------------------以下为29页的内容----------------------------------

非流水线的指令执行步骤

每条指令可以分5个步骤执行。

1、取指令周期（IF）

IR ? Mem[PC]

NPC ? PC + 4

2 、译码/读寄存器周期（ID）

A ? Reg[IR 6..10]

B ? Reg[IR11..15]

Imm ? ( (IR16)16## IR16..31)

3、执行/有效地址计算（EX）

Load/Store： ALUoutput ?A+Imm

R-R ALU： ALUoutput ?A func B

R-I ALU： ALUoutput ?A op Imm

Branch： ALUoutput ?NPC + Imm;

Cond ?A op 0

--------------------以下为30页的内容----------------------------------

4、存储器访问/转移完成（MEM）

Load/Store： LMD ? Mem[ALUoutput]

Mem[ALUoutput] ? B

Branch： if (Cond) then PC?ALUoutput

else PC ? NPC

5、写回周期（WB）

R-R ALU： Regs[IR16..20] ? ALUoutput

R-I ALU： Regs[IR11..15] ? ALUoutput

Load： Regs[IR11..15] ? LMD

--------------------以下为31页的内容----------------------------------

--------------------以下为32页的内容----------------------------------

流水线的实现

对前面的处理器，将五个执行步骤改为五个流水节拍，就形成具有五个流水深度的流水线结构处理器，每个节拍为一个时钟周期，每个时钟周期可以启动一条指令。如P136表4-2：

--------------------以下为33页的内容----------------------------------

基本处理器进行流水处理时，无法要求数据通路上的一个硬件单元在同一时刻做两个不同的操作。例如单个ALU不能同时进行有效地址计算和加法运算操作。因此，要保证流水线顺利进行，必须消除指令重叠执行时产生的各种冲突。

--------------------以下为34页的内容----------------------------------

基本流水线的工作过程

下图分析了RISC处理器在工作时的硬件资源使用情况，

--------------------以下为35页的内容----------------------------------

上图中时钟周期5（CC5）存在有以下几种冲突：

取指令和数据存取操作都要访问存储器。

解决办法：采用分离的数据和指令寄存器，如指令Cache和数据Cache。

注意：IF 流水时钟周期=非流水时钟周期，THEN

存储器的带宽增加5倍。

寄存器组有两个流水级要使用：

译码级（ID）

写回级（WB）

在一个周期进行一次读和一次写操作会产生冲突。

转移PC计算出来的值落后于下一拍IF。

a. PC自增（IF）

b. PC值修改（MEM）

--------------------以下为36页的内容----------------------------------

在一个节拍中有如下三种情况要使用ALU部件或加法器见P138表4-3：

在取指令级中计算PC指针值

计算存储器数据存取的有效地址

ALU操作中的算术或逻辑运算

其中对于L/S结构2、3不会在同一时钟周期内同时出现。

PC指针值计算需要单独用一个加法器，而有效地址计算和ALU操作可共用一个ALU部件。

--------------------以下为37页的内容----------------------------------

--------------------以下为38页的内容----------------------------------

流水线上每一个流水部件的处理结果都要放在寄存器里从前一流水级进入下一流水级。在流水级之间的寄存器称为流水线寄存器或流水线锁存器。

a.每个流水寄存器其实包含有一组寄存器

b.有时前面流水级部件的值是由后面流水级执行结果提供。

--------------------以下为39页的内容----------------------------------

--------------------以下为40页的内容----------------------------------

流水线的开头两级的工作情况是和当前执行的指令类型无关。以下是流水线各级所要处理的工作：

IF：取指令和计算新PC值，保存新PC值在流水线寄存器中，供后面计算转移目标地址时使用。

ID：选通寄存器并用符号位扩展指令寄存器IR的低16位，将NPC和IR传入ID/EX流水寄存器。

EX：完成ALU操作和地址计算，并将指令寄存器IR和B寄存器传入EX/MEM流水寄存器。

MEM：访问存储系统，作出转移决定，如果需要改写PC值，并将所需值传送到最后一级。

--------------------以下为41页的内容----------------------------------

WB：用ALU输出或LOAD指令的结果修改目的寄存器。

在整个流水过程中，指令寄存器始终从一级传到下一级，对它的使用也随之越来越少。但IF级的动作取决于EX/MEM中的指令是否是一条成功转移指令。

图4-8中四个多路选择电路，用来控制流水线工作。

ALU级：用于控制不同类型的数据进入ALU

ID/EX级：选择目标地址或源操作数

IF级：当前PC还是转移PC值

WB级：由WB的操作功能来控制

--------------------以下为42页的内容----------------------------------

流水线的基本性能

流水线增加了CPU的指令吞率——单位时间内完成的指令数。但它不减少单条指令的执行时间。

事实上单条指令的时间反而增加了流水线的开销时间----由流水线寄存器延时和时钟上升沿引起。

--------------------以下为43页的内容----------------------------------

例4-1：流水线性能计算

假定RISC流水线计算机，时钟周期是10ns，ALU操作和条件转移要4个时钟周期，而存储器访问操作要5个时钟周期。这三种指令操作的使用概率相应是40%，20%和40%。假设由于时钟上升和建立，流水线机器周期要增加1ns的开销。忽略任何其他延时影响，问：5级流水线机器可以获得的加速比是多少？

--------------------以下为44页的内容----------------------------------

已知

unpipeline: τ =10ns,

ALU(40%)、Branch(20%) 4τ

Load/Store (40%) 5τ

pipeline τ pipeline = (10+1) = 11ns

问：用流水线，执行速度提高几倍？

解：

非流水单条指令执行时间 = τ ? CPI

= 10 ?（60% ?4 + 40% ?5）= 44ns

流水平均指令执行时间： 11 ? 5/5= 11ns

Speedup = 44 /11 = 4

--------------------以下为45页的内容----------------------------------

例12-2 流水线与非流水线性能比较

已知：

CPI=1。设各流水级的执行时间分别为：

IF：10ns；ID：8ns；ALU：10ns；MEM：10ns

WB：7ns

解：

非流水平均指令执行时间 = 10+8+10+10+7 = 45ns

流水线时平均指令执行时间 = 11ns

Speedup = 45/11 = 4.1

假定机器指令执行需要5个功能单元，这5个单元的操作所需要的时间分别是10，8，10，10，7ns。假定流水线要增加1ns的开销，求出流失相对于单周期指令机器的加速比。

--------------------以下为46页的内容----------------------------------

12.4 流水线相关问题

流水线相关：是流水线中造成下一条指令不能在指令时钟周期被执行的情况。

流水线相关种类

1．结构相关：资源冲突（不支持某些指令组合重叠执行）

2．数据相关：后续指令的执行依赖于前面指令的执行结果

3．控制相关：因转移或修改PC引起的竞争

流水线停顿(stall)：

若 i 指令引起竞争，在 i 指令之前进入流水线的指令继续执行，而在 i 指令之后进入流水线或尚未进入流水线的指令停下来等待竞争消除。

--------------------以下为47页的内容----------------------------------

12.2.1流水线竞争时的性能

平均指令执行时间unpipeline

Speedup = ----------------------------------------

平均指令执行时间pipeline

nK τ unpipeline K τ unpipeline

=----------------------------------=-------------------- ? -----------

[(K+n-1)+xb] τ pipeline (K=n-1)/n+x/nb τ pipeline

CPI unpipeline τ unpipeline

=------------------ ? -----------

CPI I+ab τ pipeline

CPI unpipeline τ unpipeline

= ------------------ ? -------------

CPI pipeline τ pipeline

x——竞争出现的次数

b——每次竞争的平均代体（时钟数

a——竞争出现的概率 CPIi——理想流水线CPI

--------------------以下为48页的内容----------------------------------

CPI pipeline = CPI ideal +Cstall (流水线stall周期)

= 1 + Cstall

(设CPI ideal = 1 )

--------------------以下为49页的内容----------------------------------

忽略流水线开销（延迟等）：τ un=τ p

CPI unpipeline CPI unpipeline

Speedup = ----------------- = -------------------------

CPI pipeline 1+Cstall

最简单情况： 所有指令的执行周期数相等，均为流水级数,

则有：

CPI unpipeline = Pd(流水级)

例五级流水线：非流水时CPI=5，流水时CPI=1

Pd

Speedup = ---------------

1+Cstal

--------------------以下为50页的内容----------------------------------

非流水线时单时钟周期完成：CPI un=1 τ un<>τ p

1 τ unpipeline

Speedup = ------------------------- ? ----------------

1+ Cstal τ pipeline

若流水线各级完成时间均衡，且无其他开销，则

τ unpipeline

------------------ = Pd (流水级)

τ pipeline

Pd

Speedup = -----------------

1+ Cstal

--------------------以下为51页的内容----------------------------------

结构相关及防止措施

定义——如果流水线因资源冲突不能支持某些指令组合

的重叠执行，则称之为结构竞争。

产生原因

功能部件非完全流水

硬件资源数量不足

--------------------以下为52页的内容----------------------------------

例1：结构相关

--------------------以下为53页的内容----------------------------------

存储结构相关（图4-9）

--------------------以下为54页的内容----------------------------------

--------------------以下为55页的内容----------------------------------

例４－３结构竞争对性能的影响

已知

CPIideal = 1，数据访存占40%，

f hazard = 1.05 f ideal τ ideal= 1.05 τ hazard

解：

有冲突平均指令执行时间 = I* CPIhazard * τ hazard

= I*（1+0.4*1）* τ ideal/1.05

= 1.3 *I* τ ideal

CPI ideal < CPI hazard

假定程序中存储器数据访问有40％。计算机流水线忽略结构冲突的理想CPI等于1。又假设有结构竞争的计算机时钟频率是没有结构竞争时的1.05倍。不考虑其他性能损失。流水线有结构竞争和无结构竞争哪一个执行速度快？快多少？

--------------------以下为56页的内容----------------------------------

结构相关解决方法

重复设置功能部件

例如对于访存引起的结构竞争可以用下列方法：

用两个存储器：指令存储器/数据存储器； 指令Cache/数据Cache

用多端口存储器：一个端口用于指令访存， 另一个端口用于数据访存；

用指令缓冲栈/数据缓冲栈

功能部件完全流水化实现

--------------------以下为57页的内容----------------------------------

设计有hazard机器的原因

有些结构竞争在具体实现时对性能的影响不会很厉害；

降低实现成本

降低单元电路的延时时间非流水部件延时< 不完全流水部件 < 完全流水部件

减少电路的复杂程度

--------------------以下为58页的内容----------------------------------

例12-4： 非流水线浮点部件对性能的影响

现代许多RISC计算机，浮点操作都没有采用完全流水方式。假设在5级RISC流水处理器中，浮点乘法没用流水方式实现，有4个时钟周期的等待时间，已知浮点乘法指令的使用频度为14%。且假设浮点乘法指令在程序中完全均匀分布，请分析结构竞争对性能影响的程度。

解释：

一条要使用该条指令结果的指令需要隔多少时钟周期才能进入流水线，以保证得到正确的执行结果。

或一条浮点乘法必须和前一条指令隔几个时钟周期才不会与前一条浮点乘法指令冲突

--------------------以下为59页的内容----------------------------------

例题解答

最好情况：完全均匀分布

指令流水线最多能处理20%的浮点乘法 20%>14%

最坏情况：分布最不均匀

　因结构竞争造成CPI增加：14%*4 = 0.6

实测结果：用流水线实现与理想情况相比仅使性能降低3%　　

浮点乘法使用频度低

因数据竞争引起的Stall避免了结构竞争

--------------------以下为60页的内容----------------------------------

数据相关

数据竞争产生原因

指令之间存在着数据相关性

流水实现时的读写顺序?非流水时的读写顺序，使得在流水实现时无法保证指令的相关性。

[例] ADD R1, R2, R3

SUB R4, R5, R1

AND R6, R1, R7

OR R8, R1, R9

XOR R10, R1, R11

后四条指令都用ADD的结果R1作为源操作数

--------------------以下为61页的内容----------------------------------

例题的流水状态图

中断

--------------------以下为62页的内容----------------------------------

最简单的解决方法：插入stall

进入流水线的指令一旦检测到与前面的指令有RAW相关，就stall流水线，等待竞争消除，然后再继续执行。----极大地降低流水线的效率

寄存器读写小技巧：

前半周期：写；后半周期：读

但要寄存器组的操作速度提高一倍

--------------------以下为63页的内容----------------------------------

12.2.3.1旁路技术（forwarding, bypassing, short-circuiting)

注意：ADD结果在EX级之后就有了（CC3)

SUB真正需要R1的值是在EX级(CC4)

forwarding: EX/MEM中ALU的结果反馈给ALU的输入端

工作过程：

1、EX/MEM中ALU的结果反馈给ALU的输入端

2、若硬件检测到前面指令的目的Reg是当前ALU指令的源Reg，则把旁路结果作为ALU的输入。而不采用寄存器读出的值

3、ID级工作不变，供MUX选择输入

--------------------以下为64页的内容----------------------------------

比较前面指令的目的Reg是否为当前ALU指令的源Reg

--------------------以下为65页的内容----------------------------------

引入forwarding path后的状态图

--------------------以下为66页的内容----------------------------------

MEM级采用旁路

旁路电路不仅要包含同一流水功能单元之间的旁路通道，还要解决不同流水功能单元之间的旁路通道。

ADD R1，R2，R3

LW R4，0（R1）

SW 12（R1），R4

ADD指令从MEM级功能单元直接送到EX级功能单元。

各级流水寄存器和流水功能部件的输入端之间都要旁路机构。前面提到的EX级检测条件“0”也需要旁路机构。

--------------------以下为67页的内容----------------------------------

--------------------以下为68页的内容----------------------------------

数据相关分类

数据相关：指令间有依赖关系，且间距较近，重叠执行引起操作数访问顺序发生变化，在Cache失配时，导致运行结果错误。

寄存器操作数相关

存储器操作数相关（Cache失配时）

仅讨论寄存器操作数的数据相关问题

数据相关分类

先写后读相关 RAW（read after write）

写写相关WAW （write after write）

先读后写(WAR) （ write after read ）

--------------------以下为69页的内容----------------------------------

先写后读相关----RAW

假定有两条指令i和j，并且指令i在指令j前面进入流水线。

读操作在写操作之后，也称真相关

指令 j 需读源操作数Rx

指令 i 写目的操作数 Rx还未完成

采用旁路机构解决

--------------------以下为70页的内容----------------------------------

写写相关——WAW

写操作在写操作之后，也称输出相关

指令 j 写目的操作数 Rx在指令 i写 操作数 Rx之前

最后Rx中得到的是 i 指令写的错误结果

--------------------以下为71页的内容----------------------------------

例: 写写竞争

假设乱序执行,且存储器访问需要两个时钟周期.

LW R1, 0(R2)

ADD R1, R2, R3

基本流水线中不会发生WAW竞争, 原因是:WB总在最后一拍

浮点操作存在WAW

--------------------以下为72页的内容----------------------------------

先读后写相关——WAR

写操作在读操作之后，也称反相关

指令 j 写目的操作数 Rx在指令 i读 操作数 Rx之前

最后指令 i读得错误的（j指令改写过的）操作数

注意

基本流水线中一般不会出现

当指令乱序执行或存在长周期指令时出现

--------------------以下为73页的内容----------------------------------

例: WAR竞争

假设乱序执行,且存储器访问需要两个时钟周期.

SW 0(R1), R2

ADD R2, R3, R4

若R2直到MEM2才读,则造成WAR竞争.

基本流水线中不会发生WAR竞争,原因是: Read(ID)总是早于WB

--------------------以下为74页的内容----------------------------------

例：不能用“旁路”方法解决所有数据竞争

LW R1,0（R2）

SUB R4,R1,R5

AND R6,R1,R7

OR R8,R1,R9

R1最早等到第四拍MEM结束,才能得到.(即才能从Data Memory读入，存入暂存器）

SUB所用的R1最迟在第三拍EX开始时要准备好,与LW相差一拍。

LOAD指令的操作结果迟到不能用旁路机构，采用另一种硬件技术：流水内锁电路。

12.2.3.3 插入Stall

--------------------以下为75页的内容----------------------------------

前例的流水线状态图

--------------------以下为76页的内容----------------------------------

流水线内锁电路（interlock)

检测数据相关，并插入Stall暂停，直到数据竞争可以用旁路电路消除为止。

--------------------以下为77页的内容----------------------------------

表4-5 ALU指令需要Load指令产生的结果引起数

据竞争和消除过程

--------------------以下为78页的内容----------------------------------

例: Load Stall对流水线的性能影响

例4-5：假定30%的指令是Load指令，其中一半情况是紧跟Load后面的指令依赖Load指令的结果。如果出现数据竞争要停顿一个流水节拍。那么相对于理想流水线机器（CPI=1），实际流水线性能损失多少？忽略其他流水停顿。

--------------------以下为79页的内容----------------------------------

已知：Load指令的使用频度是30%，且Load后面的指令有50%运行时间是执行依赖于Load的指令。若竞争产生一个时钟周期的延时（只需插入一个Stall），理想机器（CPI=1）（不考虑其他Stall）？

解答：有数据竞争时，令CPI=2

实际CPI = 70% *1 + 30% * （50%*1 + 50%*2）

=0.7 + 0.45 = 1.15

实际机器性能损失：

(1.15-1)/1=15%

--------------------以下为80页的内容----------------------------------

编译调度（流水线静态调度或指令调度）

编译调度：由编译器重新按排指令执行顺序，来避免停顿周期。

针对Load 的调度：避免在一条Load指令之后立即出现一条使用Load指令目的寄存器的指令。即在如下的两条指令中间插入一条其它无关指令。

Load Rx， Data

OP ， ，Rx

基本模块：除第一条或最后一条指令外，不含转入或转出该段代码的指令序列

编译调度步骤：

画出依赖图 ? 重排指令使Stall最少

--------------------以下为81页的内容----------------------------------

表4-6 A=B+C的代码序列

--------------------以下为82页的内容----------------------------------

编译调度例4-6： a = b+c ; d = e-f

LW Rb, b

LW Rc, c

ADD Ra,Rb,Rc

SW a, Ra

LW Re, e

LW Rf, f

SUB Rd,Re,Rf

SW d, Rd

LW Rb， b

LW Rc， c

LW Re， e

ADD Ra，Rb,Rc

LW Rf， f

SW a， Ra

SUB Rd，Re,Rf

SW d， Rd

流水线静态调度需要增加使用寄存器数目。

--------------------以下为83页的内容----------------------------------

P153 图4-18表明采用编译调度减少load引起的数据竞争是相当成功的。

延时加载：load操作后的指令不用其结果的方法。

延时槽：load指令后，要安插调度指令的地方。

--------------------以下为84页的内容----------------------------------

12.2.3.4数据竞争检测控制的实现

指令发射：指令从译码ID级流入执行级EX级。一条指令已建

立了这一过程，称已发射（issued）。

数据竞争控制实现的关键问题：

如何检测数据竞争：在ID级检测所有数据竞争。

流水内锁在ID级作检测。（一般在指令发射(issue)前作检测，因为指令一旦发射进入执行级，往往容易改变处理器状态，不容易使之指令停顿。）

旁路可以在EX或MEM级检测。

--------------------以下为85页的内容----------------------------------

LOAD引起数据况竞争的几种情况

P154表4-7：

操作数不相关：无竞争

操作数相关：需插入Stall解决

操作数相关：需旁路机构解决

操作数相关： 可用按序访问（时钟节拍分前后）解决

--------------------以下为86页的内容----------------------------------

Load引起数据竞争的检测

流水内锁的检测和实现

立即数型：

寄存器型：

6

5

5

16

6

5

5

5

11

--------------------以下为87页的内容----------------------------------

如何实现内锁

一旦检测到Load Delay情况,只需

把下一条指令的ID/EX暂存器的操作码寄存器内容置0,使ADD R0, R0, R0,成为一条空操作。

使IF/ID中被停顿指令的操作码寄存器的内容延长保留一拍。

--------------------以下为88页的内容----------------------------------

分析需使用旁路硬件的情况P155表4-9及P156图4-19

--------------------以下为89页的内容----------------------------------

以ALU输入端口为数据输入端的旁路电路

--------------------以下为90页的内容----------------------------------

控制相关及防止措施

控制相关主要来自转移指令。

控制相关造成的性能损失比数据相关大

最简单的处理方法（插入STALL）

ID知道转移后，暂停流水线，直到MEM后PC确定下来

IF ID EX MEM WB

IF s s IF ID

3拍

若转移指令占30% ，则

考虑控制竞争后的流水线CPI实际=1+30%*3 = 1.9

(假设CPI理想= 1)

--------------------以下为91页的内容----------------------------------

控制竞争带来延时的流水线状态图

--------------------以下为92页的内容----------------------------------

控制竞争带来3个停顿的原因分析

转移地址在第三拍EX中计算；转移条件比较结果在第四拍即MEM 拍才送到IF级的MUX。所以要等到第四拍结束才能知道转移成功与否。

--------------------以下为93页的内容----------------------------------

减少控制竞争延时的措施

提前计算转移的目的地址和提前比较转移条件可使转移指令造成的停顿周期由3个减少到1个。

尽早知道转移是否成功： 将 =0检测移入ID级

尽早计算出目标地址：在ID级引入ALU计算目标地址

--------------------以下为94页的内容----------------------------------

目标地址计算和条件判断提前后的流水线

修改后的流水线前二级流水部件工作过程：P157表4-11

--------------------以下为95页的内容----------------------------------

条件判断及目标计算提前后要注意的情况

注意：

一条ALU指令后跟一条转移指令，可能引起数据相关

ALU Rx, -, - IF ID EX MEM WB

Branch Rx, L1 IF stall ID EX MEM WB

（原本RX在EX中用到，现在在ID要用到，产生数据竞争）

流水线级数越多，转移损失越大

CPI越小，转移造成的性能损失所占比例越大

--------------------以下为96页的内容----------------------------------

12.2.4.1 分析转移行为特点

由P159图4-21及4-22得，

平均成功率：67%

向前转移的成功率平均为：60%

向后转移的成功率平均为：95%

转移

条件转移

无条件转移

向前条件转移

向后条件转移

--------------------以下为97页的内容----------------------------------

12.2.4.2减少流水线转移损失的基本措施

1、预测转移成功。即预测每一个转移都成功，但必须等算出转移目标地址，才能取转移目的指令。

条件： 转移目标地址形成早于转移条件码结果生成，才有可能改善控制竞争时的性能。

注意：因为在基本流水线机器中，转移地址计算和转移条件比较（即知道转移能否成功）是同时获得的，因而无利可图。但对其他有些机器可能有利。

方法：基于对转移行为的预测。

--------------------以下为98页的内容----------------------------------

2、预测转移不成功。即无论最后是否转移，都在下一拍立即取转移指令的下一条指令进入流水线开始执行。

问题： 在确定转移是否成功前不能修改机器状态

实际转移不成功： 无Stall

实际转移成功： 1 Stall

编译优化：将大概率分支放在不成功分支中

--------------------以下为99页的内容----------------------------------

预测正确，即实际为不转移，则无停顿

--------------------以下为100页的内容----------------------------------

预测出错，即实际为转移，停顿一个周期

--------------------以下为101页的内容----------------------------------

两种方案的比较

预测成功利用转移成功率高的行为特性，实现比较复杂。要在一个时钟周期内计算完目标地址，用新地址取指，时间较紧张，必须用旁路机构。

预测不成功利用转移不成功的概率的转移行为特性，这个概率数值要比前者低，但实现方法简单，预测命中损失为0，不命中也只有一个时钟损失。

两者对性能损失的防止效果是相当的。

--------------------以下为102页的内容----------------------------------

3、提前生成条件码。判断条件是否满足需要条件码已经准备就绪，尽早形成条件码，可以尽快得到条件转移是否满足。

4、适当增加指令缓冲区器。对转移成功和不成功两个方向都取指，减少不命中的性能损失。对循环操作更有利。

5、提高转移预测的命中率。采用动态预测，根据实际程序工作时转移行为概率自动调整预测形式，提高命中率。

--------------------以下为103页的内容----------------------------------

6、延时转移技术

转移延时槽：从开始处理转移指令到明确转移是否发生之间存在一段转移延时时间，（branch-delay-slot)。

一般机器中这一由转移指令造成的延时时间为一个时钟周期，即允许利用branch-delay-slot执行一条指令。

Delayed branch方法就是由编译器挑选合适的，有用的指令填入延时槽中执行，即合理利用这一延时时间，而不浪费。

具体措施

硬件：无论转移成功与否都执行延时槽中的指令

编译：在延时槽中插入合适的有效指令

--------------------以下为104页的内容----------------------------------

延时转移技术

对延时槽中指令的处理称为转移延时技术

--------------------以下为105页的内容----------------------------------

三种转移延时槽调度方法（由编译完成）

a. 取自转移指令前。在转移指令前找一条与转移指令不相关的有用指令插 入转移延时槽。最佳选择

b.取自目标指令。在转移成功分支中找一条与转移指令无关的指令插入延时槽。而且要求所选延时槽指令不会影响不成功分支的正确执行。

即转移成功概率大时（如循环）采用，即编译预测转移成功时，选用此策略；

c.取自转移指令后。在转移不成功分支中找一条与转移指令无关的指令插入延时槽。而且要求所选延时槽指令不会影响成功分支的正确执行。

转移成功概率小时有效，即编译预测转移不成功；

d.插入空指令。

--------------------以下为106页的内容----------------------------------

图示：三种转移延时槽调度方法

--------------------以下为107页的内容----------------------------------

7、硬件支持延时转移

延时转移技术对性能改善的限制：

插入延时槽的指令是有限制的。

编译对转移与否的预测能力。

硬件清除转移延时槽功能：

当转移行为预测不正确时，自动消除转移延时槽内的指令，使硬件支持编译调度可以直接使用b、c两种方案，而不必考虑延时槽内指令的影响。

--------------------以下为108页的内容----------------------------------

--------------------以下为109页的内容----------------------------------

P163表4-14 转移延时槽长度为1的转移调度效率

1）20%的延时填入的是空操作

2）80%是标准延时转移和清除转移，各占一半

--------------------以下为110页的内容----------------------------------

四种转移处理机制的性能评估

在流水线实现的处理机中延时转移技术是编译程序员可见的特性。

优点：利用简单的编译调度技术就可减少控制竞争带来的性能损失，明显改善处理器性能。

缺点：计算机实现要有较大变化。

深度流水线时，延时槽大，实现代价很高。

额外硬件代价：多一个PC寄存器

原因：当转移成功而 延时槽指令发生中断时，因为转移目标地址和延时槽指令地址是不连续的，所以保护现场要保存

当前中断指令PC + 转移目标地址

--------------------以下为111页的内容----------------------------------

4.2.4.3控制竞争时流水线性能

流水深度

Speedup=

1+转移引起的流水停顿周期

流水深度

=

1+转移概率*转移损失

--------------------以下为112页的内容----------------------------------

表4-15 不同转移方案的转移代价

--------------------以下为113页的内容----------------------------------

例4-7

MIPS-R4000型具有8级流水线,在获得转移地址前要花费2个流水级，假定条件比较在寄存器上进行没有延时，转移条件的比较要增加一个时钟周期。表4-16给出类三种最简单的转移预测方案的转移代价。

根据图4-21和图4-22的个SPEC整数基准程序数据，计算此流水线转移对CPI的影响？

--------------------以下为114页的内容----------------------------------

解：

--------------------以下为115页的内容----------------------------------

12.2.4.4 控制竞争中的数据相关及编译优化

转移预测的编译优化技术的作用:

延时转移效率与转移频度和预测的准确性直接相关

例 LW R1, 0(R2)

SUB R1, R1, R3 LW与SUB有竞争, 产生

BEQZ R1, L 一个Load stall.

OR R4, R5, R6

ADD R10,R4,R3

L: ADD R7, R8, R9

若已知转移总是成功，且不成功分支不需要用到R7的值，则可以将ADD指令插到LW之后；（转移总是成功，所以不需要延时槽，作简单指令调度消除STALL）

若已知转移总是不成功，且成功分支中不会用R4的的值，则可以将OR指令插到LW之后；（同上）

转移是否成功的信息也同样可运用于延时转移中。

--------------------以下为116页的内容----------------------------------

几种静态转移预测技术

利用 以前程序的运行情况统计，大部分转移是成功的，采用预测成功方案。

平均出错率 33%，

出错率变化范围较大 10% ~ 58%

基于方向预测，用后向转移成功和前向转移不成功。

对于反向转移，预测成功；（反向转移成功率95%）

对于正向转移，预测转移失败。

3. 根据早期程序运行的分布情况来做预测。

转移行为呈双峰

--------------------以下为117页的内容----------------------------------

12.2.4.5 基本流水线的性能测试

P167图4-27

平均每条指令有0.06拍转移停顿，0.07拍Load停顿。

CPI=1.13，比理想时下降13%。

--------------------以下为118页的内容----------------------------------

12.2.5实现流水线的困难

中断处理

指令集的复杂性

--------------------以下为119页的内容----------------------------------

中断处理

中断的类型(interrupt, fault, exception)

I/O设备请求、OS调用、指令执行跟踪、断点、整数运算溢出、FP操作出错

缺页中断、不对齐访问、存储保护错、未定义指令、硬件错、电源故障

--------------------以下为120页的内容----------------------------------

中断性质

同步/异步

同步：程序每次执行都在同样的地方发生中断

异步：由处理机、存储器以外其他设备引起，可在当前指令执行完后处理。

用户请求 / 强制中断

用户请求：可预测，可在当前指令执行完后处理

强制中断： 用户程序无法控制的硬件原因，不可预测

用户可屏蔽 / 不可屏蔽

用户可屏蔽：

不可屏蔽：用户无法屏蔽的中断，通常是那些硬件引起中断

--------------------以下为121页的内容----------------------------------

中断性质（续）

指令内 / 指令间

指令内： 往往是同步中断，若指令内中断为异步中断往往导致程序终止运行。比指令间发生的中断难处理，因为要终止执行，在处理完后还要重执

可恢复执行 / 不可恢复执行

可恢复执行：

不可恢复执行：中断发生就导致程序停止运行

--------------------以下为122页的内容----------------------------------

中断处理难点

流水中断实现中最困难的：

指令内中断 within

中断指令恢复执行 restartable

中断处理要求：

关闭流水线

保护处理器状态（恢复执行指令的PC值）

处理中断

恢复处理器状态，重新执行指令

中断处理的关键点

中断检测（每个节拍开始时检测）

正确保存处理器状态

--------------------以下为123页的内容----------------------------------

中断处理步骤

流水线处理机保护流水线状态的步骤：

强制在下一个IF级取入Trap指令；

Trap指令中止所有指令的写操作包括异常指令及其后进入流水线的指令的写操作；其方法是将所有指令的流水寄存器置“0”，并制止其他指令进入流水线，然后启动中断指令。

操作系统的中断处理例程接管控制后，立即保存中断指令的PC值，以便在中断处理结束后返回断点。

注意：

如果采用延时转移技术的话，那么，保存单个PC值就不能完整地保存流水线状态。所以，此时在第三步就需要保存 （延时槽长度+1）个PC值。

--------------------以下为124页的内容----------------------------------

精确中断

精确中断定义：

发生中断时能够使流水线恰好停在中断指令之前，即使得那些在异常指令之前的指令执行完毕，而异常指令及其后指令能在中断处理后恢复执行，则称此流水线支持精确中断。

精确中断的实现

理想的情况：中断指令没有改变处理器状态，那么正确处理中断只要保证中断指令没有执行结果就可以。

其它情况，即中断指令在进行中断处理前已经完成写结果操作，改变了处理器状态，则硬件必须能够恢复源操作数的值。（比如浮点操作执行往往需要很多个时钟周期，而且常常是乱序完成的，当中断指令尚未进行处理时，可能后续的指令已经执行结束了。）

--------------------以下为125页的内容----------------------------------

引入非精确中断

因为实现精确中断，硬件必须能够恢复中断指令执行前的处理器状态，所以允许指令执行的重叠程度大大降低，所以支持精确中断的流水线的执行速会很慢(慢10倍以上)，所以引入非精确中断。

一些高性能计算机，允许有两种运行模式：

精确中断模式： 一般在代码调试时用

非精确中断模式：

要有足够的信息使中断结束后程序能从断点继续执行下去

这种方式速度快，但对操作系统的要求较高

--------------------以下为126页的内容----------------------------------

实现精确中断的必要性

精确中断的必要性：

精确中断在有些机器中不是必须实现的功能，但实现精确中断能简化OS系统界面。

哪些机器必须实现精确中断，（精确中断可以用硬件实现也可以部分由软件支持）

一般整数流水线容易实现精确中断，同时，为了适应虚拟存储器的需要，存储器访问指令都提供精确中断支持。因此设计人员总是为整数流水线实现精确中断。

--------------------以下为127页的内容----------------------------------

基本流水级可能发生的中断

--------------------以下为128页的内容----------------------------------

整数流水线的各个流水级均可能产生中断

在同一个时钟周期可能产生多个中断，且指令顺序与中断顺序不同。因为有多条指令同时在运行。

处理

先处理数据访存引起的缺页中断，然后重执指令LW。

ADD指令可能会再次发生中断（但一般回和原来的中断不同），此时再独立处理这个中断。

--------------------以下为129页的内容----------------------------------

精确中断的实现

中断实现的三个关键：

保证正确的处理顺序：设置与指令关联的状态向量。 一出现中断，则相应的状态位置位

关闭写操作： 一旦状态向量有一位置位，则关闭写操作 （寄存器写和存储器写）

检测：在离开MEM前 / 进入WB时检查状态向量

正确的中断处理顺序指：

第 i 条指令引起的中断先于第 i+1条指令的中断的处理

指令中第 i 级发生的中断先于第 i+1级的中断的处理

--------------------以下为130页的内容----------------------------------

异常中断处理原则

如果多个异常中断顺序出现，常用的方法是先处理与最早指令有关的异常情况，以避免指令相关性。

如果有多个异常中断同时出现时，那么应首先处理最严重的异常中断，如指令i在EX级发生溢出，而指令i+1在ID级发现非法指令代码，那么应首先处理溢出。

流水线中某条指令前几级流水级出现异常中断，该指令前的指令必须执行完，避免前指令对其产生影响，然后再进行异常中断处理。

--------------------以下为131页的内容----------------------------------

12.2.5.3 指令集复杂性

指令交付：当指令保证能执行完毕时，称其为 committed.

对于复杂指令和长周期指令要实现精确中断很困难：

交付前可能修改机器状态（如自增指令）

如果保存的是非精确断点，则恢复重执很困难；

避免指令在交付前修改状态，则硬件代价很高。因为一个寄存器可能已经被多次修改。

一般做法： 虽然在交付前允许状态修改，但记录所有的修改情况。一旦发生中断，则利用这些记录恢复寄存器的值，使处理器状态回退到中断指令执行前。

指令集的复杂度增加了流水线及中断实现的困难

--------------------以下为132页的内容----------------------------------

12.3 多周期操作的流水线策略

RISC设计思想并不排斥多周期指令和复杂指令存在

分析:

浮点操作要在5个时钟内完成是不现实的

我们可以改进、扩展基本流水线

浮点操作和整数操作在同一流水控制下工作

流水线扩展

分析整数和浮点操作其主要区别在于EX级

EX级的执行周期随指令操作不同而不同

修改基本流水线结构、增加流水部件

--------------------以下为133页的内容----------------------------------

12.3.1 基本流水线作如下扩充

浮点指令 在EX级可多周期自反馈执行

修改整数部件、增加浮点操作部件

主整数部件——与基本流水线相同，主要处理存取指 令和数据，整数ALU操作和转移指令

浮点和整数乘法部件: 整数乘、浮点乘

浮点加法部件——处理浮点加、减和转换操作

浮点和整数除法部件整数除、浮点除

如果流水线出现结构竞争或数据竞争则插入Stall

输入、输出流水部件共用

浮点功能部件非流水(每拍1个时钟)或非完全流水实现(每拍>1个时钟)

指令按序发射

--------------------以下为134页的内容----------------------------------

描述FP流水线的两个参量

启动间隔（initiation interval/repeat interval)

两条同类型指令进入流水线而不发生结构竞争所必须保持的时间间隔（反映操作的流水化实现程度）

部件延时（等待时间、latency)

产生结果指令与使用结果的指令进入流水线而不发生数据竞争（用forwarding path) 所必须保持的时间间隔

最大不超过EX级的流水深度-1

--------------------以下为135页的内容----------------------------------

多周期操作流水线--基本流水线扩充

--------------------以下为136页的内容----------------------------------

本章中各部件的两个参量约定值

--------------------以下为137页的内容----------------------------------

浮点加法器和浮点乘法器完全流水实现;

完成浮点加法需4个时钟周期。所以在浮点加法指令后的第3条指令可以通过提前电路顺利使用浮点加法的结果数据。

完成浮点乘法需7个时钟周期。故在浮点乘法指令后的第6条指令可以通过提前电路顺利使用浮点乘法的结果数据。

浮点Load指令和整数Load指令均在MEM完成取数操作，意味着memory在一个时钟周期里要能提供32bit或64bit的数据。

浮点除法用非流水方式实现，所以可能产生结构竞争。

--------------------以下为138页的内容----------------------------------

流水浮点操作的流水线结构

要引入新的流水线锁存器

M1/M2, M2/M3, M3/M4, M4/M5, M5/M6, M6/M7

A1/A2, A2/A3, A3/A4

引入新的连接寄存器

ID/EX, ID/M1, ID/A1, ID/DIV

EX/MEM, M7/MEM, A4/MEM, DIV/MEM

--------------------以下为139页的内容----------------------------------

引入浮点操作的流水线

--------------------以下为140页的内容----------------------------------

12.3.2长延时流水线的竞争与消除

非完全流水引起的结构竞争（浮点除法）

同一时钟周期内的Reg写操作可能多于一个(结构竞争)

指令执行所需时钟周期数不同，到达WB级顺序不同于发射次序（乱序），所以有WAW竞争（无WAR竞争）

RAW竞争比整数流水线严重，引起的Stall 增多

指令完成顺序不同于发射顺序（乱序），所以中断会出现新的问题

--------------------以下为141页的内容----------------------------------

非完全流水引起的结构竞争

--------------------以下为142页的内容----------------------------------

Reg端口结构竞争

--------------------以下为143页的内容----------------------------------

Reg写口结构竞争的解决方法

在ID级跟踪Reg写口使用情况——移位寄存器

代价：移位寄存器、写竞争检测逻辑

优点：在ID级检测，控制简单

缺点：操作功能部件推迟占用，使RAW竞争带来的延时更厉害

在进入MEM或WB级前检测

优点： 竞争检测逻辑简单

缺点: 有两处检测竞争（可能造成前一级产生竞争），插入Stall，控制复杂

--------------------以下为144页的内容----------------------------------

12.3.2.1　WAW 数据竞争

--------------------以下为145页的内容----------------------------------

WAW 数据竞争的解决方法

推迟发射LD，直到ADDD进入MEM级

检测到竞争后，取消第一次写，立即发射LD（两个写操作之间没有读操作是很少见的，此时第一次写无意义）

（都在 ID 级检测）

困难之处：如何知道LD在ADDD之前结束（必须实现知道各操作部件的流水级数和当前ADDD指令所在位置）

实际使用简单处理方法：

if 本指令的目的Reg = 已发射指令的目的Reg

then 暂停发射当前指令

--------------------以下为146页的内容----------------------------------

浮点流水线中的RAW竞争

--------------------以下为147页的内容----------------------------------

浮点指令和整数指令之间的竞争

浮点寄存器 + 通用寄存器

Load/Store 指令与浮点指令之间

--------------------以下为148页的内容----------------------------------

引入浮点操作流水线竞争处理小结

在发射前需作竞争检测，竞争检测逻辑与整数流水线类似。指令在发射前要做以下判断：

检查是否有结构竞争

当所需的功能部件不忙时(非完全流水引起，在DLX流水线中，只有浮点除法指令需要做此项检查)，并且确认在当前指令执行到WB级时，寄存器写端口是可用的。

检查是否有RAW数据竞争

当前指令的源操作数要与所有pending指令的目的寄存器比较，若有相等的，则stall直到源操作数可用。

检查是否有WAW数据竞争

当前指令与所有在流水线中的前面的指令比较，若目的寄存器相同，则stall，直到竞争消除。

--------------------以下为149页的内容----------------------------------

12.3.2.2浮点流水线时的精确中断

困难之处：

按序发射，乱序完成

例： DIVD F0, F2, F4

ADDD F10, F10, F8

SUBD F12, F12, F14

在乱序执行情况下，ADDD指令和SUBD指令会在DIVD前先完成。若DIVD引起一个浮点运算出错中断时，ADDD和SUBD已经完成执行，修改了寄存器的值，此时，即使在软件的帮助下，硬件也很难将寄存器的值恢复到DIVD执行前，因此实现精确中断非常困难。

--------------------以下为150页的内容----------------------------------

乱序执行时中断的可能解决方法1

忽略乱序执行造成的影响，按不精确中断方法处理。

60年代和70年代早期使用，一些超级计算机也用此法

不允许出现一些特殊中断，或由硬件处理而不暂停流水线。由于采用虚拟存储器技术，并且符合IEEE的浮点运算标准，要求必须支持精确中断，因此今天的计算机一般无法采用这种方法。如前述，解决方法是：

采用精确中断/非精确中断两种执行模式

启动慢的精确中断模式可以通过模式开关来实现，也可以通过插入一条显式的检测浮点中断的指令来实现。

--------------------以下为151页的内容----------------------------------

乱序执行时中断的可能解决方法2

用缓冲器保存指令操作结果，直到所有先发射的指令都完成

代价昂贵

由于操作部件的功能时间差距很大,使得要缓冲的结果数非常多。

若等待一条指令的结果的时间很长的话，可能还要将等待在缓冲序列中的结果通过旁路送到需要它的功能部件去，这又需要大量的比较器和很大的多路转换器。

两种不同的实现方法

历史文件：记录寄存器的原值，在中断发生时，能够通过历史纪录重新加载寄存器的值，状态恢复到中断指令执行前的状态。(VAXes的自增自减寻址指令采用了类似的方法）

未来文件：用未来文件记录一些乱序执行完指令的结果，当指令按顺序完成次序轮到某指令写结果时，利用未来文件记录的值更新寄存器。当中断发生时，寄存器状态即为准确的中断现场状态(PowerPC 620和MIPS R10000采用了一种扩充的类似方法。）

--------------------以下为152页的内容----------------------------------

乱序执行时中断的可能解决方法3

允许中断在某种程度上不精确，但保持信息使自陷处理例程能生成精确中断的执行序列。

记录流水线中在某一已完成指令之前，但在中断指令之后的所有指令的操作以及指令的PC值。当中断处理后，由软件重新模拟执行这未完成的指令序列。

例 Instruction1 --最终发生中断的长操作指令；

Instruction2 , …, Instructionn-1-- 未完成的指令序列；

Instructionn-- 已完成的指令。

若已知流水线中所有指令的PC值，软件就可以知道所有指令的状态。因为中断发生时，指令n已完成，所以希望在中断处理后，能从指令n+1开始重新执行。中断处理之后，由软件模拟执行Ins1, …, Insn-1,然后返回断点，从n+1条指令处开始恢复执行。

--------------------以下为153页的内容----------------------------------

乱序执行时中断的可能解决方法4

采用流水线指令发射暂停方法。

确保已发射的所有指令都将顺利完成，不会产生中断，才继续发射新的指令。

浮点功能部件必须早知道某指令是否会产生异常中断，即在EX级之前作出判断。

--------------------以下为154页的内容----------------------------------

12.4 流水线的动态调度

静态调度：利用编译器来进行优化指令代码的次序。依据程序未执行时的行为特征和统计数据进行的调度策略。

动态调度：通过硬件在程序执行时重新安排代码的执行序列来减少竞争引起的流水线停顿时间。

优点：

能调度在编译时不知道的竞争情况

符合程序执行的实际情况

具有更高的效率和准确性

简化编译程序设计

代码的移植性强

缺点：硬件复杂，异常处理困难（非精确）

--------------------以下为155页的内容----------------------------------

12.4.1数据竞争的动态调度

前述假定，流水线取指、发射的条件是当前指令与已发射进入流水的指令之间没有数据相关，或存在相关但相关数据可以从旁路通道直接获取。否则，暂停流水线。

动态调度不可能消除真正的数据相关，但它可以在出现数据相关时，避免暂停流水线。

--------------------以下为156页的内容----------------------------------

按序发射，按序执行的限制：

若一条相关指令被暂停发射，则所有后续指令都被暂停，即使不相关。

DIVD F0,F2,F4 ;1

ADDD F10,F0,F8 ;2

SUBD F12,F8,F14 ;3

上述指令2要依赖于1完成后才能执行，所以在1未完成时2要停顿，并且此时3也要停顿，虽然3与1、2无关。造成这一情况主要是因为指令的按序发射，按序执行。

--------------------以下为157页的内容----------------------------------

乱序发射，乱序执行：

首先检测结构竞争，然后等待数据竞争。即要指令所需要的操作数准备好，指令就可以发射进入EX级。

主要难点：由于指令完成不按顺序，中断处理很困难。（采用不精确中断）

实现：修改流水线结构，将ID分解成两级

发射（issue）。指令译码，同时检测结构竞争。

读操作数(RD:read operands )。等到数据竞争消除，如操作数有效，则读操作数。

--------------------以下为158页的内容----------------------------------

指令取入流水线后将其送入单一入口的锁存器或进入指令队列中，发射级从锁存器中或指令队列中发射指令，EX级紧跟在读操作数级后面。

在发射级指令是有序发射的，但在RD级根据操作数的时局情况暂停或立即处理，即进入EX级是乱序的。

--------------------以下为159页的内容----------------------------------

12.4.1.1 记分牌（soreboarding）动态调度算法

基本过程：所有指令有序地通过发射级，但进入读操作级后，每条指令有的立即处理，有的暂停，使后面几级流水线指令的执行变成乱序进行。

对监测WAR型竞争非常有用：如

DIVD F0,F2,F4

ADDD F10,F0,F8

SUBD F8（F10）,F8,F14

由于DIVD时间长所以ADDD 不能立即执行，可以调SUBD 先执行，但由于SUBD 与ADDD 为WAR竞争所以要防止。如F8改成F10，则会出现WAW竞争。

目的：在无资源竞争的前提下保持每一个时钟周期执行一条指令的速度。

思想方法：尽可能提早指令执行。

任务：控制指令的发射和执行，同时检测所有竞争。

--------------------以下为160页的内容----------------------------------

--------------------以下为161页的内容----------------------------------

以RISC的浮点处理器为例：含有两个乘法器、一个加法器、一个除法器、一个整数部件。

作用：当每条指令通过记分牌时，分析、记录指令间的数据相关情况，决定指令何时读操作数、何时执行、何时写目标寄存器。也称集中式动态调度。

将记分牌过程以四级流水代替原来标准的ID、EX、WB级：

1）发射级（issue）：指令所需的功能部件是空闲的（无结构竞争），且与其他已激活的指令没有相同的目的寄存器（无WAW竞争），则发射、并修改数据结构，建立数据相关性记录。当发射暂停时，IF取得的指令要进入缓冲区。

--------------------以下为162页的内容----------------------------------

读操作数(read operands)：决定何时读操作数，要求没有已发射的激活指令要对该操作数进行写操作，或没有当前活动的功能部件正在向包含该操作数的寄存器写结果。以上两级相当于原来的标准的ID级。

执行（execution）:当所有的源操作数可用后，开始执行。

写结果（write result）:当有WAR型竞争存在，则暂停该指令，否则写结果。出现以下情况要暂停：

存在一条前面的指令还没有读源操作数。

一个源作数和该指令的结果采用同一寄存器。

注意：记分牌不能利用旁路技术的优点。

--------------------以下为163页的内容----------------------------------

主要数据结构：

指令状态表：指令所处四个状态中的哪一个

功能部件状态表： buzy,op,Fi, Fj,Fk,Qj,Qk ,Rj,Rk

寄存器结果状态表：写寄存器的操作部件

以下面程序为例分析记分牌数据结构和工作过程：

LD F6,34(R2)

LD F2,45(R3)

MULTD F0,F2,F4 ;F2未准备好时要二个stall

SUBD F8,F6,F2 ; F2未准备好时要一个stall

DIVD F10,F0,F6 ;F0未准备好时要多个stall

ADDD F6,F8,F2 ;F8未准备好时要二个stall,且不能在DIVD使用F6前改就变F6的值。

--------------------以下为164页的内容----------------------------------

记分牌构成分为三个部分：

1、指令状态。指出指令工作处于四级中的哪一级。

--------------------以下为165页的内容----------------------------------

2、功能部件工作状态。指出工作情况，每个部件需9项相关参数

--------------------以下为166页的内容----------------------------------

3、寄存器结果状态。如果有一条已激活指令有一目的操作数是寄存器，则指出哪个功能单元将写这个寄存器。

上述各状态处于：

第一条LD指令已经完成并且结果已写入寄存器，而第二条LD指令已经执行完成，但还没有写结果，第三、四、五已经发射，但被暂停在读操作数一级，等候操作数的到来。

指令MULTD进入写结果级前的记分牌数据结构如表4-25 P183

--------------------以下为167页的内容----------------------------------

--------------------以下为168页的内容----------------------------------

记分牌控制流水线执行的详细过程

FU表示指令使用的功能部件

D表示目的寄存器名

S1、S2表示源寄存器名

Op表示指令所做的操作

Fj(FU):表示Fj要用功能部件FU

Fj(FU)?S1表示源寄存器名置入

Result表示目的寄存器D的植

如果有一条指令的源操作数和Fi(FU)相同或某指令已写了这些寄存器（即Rj=Yes 或Rk=Yes），则有WAR竞争，暂停写结果。

--------------------以下为169页的内容----------------------------------

--------------------以下为170页的内容----------------------------------

计分牌算法的主要局限性

性能依赖于指令间本身所具有的并行性

记分牌的项数（向前检查的指令条数）是有限的

功能部件的种类与数目直接与结构竞争可能带来的延迟有关

名称相关的存在仍导致WAW和WAR竞争，并带来延时。

2、3可用增加容量和功能部件数量来克服，4可以用下一节的寄存器改名方案来克服。

--------------------以下为171页的内容----------------------------------

12.4.1.2 Tomasulo 动态调度算法

最初的目的：获得高浮点运算性能

记分牌＋寄存器重命名　＝Tomasulo

消除寄存器名称相关，从而避免产生WAR和WAW型竞争技术。寄存器改名技术的实施是采用大量的虚拟寄存器来取代指令中的寄存器，就象保存在计分牌中那样。它是基于旁路机构来实现的。

--------------------以下为172页的内容----------------------------------

与记分牌算法不同之处：

一旦操作数可用就可取到保存站中

利用重命名消除WW和WAR竞争

竞争检测和执行控制分布处理（由保存站处理）

结果从保存站直接送到执行部件，而不经过寄存器　

支持多次迭代间的重迭执行

带Tag的保存站和Load/Store buffers 相当于虚拟寄存器

--------------------以下为173页的内容----------------------------------

基本结构： p187

基本步骤：

发射：从浮点操作队列到保存站。

执行：若操作数还不可用，监听CDB等待数据，

若所有操作数可用，操作部件空，执行相

应操作。

写结果：得到计算结果后，放到CDB上，送入寄

存器或需要该数据的保存站或缓冲里。

--------------------以下为174页的内容----------------------------------

与记分牌算法的不同之处：

不必检测WW和WAR竞争

不是让寄存器等待结果，而是通过CDB广播结果

存取操作和基本操作部件同等对

主要数据结构

保存站状态：Buzy,op,Vj,Vk,Qj,Qk

寄存器状态：写结果的操作部件名

--------------------以下为175页的内容----------------------------------

12.4.2控制冲突的硬件预测

4.4.2.1基本转移预测和转移预测缓冲器

转移预测缓冲器或转移历史表:是用转移指令地址的低位来寻址的存储器。

最简单情况：转移预测缓冲器用一位，仅用于减少由于计算转移目标地址PC值而引起转移延时。

缺点：当出现不发生的转移指令时，会出现两次不正确预测。

--------------------以下为176页的内容----------------------------------

例4-10

某循环体的转移行为是9次转移成功，紧接后面一次转移不成功。假定用一位转移预测缓冲器来控制转移，对此循环的预测正确率是多少？

解：8次预测正确2次预测不正确。预测正确率是80%。

通常下，在循环体中多次条件转移是成功的，仅一次是不成功的。因此一位预测对出现一次不成功转移的误测率是2次误预测。

--------------------以下为177页的内容----------------------------------

两位预测方案

出现两次预测失误才改变预测器状态。

预测转移成功

预测转移成功

预测转移不成功

预测转移不成功

不成功

成功

成功

不成功

成功

成功

不成功

不成功

正确性：99%——82%

--------------------以下为178页的内容----------------------------------

两位预测器是用一个转移行为去预测后继的转移行为。为了提高精度，考虑当前转移指令以前其他转移指令的行为。

相关预测器或双层预测器：同时用多条转移指令的行为去预测转移结果的转移预测器。

（1，1）维转移预测器：利用程序中前一次转移指令的执行情况，从一对1位转移预测器中选择预测值。

（2，2）维转移预测器：

--------------------以下为179页的内容----------------------------------

12.4.2.2 转移目标缓冲器(BTB)

转移目标缓冲器(BTB)：将转移指令转移后要执行的下一条指令地址存放的地方。

解决方法：对于基本流水线，在IF级取指时访问它，如命中，可以提早一个时钟周期。

--------------------以下为180页的内容----------------------------------

12.5高级流水线--进一步开发指令级的并行处理

指令级并行性(ILP：Instruction Level Parallelism)

------指令间潜在的可重叠执行的特性

尽量减少指令间的前后关系，减少由此引起的stall.

主要技术：循环展开、超标量流水线、超级流水线、超长指令字、和软件流水、路径调度等。

--------------------以下为181页的内容----------------------------------

12.5.1 循环体并行处理

转移发生概率：15%，平均6~7条指令一次转移

基本块间指令重叠率小：开发基本块间的ILP

表4-37浮点操作延迟时间

--------------------以下为182页的内容----------------------------------

例：for(i=1;i<=1000;i++) x[i]=x[i]+s;分别作无调度和有调度展开如下：（R1是数组的初始地址，F2保存标量值S）

Loop: LD F0, 0(R1)

ADDD F4, F0, F2

SD 0(R1), F4

SUBI R1, R1, 8

BNEZ R1, Loop

F D X M W

F D s A1 A2 A3 A4 W

F s D s s X W

F s s D X M W

F s D X M W

10 CC F F

（到下一循环取指令）

Loop: LD F0, 0(R1)

SUBI R1, R1,#8

ADDD F4, F0, F2

BNEZ R1, Loop

SD 8(R1), F4

F D X M W

F D X M W

F DA1A2A3A4W

F D X M W

F D s X M W

6 CC F s D X M W

1、展开方法

--------------------以下为183页的内容----------------------------------

对上述指令进行分析：

1、其中LD、ADDD、SD为对数组元素进行操作

2、而SUBI、BNEQ、STALL是为了进入下一次循环进行的操作

可以对以上循环进行如下有调度和无调度循环展开：

--------------------以下为184页的内容----------------------------------

Loop: LD F0, 0(R1)

stall

ADDD F4, F0, F2

stall, stall

SD 0(R1), F4

LD F6, -8(R1)

stall

ADDD F8, F6, F2

stall, stall

SD -8(R1), F8

LD F10, -16(R1)

stall

ADDD F12, F10, F2

stall, stall

SD -16(R1), F12

LD F14, -24(R1)

stall

ADDD F16, F14, F2

stall, stall

SD -24(R1), F16

SUBI R1, R1, #32

stall

BNEZ R1, loop

stall

P205例4-14，采用4次循环体复制展开循环

一、无调度：

--------------------以下为185页的内容----------------------------------

展开4次

Loop展开4次

SUBI指令中R1要减32

注意loop展开后,每一次迭代采用不同寄存器,如用F0, F6, F10, F14表示LD的目的寄存器,分别表示不同变量

展开后loop需28个时钟周期,即每次迭代平均需28/4=7个时钟周期,仅通过展开,消除loop overhead, 就可缩短每次迭代的时钟周期数, 这里没有做任何调度.

--------------------以下为186页的内容----------------------------------

二、有调度展开

Loop: LD F0, 0(R1)

LD F6, -8(R1)

LD F10, -16(R1)

LD F14, -24(R1)

ADDD F4, F0, F2

ADDD F8, F6, F2

ADDD F12, F10, F2

ADDD F16, F14, F2

SD 0(R1), F4

SD -8(R1), F8

SUBI R1, R1, #32

SD +16(R1), F12

BNEZ R1, Loop

SD +8(R1), F16

(因R1已减32, 所以加8)

--------------------以下为187页的内容----------------------------------

展开调度后的循环共需14个时钟周期,则每次迭代平均只需14/4=3.5个时钟周期

调度展开的循环对提高性能的作用大于单纯的调度

展开增加了指令数，增加了寄存器的个数，增加了存储空间，所以不能无限展开

--------------------以下为188页的内容----------------------------------

2、相关性分析

循环体能并行展开的条件是连续两次迭代之间是否有数据相关。

如：for (i=1;i<=100;i++)

{ a[i+1]=a[i]+c[i]; 语句S1

b[i+1]=b[i]+a[i+1]; 语句S2

}

1、语句S1要用到前一次循环的结果a[i]，S2要用到前一次循环的结果b[i]，称为循环传递相关。

2、在同一循环中S2要用到S1的计算结果a[i+1]，称为内相关。

对于循环传递相关，只要连续的循环迭代有序进行，可以不影响并行性。

对于内相关，只要同一循环内保证数据的次序，可以不影响并行性。

--------------------以下为189页的内容----------------------------------

例4-15分析相关性，并确定循环能否并联？如何并联？

for (i=1;i<=100;i++)

{ a[i]=a[i]+b[i]; 语句S1

b[i+1]=c[i]+d[i]; 语句S2

}

S1和前一次S2相关（b[i]），存在循环传递相关，由于相关不是环形的：s1依赖于s2，s2不依赖于s1。所以可并联。

并联时，作变换如下：

a[1]=a[1]+b[1];

for (i=1;i<=99;i++)

{ b[i+1]=c[i]+d[i];

a[i+1]=a[i+1]+b[i+1];

}

b[101]=c[100]+d[100];

--------------------以下为190页的内容----------------------------------

12.5　指令级并行技术

指令流水比传统的串行提高了吞吐率。最好可以做到一

个时钟周期可以完成一条指令。

CPI（clock　Cycles　Per　Instruction）

ILP (instruction level parallelism):一个时钟周期内流水线上流出的指令数。

CPI<1,　如何实现？

--------------------以下为191页的内容----------------------------------

12.5.1 多发射处理机

分类：

1、超标量处理机；

2、超流水线处理机；

3、超标量超流水线处理机；

4、超长指令字处理机；

--------------------以下为192页的内容----------------------------------

1　超标量处理器机：

在一个时钟周期内能同时发射多条指令的处理机。

基本要求：

有两套或以上指令执行部件。一般可以发射1-8条。

通常要求指令是不相关的，并要满足一些约束条件。

--------------------以下为193页的内容----------------------------------

2　超流水线处理机

　在一个时钟周期内能分时发射多条指令的处理机。

　　或：

　指令流水线段数＞＝8。

--------------------以下为194页的内容----------------------------------

3　超标量超流水线处理机

　　　超标量＋超流水线

　　在一个时钟周期内发射指令m次，每次发射n条指令，每个时钟周期共发射指令m×n条 。

--------------------以下为195页的内容----------------------------------

4　超长指令字（VLIW）处理机：

是每次发射一个由若干条简单指令组成的长指令。

思想：由编译器程序在编译时找出指令的潜在的并行性，把多个能并行执行的操作组合在一起，形成一个具有多个操作段的超长指令。

特点：

1）超长指令由编译器生成；

2）每个时钟周期发射一条长指令；

3）长指令的多个操作字段独立控制每个功能部件。

4）含有大量的数据通路和功能部件。

--------------------以下为196页的内容----------------------------------

12.5.3 编译支持指令级并行性开发

要充分发挥多发射处理器的效率，需要指令级有大量的不相关连续指令存在，这就需要编译对程序代码进行优化调度，支持指令级的并行性开发。

--------------------以下为197页的内容----------------------------------

12.5.3.1 程序变量相关性分析

开发程序中指令级的并行性主要有三方面的任务：

1、寻找线性基本块中的不相关代码，用于编译调度。

2、寻找那些可能包含有并行性的循环。

3、消除变量名相关。

相关分析主要是分析数组变量的相关性，确定是否存在相关链。

--------------------以下为198页的内容----------------------------------

例：

for (i=1;i<=100;i++)

{ a[i]=b[i]+c[i]; 语句S1

d[i]=a[i]*e[i]; 语句S2

}

以上变量a只是内相关，没有循环传递相关，可以展开循环。且两次a[i]访问是同一地址，第二次可以直接利用第一次存在寄存器中的结果，减少存储访问。

--------------------以下为199页的内容----------------------------------

例：递归调用循环

for (i=2;i<=100;i++)

{ y[i]=y[i-1]+y[i]; 语句S1

}

存在循环传递相关。相关距离是1。

for (i=0;i<=100;i++)

{ y[i]=y[i-5]+y[i]; 语句S1

}

存在循环传递相关。相关距离是5。相关距离越大，展开循环可以有更多的并行性。

--------------------以下为200页的内容----------------------------------

例4-17：找出相关，消除相关

for (i=1;i<=100;i++)

{ y[i]=x[i]/c; S1

x[i]=x[i]+c; S2

z[i]=y[i]+c; S3

y[i]=c-y[i]; S4 }

以上存在四种相关：

1、s1和 s3， s1和 s4存在着 y[i]变量的内相关。

2 、s1读 x[i]， s2 写x[i]， s1和 s2存在逆相关 WAR

3、 s3读 y[i]， s4写 y[i]， s3和 s4存在逆相关 WAR

4 、s1和 s4都写 y[i]，存在输出相关 WAW 。

for (i=1;i<=100;i++)

{ t[i]=x[i]/c; y改名t消除输出相关

x1[i]=x[i]+c; x改名x1消除逆相关

z[i]=t[i]+c; y改名t消除逆相关

y[i]=c-t[i]; }

--------------------以下为201页的内容----------------------------------

12.5.4在硬件支持下进一步开发并行性

1、预测指令

2、硬件支持的编译投机

3、基于硬件的投机技术

--------------------以下为202页的内容----------------------------------

12.5.5超级流水线

一个流水线具有较高的时钟频率和较深的流水线（如8级、10级），称之为超级流水线（superpipeline）技术。

增加流水深度的主要方法是将原有流水线的功能部件流水化。即将基本流水线的每一级细分成若干级小过程。

例P234表4-45、P235图4-46

--------------------以下为203页的内容----------------------------------

12.6非线性流水线

非线性流水线中，各非线性流水级之间存在有反馈回路，一条指令在流水的全过程中，可能会多次通过同一级，这样如果每个时钟发射一条指令，就会发生几个操作同时争用同一流水级。

要想不发生冲突，应该间隔适当时间发射下一条指令，这就需要对流水线指令发射进行调度。

1、采用二维的预约表进行调度：

例如，1号功能部件使用相隔时钟数为8，2号功能部件使用相隔时钟数为1、5、6。此时如果两条指令相隔8个节拍进入流水线会发生争用1号部件，相隔1、5、6节拍进入流水线，会争用2号部件。P236图4-47

--------------------以下为204页的内容----------------------------------

2、冲突向量状态。P236图4-47

由禁止表{1，5，6，8}得出初始冲突向量（10110001），并可知第二条指令可间隔2，3，4，7个时钟进入流水线，可以依次推出后续冲突向量。

本文文档版下载：http://www.k12zy.com/50/45/504548.htm