计算机组成与系统结构课件：流水线技术

流水线技术7.1流水线处理的概念7.2浮点运算流水线7.3指令流水线7.4流水线性能测量7.5指令流水线的性能提高7.6多发射处理器7.7指令级并行概念

7.1流水线处理的概念

7.1.1流水线的处理方式流水线在我们日常生活和工厂生产线中经常采用。例如,工厂的自动化生产线均采用流水作业的方式进行工件的加工处理,原材料每经过一道工序完成一步加工处理,变成半成品,当半成品经过所有工序加工处理后就成为可用的成品。

7.1.2CPU中流水线的一般结构及运作

在CPU中,流水线的一般结构如图7.1所示,这是一个典型的m级流水线,它由m个段(Stage或Segment,也称为级)S1,S2,…,Sm组成。段Si包含一个多字输入的寄存器或缓冲器Ri和一个实现特定操作的功能部件Ci。Ri缓存流水线中前一段Ci-1产生的结果,并作为Ci的输入,同时也起到各段隔离的作用,防止相邻段间相互干扰,以确保各段功能部件可以并行独立地工作。每一段对通过它的信息同时完成各自独立的操作处理,最终的处理结果仅在一组信息通过了整个流水线各段之后才能获得。图7.1CPU中流水线的一般结构

假设对一组信息的处理需要经过m个段,每段的锁存与处理时间为τ,那么τ就是流水线的时钟周期TLCLK。在非流水线处理中,每经过mτ时间才可以获得对一组信息的处理结果;而在流水线处理中,尽管一组信息的处理时间仍为mτ时间,但在不增加处理设备的情况下,使流水线各段操作时间重叠,这样每经过τ时间就可以获得对一组信息的处理结果,所以流水线可以提高单位时间内信息的处理量。这就是并行处理中的时间重叠技术。采用该技术的目的是希望单条流水线的吞吐量达到每个时钟周期产生一个结果的目标。

从上述分析可以得出以下结论:

(1)流水过程由多个相互关联的子过程组成,每个子过程由专用的功能部件实现,每个子过程称为流水线的级或段,级数称为流水线的深度,各段间需要缓冲器隔离。

(2)流水线需要有通过时间(第一个结果开始流出流水线所需的时间,也称装入时间或填充时间),在此之后流水过程才进入稳定工作状态,每一个流水线时钟周期(节拍)流出一个结果。流水线上的时钟可以由系统时钟生成,也可以使用独立时钟,频率一般取为系统主频的1/n(n≥1)。

(3)流水线不能缩短单个任务的响应时间,但可以提高吞吐率。

(4)流水线速度受限于最慢流水线段的运行速度,所以各个功能段所需时间应尽量相等(典型为一个流水线时钟周期),否则运行时间长的功能段将成为流水线的瓶颈,造成流水线的停顿(也称断流或阻塞)。

(5)流水线技术适合于大量重复的处理过程,只有流水线的输入能连续地提供任务,流水线的效率才能得到充分的发挥。

(6)流水线中多个任务是并行处理的。

7.1.3流水线的类型

1.按位于计算机系统的层次划分

按流水线位于计算机系统的层次,流水线可以分为系统级流水线、处理器级流水线、部件级流水线。系统级流水线也称为宏流水线,是指在多(计算)机系统中由多个处理机串行构成的流水线,如图7.2所示。图7.2系统级流水线

处理器级流水线是指在处理器内部由多个部件构成的流水线,其典型就是指令流水线。图7.3(a)是Intel8086中的指令流水线,这是一个初级的指令流水线,它仅由两段构成。取指部件从内存中获取指令并将其存入指令缓冲队列中,执行部件从指令缓冲队列中取出指令并加以译码、执行。由于在取指部件与执行部件之间有一个6字节的指令缓冲队列,使得取指部件可以在执行部件工作期间从内存中预取一至多条指令存入指令缓冲队列中,这样执行部件只需要从速度较快的指令缓冲队列获取指令执行即可。也就是说,当执行部件在执行第i条指令时,取指部件正在取得第i+1条指令甚至第i+2条指令,两者并行工作的效果如图7.3(b)所示。n条指令的运行时间仅由执行部件对n条指令的执行时间确定,而n-1条指令的获取时间被隐含在执行时间内。图7.3处理器级流水线

部件级流水线是指在处理器中某部件内部由多个子部件构成的流水线。例如,运算器中的浮点运算流水线,控制器中的微程序控制单元流水线,它们也被称为操作流水线。图7.4是一个两段流水线的微程序控制单元。取微指令段S1由微程序计数器μPC和控制存储器CM组成,μPC提供微指令地址,CM存储微指令。μPC有双重作用,它既是CM地址的提供源,又是S1段的缓冲寄存器图7.4部件级流水线的微程序控制单元

2.按功能强弱划分

按流水线功能的强弱,流水线可以分为单功能流水线和多功能流水线。

单功能流水线是指只能实现一种功能的流水线。美国Cray公司是世界超级计算机(Supercomputer)的代表之一,1976年第一个Cray-1向量计算机被安装在洛斯阿拉莫斯国家实验室(LosAlamosNationalLaboratory),它具有每秒160百万次浮点运算速度和8兆字节主存储器。Cray-1计算机有12条单功能运算流水线,分别完成地址加、地址乘、标量加、标量移位、标量逻辑运算、标量计数、向量加、向量移位、向量逻辑运算、浮点加、浮点乘、浮点迭代求倒数。将多个单功能流水线加以组合就可以实现多功能的流水操作。

多功能流水线是指在同一流水线上通过各段之间不同的连接方式以实现多种运算或处理的功能。TIASC(TexasInstrumentsAdvancedScientificComputer)在20世纪60年代末70年代初被设计与构建,并为后来的向量处理机设定了标准。ASC计算机的运算器流水线就是一种多功能静态流水线,它有8个可并行工作的独立功能段,如图7.5(a)所示。当要进行浮点加、减运算时,各功能段可连接成图7.5(b)所示的形式;当要进行定点乘法运算时,各功能段可连接成图7.5(c)所示的形式。图7.5TIASC计算机的运算器流水线

3.按是否有回路划分

