第五章-重叠流水和现代处理器技术

主要内容：基本问题流水线技术向量流水技术现代处理器技术基本问题

如何提高CPU执行效率？

TCPU=IN*CPI*TCIN

：执行程序中的指令总数；CPI：执行每条指令所需的平均时钟周期数；TC

：时钟周期的时间长度。基本问题

其中：Ii

表示第i种指令在程序中执行次数,CPII表示执行一条第i类指令所需的平均时钟周期数,IN

为程序中所有的指令类数..

顺序执行方式

一条指令的执行过程：取指令->分析->执行执行n条指令所用的时间为：如每段时间都为t，则执行n条指令所用的时间为：T=3nt主要优点：控制简单，节省设备。主要缺点：执行指令的速度慢，功能部件的利用率很低。取指令k分析k执行k取指令k+1分析k+1执行k+1指令执行方式分析

此时，执行n条指令的时间为：T=(2+2n)t主要优点：

指令的执行时间缩短

功能部件的利用率明显提高主要缺点：

需要增加一些硬件

控制过程稍复杂取指分析执行取指分析执行取指分析执行一次重叠执行方式(一种最简单的流水线方式)二次重叠执行方式把取第k+1条指令提前到分析第k条指令同时执行如果三个过程的时间相等，执行n条指令的时间为：T=(2+n)t理想情况下同时有三条指令在执行处理机的结构要作比较大的改变（必须采用先行控制方式）取指k+2分析k+2执行k+2取指k+1分析k+1执行k+1取指k分析k执行k主要内容：基本问题流水线技术向量流水技术现代处理器技术流水线技术

包含以下内容：流水线的分类流水线的表示方法流水线的特点流水线的性能分析非线性流水线技术流水线的分类从流水线具有功能多少来看，可以分为单功能流水线和多功能流水线。单功能流水线只能实现一种功能的流水处理。取指令译码执行保存结果t1t2t3t4多功能流水线是指同一流水线的各段之间可以通过不同的连接方式实现多种不同的运算或功能。流水线的分类输入减阶对阶移位相加规格化相乘累加输出12345678输入减阶对阶移位相加规格化输出123458输入相乘累加输出1678流水功能段浮点加、减法运算定点乘法运算按多功能流水线的各段能否允许同时用多种不同功能连接流水，可把流水线分为静态流水线和动态流水线。静态流水线在某一时间内各段只能按一种功能连接流水。动态流水线的各段在同一时间内可按不同运算或功能连接。流水线的分类可同时进行浮点加、减运算和定点乘法运算的流水线流水线的分类输入减阶对阶移位相加规格化相乘累加输出12345678从流水线中各功能段之间是否有反馈回路，可以把流水线分为线性流水线和非线性流水线。流水线的分类S1S2S3S4输出输入反馈线流水线的表示方法流水线的表示法有三种：连接图、时空图、预约表。主要考虑前二种。1、简单流水线的连接图表示流水线的每一个阶段称为流水步、流水步骤、流水段、流水线阶段、流水功能段、功能段、流水级、流水节拍等。一个流水阶段与另一个流水阶段相连形成流水线。指令从流水线一端进入，经过流水线的处理，从另一端流出。有些复杂指令在执行阶段也采用流水线方式工作，称为操作流水线。取指令译码执行保存结果t1t2t3t42、一种指令流水线一般4至12个流水段，等于及大于8个流水段的称为超流水线处理机。取指形成操

作数地址译码取操作数执行保存结果流水线的表示方法3、流水线的时空图采用“时空图”表示流水线的工作过程。一条简单流水线的时空图：分析k分析k+1分析k+2分析k+3执行k执行k+1执行k+2执行k+3时间空间0t1t2t3t4t5流水线的表示方法

一个浮点加法器流水线的时空图(由求阶差、对阶、尾数加和规格化4个流水段组成)：ED1时间空间0t1t2t3t4t5ED2ED3ED4ED5EA1EA2EA3EA4EA5MA1MA2MA3MA4MA5NL1NL2NL3NL4NL5t6t7t8NL：规格化MA：尾数加EA：对阶ED：求阶差流水线的表示方法在流水线的每一个功能部件的后面都要有一个缓冲器，称为锁存器、闸门寄存器等，它的作用是保存本流水段的执行结果。各流水段的时间应尽量相等，否则回引起阻塞、断流等。只有连续提供同类任务才能充分发挥流水线的效率。在流水线的每一个流水线段中都要设置一个流水锁存器。流水线需要有“装入时间”和“排空时间”。只有流水线完全充满时，整个流水线的效率才能得到充分发挥。流水线的主要特点衡量流水线性能的主要指标有：吞吐率、加速比和效率1、吞吐率（ThoughPut）求流水线吞吐率的最基本公式：

TP=n/Tk

n为任务数,Tk为完成n个任务所用时间各段执行时间相等，输入连续任务情况下完成n个连续任务需要的总时间为：

Tk=(k+n-1)Dt

k为流水线的段数，Dt为时钟周期线性流水线的性能分析1时间空间S123……n-1nS2S3S4123……n-1n123……n-1n123……n-1nkDt(n-1)DtnDt(k-1)DtT线性流水线的性能分析

吞吐率：

最大吞吐率为：

各段执行时间不相等、输入连续任务情况下：

吞吐率为：

最大吞吐率为：线性流水线的性能分析流水线各段执行时间不相等的解决办法S1输入Dt1=DtS2Dt2=3DtS3Dt3=DtS4Dt4=Dt输出1时间空间S1S2S3S4SDti(n-1)Dt2Tk23…n123…n123…n123…n线性流水线的性能分析一是将“瓶颈”流水段细分(如果可分的话)：二是将“瓶颈”流水段重复设置：S1输入输出DtS2-1DtS2-2DtS2-3DtS3DtS4DtS2(3Dt)S1输入输出Dt1=DtS2-1S2-1S2-1S3S4Dt3=DtDt4=DtDt2=3Dt线性流水线的性能分析流水段重复设置的流水线1时间空间23nS1S2-1456…14…-2-1n-225…n-136…n123n456…-2-1123n456…-2-1S2-2S2-3S3S4线性流水线的性能分析2、加速比（Speedup）计算流水线加速比的基本公式：

