计算机系统结构第五章标量处理机.ppt

第五章 标量处理机,2019/6/12,2019/6/12,2,本章主要内容,5.1 先行控制技术 5.2 流水线技术 5.3 相关性分析技术 5.4 超标量处理机 5.5 超流水线处理机 5.6 超标量超流水线处理机,2019/6/12,3,标量处理机,只有标量数据表示和标量指令系统的处理机称为标量处理机，是最常用最普通的处理机。 设计处理机的主要任务就是缩短解释指令的时间，提高处理机指令的执行速度： 提高处理机的工作主频。5、60年代主要采用这种技术，每3、4年处理机的速度要提高一个数量级。 采用更好的算法和设计更好的功能部件，如采用RISC等。 多条指令并行执行。指令级的并行技术。 流水线技术。 处理机中设置多个独立的功能部件，如浮点运算器，定点运算器，访存部件等。 超长指令技术。,2019/6/12,4,5.1 先行控制技术,先行控制技术的关键是采用缓冲技术和预处理技术，以及两者都采用，通过对指令流和数据流的预处理和缓冲，能够尽量使指令分析器和指令执行部件独立工作并始终处于忙碌状态。 5.1.1 指令的重叠执行方式 5.1.2 先行控制方式的原理 5.1.3 处理机结构 5.1.4 指令执行序列 5.1.5 先行缓冲栈 5.1.6 缓冲深度的设计方法,2019/6/12,5,指令的重叠执行方式,一条指令的执行可以分为多个阶段，具体分法视处理机而定，一般可以分为三个阶段： 取指令是指按照指令计数器的内容访问主存，取出一条指令送到指令寄存器。 分析指令是指对指令的操作码进行译码，按照给定的寻址方式和地址字段内容形成操作数地址，并用这个地址读出操作数，操作数可以在主存也可以在寄存器。 执行指令是根据操作码的要求，完成指令规定的功能，把结果写到主存或者寄存器。 指令分析或者指令执行阶段还得修改指令计数器的更新，为下一条指令作准备。,2019/6/12,6,指令的重叠执行方式,1.顺序执行方式 执行n条指令所用的时间为： 如果每段时间都为t，则执行n条指令所用的时间为：T3 n t 主要优点：控制简单，节省设备。 主要缺点：速度慢，功能部件的利用率低。,2019/6/12,7,2.一次重叠执行方式 如果两个过程的时间相等，则执行n条指令的时间为：T(1+2n)t 主要优点： 指令的执行时间缩短， 功能部件的利用率明显提高。 主要缺点： 需要增加一些硬件， 控制过程稍复杂。,指令的重叠执行方式(续),2019/6/12,8,3.二次重叠执行方式 如果三个过程的时间相等，执行n条指令的时间为：T(2n）t 在理想情况下，处理机中同时有三条指令在执行。 处理机的结构要作比较大的改变，需要采用先行控制技术。,指令的重叠执行方式(续),2019/6/12,9,先行控制方式的原理,1.采用二次重叠执行方式必须解决两个问题： (1)有独立的取指令部件、指令分析部件和指令执行部件 把一个集中的指令控制器，分解成三个独立的控制器： 存储控制器、指令控制器、运算控制器。 (2)要解决访问主存储器的冲突问题 取指令、分析指令、执行指令都可能要访问存储器。,2019/6/12,10,2.解决访存冲突的方法： (1)采用低位交叉存取方式： 这种方法不能根本解决冲突问题。 取指令、读操作数、写结果。 (2)主存分为两个独立的存储器：独立的指令存储器和数据存储器。 如果再规定，执行指令所需要的操作数和执行结果只写到通用寄存器，则取指令、分析指令和执行指令就可以同时进行。 在许多高性能处理机中，有独立的指令Cache和数据Cache。这种结构被称为哈佛结构。,先行控制方式的原理（续）,2019/6/12,11,(3)采用先行控制技术 采用先行控制技术的关键是缓冲技术和预处理技术。 缓冲技术通常用在工作速度不固定的两个功能部件之间。设置缓冲栈的目的是用来以平滑功能部件之间的工作速度。 在采用了缓冲技术和预处理技术之后，运算器能够专心于数据的运算，从而大幅度提高程序的执行速度。,先行控制方式的原理（续）,2019/6/12,12,处理机结构,1.三个独立的控制器： 存储控制器、指令控制器、运算控制器。 2.四个缓冲栈： 先行指令缓冲栈、先行读数缓冲栈、先行操作栈、后行写数栈。 3.处理机组成,2019/6/12,13,4.先行指令缓冲栈的组成 作用：只要指令缓冲栈没有充满，就自动发出取指令的请求。 指令分析器每分析完一条指令，自动向指令缓冲栈发出取下一条指令的请求，指令取出后就把先行指令缓冲栈中的指令作废。 分析指令速度和从主存取指令的速度是随机的，指令缓冲栈的指令数目是动态的。 设置两个程序计数器： 先行程序计数器PC1，用来指示取指令， 现行程序计数器PC，记录指令分析器正在分析的指令地址。,处理机结构（续）,2019/6/12,14,处理机结构（续）,先行缓冲站的组成,指令缓冲存储器堆，采用先进先出的方式，保证指令的执行顺序不致混乱。,2019/6/12,15,处理机结构（续）,先行控制方式中的一次重叠执行,重叠部分，无论谁先结束，都不能提前执行下一条指令，需要等待。 无论任何时刻，在指令分析部件和指令执行部件内都只有相邻的两条指令重叠执行，处理机只需要设置一套指令分析部件，指令控制器；一套指令执行部件，运算控制器和运算器。控制方式简单。 所需要时间为T=（1+n）t,2019/6/12,16,处理机结构（续）,5.存在的主要问题： 计算机指令系统复杂，各类指令“分析”和“执行”的时间相差很大，分析指令和执行指令常常相互等待，造成部件的浪费。 分析k+1操作所需要的操作数正好是执行k的结果，不能重叠执行，发生数据相关，还有控制相关，变址相关。 转移或转子程序指令时，程序的执行过程不是顺序的，先行指令缓冲栈中预取指令和分析的下一条指令都可能要作废。,2019/6/12,17,指令执行时序,设置了指令缓冲栈，取指令的时间就可以忽略不计。 一条指令的执行可分为2个过程。 1.分析指令和执行指令时间不相等时的情况。,2019/6/12,18,指令执行时序,2.采用先行缓冲栈的指令执行过程 先行读数栈,先行操作栈,后行写数栈。 理想情况下，指令执行部件应该一直忙碌。 连续执行n条指令的时间为：,2019/6/12,19,先行缓冲栈,设置先行缓冲栈的目的：使指令分析器和指令执行部件能够独立工作。 1.先行指令缓冲栈： 处于主存储器与指令分析器之间。 用它来平滑主存储器取指令和指令分析器使用指令之间的速度差异。 RR型指令，不必处理，直接送先行缓冲栈。 RS型指令，主存有效地址送先行读数栈，用该先行读数栈的寄存器编号替换指令中的主存地址码部分，形成RR*指令送先行缓冲栈。,2019/6/12,20,RI型指令，指令中的立即数送先行读数栈，用该先行读数栈的寄存器编号替换指令中的立即数部分，形成RR*指令送先行缓冲栈。 转移指令，一般在指令分析器中直接执行。 2.先行操作栈 处于指令分析器和运算控制器之间。 使指令分析器和运算器能够各自独立工作。 采用先进先出方式工作，由指令寄存器堆和控制逻辑组成。,先行缓冲栈（续）,2019/6/12,21,3.先行读数栈 处于主存储器与运算器之间。 平滑运算器与主存储器的工作。 每个缓冲寄存器由地址寄存器、操作数寄存器和标志三部分组成。也可以把地址寄存器和操作数寄存器合为一个。 当收到从指令分析器中送来的有效地址时，就向主存申请读操作数。 读出的操作数存放在操作数寄存器中或覆盖掉地址寄存器中的地址。,先行缓冲栈（续）,2019/6/12,22,4.后行写数栈 每个后行缓冲寄存器由地址寄存器、数据寄存器和标志三部分组成。 指令分析器遇到向主存写结果的指令时，把形成的有效地址送入后行写数栈的地址寄存器中，并用该地址寄存器的编号替换指令的目的地址部分，形成RR*指令送入先行操作栈。 当运算器执行这条RR*型写数指令时， 只要把写到主存的数据送到后行写数栈的数据寄存器中即可。,先行缓冲栈（续）,2019/6/12,23,先行缓冲栈（续）,5.采用先行控制方式时一个程序的执行情况：,2019/6/12,24,缓冲深度的设计方法,以静态分析为主，通过模拟来确定缓冲深度。 1.先行指令缓冲栈的设计 考虑两种极端情况：假设缓冲深度为DI (1)先行指令缓冲栈已经充满 指令流出的速度最快，例如连续分析RR型指令，设这种指令序列的最大长度为L1，平均分析一条这种指令的时间为t1。 指令流入的速度最慢，设平均取一条指令的时间为t2。从主存储器中取到先行指令缓冲栈中的指令条数是L1DI条。,2019/6/12,25,应该满足如下关系：L1 t1(LIDI) t2 计算出缓冲深度为： 如果这种指令流的连续长度超过L1，则先行指令缓冲栈被取空，指令分析器没有指令可分析，被迫处于等待状态。缓冲栈失去作用。 (2)先行指令缓冲栈原来为空 输入端指令流入的速度最快，每次取指令的时间最短；设这种指令序列的最大长度为 L2，平均取一条这种指令的时间为 t2；,缓冲深度的设计方法（续）,2019/6/12,26,输出端指令流出的速度最慢，指令分析器连续分析最难分析的指令；设平均分析一条指令的时间为 t1。分析的指令条数是L2DI条。 应该满足如下关系：(L2DI) t1LI t2 计算出缓冲深度为： 如果这种指令流的连续长度超过L2，先行指令缓冲栈被完全充满，失去缓冲作用。,缓冲深度的设计方法（续）,2019/6/12,27,2.设计举例 在一般处理机中连续执行短指令的概率大。 例：一个采用先行控制方式的处理机，指令分析器分析一条指令用一个周期，到主存储器中取一条指令装入先行指令缓冲栈平均用4个周期，如果这种指令的平均长度为9，即90的指令是执行时间短的指令。 解：计算先行指令缓冲栈的缓冲深度为：,缓冲深度的设计方法（续）,2019/6/12,28,3.先行指令缓冲栈的工作时间关系 第1个周期，取走指令k+1，请求取指令。 第4个周期末尾，指令k+8取到先行指令缓冲栈。 第8个周期末尾，指令k+9取到先行指令缓冲栈。 第9个周期，分析指令k+9，先行指令缓冲栈空。 第10个周期，指令分析器等待。,缓冲深度的设计方法（续）,2019/6/12,29,4.其余缓冲栈的设计原则 一般有关系：DIDCDRDW 其中：DI是先行指令缓冲栈的缓冲深度， DC是先行操作栈的缓冲深度， DR是先行读数栈的缓冲深度， DW是后行写数栈的缓冲深度。 例如：IBM370/165机： DI4，DC3，DR2，DW1。 我国研制的两台大型计算机： DI8，DCDR4，DW2。 DI12，DCDR6，DW2。,缓冲深度的设计方法（续）,2019/6/12,30,数据相关,数据相关： 在执行本条指令的过程中，如果用到的指令、操作数、变址量等是前面指令的执行结果，这种相关称为数据相关。 控制相关： 由条件分支指令、转子程序指令、中断等引起的相关。 解决数据相关的方法有两种： 推后分析法，遇到相关数据，推后本条指令的分析，直至所需要的数据写入到相关的存储单元。 设置专用路径。不必等到所需要的数据写入到相关存储单元，而是经专门设置的数据通路读取所需要的数据。,2019/6/12,31,1.指令相关 发生指令相关的情况： n： STORE R1, n+1 n+1： 满足关系： 结果地址(n)指令地址(n+1) 当第n条指令还没有把执行结果写到主存之前，取出的第n+1条指令显然是错误的。 在k个流水段的流水线处理机中，第n条指令要修改从第n+1到第n+ k 指令中的任意一条指令，都可能造成程序执行结果发生错误。,数据相关（续）,2019/6/12,32,在采用先行控制方式的处理机中，如果执行部件正在执行第n条指令，与下述情况之一发生相关，都可能造成程序执行结果发生错误。 存放在先行操作栈中的指令 正在指令分析器中分析的指令 已经预取到先行指令缓冲栈中的指令 指令执行结果还在后行缓冲栈中的指令 更严重的是：有些分支指令，可能已经在指令分析器中执行完成。,数据相关（续）,2019/6/12,33,解决指令相关的根本办法是： 在程序执行过程中不允许修改指令。 现代程序设计方法要求程序具有再入性，可以被递归调用等，也要求不修改指令。 在IBM370系列机中，用“执行指令”来解决：在程序执行过程中既能够修改指令，程序又具有再入性。 “执行指令”执行由第二地址(X2)+(B2)+D2)决定的主存数据区中的指令。,数据相关（续）,2019/6/12,34,2.主存操作数相关 发生主存操作数相关的指令序列： n：OP A1，A2，A3 ；A1(A2) OP (A3) n+1：OP A4，A1，A5 ；A4(A1) OP (A5) 出现下列情况之一，A1、A2、A3是主存地址，就发生主存操作数相关： A1（n） A2（n1） A1（n） A3（n1） 解决办法： 运算结果写到通用寄存器，而不写到主存 对于访问主存储器的请求，写结果的优先级高于读操作数。,数据相关（续）,2019/6/12,35,有先行操作栈处理机中，分析指令、已经执行指令需要进入后行写数操作栈向主存写回运算结果的指令之间可能相隔很多条指令。已经进入先行操作栈的任何一条指令在向主存申请读数时都可能与正在执行部件中执行的指令、正在后行写数栈中等待写结果到主存的指令，甚至还在先行操作栈中的指令发生主存操作数相关。 解决办法： 对于刚进入先行操作栈中的指令在向主存读数之前，首先把访问主存的地址与后行写数栈中的所有主存地址比较，如果发现有相等的，则先行栈的读数操作缓行，等到相关写操作数指令完成，并把结果写到主存之后再读数。,数据相关（续）,2019/6/12,36,数据相关（续）,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)称为R2数据相关。,2019/6/12,37,解决通用寄存器数据相关的方法： 方法一：把读操作数、写运算结果与指令执行合在一个节拍。 从数据从通用寄存器读出，在运算器中完成运算，结果写回通用寄存器的整个回路中，只有通用寄存器是时序逻辑。 当发生下述情况时，不能采用这种方法： 当寄存器个数多时，读写寄存器的时间长。 当功能部件数量多时，寄存器的读写端口多。 当功能部件的执行时间比较长，或要求指令的执行时间短时 。,数据相关（续）,2019/6/12,38,方法二：建立相关专用通路(ByPass) 由于发生寄存器数据相关的情况很普遍，一般计算机系统都采用专用数据通路。 把读通用寄存器、执行操作和写结果分为3个周期，或2个周期。 采用专用数据通路能够缩短1至2个周期。,数据相关（续）,2019/6/12,39,变址相关：在采用变址寻址方式的处理机中，由于变址量放在寄存器中，因此，可能发生与通用寄存器数据相关类似变址相关.,4. LOAD相关 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数据相关。,数据相关（续）,2019/6/12,40,解决方法： 方法一：由编译器在LOAD之后插入不发生数据相关的指令，由于LOAD的执行时间不确定，不能根本解决问题。 方法二：由硬件自动插入空操作，直到LOAD操作完成。 在单条流水线处理机中，也可以停止节拍发生器，直到数据从存储器中读出为止。,数据相关（续）,2019/6/12,41,控制相关,因程序的执行方向可能被改变而引起的相关，也称为全局相关。 主要包括：无条件转移、一般条件转移、复合条件转移、中断等。 1. 无条件转移 在流水线处理机中，无条件转移指令不进入执行流水段，一般在指令译码阶段就实际执行完成。 如果在处理机中设置有指令先行缓冲栈，则要全部或部分作废先行指令缓冲栈中的指令。,2019/6/12,42,如果转移目标指令L不在先行指令缓冲栈中，则要将先行指令缓冲栈中的所有指令全部作废，并等待取出转移目标指令L。 如果转移目标指令L在先行指令缓冲栈中，只要作废先行指令缓冲栈中的部分指令。 无条件转移指令一般对指令执行部件的工作不会造成影响。 为进一步减少无条件转移指令造成的影响，在先行指令缓冲栈的入口处增设一个专门处理无条件转移指令的指令分析器,控制相关(续),2019/6/12,43,2.一般条件转移 k： ;置条件码CC k+1：JMP(CC) L ;如果CC为真转向L L： 当条件码是上一条指令产生时，相关最严重,控制相关(续),2019/6/12,44,无论转移是否成功，条转移指令都在指令分析阶段就已经执行完成。 无论转移不成功或不成功，指令分析器要停顿一段时间，等待条件码产生。,控制相关(续),2019/6/12,45,如果转移成功：指令L已经在先行指令缓冲栈，指令分析器接着“分析L”，如果指令L不在先行指令缓冲栈，指令分析器要等待一个周期。 转移不成功，对程序执行影响不大， 当转移成功时，不仅指令执行过程变成完全串行，而且要作废先行指令缓冲栈中的大量指令。 在采用流水线方式的处理机中，要通过软件与硬件的多种手段来近可能地降低转移成功的概率，减少转移成功造成的影响。,控制相关(续),2019/6/12,46,3.复合条件转移 k：OP L ;产生条件码，并决定是否转向L L： 如果转移不成功：不造成任何影响，就象普通的运算型指令一样 如果转移成功：造成的影响比一般条件转移指令还要大得多。全部或部分作废先行指令缓冲栈、先行操作栈、先行读数栈和指令分析器中的指令。 必须采取策略，减小转移成功造成的影响。,控制相关(续),2019/6/12,47,控制相关(续),2019/6/12,48,转移预测技术,转移预测技术包括： 静态分支预测： 在程序执行过程中转移预测方向不能改变 动态分支预测： 在程序执行过程中能够改变转移预测方向,2019/6/12,49,静态分支预测技术,1.软件“猜测法” 目标：通过编译器尽量降低转移成功的概率。 例如：对于循环程序，普通编译器生成的目标代码，转移成功的概率很高，不成功的只有一次。这种编译结果对流水线极为不利。 优点： 不需要改变先行控制器的硬件结构，只需适当修改编译器就能够大幅度降低条件转移指令对先行控制器产生的影响。其最终目标是提高处理机执行程序的速度。,2019/6/12,50,静态分支预测技术（续）,软件“猜测法”： 通过编译器降低转移成功的概率,2019/6/12,51,2.硬件“猜测法” 方法：通过改变硬件结构来降低转移指令对流水线的影响 在先行指令缓冲栈的入口处设置一个简单的指令分析器，当检测到转移指令时，就把转移目标地址L送入先行程序计数器PC1中，同时保留当前PC1中的内容到另一寄存器中。 转移成功，猜测正确。对转移指令对流水线不造成影响。 转移不成功，用保存下来的地址恢复PC1和PC。 软硬件共同配合，都往同一个方向去猜测。,静态分支预测技术（续）,2019/6/12,52,3.两个先行指令缓冲栈 向前条件转移，转移成功与不成功各50% 在先行指令缓冲栈中增加一个先行目标缓冲栈 按照转移成功的方向预取指令到先行目标缓冲栈中。 先行指令缓冲栈仍然按照转移不成功的方向继续预取指令。 如果转移不成功，则继续分析原来先行指令缓冲栈中指令。 如果转移成功，则分析新增设的先行目标缓冲栈中的指令。,静态分支预测技术（续）,2019/6/12,53,静态分支预测技术（续）,AIB，新增先行指令缓冲栈，IB原先行指令缓冲栈。 TR1，TR2，保存PC1和PC中的内容，转移不成功，恢复PC1和PC。,2019/6/12,54,短循环程序的处理,在循环程序中存在大量的短循环程序，对于短循环程序，一般先行指令缓冲栈的效率很低，一种极端的情况是：当循环体只有一条指令，先行缓冲栈失效。指令分析器分析完该指令后就清除指令缓冲栈，重新到主存取指令。 短循环程序的特点： 循环体的长度小于等于先行指令缓冲栈的深度。 使得在循环程序执行过程中，整个循环体能够始终存放在先行指令缓冲栈不被清除。循环程序可以多次重复使用减少访问主存的次数。 循环次数的控制采用计数转移指令实现。 因为计数转移指令可以在指令分析器中直接执行，指令分析器分析到这种特殊条件转移指令时不必等到指令执行部件形成条件码，而在指令分析器中就可以判断循环出口条件是否满足。 控制循环的条件转移指令一般是向后转移的指令。,2019/6/12,55,短循环程序的处理（续）,要在先行控制器中对短循环程序作特殊处理，必须解决好三个问题： 指令分析器如何发现短循环程序。 如何控制短循环程序在先行缓冲栈不被清除。 如何控制循环体的执行次数，即处理好循环体的出口。,2019/6/12,56,短循环程序的处理（续）,方法一： 在指令系统中专门设置短循环程序的开门指令和关门指令，由编译器在对源程序进行编译时发现短循环程序，并在其开头加上短循环开门指令，在末尾加上关门指令。 在指令分析器中增加专门的硬件来处理短循环开关门指令。 设置专门的短循环标志触发器TL。当TL=1时表示先行指令缓冲栈内是短循行程序而不被清除,2019/6/12,57,短循环程序的处理（续）,执行过程： 指令分析器分析到开门指令表示循环开始，开门指令主要为循环做预处理： 将短循环程序的循环次数送入指令分析器的循环次数计数器。 设置短循环程序在先行指令缓冲栈的起始地址，即入口。 置位短循环标志触发器TL，表示短循环程序的开始。 先从指令缓冲栈中取出一条指令进行分析，如果TL=1，每从指令缓冲栈取一条指令，都不清除该指令。 执行到关门指令，循环体结束，指令缓冲栈放置了全部该段循环体的指令。每次循环都执行关门指令，关门指令控制循环体的次数。,2019/6/12,58,短循环程序的处理（续）,关门指令的工作： 把循环计数器减1。 若循环计数器值大于等于1，现行程序计数器指向短循环程序的入口，准备下一次循环。若等于1， 还要把Tl清零。 当Tl=0时，每分析一条指令就清除该指令，先行缓冲栈恢复正常功能。 若循环计数器值为0，循环结束，顺序执行后续指令。,2019/6/12,59,短循环程序的处理（续）,优缺点： 优点是硬件简单，开关门指令确定循环体，指令操作马即可识别此两条指令，不需专门的硬件。缺点是增加了程序员的负担。 方法二： 在有的机器中为使短循环程序处理对程序员透明，不采用专门的开关门指令。而是采用专门的硬件来识别短循环程序。 IBM360/370在指令分析器中有一个向后检测8条指令的功能，如果条件转移指令的转移目标地址和转移指令本身地址相差小于0，大于-8，即认为遇到短循环程序。处理方法和开关方法相同。 许多高性能处理机采用专门的一级指令Cache，把指令Cache和数据Cache分开，其中指令可以较长时间保存，有效提高循环程序的执行速度。,2019/6/12,60,5.2 流水线处理机技术,空间并行性：设置多个独立的操作部件 时间并行性：分时使用同一个部件的不同部分 5.2.1 流水线工作原理 5.2.2 流水线的分类 5.2.3 线性流水线的性能分析 5.2.4 非线性流水线的调度,2019/6/12,61,流水线工作原理,1.流水寄存器 流水线的每一个阶段称为流水步、流水步骤、流水段、流水线阶段、流水功能段、功能段、流水级、流水节拍等。 在每一个流水段的末尾或开头必须设置一个寄存器，称为流水寄存器、流水锁存器、流水闸门寄存器等。 加入流水寄存器，会增加指令的执行时间。 在一般流水线时空图中不画出流水寄存器。,2019/6/12,62,2.一种指令流水线 一般4至12个流水段，8个流水段的称为超流水线处理机 3.流水线时空图,流水线工作原理（续）,2019/6/12,63,流水线工作原理（续）,一个浮点加法器流水线的时空图,2019/6/12,64,4.流水线的主要特点 只有连续提供同类任务才能发挥流水线效率 尽量减少因条件分支造成的“断流” 通过编译技术提供连续的相同类型操作 每个流水线段都要设置一个流水寄存器 时间开销：流水线的执行时间加长 是流水线中需要增加的主要硬件 各流水段的时间应尽量相等 流水线处理机的基本时钟周期等于时间最长的流水段的时间长度。 流水线需要有“装入时间”和“排空时间”,流水线工作原理（续）,2019/6/12,65,流水线的分类,1.线性流水线与非线性流水线 流水线的各个流水段之间是否有反馈信号 线性流水线（Linear Pipelining）： 每一个流水段都流过一次，而且仅流过一次 非线性流水线（Nonlinear Pipelining）： 某些流水段之间有反馈回路或前馈回路。 线性流水线能够用流水线连接图唯一表示。 非线性流水线必须用流水线连接图和流水线预约表共同表示。,2019/6/12,66,流水线的分类（续）,2.按照流水线的级别来分 处理机级流水线，又称为指令流水线。 例如：在采用先行控制器的处理机中，各功能部件之间的流水线,2019/6/12,67,流水线的分类（续）,部件级流水线(操作流水线) 如浮点加法器流水线 宏流水线(Macro Pipelining) 处理机之间的流水线称，每个处理机对同一个数据流的不同部分分别进行处理。,2019/6/12,68,流水线的分类（续）,3. 单功能流水线与多功能流水线 单功能流水线： 只能完成一种固定功能的流水线。 Cray-1计算机种有12条，YH-1计算机有18条 Pentium有一条5段定点和一条8段浮点流水线。 Pentium有两条定点和一条浮点指令流水线。 多功能流水线： 流水线的各段通过不同连接实现不同功能 Texas公司的ASC机，8段流水线，能够实现：定点加减法、定点乘法、浮点加法、浮点乘法、逻辑运算、移位操作、数据转换、向量运算等。,2019/6/12,69,流水线的分类（续）,2019/6/12,70,4.静态流水线与动态流水线 静态流水线：同一段时间内，多功能流水线各个功能段只能按照一种方式连接，实现一种固定的功能。,流水线的分类（续）,2019/6/12,71,动态流水线：在同一段时间内，多功能流水线各段可以按照不同的方式连接，同时执行多种功能。,流水线的分类（续）,条件：流水线中各个功能部件之间不能发生冲突。,2019/6/12,72,5.流水线的其他分类方法 按照数据表示方式：标量流水线和向量流水线 按照控制方式：同步流水线和异步流水线 顺序流水线与乱序流水线，按照流水线输出端流出的任务和流水线输入端流入的任务顺序是否相同划分。乱序流水线又称为无序流水线、错序流水线或异步流水线等。,流水线的分类（续）,2019/6/12,73,线性流水线的性能分析,主要指标：吞吐率、加速比和效率 1.吞吐率（Though Put），单位时间内流水线所完成的任务数量或输出结果数量。 流水线吞吐率的最基本公式： 其中：n为任务数， k为完成n个任务所用的时间。 各段执行时间相等，输入连续任务情况下，完成n个任务需要的总时间为： Tk(kn1)t 其中：k 为流水线的段数，t为时钟周期。,2019/6/12,74,线性流水线的性能分析（续）,依据： 从输出端： 用k个时钟周期输出第一个任务，其余n-1个周期，每个周期输出一个任务，共n-1个任务。 从输入端： 用n个周期输入n个任务。另外还有k-1个周期等待流水线排空。,2019/6/12,75,线性流水线的性能分析（续）,Tk= kt + (n-1)t = (k+n-1)t 吞吐率为： 最大吞吐率为：,2019/6/12,76,线性流水线的性能分析（续）,最大吞吐率和实际吞吐率的关系： 流水线的实际吞吐率要小于最大吞吐率。 实际吞吐率和t，流水线短数k，输入到流水线的任务数n相关。 只有nk时，才有TPTPmax。,2019/6/12,77,线性流水线的性能分析（续）,各段时间不等，完成n个连续任务： 吞吐率： 最大吞吐率： 流水线各段执行时间不相等的解决办法,2019/6/12,78,线性流水线的性能分析（续）,(1)将“瓶颈”部分再细分（如果可分的话）,2019/6/12,79,线性流水线的性能分析（续）,2019/6/12,80,线性流水线的性能分析（续）,2.加速比（Speedup） 计算加速比的基本公式： 各段执行时间相等，输入连续任务情况下,加速比： 最大加速比： 各段时间不等，输入连续任务情况下, 实际加速比为：,2019/6/12,81,线性流水线的性能分析（续）,是否流水线的段数越多越好？ 当流水线段数增加时，需要连续输入的任务数也必须增加。 由于程序中存在数据相关、转移、中断等情况。任务数n受到很大限制。 控制的复杂性，电路的实现及组装技术，实现的成本等的限制，流水线不可能很多。,2019/6/12,82,3.效率（Efficiency）流水线的设备利用率。 计算流水线效率的一般公式： 各流水段时间相等，输入n个连续任务，流水线的效率为： 最高效率为： 各流水段时间不等，输入n个连续任务，流水线效率为：,线性流水线的性能分析（续）,2019/6/12,83,各段设备量或价格不等时，流水线的效率为： 即： 其中，aik，且k。 流水线的吞吐率、加速比与效率的关系： 因为： 因此：ETP t，Sk E,线性流水线的性能分析（续）,2019/6/12,84,4.流水线最佳段数的选择 采用顺序执行方式完成一个任务的时间为t 在同等速度的 k 段流水线上执行一个任务的时间为：tkd (d为流水锁存器的延迟时间) 流水线的最大吞吐率为：P=1(tkd) 流水线的总价格估计为：Cab k， 其中：a为功能段身的总价格， b为每个锁存器的价格 A.G.Larson把流水线的性能价格比PCR定义为：,线性流水线的性能分析（续）,2019/6/12,85,线性流水线的性能分析（续）,求PCR的最大值为：,2019/6/12,86,5. 流水线性能分析举例 对于单功能线性流水线，输入连续任务的情况，通过上面给出的公式很容易计算出流水线的吞吐率、加速比和效率。 对于输入不连续任务，或多功能流水线，通常采用基本公式计算。 例：用一条4段浮点加法器流水线求8个浮点数的和：ZABCDEFGH,线性流水线的性能分析（续）,2019/6/12,87,解： Z(AB)(CD)(EF)(GH),线性流水线的性能分析（续）,2019/6/12,88,解：,线性流水线的性能分析（续）,2019/6/12,89,线性流水线的性能分析（续）,例，多功能、线形流水线，输入任务是不连续的情况，计算流水线的吞吐率、加速比和效率。利用Ti-ASC多功能静态流水线计算两个向量的点积：Z=AB+CD+EF+GH。 解，为减少数据相关性充分发挥流水线的作用，因该先做4个乘法，AB，CD，EF，GH。然后坐两个加法AB+CD和EF+GH。最后求总的结果Z。,2019/6/12,90,线性流水线的性能分析（续）,流水线的时空图：,2019/6/12,91,线性流水线的性能分析（续）,20个周期完成7个运算。每个功能能段的延迟时间都为t，则Tk=20 t，n=7。 则有流水线吞吐率TP为： 如果采用顺序执行方式，完成一次乘法要用4个t ，完成一次加法要用6个t ，完成全部运算要用： t tt。流水线的加速比为： 整个流水线共有段，流水线的效率为：,2019/6/12,92,线性流水线的性能分析（续）,整个流水线效率很低： 多功能流水线在做某一运算时，总有一些功能段是闲置的。 静态流水线必须等前一种运算运算全部排除流水线之后才能重新进行连接。 计算本身存在数据相关，发生数据相关时必须等待前一个运算结果产生之后，下一个运算才能开始。 流水线有装入和排空部分，当输入到流水线中的任务不多时，装入与排空部分所占的比例比较大。,2019/6/12,93,非线性流水线的调度,非线性流水线中存在反馈回路，当一个任务在流水线中流过时，在同一功能段中可能要多次经过。 不能在一个时钟周期内向流水线输入一个任务，否则会发生在同一个时刻有几个任务争用同一个功能段的情况。称为功能部件冲突或者流水线冲突。 为避免冲突，采用延迟输入新任务的方法。间隔几个周期再输入新任务。 间隔的周期数不是一个常数。而是一串周期变化的数字。,2019/6/12,94,非线性流水线的调度（续）,非线性流水线调度的任务是要找出一个最小的循环周期，按照这周期向流水线输入新任务，流水线的各个功能段都不会发生冲突，而且流水线的吞吐率和效率最高。 1.非线性流水线的表示 线性流水线能够用流水线连接图唯一表示 对于非线形流水线，连接图不能唯一表示工作流程，因此，引入流水线预约表,2019/6/12,95,非线性流水线的调度（续）,例如： 非线形流水线的连接图和预约表,2019/6/12,96,非线性流水线的调度（续）,四个功能段组成非线性流水线。 与线性流水线相同地方： 从第一个功能段S1到最后一个功能段S4的单方向传输线。 不同的地方： 有两条反馈线和一条前馈线。 输出端经常不在最后一个功能段，可能从中间的任意一个功能段输出。,2019/6/12,97,非线性流水线的调度（续）,预约表： 预约表的横坐标表示流水线工作的时钟周期，纵坐标表示流水线的功能段。 中间的X表示该功能段在该时钟周期处于工作状态。即有任务在该时钟段通过该功能段。空白表示该时钟周期该功能段不工作。 一行可以有多个X，表示一个任务在不同时钟周期重复使用同一个功能段。一列可以有多个X，指同一个时钟周期多个功能段被使用。 预约表的行数是非线性流水线的段数。列数是指一个任务从进入流水线到从流水线输出经过的时钟周期数。又称为功能求值时间或装入时间。,2019/6/12,98,非线性流水线的调度（续）,一张预约表可能与多个流水线连接图相对应,原因：在预约表的同一列中可能有多个X，即该时钟周期有多个功能段输出，下一功能段的输入有多个来源，从而应对有多个连接图。,2019/6/12,99,非线性流水线的调度（续）,一个流水线连接图对应与多张预约表,原因：非线性流水线的有些功能段可能有多个输出端，也有些功能段有多个输入端，输出端和输入端之间连接的先后次序形成多张预约表。,2019/6/12,100,非线性流水线的调度（续）,2.非线性流水线的冲突 启动距离：连续输入两个任务之间的时间间隔，又称等待时间。 流水线冲突：以某启动距离连续向一条非线性流水线输入任务，可能会存在几个任务争用同一个流水段。,2019/6/12,101,非线性流水线的调度（续）,2019/6/12,102,非线性流水线的调度（续）,引起非线性流水线功能段冲突的启动距离称为禁止启动距离。 有些启动距离在非线性流水线的所有功能段，在任何时间都不会发生冲突，如前表的（5），（1，7）。 不发生冲突的启动距离不一定仅仅是一个常数，在一般情况下是一个循环数列。称为非线性流水线的启动循环。只有一个启动距离的启动循环又称为恒定循环。,2019/6/12,103,非线性流水线的调度（续）,要正确的调度一条非线性流水线，首先需要找到流水线的所有禁止启动距离。把所有禁止启动距离组合在一起形成数列，称为非线性流水线的禁止向量。 计算禁止向量： 把预约表中每一行中任意两个X之间的距离算出来，去掉重复的，这些数组成数列就是该非线性流水线的禁止向量。 把一个启动循环内的所有启动距离相加再除以这个启动循环内的启动距离个数就得到该启动循环的平均启动距离。,2019/6/12,104,3.无冲突调度方法 主要目标：找出最小平均启动距离的启动循环。 由E.S.Davidson及其学生于1971年提出 禁止向量：预约表中每一行任意两个“”之间距离的集合。上例中为（3，4，6） 冲突向量：用C（CmCm-1C2C1）表示，m位的二进制数。 其中：m是禁止向量中的最大值。 如果i在禁止向量中，则Ci1，否则Ci0。 上例中C(101100),非线性流水线的调度（续）,2019/6/12,105,非线性流水线的调度（续）,由冲突向量可以构造状态图。 将冲突向量C作为初始冲突向量送入m位的右移逻辑移位器。移出为0，移位器内的值和初始冲突向量做按位或运算。得到一个新的冲突向量。 移出为1，不做任何处理。移位器继续右移。 中间形成的新的冲突向量，也按上述方法处理。 在初始向量和新的冲突向量之间用箭头连接，并标注右移次数。表示各种状态之间的转换关系，向量重复时合并到一起。,2019/6/12,106,非线性流水线的调度（续）,当初始冲突向量确定后，状态图就是唯一的。 不同的预约表可能产生相同的初始冲突向量，因而不同的预约表也可能有相同的状态图。从预约表可以画出状态图，冲状态图不能获得预约表。 当启动距离大于或等于m+1时，流水线的任何一个功能段在任何时钟周期都不会发生冲突，但流水线的吞吐率、加速比、效率都很差。,2019/6/12,107,例：一条4功能段的非线性流水线，每个功能段的延迟时间都相等，它的预约表如下： (1)写出流水线的禁止向量和初始冲突向量。 (2)画出调度流水线的状态图。 (3)求最小启动循环和最小平均启动距离。 (4)求平均启动距离最小的恒定循环。,非线性流水线的调度（续）,2019/6/12,108,解： (1)禁止向量为：(2，4，6) 初始冲突向量：S = 101010 (2)构造状态图 S逻辑右移2、4、6位时，不作任何处理， 逻辑右移1、3、5和大于等于7时： S右移1位之后：010101101010111111， S右移3位之后：000101101010101111， S右移5位之后：000001101010101011， S右移7位或大于7位后：按位或就还原到它本身。,非线性流水线的调度（续）,2019/6/12,109,非线性流水线的调度（续）,新冲突向量再处理： 101111右移5位之后：000001101010101011， 101011右移3位之后：000101101010101111， 101011右移5位之后：000001101010101011。,2019/6/12,110,简单循环：状态图中各种冲突向量只经过一次的启动循环。在一个状态图中，简单循环的个数是有限的。 (3)最小的启动循环为（1，7）和（3，5）, 平均启动距离为 4。 (4)启动距离最小的恒定循环为（5）,非线性流水线的调度（续）,2019/6/12,111,非线性流水线的调度（续）,2019/6/12,112,非线性流水线的调度（续）,2019/6/12,113,4.优化调度方法 采用最小启动循环启动非线性流水线时，许多功能段还有空闲，即预约表中还有空白格子。最小启动循环实际上不能使非线性流水线充分发挥效率。 L.E.Shar于1972年提出流水线最小平均启动距离的限制范围： 最小平均启动距离的下限是预约表中任意一行里“”的最多个数。即同一任务通过流水线中任意一个功能段的次数。 最小平均启动距离小于等于状态图中任意一个简单循环的平均启动距离。 最小平均启动距离的上限是冲突向量中1的个数再加上1。 1992年，L.E.Shar又证明了上述限制范围。 最有用的是第1条。预约表中“”最多的行一定是瓶颈流水段。要使整个流水线最大发挥作用，必须使瓶颈功能段不间断工作。不得空闲。,非线性流水线的调度（续）,2019/6/12,114,非线性流水线的调度（续）,采用预留算法来调度非线性流水线，可以达到最优调度。 确定流水线的最小平均距离，最小平均距离等于预约表中任意一行中X的最大个数。或者同一个任务流过任意功能段的最多次数。 确定最小启动循环，相对于同一个最小平均启动距离可能有多个最小启动循环。其中有一个且只有一个启动距离都相等的恒定循环。选用该恒定循环为最小启动循环。 结合流水线预约表和连接图，采用预留算法，通过插入非计算延迟功能段实现最小启动循环。,2019/6/12,115,对于前例的预约表，在同一行中“”最多的为2个，因此，最小平均距离可以达到2。 最小启动循环可以是(2)、(1,3)、(1,1,4)、(1,2,3)、。现取恒定循环(2)。 每一行中与第1个“”的距离为2的倍数的位置都要预留出来。 S3行的第2个“”从周期5延迟到周期6。为此， S2行的第2个“”从周期6延迟到周期7； S1行的第2个“”从周期7延迟到周期8。 实际上，只要在流水段S4的输出端到流水段S3的输入端中间插入一个非计算延迟D1。,非线性流水线的调度（续）,2019/6/12,116,非线性流水线的调度（续）,2019/6/12,117,非线性流水线的调度（续）,2019/6/12,118,在非线性流水线中，“”最多的流水段一定是“瓶颈“流水段。 实现最优调度的目标是使“瓶颈”流水段处于忙碌状态，没有空闲周期。 最优调度方法能够使非线性流水线的吞吐率、加速比和效率达到最优。,非线性流水线的调度（续）,2019/6/12,119,局部相关,在流水线处理机中由于处理的指令条数很多，发生相关的可能性及其造成的影响将更严重。 按照对程序执行过程可能造成的影响划分：可以把相关分为局部相关和全局相关两类。 如图，程序中一条分支指令把程序划分为三个部分，每部分内部不再有分支操作，这种部分称为基本块。,2019/6/12,120,局部相关（续）,同一个基本块内部的相关称为局部相关（lacal correlation） 在基本块之间的相关成为全局相关（）。引起全局相关的除了分支操作还有中断。 局部相关对程序执行影响较小，仅限于相关指令临近的几条指令。全局相关影响很大，影响到整个程序的执行方向。,2019/6/12,121,局部相关（续）,促使流水线充分发挥作用，需要软硬件结合。 软件编译的目标代码要适合流水线结构，尽量把相关数据和相关控制的指令安排得远一些。把相同操作尽量安排在一起。 在硬件方面解决好存储系统的频带问题，能够为流水线提高足够的指令和数据。解决好流水线的局部相关和全局相关。 局部相关包括： 先写后读数据相关，先读后写数据相关，写写相关三种。,2019/6/12,122,顺序流动与乱序流动,1.顺序流动方式：任务按顺序流入流水线,也按顺序流出流水线 把如下一段程序输入到这条流水线中： k： R0（R1） k+1： k+2： R2（R0）（R3） k+3： k+4： k+5： ,2019/6/12,123,指令k+2无法继续执行，要在功能段S2中等待。 后续的指令k+