计算机体系结构【二】

三、流水线技术


1、流水线的基本概念

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

(1)时空图

时空图从时间和空间两个方面描述了流水线的工作过程。时空图中,横坐标代表时间,纵坐标代表流水线的各个段。

(2)流水线技术的特点

  • 流水线把一个处理过程分解为若干个子过程(段),每个子过程由一个专门的功能部件来实现

  • 流水线中各段的时间应尽可能相等,否则将引起流水线堵塞、断流。时间长的段将成为流水线的瓶颈。

  • 流水线每一个功能部件的后面都要有一个缓冲寄存器(锁存器),称为流水寄存器。作用:在相邻的两段之间传送数据,以保证提供后面要用到的数据,并把各段的处理工作相互隔离。

  • 流水技术适合于大量重复的时序过程,只有在输入端不断地提供任务,才能充分发挥流水线的效率。

  • 流水线需要有通过时间和排空时间

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

流水线级数不是越深越好。

(1)每一级流水线都由寄存器组成,更多的流水线级数意味着消耗更多的寄存器,产生更大的面积开销,功耗也会增大。

(2)每一级流水线需要握手,流水线的最后一级反压信号可能会一直串扰到最前一级造成严重的时序问题。

(3)流水线的取指阶段得知条件跳转的结果是到底跳还是不跳,因此只能进行预测,而到了流水线的末端才能通过实际运算得知该分支是真的该跳还是不该跳。如果发现真实的结果与预期的结果不一致,意味着预测失败,需要将所有的预取指令全部丢失。流水线越深,则意味着浪费和损失越严重;流水线越浅,则浪费和损失越少。

(3)流水线分类

1、按完成的功能分类

  • 单功能流水线:只能完成一种固定功能的流水线。
  • 多功能流水线:流水线的各段可以进行不同的连接,以实现不同的功能。多功能流水线可按照同一时间内各段之间的连接方式对多功能流水线做进一步的分类
    • 静态流水线:在同一时间内,多功能流水线中的各段只能按同一种功能的连接方式工作。
    • 动态流水线:在同一时间内,多功能流水线中的各段可以按照不同的方式连接,同时执行多种功能。

从时空图中可以看出,动态流水线的同一时间可以有不同功能。但是一定不能对某一段产生共用的冲突

2、按照流水的级别来进行分类

  • 部件级流水线(运算操作流水线):把处理机的算术逻辑运算部件分段,使得各种类型的运算操作能够按流水方式进行。

  • 处理机级流水线(指令流水线):把指令的解释执行过程按照流水方式处理。把一条指令的执行过程分解为若干个子过程,每个子过程在独立的功能部件中执行。

  • 处理机间流水线(宏流水线):它是由两个或者 两个以上的处理机串行连接起来,对同一数据流进行处理,每个处理机完成整个任务中的一部分。

3、按照流水线中是否有反馈回路来进行分类

  • 线性流水线:流水线的各段串行连接,没有反馈回路。数据通过流水线中的各段时,每一个段最多只流过一次。

  • 非线性流水线:流水线中除了有串行的连接外,还有反馈回路。

非线性流水线的调度问题十分重要。它需要确定什么时候向流水线引进新的任务,才能使该任务不会与先前进入流水线的任务发生冲突——争用流水段。方法有很多,可自行查阅了解

4、根据任务流入和流出的顺序是否相同来进行分类

  • 顺序流水线:流水线输出端任务流出的顺序与输入端任务流入的顺序完全相同。每一个任务在流水线的各段中是一个跟着一个顺序流动的。
  • 乱序流水线:流水线输出端任务流出的顺序与输入端任务流入的顺序可以不同,允许后进入流水线的任务先完成(从输出端流出)。也称为无序流水线、错序流水线、异步流水线

乱序流水线:例如第一个任务中途暂停,第二个任务能够继续执行,最终结果是第二个任务先出去。

5、按照处理的数据分类

把指令执行部件中采用了流水线的处理机称为流水线处理机。

  • 标量处理机:处理机不具有向量数据表示和向量指令,仅对标量数据进行流水处理。

  • 向量流水处理机:具有向量数据表示和向量指令的处理机。是向量数据表示和流水技术的结合

2、流水线的性能指标

(1)吞吐率

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