按照流水线是否有反馈回路,流水线可以分为线性流水线和非线性流水线。线性流水线是指流水线的各段串行连接,没有反馈回路。非线性流水线是指流水线中除有串行连接的通路外,还有反馈回路。由于有反馈,因此数据会在流水线的某些段重复流过,使流水线中有可能出现冲突。解决冲突的方法就是进行流水线调度。确定什么时候向流水线引进新的输入,使新输入的数据和先前操作的反馈数据在流水线中不产生冲突,即是流水线调度问题。

4.按任务顺序划分

按照输出端任务流出顺序与输入端任务流入顺序是否相同,流水线可以分为顺序流动流水线(入出顺序相同)和异步流动流水线(入出顺序不同)。异步流动流水线也称为无序流水线、错序流水线或乱序流水线。

5.按处理数量划分

按一次处理对象的数量可将流水线分为标量流水线、超标量流水线、向量流水线和超长指令字流水线。标量流水线由一条流水线构成,一次流水过程仅处理单一的指令或标量数据,如IBM360/91、Amdahl470V/6等。

7.2浮点运算流水线

对数据的运算处理是计算机的重要功能,浮点运算是其中涉及最广的一类运算。由第3章可知,浮点运算是一种较为复杂、耗时的运算,用非流水线结构运算器完成一次浮点运算需要花费较长的时间,所以,每秒钟完成浮点运算的次数已成为衡量计算机系统运行速度的重要指标。如何提高浮点运算的速度成为计算机系统设计中要解决的关键问题之一,而流水线技术提供了解决问题的有效途径。

7.2.1浮点加减运算流水线

1.浮点加减运算方法及运算单元实现

由第3章可知,浮点加减运算需要如下4个操作步骤:

4)舍入处理

舍入处理可以采用截断法、末位恒置“1”法、0舍1入法等。当选择截断法时,舍弃部分自然丢弃,所以不需要任何舍入处理操作或电路。

图7.6是在IBMSystem360/91计算机系统中按照上述算法设计的浮点加减法单元,它可以完成32位和64位的浮点加减运算。图7.6IBMSystem360/91的浮点加/减法单元

2.设计运算流水线的一般方法

当为某运算功能设计流水线实现逻辑时,要为该功能实现寻找一个适当的、可分解为多步骤的、连续运行的算法,该算法的每一步骤应是时间均衡的、可以由硬件电路实现的。将实现算法每一步骤的硬件电路作为流水线的一段,并按照步骤顺序将各段连接起来,就可以构成实现指定功能的流水线电路。为了防止流水线各段的相互干扰,通常在流水线各段之间放置快速缓冲寄存器来分离各段,并利用缓冲寄存器逐段传送处理数据(部分或全部结果)。所有缓冲寄存器受同一时钟控制,以保证流水线中数据在各段同步向下级传送。

3.浮点加减运算单元的流水线实现

浮点加减运算完全符合流水线的设计要求。图7.7所示的浮点加减法电路正是图7.6的流水线版本,该流水线由4段组成。对比图7.7与图7.6可见,通过在流水线运算单元中增加E4~E7和M4~M7寄存器,使得流水线运算单元的每一段输入端都有阶码和尾数的暂存寄存器,用来将上一段产生的结果加以缓存,并提供给本段使用。流水线结构对非流水线结构的主要改变就是加入了隔离4个段的缓冲寄存器,使得各段可以同时独立地进行计算。图7.7所示电路的运算速度理论上是图7.6所示电路的4倍。图7.7浮点加减运算的流水线实现

7.2.2浮点乘除运算流水线

1.浮点乘除运算方法

浮点乘除运算无须对阶操作,相对于浮点数加减运算而言,它的操作步骤更加简洁。

4)舍入处理

舍入处理可以采用截断法、末位恒置“1”法、0舍1入法等。当选择截断法时,舍弃部分自然丢弃,所以不需要任何舍入处理操作或电路。

2.浮点乘除运算的流水线实现

按照流水线的设计要求,浮点数乘除运算同样可以用流水线实现。图7.8就是一个两段结构的浮点乘除运算的流水线实现。由于阶码运算与尾数运算互不干扰,可以同时进行,因此它们被放在流水线的同一段S1中处理,而S2段完成对尾数乘除结果的规格化处理。7.8浮点乘除运算的流水线实现

一种乘法器中经常采用的、特别适宜流水计算的技术称为进位保留加法(Carry-SaveAddition)计算。一个n位的进位保留加法器由n个独立的全加器组成,它的输入是3个相加的n位数,输出是n位和S与n位进位C。与其他加法器的不同在于,进位保留加法器内没有进位传递。进位保留加法器的输出S和C可以提供给另一个n位进位保留加法器,与另一个n位数W相加,如图7.9所示。注意图中进位的连接。通常,利用进位保留加法器的树状网络,可以将m个数相加,其结果为(S,C)形式,再将S和C用具有进位传递的常规加法器相加,即获得最终求和结果。图7.9两级的进位保留加法器

采用多级进位保留加法器实现乘法运算的电路如图7.10所示,该电路被称为Wallace树。加法器树的输入为部分积Mi,它由式(7.1)确定。由于需要产生2n位长度的乘积,因此Mi均为2n位长度。最终的乘积由一个快速的先行进位加法器将2n位的和S与2n位的进位C相加获得,该先行进位加法器(Carry-lookaheadAdder)具有正常的内部进位传递功能。图7.10进位保留(Wallace树)乘法器

进位保留乘法可以非常方便地用流水线实现,在图7.10所示电路的适当位置加入缓冲寄存器就可以得到流水线结构的进位保留乘法器(Carry-saveMultiplier)。图7.11是一个四段流水线的进位保留乘法器,第1段是乘法器的译码与门控电路,该电路的作用是生成所有的部分积Mi;第2、3段为进位保留加法逻辑;第4段是先行进位加法器。图7.114段流水线的进位保留乘法器

7.3指令流水线

7.3.1基本的指令流水线指令流水线是实现多条指令重叠执行的技术。正如图7.3(b)所示,如果将指令的处理简单地分解为两个步骤———取指令和执行指令,那么就可以设计一个两级的指令流水线,流水线的第1段为取指部件,第2段为执行部件,两段通过缓冲器连接且并行工作,如图7.3(a)所示。