S=顺序执行时间T0/流水线执行时间Tk各段执行时间相等，输入连续任务情况下

加速比为：

最大加速比为：

各段执行时间不等，输入连续任务情况下实际加速比为：线性流水线的性能分析K=6K=10任务

个数加速比10246811248163264128线性流水线的性能分析3、效率（Efficiency）计算流水线效率的一般公式：

各流水段执行时间相等，输入n个连续任务

流水线的效率为：

流水线的最高效率为：

线性流水线的性能分析1时间空间S123……n-1nS2S3S4123……n-1n123……n-1n123……n-1nkDt(n-1)DtnDt(k-1)DtT线性流水线的性能分析

各流水段执行时间不等，输入n个连续任务流水线的效率为：线性流水线的性能分析S1输入Dt1=DtS2Dt2=3DtS3Dt3=DtS4Dt4=Dt输出1时间空间S1S2S3S4SDti(n-1)Dt2Tk23…n123…n123…n123…n线性流水线的性能分析流水线的吞吐率、加速比与效率的关系：

因为

因此：E=TP·

Dt

，S=k·E线性流水线的性能分析4、流水线性能分析举例对于单功能线性流水线，输入连续任务的情况，通过上面给出的公式很容易计算出流水线的吞吐率、加速比和效率。例5.2：用一条4段浮点加法器流水线求8个浮点数的和：

Z＝A＋B＋C＋D＋E＋F＋G＋H线性流水线的性能分析解：Z=[(A+B)+(C+D)]+[(E+F)+(G+H)]1时间空间23求阶差4567123456712345671234567对阶尾数加规格化加数ACEGA+BE+FBDFHC+DG+HA+B+C+DE+F+G+H结果A+BC+DE+FG+HA+B+C+DE+F+G+HZ线性流水线的性能分析7个浮点加法共用了15个时钟周期。

流水线的吞吐率为：

流水线的加速比为：

流水线的效率为：线性流水线的性能分析什么是非线性流水线？

如果存在反馈回路，当一个任务在流水线中流过时，在同一个流水段中可能要经过多次。不能每一个时钟周期向流水线输入一个新任务。这样的流水线就是非线性流水线。非线性流水线的调度问题就是要解决要隔多少个时钟周期向流水线输入一个新任务才能使流水线的各个流水段都不发生冲突。表示一个非线性流水线需要用到连接图和预约表。非线性流水线技术S1S2S3S4输出输入反馈线

时间流水段1234567S1XXXS2XS3XXS4X非线性流水线1的连接图非线性流水线的预约表S1S2S3S4输出输入反馈线

时间流水段1234567S1XXXS2XXS3XXS4X非线性流水线2的连接图非线性流水线的预约表预约表横坐标表示流水线的时钟周期，纵坐标表示流水线的各个流水段，中间有“X”表示该流水段在这一个时钟周期处于工作状态，空白表示该流水段在这一个时钟周期不工作。一行中可以有多个“X”，表示一个任务在不同时钟周期重复使用了同一流水段；一列中有多个“X”表示在同一个时钟周期同时占用了多个流水段。预约表的行数是流水线的段数，预约表的列数是一个任务从进入流水线到流水线中输出所经过的时钟周期数。向一条非线性流水线的输入端连续输入两个任务之间的时间间隔称为非线性流水线的启动距离，以时钟周期数表示。非线性流水线技术当使用某些启动距离时，将在某些流水段发生冲突，即两个或两个以上任务同时争用一个流水段。引起非线性流水线流水段冲突的启动距离称为禁启动止距离。不发生冲突的启动距离是一个循环数列。使非线性流水线的任何一个流水段在任何一个时钟周期都不发生冲突的循环数列称为非线性流水线的启动循环。非线性流水线技术…X3X2X1S4…X4X2X3X1X2X1S3…X3X4X2X3X1X2X1S2…X2X3X4X1X2X3X1X2X1S1…1110987654321

时间流水段启动距离为3的流水线冲突情况两个任务争用一个流水段S1三个任务争用一个流水段S1启动距离为5的流水线预约表…X2X1X1S4…X2X2X2X1S3…X3X1X1S2…X2X1X1X1S1…1110987654321

时间流水段X2X2启动周期重复启动周期（5）是一个循环，称为恒定循环。非线性流水线技术时间流水段12345678910111213141516S1X1X2X1X2X1X2X3X4X3X4X3X4S2X1X2X1X2X3X4X3X4S3X1X2X1X2X3X4X3X4S4X1X2X3X4启动距离为（1，7）循环时的流水线预约表要正确地调度一条非线性流水线，首先要找出流水线的所有禁止启动距离。所有禁止启动启动距离组合在一起成为一个数列，称为禁止向量。非线性流水线技术由预约表得到禁止向量的方法：

将预约表的每一行中任意两个“X”之间的距离都计算出来，去掉重复的，这种数组成的一个数列就是这条非线性流水线的禁止向量。例如：前述的非线性流水线，其禁止向量为（3，4，6）。把一个启动循环内的所有启动距离相加，然后再除以这个循环内的启动距离个数，就得到这个启动循环的平均启动距离。非线性流水线无冲突调度的主要目标是要找出具有最小平均启动距离的启动循环，按照这样的启动循环向非线性流水线的输入端输入任务，流水线的工作速度最快，而且所有流水段在任何时间都没有冲突。非线性流水线技术例子：一条有4个流水段的非线性流水线，每个流水段的延迟时间都相等，它的预约表如下图：