1、各段时间均相等的流水线:

  • 实际吞吐率:TP=n/(k+n-1)△t
    • 第一个任务使用k△t时间,后面n-1个任务都是每一个△t出一个结果。
  • 最大吞吐率:TPmax=1/△t
    • 当n->∞时
  • 流水线的实际吞吐率小于最大吞吐率,它除了与每个段的时间有关外,还与流水线的段数k以及输入到流水线中的任务数n等有关。

2、各段时间不完全相等的流水线:

  • 各段时间不等的流水线的实际吞吐率:
    • 第一个任务使用的时间+剩下n-1个任务。每隔一个max(△t1、△t2、△t3…)就会得出一个结果
  • 流水线的最大吞吐率为:
    • 同样当n->∞时

3、解决流水线瓶颈问题的常用方法:

  • ①细分瓶颈段
    • 例如:把瓶颈段占3△t的S3细分为3个占1△t子流水线段:S3a,S3b,S3c。TPmax由1/3△t变为1/△t
    • 缺点:有时候实在不好分
  • ②重复设置瓶颈段
    • 同样的TPmax由1/3△t变为1/△t。
    • 缺点:控制逻辑比较复杂,所需的硬件增加了
    • 重复设置瓶颈段后的时空图:

(2)加速比

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

1、流水线各段时间相等

  • 加速比S=n*k/(k+n-1)
    • 原来不使用流水线:Ts= nk△t
    • 使用流水线:Tk = (k+n-1)Δt
    • S=Ts/Tk
  • 最大加速比:当n>>k时,S ≈ k

2、流水线的各段时间不完全相等时

(3)效率

效率:流水线中的设备实际使用时间与整个运行时间的比值,即流水线设备的利用率。

从时空图上看,效率就是n个任务占用的时空面积和k个段总的时空面积之比。

  • 当n>>k时n最高效率为1

  • 当流水线各段时间相等时,流水线的效率与吞吐率成正比。

    • TP=n/(k+n-1)△t
    • E=n/(k+n-1)
  • 流水线的效率是流水线的实际加速比S与它的最大加速比k的比值

    • S=n*k/(k+n-1)
    • E=n/(k+n-1)
    • 最大加速比:当n>>k时,S ≈ k

(4)流水线的性能分析举例

总结:

  • E=TP*一个程序的时间/k=S/k

(5)流水线设计中的若干问题

  • 1.瓶颈问题

    • 在设计流水线时,要尽可能使各段时间相等。前面已经举过例子
  • 2.流水线的额外开销

    • 流水寄存器延迟。例如3△t的过程分成3个△t,每个过程中间需要加一个流水寄存器保存中间值。
    • 时钟偏移开销。虽然电流很快,但是还是需要时间的。
  • 3.流水寄存器需要建立时间和传输延迟

    • 时钟信号来临和执行是需要时间的。上面分成3个△t实际上还需要两个流水寄存器接受时钟时刻的作用等待时间T。
  • 4.时钟偏移开销

    • 流水线中,时钟到达各流水寄存器的最大差值时间。(时钟到达各流水寄存器的时间不是完全相同)因为电路到达每个寄存器的长度是不同的,即路程不同所以耗费时间就不同。
  • 几个问题:

    • 流水线并不能减少(而且一般是增加)单条指令的执行时间,但却能提高吞吐率。
    • 增加流水线的深度(段数)可以提高流水线的性能。
    • 流水线的深度受限于流水线的额外开销。
    • 当时钟周期小到与额外开销相同时,流水已没意义。因为这时在每一个时钟周期中已没有时间来
    • 做有用的工作。

3、相关与流水线冲突

(1) 一个经典的5段流水线

  • 取指令周期(IF)
    • IR ← Mem[PC] 。
    • PC值加4。(假设每条指令占4个字节)
  • 指令译码/读寄存器周期(ID)
    • 译码。
    • 用IR中的寄存器编号去访问通用寄存器组,读出所需的操作数。
  • 执行/有效地址计算周期(EX):不同指令所进行的操作不同
    • 存储器访问指令:ALU把所指定的寄存器的内容与偏移量相加,形成用于访存的有效地址。
    • 寄存器-寄存器ALU指令:ALU按照操作码指定的操作对从通用寄存器组中读取的数据进行运算。
    • 寄存器-立即数ALU指令:ALU按照操作码指定的操作对从通用寄存器组中读取的第一操作数和立即数进行运算。
    • 分支指令:ALU把偏移量与PC值相加,形成转移目标的地址。同时,对在前一个周期读出的操作数进行判断,确定分支是否成功。
  • 存储器访问/分支完成周期(MEM)
    • 该周期处理的指令只有load、store和分支指令。 其他类型的指令在此周期不做任何操作。
    • load指令:用上一个周期计算出的有效地址从存储器中读出相应的数据。
    • store指令:把指定的数据写入这个有效地址所指出的存储器单元。
    • 分支指令:分支“成功”,就把转移目标地址送入PC。
  • 写回周期(WB)
    • ALU运算指令和load指令在这个周期把结果数据写入通用寄存器组。