在大多数情况下,取指令和执行指令的操作时间并不相同,如执行指令期间若有访存操作,则会使指令的执行时间比指令的获取时间要长。如果流水线采用同步方式控制各段间信息的同步推进,如图7.1所示,则流水线同步控制时钟的周期应选定为

例如,可以将指令处理分解为以下4步:

(1)指令获取(IF):从主存或Cache中获取指令并对指令进行译码。

(2)操作数加载(OL):从主存或Cache中获取操作数并将其放入寄存器中。

(3)执行指令(EX):利用ALU等执行部件,对寄存器中的操作数进行处理,结果存于寄存器中。

(4)写操作数(WO):将寄存器中的结果存入主存或Cache中。

按照这种分解,可以将CPU组织成一个4级指令流水线,如图7.12所示。S2段和S4段实现存储器的加载和存储操作;S2段、S3段和S4段共享CPU的内部寄存器,并将这些寄存器作为流水线各段间的缓冲寄存器;S3段中的ALU完成寄存器寄存器类型的数据传送和数据运算操作。图7.12由4级指令流水线组织的CPU结构

Amdahl470V/7是1978年设计的与IBMSystem/370系列主机架构相适应的经典计算机,它的内存由主存和Cache(指令和数据均存于其中)组成,CPU由12级流水线构成,见表7.1。为了支持470V/7的CISC架构,470V/7有许多寻址方式和指令类型,这使得它的指令流水线段需要进一步细分。S1、S2段与存储器控制器通信,存储器控制器负责所有对主存和Cache的访问操作,所以S1、S2段用于在流水线与Cache之间传送指令或操作数。所有的结果在S11段利用奇偶检验(大多数情况)进行错误检查,如果结果有错,则自动地重新执行出错的指令,这种错误恢复技术被称为指令重试(InstructionRetry)。

7.3.2指令流水线策略

指令流水线利用了指令之间潜在的并行性。为了追求更快的指令处理速度,指令流水线设计的策略是不断向深度和广度发展,使得深度流水线结构和多条流水线结构在指令流水线中越来越普遍。

1.深度流水线结构

深度流水线结构是指将指令的执行过程进一步细化,使流水线的级(段)数变多,而每一级的工作更少、更合理。这样做有两个好处:

一是指令流水线级数变多,各段处理更趋合理,可使流水线重叠执行更多的指令,并行执行能力更强;

二是每一级的处理时间更短,可以进一步提高处理器的工作频率。

也就是说,增加指令流水线深度可以使处理器执行指令的速度更快,效率更高。

图7.13为IntelPentiumⅡ的指令流水线结构示意图。PentiumⅡ架构具有RISC内核、CISC外壳的特点,内部RISC微操作利用至少11段流水线实现(某些微操作需要多个执行段)。图7.13IntelPentiumⅡ的指令流水线结构

ROB是一个循环缓冲器,能够保存多达40个微操作,并且也包含40个硬件寄存器。每一个缓冲器条目由以下几个域组成:

(1)状态———指示该微操作是否被安排执行,是否已为了执行而发送出,是否已完成执行,是否准备退出。

(2)存储器地址———产生微操作的Pentium指令的地址。

(3)微操作———实际的操作。

(4)重命名寄存器———如果微操作与16个程序员可见寄存器关联,则该条目更改寄存器名以便与40个硬件寄存器之一进行映射。

2.多条流水线结构

虽然增加指令流水线的深度能够提高指令的并行处理能力,但是采用这种方法,指令的并行处理能力是有限度的。首先,指令执行过程的细化是有限度的,它最多可以分解为有限的微操作,并且这些微操作必须能够在可以独立工作的硬件部件上完成;其次,随着流水线深度的增加,流水线段之间的缓冲器增多,延迟加大,使流水线的性能提高受到阻碍。如果在微处理器中增加指令流水线的条数,那么指令执行的并行度在原有基础上又可以进一步提高。

PowerPC是第一个RISC系统IBM801的直系后裔,是市场上最强、设计最好的基于RISC的系统之一。PowerPC601微处理器的第一个芯片在1993年发布,之后得到不断的改进。它内部有三个功能单元,每一个功能单元都是一个独立的流水线,如图7.14所示。图7.14PowerPC601的指令流水线

7.3.3指令流水线设计方法———RISC-V基本指令流水线设计示例

流水线设计是建立在非流水的功能实现硬件电路的基础上的,指令流水线设计一般采用以下步骤:

(1)设计能够使指令系统中所有指令有效获取、执行的硬件逻辑电路。

(2)对指令获取、执行过程在该硬件逻辑电路上进行分段。

(3)在每段之间加入缓冲器(称为流水线寄存器)。

(4)设计流水线控制器。

1.设计指令获取、执行的硬件逻辑电路

首先要设计好指令系统,然后设计能够使指令系统中所有指令有效获取、执行的硬件逻辑电路。为了简化硬件逻辑,假设实现的是RISC-V指令系统中的RV64I子集(仅包括访存指令ld和sd,算术逻辑指令add、sub、and和or,条件分支指令beq),能够使该子集中所有指令有效获取、执行的硬件逻辑已设计完成,见6.1.2节中图6.2。

2.对硬件逻辑分段

对硬件逻辑分段是指将指令获取、执行过程拆分成若干子过程,然后对实现该过程的硬件逻辑电路进行对应分段。分段时尽量使每段处理功能相对独立,处理时间基本均衡。

结合图6.2的硬件逻辑,可将指令获取、执行所经历的数据通路从左至右分为指令获取(IF)、指令译码/读寄存器(ID)、执行/地址计算(EX)、存储器访问(MEM)、写回(WB)五个硬件逻辑段,如图7.15所示。图7.15指令获取与执行的数据通路分段结果

3.段间加入流水线寄存器

流水线设计的关键是在划分的每段之间加入流水线寄存器,使得各段被隔离,段间的各种信息只通过流水线寄存器传递。这样,流水线寄存器与某段功能部件组合就构成了流水线的一段,若干流水线段串联,就得到了指令流水线,其每段可并行运行。

在图7.15中加入流水线寄存器,得到支持RV64I子集(7条指令)的RISC-V指令流水线,如图7.16所示。图7.16支持RV64I子集的RISC-V指令流水线

