流水线基本概念及其性能指标

基本概念

  和工业生产中的流水线类似,在计算机系统中,把一个重复的过程,分解成若干个子过程,每个子过程由专门的功能部件来实现。将多个处理过程在时间上错开,依次通过各功能段,每个子过程都可以与其他子过程同时并行进行。这就是流水线技术。
  流水线中的每个字过程及其功能部件成为流水线的段或级,段与段之间互相连接形成流水线。流水线的段数成为流水线的深度。
  把流水线技术应用于运算的执行过程,形成运算操作流水线;吧流水线技术应用于指令的解释执行过程,形成指令流水线。流水线的工作过程常常采用时空图的方法描述。

流水线特点

  (1) 流水线把一个处理工程分解为若干子过程(段),每个子过程都由一个专门的功能部件实现。
  (2) 流水线中各段的时间应该尽可能相等。否则,将引起流水线阻塞、断流,因为时间长的段将成为流水线的瓶颈,此时流水线中的其他功能部件就不能充分发挥作用。
  (3) 流水线每个功能部件的后面都有一个缓冲寄存器(锁存器),称为流水寄存器。其作用是在相邻两段之间相互传送数据,保证提供后面要用到的数据,并把各段的处理工作互相隔离。
  (4) 流水线技术适合于大量重复的时序过程,只有在输入端不断地输入任务,才能充分发挥流水线的效率。
  (5) 流水线需要通过实践和排空时间。通过时间是第一个任务从进入到流出的时间段,排空时间是最后一个任务的时间段。在这两个时间段内,流水线都不是满载。效率未得到充分发挥。

流水线分类

从完成功能角度

  (1)单功能流水线:只能完成一种固定功能的流水线。
  (2)多功能流水线:可以以各段进行不同的连接,而实现不同的功能的流水线。但要保证不能发成冲突。

按照同一时间段内各段之间的连接方式

  (1)静态流水线:在同一时间段内,多功能流水线的各段只能按照同一功能的连接工作。当按另一种连接实现其他功能时,必须等按照原来连接方式处理的所有任务都流出流水线之后,才能改变连接。
  (2)动态流水线:在同一时间段内,多功能流水线的各段可以按照不同连接,同时执行多种功能。

从流水点级别角度

  (1)部件级流水线(运算操作流水线):它把处理机的算术处理运算部件分段,使得各种类型的运算操作能够按照流水方式进行。
  (2)处理机级流水线(指令流水线):它是把指令的解释过程分成不同过程,按照流水方式处理。
  (3)处理机间流水线(宏流水线):它是由两个或两个以上处理机串行连接起来,对同一数据流进行处理,每个处理机完成整个任务的一部分。前一个处理机的输出结果存入存储器中,作为后一个处理机的输入。这一般属于异构型多处理机系统,它对提高各处理机的效率有很大的作用。

从反馈角度

  (1)线性流水线:流水线的各段串行连接,没有反馈回路。
  (2)非线性流水线:流水线中除了有串行的连接外,还有反馈回路。常用于递归或组成多功能流水线。
  在非线性流水线中,一个重要的问题是确定什么时候向流水线引进新任务,才能使该任务不会与先前进入流水线的任务发生冲突——争用流水段。这就是非线性流水线的调度问题。

从任务流入流出角度

  (1)顺序流水线:流水线输出端任务流出的顺序与输入端任务流入的顺序完全相同。
  (2)乱序流水线,又称无序流水线、错序流水线、异步流水线。
  通常把指令执行部件中采用流水线的处理机成为流水线处理机。如果处理机不具有向量数据表示和向量指令,仅对标量数据进行流水处理,如IBM 360/91、Amdahl 470V/6,称为标量处理机。具有向量表示和向量指令的处理机,称为向量流水处理机。向量处理机是向量数据表示和流水技术的结合。

流水线性能指标

  主要有吞吐率、加速比和效率三个指标。

吞吐率

  吞吐率TP(ThroughPut)是指在单位时间内流水线所完成的任务数量或者输出结果的数量。

$ TP=\frac{n}{T_k} $
  其中,n为任务数,$ {T_k} $ 是处理完成n个任务所用的时间。
时空图
  由图知:
$$ T_k=k \Delta t+ (n-1)\Delta t= (k+n-1) \Delta t $$
  得出:
$$ TP= \frac{n}{(k+n-1)\Delta t} $$
  这种情况下最大吞吐率为:
$$ TP_{max}= \lim {(n \rightarrow \infty)}\frac{n}{(k+n-1)\Delta t} = \frac{1}{\Delta t}$$
  最大吞吐率与实际吞吐率的关系为:
$$ TP= \frac{n}{k+n-1} TP_{max} $$

解决流水线瓶颈问题常用方法

  1) 细分瓶颈段。
  2) 重复设置瓶颈段。

加速比

  完成同一批任务,不使用流水线所用的时间和使用流水线所用的时间之比称为流水线的加速比。
  设不使用流水线所用的时间$ T_s $, 使用流水线所用的时间为$ T_k $,则流水线的加速比为:

$$ S= \frac {T_s}{T_k} $$
  理想情况下,一条k段流水线完成n个连续任务所需要的时间为 $ T_k=(k+n-1) \Delta t $,不使用流水线技术,而采用顺序执行方式,完成n个任务所需要的时间为:$ T_s=nk \Delta t $。带入上述公式得到加速比:
$$ S=\frac{nk }{(n+k-1) } $$
  这种情况下流水线的最大技术比为:
$$ S_{max}=\lim {(n \rightarrow \infty)} \frac{nk}{n+k-1}=k $$

效率

  流水线的效率是指流水线中的设备实际使用时间和整个运行时间的比值,即流水线设备的利用率。
  理想状态下,如上面时空图所示,各段的效率是相同的。

$$ e_1=e_2=····=\frac{n \Delta t}{T_k}=\frac{n}{n+k-1} $$

  整条流水线的效率为:

$$ E=\frac{e_1+e_2+···+e_k}{k}=\frac{ke_1}{k}=\frac{kn \Delta t}{kT_k} $$

  或:

$$ E=\frac{n}{k+n-1} $$

  最高效率为:

$$ E_{max}=\lim{(n \rightarrow \infty)} \frac{n}{k+n-1}=1 $$

  显然当$ n\rightarrow \infty $时,流水线的效率接近于1。这时流水线各段都趋于忙碌状态。上述公式也可写成:

$$ E=TP \Delta t $$

$$ E=\frac{S}{k} $$

  即流水线的效率是流水线实际加速比S与其段数k的比值。只有当$ E=1 S=k $,实际极速比达到最大。
  引入时空图中,流水线的效率即为任务占用的时空面积和k个段总的时空面积之比。可以表示为:

$$ E=\frac{n个任务实际占用的时空区}{k个段总的时空区} $$

  画出时空图,根据上述公式计算效率,对于线性流水线、非线性流水线、多功能流水线、任务不连续等情况均使用。
  当各段时间不相等时,连续执行n个任务时,效率为:

$$ E=\frac{n \sum\limits_{i=1}^k \Delta t_i}{k[\sum\limits_{i=1}^k \Delta t_i+ (n-1)max(\Delta t_1,\Delta t_2,···,\Delta t_k)]} $$

流水线设计的若干问题

瓶颈问题

流水线的额外开销

  流水线的额外开销是指流水寄存器延迟和时钟偏移开销。流水寄存器需要建立时间和传输延迟。时钟偏移开销是指流水线中时钟到达各流水寄存器的最大差值时间。

冲突问题