在这个实现方案中:分支指令需要4个时钟周期(如果把分支指令的执行提前到ID周期,则只需要2个周期)。store指令需要4个周期。其他指令需要5个周期才能完成。(ALU只是MEM不做事情依旧需要执行WB所以等5个周期)

它的执行方式如下:

由图中我们可以看出具有很多冲突,例如不同指令的阶段同时访存等。

所以采用流水线方式实现时,应解决以下几个问题:

  • ①要保证不会在同一时钟周期要求同一个功能段做 两件不同的工作。
    • 例如,不能要求ALU同时做有效地址计算和算术运算。
  • ②避免IF段的访存(取指令)与MEM段的访存(读/写数据)发生冲突。
    • 可以采用分离的指令存储器和数据存储器;
    • 一般采用分离的指令Cache和数据Cache。
  • ③ID段和WB段都要访问同一寄存器文件。
    • 把写操作安排在时钟周期的前半拍完成,把读操作安排在后半拍完成。
  • ④考虑PC的问题
    • PC值的加4操作,并保留新的PC值。这种操作必须在IF段完成,以便为取下一条指令做好准备。(需设置一个专门的加法器)
    • 但分支指令也可能改变PC的值,而且是在MEM段进行,这会导致冲突。

(2)相关与流水线冲突

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

  • ①数据相关(也称真数据相关):某指令的运行需要前一个指令的结果,且具有传递性
    • 该语句就不能连续执行流水指令,产生了数据相关
  • ②名相关:同时使用一个寄存器,它分为反相关:一个读一个写,输出相关:两个都写;名相关的两条指令之间并没有数据的传送。
    • 换名技术:通过改变指令中操作数的名(寄存器换名)来消除名相关。既可以用编译器静态实现,也可以用硬件动态完成。
  • ③控制相关:由分支指令引起的相关为了保证程序应有的执行顺序,必须严格按控制相关确定的顺序执行。
    • 与一条分支指令控制相关的指令不能被移到该分支之前,否则这些指令就不受该分支控制了。
    • 如果一条指令与某分支指令不存在控制相关,就不能把该指令移到该分支之后。
      • 例如两个if语句之间有一个其他语句,这个语句就不能移动

流水线冲突指对于具体的流水线来说,由于相关的存在,使得指令流中的下一条指令不能在指定的时钟周期执行