图7.16仅提供的是指令获取与执行硬件逻辑中的数据通路流水线,其中所有功能部件的有效工作都必须受到控制信号的控制。将图6.2中的控制逻辑加入图7.16中,得到带控制信号的RISC-V指令流水线,如图7.17所示,其中主控制逻辑位于ID段,ALU控制逻辑位于EX段。

为了保证各段完全独立,由ID段中主控制逻辑产生的控制信号不能像图6.2非流水结构那样直接加载到各段相应功能部件上,而是必须通过各段流水线寄存器加载至本段功能部件上(见表7.2),所以图7.17中的ID/EX、EX/MEM、MEM/WB流水线寄存器做了保存控制信号的相应扩展。图7.17带控制信号的RISC-V指令流水线

另外,写寄存器操作发生在WB段,所以需要修改图7.16中写寄存器地址的加载方式为图7.17所示,即写寄存器地址(5位)需要经过ID/EX、EX/MEM流水线寄存器传递到MEM/WB流水线寄存器中,提供给WB段使用;在EX段的ALU控制逻辑需要对指令中附加的操作码Funct字段进行译码,所以Funct字段相关位(4位)需要传递到ID/EX流水线寄存器中。这样,ID/EX、EX/MEM、MEM/WB流水线寄存器位宽需要进一步扩展。

最终,流水线寄存器成为流水线上相邻两段传递信息的唯一通道。

4.设计流水线控制器

流水线控制器最简单的实现方案是同步时钟控制。

首先,设计流水线时钟,并按式(7.2)设置流水线时钟周期TLCLK。可以单独设计流水线时钟,也可以对系统时钟分频获得。如果流水线各段运行速度足够快,可以在一个系统时钟周期TCLK内完成相应处理,则可以用系统时钟直接作为流水线时钟。

其次,用流水线时钟控制所有流水线寄存器的输入锁存信号,使流水线寄存器在每个流水线时钟周期开始时锁存前一流水段产生的结果,并提供给本段做进一步处理。将图7.17中的PC看作IF段的流水线寄存器,5个流水线寄存器受同一流水线时钟控制,同步地实现将上段信息向下段传递,这样,每段的功能部件就可以对不同信息做同时处理。图7.18是加入流水线时钟实施同步控制的5级流水线逻辑图,它可以实现5条指令的同时处理。

图7.18带流水线时钟控制的RISC-V指令流水线

7.3.4指令系统对流水线设计的支持

(1)所有RISC-V指令长度相同,这一限制使得在IF段和ID段取指令与译码指令变得更加容易。而x86指令系统中的指令为1~17字节不等,实现流水线的难度要大得多。实际上,现代x86体系结构是将x86指令转换为类似于RISC-V指令的简单操作,然后将简单操作(而不是原生x86指令)流水化。

(2)RISC-V只有几种指令格式,源和目标寄存器字段位于每条指令的相同位置。

(3)主存操作数仅出现在RISC-V的加载或存储指令中,这个限制意味着可以使用EX段来计算主存地址,然后在MEM段访问主存。如果像x86那样访问主存操作数,那么EX段和MEM段将需要扩展到地址计算段、主存访问段,然后是执行段,甚至需要更多的流水段。

7.4流水线性能测量

7.4.1时－空图

为了直观地描述流水线的工作过程,通常采用时空图。时空图从时间和空间两个方面对流水线进行描述,如图7.19所示。其中,横坐标表示时间,纵坐标表示流水线资源(段,见图7.19(a))或流水线处理对象(指令/数据,见图7.19(b))。图7.19流水线时空图

从时空图中可以看到,当流水线被启动后,需要经过一个启动阶段流水管道才能被充满,这个启动阶段所用时间即为装入时间(也称通过时间或填充时间)。在理想的情况下,有

装入时间=(流水线级数-1)×时钟周期(7.3)

在装入时间之后,流水线达到稳定而被充分利用,并且每个时钟周期输出一个新的结果。

7.4.2吞吐率

吞吐率是指单位时间内流水线所完成的任务数或输出结果的数量,它是衡量流水线速度的重要指标。图7.20各段时间不等的流水线结构及时空图

最大吞吐率取决于流水线中最慢一段所需的时间,所以该段成为流水线的瓶颈。消除瓶颈的方法有:

(1)细分瓶颈段。这是一种普遍采用的方法,通过细分,使流水线的每一段运行时间尽可能地短,尽可能地一致,从而消除瓶颈段。

(2)重复设置瓶颈段。当瓶颈段不便于细分时,可以采用重复设置瓶颈段(即资源复用)的方法,如图7.21所示。图7.21重复设置瓶颈段的流水线结构及时空图

2.实际吞吐率

7.4.3加速比

7.4.4效率

效率指流水线的设备利用率。由于流水线有装入(填充)时间和排空时间,以及冒险(相关)造成的流水线停顿,因此流水线的各段并非一直满负荷工作,效率E<1。假设流水线各段运行时间τ相等,各段效率ei也相等,即

7.4.5流水线性能分析

例7.1某处理器中,浮点加法器采用4级流水线实现,流水线示意图如图7.7和图7.22(a)所示,每级处理时间为250ps。请确定:

(1)该浮点加法器计算100组数据采用非流水和流水处理所用时间各是多少?

(2)采用流水处理的加速比是多少?

(3)采用流水处理的最大吞吐率是多少?图7.22浮点加法流水线及时空图

例7.2在图7.18提供的5级RISC-V指令流水线上,7条指令分别在各段花费的处理时间如表7.3(流水线寄存器延迟忽略)所示。

(1)试为该流水线确定时钟频率。

(2)某段程序有1000条指令,ld和sd指令各占15%,beq指令占10%,其余为R型指令。该段程序在图6.2的非流水结构中的运行时间是多少?

(3)该段程序在图7.18的流水线上执行,若不考虑指令相关的影响,与非流水执行相比,加速比为多少?

例7.4某指令流水线各流水段的执行时间分别为

IF:10ns;ID:8ns;EX:10ns;WB:7ns

已知流水线级间缓冲延迟为1ns,求该指令流水线的加速比。

解在非流水线上,有

平均指令执行时间=10+8+10+7=35ns

