重叠执行和先行控制

指令缓冲存储区和相应的控制逻辑

  • 按队列方式工作。

  • 只要指令缓冲站不满,它就自动地向主存控制器发取指令请求,不断地预取指令。

指令分析部件

  • 每分析完一条指令,就自动向指令缓冲站发出取下一条指令的请求。指令取出之后就把指令缓冲站中的该指令作废。

  • 指令缓冲站中存放的指令的条数是动态变化的。

两个程序计数器

  • 先行程序计数器PC1:用于从主存预取指令;

  • 现行程序计数器PC:用来记录指令分析部件当前正在分析的指令的地址。

先行控制技术:缓冲技术和预处理技术的结合

  • 缓冲技术:在工作速度不固定的两个功能部件之间设置缓冲器,用以平滑它们的工作。

  • 预处理技术:预取指令、对指令进行加工以及预取操作数等。

采用先行控制方式的处理机结构

1

先行操作站

  • 在指令分析部件和运算器之间提供缓冲

  • 先行:因为其中的指令对于运算器正在执行的

​ 指令来说是后续的,但却被先行取出并预处理。

指令分析部件

  • 从先行指令缓冲站取指令,并进行预处理,加工成统一格式的RR型操作命令,然后送入先行操作站。

  • 对于不同指令做不同的处理。

运算器

  • 从先行操作站取出RR型操作命令并执行。

  • 每执行完一条,将运算结果写入通用寄存器组或者后行写数站。

  • 继续执行先行操作站中的后续命令。

先行读数站

  • 作用:接收指令分析部件送来的访问主存的有效地址,按顺序依次从主存读取操作数,提供给运算器

​ 使用。

  • 先行:因为对于正在执行的指令来说,先行读数站中的操作数是先行取出的。

后行写数站

  • 作用:接收从运算器送来的结果数据,并负责将之写入主存。

  • 后行:因为站在运算器的角度来看,结果数据不是在相应的指令运算完后立即写入主存,而是由后行写数站滞后写入的。

  • 每一个存储单元由3部分组成:后行地址字段、后行数据字段、标志字段。每当从运算器接收数据时,将之放入后行数据字段,并把相应的数据有效标志置位。后行写数站的控制逻辑自动向主存发出写数请求。当写数据操作完成后,也要置位有关标志。

采用先行控制后的一次重叠执行:

2

3

流水线的基本概念

并行性:时间重叠,资源重复。

流水计算机系统中采用的并行处理方式是(时间重叠 )方式。

流水线中的每个子过程及其功能部件称为流水线的级或段,段与段相互连接形成流水线。流水线的段数称为流水线的深度。

吞吐率:在单位时间内流水线所完成的任务数量或输出结果的数量。

4

n:任务数

Tk:处理完成n个任务所用的时间

各段时间均相等的流水线时空图

5

流水线完成n个连续任务所需要的总时间为:Tk=kΔt+(n-1)Δt=(k+n-1)Δt

实际吞吐率:6

最大吞吐率:7

最大吞吐率与实际吞吐率的关系:

8

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

9

流水线的最大吞吐率为:

10

细分瓶颈段:

14

重复设置瓶颈段:

缺点:控制逻辑比较复杂,所需的硬件增加了。

13

11

12

加速比:完成同样一批任务,不使用流水线所用的时间与使用流水线所用的时间之比。

假设:不使用流水线(即顺序执行)所用的间为Ts,使用流水线后所用的时间为Tk,则该流水线的加速比为

15

流水线的实际加速比为:

16

最大加速比:

17

流水线的效率是流水线的实际加速比S与它的最大加速比k的比值。

当E=1时,S=k,实际加速比达到最大。

效率:流水线中的设备实际使用时间与整个运行时间的比值,即流水线设备的利用率。由于流水线有通过时间和排空时间,所以在连续完成n个任务的时间内,各段并不是满负荷地工作。

  • 通过时间:第一个任务从进入流水线到流出结果所需的时间。

  • 排空时间:最后一个任务从进入流水线到流出结果所需的时间。

多功能流水线在做某一种运算时,总有一些段是空闲的。

静态流水线在进行功能切换时,要等前一种运算全部流出流水线后才能进行后面的运算。

运算之间存在关联,后面有些运算要用到前面运算的结果。

流水线的工作过程有建立与排空部分。

18

19

流水线设计中的若干问题:

  1. 瓶颈问题

    • 理想情况下,流水线在工作时,其中的任务是同步地每一个时钟周期往前流动一段。

    • 当流水线各段不均匀时,机器的时钟周期取决于瓶颈段的延迟时间。

    • 在设计流水线时,要尽可能使各段时间相等。

  2. 流水线的额外开销

    • 流水寄存器延迟

    • 时钟偏移开销