我们约定:当一条指令被暂停时,在该暂停指令之后流出的所有指令都要被暂停,而在该暂停指令之前流出的指令则继续进行(否则就永远无法消除冲突)。

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

    • 例如同时执行浮点加法,硬件只有一个设施
    • 结构冲突的解决办法:
      • 插入暂停周期
      • 设置相互独立的指令存储器和数据存储器或设置相互独立的指令Cache和数据Cache。
    • 注意:有时流水线设计者允许结构冲突的存在因为需要减少硬件成本
  • ②数据冲突:当指令在流水线中重叠执行时,因需要用到前面指令的执行结果而发生的冲突。

    • 例如:后面指令用前面的结果
    • 根据指令读访问和写访问的顺序,可以将数据冲突分为3种类型。
      • 写后读冲突(RAW)(数据相关): 在 i 写入之前,j 先去读。 j 读出的内容是错误的。这是最常见的一种数据冲突,它对应于真数据相关。
      • 写后写冲突(WAW)(输出相关):在 i 写入之前,j 先写。最后写入的结果是 i 的。错误!这种冲突对应于输出相关。写后写冲突仅发生在这样的流水线中:流水线中不只一个段可以进行写操作、当先前某条指令停顿时,允许其后续指令继续前进。*前面介绍的5段流水线不会发生写后写冲突。(因为只在WB段写寄存器) *
      • 读后写冲突(WAR)(反相关) :在 i 读之前,j 先写。i 读出的内容是错误的!这种冲突仅发生在这样的情况下:有些指令的写结果操作提前了,而且有些指令的读操作滞后了、令被重新排序了。读后写冲突在前述5段流水线中不会发生。(读操作(在ID段)在写结果操作(在WB段)之前)
    • 数据冲突的解决办法:
      • 通过定向技术减少数据冲突引起的停顿. 因为某些数据在存入前其实已经产生了,我们可以之前在临时存储中直接导出。但是要注意:不能隔节拍导入,因为是流水线不断变化的(T3节拍产生的结果不可能保存到第5节拍不要被图迷惑了),而且注意不能是后节拍导入前节拍,这是不可能的。实际上定向是同时间不同空间的传递。
      • 停顿等待并不是所有的数据冲突都可以用定向技术来解决。
      • 依靠编译器解决数据冲突。编译器在编译成机器指令的时候进行相应的调换顺序使得不需要停顿
  • ③控制冲突:流水线遇到分支指令和其他会改变PC值的指令所引起的冲突。

    • 分支等改变PC值的冲突
    • 控制冲突的解决办法
      • 冻结”或者“排空”流水线 。
      • 减少分支延迟。
        • 在流水线中尽早判断出分支转移是否成功;
        • 尽早计算出分支目标地址。
      • 通过软件(编译器)来减少分支延迟的方法
        • 预测分支失败,若真的分支失败则就分支指令看作是一条普通指 令允许分支指令后的指令继续在流水线中流动。相当于什么都没发生
        • 预测分支失败,若实际分支成功,流水线就把在分支指令之后取出的所有指令转化为空操作,并按分支目地重新取指令执行。
        • 若能够先知道分支目标地址,后知道分支是否成功。则假设分支转移成功时,直接分支目标地址处取指令执行。然而前述5段流水线中,这种方法没有任何好处。
        • 要保证:分支结果出来之前不会改变处理机的状态,以便一旦猜错时,处理机能够回退到原先的状态。
      • 延迟分支:在延迟槽中放入有用的指令。
        • 从前调度
        • 从目标处调度
        • 从失败处调度
        • 要求编译器实现时尽量判断哪些指令确实可以调度,不会改变原程序结果
        • 进一步改进:分支取消机制当分支的实际执行方向和事先所预测的一样时,
          执行分支延迟槽中的指令,否则就将分支延迟槽中的指令转化成一个空操作(这里我们假设了结果会在ID段出现即使用了尽早计算出分支目标地址。)。

4、MIPS流水线实现

参考机组的MIPSCPU设计课程设计,对照课本理解。

5、向量处理机

(1)介绍

在流水线处理机中,设置向量数据表示和相应的向量指令,称为向量处理机。

不具有向量数据表示和相应的向量指令的流水线处理机,称为标量处理机。

向量实际上就可以看成个数组,对其计算计算对每其一个内容进行相应计算。

  • 横向计算就是每一位上都需要对一个计算过程全部计算完毕再进行下一位直至结束
  • 纵向计算就是对每一种计算方式,从前往后全部计算完毕,在进行下一个计算方式从前往后,直到结束。
    • 由于向量过长,每一次计算方式计算完毕后想要寄存保持就需要很大的寄存器,这样成本太高,只适合存储器-存储器。
  • 纵横计算,就是将向量分组,例如512位向量分成8*64段,若不是恰好的向量则最后剩余的也为一段。对每一段中的内容进行纵向计算,段与段之间横向计算。这样64位就很好储存了,可用寄存器=寄存器结构。

注:向量处理中的每一位,不是1bit,通常是1字节,数据处理加减乘除也是和我们平时相同。

(2)提高向量处理机性能的方法

1、设置多个功能部件

2、链接技术

链接特性的实质:把流水线定向的思想引入到向量执行过程的结果

四、指令级并行

1、tomsulo算法

注意load出来的result填写是使用Mem[regs[]+]类型而不是Regs[Fxx]

2、循环展开

-----------------------本文结束 感谢阅读-----------------------
坚持原创技术分享,您的支持将鼓励我继续创作!恰饭^.^~