在流水线上,有

例7.5某指令流水线由10级构成,每级处理时间为100ps。现要执行一段程序,该程序由50个结构相同、顺序执行的小程序段组成,每个小程序段由15条指令构成,其中第4条指令I4为条件跳转指令,当条件为真时程序跳转到指令I10,当条件为假时程序顺序执行。

(1)当所有条件跳转指令均未发生跳转时,执行这段程序时流水线的实际吞吐率、加速比、效率各是多少?

(2)当所有条件跳转指令均发生跳转时,执行这段程序时流水线的实际吞吐率、加速比、效率又是多少?

(3)比较(1)、(2)两种情形下的计算结果,可以清楚地看到,流水线一旦出现断流,其性能将明显下降。填充、停顿对流水线来说均是坏消息。

例7.6某指令流水线结构如图7.20(a)所示,在流水线不断流的情况下,试分析该流水线的吞吐率和加速比。

解由于流水线各段运行时间不同,假设可以采用异步方式控制,即流水线各段的推进可以按照各段运行时间进行控制,则流水线工作的时空状态如图7.23所示。最慢运行段S3的限制使得S1、S2段不能及时向前推进,到执行第4条指令开始,对流水线各段推进的控制已出现规律性,该规律正是图7.20(b)时空图所描述的流水线各段的时钟控制规律。图7.23图7.20(a)流水线时空图的另一种表示

也就是说,流水线采用异步控制并没有给流水线性能带来改善,反而会增加控制电路的复杂性,所以,流水线采用的基本控制方式一般为同步方式。同步控制与异步控制的差别还在于装入时间的不同和一条指令执行时间的不同,如表7.4所示。

7.5指令流水线的性能提高

理想的CPU体系结构是它的每个部分都一直在“工作”,且每个时钟周期至少启动/完成一条新的指令,这种结构的最佳实现之一就是流水线。合理地划分、设计流水线,使流水线每段内的操作必须在一个系统时钟周期内完成,就有可能实现每条流水线CPI=1的理想目标。

7.5.1流水线的基本性能问题

流水线并不能减少单条指令的执行时间,而且由于流水线段间存在流水线寄存器传输延迟、附加控制和时钟偏移等带来的额外开销时间,一般还会增加单条指令的执行时间。在流水线设计中,当流水线时钟周期小于最慢流水线段的运行时间时,流水线不能正常工作;当时钟周期小到与流水线额外开销相当时,流水已没有意义(因为这时在每一个时钟周期中已没有时间来做有用的工作)。但流水线能够显著提高处理指令的吞吐量,所以合理地设计指令流水线,解决影响流水线性能的各种问题,才能获得CPU对指令的高速执行。

增加流水线的深度(级数)可以提高流水线的性能,但流水线的深度受限于指令执行过程的可分解程度、流水线段的时间不均衡性和流水线的额外开销。除了流水线级数不能无限增大之外,限制指令流水线性能提高,使我们不能达到每条流水线在每个时钟周期处理一条指令这一目标的另一个主要问题是指令执行时可能存在的相关(Dependence)或“冒险(Hazard)”问题。如果流水线中指令间相互关联,就可能产生冒险。在没有特殊硬件和特定避免算法的情况下,冒险会导致流水线性能降低。

流水线中的冒险是指相邻或相近的两条指令因存在某种关联,使后一条指令不能在原设定的时钟周期开始执行,而必须暂停运行。冒险有以下3类:

(1)结构冒险(StructuralHazard)。当硬件资源不支持在同一个时钟周期内同时重叠执行多条指令时,出现结构冒险。

(2)数据冒险(DataHazard)。当一条指令需要用到前面某条指令尚未产生的结果,从而使该指令无法在预定的时钟周期执行时,发生数据冒险。

(3)控制冒险(ControlHazard)。当遇到分支等转移类指令或其他能够改变PC值的指令时,其后进入流水线的部分指令可能变成不期望执行的指令,由此造成流水线输出空操作,产生控制冒险。

消除冒险的基本方法就是暂停冒险出现之后发射到流水线中的指令,而让冒险出现之前发射的指令继续执行。所以冒险会引起流水线停顿(PipelineStall),停顿也称为气泡(Bubble)。

有停顿的流水线的CPI为

理想流水线CPI是指流水线能达到的最大性能,即CPI理想=1。通过减小式(7.17)右边各项停顿值,可以将总的流水线CPI减小,或IPC(每时钟周期指令数量)提高。

有停顿的流水线的加速比为

显然,如果流水线中没有停顿,加速比就会随流水线深度增加而加大。所以,消除冒险、减少停顿是提高已有流水线性能最重要的手段。

例7.7假设某流水线在分支跳转成功后会导致3个时钟周期的停顿,若分支指令的频度为30%,理想CPI=1,则实际的CPI为多少?

解实际CPI=1+30%×3≈2,因此实际的加速比将只能达到理想加速比的50%。

7.5.2结构冒险

有以下两种情形会导致结构冒险:

(1)部分功能单元没有充分流水(即存在流水线瓶颈段),造成使用该单元的指令不能按照预定的时钟周期向前流水,进而后续指令出现停顿。解决的方法就是将流水线设计得更合理,使每一流水段运行时间尽可能均衡。

(2)资源冲突(ResourceConflicts)。当两个以上流水线段需要同时使用同一个硬件资源时,冲突发生。例如,在指令流水线上,当取指段正从存储器中读出一条指令时,存结果段恰好要将之前某指令的执行结果写入到存储器中,因两者要同时访问同一存储器,故出现冲突。解决资源冲突的方法有:

①增加资源副本。

②改变资源以便它们能并发的使用。

③通过延迟(或暂停)流水线的冲突段或在冲突段插入流水线气泡(气泡在流水线中只占资源不做实际操作,即空操作),使各段“轮流”使用资源。

7.5.3数据冒险

在程序设计时,功能实现的逻辑需求使相邻或相近的指令常常因数据关联而具有相关性。当这些相关指令在流水线中重叠执行时,有可能出现预设的操作数读/写顺序被改变。当一条指令的结果还未有效生成,该结果就被作为后续指令的操作数时,数据冒险出现。

1.数据冒险类型