流水寄存器需要建立时间和传输延迟

  • 建立时间:在触发写操作的时钟信号到达之前,寄存器输入必须保持稳定的时间。
  • 传输延迟:时钟信号到达后到寄存器输出可用的时间。

  • 时钟偏移开销: 流水线中,时钟到达各流水寄存器的最大差值时间。(时钟到达各流水寄存器的时间不是完全相同)

  1. 冲突问题

经典的5段RISC流水线 :

一条指令的执行过程分为以下5个周期:

  1. 取指令周期(IF)

    • IR ← Mem[PC] 。  

    • PC值加4。(假设每条指令占4个字节)

  2. 指令译码/读寄存器周期(ID)

    • 译码。

    • 用IR中的寄存器编号去访问通用寄存器组,读出所需的操作数。

  3. 执行/有效地址计算周期(EX)

    不同指令所进行的操作不同:

    • 存储器访问指令:ALU把所指定的寄存器的内容与偏移量相加,形成用于访存的有效地址。

    • 寄存器-寄存器ALU指令:ALU按照操作码指定的操作对从通用寄存器组中读取的数据进行运算。

    • 寄存器-立即数ALU指令:ALU按照操作码指定的操作对从通用寄存器组中读取的第一操作数和立即数

    进行运算。

    • 分支指令:ALU把偏移量与PC值相加,形成转移目标的地址。同时,对在前一个周期读出的操作数进行

    判断,确定分支是否成功。

  4. 存储器访问/分支完成周期(MEM)

    • 该周期处理的指令只有load、store和分支指令。

    • 其他类型的指令在此周期不做任何操作。

load指令:用上一个周期计算出的有效地址从存储器中读出相应的数据。

store指令:把指定的数据写入这个有效地址所指出的存储器单元。

  • 分支指令:分支“成功”,就把转移目标地址送入PC。分支指令执行完成。
  1. 写回周期(WB)

    • ALU运算指令和load指令在这个周期把结果数据写入通用寄存器组。

ALU运算指令:结果数据来自ALU。

load指令:结果数据来自存储器系统。

在这个实现方案中:

分支指令需要4个时钟周期(如果把分支指令的执行提前到ID周期,则只需要2个周期)。store指令需要4个周期。其他指令需要5个周期才能完成。

相关与流水线冲突

相关:两条指令之间存在某种依赖关系。如果两条指令相关,则它们就有可能不能在流水线中重叠执行或者只能部分重叠执行。

相关有3种类型

  • 数据相关(也称真数据相关)

  • 名相关

  • 控制相关

1.数据相关

对于两条指令i(在前,下同)和j(在后,下同),如果下述条件之一成立,则称指令j与指令i数据相关。

  • 指令j使用指令i产生的结果;

  • 指令j与指令k数据相关,而指令k又与指令i数据相关。

数据相关具有传递性。数据相关反映了数据的流动关系,即如何从其产生者流动到其消费者。

2.名相关

名:指令所访问的寄存器或存储器单元的名称。

如果两条指令使用相同的名,但是它们之间并没有数据流动,则称这两条指令存在名相关。

指令j与指令i之间的名相关有两种:

  • 反相关:如果指令j写的名与指令i读的名相同,则称指令i和j发生了反相关。

​ 指令j写的名=指令i读的名

  • 输出相关:如果指令j和指令i写相同的名,则称指令i和j发生了输出相关。指令j写的名=指令i写的名

换名技术:通过改变指令中操作数的名来消除名相关。

对于寄存器操作数进行换名称为寄存器换名。

既可以用编译器静态实现,也可以用硬件动态完成。

例如:考虑下述代码:

​ DIV.D F2,F6,F4

​ ADD.D F6,F0,F12

​ SUB.D F8,F6,F14

​ DIV.D和ADD.D存在反相关。

​ 进行寄存器换名(F6换成S)后,变成:

​ DIV.D F2,F6,F4

​ ADD.D S,F0,F12

​ SUB.D F8,S,F14

控制相关是指由分支指令引起的相关。

为了保证程序应有的执行顺序,必须严格按控制相关确定的顺序执行。

流水线冲突有3种类型:

  • 结构冲突:因硬件资源满足不了指令重叠执行的要求而发生的冲突。

  • 数据冲突:当指令在流水线中重叠执行时,因需要用到前面指令的执行结果而发生的冲突。

  • 控制冲突:流水线遇到分支指令和其他会改变PC值的指令所引起的冲突。

当一条指令被暂停时,在该暂停指令之后流出的所有指令都要被暂停,而在该暂停指令之前流出的指令则

继续进行(否则就永远无法消除冲突)。

1.结构冲突

在流水线处理机中,为了能够使各种组合的指令都能顺利地重叠执行,需要对功能部件进行流水或重复设置资源。

如果某种指令组合因为资源冲突而不能正常执行,则称该处理机有结构冲突。

常见的导致结构相关的原因:

  • 功能部件不是完全流水

  • 资源份数不够

结构冲突举例:访存冲突

