第五章重叠、流水和向量处理机

1、第五章重叠、流水和向量处理机5.1重叠解释方式5.2流水方式5.3向量流水处理与向量处理机5.4指令级高度并行的超级处理机5. 1重叠解释方式 5. 1. 1重叠的基本概念1. 顺序执行方式执行n条指令所用的时间为：nT二、（f取指令i f分析i + f执行i）Z = 1如果每段时间都为t，则执行n条指令所用的时间为：T=3xnxt 主要优点：控制简单，节省设备 主要缺点：速度慢，功能部件的利用率低取指令k分析k执行k取指令k+1分析k+1执行k+12. 一次重叠执行方式执行k将一条指令的执行分解成“分析”和 “执行”两个弃曲匹分析k分析k+1执行k+1主宴价占.分析k+2执行k+2指令矗执行

2、时间缩短，功能部件的利用率明显提高。 主要缺点：需要增加一些硬件，控制过程稍复杂。3. 二次重叠执行方式将一条指令的执行分解成“取指”、“分析” 和“执行”三个子过程在理想情况下，处理机中同时有三条指令在执 行。处理机的结构要作比较大的改变，需要釆用先 行控制技术。|取指令k分析k执行k取指令k+1分析k+l执行k+l取指令k+2分析k+2执行k+2二次重叠执行方式5. 1. 2先行控制方式的原理1. 采用二次重叠执行方式必须解决两个问题：(1) 有独立的取指令部件、指令分析部件和指 令执行部件把一个集中的指令控制器，分解成三个独立 的控制器：存储控制器、指令控制器、运算控制器(2) 要解决访

3、问主存冲突问题取指令、分析指令、执行指令都可能要访问 存储器2. 解决访存冲突的方法：(1) 采用低位交叉存取方式：这种方法不能根本解决冲突问题。指令、读操作数、写结果。(2) 两个独立的存储器：独立的指令存储器和 数据存储器。如果再规定，执行指令所需要的操作数和执行 结果只写到通用寄存器，则取指令、分析指 令和执行指令就可以同时进行。在许多高性能处理机中，有独立的指令Cache 和数据Cacheo这种结构被称为哈佛结构。（3）釆用先行控制技术釆用先行控制技术的关键是缓冲技术和预处 理技术。缓冲技术通常用在工作速度不固定的两个功能 部件之间。设置缓冲栈的目的是用来以平滑 功能部件之间的工作速度

4、。在采用了缓冲技术和预处理技术之后，运算器 能够专心于数据的运算，从而大幅度提高程 序的执行速度。55. 1. 3处理机结构1. 三个独立的控制器：存储控制器、指令控制器、运算控制器。2. 四个缓冲栈：先行指令缓冲栈、先行读数缓冲栈、先行操作 栈、后行写数栈。3. 处理机组成主 存 储 器存储 控 制 器后行写数栈先行读数栈5. 2流水方式空间并行性：设置多个独立的操作部件 时间并行性：分时使用同一个部件的不同部分 5.2.1流水线工作原理与分类5.2.2流水线处理机的性能5.2.3流水线相关的处理5.2.4非线性流水线的调度95. 2.1流水线工作原理与分类1=(1)基本概念流水线：重叠概念

5、的引申 时空图：空间、时间空味执行部件执行k执行k+1执行k+2执行k+3分析部件分析k分析k+1分析k+2分析k+3取指令部件取指令k取指令k+1取指令k+2取指令k+30tlt4t5 麻(2)流水线的分类1.是否有反馈回路线性流水线 (Linear Pipelining): 数据顺序流过流水线各段一次且仅一次 非线性流水线 (Nonlinear Pipelining):有回路，即流水线某段被使用多次前馈回路输入一输出反馈回路一种简单的非线性流水线#2按使用级另U来分动能部件级 如“浮点加法流水线”，也叫“运算流水线” 处理机级 指一条指令分解成多个子过程，也叫“指令流水线” 处理机间级 多