典型的数据冒险有写后读(RAW)、读后写(WAR)和写后写(WAW)。假设两条指令i和j,i先进入流水线。

(1)写后读或真相关。指令i修改寄存器或存储单元,指令j读取该寄存器或存储单元中的数据。如果读取发生在写入操作完成之前,则发生数据冒险。

(2)读后写或反相关。指令i读取寄存器或存储单元,指令j写入该寄存器或存储单元。如果写入操作在读取操作发生之前完成,则发生数据冒险。这种数据冒险仅出现在此类流水线中:有些指令是在流水线的后部读源操作数,而有些指令则是在流水线的前部写结果。一般流水线都是先读操作数,后写结果,因此这种冒险很少发生。复杂指令可能会导致这种冒险。

(3)写后写或输出相关。两个指令都写同一个寄存器或存储单元。如果i写入结果之前,j先写入结果,导致最后写入的结果不是预期的,则发生数据冒险。这种数据冒险仅出现在此类流水线中:流水线中有多个段可以进行写操作;或者当某条指令在流水线中暂停时,允许其后的指令继续向前流动。

例7.9某4级指令流水线如图7.24所示,各流水线段分别为取指IF、读数RD、执行EX和写结果WB。简单指令(表7.5中第1、2、4、6条指令)在EX1段执行,需1个时钟周期;复杂指令(表7.5中第3、5条指令)在EX2段执行,需3个时钟周期。当表7.5中第1~6条指令在流水线上执行时,分析指令的数据相关及冒险。图7.244级流水线结构示意图

2.解决方法

有几种方法处理流水线中数据冒险带来的问题:

(1)采用转发(Forwarding)技术。转发即在某些流水线段之间设置直接连接通路,也称为旁路(Bypassing)或短路(Short-Circuiting)。当转发硬件检测到前面某条指令的结果就是当前指令的源操作数时,控制逻辑会将前面那条指令的结果从其产生的地方直接连通到当前指令所需的位置,而将流水线上某些段旁路或短路掉,使当前指令提前获取操作数,避免流水线停顿。一个功能单元的输出不仅可以直接连通到其自身的输入,而且还可以直接连通到其他单元的输入,如图7.25中虚线所示。图7.25采用转发技术的流水线

(2)增加专用硬件。如果某种数据冒险不能用转发技术解决,则可以考虑增加流水线互锁(PipelineInterlock)硬件。互锁硬件先检测流水线上指令间是否存在数据冒险,当发现数据冒险时,使流水线在冒险出现段停顿下来(即插入气泡,或称空操作),直到冒险消失为止。

(3)利用编译器。某些系统的编译器可以对指令重新排序或插入空操作指令,使得会引起数据冒险的指令加载被延迟,但对程序逻辑或输出不受影响,这种技术称为流水线调度或指令调度。

(4)对寄存器读写做特别设计。在RISC-V中设定,在流水线时钟周期的前半部分写寄存器,后半部分读寄存器,在同一时钟周期中可以实现对同一寄存器先写后读操作。这样,当不同的流水线段在同一时钟周期内发生RAW时,不会产生数据冒险。

7.5.4控制冒险

一条正在处理的转移指令执行之前,流水线已获取甚至译码了几条在它之后的指令,转移指令的执行必然导致流水线上已有的一些指令变为不可用,需要将转移目标处的指令流重新发送到流水线中,流水线出现断流或停顿,从而引起控制冒险。

使程序执行顺序发生改变的转移指令有两类:无条件转移指令(如无条件跳转、调用、返回指令等)和条件分支指令(为零跳转、循环控制指令等)。由于流水线本身的结构特点,当流水线得知当前处理的是一条转移指令时,紧随转移指令之后的若干指令已被发送到流水线中。

条件分支指令是最难处理的转移指令。为了支持流水线,必须在每个流水线时钟周期内获取指令,但是是否有分支要到流水线深处才能知道,如在RISC-V的MEM段分支指令才会确定到哪里去取下一条指令,必然造成转移目标地址处的指令加载延迟。所以条件分支指令对流水线性能的影响远比无条件转移指令要大。

1.冻结(Freeze)流水线

CPU采用最简单的冻结流水线的方法处理早期的流水线分支指令,即一旦在指令译码段检测到分支指令,就在转移目标地址确定之前清除所有紧随分支指令之后发送到流水线上的指令,并插入流水线气泡(即空操作指令nop,这是一条没有动作且不改变状态的指令)。当分支指令从执行段流出并确定出新的PC值时,流水线才继续依据新PC值获取指令填充流水线。这样做控制简单,能保证程序正确运行,但会严重影响流水线的性能。

2.静态分支预测(StaticBranchPrediction)

程序中遇到条件分支指令时,若条件成立,则程序跳转到转移目标地址所确定的指令继续执行,分支跳转成功;若条件不成立,则程序顺序执行紧跟分支指令之后的指令。统计分析表明,在所有的条件分支中,跳转成功的概率是67%,其中向前跳转的成功率是60%,向后跳转的成功率是85%。

分支决策可以采用以下预测方法。

1)预测分支跳转不会发生(PredictNeverTaken)

在这样的预测机制下,知道分支结果之前,分支指令和紧随其后的指令均在流水线上正常流动。若分支未发生,则正如预期,流水线正常执行,没有停顿,控制冒险被消除;若分支成功,出现控制冒险,最简单的处理方式是用空操作取代已取得的指令(例如清除流水线输入端到执行段之前的各流水线段),并到目标地址重新取指令发送到流水线上。

2)预测分支跳转总是发生(PredictAlwaysTaken)

在这样的预测机制下,紧随分支指令进入流水线的指令,不是其后的顺序指令,而是从预先计算出的分支目标地址开始连续取得的指令。当分支指令成功跳转时,则正如预期,流水线正常执行,没有停顿,控制冒险被消除。

如果一个程序中包含较多的循环,那么采用这种预测机制是有利的,因为n次循环仅有一次会出现分支跳转失败。

3)由编译器预测