时间流水段1234567S1XXS2XXS3XXS4X非线性流水线技术（1）写出流水线的禁止向量和初始冲突向量（2）画出调度流水线的状态图（3）求流水线的最小启动循环和最小启动距离（4）求平均启动距离最小的恒定循环。解：（1）禁止向量为（2，4，6）冲突向量：用二进制表示，长度是禁止向量的最大距离。冲突向量C=（C6C5C4C3C2C1），由禁止向量，C2=C4=C6=1，其余位为0，冲突向量为C=（101010）。非线性流水线技术（2）由冲突向量构造一张图：将C放到一个6位逻辑右移移位器，当从移位器右移出0，用移位器中的值与初始冲突向量做“按位或”，得到一个新的冲突向量。当移位器移出1，不做任何处理。重复这个步骤。对产生的每一个新的冲突向量做同样处理。在初始冲突向量和所有形成的冲突向量之间，箭头连接。非线性流水线技术1010101111111011111010117*157*3537*当右移2、4、6位，时移出位为1，表示用这些启动距离输入新任务要发生冲突，不做任何处理。当右移1、3、5和大于等于7位时，移出位是0，表示用这些启动距离输入新任务不会发生冲突。7*表示大于等于75（3）从状态图中可以找到许多不发生流水段冲突的启动循环。，只要找到简单循环，进而确定平均启动距离最小的启动循环。它们是：（1，7）、（3，5，7）、（5，7）等简单循环平均启动距离（1，7）4（3，5）4（5，7）6（3，5，7）5（5，3，7）5（3，5）4（5）5（7）7最小启动循环是具有最小平均最小启动距离的启动循环。非线性流水线技术最小循环为（1，7）、（3，5）最小恒定循环为（5）

时间流水12345678910111213141516S1X1X2X1X3X2X4X3…S2X1X2X1X2X3X4X3…S3X1X1X2X2X3X3X4…S4X1X2X3X4…最小启动循环为（3，5）的流水线工作状态非线性流水线技术

时间流水段123456789101112131415S1X1X2X1X2X3X4X3S2X1X2X1X2X3X4X3X4S3X1X2X1X2X3X4X3X4S4X1X2X3X4最小启动循环为（1，7）的流水线工作状态非线性流水线技术

时间流水段123456789101112131415S1X1

X2X1

X3X2

S2X1

X1X2X2X3

S3X1

X1

X2X2

X3

X3S4X1

X2

X3恒定启动循环（5）的流水线工作状态启动周期重复启动周期非线性流水线技术主要内容：基本问题流水线技术向量流水技术现代处理器技术向量流水技术向量处理的特点向量处理机的基本结构向量处理的方法向量处理的关键技术向量流水处理的主要特点1、向量流水处理的主要特点

(1)各个元素的操作一般相同且数据相互独立，不存在相关。非常适合于流水处理；

(2)一条向量指令相当于一个标量循环,可降低对指令访问带宽的要求；

(3)一般采用多体交叉存储，支持跨步长度访问向量处理机的基本概念

具有向量数据表示和向量指令系统的处理机称为向量处理机。向量处理机是解决数值计算问题的一种高性能计算机结构。向量处理机一般都采用流水线结构，往往有多条流水线并行工作。向量处理机通常属大型或巨型机，也可以用微机加一台向量协处理器组成。一般向量计算机中包括有一台高性能标量处理机。必须把要解决的问题转化为向量运算，向量处理机才能充分发挥作用。一个典型向量求解问题:

Y=a*X+Y

其中X和Y为向量,初始值存放在存储器中,a为标量。通常,根据这一求解表达式是单精度还是双精度操作,分别称为SAXPY(Single-precisionAXplusY)或DAXPY循环,表示是单精度或双精度的A乘X后再加Y。若用向量机来完成同样操作,则有:

LDF0,a;标量a装入F0LVV1,Rx;装入向量X,LV为向量取指令

MULTVV2,F0,V1;向量X与标量a相乘

LVV3,Ry;装入向量YADDVV4,V2,V3;向量加aX+YSVRy,V4;存结果向量,SV为向量存指令向量机只需执行6条指令,从而可大大降低对指令带宽要求向量处理机的基本结构

向量处理机的基本结构形式按向量操作对象及结果主要存放方式分类：

1）存储器—存储器工作方式向量机利用多个独立的存储器模块并行工作。

2）寄存器—寄存器工作方式向量机主要利用向量寄存器。存储器－存储器结构

采用多个存储体交叉和并行访问来提高存储器速度；操作数缓冲栈和写结果缓冲栈主要用于解决访问存储器冲突；主要优缺点：硬件结构简单，造价低。速度相对比较低。早期的向量处理多采用这种存储器-存储器结构。

主存储器操作数缓冲栈流水线运算部件写结果缓冲栈寄存器－寄存器结构（Cray－1）寄存器－寄存器结构把存储器-存储器结构中的缓冲栈改为向量寄存器，运算部件需要的操作数从向量寄存器中读取，运算的中间结果也写到向量寄存器中。向量寄存器与标量寄存器的主要差别是：一个向量寄存器能够保存一个向量，例如：64个64位寄存器。采用寄存器-寄存器结构的主要优点：降低主存储器的流量。

例如：寄存器-寄存器结构的CRAY-1与存储器-存储器结构的STAR-100比较，运算速度高3倍多（时钟周期为40：12.5），主存储器流量低2.5倍。1976年，CRAY公司推出CRAY-1向量机，开始了向量机的蓬勃发展，其峰值速度为0.1Gflops。

Cray1

1985年，CRAY-2，1Gflops

1990年,SX-3,22Gflops

1991年，Cray-YMP-C90,16GflopsCray2CrayXMP/4CRAYY-MP816系统结构1991年多向量处理器时间并行+空间并行256交叉存储16MB－1GB大量使用寄存器64位浮点/定点1983年12月,银河-I巨型计算机由国防科技大学计算机研究所研制成功。

银河-II并行巨型计算机由国防科技大学计算机研究所于1992年11月研制成功。银河1银河2向量处理方法

