《计算机系统结构(第七讲).ppt》由会员分享，可在线阅读，更多相关《计算机系统结构(第七讲).ppt（77页珍藏版）》请在三一办公上搜索。
1、计算机系统结构(第七讲),厦门大学计算机科学系 陆达2004年11月28日,第五章 标量处理机,5.2 流水线处理机,5.2.3 线性流水线的性能分析,5.2.3.5 流水线性能分析举例,单功能、线性流水线，输入任务连续单功能、线性流水线，输入任务不连续多功能、线性流水线，输入任务不连续非线性流水线,例5.1：单功能、线性流水线，输入任务不连续 Z=A+B+C+D+E+F+G+H Z=(A+B)+(C+D)+(E+F)+(G+H)图5.42：用一条4段浮点加法器流水线求8个数之和的流水线时空图 吞吐率：TP=n/Tk=7/(15*t)=0.47*(1/t)加速比：S=T0/Tk=(4*7*t)
2、/(15*t)=1.87 效率：E=T0/(k*Tk)=(4*7*t)/(4*15*t)=0.47,例5.2：多功能、线性流水线，输入任务不连续 Z=AB+CD+EF+GH Z=AB+CD+EF+GH 图5.43：用TI-ASC多功能静态流水线求两个向量点积的流水线时空图 吞吐率：TP=n/Tk=7/(20*t)=0.35*(1/t)加速比：S=T0/Tk=(4*4*t+3*6*t)/(20*t)=1.70 效率：E=T0/(k*Tk)=(4*4*t+3*6*t)/(8*20*t)=0.21 该流水线的效率很低，原因主要有四个：p294,5.2.4 非线性流水线的调度技术,功能部件冲突，或流水
3、线冲突采用延迟输入新任务的方法非线性流水线的调度问题非线性流水线调度的任务：要找出一个最小的循环周期，按照这个周期向流水线输入新任务，流水线的各个功能段都不会发生冲突，而且流水线的吞吐率和效率最高,5.2.4.1 非线性流水线的表示,图5.44(a)：非线性流水线的连接图图5.44(b)：非线性流水线的预约表预约表的横坐标（列数）：流水线工作的时钟周期数，或流水线的功能求值时间，或流水线的装入时间预约表的纵坐标（行数）：流水线的功能段,一张非线性流水线的预约表可能与多个非线性流水线连接图相对应，如图5.45一个非线性流水线的连接图也可能对应有多张预约表，如图5.46,5.2.4.2 非线性流水
4、线的冲突,启动距离（initiation interval），或等待时间（latency）非线性流水线中的冲突（collision）图5.47：启动距离为3的流水线冲突情况图5.48：启动距离为2的流水线冲突情况禁止启动距离：如启动距离3、启动距离2,图5.49：启动距离为5的流水线预约表（任何一个功能段在任何一个时钟周期都不发生冲突）,非线性流水线的启动循环：如启动循环(1,7)图5.50：启动距离为(1,7)循环时的流水线预约表恒定循环：如启动循环(5),非线性流水线的禁止向量如何由预约表得到禁止向量？P297-298平均启动距离：如启动循环(1,7)的平均启动距离为4；启动循环(5)的平
5、均启动距离为5,5.2.4.3 无冲突调度方法,目的是要找出具有最小平均启动距离的启动循环E.S.Davidson及其学生1971年提出冲突向量：可由一张预约表的禁止向量得到，如禁止向量为(3,4,6)，则冲突向量为C=(CmCm-1C2C1)=(101100)状态图：由冲突向量构造而成m位逻辑右移移位器：当移出的位为0时，用移位器中的值与初始冲突向量作“按位或”运算，得到一个新的冲突向量；若移出的位为1，不作任何处理,图5.51：非线性流水线的状态图与一张预约表相对应，只有唯一的一个状态图从预约表可以画出状态图，但从状态图不能得到预约表,在状态图中可以找到很多不发生功能冲突的启动循环简单循环
6、：表5.1(各冲突相量只经过一次的启动循环）,最小启动循环：如启动循环(1,1,7)图5.52：最小启动循环(1,1,7)的流水性预约表恒定循环：如启动循环(5),5.2.4.4 优化调度方法,L.E.Shar在1971年提出了流水线最小平均启动距离的限制范围，对于一条静态可重构的流水线，通过预约表可以得到其最小平均启动距离的范围。共有三个方面，见P301采用预留算法来调度非线性流水线，可以达到最优调度。具体方法有三条，见P301图5.53：采用预留算法调度的预约表、连接图（有非计算延迟的非线性流水线）,图5.54：与图5.53相对应的流水线状态图（有非计算延迟的流水线状态图）,图5.55：按
7、照最小启动循环(3)工作的流水线预约表,单功能非线性流水线静态多功能非线性流水线动态多功能非线性流水线,5.2.5 局部相关,相关：数据相关、控制相关相关：局部相关（local correlation）、全局相关（global correlation），图5.56基本块（basic block）软件方面：编译器生成的目标程序要能够适合流水线结构硬件方面：要解决好存储系统的频带平衡问题局部相关有三种：（1）、“先写后读”数据相关，“写读”相关，“WR”或“RAW”（2）、“先读后写”数据相关，“读写”相关，“RW”或“WAR”（3）、“写-写”相关，“WW”或“WAW”,5.2.5.1 顺序流动
8、和乱序流动,什么是顺序流动方式？P304图5.57：一条6段指令流水线,把如下一段程序输入到流水线中：p304,图5.58：顺序流动方式正常流动：S1-S2-S3-S4-S5-S6=k+5-k+4-k+3-k+2-k+1-k发生“先写后读”数据相关时：流水线就会“断流”，有些功能段要出现“空闲”，如图5.58的“ti-ti+1-ti+2-ti+3-ti+4”,什么是乱序（out of order）流动方式？P305 亦称错序流动方式、无序流动方式、异步流动方式,从流水线的输出端看，指令流出流水线的顺序与输入端指令进入流水线的顺序是不一样的有些指令执行的时间短或经过的功能段比较少，它们要越过执行
9、时间长或经过功能段多的指令向前流动,程序中出现的三种数据相关：p306（1）、“先写后读”：k-k+2（2）、“先读后写”：k+2-k+3（3）、“写-写”：k+2-k+4,如何测试程序中的“先写后读”数据相关？采用相联比较器（p306）如何测试程序中的“先读后写”数据相关？采用相联比较器（p306）如何测试程序中的“写-写”数据相关？采用相联比较器（p306-307）,5.2.5.2 数据相关及其避免方法,流水线中的数据相关，在逻辑设计中称为“冒险（hazard）”或“竞争（competition）”图5.60：在指令流水线中可能出现的数据相关“先写后读”相关：D(i)S(j)“先读后写”相
10、关：S(i)D(j)“写-写”相关：D(i)D(j),避免发生数据相关的方法：（1）、延迟执行 如图5.58（2）、建立专用路径 如图5.57，设置一条从功能段S5到功能段S3的专用路径 图5.61：建立有专用路径的顺序流动方式,有多种设置专用路径的专门方法：如采用分散控制的公共数据总线法（也称Tomasulo算法）；采用集中控制的CDC记分牌法,5.2.5.3 数据重定向,通过建立专用路径来避免数据相关的基本原理是数据重定向在单条流水线中，建立专用路径的方法有：（1）、对于“先写后读”数据相关：图5.62(a)（2）、对于“写-写”数据相关：图5.62(b)对于“先读后写”数据相关：设置一个
11、缓冲寄存器，p309,例子：如何通过数据重定向来避免数据相关一个简单的程序：存在“先写后读”数据相关，“写-写”数据相关 k：LOAD F1，A k+1：FADD F1，F2 k+2：FMUL F1，F3 k+3：STORE F1，B图5.63：数据重定向原理,5.2.5.4 Tomasulo动态指令调度算法,1967年由R.M.Tomasulo提出，又称公共数据总线（CDB：Common Data Bus）法，或令牌法Tomasulo算法采用乱序流动方式来提高流水线的吞吐率和效率，并通过分散控制的办法处理数据相关最早在IBM 360/91处理机的浮点处理部件中被采用,IBM 360/91处理
12、机：图5.64（1）一个浮点加法器：两段流水线，三个保存站A1、A2、A3（2）一个浮点乘/除法器：六段流水线，两个保存站M1、M2数据流计算机中的数据驱动方式先行控制方式：浮点先行操作站、浮点先行读数站、浮点后行写数站FLB：Float Look-ahead Buffer FLOS：Float Look-ahead Operation Station FLR：Float Look-ahead Register CDB：Common Data Bus,这就相当于建立了一条从主存储器到浮点加法器的专用数据路径，A-FADD，p310，参见图5.63这就相当于建立了一条从浮点加法器到浮点乘法器的专
13、用数据路径，FADD-FMUL，p311，参见图5.63在把运算结果通过CDB送入浮点通用寄存器F1的同时，也送入浮点后行写数站SDB，由SDB负责把这个结果写到主存储器的B单元中，FMUL-B，p312，参见图5.63,CDC计分牌法：是另一种可以用来动态调度多条流水线的经典方法CDC计分牌法由J.E.Thornton于1970年提出最先用于CDC 6000大型计算机系统中计分牌（scoreboard）:是一个集中控制部件，它记录了数据寄存器和多个操作部件状态的变化情况，可以通过它来消除或减少某些数据相关，加快程序的执行速度,5.2.6 全局相关,什么是全局相关？由条件转移或程序中断引起的相
14、关称为全局相关，也称控制相关关键问题：一是要确保流水线能够正常工作；二是要减少因“断流”引起的吞吐率和效率的下降,5.2.6.1 转移的影响,“猜测法”：图5.65，猜测的分支方向是固定，它选择的是转移不成功的方向当流水线沿猜测方向执行指令时，一定不能破坏通用寄存器和主存储器中的内容两种做法：（1）、只进行指令译码和准备好运算所需要的操作数，在转移条件没有形成之前不执行运算；（2）、一直执行到运算完成，但不送回运算结果,包括条件转移指令在内的n条指令的总的执行时间是：TK-IF=(n+k-1)*t+n*p*q*(k-1)*t吞吐率：TPIF=n/(n+k-1)*t+n*p*q*(k-1)*t
15、TPMAX-IF=1/(1+p*q*(k-1)*t TPMAX=1/t D=(TPMAX-TPMAX-IF)/TPMAX=pq(k-1)/1-pq(k-1),减少条件转移指令对流水线的影响的措施：（1）、延迟转移技术和指令取消技术（p118-p119）（2）、静态转移预测技术（p272-p274）软件猜测法、硬件猜测法、两个先行指令缓冲栈（3）、动态转移预测技术,5.2.6.2 动态转移预测技术,关键要解决好两个问题：（1）、如何记录转移历史信息（2）、如何根据所记录的转移历史信息预测转移的方向记录转移历史信息的方法：（1）、把最近一次或几次转移是否成功的信息记录在转移指令中（2）、用一个小容
16、量的高速缓冲栈保存条件转移指令的转移目标地址（3）、用Cache保存转移目标地址之后的n条指令,方法一：在指令Cache中记录转移历史信息,转移历史表：在指令Cache中专门设置的一个字段转移预测逻辑根据“转移历史表”中记录的信息预测转移成功或不成功图5.66(a)：只记录最近一次转移是否成功的历史信息 无论预测是否成功，都要用本条转移指令实际转移是否成功的信息来修改“转移历史表”图5.66(b)：记录最近两次转移是否成功的历史信息 采用向左移位的方法修改“转移历史表”优点：不必专门设置转移缓冲栈，所记录的转移历史信息比较少缺点：需要有专门的指令Cache和专门的指令Cache控制逻辑,方法二
17、：转移目标地址缓冲栈,转移目标地址缓冲栈：用一个小容量的高速缓冲栈保存最近执行的k条转移指令的“转移历史表”和转移目标地址图5.67：转移目标地址缓冲栈=转移指令地址（采用全相联方式访问）+转移历史表+转移目标地址,方法三：转移目标指令缓冲栈,将方法二转移目标地址缓冲栈中的转移目标地址部分改为存放转移目标地址之后的n条指令图5.68：转移目标指令缓冲栈转移目标指令缓冲栈=转移指令地址+转移历史表+转移目标地址之后的n条指令,5.2.6.3 提前形成条件码,对于一般条件转移指令：只要在运算部件的入口处设置一个比较器，就能提前产生条件码对于用来控制循环次数的计数转移指令：采用专门的循环控制指令（L
18、DEC、LBNE）和专门的条件码寄存器（CCL），能够把产生条件码的运算型指令与使用这个条件码的条件转移指令分离开来,5.2.6.4 精确断点与不精确断点,不精确断点法（imprecise interrupt）：让已经进入流水线的所有指令都执行完成，断点就是最后进入流水线的那条指令的地址不精确断点法可能会发生二个问题：一是程序执行的结果可能出错；二是在程序调试过程中，通常要设置断点，程序员通过查看断点处的中间执行结果来判断程序编写是否正确精确断点法（precise interrupt）：由哪一条指令的程序性错误或故障发出的中断申请，断点就是这条指令的地址；需要把断点以前的指令的执行结果都保存下
19、来；要设置一定数量的后援寄存器图5.69：流水线处理机的中断处理,5.3 超标量处理机与超流水线处理机,表5.2：四种不同类型处理机的性能比较基准标量处理机（scalar processor）：一台普通的单流水线处理机超标量处理机（superscalar processor）：同时发射m条指令超流水线处理机（superpipelining processor）：机器流水线周期=1/n超标量超流水线处理机（superpipelining superscalar processor）：同时发射m条指令，机器流水线周期=1/nILP（instruction level parallelism）：指令
20、级并行度,5.3.1 超标量处理机,一般的流水线处理机：只有一条指令流水线，一个多功能的操作部件；k=4；“取指令”、“分析”、“执行”、“写回运算结果”指令所要执行的功能主要在多功能操作部件中，在“执行”这一功能段完成 ILP1,5.3.1.1 基本结构,超标量处理机：有多个操作部件，一个或几个比较大的通用寄存器堆，一个或二个高速Cache。三个处理单元（操作部件）：（1）、定点处理单元，也称中央处理单元（CPU），由一个或多个整数处理部件组成；（2）、浮点处理单元（FPU），由浮点加减法部件和浮点乘除法部件组成；（3）、图形加速部件（GPU）两个通用寄存器堆：采用重叠寄存器窗口技术（p12
21、1）两个一级高速Cache（Harvard结构）：指令Cache、数据Cache,图5.70：Motorola公司的MC88110超标量处理机10个操作部件：（1）、二个整数部件（2）、一个位操作部件（3）、三个浮点运算部件：浮点加、浮点乘、浮点除（4）、二个图形处理部件（5）、读数/存数部件：先行读数栈、后行写数栈（6）、指令分配/转移部件两个寄存器堆：（1）、通用寄存器堆（2）、扩展寄存器堆指令Cache：采用两路组相联方式工作 数据Cache：采用两路组相联方式工作 目标指令Cache：,5.3.1.2 单发射与多发射,单发射处理机：图5.71(a)取指令（IF）、指令译码（ID）、执行
22、指令（EX）、写回运算结果（WR）单发射处理机中，取指令部件和指令译码部件只各设置一套，操作部件可以只设置一个多功能操作部件，也可以设置多个独立的操作部件（如ALU、LSU、FAD、MDU）图5.72(a)：单发射指令流水线单发射处理机：就是一台有k段流水线的普通标量处理机，ILP1,多发射处理机：在一个基本时钟周期内同时从指令Cache中读出多条指令，同时对多条指令进行译码图5.71(b)：同时发射三条指令的多发射处理机的指令执行时空图图5.72(b)：同时发射二条指令的多发射处理机的指令流水线多发射处理机，亦称超标量处理机，1ILPm,先行指令窗口：用于保存由于功能部件冲突、数据相关或控制
23、相关等原因暂时还不能送到操作部件中去执行的指令；先行指令窗口的作用与先行控制技术中的先行指令缓冲栈相似先行指令窗口大小=28条指令图5.73：有先行指令窗口的多发射流水线处理机结构,5.3.1.3 多流水线调度,多流水线调度问题：NP完全问题顺序发射（in-order issue）乱序发射（out-order issue）顺序完成（in-order completion）乱序完成（out-order completion）顺序发射顺序完成 顺序发射乱序完成 乱序发射乱序完成,例子：p327“先写后读”数据相关：I1I2“先读后写”数据相关：I3I4“先写后读”和“写-写”数据相关：I5I6 功
24、能部件冲突：I2I4（都是FADD指令）功能部件冲突：I3I6（都是FMUL指令）,方法一、顺序发射顺序完成,图5.74：顺序发射顺序完成的指令流水线时空图I1I2和I5I6的“先写后读”数据相关：各一个等待时钟周期（I2和I6）I2I4的功能部件冲突（都是FADD指令）：一个等待时钟周期（I4）顺序完成要求：I3延迟一个时钟周期；I5延迟三个时钟周期I5I6的“写-写”数据相关：延迟一个时钟周期（I6）I3I4的“先读后写”数据相关：自然得到满足I3I6的功能部件冲突（都是FMUL指令）：自然得到满足,方法二、顺序发射乱序完成,图5.75：顺序发射乱序完成共需3个等待时钟周期（比顺序发射顺序
25、完成少5个等待时钟周期）其中：2个等待时钟周期用于I1I2和I5I6的“先写后读”数据相关（各一个等待时钟周期（I2和I6）；1个等待时钟周期用于I2I4的功能部件冲突（都是FADD指令）总的执行时间为9个时钟周期,方法三、乱序发射乱序完成,需采用先行指令窗口（参见图5.73）图5.76：乱序发射乱序完成先行指令窗口除了能够做数据相关性分析和功能部件冲突的检测之外，还应该至少有一套取指令部件和一套指令译码部件没有等待时钟周期，总的执行时间为8个时钟周期,乱序发射乱序完成：已在许多高性能超标量处理机中采用需要：（1）、先行指令窗口（2）、一个比较简单的数据相关性分析部件和一个功能部件冲突的检测机
26、构（3）、采用计分牌机制来表示数据相关性和功能部件的冲突（4）、通过优化编译器对指令序列进行重组,5.3.1.4 资源冲突,多个独立的操作部件：ALU、FADD、MDU、GPU、LSU如果采用流水线结构，发生资源冲突的可能性很小；如果不采用流水线结构，发生资源冲突的可能性就大图5.77：双流水线超标量处理机，操作部件不采用流水线的时空图 总共用了11个时种周期图5.78：双流水线超标量处理机，操作部件采用流水线的时空图 总共用少了3个时种周期,要为每一个操作部件设置一个“忙”标志触发器每个周期发射m条指令，延迟时间为k个时钟周期：不采用流水线结构，相差m*k每个周期发射m条指令，延迟时间为k个
27、时钟周期：采用k个功能段的流水线结构，相差m或m以上在单流水线的标量处理机中，只有连续出现相同操作的指令序列时，流水线才能不“断流”，功能部件的效率才能得到充分发挥在超标量处理机中，希望相同操作的指令不要连续出现，否则会发生资源冲突，要求相同操作的指令能够相对均匀地分布在程序中一般标量程序具有这个特点,5.3.1.5 超标量处理机性能,单流水线普通标量处理机：ILP=(1,1)超标量处理机：ILP=(m,1)超流水线处理机：ILP=(1,n)超标量超流水线处理机：ILP=(m,n)单流水线普通标量处理机：执行时间 T(1,1)=(k+N-1)*t超标量处理机：执行时间 T(m,1)=k+(N-m)/m*t加速比：S(m,1)=T(1,1)/T(m,1)=m*(k+N-1)/N+m*(k-1)S(m,1)max=m,本讲习题,P343：5.6 5.7 5.11,