当编译器检测到语句For(i=0;i<1000000;i++){…}时,它就预测到循环尾部的跳转几乎肯定会发生。如果能有办法让编译器把这一信息告诉硬件流水线,将会消除大量的控制冒险。使用这种技术会带来体系结构的变化,而不仅仅是实现问题。例如,微处理器UltraSPARCⅢ中设计了一组新的条件跳转指令,这些指令中有一位可以由编译器设置,当编译器认为会发生跳转时(或者不会发生时),就设置该位。当遇到这样的指令时,取指单元就直接按照指令中的指示采取行动。

4)预测错误的处理

当预测错误时,流水线控制逻辑必须确保被错误预测的分支之后的指令执行不会生效,并且必须在正确的分支目标地址处重新开始启动流水线。

对于级数较小的指令流水线,简单的静态预测方案与编译器结合通常会有准确度较高的预测,但深度流水线会遇到许多复杂问题,分支惩罚会明显增加,流水线性能会受到影响。一种改进的机制是使用更多的硬件,并尝试在程序执行期间预测分支行为,即动态分支预测。

3.动态分支预测(DynamicBranchPrediction)

动态分支预测通过记录分支指令的近期运行历史,并以此作为预测的依据,来提高分支预测的准确度。

1)1位分支历史表动态分支预测的一种实现方案是分支历史表(BranchHistoryTable)或分支预测缓冲器(BranchPredictionBuffer)。分支历史表或分支预测缓冲器是由CPU维护的,由分支指令低位地址索引的,位于取指流水段IF的一个小存储器,用来记录分支指令在最近一次执行中是否发生了跳转。

图7.26(a)是动态分支预测的最简单情况。分支历史表为每个条件分支指令分配一个表项,该表项包括分支指令的地址(只保存高地址位作为标识),还有一位用于表示该指令最近一次执行时是否发生了跳转。分支历史表可以作为在IF段通过指令地址访问的专用Cache来实现,也可以附属于指令Cache中的每一块,随指令一起读取。图7.26分支历史表

2)2位分支历史表

为了减少类似循环这样的预测失误,可以在历史表中设置两个记录位,一位是对分支跳转的预测,另一位是上次实际跳转的情况,如图7.26(b)所示。使用该方案时,只有两次连续的预测都发生错误时才改变预测位。预测算法可以采用4个状态的有限状态机(FSM)实现,如图7.27所示,其中2位编码的左边一位表示预测,右边一位表示上次的实际跳转情况。在一系列连续正确的“不跳转”预测之后,FSM进入状态00,并对下一次跳转预测是“不跳转”。如果预测不正确,则FSM进入状态0l,但是继续预测是“不跳转”。如果预测仍然不正确,则FSM进入状态11,即把预测位改为“跳转”。该设计只使用了2位历史记录,我们也可以使用4位或者8位历史记录进行预测。图7.27用于分支预测的2位编码有限状态机

3)分支目标缓冲器

至此,我们都是假定每条分支指令的目标地址是已知的,或者是一个明确的地址(包括在指令中),或者是相对于当前指令的相对偏移量(即程序计数器加上一个带符号的数),通常情况下这种假设是成立的。但是,某些条件分支指令的目标地址是通过对寄存器内容进行运算得到的,这时,即使图7.27中的FSM能够准确地预测将要发生的跳转,但是这种预测对于目标地址未知的跳转指令也是毫无意义的,因为仍需要计算分支目标地址,依然存在控制冒险带来的若干时钟周期惩罚。解决这个问题的一种方案是在历史表中保存上一次分支指令的实际跳转地址,如图7.26(c)所示,这种方法称为分支目标缓冲器(BranchTargetBuffer,BTB)。

4)加入全局分支信息的预测器

2位动态预测方案只使用了特定分支指令的局部信息。研究表明,将局部分支信息和最近执行的分支指令的全局行为结合在一起,对于采用同样数量的预测位而言,具有更高的预测精度。当分支历史记录的数量和类型足够多时,动态分支预测能达到90%的正确率。这类利用全局分支信息的预测器包括相关预测器(CorrelatingPredictor)、锦标赛分支预测器(TournamentBranchPredictor)等。因为加入了对其他分支行为的记录而获得了全局历史信息,使这类方法具有更好的预测效果,所以近期研发的一些微处理器使用了这类预测器。

例7.10考虑三个分支预测方案:预测分支跳转绝对不会发生、预测分支跳转总是会发生和动态分支预测。假设正确预测时三种方案都有零惩罚,错误预测时都有两个时钟的惩罚,且动态预测器的平均预测准确度为90%。对于下列分支情形,哪个预测器是最佳选择?

(1)条件分支发生跳转的频率为5%。

(2)条件分支发生跳转的频率为95%。

(3)条件分支发生跳转的频率为70%。

解

(1)因为发生跳转的概率很低,所以最佳预测器选择为预测分支跳转绝对不会发生。

(2)因为发生跳转的概率很高,所以最佳预测器选择为预测分支跳转总是会发生。

(3)因为发生跳转的概率较高,且动态预测器的平均预测准确度为90%,所以最佳预测器选择为动态分支预测。

例7.11一个有10轮循环的循环程序段,假设采用1位分支历史表进行是否继续循环的预测,则该循环分支的预测准确度为多少?

解如果该循环程序段仅执行一次,且之前已将预测位设置为跳转,则仅在最后一轮循环中,对循环分支不可避免地会做出错误预测(退出循环时不需要跳转)。因为循环分支有9次正确预测,1次错误预测,故预测准确率为90%。如果该循环程序段执行多次,则之后的每次循环程序段执行时,由于上次循环结束时预测错误,且已将预测位修改为不跳转,使得进入本循环程序段的第一轮循环就出现错误预测。然后翻转预测位,使后8轮正确预测,最后一轮又出现错误预测。因此,此时循环分支的预测准确率仅为80%。

4.延迟分支(DelayedBranch)

延迟分支是利用编译器对指令代码进行重新排序,或在分支指令之后插入有用指令或空操作(Nop)指令,使分支延迟发生时流水线尽可能保持在充满状态。把分支开销为n的分支指令看成是延迟长度为n的分支指令,其后紧跟n个延迟槽。流水线遇到分支指令时,按正常方式处理,同时执行延迟槽中的指令,分支延迟槽中的指令“掩盖”了流水线原来必需插入的停顿周期,从而减少分支开销。