向量处理方式有三种类型：1．横向处理方式：向量计算是按行的方式从左至右横向地进行。也称水平处理方式，横向加工方式等。2．纵向处理方式：向量计算是按列的方式自上而下纵向地进行。也称垂直处理方式，纵向加工方式等。3．纵横处理方式：横向处理和纵向处理相结合的方式。也称分组处理方式，纵横向加工方式等。

以一个简单的C语言编写的程序为例，说明向量的三种处理方式的工作原理。for(i=1；i<=N；i++)y[i]=a[i](b[i]+c[i]);

逐个分量进行处理：假设中间结果为T(I)。计算第1个分量：T(1)=B(1)+C(1) Y(1)=A(1)

T(1)计算第2个分量：T(2)=B(2)+C(2) Y(2)=A(2)

T(2)

……计算最后一个分量：T(N)=B(N)+C(N) Y(N)=A(N)

T(N)

即逐个求Y中的N个分量,先进行相加t1←b1+c1,其中t1为暂存单元,然后相乘y1←t1×a1。横向处理方式横向处理方式存在两个问题：在计算向量的每个分量时，都发生写读数据相关。流水线效率低。如果采用多功能流水线，必须频繁进行流水线切换。结论：这种加工方式不适合于向量流水处理。纵向处理方式

先纵向加工所有B和C向量中元素对的相加操作,中间结果暂存到t1～tN中,然后再纵向加工所有对应元素的乘法操作。

T(1)=B(1)+C(1) T(2)=B(2)+C(2)

…… T(n)=B(n)+C(n) Y(1)=A(1)

T(1) Y(2)=A(2)

T(2)

…… Y(n)=A(n)

T(n)

用向量指令形式表示时,变成:T=B+CY=T×A纵向处理方式特点：流水线功能的切换只需一次。可获得较高的吞吐率。

数据相关不影响流水线连续工作，可采用向量链接技术。结论：

这种处理方式适用于向量处理机。纵横处理方式纵横向加工(或称为分组加工)

以寄存器—寄存器方式工作的向量机都采用这种加工方式。因为向量寄存器的长度有限(如CRAY-1的长度为64)。当向量长度超过向量寄存器可表示的最大限度n时,就不得不分组加以处理。假设向量长度为N,则有N=kn+r,其中n≤N,r<n,n、k、r均为正整数,k为组数,r为余数(余下的部分也作为一组处理)。它的加工方式是:组内纵向加工,组间为横向加工。第一组计算:t1～n=b1～n+c1～ny1～n=a1～n+t1～n再算第二组:tn+1～2n=bn+1～2n+cn+1～2nyn+1～2n=an+1～2n+tn+1～2n

向量处理的关键技术向量与标量性能的平衡向量链接技术向量循环开采技术向量与标量性能的平衡

实际的应用问题中通常既有向量计算又有标量计算，而且两类计算有一定的比例。向量平衡点(vectorbalancepoint)：

为了使向量硬件设备和标量硬件设备的利用率相等，一个程序中向量代码所占的百分比。关键问题是：向量硬件和标量硬件都能充分利用，都不空闲。向量处理机的向量平衡点必须与用户程序的向量化程度相匹配。向量与标量性能的平衡机器型号CrayISCray2SCrayX-MP

CrayY-MPhitachiS820

NECSX2

FujitsuVP4000

向量性能(Mflops)85.0151.5143.3201.6737.3424.2207.1标量性能(Mflops)9.811.213.117.017.89.56.6向量平衡点0.900.930.920.920.980.980.97几种超级计算机向量和标量的性能向量链接技术向量运算中的相关和冲突向量运算中的数据相关和功能部件冲突主要有：写读数据相关；读读数据相关，或向量寄存器冲突；运算部件冲突。V0

V1＋V2 V0

V1＋V2V3

V4

V5 V3

V0

V4(a)不相关的指令

(b)写读数据相关V0

V1＋V2 V0

V1＋V2V3

V4＋V5 V3

V1

V4(c)功能部件冲突 (d)读读数据相关向量链接技术

利用向量指令间存在的先写后读的数据相关性来加快向量指令序列执行速度的技术称为链接技术。具体的说，结果寄存器可能成为后继指令的操作数寄存器，两条有数据相关的向量指令并行执行。

例如：ADDVV1,V2,V3;V1←V2+V3MULTVV4,V1,V5;V4←V1×V5

分析：这两条指令间对V1向量寄存器存在先写后读相关,通常必须等加法指令做完后才可开始乘法指令,但如果使向量寄存器(例中的V1)在同一时钟周期内,既接收一个功能部件送来的运算结果,又可把这一结果作为下一个向量指令运算所需的源操作数送给另一个功能部件,那就可使这两个部件链接起来进行操作。当链接进入充分流水操作状态后,在一个时钟周期内就可同时获取两个操作结果。向量链接技术以CRAY-1为例,设有如下向量运算:D=A×(B+C)

假设向量长度≤64,且B和C已由存储器取至V0和V1,则下面3条向量指令就可完成上述运算:LDV3,A;V3←aADDVV2,V0,V1;V2←V0+V1MULTVV4,V2,V3;V4←V2×V3向量链接技术LDV3,A;V3←aADDVV2,V0,V1;V2←V0+V1MULTVV4,V2,V3;V4←V2xV3情况一：若这三条指令全部用串行方法则所需时间为:[(1+6+1)+N-1]+[(1+6+1))+N-1]+[(1+7+1)+N-1]=3N+22情况二：若前两条指令并行执行,第三条指令串行执行,则所需时间为:[(1+6+1)+N-1]+[(1+7+1)+N-1]=2N+15拍情况三：采用并行和链接加速技术后,执行所需时间为:(1+6+1)+(1+7+1)+(N-1)=17+N-1=N+16拍设被加工向量长度为N向量链接技术链接的条件：链接两条或多条指令存在先写后读相关只有当前一指令的第一个结果分量送入结果向量寄存器的那一个时钟周期方可链接当一条向量指令的两个源操作数分别是两条先行指令的结果寄存器时,要求先行的两条指令产生运算结果的时间必须相等,即要求有关功能部件的延迟时间相等链接的两条向量指令的向量长度必须相等针对不同的向量机,可能对链接还有其他特殊限制。如CRAY-1中,允许自存储器取数操作参与链接,但不允许向存储器写数操作实现链接,因为CRAY-1并不提供这种链接功能。向量循环开采技术