6、处理机通过存储器串联，形成流水线，宏流水线Atx At2 At3At4浮点加法流水线输入俞出功能取指令指令译码，取操作数执行算术形成操作数地址形成RR*指令逻辑运算向存储器 写结果先行控制方式中的指令流水线3单功能流水线与多功能流水线 单功能流水线：只能完成一种固定功能的流水线OCey1计算机种有12条，YH1计算机有18条Pentium有一条5段定点和一条8段浮点流水线。Pentiumlll有两条定点和一条浮点指令流水线。多功能流水线：流水线的各段通过不同连接实现不同功能UJTexas公司的ASC机，8段流水线，能够实现: 定点加减法、定点乘法、浮点加法、浮点乘法、 逻辑运算、移位操作、数据

7、转换、向量运算等。3I彥数義I累加I输:'丨丨I定点乘(b)定点乘法3弋输入求阶差(d)浮点点积4多功能流水线又可分为：静态流水线与动态流水线静态流水线:同一段时间内，各个功能段只能按照一种方式连接，实现一种固定的功能。动态流水线：在同一段时间内，各段可以按照不同的方式连接，同时执行多种功能。5. 2. 2流水线处理机的性能主要指标：吞吐率、加速比和效率1.吞吐率(Though Put)流水线吞吐率的最基本公式：TP = 其中：n为任务数，TkT *为完成n个任务所用的时间。各段执行时间相等，输入连续任务情况下，完成n个任务需要的总时间为:Tk=(k+n1)At其中：k为流水线的段数，

8、At为时钟周期。15Tk= k At + (n-1) At = (k+n-1)At吞吐率为：TP=yk + n 】)/最大吞吐率为：TP max = Lim-S (k + n-l)At AZ各段时间不等，完成n个连续任务:n吞吐率:（n 一 1） max（小圮、力）k£力+i=最大吞吐率：TP =max（ AZi,力）> S2> S3 卡 & '输出*A j流水线各段执行时间不相等的解决办法:iiU输导 S，Ati=AtAt2=3AtAt3=AtAt4=At(1)分离瓶颈段(如果可分的话)输出AtAtAt :“瓶颈”流水段再次细分AtAt_匚二苍弹匚_ 输

9、MsmI彳 S2-3 牡”必 |At12345678910111212345678910111212345678910111212345678910111212345678910111212345678910111211S4S3cS3bS3aS2SiuU2tl7采取“分离瓶颈段”方式时的任务时空图T(2) “瓶颈“流水段重复设置：增加分配器和收集器At2=3AtS4s3S2-3S2-2S2-1Si1234Fn-2n-1n1234Ar-n-2n-1n1113n511234s24n-2n-1n-2流水段重复设置的流水线2加速比（Speedup）计算加速比的基本公式:顺序执行时间口流水线执行时间八e

10、 kn22 力i=l、_ k:/： +(M -一 1) max( AZi, Azl2,- - ，力)Z=1实际加速比为:各段执行时间相等,加速比:kn山 _(k + n 1)A£ + 1最大加速比：Sms. = Lim- = k/i-k + n 1 各段时间不等，牺人珪2买仕分T肓侃下,当流水线段数增加时，需要连续输入的任务 数也必须增加A加速比s10 任务个数3效率(Efficiency) 计算流水线效率的一般公式:厂个任务占用的时空区To匕二E个流水段的总的时空区 kTk 各流水段时间相等，输入n个连续任务,流水线的效率为:最高效率为：knN _ nk (k + n 1) / E

11、 1E max=Limnsnk +n-各流水段时间不等，输入n个连续任务，流水kn 工线效率为:E =工k 1) max(A?i, AZ2< ，%)Z=1Z44流水线性能分析举例对于单功能线性流水线，输入连续任务的情 况，通过上面给岀的公式很容易计算出流水 线的吞吐率、加速比和效率。对于输入不连续任务，或多功能流水线，通 常具体情况具体分析。例 5.2：用一条4段浮点加法器流水线求8个浮点数的和：Z=A+B+C+D+E+F+G+H25解:Z=(A+B) + (C + D)+(E + F) + (G + H)牛空间周期123789 10 11 12 13 14 15规格化；2345尾数加对

