《【教学课件】第5章标量处理机.ppt》由会员分享，可在线阅读，更多相关《【教学课件】第5章标量处理机.ppt（180页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第第5章章 标量处理机标量处理机 只有标量数据表示和标量指令系统的处理机称为只有标量数据表示和标量指令系统的处理机称为标量处理机。标量处理机。5.1 先行控制技术先行控制技术5.2 流水线技术流水线技术5.3 相关性分析技术相关性分析技术5.4 超标量处理机超标量处理机5.5 超流水线处理机超流水线处理机5.6 超标量超流水线处理机超标量超流水线处理机5.1 5.1 先行控制技术先行控制技术5.1.1 指令的重叠执行方式指令的重叠执行方式5.1.2 先行控制方式的原理先行控制方式的原理5.1.3 处理机结构处理机结构5.1.4 指令执行序列指令执行序列5.1.5 先行缓冲栈先行缓冲栈5.1.6
2、 缓冲深度的设计方法缓冲深度的设计方法5.1.1 5.1.1 指令的重叠执行方式指令的重叠执行方式1.1.顺序执行方式顺序执行方式执行执行n n条指令所用的时间为：条指令所用的时间为：如果每段时间都为t，则执行n条指令所用的时间为：T3 n t3 n t主要优点：主要优点：控制简单，节省设备控制简单，节省设备主要缺点：主要缺点：速度慢，功能部件的利用率低速度慢，功能部件的利用率低2.2.一次重叠执行方式一次重叠执行方式如果每段时间相等，则执行n条指令的时间为：T(1+2n)t1+2n)t主要优点：主要优点：指令的执行时间缩短，指令的执行时间缩短，功能部件的利用率明显提高。功能部件的利用率明显提
3、高。主要缺点：主要缺点：需要增加一些硬件，需要增加一些硬件，控制过程稍复杂。控制过程稍复杂。3.3.二次重叠执行方式二次重叠执行方式如果三个过程的时间相等，执行n条指令的时间为：T(2 2n n）t t在理想情况下，处理机中同时有三条指令在执行。处理机的结构要作比较大的改变，需要采用先行控制处理机的结构要作比较大的改变，需要采用先行控制技术。技术。5.1.2 5.1.2 先行控制方式的原理先行控制方式的原理1.1.采用二次重叠执行方式必须解决两个问题：采用二次重叠执行方式必须解决两个问题：(1)(1)有独立的取指令部件、指令分析部件和指令执行有独立的取指令部件、指令分析部件和指令执行部件部件
4、把一个集中的指令控制器，分解成三个独立的控制器：存储控制器、指令控制器、运算控制器存储控制器、指令控制器、运算控制器(2)(2)要解决访问主存储器的冲突问题要解决访问主存储器的冲突问题 取指令、分析指令、执行指令都可能要访问存储器2.2.解决访存冲突的方法：解决访存冲突的方法：(1)(1)采用低位交叉存取方式采用低位交叉存取方式：这种方法不能根本解决冲突问题。指令、读操作数、写结果。(2)(2)两个独立的存储器两个独立的存储器：独立的指令存储器和数据存独立的指令存储器和数据存储器。储器。如果再规定，执行指令所需要的操作数和执行结果只写到通用寄存器，则取指令、分析指令和执行指令就可以同时进行。在
5、许多高性能处理机中，有独立的指令Cache和数据Cache。这种结构被称为哈佛结构。(3)(3)采用先行控制技术采用先行控制技术 采用先行控制技术的关键是缓冲技术和预处理技术。采用先行控制技术的关键是缓冲技术和预处理技术。缓冲技术通常用在工作速度不固定的两个功能部件之间。设置缓冲栈的目的是用来以平滑功能部件之间的工作速度。预处理技术是把进入运算器的指令都处理成RR型指令，它与缓冲技术相结合，为进入运算器的指令准备好所需要的全部操作数。在采用了缓冲技术和预处理技术之后，运算器能够专心于数据的运算，从而大幅度提高程序的执行速度。5.1.3 5.1.3 处理机结构处理机结构1.1.三个独立的控制器：
6、三个独立的控制器：存储控制器、指令控制器、运算控制器。存储控制器、指令控制器、运算控制器。2.2.四个缓冲栈：四个缓冲栈：先行指令缓冲栈、先行读数缓冲栈、先行操作栈、后先行指令缓冲栈、先行读数缓冲栈、先行操作栈、后行写数栈。行写数栈。3.3.处理机组成处理机组成4.4.先行指令缓冲栈的组成先行指令缓冲栈的组成作用：作用：只要指令缓冲栈没有充满，就自动发出取指令只要指令缓冲栈没有充满，就自动发出取指令的请求。的请求。设置两个程序计数器：先行程序计数器先行程序计数器PC1，用来指示取指令，用来指示取指令，现行程序计数器现行程序计数器PC，记录指令分析器正在分析的指令，记录指令分析器正在分析的指令地
7、址。地址。5.5.存在的主要问题：存在的主要问题：各类指令各类指令“分析分析”和和“执行执行”的时间相差很大，怎样的时间相差很大，怎样使各个部件始终处于忙碌状态使各个部件始终处于忙碌状态数据相关数据相关转移或转子程序指令转移或转子程序指令 先行缓冲站的组成先行缓冲站的组成5.1.4 5.1.4 指令执行时序指令执行时序设置了指令缓冲栈，取指令的时间就可以忽略不设置了指令缓冲栈，取指令的时间就可以忽略不计。计。一条指令的执行可分为一条指令的执行可分为2 2个过程个过程1.1.分析指令和执行指令时间不相等时的情况分析指令和执行指令时间不相等时的情况2.2.采用先行缓冲栈的指令执行过程采用先行缓冲栈
8、的指令执行过程 先行读数栈,先行操作栈,后行写数栈。理想情况下，指令执行部件应该一直忙碌。理想情况下，指令执行部件应该一直忙碌。连续执行连续执行n n条指令的时间为：条指令的时间为：5.1.5 5.1.5 先行缓冲栈先行缓冲栈设置先行缓冲栈的目的：设置先行缓冲栈的目的：使指令分析器和指令执行部件能够独使指令分析器和指令执行部件能够独立工作。立工作。1.1.先行指令缓冲栈：先行指令缓冲栈：处于主存储器与指令分析器之间用它来平滑主存储器取指令和指令分析器使用指令之间的速度用它来平滑主存储器取指令和指令分析器使用指令之间的速度差异差异指令分析器对已经存放在先行指令缓冲栈里的指令进行预处理，指令分析器
9、对已经存放在先行指令缓冲栈里的指令进行预处理，把处理之后的指令送入先行操作栈把处理之后的指令送入先行操作栈RRRR型指令型指令，不必处理，直接送先行缓冲栈RSRS型指令型指令，指令分析器计算出主存有效地址后送入先行读数栈，用该先行读数栈负责到主存中读取操作数，同时用先行读数栈的寄存器编号替换指令中的主存地址码部分，形成RR*指令送先行操作栈RIRI型指令型指令，指令中的立即数送先行读数栈，用该先行读数栈的寄存器编号替换指令中的立即数部分，形成RR*指令送先行缓冲栈转移指令转移指令，一般在指令分析器中直接执行。2.2.先行操作栈先行操作栈处于指令分析器和运算控制器之间使指令分析器和运算器能够各自
10、独立工作。使指令分析器和运算器能够各自独立工作。采用先进先出方式工作，由指令寄存器堆和控制逻辑组成。3.3.先行读数栈先行读数栈由一组缓冲寄存器和有关控制逻辑组成，处于主存储器与运算器之间平滑运算器与主存储器的工作平滑运算器与主存储器的工作每个缓冲寄存器由先行地址缓冲寄存器、先行操作数缓冲寄存器和标志字段三部分组成。也可以把先行地址缓冲寄存器和先行操作数缓冲寄存器合为一个。当先行地址缓冲寄存器收到从指令分析器中送来的有效地址时，就把地址的有效标志置位，并向主存申请读操作数。读出的操作数存放在先行操作数缓冲寄存器中或覆盖掉地址寄存器中的地址，同时要置位数据标志。4.4.后行写数栈后行写数栈由一组
11、缓冲寄存器和有关控制逻辑组成，每个后行缓冲寄存器由后行地址缓冲寄存器、后行数据缓冲寄存器和标志字段三部分组成。指令分析器遇到向主存写结果的指令时，把形成的有效地址送入后行写数栈的地址寄存器中，并用该地址寄存器的编号替换指令的目的地址部分，形成RR*指令送入先行操作栈。当运算器执行这条RR*型写数指令时，只要把写到主存的数据送到后行写数栈的数据寄存器只要把写到主存的数据送到后行写数栈的数据寄存器中即可。中即可。5.5.采用先行控制方式时一个程序的执行情况：采用先行控制方式时一个程序的执行情况：5.1.6 5.1.6 缓冲深度的设计方法缓冲深度的设计方法以静态分析为主，通过模拟来确定缓冲深度。以静
12、态分析为主，通过模拟来确定缓冲深度。1.1.先行指令缓冲栈的设计先行指令缓冲栈的设计 考虑两种极端情况：假设缓冲深度为DI(1)(1)先行指令缓冲栈已经充满先行指令缓冲栈已经充满指令流出的速度最快指令流出的速度最快，例如连续分析RR型指令，设这种指令序列的最大长度为L1，平均分析一条这种指令的时间为t1；指令流入的速度最慢指令流入的速度最慢，设平均取一条指令的时间为t2。从主存储器中取到先行指令缓冲栈中的指令条数是L1DI条。应该满足如下关系：L1 t1(LIDI)t2 计算出缓冲深度为：如果这种指令流的连续长度超过L1，则先行指令缓冲栈失去作用。(2)(2)先行指令缓冲栈原来为空先行指令缓冲
13、栈原来为空输入端指令流入的速度最快输入端指令流入的速度最快，每次取指令的时间最短；设这种指令序列的最大长度为 L2，平均取一条这种指令的时间为 t2；输出端指令流出的速度最慢输出端指令流出的速度最慢，指令分析器连续分析最难分析的指令；设平均分析一条指令的时间为 t1。分析的指令条数是L2DI条。应该满足如下关系：(L2DI)t1LI t2 计算出缓冲深度为：如果这种指令流的连续长度超过L2，先行指令缓冲栈失去缓冲作用。2.2.设计举例设计举例在一般处理机中连续执行短指令的概率大。例例5.15.1：一个采用先行控制方式的处理机，指令分析器分析一条指令用一个周期，到主存储器中取一条指令装入先行指令
14、缓冲栈平均用4个周期，如果这种指令的平均长度为9，即90的指令是执行时间短的指令。解：解：计算先行指令缓冲栈的缓冲深度为：3.3.先行指令缓冲栈的工作时间关系先行指令缓冲栈的工作时间关系第1个周期，取走指令k+1，请求取指令第4个周期末尾，指令k+8取到先行指令缓冲栈第8个周期末尾，指令k+9取到先行指令缓冲栈第9个周期，分析指令k+9，先行指令缓冲栈空第10个周期，指令分析器等待4.4.其余缓冲栈的设计原则其余缓冲栈的设计原则一般有关系：一般有关系：DIDCDRDW 其中：DI是先行指令缓冲栈的缓冲深度，DC是先行操作栈的缓冲深度，DR是先行读数栈的缓冲深度，DW是后行写数栈的缓冲深度。例如
15、：例如：IBM370/165机：DI4，DC3，DR2，DW1。我国研制的两台大型计算机：DI8，DCDR4，DW2。DI12，DCDR6，DW2。空间并行性空间并行性：设置多个独立的操作部件设置多个独立的操作部件 时间并行性时间并行性：分时使用同一个部件的不同部分分时使用同一个部件的不同部分 5.2.1 流水线工作原理流水线工作原理 5.2.2 流水线的分类流水线的分类 5.2.3 线性流水线的性能分析线性流水线的性能分析 5.2.4 非线性流水线的调度非线性流水线的调度5.2 5.2 流水线技术流水线技术5.2.1 5.2.1 流水线工作原理流水线工作原理1.1.流水寄存器流水寄存器流水线
16、的每一个阶段称为流水步流水步、流水步骤、流水段流水段、流水线阶段、流水功能段、功能段功能段、流水级流水级、流水节拍等。在每一个流水段的末尾或开头必须设置一个寄存器，称为流水寄存器、流水锁存器、流水闸门寄存器等流水寄存器、流水锁存器、流水闸门寄存器等。加入流水寄存器，会增加指令的执行时间。在一般流水线时空图中不画出流水寄存器。2.2.一种指令流水线一种指令流水线一般4至12个流水段，8个流水段的称为超流水线处理机3.3.流水线时空图流水线时空图 一个浮点加法器流水线的时空图一个浮点加法器流水线的时空图4.4.流水线的主要特点流水线的主要特点 P279P279只有连续提供同类任务才能发挥流水线效率
17、只有连续提供同类任务才能发挥流水线效率尽量减少因条件分支造成的“断流”通过编译技术提供连续的相同类型操作每个流水线段都要设置一个流水寄存器每个流水线段都要设置一个流水寄存器时间开销：流水线的执行时间加长是流水线中需要增加的主要硬件各流水段的时间应尽量相等各流水段的时间应尽量相等 流水线处理机的基本时钟周期等于时间最长的流水段的时间长度。流水线需要有流水线需要有“装入时间装入时间”和和“排空时间排空时间”5.2.2 5.2.2 流水线的分类流水线的分类1.1.线性流水线与非线性流水线线性流水线与非线性流水线 流水线的各个流水段之间是否有反馈信号线性流水线线性流水线（Linear Pipelini
18、ng）：将流水线的各段逐个串接起来，输入数据从流水线的一端进入，从另一端输出。数据在流水线中的各个功能段流过时，每一个功能段都流过一次，而且仅流过一次。非线性流水线非线性流水线（Nonlinear Pipelining）：某些流水段之间有反馈回路或前馈回路。线性流水线能够用流水线连接图唯一表示非线性流水线必须用流水线连接图和流水线预约表共同表示2.2.按照流水线的级别来分按照流水线的级别来分 处理机级流水线处理机级流水线，又称为指令流水线指令流水线。例如：在采用先行控制器的处理机中，各功能部件之间的流水线 部件级流水线部件级流水线(操作流水线操作流水线)如浮点加法器流水线 宏流水线宏流水线(M
19、acro Pipelining)处理机之间的流水线称，每个处理机对同一个数据流的不同部分分别进行处理。3.3.单功能流水线与多功能流水线单功能流水线与多功能流水线 单功能流水线：单功能流水线：只能完成一种固定功能的流水线。只能完成一种固定功能的流水线。Cray-1计算机种有12条，YH-1计算机有18条 Pentium有一条5段定点和一条8段浮点流水线。Pentium有两条定点和一条浮点指令流水线。多功能流水线：多功能流水线：流水线的各段通过不同连接实现不同功能流水线的各段通过不同连接实现不同功能即根据所需要的功能在给定的流水线上选择某些部件组合来实现，因此，对于一条流水线可以实现多个功能。T
20、exas公司的ASC机，8段流水线，能够实现：定点加减法、定点乘法、浮点加法、浮点乘法、逻辑运算、移位操作、数据转换、向量运算等。n4.4.静态流水线与动态流水线静态流水线与动态流水线n静态流水线静态流水线：同一段时间内，多功能流水线中的各个功能段：同一段时间内，多功能流水线中的各个功能段只能按照一种方式连接，实现一种固定的功能。只有当按照只能按照一种方式连接，实现一种固定的功能。只有当按照这种连接方式工作的所有任务都流出流水线之后，多功能流这种连接方式工作的所有任务都流出流水线之后，多功能流水线才能重新进行连接，以实现其它功能。水线才能重新进行连接，以实现其它功能。动态流水线动态流水线：在同
21、一段时间内，各段可以按照不同的方式连接，：在同一段时间内，各段可以按照不同的方式连接，同时执行多种功能。当然实现多种连接方式必须要求流水线同时执行多种功能。当然实现多种连接方式必须要求流水线中的各个功能部件之间不能发生冲突。中的各个功能部件之间不能发生冲突。5.5.流水线的其他分类方法流水线的其他分类方法按照数据表示方式：标量流水线和向量流水线标量流水线和向量流水线按照控制方式：同步流水线和异步流水线同步流水线和异步流水线n按照流水线输出端流出的任务与输入端流入的任务的顺序是否相同：顺序流水线与乱序流水线顺序流水线与乱序流水线，乱序流水线又称为无序流水线、错序流水线或异步流水线等。5.2.3
22、5.2.3 线性流水线的性能分析线性流水线的性能分析n 主要指标：吞吐率、加速比和效率吞吐率、加速比和效率n1.1.吞吐率（吞吐率（Though PutThough Put）n单位时间内流水线所完成的任务数量或输出的结果数量。n流水线吞吐率的最基本公式：流水线吞吐率的最基本公式：n 其中：n为任务数，n k为完成n个任务所用的时间。n各段执行时间相等，输入连续任务情况下，完成n个任务需要的总时间为：n Tk(kn1)tn 其中：k 为流水线的段数，t为时钟周期。Tk=k t+(n-1)t=(k+n-1)t 吞吐率为：吞吐率为：最大吞吐率为：最大吞吐率为：各段时间不等，完成各段时间不等，完成n
23、n个连续任务：个连续任务：吞吐率：吞吐率：最大吞吐率：最大吞吐率：(1)(1)将将“瓶颈瓶颈”部分再细分部分再细分（如果可分的话）（如果可分的话）流水线各段执行时间不相等的解决办法流水线各段执行时间不相等的解决办法2.2.加速比（加速比（SpeedupSpeedup）不使用流水线所用的时间与使用流水线所用的时间之比称为流不使用流水线所用的时间与使用流水线所用的时间之比称为流水线的加速比。水线的加速比。计算加速比的基本公式：计算加速比的基本公式：各段执行时间相等，输入连续任务情况下,加速比：最大加速比：流水线的各段时间不等，一条k段线性流水线完成n个连续任务的实际加速比为：当流水线段数增加时，需
24、要连续输入的任务 数也必须增加n3.3.效率（效率（EfficiencyEfficiency）n流水线的设备利用率。在时空图上反映为流水线的设备利用率。在时空图上反映为n个任务占用的时空区个任务占用的时空区与与k个功能段总的时空区之比。个功能段总的时空区之比。n计算流水线效率的一般公式：计算流水线效率的一般公式：n各流水段时间相等，输入n个连续任务，流水线的效率为：n最高效率为：n各流水段时间不等，n输入n个连续任务，n流水线效率为：EnkTk Tk=个任务占用的时空区个流水段的总的时空区0n各段设备量或价格不等时，流水线的效率为：流水线的效率为：n n即：n n其中，aik，且k。n流水线的
25、吞吐率、流水线的吞吐率、加速比与效率的关系：加速比与效率的关系：n因为：n因此：ETPt，SkE4.4.流水线最佳段数的选择流水线最佳段数的选择采用顺序执行方式完成一个任务的时间为t在同等速度的 k 段流水线上执行一个任务的时间为：tkd(d为流水锁存器的延迟时间)流水线的最大吞吐率为：P=1(tkd)流水线的总价格估计为：Cab k，其中：a为功能段身的总价格，b为每个锁存器的价格 把流水线的性能价格比PCR定义为：求PCR的最大值为：5.5.流水线性能分析举例流水线性能分析举例对于单功能线性流水线，输入连续任务的情况，通过上面给出的公式很容易计算出流水线的吞吐率、加速比和效率。对于输入不连
26、续任务，或多功能流水线，通常采用基本公式计算。例例5.2：用一条4段浮点加法器流水线求8个浮点数的和：ZABCDEFGH解：解：Z(AB)(CD)(EF)(GH)解：解：5.2.4 5.2.4 非线性流水线的调度非线性流水线的调度非线性流水线调度的任务是要找出一个最小的循环周期，按照非线性流水线调度的任务是要找出一个最小的循环周期，按照这周期向流水线输入新任务，流水线的各个功能段都不会发这周期向流水线输入新任务，流水线的各个功能段都不会发生冲突，而且流水线的吞吐率和效率最高。生冲突，而且流水线的吞吐率和效率最高。1.1.非线性流水线的表示非线性流水线的表示线性流水线能够用流水线连接图唯一表示对
27、于非线形流水线，连接图不能唯一表示工作流程，因此，引入流水线预约表例如：非线形流水线的连接图和预约表非线形流水线的连接图和预约表 一张预约表可能与多个流水线连接图相一张预约表可能与多个流水线连接图相对应对应 一个流水线连接图对应与多张预约表一个流水线连接图对应与多张预约表2.2.非线性流水线的冲突非线性流水线的冲突 启动距离：启动距离：连续输入两个任务之间的时间间隔 流水线冲突：流水线冲突：几个任务争用同一个流水段1/9/2023573.3.无冲突调度方法无冲突调度方法由及其学生于1971年提出禁止向量禁止向量：预约表中每一行任意两个“”之间距离的集合。上例中为（3 3，4 4，6 6）冲突向
28、量冲突向量：C（CmCm-1C2C1）其中：m是禁止向量中的最大值。如果i在禁止向量中，则Ci1，否则Ci0。上例中C C(101100)(101100)例例5.35.3：一条4功能段的非线性流水线，每个功能段的延迟时间都相等，它的预约表如下：(1)写出流水线的禁止向量和初始冲突向量。(2)画出调度流水线的状态图。(3)求最小启动循环和最小平均启动距离。(4)求平均启动距离最小的恒定循环。解解：(1)(1)禁止向量为：禁止向量为：(2，4，6)初始冲突向量：初始冲突向量：S=101010S=101010(2)(2)构造状态图构造状态图 S S逻辑右移逻辑右移2 2、4 4、6 6位时，不作任何
29、处理，位时，不作任何处理，逻辑右移逻辑右移1 1、3 3、5 5和大于等于和大于等于7 7时：时：S右移1位之后：010101101010111111111111，S右移3位之后：000101101010101111101111，S右移5位之后：000001101010101011101011，S右移7位或大于7位后：还原到它本身。101111右移5位之后：000001101010101011101011，101011右移3位之后：000101101010101111101111，101011右移5位之后：000001101010101011101011。简单循环：简单循环：状态图中各种冲突向
30、量只经过一次的启动状态图中各种冲突向量只经过一次的启动循环。循环。(3)(3)最小的启动循环最小的启动循环为为（1，7）和（3，5）,平均启动距离为平均启动距离为 4 4。(4)(4)启动距离最小的恒定循环为（启动距离最小的恒定循环为（5 5）4.4.优化调度方法优化调度方法于1972年提出流水线最小平均启动距离的限制范围：(1)(1)最小平均启动距离的下限是预约表中任意一行最小平均启动距离的下限是预约表中任意一行里里“”的最多个数。的最多个数。(2)(2)最小平均启动距离小于等于状态图中任意一个最小平均启动距离小于等于状态图中任意一个简单循环的平均启动距离。简单循环的平均启动距离。(3)(3
31、)最小平均启动距离的上限是冲突向量中最小平均启动距离的上限是冲突向量中1 1的个数的个数再加上再加上1 1。1992年，又证明了上述限制范围。最有用的是第1条。预约表中“”最多的行一定是瓶颈流水段瓶颈流水段对于例5.3的预约表，在同一行中“”最多的为2个，因此，最小平均距离可以达到最小平均距离可以达到2。最小启动循环可以是(2)、(1,3)、(1,1,4)、(1,2,3)、。现取恒定循环恒定循环(2)(2)。每一行中与第每一行中与第1 1个个“”的距离为的距离为2 2的倍数的位置都要的倍数的位置都要预留出来。预留出来。S3行的第2个“”从周期5延迟到周期6。为此，S2行的第2个“”从周期6延迟
32、到周期7；S1行的第2个“”从周期7延迟到周期8。实际上，只要在流水段S4的输出端到流水段S3的输入端中间插入一个非计算延迟非计算延迟D1。在非线性流水线中，“”最多的流水段一定是“瓶颈“流水段。实现最优调度的目标是使“瓶颈瓶颈”流水段处于忙碌状流水段处于忙碌状态，没有空闲周期。态，没有空闲周期。最优调度方法能够使非线性流水线的吞吐率、加速比和效率达到最优。n在一个5段的流水线处理机上需经9t才能完成一个任务，各段执行时间均为t，任务处理过程对各段使用时间的预约表如下：n画出流水线的状态图，并由状态图得出流水线的最优调度策略和最大吞吐率。n按最优调度策略输入6个任务，求流水线的实际吞吐率、加速
33、比和效率。5.3 5.3 相关性分析技术相关性分析技术5.3.1 数据相关数据相关5.3.2 控制相关控制相关5.3.3 条件分支对流水线的影响条件分支对流水线的影响5.3.4 静态分支预测技术静态分支预测技术5.3.5 动态分支预测技术动态分支预测技术5.3.6 提前形成条件码提前形成条件码5.3.7 精确断点与不精确断点精确断点与不精确断点5.3.1 5.3.1 数据相关数据相关数据相关：数据相关：在执行本条指令的过程中，如果用到的指令、操作在执行本条指令的过程中，如果用到的指令、操作数、变址量等是前面指令的执行结果，这种相关称为数据相数、变址量等是前面指令的执行结果，这种相关称为数据相关
34、。关。控制相关：控制相关：由条件分支指令、转子程序指令、中断等引起的相由条件分支指令、转子程序指令、中断等引起的相关关。解决数据相关的方法有两种：解决数据相关的方法有两种：推后处理推后处理设置专用路径设置专用路径。1.1.指令相关指令相关发生指令相关的情况：发生指令相关的情况：n：STORE R1,STORE R1,n+1+1 n+1+1：满足关系：满足关系：结果地址结果地址(n)指令地址指令地址(n+1)+1)当第当第n条指令还没有把执行结果写到主存之前，取出条指令还没有把执行结果写到主存之前，取出的第的第n+1+1条指令显然是错误的。条指令显然是错误的。在k个流水段的流水线处理机中，第n条
35、指令要修改从第n+1到第n+k 指令中的任意一条指令，都可能造成程序执行结果发生错误。在采用先行控制方式的处理机中，如果执行部件正在执行第n条指令，与下述情况之一发生相关，都可能造成程序执行结果发生错误。存放在先行操作栈中的指令正在指令分析器中分析的指令已经预取到先行指令缓冲栈中的指令指令执行结果还在后行缓冲栈中的指令更严重的是：有些分支指令，可能已经在指令分析器中执行完成。解决指令相关的根本办法是：解决指令相关的根本办法是：在程序执行过程中不允许修改指令。在程序执行过程中不允许修改指令。现代程序设计方法要求程序具有再入性，可以被递归调用等，也要求不修改指令。在IBM370系列机中，用“执行指
36、令”来解决：在程序执行过程中既能够修改指令，程序又具有再入性。“执行指令”执行由第二地址(X2)+(B2)+D2)决定的主存数据区中的指令。2.2.主存操作数相关主存操作数相关发生主存操作数相关的指令序列：n：OP A1，A2，A3 ；A1(A2)OP(A3)n+1：OP A1，A2，A3 ；A1(A2)OP(A3)出现下列情况之一，就发生主存操作数相关：A1（n）A2（n1）A1（n）A3（n1）解决办法：解决办法：运算结果写到通用寄存器，而不写到主存运算结果写到通用寄存器，而不写到主存对于访问主存储器的请求，写结果的优先级高于读操对于访问主存储器的请求，写结果的优先级高于读操作数。作数。3
37、.3.通用寄存器数据相关通用寄存器数据相关发生寄存器数据相关的可能性很大，影响面也很大 n：OP R1，A2 ；R1(R1)OP(A2)n+1：OP R1，R2 ；R1(R1)OP(R2)发生发生R1(n)R1(n1)称为称为R1数据相关。数据相关。发生发生R1(n)R2(n1)称为称为R R2数据数据相关。相关。解决通用寄存器数据相关的方法：解决通用寄存器数据相关的方法：方法一：方法一：把读操作数、写运算结果与指令执行合在一把读操作数、写运算结果与指令执行合在一个节拍。个节拍。从数据从通用寄存器读出，在运算器中完成运算，结果写回通用寄存器的整个回路中，只有通用寄存器是时序逻辑。在通用寄存器到
38、运算器之间建立直接数据通路，即不设置缓冲寄存器或锁存器，则不会发生通用寄存器数据相关。这种情况下，实际上不需要分析周期，在一个节拍中就可以完成从通用寄存器中通过两个多路选择器分别读操作数到通用寄存器。方法二：方法二：建立建立相关专用通路相关专用通路(ByPass)(ByPass)由于发生寄存器数据相关的情况很普遍，一般计算机系统都采用专用数据通路。把读通用寄存器、执行操作和写结果分为3个周期，或2个周期。采用专用数据通路能够缩短1至2个周期。变址相关：变址相关：在采用变址寻址方式的处理机中，由于变址量放在寄存器中，因此，可能发生与通用寄存器数据相关类似变址相关4.LOAD4.LOAD相关相关
39、LOAD操作的执行时间可能比较长 n：LOAD R1，A ；R1(A)n+1：ADD R1，R2 ；R1(R1)OP(R2)如果 R1(n)R2(n1)，或 R1(n)R1(n1)，则发生LOAD数据相关。解决方法：解决方法：方法一：方法一：由编译器在由编译器在LOADLOAD之后插入不发生数据相之后插入不发生数据相关的指令，关的指令，由于由于LOAD的执行时间不确定，不能根本解决问题方法二：方法二：由硬件自动插入空操作，直到由硬件自动插入空操作，直到LOADLOAD操作操作完成完成在单条流水线处理机中，也可以停止节拍发生器，直到数据从存储器中读出为止。5.3.2 5.3.2 控制相关控制相关
40、因程序的执行方向可能被改变而引起的相关，也称为全局相关全局相关。主要包括：无条件转移、一般条件转移、复合条件转无条件转移、一般条件转移、复合条件转移、中断移、中断等。1.1.无条件转移无条件转移在流水线处理机中，无条件转移指令不进入执行流水段，一般在指令译码阶段就实际执行完成。如果在处理机中设置有指令先行缓冲栈，则要全部或部分作废先行指令缓冲栈中的指令。如果转移目标指令如果转移目标指令L L不在先行指令缓冲栈中不在先行指令缓冲栈中，则要将先行指令缓冲栈中的所有指令全部作废，并等待取出转移目标指令L。如果转移目标指令如果转移目标指令L L在先行指令缓冲栈中在先行指令缓冲栈中，只要作废先行指令，只
41、要作废先行指令缓冲栈中的部分指令。缓冲栈中的部分指令。无条件转移指令一般对指令执行部件的工作不会造成影响。为进一步减少无条件转移指令造成的影响，在先行指令缓冲栈在先行指令缓冲栈的入口处增设一个专门处理无条件转移指令的指令分析器的入口处增设一个专门处理无条件转移指令的指令分析器P270P2702.2.一般条件转移一般条件转移 k：;置条件码CC k+1：JMP(CC)L ;如果CC为真转向L L：当条件码是上一条指令产生时，相关最当条件码是上一条指令产生时，相关最严重严重P271P271无论转移是否成功，第k1条转移指令都在指令分析阶段就已经执行完成。无论转移不成功或不成功，指令分析器要停顿一段
42、时间，无论转移不成功或不成功，指令分析器要停顿一段时间，等待条件码产生。等待条件码产生。如果转移成功：指令L已经在先行指令缓冲栈，指令分析器接着“分析L”，如果指令L不在先行指令缓冲栈，指令分析器要等待一个周期。转移不成功，对程序执行影响不大，当转移成功时，不仅指令执行过程变成完全串行，而当转移成功时，不仅指令执行过程变成完全串行，而且要作废先行指令缓冲栈中的大量指令。且要作废先行指令缓冲栈中的大量指令。在采用流水线方式的处理机中，要通过软件与硬件的在采用流水线方式的处理机中，要通过软件与硬件的多种手段来近可能地降低转移成功的概率，减少转多种手段来近可能地降低转移成功的概率，减少转移成功造成的
43、影响。移成功造成的影响。3.3.复合条件转移复合条件转移 k k：OP L;OP L;产生条件码，并决定是否转向产生条件码，并决定是否转向L L L L：如果转移不成功：不造成任何影响，就象普通的运算型指令一样如果转移成功：造成的影响比一般条件转移指令还要如果转移成功：造成的影响比一般条件转移指令还要大得多。大得多。全部或部分作废先行指令缓冲栈、先行操作栈、先行读数栈和指令分析器中的指令。必须采取策略，减小转移成功造成的影响。必须采取策略，减小转移成功造成的影响。5.3.3 5.3.3 条件分支对流水线的影响条件分支对流水线的影响处理好条件转移和中断的关键问题有两个：要确保流水线能够正常工作要
44、确保流水线能够正常工作减少因减少因“断流断流”引起的吞吐率和效率的下降引起的吞吐率和效率的下降1.1.条件分支的处理方法条件分支的处理方法条件转移指令对流水线的影响很大，必须采取措施来减少这种影响。可能的措施有：(1)(1)延迟转移技术和指令取消技术延迟转移技术和指令取消技术只能用于单流水线处理机中，且流水线的级数不能太只能用于单流水线处理机中，且流水线的级数不能太多；多；据统计，据统计，编译器调度一条指令成功的概率在编译器调度一条指令成功的概率在90以上，以上，而调度两条指令成功的概率只有而调度两条指令成功的概率只有40左右。左右。当没有合适的指令可调度时，编译器只能插入空操作。(2)(2)
45、动态分支预测技术动态分支预测技术根据近期转移是否成功的记录来预测下一次转移的方根据近期转移是否成功的记录来预测下一次转移的方向。向。所有的动态转移预测方法都能够随程序的执行过程动所有的动态转移预测方法都能够随程序的执行过程动态地改变转移的预测方向。态地改变转移的预测方向。(3)(3)静态分支预测技术静态分支预测技术转移预测的方向是确定的，或者预测转移不成功，或者预测转移成功，在程序实际执行过程中，转移预测的方向不能改变。在程序实际执行过程中，转移预测的方向不能改变。静态转移预测可以只用软件实现，也可用硬件来实现，还可以在转移的两个方向上都预取指令。TI公司的SuperSPARC处理机采用了静态
46、转移预测技术，而且设置有转移目标缓冲栈，在两个方向上都预取指令。2.2.条件分支在流水线中的执行过程条件分支在流水线中的执行过程因为第i条指令所需要的条件码由第i-1条指令给出；在一条由k个功能段的流水线中，第i-1条指令要等到第i+k-2条指令进入流水线时才能形成条件码。转移不成功，猜测正确，流水线的吞吐率和效率没有降低，转移成功，猜测错误，要先作废流水线中已经执行的转移成功，猜测错误，要先作废流水线中已经执行的i+1i+1、i+2i+2、i+k-2i+k-2指令；然后再从分支点开指令；然后再从分支点开始执行第始执行第P P、p+1p+1、指令。一条指令。一条k k段流水线有段流水线有k-2
47、k-2个功能段是浪费的。个功能段是浪费的。条件分支指令在流水线中的执行过程条件分支指令在流水线中的执行过程当分支的执行方向猜测错误时，可能造成程序执行结当分支的执行方向猜测错误时，可能造成程序执行结果发生错误。果发生错误。例如，若第i+1条指令是：(R1)(R2)R1，寄存器R1中内容就被破坏，整个程序执行的结果是错误的。目前的处理机有两种做法：目前的处理机有两种做法：一种方法是只进行指令译码和准备好运算所需要的操一种方法是只进行指令译码和准备好运算所需要的操作数，在转移条件没有形成之前不执行运算；作数，在转移条件没有形成之前不执行运算；另一种方法是一直执行到运算完成，但不送回运算结另一种方法
48、是一直执行到运算完成，但不送回运算结果。果。3.3.条件分支对流水线性能的影响条件分支对流水线性能的影响P313P313假设条件转移指令在一般程序中所占的比例为p，转移成功的概率为q。n条指令的总的执行时间是：条指令的总的执行时间是：TK-IF(n+k-1)t+npq(k-1)t有条件转移影响的流水线吞吐率为：有条件转移影响的流水线吞吐率为：有条件转移影响的流水线最大吞吐率为：有条件转移影响的流水线最大吞吐率为：流水线吞吐率下降的百分比为：流水线吞吐率下降的百分比为：在典型程序中，转移指令占的比例为p20，转移成功的概率为60。对于一条8功能段的指令流水线，由于条件转移指令的影响，流水线的最大
49、吞吐率要下降：如果指令流水线的功能段数为10，由于条件转移指令的影响，流水线的最大吞吐率将下 降一半以下：%46)18(60.020.01)18(60.020.08=-+-=D5.3.4 5.3.4 静态分支预测技术静态分支预测技术静态分支预测：静态分支预测：在程序执行过程中转移预测方向不能改变在程序执行过程中转移预测方向不能改变动态分支预测：动态分支预测：在程序执行过程中能够改变转移预测方向在程序执行过程中能够改变转移预测方向本节讲静态预测技术,下节讲动态预测技术1.1.软件软件“猜测法猜测法”目标：目标：通过编译器尽量降低转移成功的概率。通过编译器尽量降低转移成功的概率。例如：例如：对于循
50、环程序，普通编译器生成的目标代码，转移成功的概率很高，不成功的只有一次。这种编译结果对流水线极为不利。P273 软件软件“猜测法猜测法”：通过编译器降低转移成功的概率通过编译器降低转移成功的概率2.2.硬件硬件“猜测法猜测法”方法：方法：通过改变硬件结构来降低转移指令对流水线的通过改变硬件结构来降低转移指令对流水线的影响影响在先行指令缓冲栈的入口处设置一个简单的指令分析器，当检测到转移指令时，就把转移目标地址L送入先行程序计数器PC1中，同时保留当前PC1中的内容到另一寄存器中。转移成功，猜测正确。对转移指令对流水线不造成影响。转移不成功，用保存下来的地址恢复PC1和PC。软硬件共同配合，都往