当向量的长度大于向量寄存器的长度时，必须把长向量分成长度固定的段，采用循环结构处理这个长向量，这种技术称为向量循环开采技术，也称为向量分段开采技术。

例如：A和B为长度N的向量。

for(i=1;i<=N;i++)a[i]=5*b(i)+c;向量循环开采技术当N为64或更小时，产生A数组的7条指令序列是：1：S1

5.0 在标量寄存器内设置常数2：S2

C 将常数C装入标量寄存器3：VL

N 在VL寄存器内设置向量长度4：V0

B 将B向量读入向量寄存器5：V1

S1

V0B数组的每个分量和常数相乘6：V2

S2＋V1 C和5

B(i)相加7：A

V2

将结果向量存入A数组第4、5、6、7条指令可以采用向量链接执行。当N超过64时，就需要采用向量循环。向量循环开采技术

向量的分段开采：

low=1VL=(NmodMVL)*找出零头长度值

do20j=0,(N/MVL)*外循环

do10i=low,low+VL-1*以长度VL操作

4：V0

B 5：V1

S1

V0 6：V2

S2＋V1 主要操作

7：A

V2

10continuelow=low+VL*下一向量的开始

VL=MVL*将长度值恢复成MVL20contine

经分段处理后,第一段长度为nmodMVL,而以后各段的长度均为MVL（向量寄存器的长度）。主要内容：基本问题流水线技术向量流水技术现代处理器技术不能回避的问题SoEasy???No!进一步的思考：采用流水线技术所带来的问题。取指令译码执行保存结果t1t2t3t4I:addr1,r2,r3J:subr4,r1,r3

研究相关性，不但可作为是否可指令调度的依据，而且可了解程序固有的并行性以及可以获得的并行性。相关

意味指令的运行、结果产生的顺序有要求，意味指令的并行运行和改变顺序可能会产生问题，是否意味指令的流水线运行一定会产生停顿。流水线的主要障碍:

相关(Hazard)流水线3类相关结构相关:硬件不能支持两条指令同时访问同一个资源

twodogsfightingforthesamebone数据相关:指令依赖于前面尚在流水线中的指令的执行结果控制相关:在判断转移条件之前，就试图决策转移方向(分支指令、跳转指令)解决相关性问题，提高处理器执行效率，是推动处理器新技术产生的动力源泉。流水线的主要障碍:

相关(Hazard)结构相关－单口存储器指令和数据共用同一个存储器存储器为单口存储器冲突发生条件Instr1存储器访问指令读写存储器Instr2取指令时间(时钟周期)LoadInstr1Instr2Instr3Instr4RegALUDMemIfetchRegRegALUDMemIfetchRegRegALUDMemIfetchRegCycle1Cycle2Cycle3Cycle4Cycle6Cycle7Cycle5存储器冲突DMemRegALUDMemRegIfetch结构相关－单口存储器指令执行次序时间(时钟周期)LoadInstr1Instr2StallInstr3RegALUDMemIfetchRegRegALUDMemIfetchRegRegALUDMemIfetchRegCycle1Cycle2Cycle3Cycle4Cycle6Cycle7Cycle5RegALUDMemIfetchReg气泡气泡气泡气泡气泡结构相关解决方案之一：气泡消除结构相关原因：资源争用方法1:等待第一步：检测第二步：插入等待(空操作/气泡)方法2:投入更多的硬件资源双存储器(“HarvardArchitecture”)多端口存储器（寄存器堆）三类数据相关ReadAfterWrite(RAW)

先写后读(写未完成，读即发出)InstrJ在InstrI完成写之前读

起因：基于变量的通讯RAW相关是程序相关性中最本质的相关性之一。I:addr1,r2,r3J:subr4,r1,r3WriteAfterRead(WAR)

先读后写InstrJ在InstrI完成读之前进行写操作

反相关起因：r1的重用I:subr4,r1,r3J:addr1,r2,r3K:mulr6,r1,r7三类数据相关WriteAfterWrite(WAW)

写后写InstrJ在InstrI完成写之前进行写操作

输出相关起因是r1的重用I:subr1,r4,r3J:addr1,r2,r3K:mulr6,r1,r7三类数据相关

无妨假设处理器执行如下形式的操作：rk(ri)op(rj)则：rk(ri)op(rj)rm(rk)op(rn)称为RAW（ReadAfterWrite）相关；

ri(rk)op(rj)rk(rm)op(rn)称为WAR（WriteAfterRead）相关；

rk(ri)op(rj)rk(rm)op(rn)称为WAW（WriteAfterWrite）相关。三类数据相关（一般性定义）

指令的范围（Range)和域(Domain)：

R(i):

指令i所修改的寄存器（或存储器单元）的集合。

D(i):

指令i所读取的寄存器（或存储器单元）的集合。假设指令j在程序的执行顺序中是指令i的后续指令。若指令j提前于指令i执行，则可能引起：

RAW相关冲突，如果R(i)D(j)Ø;WAR相关冲突，如果D(i)R(j)Ø;