12、阶能数数果 nM nN 士口 求力力幺k167776耐间GA+BE+FHC+DG+HA+B C+D E+F g+HA+B+C+DE+F+G+HA+B+C+DE+F+G+H用一条4段浮点加法器流水线求8个数之和的流水线时空图27解:7个浮点加法共用了 15个时钟周期。n 71流水线的吞吐率为：TP =肓二 = 0*47Tk 15 b Ar流水线的加速比为：S = ¥m187Tk 15-Ar流水线的效率为：E二上二二°47kTk 4x15. Ar例：计算向量点积= f %勺2 = 1 设有两个向量A和B,各有4个元素，要在如图所示 的静态双功能流水线上，计算向量点积AB,其中1

13、- 2-) 3-5组成加法流水线，1-) 4-) 5组成乘法流水 线，又设每个流水线所经过的时间均为而且流水 线的输出结果可以直接返回到输入或存于相应的缓冲 寄存器中，其延迟时间和功能切换所需的时间都可以 忽略不计。XyZ例：计算向量点积A-B = ai-bii=如果在动态流水线中，时空图变化如下:44 B =，a.b.Z / i ii=l练习设向量A和B各有6个元素在下图所示的静态双功能8流水线上计算向量点积AB=£q& ,其中1组成加法流水线1 -5-4组成乘法流水线。若假定流水线的各段所经过的时间均为At, 流水线输出可直接送回输入或暂存于相应缓冲寄存 器中，其延迟时间

14、和功能切换所需的时间都可忽略。(1) 画岀时空图求岀吞吐率、加速比。335.2.3流水线的相关处理局部性相关：在执行本条指令的过程中，如果用到的 指令、操作数、变址量等是前面指令的执行结果，这 种相关称为局部性相关。全局相关：由条件分支指令、转子程序指令等引起的 相关。流水机器的中断处理局部性相关入指令地址:（可以不顺序流动的）（顺序流动的）（判出卜h相关）读写段T111段m空16|781k空 空 h出段号： 12!345指令j的操作数是指令h的结果，流水线第2段为读段，第7段为写段。指令j 结果：流水线断流 解决思路顺序流动（2）异步流动（3）设置相关专用通路需要指令h达到第8段时，才能进入

15、第2段进行“读"（先写后读相关）全局性相关(1)猜测法转移不成功分支*+；|» 耳k+3|_卜+j|_|i+s|_卜壬1| p + 2 p + 寸|p匚彳p+耳 -猜 测路径(转移不成功路径转移成功路径(2) 加快和提前形成条件码条件码i-l与转移指令分开，将i-l提前形成(3) 采取延迟转移编译器生成目标程序时，将转移指令与其前面不相关 的一条或多条指令交换位置。(4) 加快短循环程序的处理将长度小于指缓容量的短循环程序整个一次性放入指缓内，并暂停取指 令；猜选分支恒选循环分支。流水机器的中断处理中断会引起流水线断流。然而，其出现概率比条件转 移的概率要低得多，且又是随机

16、发生的。所以，流水机器 处理中断主要是如何处理好断点现场的保存和恢复，而不 是如何缩短流水线的断流时间。在执行指令i时有中断，断点本应在指令i执行结束，指 令i+l尚未开始执行的地方，但流水机器是同时解释多条指 令，指令i+l、i+2可能已进入流水线被部分解释。有两种处理方式（1）精确断点法（2）不精确断点法5.2.4非线性流水线的调度非线性流水线调度的任务是要找出一个最小的循环周期,按照这周期向流水线输入新任务，流水线的各个功能段都不会发生冲突，而且流水线的吞吐率和效率最高。1234567891772寸寸374775拍号n段号k构建禁止表F (Forbidden List)F=1,5, 6,