​ 有些流水线处理机只有一个存储器,将数据和指令放在一起,访存指令会导致访存冲突。

  • 解决办法Ⅰ:插入暂停周期(“流水线气泡”或“气泡”)引入暂停后的时空图

  • 解决方法Ⅱ: 设置相互独立的指令存储器和数据存储器或设置相互独立的指令Cache和数据Cache。

有时流水线设计者允许结构冲突的存在

主要原因:减少硬件成本。如果把流水线中的所有功能单元完全流水化,或者

​ 重复设置足够份数,那么所花费的成本将相当高。

2.数据冲突

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

根据指令读访问和写访问的顺序,可以将数据冲突分为3种类型。考虑两条指令i和j,且i在j之前进入流水线,

可能发生的数据冲突有:

  • 写后读冲突(RAW):在i 写入之前,j 先去读。j 读出的内容是错误的。这是最常见的一种数据冲突,它对应于真数据相关。

  • 写后写冲突(WAW):在i 写入之前,j 先写。最后写入的结果是 i 的。错误!这种冲突对应于输出相关。

​ 写后写冲突仅发生在这样的流水线中:

  1. 流水线中不只一个段可以进行写操作。

  2. 当先前某条指令停顿时,允许其后续指令继续前进。

前面介绍的5段流水线不会发生写后写冲突。(只在WB段写寄存器)

  • 读后写冲突(WAR) :在 i 读之前,j 先写。i 读出的内容是错误的!由反相关引起。

这种冲突仅发生在这样的情况下:

  1. 有些指令的写结果操作提前了,而且有些指令的读操作滞后了。

  2. 指令被重新排序了。

读后写冲突在前述5段流水线中不会发生。(读操作(在ID段)在写结果操作(在WB段)之前)

通过定向技术减少数据冲突引起的停顿

(定向技术也称为旁路或短路)

关键思想:在某条指令产生计算结果之前,其他指令并不真正立即需要该计算结果,如果能够将该计

算结果从其产生的地方直接送到其他指令需要它的地方,那么就可以避免停顿。

20

当定向硬件检测到前面某条指令的结果寄存器就是当前指令的源寄存器时,控制逻辑会将前面那条指令的结果直接从其产生的地方定向到当前指令所需的位置。

结果数据不仅可以从某一功能部件的输出定向到其自身的输入,而且还可以定向到其他功能部件的输入。

需要停顿的数据冲突

并不是所有的数据冲突都可以用定向技术来解决增加流水线互锁硬件,插入“暂停”。作用:检测发现数据冲突,并使流水线停顿,直至冲突消失。

21

无法将LD指令的结果定向到DADD指令

依靠编译器解决数据冲突让编译器重新组织指令顺序来消除冲突,这种技术称为指令调度或流水线调度。

3.控制冲突

执行分支指令的结果有两种

  • 分支成功:PC值改变为分支转移的目标地址。在条件判定和转移地址计算都完成后,才改变PC值。

  • 不成功或者失败:PC的值保持正常递增,指向顺序的下一条指令。

处理分支指令最简单的方法:

  • “冻结”或者“排空”流水线 。优点:简单。

前述5段流水线中,改变PC值是在MEM段进行的。给流水线带来了3个时钟周期的延迟。

22

把由分支指令引起的延迟称为分支延迟。

分支指令在目标代码中出现的频度:每3~4条指令就有一条是分支指令。

​ 假设:分支指令出现的频度是30%,

​ 流水线理想CPI=1,

​ 那么:流水线的实际 CPI = 1.9。

可采取两种措施来减少分支延迟。

  • 在流水线中尽早判断出分支转移是否成功;

  • 尽早计算出分支目标地址。

Ø3种通过软件(编译器)来减少分支延迟的方法

​ 共同点:

n对分支的处理方法在程序的执行过程中始终是

​ 不变的,是静态的。

n要么总是预测分支成功,要么总是预测分支失败。

q预测分支失败

n允许分支指令后的指令继续在流水线中流动,就

​ 好象什么都没发生似的。

n若确定分支失败,将分支指令看作是一条普通指

​ 令,流水线正常流动。

n若确定分支成功,流水线就把在分支指令之后

取出的所有指令转化为空操作,并按分支目地

重新取指令执行。

要保证:分支结果出来之前不会改变处理机的状态,以

​ 便一旦猜错时,处理机能够回退到原先的状态。

流水线的处理过程

预测分支成功 :假设分支转移成功,并从分支目标地址处取指令执行。起作用的前题:先知道分支目标地址,后知道分支是否成功。

前述5段流水线中,这种方法没有任何好处。

延迟分支:

​ 主要思想:从逻辑上“延长”分支指令的执行时间。把延迟分支看成是由原来的分支指令和若干个延迟槽构成,不管分支是否成功,都要按顺序执行延迟槽中的指令。延迟分支以及指令的执行顺序