WAW相关冲突，如果R(i)R(j)Ø;三类数据相关（判别）RAW相关的解决策略－流水线旁路时间(时钟周期)指令执行次序addr1,r2,r3subr4,r1,r3andr6,r1,r7orr8,r1,r9xorr10,r1,r11RegALUDMemIfetchRegRegALUDMemIfetchRegRegALUDMemIfetchRegRegALUDMemIfetchRegRegALUDMemIfetchRegRegALUDMemIfetchRegRAW相关的解决策略－流水线旁路时间(时钟周期)指令执行次序ldr1,4(r2)subr4,r1,r6andr6,r1,r7orr8,r1,r9RAW相关仍然存在－Load指令RegALUDMemIfetchRegRegALUDMemIfetchRegRegALUDMemIfetchRegRegALUDMemIfetchReg旁路未能解决所有问题流水线互锁－解决Load引发的RAW相关时间(时钟周期)orr8,r1,r9指令执行次序ldr1,4(r2)subr4,r1,r6andr6,r1,r7RegALUDMemIfetchRegRegIfetchALUDMemRegBubbleIfetchALUDMemRegBubbleRegIfetchALUDMemBubbleRegWAR和WAW相关WAR：WAW：这两类相关由寄存器重用引起；指令顺序不能改变；在单功能流水线中不可能发生。I:subr4,r1,r3J:addr1,r2,r3K:mulr6,r1,r7I:subr1,r4,r3J:addr1,r2,r3K:mulr6,r1,r7多功能流水线IFIDIssueGPR’sFPR’sALUFaddFmulFdivWBI:Fdivr4,r1,r3J:addr1,r2,r3K:mulr6,r1,r7I:Fmulr1,r4,r3J:addr1,r2,r3K:mulr6,r1,r7定点指令：1clock浮点指令：3clocks对于多功能流水线：由每个功能单元的执行时间不同（如定点和浮点运算）WAR和WAW相关可能引起执行错误。解决WAR和WAW相关的最简单的方法：停顿（暂停）。指令的可以按程序顺序发射（In-order-Issue），但完成顺序则可能与程序顺序不同，即乱序完成（Out-of-orderComplete）。多功能流水线数据相关的解决策略－指令调度

指令调度：通过改变指令在程序中的位置，将相关指令之间的距离加大到不小于指令执行延迟的时钟数，使相关指令成为实际上的无关指令。指令调度（静态）通常由编译完成。指令调度（动态）通常采用硬件实现。动机编译时某些情况无法判断，可以利用那些只有运行时才能看到的信息；简化编译器设计；代码的可移植性好。核心思路允许暂停后的指令执行；寄存器重命名。硬件动态调度算法硬件动态调度算法记分板(Scoreboard)

命名起源于CDC6600，其基本结构：寄存器文件浮点乘浮点乘浮点除浮点加定点部件记分板硬件动态调度算法其基本控制阶段：发射(Issue)指令译码检测结构相关、写写相关当前指令被阻塞后续指令被阻塞读操作数(Readoperands)在没有数据相关的前提下读取操作数执行(Execution)功能部件执行完后通知记分板控制系统写回结果(WriteResult)记分板检测功能部件的写回，若发现有相关冲突则暂停记分板主要部件：指令状态表指令处于哪个阶段功能部件状态表

功能部件当前状态，9个域

Busy—是否正在使用

Op—运算类型(＋/－)

Fi—目标寄存器

Fj,Fk—源寄存器

Qj,Qk—产生Fj，Fk的功能部件

Rj,Rk—Fj,Fk就绪标志寄存器结果状态表

指示哪个功能部件将写入该寄存器。如果没有指令写该寄存器，则为空。硬件动态调度算法记分板算法对CDC6600的加速比：对FORTRAN语言，性能提高1.7倍；对手写汇编程序，性能提高2.5倍。6600记分板局限性：指令窗口小

指令调度有限；功能部件少

结构冒险(整数load/store部件)；结构冒险

暂停发射。硬件动态调度算法硬件动态调度算法Tomasulo算法1.采用于IBM360/91浮点部件(1967年)；2.将记分牌技术和寄存器重命名技术结合起来，更有效地解决写后写、读后写相关；1967年，IBM公司的RobertTomasulo

开创性的提出了解决上述问题的方法-------寄存器重命名（RrgisterRenaming)。寄存器重命名技术使得在不改变指令系统前提下实际寄存器数量得到增加。换句话说，可以使用比ISA（IndustryStandardArchitecture)更多的寄存器而依然保持与ISA的兼容性。FP加法器Add1Add2Add3FP乘法器Mult1Mult2丛主存来保留站CommonDataBus(CDB)去主存FP操作队列读数缓冲区写缓冲区硬件动态调度算法硬件动态调度算法保留站的组成：Op:功能单元运算类型(+或–)Vj,Vk:源操作数值Qj,Qk:产生源操作数的保留站Qj,Qk=0

数据就绪Busy:保留站或相关FU忙寄存器结果状态表指示哪个FU要写哪个寄存器如果没有将写入寄存器的未决指令，则该域为空硬件动态调度算法发射—丛FP操作队列中取指令如果保留站空闲(没有结构冒险)，则控制单元发射指令&发送操作数(对寄存器进行换名)执行—对操作数进行操作(EX)如果两个操作数都就绪

执行如果未就绪监控CDB写回—完成执行(WB)通过CDB将结构写入所有等待的功能单元中标记保留站可用公共数据总线:数据+源

(“来源”总线)64位数据+4位功能单元源地址如果与期望的功能单元匹配则写入(产生结果)广播模式Tomsulo算法的基本思想：只要操作数一有效就取至保留栈；要执行的指令将从保留栈中取得操作数；一条指令发射时，取操作数的寄存器被重新命名为该寄存器保留站的名称。

通过指令发射逻辑和保留站的结合实现寄存器重命名。硬件动态调度算法例：执行时间I1LDf2,34(r2)1I2LDf4,45(r3)很长I3MULTDf6,f4,f23I4SUBDf8,f5,f21I5DIVDf4,f2,f84I6ADDDf10,f6,f41124356顺序发射：1(2,1)......2344