编译器的任务就是在延迟槽中放入有用指令或Nop指令,称为延迟槽调度。有三种调度方法:从分支前(FromBefore)调入、从目标处(FromTarget)调入、从失败处(FromFall-Through)调入,如图7.28所示。

(1)从分支前调入:被调度的指令必须与分支无关。

(2)从目标处调入:必须保证在分支失败时执行被调度的指令不会导致错误。有可能需要复制指令。

(3)从分支失败处调入:必须保证在分支成功时执行被调度的指令不会导致错误。图7.28调度延迟槽的方法

采用延迟分支法有两个限制:

①放入延迟槽的指令需要满足一定的条件;

②编译器要有预测分支是否成功的能力。为了提高编译器填充延迟槽的能力,大部分带条件跳转的计算机系统都引入了取消分支的技术,即分支指令带有对分支能否成功的预测。当预测正确时,正常执行延迟槽中的指令;否则,将延迟槽中的指令变成空操作(Nop)指令。

5.结论

事实上,分支指令在允许我们更改程序的执行顺序,使程序设计变得灵活方便的同时,也成为影响流水线性能提高的最大障碍。控制冒险对流水线性能造成的损失远比数据冒险要大得多。

7.6多发射处理器

对于单条指令流水线来说,理想CPI就是1。也就是说,在没有任何停顿的情况下,流水线毫无断流地处理指令所达到的最大吞吐率是每个时钟周期输出一条指令结果。在实际系统中,可以通过前述的各种手段使单条流水线的实际CPI接近于理想CPI。但随着对指令级并行性更高的要求,期望突破CPI理想=1的限制,使实际CPI<1成为高性能处理器支持指令级高度并行的基本理念。然而利用每个时钟周期发射一条指令的单流水线处理器是根本无法实现CPI<1这个目标的,于是多发射处理器应运而生。

7.6.1多发射的概念

多发射(MultipleIssue)是在一个时钟周期内启动多个指令并行执行的处理器实现方案。实现多发射处理器主要有两种方法:静态多发射和动态多发射,其主要区别在于编译器和硬件之间的分工。静态多发射(StaticMultipleIssue)是在程序编译时由编译器作出指令如何发射的决定。动态多发射(DynamicMultipleIssue)是在程序执行过程中由处理器硬件作出指令如何发射的决定。

多发射处理器实现需要解决以下两大问题:

(1)如何打包指令并将其送到发射槽中?

(2)如何处理数据冒险和控制冒险?

大多数静态发射处理器依赖编译器协助打包指令和处理数据与控制冒险。编译器的任务包括:确定在指定时钟周期向流水线发送多少条指令以及发送哪些指令,即组织发射包;进行静态分支预测和指令调度,以减少或防止各种冒险,并处理冒险引起的一些后果。

由于发射宽度的增长会削弱静态调度超标量的优势,因此静态超标量主要应用于发射宽度有限(一般情况下只有两条指令)的情况。而对于更大发射宽度,大多数设计者会选择VLIW或动态调度超标量来实现。表7.6给出了在多发射处理器中应用的五种主要方法以及它们的主要特征。

在多发射处理器中并行地处理指令需要做以下3项工作:

(1)检查指令间的相关性,以确定哪些指令可以组合在一起用于并行执行。

(2)将指令分配(Dispatch)给硬件功能单元。

(3)确定多个指令(或放在一个单字中)的启动时刻。

表7.7给出了硬件及编译器在这3项工作中所起的作用。

7.6.2超标量处理器

超标量处理器是由多条指令流水线或多个独立的执行单元组成的处理器。例如,PowerPC604有6个独立的执行单元:分支执行单元、加载/存储单元、浮点单元和3个整数单元,每个单元采用流水结构,构成多条流水线。

1.超标量处理器的一般结构

在超标量处理器中,简单的操作仅需要一个时钟周期的延迟,正如在基本的标量处理器(单条指令流水线)中一样。许多超标量处理器采用乱序发射、重命名技术,在每个时钟周期发射多条指令,通过使用多条功能流水线对多个标量数据进行并行处理,使每指令时钟数CPI实际低于1。现在实际的超标量处理器可以达到每时钟周期指令数IPC为2~6。

图7.29所示的是超标量处理器的一般结构。图7.29超标量处理器的一般结构

为了充分利用度为m的超标量处理器,m条指令必须是可并行执行的,否则流水线的停顿会使处理器进入等待状态。图7.30是度m=3的超标量流水线时空图,每条流水线均由4级构成。从图中可以清楚地看到,一个度为m的超标量处理器在没有冒险的情况下,其IPCmax=m。图7.30超标量处理器(度m=3)的时空图

2.超标量处理器实例

图7.31给出的是超标量处理器实例R10000。R10000是我们在第6章介绍的SGI/MIPS公司1995年生产的一款RISC微处理器,是一个单片的超标量处理器,其每个时钟周期发射4条指令,采用乱序控制。当时钟频率为200MHz时,其CPI为0.25,也即每秒执行800百万条指令(MIPS=800)图7.31R10000的指令流水线

7.6.3超长指令字处理器

1.VLIW处理器的一般结构

VLIW体系结构是开发指令级并行性的另一种选择。VLIW处理器的一般结构如图7.32所示,对比图7.29的超标量处理器的一般结构,两者似乎很相像,但实际上有两个关键不同。图7.32VLIW处理器的一般结构

(1)VLIW处理器从指令Cache每次取得一条很长的指令字(即VLIW)存入指令寄存器,该字由几个可以并行执行的原始指令组成,格式见图7.33(a),每个原始指令在VLIW中所占字段称为一个指令槽或操作槽(Slot),每个槽与功能单元一一对应。指令寄存器将VLIW中各原始指令同时派发到各功能单元中并行执行。图7.33VLIW处理器指令格式和流水线时空图

(2)VLIW处理器结构及控制逻辑比超标量处理器简单得多。由于并行执行的指令已由VLIW指令一次完整地显式提供,一般不需要完成动态调度或指令/操作的重排序,所以VLIW处理器没有复杂的重排序缓冲器和译码、分配逻辑,功能单元中也可以不设置保留站。这导致VLIW处理器执行指令的过程也异常简单:从指令Cache取得VLIW指令,然后在功能单元上并行执行VLIW指令。