第五章 重叠、流水和现代处理器技术北京航空航天大学计算机学院2005年4月主要内容：基本问题流水线技术向量流水技术现代处理器技术基本问题基本问题如何提高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 1、简单流水线的连接图表示、简单流水线的连接图表示、简单流水线的连接图表示、简单流水线的连接图表示流水线的每一个阶段称为流水步、流水步骤、流水段、流水线阶段、流水功能段、功能段、流水级、流水节拍等。一个流水阶段与另一个流水阶段相连形成流水线。指令从流水线一端进入，经过流水线的处理，从另一端流出。有些复杂指令在执行阶段也采用流水线方式工作，称为操作流水线。取指令译码执行保存结果t1t2t3t42 2、一种指令流水线、一种指令流水线、一种指令流水线、一种指令流水线一般4至12个流水段，等于及大于8个流水段的称为超流水线处理机。取指形成操作数地址译码取操作数执行保存结果流水线的表示方法流水线的表示方法3 3、流水线的时空图、流水线的时空图、流水线的时空图、流水线的时空图采用“时空图”表示流水线的工作过程。一条简单流水线的时空图：分析k分析k+1 分析k+2 分析k+3执行k执行k+1 执行k+2 执行k+3时间空间0t1t2t3t4t5流水线的表示方法流水线的表示方法一个浮点加法器流水线的时空图(由求阶差、对阶、尾数加和规格化4个流水段组成)：ED1时间空间0t1t2t3t4t5ED2 ED3 ED4 ED5EA1 EA2 EA3 EA4 EA5MA1 MA2 MA3 MA4 MA5NL1 NL2 NL3 NL4 NL5t6t7t8NL：规格化MA：尾数加EA：对阶ED：求阶差流水线的表示方法流水线的表示方法在流水线的每一个功能部件的后面都要有一个缓冲器，称为锁存器、闸门寄存器等，它的作用是保存本流水段的执行结果。各流水段的时间应尽量相等，否则回引起阻塞、断流等。只有连续提供同类任务才能充分发挥流水线的效率。在流水线的每一个流水线段中都要设置一个流水锁存器。流水线需要有“装入时间”和“排空时间”。只有只有流水线完全充满时，整个流水线的效率才能得到充流水线完全充满时，整个流水线的效率才能得到充分发挥。分发挥。流水线的主要特点流水线的主要特点衡量流水线性能的主要指标有：吞吐率、加速比和效率1 1 1 1、吞吐率（、吞吐率（、吞吐率（、吞吐率（Though PutThough PutThough PutThough Put）求流水线吞吐率的最基本公式： TPTP = = n n / / T Tkn为任务数,Tk为完成n个任务所用时间各段执行时间相等，输入连续任务情况下完成n个连续任务需要的总时间为：T Tk= (= (k k+ +n n-1) -1) D D D Dt t k为流水线的段数，D t为时钟周期线性流水线的性能分析线性流水线的性能分析1时间空间S123 n-1 nS2S3S4123 n-1 n123 n-1 n123 n-1 nkDt(n-1)DtnDt(k-1)DtT线性流水线的性能分析线性流水线的性能分析吞吐率：最大吞吐率为：各段执行时间不相等、输入连续任务情况下：吞吐率为：最大吞吐率为：线性流水线的性能分析线性流水线的性能分析流水线各段执行时间不相等的解决办法S1输入Dt1=DtS2Dt2=3DtS3Dt3=DtS4Dt4=Dt输出1时间空间S1S2S3S4SDti(n-1)Dt2Tk23n123n123n123n线性流水线的性能分析线性流水线的性能分析一是将“瓶颈”流水段细分(如果可分的话)：二是将“瓶颈”流水段重复设置：S1输入输出tS2-1tS2-2tS2-3tS3tS4tS2(3t)S1输入输出t1=tS2-1S2-1S2-1S3S4t3=tt4=tt2=3t线性流水线的性能分析线性流水线的性能分析流水段重复设置的流水线1时间空间2 3nS1S2-14 5 614-2 -1n-225n-136n1 2 3n4 5 6-2 -11 2 3n4 5 6-2 -1S2-2S2-3S3S4线性流水线的性能分析线性流水线的性能分析2 2、加速比（、加速比（SpeedupSpeedup）计算流水线加速比的基本公式：S=顺序执行时间T0/流水线执行时间Tk各段执行时间相等，输入连续任务情况下加速比为：最大加速比为：各段执行时间不等，输入连续任务情况下实际加速比为：线性流水线的性能分析线性流水线的性能分析K=6K=10任务个数加速比10246811 248 16 32 64 128线性流水线的性能分析线性流水线的性能分析3 3 3 3、效率（、效率（、效率（、效率（EfficiencyEfficiencyEfficiencyEfficiency）计算流水线效率的一般公式：各流水段执行时间相等，输入n个连续任务流水线的效率为：流水线的最高效率为：线性流水线的性能分析线性流水线的性能分析1时间空间S123 n-1 nS2S3S4123 n-1 n123 n-1 n123 n-1 nkDt(n-1)DtnDt(k-1)DtT线性流水线的性能分析线性流水线的性能分析各流水段执行时间不等，输入n个连续任务流水线的效率为：线性流水线的性能分析线性流水线的性能分析S1输入Dt1=DtS2Dt2=3DtS3Dt3=DtS4Dt4=Dt输出1时间空间S1S2S3S4SDti(n-1)Dt2Tk23n123n123n123n线性流水线的性能分析线性流水线的性能分析流水线的吞吐率、加速比与效率的关系：因为因此：E=TPt，S=kE线性流水线的性能分析线性流水线的性能分析4 4 4 4、流水线性能分析举例、流水线性能分析举例、流水线性能分析举例、流水线性能分析举例对于单功能线性流水线，输入连续任务的情况，通过上面给出的公式很容易计算出流水线的吞吐率、加速比和效率。例5.2：用一条4段浮点加法器流水线求8个浮点数的和：ZABCDEFGH线性流水线的性能分析线性流水线的性能分析解：Z=(A+B)+(C+D)+(E+F)+(G+H)1时间空间2 3求阶差45671 2 3 45671 2 3 45671 2 3 4567对阶尾数加规格化加数 A C E GA+BE+FB D F HC+DG+HA+B+C+DE+F+G+H结果A+BC+DE+FG+HA+B+C+DE+F+G+HZ Z线性流水线的性能分析线性流水线的性能分析7个浮点加法共用了15个时钟周期。流水线的吞吐率为：流水线的加速比为：流水线的效率为：线性流水线的性能分析线性流水线的性能分析什么是非线性流水线？什么是非线性流水线？如果存在反馈回路，当一个任务在流水线中流过时，在同一个流水段中可能要经过多次。不能每一个时钟周期向流水线输入一个新任务。这样的流水线就是非线性流水线。 非线性流水线的调度问题就是要解决要隔多少个时钟周期向流水线输入一个新任务才能使流水线 的各个流水段都不发生冲突。 表示一个非线性流水线需要用到连接图和预约表。非线性流水线技术非线性流水线技术S1S2S3S4输出输入反馈线时间流水段1234567S1XXXS2XS3XXS4X非线性流水线1的连接图非线性流水线的预约表S1S2S3S4输出输入反馈线时间流水段1234567S1XXXS2XXS3XXS4X非线性流水线2的连接图非线性流水线的预约表预约表横坐标表示流水线的时钟周期，纵坐标表示流水线的各个流水段，中间有“X”表示该流水段在这一个时钟周期处于工作状态，空白表示该流水段在这一个时钟周期不工作。一行中可以有多个“X”，表示一个任务在不同时钟周期重复使用了同一流水段；一列中有多个“X”表示在同一个时钟周期同时占用了多个流水段。预约表的行数是流水线的段数，预约表的列数是一个任务从进入流水线到流水线中输出所经过的时钟周期数。向一条非线性流水线的输入端连续输入两个任务之间的时间间隔称为非线性流水线的启动距离，以时钟周期数表示。非线性流水线技术非线性流水线技术当使用某些启动距离时，将在某些流水段发生冲突，即两个或两个以上任务同时争用一个流水段。引起非线性流水线流水段冲突的启动距离称为禁启动止距离。不发生冲突的启动距离是一个循环数列。使非线性流水线的任何一个流水段在任何一个时钟周期都不发生冲突的循环数列称为非线性流水线的启动循环。非线性流水线技术非线性流水线技术X3X2X1S4X4X2X3X1X2X1S3X3X4X2X3X1X2X1S2X2X3X4X1X2X3X1X2X1S11110987654321时间流水段启动距离为3的流水线冲突情况两个任务争用一个流水段S1三个任务争用一个流水段S1启动距离为5的流水线预约表X2X1X1S4X2X2X2X1S3X3X1X1S2X2X1X1X1S11110987654321时间流水段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）时间流水12345678910111213141516S1X1X2X1X3X2X4X3S2X1X2X1X2X3X4X3S3X1X1X2X2X3X3X4S4X1X2X3X4最小启动循环为（3，5）的流水线工作状态非线性流水线技术非线性流水线技术时间流水段123456789101112131415S1X1X2X1X2X3X4X3S2X1X2X1X2X3X4X3X4S3X1X2X1X2X3X4X3X4S4X1X2X3X4最小启动循环为（1，7）的流水线工作状态非线性流水线技术非线性流水线技术时间流水段123456789101112131415S1X1X2X1X3X2S2X1X1X2X2X3S3X1X1X2X2X3X3S4X1X2X3恒定启动循环（5）的流水线工作状态启动周期重复启动周期非线性流水线技术非线性流水线技术主要内容：基本问题流水线技术向量流水技术现代处理器技术向量流水技术向量流水技术向量处理的特点向量处理机的基本结构向量处理的方法向量处理的关键技术向量流水处理的主要特点向量流水处理的主要特点1、向量流水处理的主要特点 (1) 各个元素的操作一般相同且数据相互独立，不存在相关。非常适合于流水处理； (2) 一条向量指令相当于一个标量循环,可降低对指令访问带宽的要求； (3) 一般采用多体交叉存储，支持跨步长度访问向量处理机的基本概念向量处理机的基本概念 具有向量数据表示和向量指令系统的处理机称为向量处具有向量数据表示和向量指令系统的处理机称为向量处理机。理机。q向量处理机是解决数值计算问题的一种高性能计算机结构。q向量处理机一般都采用流水线结构，往往有多条流水线并行工作。q向量处理机通常属大型或巨型机，也可以用微机加一台向量协处理器组成。q一般向量计算机中包括有一台高性能标量处理机。q必须把要解决的问题转化为向量运算，向量处理机才能充分发挥作用。一个典型向量求解问题: Y = a*X + Y 其中X和Y为向量, 初始值存放在存储器中, a为标量。通常, 根据这一求解表达式是单精度还是双精度操作, 分别称为SAXPY(Single-precision AX plus Y)或DAXPY循环, 表示是单精度或双精度的A乘X后再加Y。若用向量机来完成同样操作, 则有: LD F0,a ;标量a装入F0 LV V1,Rx ;装入向量X, LV为向量取指令 MULTV V2,F0,V1 ;向量X与标量a相乘 LV V3,Ry ;装入向量Y ADDV V4,V2,V3 ;向量加aX+Y SV Ry,V4 ;存结果向量, SV为向量存指令 向量机只需执行6条指令, 从而可大大降低对指令带宽要求向量处理机的基本结构向量处理机的基本结构 向量处理机的基本结构形式 按向量操作对象及结果主要存放方式分类： 1）存储器存储器工作方式向量机利用多个独立的存储器模块并行工作。 2）寄存器寄存器工作方式向量机主要利用向量寄存器。存储器存储器结构存储器存储器结构采用多个存储体交叉和并行访问来提高存储器速度；操作数缓冲栈和写结果缓冲栈主要用于解决访问存储器冲突；主要优缺点：硬件结构简单，造价低。速度相对比较低。早期的向量处理多采用这种存储器-存储器结构。主主存存储储器器操作数操作数缓冲栈缓冲栈流水线流水线运算运算部件部件写结果写结果缓冲栈缓冲栈寄存器寄存器结构（寄存器寄存器结构（Cray1）寄存器寄存器结构寄存器寄存器结构把存储器-存储器结构中的缓冲栈改为向量寄存器，运算部件需要的操作数从向量寄存器中读取，运算的中间结果也写到向量寄存器中。向量寄存器与标量寄存器的主要差别是：一个向量寄存器能够保存一个向量，例如：64个64位寄存器。采用寄存器-寄存器结构的主要优点：降低主存储器的流量。例如：寄存器-寄存器结构的CRAY-1与存储器-存储器结构的STAR-100比较，运算速度高3倍多（时钟周期为40：12.5），主存储器流量低2.5倍。1976年，CRAY公司推出CRAY-1向量机，开始了向量机的蓬勃发展，其峰值速度为0.1Gflops。Cray 11985年，CRAY-2，1Gflops1990年,SX-3,22Gflops1991年，Cray-YMP-C90,16GflopsCray 2Cray XMP/4CRAYY-MP816系统结构1991年多向量处理器时间并行+空间并行256交叉存储16MB1GB大量使用寄存器64位浮点/定点1983年12月,银河-I巨型计算机由国防科技大学计算机研究所研制成功。银河-II并行巨型计算机由国防科技大学计算机研究所于1992年11月研制成功。银河银河1银河银河2向量处理方法向量处理方法向量处理方式有三种类型：1横向处理方式：横向处理方式：向量计算是按行的方式从左至右横向地进行。也称水平处理方式，横向加工方式等。2纵向处理方式：纵向处理方式：向量计算是按列的方式自上而下纵向地进行。也称垂直处理方式，纵向加工方式等。3纵横处理方式：纵横处理方式：横向处理和纵向处理相结合的方式。也称分组处理方式，纵横向加工方式等。以一个简单的C语言编写的程序为例，说明向量的三种处理方式的工作原理。for(i=1；i=N；i+)yi=ai(bi+ci);逐个分量进行处理：假设中间结果为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个分量, 先进行相加t1b1+c1, 其中t1为暂存单元, 然后相乘y1t1a1。横向处理方式横向处理方式横向处理方式横向处理方式存在两个问题：在计算向量的每个分量时，都发生写读数据相关。流水线效率低。如果采用多功能流水线，必须频繁进行流水线切换。结论：这种加工方式不适合于向量流水处理。纵向处理方式纵向处理方式 先纵向加工所有B和C向量中元素对的相加操作, 中间结果暂存到t1tN中, 然后再纵向加工所有对应元素的乘法操作。 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+C Y=TA纵向处理方式纵向处理方式特点：流水线功能的切换只需一次。可获得较高的吞吐率。 数据相关不影响流水线连续工作，可采用向量链接技术。结论：这种处理方式适用于向量处理机。 纵横处理方式纵横处理方式纵横向加工(或称为分组加工) 以寄存器寄存器方式工作的向量机都采用这种加工方式。因为向量寄存器的长度有限(如CRAY-1的长度为64)。当向量长度超过向量寄存器可表示的最大限度n时, 就不得不分组加以处理。假设向量长度为N, 则有N=kn+r, 其中nN, rn,n、k、r均为正整数, k为组数, r为余数(余下的部分也作为一组处理)。它的加工方式是: 组内纵向加工, 组间为横向加工。第一组计算: t1n=b1n+c1n y1n=a1n+t1n再算第二组: tn+12n=bn+12n+cn+12n yn+12n=an+12n+tn+12n 向量处理的关键技术向量处理的关键技术向量与标量性能的平衡向量与标量性能的平衡向量链接技术向量链接技术向量循环开采技术向量循环开采技术向量与标量性能的平衡向量与标量性能的平衡实际的应用问题中通常既有向量计算又有标量计算，而且两类计算有一定的比例。向量平衡点(vector balance point)： 为了使向量硬件设备和标量硬件设备的利用率相等，一个程序中为了使向量硬件设备和标量硬件设备的利用率相等，一个程序中向量代码所占的百分比。向量代码所占的百分比。关键问题是：向量硬件和标量硬件都能充分利用，都不空闲。向量处理机的向量平衡点必须与用户程序的向量化程度相匹配。向量与标量性能的平衡向量与标量性能的平衡机器型号CrayCrayISISCrayCray2S2SCrayCrayX-MPX-MP CrayCrayY-MPY-MPhitachihitachiS820S820 NECNECSX2SX2 FujitsuFujitsuVP4000VP4000向量性能向量性能(Mflops)85.0 151.5 143.3 201.6 737.3 424.2 207.1标量性能标量性能(Mflops)9.811.213.117.017.89.56.6向量平衡向量平衡点点0.90 0.90 0.93 0.93 0.92 0.92 0.92 0.92 0.98 0.98 0.98 0.98 0.97 0.97 几种超级计算机向量和标量的性能向量链接技术向量链接技术向量运算中的相关和冲突向量运算中的相关和冲突向量运算中的数据相关和功能部件冲突主要有： 写读数据相关； 读读数据相关，或向量寄存器冲突； 运算部件冲突。V0V1V2 V0V1V2V3V4 V5 V3V0 V4(a)不相关的指令 (b)写读数据相关V0V1V2 V0V1V2V3V4V5 V3V1 V4(c)功能部件冲突 (d)读读数据相关向量链接技术向量链接技术 利用向量指令间存在的先写后读的数据相关性来加快向量指令序列执行速度的技术称为链接技术。具体的说，结果寄存器可能成为后继指令的操作数寄存器，两条有数据相关的向量指令并行执行。 例如：ADDV V1,V2,V3 ;V1V2+ V3 MULTV V4,V1,V5 ;V4V1V5 分析：这两条指令间对V1向量寄存器存在先写后读相关, 通常必须等加法指令做完后才可开始乘法指令, 但如果使向量寄存器(例中的V1)在同一时钟周期内, 既接收一个功能部件送来的运算结果, 又可把这一结果作为下一个向量指令运算所需的源操作数送给另一个功能部件, 那就可使这两个部件链接起来进行操作。当链接进入充分流水操作状态后, 在一个时钟周期内就可同时获取两个操作结果。 向量链接技术向量链接技术以CRAY-1为例,设有如下向量运算: D = A(B+C) 假设向量长度64, 且B和C已由存储器取至V0和V1, 则下面3条向量指令就可完成上述运算: LD V3,A ;V3a ADDV V2,V0,V1 ;V2V0+V1 MULTV V4,V2,V3 ;V4V2V3向量链接技术向量链接技术 LD V3,A ;V3a ADDV V2,V0,V1 ;V2V0+V1 MULTV V4,V2,V3 ;V4V2xV3情况一：若这三条指令全部用串行方法则所需时间为: (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向量链接技术向量链接技术链接的条件：1链接两条或多条指令存在先写后读相关2只有当前一指令的第一个结果分量送入结果向量寄存器的那一个时钟周期方可链接3当一条向量指令的两个源操作数分别是两条先行指令的结果寄存器时, 要求先行的两条指令产生运算结果的时间必须相等, 即要求有关功能部件的延迟时间相等4链接的两条向量指令的向量长度必须相等5针对不同的向量机, 可能对链接还有其他特殊限制。如CRAY-1中, 允许自存储器取数操作参与链接, 但不允许向存储器写数操作实现链接, 因为CRAY-1并不提供这种链接功能。 向量循环开采技术向量循环开采技术 当向量的长度大于向量寄存器的长度时，必须把长向量分成长度固定的段，采用循环结构处理这个长向量，这种技术称为向量循环开采技术，也称为向量分段开采技术。例如：A和B为长度N的向量。for(i=1;i=N;i+)ai=5*b(i)+c;向量循环开采技术向量循环开采技术当N为64或更小时，产生A数组的7条指令序列是：1：S15.0在标量寄存器内设置常数2：S2C 将常数C装入标量寄存器3：VLN 在VL寄存器内设置向量长度4：V0B 将B向量读入向量寄存器5：V1S1 V0 B数组的每个分量和常数相乘6：V2S2V1 C和5B(i)相加7：AV2将结果向量存入A数组 第4、5、6、7条指令可以采用向量链接执行。当N超过64时，就需要采用向量循环。向量循环开采技术向量循环开采技术 向量的分段开采： low=1 VL=(N mod MVL) *找出零头长度值 do 20 j=0, (N/MVL) *外循环 do 10 i=low, low+VL-1 *以长度VL操作 4：V0B 5：V1S1 V0 6：V2S2V1 主要操作 7：AV2 10 continue low=low+VL *下一向量的开始 VL=MVL *将长度值恢复成MVL 20 contine 经分段处理后, 第一段长度为n mod MVL, 而以后各段的长度均为MVL（向量寄存器的长度）。主要内容：基本问题流水线技术向量流水技术现代处理器技术不能回避的问题不能回避的问题SoEasy?No!进一步的思考：采用流水线技术所带来的问题。取指令译码执行保存结果t1t2t3t4I: add r1,r2,r3J: sub r4,r1,r3研究相关性，不但可作为是否可指令调度的依据，而且可了解程序固有的并行性以及可以获得的并行性。相关相关 意味指令的运行、结果产生的顺序有要求，意味指令的并行运行和改变顺序可能会产生问题，是否意味指令的流水线运行一定会产生停顿。流水线的主要障碍流水线的主要障碍: 相关相关(Hazard)流水线3类相关结构相关:硬件不能支持两条指令同时访问同一个资源twodogsfightingforthesamebone数据相关:指令依赖于前面尚在流水线中的指令的执行结果控制相关:在判断转移条件之前，就试图决策转移方向(分支指令、跳转指令)解决相关性问题，提高处理器执行效率，是推解决相关性问题，提高处理器执行效率，是推动处理器新技术产生的动力源泉。动处理器新技术产生的动力源泉。流水线的主要障碍流水线的主要障碍: 相关相关(Hazard)结构相关单口存储器结构相关单口存储器指令和数据共用同一个存储器存储器为单口存储器冲突发生条件Instr1存储器访问指令读写存储器Instr2取指令时间时间(时钟周期时钟周期)LoadInstr 1Instr 2Instr 3Instr 4RegALUDMemIfetchRegRegALUDMemIfetchRegRegALUDMemIfetchRegCycle 1 Cycle 2 Cycle 3 Cycle 4Cycle 6 Cycle 7Cycle 5存储器冲突存储器冲突DMemRegALUDMemRegIfetch结构相关单口存储器结构相关单口存储器指指令令执执行行次次序序时间时间(时钟周期时钟周期)LoadInstr 1Instr 2StallStallInstr 3RegALUDMemIfetchRegRegALUDMemIfetchRegRegALUDMemIfetchRegCycle 1 Cycle 2 Cycle 3 Cycle 4Cycle 6 Cycle 7Cycle 5RegALUDMemIfetchReg气泡气泡气泡气泡气泡气泡气泡气泡气泡气泡结构相关解决方案之一：气泡结构相关解决方案之一：气泡消除结构相关消除结构相关原因：资源争用方法1:等待第一步：检测第二步：插入等待(空操作/气泡)方法2:投入更多的硬件资源双存储器(“HarvardArchitecture”)多端口存储器（寄存器堆）三类数据相关三类数据相关ReadAfterWrite(RAW)先写后读(写未完成，读即发出)InstrJ在InstrI完成写之前读起因：基于变量的通讯RAW相关是程序相关性中最本质的相关性之一。I: add r1,r2,r3J: sub r4,r1,r3WriteAfterRead(WAR)先读后写InstrJ在InstrI完成读之前进行写操作反相关起因：r1的重用I: sub r4,r1,r3 J: add r1,r2,r3K: mul r6,r1,r7三类数据相关三类数据相关WriteAfterWrite(WAW)写后写InstrJ在InstrI完成写之前进行写操作输出相关起因是r1的重用I: sub r1,r4,r3 J: add r1,r2,r3K: mul r6,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相关的解决策略相关的解决策略流水线旁路流水线旁路时间时间 (时钟周期时钟周期)指指令令执执行行次次序序add r1,r2,r3sub r4,r1,r3and r6,r1,r7or r8,r1,r9xor r10,r1,r11RegALUDMemIfetchRegRegALUDMemIfetchRegRegALUDMemIfetchRegRegALUDMemIfetchRegRegALUDMemIfetchRegRegALUDMemIfetchRegRAW相关的解决策略相关的解决策略流水线旁路流水线旁路时间时间 (时钟周期时钟周期)指指令令执执行行次次序序ld r1, 4(r2)sub r4,r1,r6and r6,r1,r7or r8,r1,r9RAW相关仍然存在相关仍然存在Load指令指令RegALUDMemIfetchRegRegALUDMemIfetchRegRegALUDMemIfetchRegRegALUDMemIfetchReg旁路未能解决所有问题流水线互锁解决流水线互锁解决Load引发的引发的RAW相关相关时间时间 (时钟周期时钟周期)or r8,r1,r9指指令令执执行行次次序序ld r1, 4(r2)sub r4,r1,r6and r6,r1,r7RegALUDMemIfetchRegRegIfetchALUDMemRegBubbleIfetchALUDMemRegBubbleRegIfetchALUDMemBubbleRegWAR和和WAW相关相关WAR：WAW：这两类相关由寄存器重用引起；指令顺序不能改变；在单功能流水线中不可能发生。I: sub r4,r1,r3 J: add r1,r2,r3K: mul r6,r1,r7I: sub r1,r4,r3 J: add r1,r2,r3K: mul r6,r1,r7多功能流水线多功能流水线IFIDIssueGPRsFPRsALUFaddFmulFdivWBI: Fdiv r4,r1,r3 J: add r1,r2,r3K: mul r6,r1,r7I: Fmul r1,r4,r3 J: add r1,r2,r3K: mul r6,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,RkFj,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丛主存来丛主存来保留站保留站Common Data Bus (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).234435.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).234435.566乱序发射（执行）：1(2,1)44.23.35.566乱序发射（乱序执行）乱序发射（乱序执行）问题：什么因素限制了流水线中指令执行的条数？程序中的那些特征限制了流水线中的可执行指令的数目？结论：寄存器的数目是限制流水线中可执行指令条数的关键因素。仅使用少量寄存器通常不能使流水线工作在满负荷状态。如何解决？原因分析原因分析例：执行时间I1LDf2,34(r2)1I2LDf4,45(r3)很长I3MULTDf6,f4,f23I4SUBDf8,f5,f21I5DIVDf4,f2,f84I6ADDDf10,f6,f41124356顺序发射：1(2,1).234435.566乱序发射：1(2,1)445.235.366流水线的效率提高了！寄存器重命名寄存器重命名寄存器重命名寄存器重命名Tomasulo记分板窗口=14指令95%）消除转移引起的性能下降。需要硬件的支持： 指令预测单元的基本构件：BHT（BranchHistoryTable)，BTB(BranchTargetBuffer)转移预测转移预测JZJZ向后转移90%向前转移50%统计表明，转移指令中转移发生的概率为6070%。静态转移预测静态转移预测动态转移预测动态转移预测动态转移预测就是通过对程序中分支指令过去的行为考察，预测当前转移指令的行为。时间相关性一条分支指令的历史行为很可能决定着该指令当前的行为。空间相关性一些分支指令的行为可能是相互关联的。考虑空间相关性问题，例：if(xi7)y+=1;if(xi5)c-=4;如果第一个语句的条件不成立，则第二条语句的条件亦不成立。转移预测方法转移预测方法基本思想：基于该分支指令的历史记录-根据该分支指令在最近一次或几次的运行情况(转移成功或失败)，来预测该分支指令的本次运行情况(转移成功或失败)。实现方法：建立一片缓冲区，记录各运行过的分支指令的运行情况(转移成功或失败)。 缓冲区如何寻址缓冲区如何寻址缓冲区如何寻址缓冲区如何寻址-根据分支指令地址的低位，究竟多少位取决于缓冲区大小。 缓冲区的内容缓冲区的内容缓冲区的内容缓冲区的内容-预测位，其长度(多少位)决定能记录该指令前多少次运行情况。转移预测方法转移预测方法转移指令的执行过程：(1)现场保留。(2)按预测方向取后继指令。(3)得到分支结果后如果预测成功，继续运行；如果预测失败，恢复保留的现场，从分支处重新执行；(4)修改预测位。转移预测方法转移预测方法(1)(1)预测位长度为预测位长度为1 1预测位内容：预测位内容：记录该指令最近一次分支是否成功,如 “1”表示分支成功， “0”表示分 支失败。预测方法：预测方法：如果该指令最近一次分支成功则预测分支成功，反之则预测分支失败。预测位修改：预测位修改：如果实际运行该指令发现分支成功，则置预测位为“1”，反之为“0”。转移预测方法转移预测方法(2)(2)预测位长度为预测位长度为n 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个记录项情况下，预测准确率为8299，即预测失败率为118。起作用的前提：目标地址的计算要快于分支结果计算。进一步减少分支延迟：分支目标缓冲进一步减少分支延迟：分支目标缓冲分支指令无延迟的前提：分支指令无延迟的前提：分支预测成功分支预测和目标地址计算都在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)指令指令Cache (8KB)Cache (8KB)系统总线系统总线3232位地址总线位地址总线3232位数据总线位数据总线超标量处理器超标量处理器MC88110MC88110的结构的结构超标量处理器单发射和多发射超标量处理器单发射和多发射单发射处理器：n每个周期只取一条指令、只译码一条指令，只执行一条指令，只写回一个运算结果；n取指部件和译码部件各设置一套；n可以只设置一个多功能操作部件，也可以设置多个独立的操作部件；n操作部件中可以采用流水线结构，也可以不采用流水线结构；n设计目标是每个时钟周期平均执行一条指令，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个操作部件超标量处理机的指令级并行度：1ILPm；m为每个周期发射的指令条数。超标量处理器超标量处理器超标量处理器超标量处理器IFIDFA1FA2FA3MD1MD2MD3ALLS浮点加法部件乘除法部件定点ALU部件取数存数部件WRIFIDWRIFID先行指令窗口两种定义：一个周期内能够分时发射多条指令的处理机称为超流水线处理器。指令流水线有8个或更多功能段的流水线处理机称为超流水线处理器。提高处理机性能的不同方法：超标量处理器是通过增加硬件资源为代价来换取处理器性能。超流水线处理器则通过各硬件部件充分重叠工作来提高处理器性能。两种不同并行性：超标量处理器采用的是空间并行性。超流水线处理器采用的是时间并行性。超流水线处理器超流水线处理器n指令执行时序每隔1/n个时钟周期发射一条指令，流水线周期为1/n个时钟周期；在超标量处理机中，流水线的有些功能段还可以进一步细分；例如：ID功能段可以再细分为译码、读第一操作数和读第二操作数三个流水段。也有些功能段不能再细分，如WR功能段一般不再细分。超流水线处理器超流水线处理器IF时钟周期指令I1I2I3IDEXWR123456I4I5I6IFIDEXWRI7I8I9IFIDEXWRIFIDEXWRIFIDEXWRIFIDEXWRIFIDEXWRIFIDEXWRIFIDEXWR每个时钟周期分时发送3条指令的超流水线超流水线处理器超流水线处理器n典型处理机结构：MIPSR4000处理机每个时钟周期包含两个流水段，是一种很标准的超流水线处理机结构。指令流水线有8个流水段有两个Cache，指令Cache和数据Cache的容量各8KB，每个时钟周期可以访问Cache两次，因此在一个时钟周期内可以从指令Cache中读出两条指令，从数据Cache中读出或写入两个数据。主要运算部件有整数部件和浮点部件。超流水线处理器超流水线处理器超流水线处理器超流水线处理器指令CacheIF：取第一条指令IS：取第二条指令RF：读寄存器堆，指令译码EX：执行指令DF：取第一个数据DS：取第二个数据TC：数据标志校验；WB：写回结果指令译码读寄存器堆ALU数据Cache标志检验寄存器堆IFISRFEXDFDSWBTCMIPS R4000处理机的流水线操作处理机的流水线操作超流水线处理器超流水线处理器IF流水线周期当前CPU周期ISRFEX DFDSTC WBIFISRFEX DFDSTC WBIFISRFEX DFDSTC WBIFISRFEX DFDSTC WBIFISRFEX DFDSTC WBIFISRFEX DFDSTC WBIFISRFEX DFDSTC WBIFISRFEX DFDSTC WB主时钟周期MIPS R4000正常指令流水线工作时序正常指令流水线工作时序超流水线处理器超流水线处理器如果在LOAD指令之后的两条指令中，任何一条指令要在它的EX流水级使用这个数据，则指令流水线要暂停一个时钟周期。采用顺序发射方式。暂停IFISRFEXDFDSTCWBISRFEXDFDSTCWBRFEXDFDSTCWBEXDFDSTCWBEXDFDSTCWBDFDSTCWBIFISRFI1I2I3I4I5I6运行运行Load指令使用Load数据超流水线处理器超流水线处理器n超流水线处理器性能指令级并行度为(1,n)的超流水线处理机，执行N条指令所的时间为：超流水线处理机相对于单流水线普通标量处理机的加速比为：超流水线处理器超流水线处理器即：超流水线处理机的加速比的最大值为：超流水线处理器超流水线处理器将超标量与超流水线技术结合在一起，就成为超标量超流水线处理器指令执行时序：超标量超流水线处理器在一个时钟周期内分时发射指令n次，每次同时发射指令m条，每个时钟周期总共发射指令m n条。超标量超流水线处理器超标量超流水线处理器超标量超流水线处理器超标量超流水线处理器IF时钟周期指令I1I2I3IDEXWR12345I4I5I6I7I8I9IFIDEXWRIFIDEXWRIFIDEXWRIFIDEXWRIFIDEXWRIFIDEXWRIFIDEXWRIFIDEXWRIFIDEXWRIFIDEXWRIFIDEXWRI10I11I12每时钟周期发射3次,每次3条指令n典型处理机结构：DEC公司的Alpha处理机采用超标量超流水线结构。主要由四个功能部件和两个Cache组成：整数部件EBOX、浮点部件FBOX、地址部件ABOX和中央控制部件IBOX。中央控制部件IBOX可以同时从指令Cache中读入两条指令，同时对读入的两条指令进行译码，并且对这两条指令作资源冲突检测，进行数据相关性和控制相关性分析。如果资源和相关性允许，IBOX就把两条指令同时发射给EBOX、ABOX和FBOX三个指令执行部件中的两个。指令流水线采用顺序发射乱序完成的控制方式。在指令Cache中有一个转移历史表，实现条件转移的动态预测。在EBOX内还有多条专用数据通路，可以把运算结果直接送到执行部件。超标量超流水线处理器超标量超流水线处理器nAlpha21064处理机共有三条指令流水线整数操作流水线和访问存储器流水线分为7个流水段，其中，取指令和分析指令为4个流水段，运算2个流水段，写结果1个流水段。浮点操作流水线分为10个流水段，其中，浮点执行部件FBOX的延迟时间为6个流水段。所有指令执行部件EBOX、IBOX、ABOX和FBOX中都设置由专用数据通路。nAlpha21064处理机的三条指令流水线的平均段数为8段，每个时钟周期发射两条指令。因此，因此，Alpha 21064处理机是超标量超流水处理机是超标量超流水线处理机。线处理机。超标量超流水线处理器超标量超流水线处理器超标量超流水线处理器超标量超流水线处理器超标量超流水线处理器超标量超流水线处理器IF取值SWAP交换双发射指令、转移预测I0指令译码I1访问通用寄存器堆，发射校验A1计算周期1，IBOX计算新的PC值A2计算周期2，查指令快表WR写整数寄存器堆，指令Cache命中检测7个流水段的整数操作流水线SWAP1IFI0I1A0A1WR234560超标量超流水线处理器超标量超流水线处理器IF取值SWAP交换双发射指令、转移预测I0指令译码I1访问通用寄存器堆，发射校验ACABOX计算有效数据地址TB查数据快表HM写读数缓冲栈，数据Cache命中/不命中检测7个流水段的访问存储器流水线SWAP1IFI0I1ACTBHM234560超标量超流水线处理器超标量超流水线处理器SWAPIF取值SWAP交换双发射指令、转移预测I0指令译码I1访问通用寄存器堆，发射校验F1-F5浮点计算流水线FWR写回浮点寄存器堆110个流水段的浮点操作流水线IFI0I1F1F2FWR234560F3F4F5789超标量超流水线处理器性能超标量超流水线处理器性能指令级并行度为(m,n)的超标量超流水线处理机，连续执行N条指令所需要的时间为：超标量超流水线处理机相对于单流水线标量处理机的加速比为：在理想情况下，超标量超流水线处理机加速比的最大值为：S(m, n)MAXm n超标量处理机、超流水线处理机和超标量超流水线处理机相对于单流水线普通标量处理机的性能曲线。三种指令级并行处理器性能比较三种指令级并行处理器性能比较0.00.51.01.52.02.512345678相对性能超标量超流水线超标量超流水线指令级并行度从三种指令级并行处理机的性能曲线中，可以得出如下结论：1、三种处理机的性能关系超标量处理机的相对性能最高，其次是超标量超流水线处理机，超流水线处理机的相对性能最低，主要原因如下：(1)超标量处理机在每个时钟周期的一开始就同时发射多条指令，而超流水线处理机则要把一个时钟周期平均分成多个流水线周期，每个流水线周期发射一条指令；因此，超流水线处理机的启动延迟比超标量处理机大。三种指令级并行处理器性能比较三种指令级并行处理器性能比较(2)条件转移造成的损失，超流水线处理机要比超标量处理机大。(3)在指令执行过程中的每一个功能段，超标量处理机都重复设置有多个相同的指令执行部件，而超流水线处理机只是把同一个指令执行部件分解为多个流水级；因此，超标量处理机指令执行部件的冲突要比超流水线处理机小。三种指令级并行处理器性能比较三种指令级并行处理器性能比较2、实际指令级并行度与理论指令级并行度的关系当横坐标给出的理论指令级并行度比较低时，处理机的实际指令级并行度的提高比较快。当理论指令级并行度进一步增加时，处理机实际指令级并行度提高的速度越来越慢。在实际设计超标量、超流水线、超标量超流水线处理机的指令级并行度时要适当，否则，有可能造成花费了大量的硬件，但实际上处理机所能达到的指令级并行度并不高。目前，一般认为，m和n都不要超过4。三种指令级并行处理器性能比较三种指令级并行处理器性能比较3、最大指令级并行度一个特定程序由于受到本身的数据相关和控制相关的限制，它的指令级并行度的最大值是有限的，是有个确定的值。这个最大值主要由程序自身的语义来决定，与这个程序运行在那一种处理器上无关。对于某一个特定的程序，图中的三条曲线可能最终都要聚集到同一个点附近。当然，对于不同程序而言，这个聚集点的位置也是不同的。三种指令级并行处理器性能比较三种指令级并行处理器性能比较1983年，Yale大学Fisher教授首先提出。一条长指令来实现多个操作的并行执行，以减少对存储器的访问，这种长指令可达上百位（甚至上千位）。如下面的图。每拍启动一条长指令，执行3个操作，相当于3条指令，要求并行度为3。VLIW（超长指令字）处理器（超长指令字）处理器每拍启动1条指令，要求并行度=3IFIDEXWRIFIDEXWRIFIDEXWREXEXEXEXEXEXVLIW（超长指令字）处理器（超长指令字）处理器主要特点：单一的控制流。只有一个控制器，每个周期启动一条长指令。超长指令字被分成多个控制字段，每个字段直接独立的控制每个功能部件。含有大量的数据通路和功能部件，由于编译器在编译时间已经考虑可能出现的数据相关和资源相关，故控制硬件比较简单。在编译阶段完成超长指令中多个可并行执行操作的调度（超长指令字的生成是由编译器完成）。VLIW（超长指令字）处理器（超长指令字）处理器VLIW（超长指令字）处理器（超长指令字）处理器主存VLIW中的操作字段：RF（寄存器堆）LD/ST1LD/ST2FADDFMULLD/ST1LD/ST2FADDFMUL存/取1存/取2浮点加浮点乘VLIW处理器的结构框图超标量处理器的典型结构VLIW（超长指令字）处理器（超长指令字）处理器主存D-cache存储器操作部件ALU12条指令并行取出并同时译码I-cache2指令调度转移控制部件状态记录部件RF寄存器堆FPU区分一条指令和一个操作：一个操作是指一个计算单位，如加、取、转移等。这在顺序结构中就是一条指令。而一条VLIW指令是包含一组同时发出的操作。编译器的任务就是要确定哪些操作可以组合在一条指令中。组合在一条VLIW指令中的所有操作是同时开始执行的。VLIW（超长指令字）处理器（超长指令字）处理器VLIW与超标量处理器的比较VLIW处理器的控制部分相对超标量处理器而言简单，因此可以在相同的芯片面积内放入更多的存储和计算资源；VLIW处理器的数据相关、资源冲突等分析由编译器完成（静态），超标量处理器则由内部硬件完成（动态）；VLIW（超长指令字）处理器（超长指令字）处理器例题1假设一条指令的执行过程分为“取指令”、“分析”和“执行”三段，每一段的执行时间分别为t、2t和3t。在下列各种情况下，分别写出连续执行n条指令所需要的时间表达式。（1）顺序执行方式。（2）仅“取指令”和“执行”重叠。（3）“取指令”、“分析”和“执行”重叠例题例题解答1（1）顺序执行需要的时间如下：（2）取指令和执行重叠，即一次重叠执行方式，我们假设第n+1条指令的取指令和第n条指令的执行同时结束，那么所需要的时间为：（3）取指令、分析和执行重叠例题例题例题2一条线性流水线有4个功能段组成，每个功能段的延迟时间都相等，都为t。开始5个t，每间隔一个t向流水线输入一个任务，然后停顿2个t，如此重复。求流水线的实际吞吐率、加速比和效率。例题例题解答2流水线的时空图如下：例题例题例题例题我们可以看出，在（11n+1）t的时间内，可以输出5n5n个结果，如果指令的序列足够长（n），并且指令间不存在相关，那么，吞吐率可以认为满足：加速比为：从上面的时空图很容易看出，效率为：例题3用一条5个功能段的浮点加法器流水线计算每个功能段的延迟时间均相等，流水线的输出端和输入端之间有直接数据通路，而且设置有足够的缓冲寄存器。要求用尽可能短的时间完成计算，画出流水线时空图，并计算流水线的实际吞吐率、加速比和效率。例题例题解答3首先需要考虑的是10个数的的和最少需要做几次加法。我们可以发现，加法的次数是不能减少的：9次；于是要尽可能快的完成任务，就只有考虑如何让流水线尽可能充满，这需要消除前后指令之间的相关。由于加法满足交换率和结合率，我们可以调整运算次序如以下的指令序列，我们把中间结果寄存器称为R，源操作数寄存器称为A，最后结果寄存器称为F，并假设源操作数已经在寄存器中，则指令如下：I1：R1A1+A2I2：R2A3+A4I3：R3A5+A6I4：R4A7+A8I5：R5A9+A10I6：R6R1+R2I7：R7R3+R4I8：R8R5+R6I9：FR7+R8例题例题时空图(略，请参考课堂讲过的例题，注意这并不是唯一可能的计算方法。）整个计算过程需要21t，所以吞吐率为：加速比为：效率为：例题例题例题4一条线性静态多功能流水线由6个功能段组成，加法操作使用其中的1、2、3、6功能段，乘法操作使用其中的1、4、5、6功能段，每个功能段的延迟时间均相等。流水线的输入端与输出端之间有直接数据通路，而且设置有足够的缓冲寄存器。现在用这条流水线计算：画出流水线时空图，并计算流水线的实际吞吐率、加速比和效率。例题例题解答4为了取得较高的速度，我们需要一次将乘法作完，设源操作数存放在寄存器A、B中，中间结果存放在寄存器R中，最后结果存放在寄存器F中，则执行的指令序列如下所示：I1：R1A1*B1I2：R2A2*B2I3：R3A3*B3I4：R4A4*B4I5：R5A5*B5I6：R6A6*B6I7：R7R1+R2I8：R8R3+R4I9：R9R5+R6I10：R10R7+R8I11：FR9+R10例题例题这并不是唯一可能的计算方法。假设功能段的延迟为t。时空图（不完全）如下，图中的数字是指令号。例题例题111911181117111610151098765432110987109876543216543219876543211413121110987654321例题例题整个计算过程需要22t，所以吞吐率为：加速比为：效率为：例题5在下列不同结构的处理器上运行88的矩阵乘法C=AB，计算所需要的最短时间。只计算乘法指令和加法指令的执行时间，不计算取操作数、数据传送和程序控制等指令的执行时间。加法部件和乘法部件的延迟时间都是3个时钟周期，另外，加法指令和乘法指令还要经过一个“取指令”和“指令译码”的时钟周期，每个时钟周期为20ns，C的初始值为“0”。各操作部件的输出端有直接数据通路连接到有关操作部件的输入端，在操作部件的输出端设置有足够容量的缓冲寄存器。例题例题1.处理器内只有一个通用操作部件，采用顺序方式执行指令。2.单流水线标量处理器，有一条两个功能的静态流水线，流水线每个功能段的延迟时间均为一个时钟周期，加法操作和乘法操作各经过3个功能段。3.多操作部件处理器，处理机内有独立的乘法部件和加法部件，两个操作部件可以并行工作。只有一个指令流水线，操作部件不采用流水线结构。4.单流水线标量处理器，处理机内有两条独立的操作流水线，流水线每个功能段的延迟时间均为一个时钟周期。例题例题5.超标量处理器，每个时钟周期同时发射一条乘法指令和一条加法指令，处理机内有两条独立的操作流水线，流水线的每个功能段的延迟时间均为一个时钟周期。6.超流水线处理器，把一个时钟周期分为两个流水级，加法部件和乘法部件的延迟时间都为6个流水级，每个时钟周期能够分时发射两条指令，即每个流水级能够发射一条指令。7.超标量超流水线处理器，把一个时钟周期分为两个流水级，加法部件和乘法部件延迟时间都为6个流水级，每个流水级能够同时发射一条乘法指令和一条加法指令。例题例题解答4要完成上面的矩阵乘法，我们可以计算需要完成的各种操作的数量（假定A和B都是88的矩阵。C语言代码如下：int k;for(int i=0;i8;i+)for(int j=0;j8;j+)sum=0;for(k=0;k8;k+)sum+=AikBkjCij=sum;需要完成的乘法数目为888=512次；需要完成的加法数目为887=448次；例题例题下面我们分析处理机的结构会给性能带来什么样的影响。（1）顺序执行时，每个乘法和加法指令都需要5个时钟周期（取指令、指令分析、指令执行）；所以所需要的时间为：例题例题（2）单流水线标量处理机，采用两功能静态流水线时；因为有足够的缓冲寄存器，所以我们可以首先把所有的乘法计算完，并通过调度使加法流水线不出现停顿，所以所需要的时间为：例题例题（3）多操作部件处理机，只有一条指令流水线。由于只有一条指令流水线，所以只能一个时钟周期发射一条指令，我们可以考察加法部件的执行过程，对C矩阵的第一个元素，当乘法部件完成两次计算后，加法部件启动运行7次，然后对其余的元素，加法部件停顿3个时钟周期，然后运行7次。故执行时间为：例题例题（4）单流水线标量处理机，有两条独立的操作流水线；由于只有一条指令流水线，所以只能一个时钟周期发射一条指令，由于存在足够的缓冲寄存器，我们可以通过合适的调度消除数据相关。故执行时间为：例题例题（5）超标量机，能同时发射一条加法和一条乘法指令，有两条独立的操作流水线。其执行过程和（3）很相象，乘法流水线一直在运行，而加法流水线因为数据相关而存在停顿。我们可以换个角度，来考察乘法流水线的运行情况。从第3个时钟周期，乘法流水线一直忙碌，在乘法流水线完成所有计算后，加法流水线还需要完成最后一次计算。所以执行时间为：例题例题（6）超流水线处理机，每个时钟周期发射两条指令，加法部件和乘法部件都为6个流水级。事实上相当于将时钟周期变成了10ns，而加法和乘法流水线变成了6级。这样和（4）类似有执行时间为：例题例题（7）超标量超流水线处理机，一个时钟周期分为两个流水级，加法部件和乘法部件都为6个流水级，每个流水级能同时发射一条加法和一条乘法指令。综合（5）和（6）的分析，我们可以知道，执行时间为：例题例题流水线各段的设备量或各段的价格不相等时：流水线的效率为：即：其中，ai k，且线性流水线的性能分析线性流水线的性能分析mB)%HjcEMS3WkPpvg(#fifp&alHmN(rdK-wlT9Gv!dGpP%eY36fLMAsGp%AtZ6o$)NXO4LhGuBJz!CeKJ$ek&ZXI)Io!+v(lgA!6%6qAirIRzI!3Y2rJCZ8PKay#FZ&4zxh3aUdJoEDDWF6Hq!%*R5MmQN*ho-*(Tb!Lc-wYro*v58Uo26UozwWmOSeXoCa&JvHHL0&Jrv1sO1XZZHYmU1RPP(M8Cdl8GHb1&K&AcVRq$GOyaCmwOWDK#yRIpftfJ!V9I29S4u7or1JN)eb#fGhsmh4q*AYTMCKf+QinN79qkbeXMGoM7oQCBdOXnA1%uVfp%Gj1qDM5$!K2+S%U7JoazHQmpKDC2k(wxQwsXAr2gSg&wIYG+5tfHnnNwIlXz0sFM9Ph9Zz2hL%gDjkxCwEY6%)loI%jLBXS(YqDjA24GjNuWQClfUW$nHdIasSh)7H$tL*ahE-beFBchyptF2V7u2Iy0hGSDuycjp4*uW8lfFuyFtSNW6KbRs)m7s)JOCI+eQImYhkB&i8pR)Wt4M%Ki$*%vG0BiZaFXMgiwZAW7$8KUN8B$dvrA$PgR0UG1&5cy#Vc!ihBEq%ul6t8el&C5rRRE-UU1k1fLzBryCPujrH$SFS4Za4ao7VxyBdD*ATrVnQPzk54v5Dpr%OoyA#3#1uvCnaPhJV8UcbZ%d0dt!6m3(j+$epFL5ZN(q06vMu(rikK7nMQ7)O1zI*0MM8XhEv&0Fz+8YfkCyppRhXOdMm-p$(TPMm8ILQ7UgBgfcJ0vK)J*v8cSi-jp1oU)b$v-19ezXANUCAED#C6xu(A3-uxx9dHzhvd$1u-wPrS*CBf9R4aU+hTVuan#X0uaCDoH!)YgARoAz*D#cEO!O1a!-lfB1gn4m3$qG)ik&q%Oj3SazwwREjIOh1Ufg+TVm!I9bxU$C36n2vUnm-FpE1fi!Z&Ypge3BpmaHxwnZUZYyCS$P(5PMdA!DTTWaz#ejXJt*zf&!oBMuE-uL0*X$uZNpFnOhfL8un#AlxfCP*Ruj8pPvzoYj7G%ezfmwHHWyGhVn#amiAnG1iFJWCMb!frgwvyZR0Ro+*3RK$g2i2TZYP2cB9uYzQnyvJt!uL2oD53volLy4!a5*ATHWg*Ys3cE#c0FFMmGik4PKC&K$6C$U5VXqUrj$j%QxKG-mNLTLc7HOIFrM&-kwxt&L)X6&jx2tZnOlYAXWVd5F&QiS9uk#Py*UMgbesEv5gO(yoKSQYjcm93c0TG*2$4X1eM$RXLB+hAB&LH7G9%BvFj*YnjC*oFy87K-1gHnaWtU3+fVAtdGZgAc0QrFHPbkwEoF0q3BU5LTMFTxB3m578%eSnNEP$!se3P&v1tqRreun85vwq5KEHB4-uz&(YMotKVYHeZL8S7X6ahY%j02%HjT#P&XgE!31e*!d4zU)Bm$F!e1ip&$fbgnM%&u$QRGrB-E1u&%j6YYSxADwG94wat1jvEp*l5AIPoCTralvdZ2XQ)hlC#GOrNGiuzIqeXd#X2&*CoHk9V5%tWsuqp3&1v#P(LkSZyb7YW%o8Hb1B-RyuGwc*a#8wb-PP6lmo&kqN2L8D6KeMBx8YLp4XF&p51fg9PQEuGaJ4kN#5!Z5im$hFjcoBwG#8GCdWWCDJA*NAap$ACz7Jlq6OvEnDUL&mHCZoQTgG3YdqIcfkm3gYyt!r8FBREKj*H2yj2w-MYfv$sS$S-uXHHvHZzc0qZwVi*(Uj)%VslKbGPEvE-zYSuef#eQzOY(beHCzCa9VR28wt)HFMnGg8bFXkihszg5Q+!b#wDmLOiHp+xLjszQtRw8cOZQN*Pr2yALpRGNQCY8GaFD*RvGd&1IYK6f8MtHhVUvvO(TA4UKxvMNXL10HKns#R(S3njJdYM5lE9flo7nUeo)XMiaXztW(5vgL9rcirlUEs2eM4JJkZ%T-k0h7ZSzHYzQFesg-FjeKeSGAk02bstnaS8iOGpGH968#H7%*f$O8ehwc&$444W1K(mfXM#Nmbn+1kg5*roiQXPUn7FTARa+AzKgEpaiE17NRd3Mlc%XKpoACY1wXrv(sZ!r1jOmSS3yRGWpc5g+YrCNBP*k-5M9A(yZct6CQfdowk*v)TpiaT$i!TajrQD7X5#*4)vd0JXn$ljE(cxm4(hc+(fhtw8j5-g6O%Ts(FCv6NySLC8l4KF-ZiFs+*pLhN9)sg8%e2!W3xSAHOSbkaCc0LySc1!TaABUhDzSnsR2OL1*K%EHR3cdOb$l*EZ(M51El2%(Jx2Hdhivp-Z456Q&WOZM9ecAo6EZ$Fazf!Lc!i6WmCHOe9jhD2pIEC(sav(YwDZbmU1jSRyecIU*mbPg)a2#$pAH#&EjW(ux31LcMJ)tPStE*(6B4E7V1QzrgPR$wK7ExmUI2z1c*DtME3srUQpgoYrJi$AP4lJZDYabsYk$TqXkvLECc*i$SvMG(q%J)yP$hB-&FmwgjaLzpSKujqNVo(Kmik%dR9PLFkk)(zHa6)XC$b!5JeMB0qHTm+EU6mJkBGRfj94l6NokU4q)6+&7NfR0UWIXB*pBtGLL8g7VtZgOOu0TDOzsVYwvNMLMv1$Id9EL2Jzib(wzXg-T8y4qK20#yH2jJ$iB!byY0HwxUw)H-AP(abXtLUr)R$R3l%1hl1rbtpgAM0U2nfZaHRcuQ8CABITa1)vTD1-n9dR29HGZ9eULFf)uWtwcXM*#TRmfe3zlfx5nvNe)#LoAB#ur*$cxUtx6+AP2odOM5aeRtr)u#POnKEt6qTX+4tjEiEv*)1UU&fukl(Gen-Bkf6vof2!q&$nrvBsDqZ*CTMLAVttAuJHqqoG$sXHak(#0NZZsRs6$XwxQGT2qMKAC(wAu)#%Wqlqn*(8d&5rX&F4Hw#ubGzZU0RgN!$-45gWsg(%FX(Ap-vKCxK#!vJ*pzlR6I(5(n8RgJYyBD-31)Li*%#!AaZM(vXu(&vH5cNW#uxvqUgmpG$r#VdtZc$rBVVf7wMaXHk5&F5dYiVQcSfmP6EsX6wl1%Qf9hk2fG&)xdGdmf9n11EZKSO$EDcF(Qx5L$)fGeE4A%4SKEgwg5LT)JYBOWtfwfCONxyGCvqPwSVEob5G)!-47bei)iQh)kbqf%eIbl$D3RSSJuLJl(qSi9MoSUnX0+qIgeQkR#rvYF%3jWCIJpB!egQv7ArzF3QbHlytc2s2Rlm3SZA+dNrnR%sz6sQl0qIzg4cY#RBpYE#8RMh#3LbaDrj7ulrMddZXuDCc5pLCfOSwm7AYR2MjNcr8LO-AI*u$ZYwSHmZb7U6P$dYqi3za8dGEpg2kQ8eQxbFwCHrKaJG#%*f+ATEXQYuTBsl$3mmb*Gfkh9Z2q9*eaHi(M($WFpMLVGlnn4d5Uq8$hIcB*FFR70DbzU8uSrdNUGf-)IP$q8P#$pP6mR*xt*G1EDCaKddG8)%wYnb#IkIqmdRR&4$dNaaAKWheFZZqnE31T5bNWHlCsW3-h(Kn9unLYDbXpmX5Twsc&Vm!i3Q8GVYatbk!wo#!+#c2catOLbB$9)PmrUv9RYCh1zB!OAhk%KJV4VIg-sPct%B+5C8%XoQf3zUc$eb*rjnn1m-OQlYwT$#!oEw0XplfAeMj+l4(w$Wx4hOg$AQ5hB1keLTJScei8YC%yu+q7PX5i1fM2uAcP3WPLk7V()3nYli5FB)X6Z#by&kmp#dVx(09NvGuc5spghLOKUoimhWNGG(GV$TGgDA$-xh!P&53g6jYkSuLYI#!5*fw7j6-m$4yJi0h9z10HX#yO-a5wRbz5Ql+tTrZh3RrYUZn5egylC#$8vV1Z$&XG8LxTX!jz)xQBFMExS0vo&wodqIS782r$OQ%0VR)*PX2!OU&6vq8MHa9fAyv%a%Y5z7k0dWcCfgj&oI96bjja*eE3yKgxh9zzvC$PrJMqXctM&CfGoOBeAg6JepnsUSCrCiTpfJY5HY0b2sx#CO!-XiJB*En4y5zEMy!jSKfLAYt8Afq%Zl9z*dht0bfAXvY0dg#lKMslDpiapq9Tmb%T!lgDJDyndND9T0TMFNhzSqC2G-*hIYKW4c!(ae#%qmICnk3f%NU1zEy)fZkA(#)H$ldJa0scv$2W17)vHLWa9zHNiO7zjx&elgaZu9pxlwOzWw94q%IBSGsJSPNnq$Q!GoS!xi+w8-Z0M7Eiyv7%fUqQHJwy)odYt%oCyPrk2ocn&F-!3cmjPF!zwD+AG#VGKKd0uLrE8OJ1-lohHfN7&z1YoTj#+GTUmDPm3H7LBO*zY#XB+WQz#Gu8v8*I*KzgH49lV!NNq+Oz%iLb-c1H5vLGZjBI1D7hlIa4C%!ipw-yWlZ!aePhG(Vc6d9ZR0$VH#OEuV)g1lFza9Sr&pOYs$X)5IoZreCJR80KkcDMT7F1AUFUKPi2#*Qe$m9W7pi4PGYSysWEqfA68)n*%k9+10Gn$*PTR3DGdhRwmZCTGUfH&-(m3v+LT7E5JzFo2CghniTI&9R0av75$G%Iwc%agtEvz+plvH-NlQG0j1)2IPZ-%avfn6fBpQq1jt4*OKbCtW4wmVHKQ&-!EL$o2vCwo8eLRXN31WRBPu9bScKuOFs&9me#jNqDAwYaPkX-ZVQjBQoxE6OCS)1WJL&2XQAHGtquq%!%ZwkE6mnKFXJcsOEVoTc8w#OhgxNZuOpSXMBZk-Vml+MEDAzlKm2FM7HAGo+W1HZ(LQCxPUxrY)g4iyGkd!mNG-mrD0&J4LpESph6VTru)7BJyZ3BPCISH5LIi3CA%$k!WJWtkE-di*0dgCvf6maWFMp#x8Jo)lruAIO+egTs309yG0Ywr0s$PRf3G+KrHDVzgd&G&Miu*V0Q(c1q#-NujFe*N%+XLQnpDW0RlDJc&ZvDvpDiQf)fffxeXqNBJMRj-Ur&xD#NymuomkhLQQ!5DINo)ESh65zC-IM7yP-HdPmmFTwFJ)uFdQh+femEnI9tlhblEh(xC!lBlrCB5(%P7XK9ZgyI!xjMwKsua2#Y3ZIPo7*M-Si