17、 8(2)由禁止表求冲突向量C (Collision Vector)C = ( Cn_Cn_2-Cj 丄3。2。)Ci=l表示禁止间隔i At流入后续任务; 5=0表示允许间隔流入后续任务;初始冲突向量Co= (10110001)(3)由初始冲突向量求后继状态C,画状态有向图后继状态冲突向量Cj= SHR(K)(Ci) V Co37Co=(1O11OOO1)有4个后继状态：C二 SHR(Co) V Co =(00101100)V(10110001) = (10111101)C2= SHR(Co) V Co =(00010110)V(10110001) = (10110111)C3= SHR(C

18、o) V "(10111011)C4= SHR (Co) V Co= Co5=(10111101)有2个后继状态：C5= SHR(Cj V C°= (00101111)V(10110001) = (10111111)C6= SHR (CJ V Co= CoC2=(10110111)有2个后继状态:C7= SHR ©) V Co二(00001011)V(10110001) = (10111011)= C3C8= SHR(C2) V Co二 Co38$有2个后继状态Q有1个后继状态，以下略，直到不产生新的后继状态为止初始39调度策略平均时间间隔2 74.5小2 2 7

19、3.67 ZU3 43.5 '弋3 4 74.674 75.5 弋77小由状态有向图求无冲突调度策略(3 4)方式最优(5)画时空图，求TP、S、E连续输入8个任务时，流水线的吞吐率为41例题一个五段的非线性流水线的预约表如下。试求出最优调度 策略，并计算连续输入10个任务时，流水线的吞吐率。1234567577S37S477S577435.3向量的流水处理与向量处理机5. 3. 1向量处理与向量指令例如：for (i= 10;i<= 1010;i+ )ci=ai+bi+5;在向量处理机上，可用1条指令表示：c(10:1010) = a(10:1010) + b(15:1015)

20、即1条向量指令可以处理N个N对操作数向量的三种处理方式:以Yi =Ai*(Bi+Ci)为例(1)横向处理方式T(l)= B(l)+C(l)，Y(1)=A(1)*TT(2) = B(2)+C(2)，Y(2)= A(2)* T(2)T(n) = B(n)+C(n)，Y(n)= A(n)* T(n)(2)纵向处理方式T(l)= B(l)+C(l)T(2) = B(2)+C(2)T(n) = B(n)+C(n)Y(1)=A(1)* T(l)Y(2)= A(2)* T(2)Y(n)= A(n)* T(n)(3 )纵横处理方式向量寄存器长度n=64，向量长度N>64，则需对向量进行分组处理N = K

21、*n + r5. 3. 2向量处理机的结构5. 3. 2向量处理机的结构向量寄存器组8X64个5W移 位逻辑运算向量长度迭代求倒数相乘'加 浮点 功能 部件向量 控制快主存贮器加向量功能部件77向量控制向量屏蔽标璟寄存器r n vhVi冲突：并行工作的各向量指令，源向量或结果向量使 用了相同的Vi例如：V4 <- V1 + V2V5 <- VI A V2 A表示任何操作功能部件冲突：同一个功能部件被要求并行工作的多条 指令所使用例如:V3 <- VI + V2V6 <- V4 + V5链接方式：只要不出现功能部件和Vi冲突，有“先写后读” 的向量指令可以采用链接方式执行例如：D=A* (B+C), B和C取至了 VO, VI后运算以下指令V3 <-存储器取AV2 <- VO + VIB+CV4 <- V2 * V3乘法向量长度为N分析：指令1. 2无功能部件和Vi冲突，可以并行，第3条指令 通过链接，可以实现3条向量指令的大部分时间并行。7浮乘 +1SV4=17 拍启动访存访存Jgv3l J送浮乘 i送浮加部件j+ i浮加j+ 存Vzj* (送浮乘j+3条指令执行完的总时间为：17+(N-1)拍5. 4指令级高度并行的超级处理机5.4. 1超标量处理机单发射、多发射，每Zkt流出m条指令(称为度m)普通标量处理机(单流水