35...566调度算法如何提高执行效率？分析指令4与指令3无关，是否可以在指令3等待指令2完成之前，先执行指令4？进一步思考，指令是否可以通过乱序发射（Out-of-orderIssue）或乱序执行（Out-of-orderExecution）提高执行效率？实现方法？对一组指令的数据相关情况进行分析，找出无RAW,WAR,WAW相关冲突指令，送入空闲执行单元（即无结构相关）执行。例：执行时间I1LDf2,34(r2)1I2LDf4,45(r3)很长I3MULTDf6,f4,f23I4SUBDf8,f5,f21I5DIVDf4,f2,f84I6ADDDf10,f6,f41124356乱序发射（执行）并未提高流水线的效率！顺序发射：1(2,1)......2344

35...566乱序发射（执行）：

1(2,1)44....23..35...566乱序发射（乱序执行）问题：什么因素限制了流水线中指令执行的条数？程序中的那些特征限制了流水线中的可执行指令的数目？结论：寄存器的数目是限制流水线中可执行指令条数的关键因素。仅使用少量寄存器通常不能使流水线工作在满负荷状态。

如何解决？原因分析例：执行时间I1LDf2,34(r2)1I2LDf4,45(r3)很长I3MULTDf6,f4,f23I4SUBDf8,f5,f21I5DIVDf4’,f2,f84I6ADDDf10,f6,f4’1124356顺序发射：1(2,1)......2344

35...566乱序发射：

1(2,1)445...235.366流水线的效率提高了！寄存器重命名Tomasulo记分板窗口<=14指令<=5指令结构冒险暂停暂停WAR通过换名避免暂停WAW通过换名避免暂停硬件动态调度算法控制相关控制相关：在判断转移条件之前，就试图决策转移方向(分支指令、跳转指令)为解决控制相关问题，必须能够进行转移预测。如果预测在

编译时进行（或固定）

----控制相关的静态解决技术 执行时进行动态进行

----控制相关的动态解决技术动机：由于转移引起的流水线效率降低极大的影响了处理器的性能。现代处理器中的转移预测机制可以很大程度上（>95%）消除转移引起的性能下降。需要硬件的支持：指令预测单元的基本构件：BHT（BranchHistoryTable)，BTB(BranchTargetBuffer)转移预测JZJZ向后转移90%向前转移50%

统计表明，转移指令中转移发生的概率为60~70%。静态转移预测动态转移预测

动态转移预测就是通过对程序中分支指令过去的行为考察，预测当前转移指令的行为。时间相关性

一条分支指令的历史行为很可能决定着该指令当前的行为。空间相关性

一些分支指令的行为可能是相互关联的。考虑空间相关性问题，例：

if(x[i]<7)y+=1;if(x[i]<5)c-=4;

如果第一个语句的条件不成立，则第二条语句的条件亦不成立。转移预测方法基本思想：基于该分支指令的历史记录----根据该分支指令在最近一次或几次的运行情况(转移成功或失败)，来预测该分支指令的本次运行情况(转移成功或失败)。实现方法：建立一片缓冲区，记录各运行过的分支指令的运行情况(转移成功或失败)。缓冲区如何寻址----根据分支指令地址的低位，究竟 多少位取决于缓冲区大小。缓冲区的内容

----预测位，其长度(多少位)决定能 记录该指令前多少次运行情况。转移预测方法转移指令的执行过程：(1)现场保留。(2)按预测方向取后继指令。(3)得到分支结果后 如果预测成功，继续运行； 如果预测失败，恢复保留的现场，从分支处重新执行；(4)修改预测位。转移预测方法(1)预测位长度为1预测位内容：记录该指令最近一次分支是否成功,

如“1”表示分支成功，“0”表示分

支失败。预测方法：

如果该指令最近一次分支成功则预测 分支成功，反之则预测分支失败。预测位修改：如果实际运行该指令发现分支成功，则 置预测位为“1”，反之为“0”。转移预测方法(2)预测位长度为n预测位内容：为0到2n-1计数器，每次分支结果 出来后，如分支成功则加1，分支失 则减1，计数器值增加到2n-1后不 再增加，减小到0后不再减小。预测方法： 如果计数器值大于或等于最大值的一 半2n-1，预测分支成功，反之预测分 支失败。转移预测方法N为2时的预测位：转移预测方法I-CacheOpcodeOffset+00TargetPCBHTIndexk2k-EntryBHT,2bits/EntryInstructionsBranch?Taken/¬TakenFatchPC转移预测方法实际试验：(1)预测位为2和预测位为n的预测性能差别不大。(2)预测缓冲区大小增加到4096个记录项后预测性能不再明显增加(只用取指令地址的低12位)(3)在预测位为2，预测缓冲区为4096个记录项情况下，预测准确率为82％

99％，即预测失败率为1％

18％。起作用的前提：目标地址的计算要快于分支结果计算。进一步减少分支延迟：分支目标缓冲分支指令无延迟的前提：分支预测成功分支预测和目标地址计算都在IF阶段就能完成。基本思想：设立一个缓冲区(称为分支目标缓冲区，或BTB)，其中存放最近一次运行时分支成功的分支指令的信息(指令地址、分支目标PC)，如果当前指令属于分支目标缓冲(与其中某一条指令的地址相同)，则确定该指令是分支指令，并预测分支成功，从分支目标缓冲直接获得目标PC；反之，则顺序取指令(普通指令或预测分支失败的分支指令)。转移预测方法转移预测方法转移预测方法BTBIndexkFatchPCMatchPCEntryPCEntryValid=ValidTargetI-Cache转移预测方法现代处理器超标量处理器超流水线处理器超标量超流水线处理器三种处理器的比较VLIW处理器超标量处理机：

一个时钟周期内能够同时发射多条指令的处理机称为超标量处理机，它必须有两条或两条以上能够同时工作的指令流水线。超标量处理机典型结构：

多条指令流水线、多个功能部件。

先进的超标量处理机有：定点处理部件CPU，浮点处理部件FPU，图形加速部件GPU，大量的通用寄存器，两个一级高速Cache，标量处理机的指令级并行度大于1。超标量处理器－定义和典型结构Motorola公司的MC88110：10个操作部件：整数（2）、位操作、浮点加、浮点乘、浮点除、图形（2）、Load/Store和指令分配转移部件。两个寄存器堆：整数部件通用寄存器堆，32个32位寄存器；浮点部件扩展寄存器堆，32个80位寄存器。每个寄存器堆有8个端口，分别与8条内部总线相连接，有一个缓冲深度为4的先行读数栈和一个缓冲深度为3的后行写数栈。超标量处理器两个独立的高速Cache：一个数据Cache和一个指令Cache，容量各为8KB，采用两路组相联方式。

一个转移目标指令Cache：在有两路分支时，存放其中一路分支上的指令。超标量处理器整数

部件整数

部件位

操作浮点加乘法

部件除法

部件图形

部件图形

部件内部总线读数存

数部件通用寄

存器堆扩展寄

存器堆目标

指令指令分配

转移部件数据Cache(8KB)指令Cache(8KB)系统总线32位地址总线32位数据总线超标量处理器－MC88110的结构超标量处理器－单发射和多发射单发射处理器：每个周期只取一条指令、只译码一条指令，只执行一条指令，只写回一个运算结果；取指部件和译码部件各设置一套；可以只设置一个多功能操作部件，也可以设置多个独立的操作部件；操作部件中可以采用流水线结构，也可以不采用流水线结构；设计目标是每个时钟周期平均执行一条指令，ILP的期望值1。IF时钟

周期指令I1I2I3IDEXWRIFIDEXWRIFIDEXWR123456单发射处理器的指令流水线时空图IF：取指令ID：指令译码EX：执行指令WR：写回结果超标量处理器超标量处理器IFIDFA1FA2FA3MD1MD2MD3ALLS浮点加法部件乘除法部件定点ALU部件取数存数部件WR来自指

令Cache通用寄存器后行写数栈由4个操作部件组成的单发射处理器多发射处理器：每个周期同时取多条指令、同时译码多条指令，同时执行多条指令，同时写回多个运算结果；需要多个取指令部件，多个指令译码部件和多个写结果部件设置多个指令执行部件，复杂的指令执行部件一般采用流水线结构设计目标是每个时钟周期平均执行多条指令，ILP的期望值大于1超标量处理器多发射处理器的指令流水线时空图IF时钟

周期指令I1I2I3IDEXWR123456I4I5I6IFIDEXWRI7I8I9IFIDEXWRIFIDEXWRIFIDEXWRIFIDEXWRIFIDEXWRIFIDEXWRIFIDEXWR超标量处理器超标量处理器IFIDFA1FA2FA3MD1MD2MD3ALLS浮点加法部件乘除法部件定点ALU部件取数存数部件WRIFIDWR先行指令窗口：

能够从指令Cache中预取多条指令，能够对窗口内的指令进行数据相关性分析和功能部件冲突的检测。窗口的大小：一般为2至8条指令，采用目前的指令调度技术，每个周期发射2至4条指令比较合理。例如：

Intel公司的i860、i960、Pentium处理机，Motolora公司的MC88110处理机，IBM公司的Power6000处理机等每个周期都发射两条指令；TI公司生产的SuperSPARC处理机以及Intel的PentiumIII处理机等每个周期发射三条指令。操作部件的个数多于每个周期发射的指令条数。4个至16个操作部件超标量处理机的指令级并行度：1＜ILP＜m；m为每个周期发射的指令条数。超标量处理器超标量处理器IFIDFA1FA2FA3MD1MD2MD3ALLS浮点加法部件乘除法部件定点ALU部件取数存数部件WRIFIDWRIFID先行指

令窗口两种定义：

一个周期内能够分时发射多条指令的处理机称为超流水线处理器。

指令流水线有8个或更多功能段的流水线处理机称为超流水线处理器。提高处理机性能的不同方法：

超标量处理器是通过增加硬件资源为代价来换取处理器性能。超流水线处理器则通过各硬件部件充分重叠工作来提高处理器性能。两种不同并行性：

超标量处理器采用的是空间并行性。超流水线处理器采用的是时间并行性。超流水线处理器指令执行时序每隔1/n个时钟周期发射一条指令，流水线周期为1/n个时钟周期；在超标量处理机中，流水线的有些功能段还可以进一步细分；例如：ID功能段可以再细分为译码、读第一操作数和读第二操作数三个流水段。也有些功能段不能再细分，如WR功能段一般不再细分。超流水线处理器IF时钟

周期指令I1I2I3IDEXWR123456I4I5I6IFIDEXWRI7I8I9IFIDEXWRIFIDEXWRIFIDEXWRIFIDEXWRIFIDEXWRIFIDEXWRIFIDEXWR每个时钟周期分时发送3条指令的超流水线超流水线处理器典型处理机结构：MIPSR4000处理机每个时钟周期包含两个流水段，是一种很标准的超流水线处理机结构。指令流水线有8个流水段有两个Cache，指令Cache和数据Cache的容量各8KB，每个时钟周期可以访问Cache两次，因此在一个时钟周期内可以从指令Cache中读出两条指令，从数据Cache中读出或写入两个数据。主要运算部件有整数部件和浮点部件。超流水线处理器超流水线处理器指令CacheIF：取第一条指令 IS：取第二条指令

RF：读寄存器堆，指令译码

EX：执行指令 DF：取第一个数据

DS：取第二个数据 TC：数据标志

校验；WB：写回结果指令

译码读寄

存器堆ALU数据Cache标志检验寄存器堆IFISRFEXDFDSWBTCMIPSR4000处理机的流水线操作超流水线处理器IF流水线周期当前CPU周期ISRFEXDFDSTCWBIFISRFEXDFDSTCWBIFISRFEXDFDSTCWBIFISRFEXDFDSTCWBIFISRFEXDFDSTCWBIFISRFEXDFDSTCWBIFISRFEXDFDSTCWBIFISRFEXDFDSTCWB主时

钟

周期MIPSR4000正常指令流水线工作时序超