您好、欢迎来到现金彩票网!
当前位置:双彩网 > 先行指令站 >

计算机系统结构(清华大学出版社)第五章ppt

发布时间:2019-06-27 02:47 来源:未知 编辑:admin

  1.本站不保证该用户上传的文档完整性,不预览、不比对内容而直接下载产生的反悔问题本站不予受理。

  第五章 标量处理机 2017-4-25 本章主要内容 5.1 先行控制技术 5.2 流水线 超流水线 超标量超流水线处理机 标量处理机 只有标量数据表示和标量指令系统的处理机称为标量处理机,是最常用最普通的处理机。 设计处理机的主要任务就是缩短解释指令的时间,提高处理机指令的执行速度: 提高处理机的工作主频。5、60年代主要采用这种技术,每3、4年处理机的速度要提高一个数量级。 采用更好的算法和设计更好的功能部件,如采用RISC等。 多条指令并行执行。指令级的并行技术。 流水线技术。 处理机中设置多个独立的功能部件,如浮点运算器,定点运算器,访存部件等。 超长指令技术。 5.1 先行控制技术 先行控制技术的关键是采用缓冲技术和预处理技术,以及两者都采用,通过对指令流和数据流的预处理和缓冲,能够尽量使指令分析器和指令执行部件独立工作并始终处于忙碌状态。 5.1.1 指令的重叠执行方式 5.1.2 先行控制方式的原理 5.1.3 处理机结构 5.1.4 指令执行序列 5.1.5 先行缓冲栈 5.1.6 缓冲深度的设计方法 指令的重叠执行方式 一条指令的执行可以分为多个阶段,具体分法视处理机而定,一般可以分为三个阶段: 取指令是指按照指令计数器的内容访问主存,取出一条指令送到指令寄存器。 分析指令是指对指令的操作码进行译码,按照给定的寻址方式和地址字段内容形成操作数地址,并用这个地址读出操作数,操作数可以在主存也可以在寄存器。 执行指令是根据操作码的要求,完成指令规定的功能,把结果写到主存或者寄存器。 指令分析或者指令执行阶段还得修改指令计数器的更新,为下一条指令作准备。 指令的重叠执行方式 1.顺序执行方式 执行n条指令所用的时间为: 如果每段时间都为t,则执行n条指令所用的时间为:T=3 n t 主要优点:控制简单,节省设备。 主要缺点:速度慢,功能部件的利用率低。 2.一次重叠执行方式 如果两个过程的时间相等,则执行n条指令的时间为:T=(1+2n)t 主要优点: 指令的执行时间缩短, 功能部件的利用率明显提高。 主要缺点: 需要增加一些硬件, 控制过程稍复杂。 指令的重叠执行方式(续) 3.二次重叠执行方式 如果三个过程的时间相等,执行n条指令的时间为:T=(2+n)t 在理想情况下,处理机中同时有三条指令在执行。 处理机的结构要作比较大的改变,需要采用先行控制技术。 指令的重叠执行方式(续) 先行控制方式的原理 1.采用二次重叠执行方式必须解决两个问题: (1)有独立的取指令部件、指令分析部件和指令执行部件 把一个集中的指令控制器,分解成三个独立的控制器: 存储控制器、指令控制器、运算控制器。 (2)要解决访问主存储器的冲突问题 取指令、分析指令、执行指令都可能要访问存储器。 2.解决访存冲突的方法: (1)采用低位交叉存取方式: 这种方法不能根本解决冲突问题。 取指令、读操作数、写结果。 (2)主存分为两个独立的存储器:独立的指令存储器和数据存储器。 如果再规定,执行指令所需要的操作数和执行结果只写到通用寄存器,则取指令、分析指令和执行指令就可以同时进行。 在许多高性能处理机中,有独立的指令Cache和数据Cache。这种结构被称为哈佛结构。 先行控制方式的原理(续) (3)采用先行控制技术 采用先行控制技术的关键是缓冲技术和预处理技术。 缓冲技术通常用在工作速度不固定的两个功能部件之间。设置缓冲栈的目的是用来以平滑功能部件之间的工作速度。 在采用了缓冲技术和预处理技术之后,运算器能够专心于数据的运算,从而大幅度提高程序的执行速度。 先行控制方式的原理(续) 处理机结构 1.三个独立的控制器: 存储控制器、指令控制器、运算控制器。 2.四个缓冲栈: 先行指令缓冲栈、先行读数缓冲栈、先行操作栈、后行写数栈。 3.处理机组成 4.先行指令缓冲栈的组成 作用:只要指令缓冲栈没有充满,就自动发出取指令的请求。 指令分析器每分析完一条指令,自动向指令缓冲栈发出取下一条指令的请求,指令取出后就把先行指令缓冲栈中的指令作废。 分析指令速度和从主存取指令的速度是随机的,指令缓冲栈的指令数目是动态的。 设置两个程序计数器: 先行程序计数器PC1,用来指示取指令, 现行程序计数器PC,记录指令分析器正在分析的指令地址。 处理机结构(续) 处理机结构(续) 先行缓冲站的组成 指令缓冲存储器堆,采用先进先出的方式,保证指令的执行顺序不致混乱。 处理机结构(续) 先行控制方式中的一次重叠执行 重叠部分,无论谁先结束,都不能提前执行下一条指令,需要等待。 无论任何时刻,在指令分析部件和指令执行部件内都只有相邻的两条指令重叠执行,处理机只需要设置一套指令分析部件,——指令控制器;一套指令执行部件,——运算控制器和运算器。控制方式简单。 所需要时间为T=(1+n)t 处理机结构(续) 5.存在的主要问题: 计算机指令系统复杂,各类指令“分析”和“执行”的时间相差很大,分析指令和执行指令常常相互等待,造成部件的浪费。 分析k+1操作所需要的操作数正好是执行k的结果,不能重叠执行,发生数据相关,还有控制相关,变址相关。 转移或转子程序指令时,程序的执行过程不是顺序的,先行指令缓冲栈中预取指令和分析的下一条指令都可能要作废。 指令执行时序 设置了指令缓冲栈,取指令的时间就可以忽略不计。 一条指令的执行可分为2个过程。 1.分析指令和执行指令时间不相等时的情况。等待!! 指令执行时序 2.采用先行缓冲栈的指令执行过程 先行读数栈,先行操作栈,后行写数栈。 理想情况下,指令执行部件应该一直忙碌。 连续执行n条指令的时间为: 先行缓冲栈 设置先行缓冲栈的目的:使指令分析器和指令执行部件能够独立工作。 1.先行指令缓冲栈: 处于主存储器与指令分析器之间。 用它来平滑主存储器取指令和指令分析器使用指令之间的速度差异。 RR型指令,不必处理,直接送先行缓冲栈。 RS型指令,主存有效地址送先行读数栈,用该先行读数栈的寄存器编号替换指令中的主存地址码部分,形成RR*指令送先行缓冲栈。 RI型指令,指令中的立即数送先行读数栈,用该先行读数栈的寄存器编号替换指令中的立即数部分,形成RR*指令送先行缓冲栈。 转移指令,一般在指令分析器中直接执行。 2.先行操作栈 处于指令分析器和运算控制器之间。 使指令分析器和运算器能够各自独立工作。 采用先进先出方式工作,由指令寄存器堆和控制逻辑组成。 先行缓冲栈(续) 3.先行读数栈 处于主存储器与运算器之间。 平滑运算器与主存储器的工作。 每个缓冲寄存器由地址寄存器、操作数寄存器和标志三部分组成。也可以把地址寄存器和操作数寄存器合为一个。 当收到从指令分析器中送来的有效地址时,就向主存申请读操作数。 读出的操作数存放在操作数寄存器中或覆盖掉地址寄存器中的地址。 先行缓冲栈(续) 4.后行写数栈 每个后行缓冲寄存器由地址寄存器、数据寄存器和标志三部分组成。 指令分析器遇到向主存写结果的指令时,把形成的有效地址送入后行写数栈的地址寄存器中,并用该地址寄存器的编号替换指令的目的地址部分,形成RR*指令送入先行操作栈。 当运算器执行这条RR*型写数指令时, 只要把写到主存的数据送到后行写数栈的数据寄存器中即可。 先行缓冲栈(续) 先行缓冲栈(续) 5.采用先行控制方式时一个程序的执行情况: 缓冲深度的设计方法 以静态分析为主,通过模拟来确定缓冲深度。 1.先行指令缓冲栈的设计 考虑两种极端情况:假设缓冲深度为DI (1)先行指令缓冲栈已经充满 指令流出的速度最快,例如连续分析RR型指令,设这种指令序列的最大长度为L1,平均分析一条这种指令的时间为t1。 指令流入的速度最慢,设平均取一条指令的时间为t2。从主存储器中取到先行指令缓冲栈中的指令条数是L1-DI条。 应该满足如下关系:L1 t1=(LI-DI) t2 计算出缓冲深度为: 如果这种指令流的连续长度超过L1,则先行指令缓冲栈被取空,指令分析器没有指令可分析,被迫处于等待状态。缓冲栈失去作用。 (2)先行指令缓冲栈原来为空 输入端指令流入的速度最快,每次取指令的时间最短;设这种指令序列的最大长度为 L2,平均取一条这种指令的时间为 t2’; 缓冲深度的设计方法(续) 输出端指令流出的速度最慢,指令分析器连续分析最难分析的指令;设平均分析一条指令的时间为 t1’。分析的指令条数是L2-DI条。 应该满足如下关系:(L2-DI) t1’=LI t2’ 计算出缓冲深度为: 如果这种指令流的连续长度超过L2,先行指令缓冲栈被完全充满,失去缓冲作用。 缓冲深度的设计方法(续) 2.设计举例 在一般处理机中连续执行短指令的概率大。 例:一个采用先行控制方式的处理机,指令分析器分析一条指令用一个周期,到主存储器中取一条指令装入先行指令缓冲栈平均用4个周期,如果这种指令的平均长度为9,即90%的指令是执行时间短的指令。 解:计算先行指令缓冲栈的缓冲深度为: 缓冲深度的设计方法(续) 3.先行指令缓冲栈的工作时间关系 第1个周期,取走指令k+1,请求取指令。 第4个周期末尾,指令k+8取到先行指令缓冲栈。 第8个周期末尾,指令k+9取到先行指令缓冲栈。 第9个周期,分析指令k+9,先行指令缓冲栈空。 第10个周期,指令分析器等待。 缓冲深度的设计方法(续) 4.其余缓冲栈的设计原则 一般有关系:DI≥DC≥DR≥DW 其中:DI是先行指令缓冲栈的缓冲深度, DC是先行操作栈的缓冲深度, DR是先行读数栈的缓冲深度, DW是后行写数栈的缓冲深度。 例如:IBM370/165机: DI=4,DC=3,DR=2,DW=1。 我国研制的两台大型计算机: DI=8,DC=DR=4,DW=2。 DI=12,DC=DR=6,DW=2。 缓冲深度的设计方法(续) 数据相关 数据相关: 在执行本条指令的过程中,如果用到的指令、操作数、变址量等是前面指令的执行结果,这种相关称为数据相关。 控制相关: 由条件分支指令、转子程序指令、中断等引起的相关。 解决数据相关的方法有两种: 推后分析法,遇到相关数据,推后本条指令的分析,直至所需要的数据写入到相关的存储单元。 设置专用路径。不必等到所需要的数据写入到相关存储单元,而是经专门设置的数据通路读取所需要的数据。 1.指令相关 发生指令相关的情况: n: STORE R1, n+1 n+1: …… 满足关系: 结果地址(n)=指令地址(n+1) 当第n条指令还没有把执行结果写到主存之前,取出的第n+1条指令显然是错误的。 在k个流水段的流水线处理机中,第n条指令要修改从第n+1到第n+ k 指令中的任意一条指令,都可能造成程序执行结果发生错误。 数据相关(续) 在采用先行控制方式的处理机中,如果执行部件正在执行第n条指令,与下述情况之一发生相关,都可能造成程序执行结果发生错误。 存放在先行操作栈中的指令 正在指令分析器中分析的指令 已经预取到先行指令缓冲栈中的指令 指令执行结果还在后行缓冲栈中的指令 更严重的是:有些分支指令,可能已经在指令分析器中执行完成。 数据相关(续) 解决指令相关的根本办法是: 在程序执行过程中不允许修改指令。 现代程序设计方法要求程序具有再入性,可以被递归调用等,也要求不修改指令。 在IBM370系列机中,用“执行指令”来解决:在程序执行过程中既能够修改指令,程序又具有再入性。 “执行指令”执行由第二地址((X2)+(B2)+D2)决定的主存数据区中的指令。 数据相关(续) 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(n+1) A1(n)= A3(n+1) 解决办法: 运算结果写到通用寄存器,而不写到主存 对于访问主存储器的请求,写结果的优先级高于读操作数。 数据相关(续) 有先行操作栈处理机中,分析指令、已经执行指令需要进入后行写数操作栈向主存写回运算结果的指令之间可能相隔很多条指令。已经进入先行操作栈的任何一条指令在向主存申请读数时都可能与正在执行部件中执行的指令、正在后行写数栈中等待写结果到主存的指令,甚至还在先行操作栈中的指令发生主存操作数相关。 解决办法: 对于刚进入先行操作栈中的指令在向主存读数之前,首先把访问主存的地址与后行写数栈中的所有主存地址比较,如果发现有相等的,则先行栈的读数操作缓行,等到相关写操作数指令完成,并把结果写到主存之后再读数。 数据相关(续) 数据相关(续) 3. 通用寄存器数据相关 发生寄存器数据相关的可能性很大,影响面也很大 n:OP R1,A2 ;R1=(R1) OP (A2) n+1:OP R1,R2 ;R1=(R1) OP (R2) 发生R1(n)=R1(n+1)称为R1数据相关。 发生R1(n)=R2(n+1)称为R2数据相关。 解决通用寄存器数据相关的方法: 方法一:把读操作数、写运算结果与指令执行合在一个节拍。 从数据从通用寄存器读出,在运算器中完成运算,结果写回通用寄存器的整个回路中,只有通用寄存器是时序逻辑。 当发生下述情况时,不能采用这种方法: 当寄存器个数多时,读写寄存器的时间长。 当功能部件数量多时,寄存器的读写端口多。 当功能部件的执行时间比较长,或要求指令的执行时间短时 。 数据相关(续) 方法二:建立相关专用通路(ByPass) 由于发生寄存器数据相关的情况很普遍,一般计算机系统都采用专用数据通路。 把读通用寄存器、执行操作和写结果分为3个周期,或2个周期。 采用专用数据通路能够缩短1至2个周期。 数据相关(续) 变址相关:在采用变址寻址方式的处理机中,由于变址量放在寄存器中,因此,可能发生与通用寄存器数据相关类似变址相关. 4. LOAD相关 LOAD操作的执行时间可能比较长 n: LOAD R1, A ;R1=(A) n+1: ADD R1, R2 ;R1=(R1) OP (R2) 如果 R1(n)=R2(n+1),或 R1(n)=R1(n+1), 则发生LOAD数据相关。 数据相关(续) 解决方法: 方法一:由编译器在LOAD之后插入不发生数据相关的指令,由于LOAD的执行时间不确定,不能根本解决问题。 方法二:由硬件自动插入空操作,直到LOAD操作完成。 在单条流水线处理机中,也可以停止节拍发生器,直到数据从存储器中读出为止。 数据相关(续) 控制相关 因程序的执行方向可能被改变而引起的相关,也称为全局相关。 主要包括:无条件转移、一般条件转移、复合条件转移、中断等。 1. 无条件转移 在流水线处理机中,无条件转移指令不进入执行流水段,一般在指令译码阶段就实际执行完成。 如果在处理机中设置有指令先行缓冲栈,则要全部或部分作废先行指令缓冲栈中的指令。 如果转移目标指令L不在先行指令缓冲栈中,则要将先行指令缓冲栈中的所有指令全部作废,并等待取出转移目标指令L。 如果转移目标指令L在先行指令缓冲栈中,只要作废先行指令缓冲栈中的部分指令。 无条件转移指令一般对指令执行部件的工作不会造成影响。 为进一步减少无条件转移指令造成的影响,在先行指令缓冲栈的入口处增设一个专门处理无条件转移指令的指令分析器 控制相关(续) 2.一般条件转移 k:…… ;置条件码CC k+1:JMP(CC) L ;如果CC为真转向L …… L:…… 当条件码是上一条指令产生时,相关最严重 控制相关(续) 无论转移是否成功,条转移指令都在指令分析阶段就已经执行完成。 无论转移不成功或不成功,指令分析器要停顿一段时间,等待条件码产生。 控制相关(续) 如果转移成功:指令L已经在先行指令缓冲栈,指令分析器接着“分析L”,如果指令L不在先行指令缓冲栈,指令分析器要等待一个周期。 转移不成功,对程序执行影响不大, 当转移成功时,不仅指令执行过程变成完全串行,而且要作废先行指令缓冲栈中的大量指令。 在采用流水线方式的处理机中,要通过软件与硬件的多种手段来近可能地降低转移成功的概率,减少转移成功造成的影响。 控制相关(续) 3.复合条件转移 k:OP L ;产生条件码,并决定是否转向L …… L:…… 如果转移不成功:不造成任何影响,就象普通的运算型指令一样 如果转移成功:造成的影响比一般条件转移指令还要大得多。全部或部分作废先行指令缓冲栈、先行操作栈、先行读数栈和指令分析器中的指令。 必须采取策略,减小转移成功造成的影响。 控制相关(续) 控制相关(续) 转移预测技术 转移预测技术包括: 静态分支预测: 在程序执行过程中转移预测方向不能改变 动态分支预测: 在程序执行过程中能够改变转移预测方向 静态分支预测技术 1.软件“猜测法” 目标:通过编译器尽量降低转移成功的概率。 例如:对于循环程序,普通编译器生成的目标代码,转移成功的概率很高,不成功的只有一次。这种编译结果对流水线极为不利。 优点: 不需要改变先行控制器的硬件结构,只需适当修改编译器就能够大幅度降低条件转移指令对先行控制器产生的影响。其最终目标是提高处理机执行程序的速度。 静态分支预测技术(续) 软件“猜测法”: 通过编译器降低转移成功的概率 2.硬件“猜测法” 方法:通过改变硬件结构来降低转移指令对流水线的影响 在先行指令缓冲栈的入口处设置一个简单的指令分析器,当检测到转移指令时,就把转移目标地址L送入先行程序计数器PC1中,同时保留当前PC1中的内容到另一寄存器中。 转移成功,猜测正确。对转移指令对流水线不造成影响。 转移不成功,用保存下来的地址恢复PC1和PC。 软硬件共同配合,都往同一个方向去猜测。 静态分支预测技术(续) 3.两个先行指令缓冲栈 向前条件转移,转移成功与不成功各50% 在先行指令缓冲栈中增加一个先行目标缓冲栈 按照转移成功的方向预取指令到先行目标缓冲栈中。 先行指令缓冲栈仍然按照转移不成功的方向继续预取指令。 如果转移不成功,则继续分析原来先行指令缓冲栈中指令。 如果转移成功,则分析新增设的先行目标缓冲栈中的指令。 静态分支预测技术(续) 静态分支预测技术(续) AIB,新增先行指令缓冲栈,IB原先行指令缓冲栈。 TR1,TR2,保存PC1和PC中的内容,转移不成功,恢复PC1和PC。 短循环程序的处理 在循环程序中存在大量的短循环程序,对于短循环程序,一般先行指令缓冲栈的效率很低,一种极端的情况是:当循环体只有一条指令,先行缓冲栈失效。指令分析器分析完该指令后就清除指令缓冲栈,重新到主存取指令。 短循环程序的特点: 循环体的长度小于等于先行指令缓冲栈的深度。 使得在循环程序执行过程中,整个循环体能够始终存放在先行指令缓冲栈不被清除。循环程序可以多次重复使用减少访问主存的次数。 循环次数的控制采用计数转移指令实现。 因为计数转移指令可以在指令分析器中直接执行,指令分析器分析到这种特殊条件转移指令时不必等到指令执行部件形成条件码,而在指令分析器中就可以判断循环出口条件是否满足。 控制循环的条件转移指令一般是向后转移的指令。 短循环程序的处理(续) 要在先行控制器中对短循环程序作特殊处理,必须解决好三个问题: 指令分析器如何发现短循环程序。 如何控制短循环程序在先行缓冲栈不被清除。 如何控制循环体的执行次数,即处理好循环体的出口。 短循环程序的处理(续) 方法一: 在指令系统中专门设置短循环程序的开门指令和关门指令,由编译器在对源程序进行编译时发现短循环程序,并在其开头加上短循环开门指令,在末尾加上关门指令。 在指令分析器中增加专门的硬件来处理短循环开关门指令。 设置专门的短循环标志触发器TL。当TL=1时表示先行指令缓冲栈内是短循行程序而不被清除 短循环程序的处理(续) 执行过程: 指令分析器分析到开门指令表示循环开始,开门指令主要为循环做预处理: 将短循环程序的循环次数送入指令分析器的循环次数计数器。 设置短循环程序在先行指令缓冲栈的起始地址,即入口。 置位短循环标志触发器TL,表示短循环程序的开始。 先从指令缓冲栈中取出一条指令进行分析,如果TL=1,每从指令缓冲栈取一条指令,都不清除该指令。 执行到关门指令,循环体结束,指令缓冲栈放置了全部该段循环体的指令。每次循环都执行关门指令,关门指令控制循环体的次数。 短循环程序的处理(续) 关门指令的工作: 把循环计数器减1。 若循环计数器值大于等于1,现行程序计数器指向短循环程序的入口,准备下一次循环。若等于1, 还要把Tl清零。 当Tl=0时,每分析一条指令就清除该指令,先行缓冲栈恢复正常功能。 若循环计数器值为0,循环结束,顺序执行后续指令。 短循环程序的处理(续) 优缺点: 优点是硬件简单,开关门指令确定循环体,指令操作马即可识别此两条指令,不需专门的硬件。缺点是增加了程序员的负担。 方法二: 在有的机器中为使短循环程序处理对程序员透明,不采用专门的开关门指令。而是采用专门的硬件来识别短循环程序。 IBM360/370在指令分析器中有一个向后检测8条指令的功能,如果条件转移指令的转移目标地址和转移指令本身地址相差小于0,大于-8,即认为遇到短循环程序。处理方法和开关方法相同。 许多高性能处理机采用专门的一级指令Cache,把指令Cache和数据Cache分开,其中指令可以较长时间保存,有效提高循环程序的执行速度。 5.2 流水线处理机技术 空间并行性:设置多个独立的操作部件 时间并行性:分时使用同一个部件的不同部分 5.2.1 流水线 非线性流水线的调度 流水线.流水寄存器 流水线的每一个阶段称为流水步、流水步骤、流水段、流水线阶段、流水功能段、功能段、流水级、流水节拍等。 在每一个流水段的末尾或开头必须设置一个寄存器,称为流水寄存器、流水锁存器、流水闸门寄存器等。 加入流水寄存器,会增加指令的执行时间。 在一般流水线时空图中不画出流水寄存器。 2.一种指令流水线个流水段的称为超流水线.流水线时空图 流水线工作原理(续) 流水线工作原理(续) 一个浮点加法器流水线.流水线的主要特点 只有连续提供同类任务才能发挥流水线效率 尽量减少因条件分支造成的“断流” 通过编译技术提供连续的相同类型操作 每个流水线段都要设置一个流水寄存器 时间开销:流水线的执行时间加长 是流水线中需要增加的主要硬件 各流水段的时间应尽量相等 流水线处理机的基本时钟周期等于时间最长的流水段的时间长度。 流水线需要有“装入时间”和“排空时间” 流水线工作原理(续) 流水线.线性流水线与非线性流水线 流水线的各个流水段之间是否有反馈信号 线性流水线(Linear Pipelining): 每一个流水段都流过一次,而且仅流过一次 非线性流水线(Nonlinear Pipelining): 某些流水段之间有反馈回路或前馈回路。 线性流水线能够用流水线连接图唯一表示。 非线性流水线必须用流水线连接图和流水线预约表共同表示。 流水线.按照流水线的级别来分 处理机级流水线,又称为指令流水线。 例如:在采用先行控制器的处理机中,各功能部件之间的流水线 流水线的分类(续) 部件级流水线(操作流水线) 如浮点加法器流水线 宏流水线(Macro Pipelining) 处理机之间的流水线称,每个处理机对同一个数据流的不同部分分别进行处理。 流水线. 单功能流水线与多功能流水线 单功能流水线: 只能完成一种固定功能的流水线条 Pentium有一条5段定点和一条8段浮点流水线。 PentiumⅢ有两条定点和一条浮点指令流水线。 多功能流水线: 流水线的各段通过不同连接实现不同功能 Texas公司的ASC机,8段流水线,能够实现:定点加减法、定点乘法、浮点加法、浮点乘法、逻辑运算、移位操作、数据转换、向量运算等。 流水线.静态流水线与动态流水线 静态流水线:同一段时间内,多功能流水线各个功能段只能按照一种方式连接,实现一种固定的功能。 流水线的分类(续) 动态流水线:在同一段时间内,多功能流水线各段可以按照不同的方式连接,同时执行多种功能。 流水线的分类(续) 条件:流水线中各个功能部件之间不能发生冲突。 5.流水线的其他分类方法 按照数据表示方式:标量流水线和向量流水线 按照控制方式:同步流水线和异步流水线 顺序流水线与乱序流水线,按照流水线输出端流出的任务和流水线输入端流入的任务顺序是否相同划分。乱序流水线又称为无序流水线、错序流水线或异步流水线等。 流水线的分类(续) 线性流水线的性能分析 主要指标:吞吐率、加速比和效率 1.吞吐率(Though Put),单位时间内流水线所完成的任务数量或输出结果数量。 流水线吞吐率的最基本公式: 其中:n为任务数, Tk为完成n个任务所用的时间。 各段执行时间相等,输入连续任务情况下,完成n个任务需要的总时间为: Tk=(k+n-1)t 其中:k 为流水线的段数,t为时钟周期。 线性流水线的性能分析(续) 依据: 从输出端: 用k个时钟周期输出第一个任务,其余n-1个周期,每个周期输出一个任务,共n-1个任务。 从输入端: 用n个周期输入n个任务。另外还有k-1个周期等待流水线排空。 线性流水线的性能分析(续) Tk= k·Δt + (n-1)Δt = (k+n-1)t 吞吐率为: 最大吞吐率为: 线性流水线的性能分析(续) 最大吞吐率和实际吞吐率的关系: 流水线的实际吞吐率要小于最大吞吐率。 实际吞吐率和Δt,流水线短数k,输入到流水线的任务数n相关。 只有n﹥﹥k时,才有TP≈TPmax。 线性流水线的性能分析(续) 各段时间不等,完成n个连续任务: 吞吐率: 最大吞吐率: 流水线各段执行时间不相等的解决办法 线性流水线)将“瓶颈”部分再细分(如果可分的话) 线性流水线的性能分析(续) 线性流水线.加速比(Speedup) 计算加速比的基本公式: 各段执行时间相等,输入连续任务情况下,加速比: 最大加速比: 各段时间不等,输入连续任务情况下, 实际加速比为: 线性流水线的性能分析(续) 是否流水线的段数越多越好? 当流水线段数增加时,需要连续输入的任务数也必须增加。 由于程序中存在数据相关、转移、中断等情况。任务数n受到很大限制。 控制的复杂性,电路的实现及组装技术,实现的成本等的限制,流水线.效率(Efficiency)——流水线的设备利用率。 计算流水线效率的一般公式: 各流水段时间相等,输入n个连续任务,流水线的效率为: 最高效率为: 各流水段时间不等,输入n个连续任务,流水线效率为: 线性流水线的性能分析(续) 各段设备量或价格不等时,流水线的效率为: 即: 其中,ai<k,且=k。 流水线的吞吐率、加速比与效率的关系: 因为: 因此:E=TP · t,S=k ·E 线性流水线.流水线最佳段数的选择 采用顺序执行方式完成一个任务的时间为t 在同等速度的 k 段流水线上执行一个任务的时间为:t/k+d (d为流水锁存器的延迟时间) 流水线/(t/k+d) 流水线的总价格估计为:C=a+b k, 其中:a为功能段身的总价格, b为每个锁存器的价格son把流水线的性能价格比PCR定义为: 线性流水线的性能分析(续) 线性流水线的性能分析(续) 求PCR的最大值为: 5. 流水线性能分析举例 对于单功能线性流水线,输入连续任务的情况,通过上面给出的公式很容易计算出流水线的吞吐率、加速比和效率。 对于输入不连续任务,或多功能流水线,通常采用基本公式计算。 例:用一条4段浮点加法器流水线个浮点数的和:Z=A+B+C+D+E+F+G+H 线性流水线的性能分析(续) 解: Z=[(A+B)+(C+D)]+[(E+F)+(G+H)] 线性流水线的性能分析(续) 解: 线性流水线的性能分析(续) 线性流水线的性能分析(续) 例,多功能、线形流水线,输入任务是不连续的情况,计算流水线的吞吐率、加速比和效率。利用Ti-ASC多功能静态流水线计算两个向量的点积:Z=AB+CD+EF+GH。 解,为减少数据相关性充分发挥流水线个乘法,AB,CD,EF,GH。然后坐两个加法AB+CD和EF+GH。最后求总的结果Z。 线性流水线的性能分析(续) 流水线的时空图: 线个运算。每个功能能段的延迟时间都为△t,则Tk=20 △t,n=7。 则有流水线吞吐率TP为: 如果采用顺序执行方式,完成一次乘法要用4个△t ,完成一次加法要用6个△t ,完成全部运算要用:T0=4×4 △t+3×6 △t=34△t。流水线的加速比S为: 整个流水线段,流水线的效率E为: 线性流水线的性能分析(续) 整个流水线效率很低: 多功能流水线在做某一运算时,总有一些功能段是闲置的。 静态流水线必须等前一种运算运算全部排除流水线之后才能重新进行连接。 计算本身存在数据相关,发生数据相关时必须等待前一个运算结果产生之后,下一个运算才能开始。 流水线有装入和排空部分,当输入到流水线中的任务不多时,装入与排空部分所占的比例比较大。 非线性流水线的调度 非线性流水线中存在反馈回路,当一个任务在流水线中流过时,在同一功能段中可能要多次经过。 不能在一个时钟周期内向流水线输入一个任务,否则会发生在同一个时刻有几个任务争用同一个功能段的情况。称为功能部件冲突或者流水线冲突。 为避免冲突,采用延迟输入新任务的方法。间隔几个周期再输入新任务。 间隔的周期数不是一个常数。而是一串周期变化的数字。 非线性流水线的调度(续) 非线性流水线调度的任务是要找出一个最小的循环周期,按照这周期向流水线输入新任务,流水线的各个功能段都不会发生冲突,而且流水线的吞吐率和效率最高。 1.非线性流水线的表示 线性流水线能够用流水线连接图唯一表示 对于非线形流水线,连接图不能唯一表示工作流程,因此,引入流水线预约表 非线性流水线的调度(续) 例如: 非线形流水线的连接图和预约表 非线性流水线的调度(续) 四个功能段组成非线性流水线。 与线性流水线相同地方: 从第一个功能段S1到最后一个功能段S4的单方向传输线。 不同的地方: 有两条反馈线和一条前馈线。 输出端经常不在最后一个功能段,可能从中间的任意一个功能段输出。 非线性流水线的调度(续) 预约表: 预约表的横坐标表示流水线工作的时钟周期,纵坐标表示流水线的功能段。 中间的X表示该功能段在该时钟周期处于工作状态。即有任务在该时钟段通过该功能段。空白表示该时钟周期该功能段不工作。 一行可以有多个X,表示一个任务在不同时钟周期重复使用同一个功能段。一列可以有多个X,指同一个时钟周期多个功能段被使用。 预约表的行数是非线性流水线的段数。列数是指一个任务从进入流水线到从流水线输出经过的时钟周期数。又称为功能求值时间或装入时间。 非线性流水线的调度(续) 一张预约表可能与多个流水线连接图相对应 原因:在预约表的同一列中可能有多个X,即该时钟周期有多个功能段输出,下一功能段的输入有多个来源,从而应对有多个连接图。 非线性流水线的调度(续) 一个流水线连接图对应与多张预约表 原因:非线性流水线的有些功能段可能有多个输出端,也有些功能段有多个输入端,输出端和输入端之间连接的先后次序形成多张预约表。 非线性流水线.非线性流水线的冲突 启动距离:连续输入两个任务之间的时间间隔,又称等待时间。 流水线冲突:以某启动距离连续向一条非线性流水线输入任务,可能会存在几个任务争用同一个流水段。 非线性流水线的调度(续) 非线性流水线的调度(续) 引起非线性流水线功能段冲突的启动距离称为禁止启动距离。 有些启动距离在非线性流水线的所有功能段,在任何时间都不会发生冲突,如前表的(5),(1,7)。 不发生冲突的启动距离不一定仅仅是一个常数,在一般情况下是一个循环数列。称为非线性流水线的启动循环。只有一个启动距离的启动循环又称为恒定循环。 非线性流水线的调度(续) 要正确的调度一条非线性流水线,首先需要找到流水线的所有禁止启动距离。把所有禁止启动距离组合在一起形成数列,称为非线性流水线的禁止向量。 计算禁止向量: 把预约表中每一行中任意两个X之间的距离算出来,去掉重复的,这些数组成数列就是该非线性流水线的禁止向量。 把一个启动循环内的所有启动距离相加再除以这个启动循环内的启动距离个数就得到该启动循环的平均启动距离。 3.无冲突调度方法 主要目标:找出最小平均启动距离的启动循环。 由E.S.Davidson及其学生于1971年提出 禁止向量:预约表中每一行任意两个“×”之间距离的集合。上例中为(3,4,6) 冲突向量:用C=(CmCm-1…C2C1)表示,m位的二进制数。 其中:m是禁止向量中的最大值。 如果i在禁止向量中,则Ci=1,否则Ci=0。 上例中C=(101100) 非线性流水线的调度(续) 非线性流水线的调度(续) 由冲突向量可以构造状态图。 将冲突向量C作为初始冲突向量送入m位的右移逻辑移位器。移出为0,移位器内的值和初始冲突向量做按位或运算。得到一个新的冲突向量。 移出为1,不做任何处理。移位器继续右移。 中间形成的新的冲突向量,也按上述方法处理。 在初始向量和新的冲突向量之间用箭头连接,并标注右移次数。表示各种状态之间的转换关系,向量重复时合并到一起。 非线性流水线的调度(续) 当初始冲突向量确定后,状态图就是唯一的。 不同的预约表可能产生相同的初始冲突向量,因而不同的预约表也可能有相同的状态图。从预约表可以画出状态图,冲状态图不能获得预约表。 当启动距离大于或等于m+1时,流水线的任何一个功能段在任何时钟周期都不会发生冲突,但流水线的吞吐率、加速比、效率都很差。 例:一条4功能段的非线性流水线,每个功能段的延迟时间都相等,它的预约表如下: (1)写出流水线的禁止向量和初始冲突向量。 (2)画出调度流水线)求最小启动循环和最小平均启动距离。 (4)求平均启动距离最小的恒定循环。 非线性流水线的调度(续) 解: (1)禁止向量为:(2,4,6) 初始冲突向量:S = 101010 (2)构造状态图 S逻辑右移2、4、6位时,不作任何处理, 逻辑右移1、3、5和大于等于7时: S右移1位之后:010101∨101010=111111, S右移3位之后:000101∨101010=101111, S右移5位之后:000001∨101010=101011, S右移7位或大于7位后:按位或就还原到它本身。 非线性流水线的调度(续) 非线性流水线的调度(续) 新冲突向量再处理: 101111右移5位之后:000001∨101010=101011, 101011右移3位之后:000101∨101010=101111, 101011右移5位之后:000001∨101010=101011。 简单循环:状态图中各种冲突向量只经过一次的启动循环。在一个状态图中,简单循环的个数是有限的。 (3)最小的启动循环为(1,7)和(3,5), 平均启动距离为 4。 (4)启动距离最小的恒定循环为(5) 非线性流水线的调度(续) 非线性流水线的调度(续) 非线性流水线.优化调度方法 采用最小启动循环启动非线性流水线时,许多功能段还有空闲,即预约表中还有空白格子。最小启动循环实际上不能使非线性流水线充分发挥效率。 L.E.Shar于1972年提出流水线最小平均启动距离的限制范围: 最小平均启动距离的下限是预约表中任意一行里“×”的最多个数。即同一任务通过流水线中任意一个功能段的次数。 最小平均启动距离小于等于状态图中任意一个简单循环的平均启动距离。 最小平均启动距离的上限是冲突向量中1的个数再加上1。 1992年,L.E.Shar又证明了上述限制范围。 最有用的是第1条。预约表中“×”最多的行一定是瓶颈流水段。要使整个流水线最大发挥作用,必须使瓶颈功能段不间断工作。不得空闲。 非线性流水线的调度(续) 非线性流水线的调度(续) 采用预留算法来调度非线性流水线,可以达到最优调度。 确定流水线的最小平均距离,最小平均距离等于预约表中任意一行中X的最大个数。或者同一个任务流过任意功能段的最多次数。 确定最小启动循环,相对于同一个最小平均启动距离可能有多个最小启动循环。其中有一个且只有一个启动距离都相等的恒定循环。选用该恒定循环为最小启动循环。 结合流水线预约表和连接图,采用预留算法,通过插入非计算延迟功能段实现最小启动循环。 对于前例的预约表,在同一行中“×”最多的为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。 非线性流水线的调度(续) 非线性流水线的调度(续) 非线性流水线的调度(续) 在非线性流水线中,“×”最多的流水段一定是“瓶颈“流水段。 实现最优调度的目标是使“瓶颈”流水段处于忙碌状态,没有空闲周期。 最优调度方法能够使非线性流水线的吞吐率、加速比和效率达到最优。 非线性流水线的调度(续) 局部相关 在流水线处理机中由于处理的指令条数很多,发生相关的可能性及其造成的影响将更严重。 按照对程序执行过程可能造成的影响划分:可以把相关分为局部相关和全局相关两类。 如图,程序中一条分支指令把程序划分为三个部分,每部分内部不再有分支操作,这种部分称为基本块。 局部相关(续) 同一个基本块内部的相关称为局部相关(lacal correlation) 在基本块之间的相关成为全局相关(global correlation )。引起全局相关的除了分支操作还有中断。 局部相关对程序执行影响较小,仅限于相关指令临近的几条指令。全局相关影响很大,影响到整个程序的执行方向。 局部相关(续) 促使流水线充分发挥作用,需要软硬件结合。 软件编译的目标代码要适合流水线结构,尽量把相关数据和相关控制的指令安排得远一些。把相同操作尽量安排在一起。 在硬件方面解决好存储系统的频带问题,能够为流水线提高足够的指令和数据。解决好流水线的局部相关和全局相关。 局部相关包括: 先写后读数据相关,先读后写数据相关,写写相关三种。 顺序流动与乱序流动 1.顺序流动方式:任务按顺序流入流水线,也按顺序流出流水线 把如下一段程序输入到这条流水线)+(R3) k+3: …… k+4: …… k+5: …… 指令k+2无法继续执行,要在功能段S2中等待。 后续的指令k+4、k+5、……等也不能进入流水线将逐渐空闲。 缺点:吞吐率和效率降低 优点:流水线的控制逻辑比较简单 顺序流动与乱序流动(续) 顺序流动与乱序流动(续) 流水线“断流”,有些功能段“空闲” 2.乱序(Out of order)流动方式:指令流出流水线的顺序与流入流水线的顺序不同。又称为错序流动方式、无序流动方式、异步流动方式等。 顺序流动与乱序流动(续) 乱序流动中的数据相关 在乱序流动方式中,可能发生三种数据相关 写写相关 k:LOAD F1, A ;F1(A) 写读相关 k+1:FADD F2, F1 ;F2(F2)+(F1) k+2:FMUL F1, F3 ;F1(F1)(F3) k+3:STORE F1, B ;B(F1) 读写相关 (1)写读相关:指令k与指令k+1之间关于F1的相关,又称为数据相关、先写后读相关、流相关、WR相关、RAW相关等。 (2)读写相关: 指令k+1与指令k+2之间关于F1的相关,变量名相关、先读后写相关、反相关、RW相关、WAR相关等。 (3)写写相关: 指令k与指令k+2左边的F1之间的相关关系称为:输出相关、写写相关、WW相关、WAW相关或写后再写相关等。 有时把相关称为“冒险”(hazard)、“竟争” (competition)等。 在程序执行过程中,只有避免相关,执行结果才是正确的。 乱序流动中的数据相关(续) 乱序流动中的数据相关(续) 测试先写后读数据相关的方法: 在流水线的读书操作功能段设置一个相联比较器,在指令读操作数之前,把源操作数地址和已经在流水线中的从读数功能段到写结果功能段之间的所有指令的目标地址进行比较,发现地址相等,则表明发生了先写后读相关。 测试先读后写,写写相关的方法: 在流水线的写功能段设置相联比较器,把自己的目标操作数地址分别与已经进入流水线的指令序号比自己小的源操作数地址和目标操作数地址进行比较。发现源操作数地址相等,发生先读后写相关,发现目标操作数地址相等,发生了写写相关。 乱序流动中的数据相关(续) 三种数据相关可以用下列关系式来表示: 对于写读相关 D(i) ∩ S(j) ≠  对于读写相关 S(i) ∩ D(j) ≠  对于写写相关 D(i) ∩ D(j) ≠  乱序流动中的数据相关(续) 在流水线中避免数据相关的方法分为两类: 延迟执行。 优点是流水线的控制简单,缺点是流水线的吞吐率和效率很低。 建立专用路径。 分散控制的公共数据总线法。 集中控制的CDC记分牌法。 流水线的吞吐率和效率有比较大的提高。 在流水线中建立专用数据路径是高性能处理机的通用方式。 数据重定向方法 1.三种数据相关的重定向 重定向之前,j只能在i之后执行。 重定向之后,可以做到: (1)写读相关,j与i可以同时执行。 即专用数据通路。 (2)写写相关,先后顺序无关。 (3)读写相关,先后顺序无关。 后两种情况又称为“变量换名技术” 数据重定向方法(续) 2.变量换名技术 用来自动消除读写数据相关和写写数据相关。 规则:一个变量只允许定值一次。 在三种数据相关中,实际上只有写读数据相关必须依靠硬件、或采用软硬件结合的方法来解决。 解决方法:推后处理或专用数据通路。 在上面的数据重定向图中,把B换成了B’,并在以后的都引用B’读写数据相关和写写数据相关就不存在了。 数据重定向方法(续) 数据重定向方法(续) 一个实际例子: Loop: LD F0, 0(R1) ADD F0, F2 SD 0(R1), F0 LD F0, -8(R1) ADD F0, F2 SD -8(R1), F0 LD F0, -16(R1) ADD F0, F2 SD -16(R1), F0 LD F0, -24(R1) ADD F0, F2 SD -24(R1), F0 SUBI R1, R1, #32 BNEZ R1, Loop Loop: LD F0, 0(R1) LD F4, -8(R1) LD F6, -16(R1) LD F8, -24(R1) ADD F0,F2 ADD F4,F2 ADD F6,F2 ADD F8,F2 SD 0(R1), F0 SD -8(R1), F4 SUBI R1, R1, #32 SD -16(R1), F6 BNEZ R1, Loop SD -24(R1), F8 数据重定向方法(续) 3.一个简单的程序: k: LOAD F1, A k+1: FADD F1, F2 k+2: FMUL F1, F3 k+3: STORE F1, B 专门设置:A→FADD、FMUL→B、FADD→FMUL三条专用路径。 撤消:F1→FADD、F1→FMUL、FADD→F1 、A→F1的路径。 数据重定向方法(续) Tomasulo动态调度算法 实用的动态调度算法主要有两种: (1)集中控制:CDC计分牌(scorebord)算法. 最先在CDC 6600大型机中采用。 (2)分散控制:Tomasulo算法, 公共数据总线法,令牌法等。 最早在大型机IBM 360/91的浮点处理部件中被采用。 以上面的一段程序为例说明Tomasulo算法 k: LOAD F1, A k+1: FADD F1, F2 k+2: FMUL F1, F3 k+3: STORE F1, B Tomasulo动态调度算法(续) 全局相关 由条件转移或程序中断引起的相关称为全局相关,在流水线中全局相关对流水线的吞吐率和效率的影响相对于局部相关要大得多。 条件转移指令和中断指令与后续指令存在一种相关。使他们不能同时进入流水线中执行。 全局相关(续) 处理好条件转移和中断的关键问题有两个: 要确保流水线能够正常工作 减少因“断流”引起的吞吐率和效率的下降 1.条件分支的处理方法 条件转移指令对流水线的影响很大,必须采取措施来减少这种影响。可能的措施有: (1)延迟转移技术和指令取消技术 只能用于单流水线处理机中,且流水线的级数不能太多; 据统计,编译器调度一条指令成功的概率在90%以上,而调度两条指令成功的概率只有40%左右。 当没有合适的指令可调度时,编译器只能插入空操作。 (2)动态分支预测技术 根据近期转移是否成功的记录来预测下一次转移的方向。 所有的动态转移预测方法都能够随程序的执行过程动态地改变转移的预测方向。 全局相关(续) (3)静态分支预测技术 转移预测的方向是确定的,或者预测转移不成功,或者预测转移成功, 在程序实际执行过程中,转移预测的方向不能改变。 静态转移预测可以只用软件实现,也可用硬件来实现,还可以在转移的两个方向上都预取指令。 TI公司的SuperSPARC处理机采用了静态转移预测技术,而且设置有转移目标缓冲栈,在两个方向上都预取指令。 (4)提前形成条件码 全局相关(续) 2.条件分支在流水线中的执行过程 因为第i条指令所需要的条件码由第i-1条指令给出;在一条由k个功能段的流水线条指令要等到第i+k-2条指令进入流水线时才能形成条件码。 转移不成功,猜测正确,流水线的吞吐率和效率没有降低, 转移成功,猜测错误,要先作废流水线指令;然后再从分支点开始执行第P、p+1、……指令。一条k段流水线个功能段是浪费的。 全局相关(续) 全局相关(续) 条件分支指令在流水线中的执行过程 当分支的执行方向猜测错误时,可能造成程序执行结果发生错误。 例如,若第i+1条指令是:(R1+(R2)→R1,寄存器R1中内容就被破坏,整个程序执行的结果是错误的。 目前的处理机有两种做法: 一种方法是只进行指令译码和准备好运算所需要的操作数,在转移条件没有形成之前不执行运算。 另一种方法是一直执行到运算完成,但不送回运算结果。 全局相关(续) 3. 条件分支对流水线性能的影响 假设条件转移指令在一般程序中所占的比例为p,转移成功的概率为q。 n条指令的总的执行时间是: TK-IF=(n+k-1)t + npq(k-1)t 有条件转移影响的流水线吞吐率为: 有条件转移影响的流水线最大吞吐率为: 条件分支对流水线的影响(续) 流水线吞吐率下降的百分比为: 在典型程序中,转移指令占的比例为p=20%,转移成功的概率为q=60%。 对于一条8功能段的指令流水线,由于条件转移指令的影响,流水线的最大吞吐率要下降: 如果指令流水线,由于条件转移指令的影响,流水线的最大吞吐率将下降一半以下: 条件分支对流水线的影响(续) 动态分支预测技术 动态转移预测技术的两个关键问题: 如何记录转移历史信息 如何根据记录的转移历史信息预测转移方向 记录转移历史信息的方法有三种: 最近一次或几次转移是否成功的信息记录在转移指令中 用一个高速缓冲栈保存条件转移指令的转移目标地址 用Cache保存转移目标地址之后的n条指令 1.在指令Cache中记录转移历史信息 在指令Cache中专门设置一个字段,称为“转移历史表”。 在执行转移指令时,把转移成功或不成功的信息记录在这个表中。 当下次再执行到这条指令时,转移预测逻辑根据“转移历史表”中记录的信息预测转移成功或不成功。 动态分支预测技术(续) 只记录最近一次转移是否成功的历史信息 如果“转移历史表”中记录的内容是“T”,则预测转移成功,如果记录的是“N”,则按照转移不成功的方向继续取指令。 并用实际转移是否成功的信息来修改“转移历史表”。 动态分支预测技术(续) 记录最近两次转移是否成功的历史信息 图中采用偏向成功的预测策略:只有历史上最近两次执行这条转移指令时转移都没有成功,本次才预测转移不成功。 也可以采用其他预测策略 动态分支预测技术(续) “转移历史表”的修改规则和转移预测规则可以有多种多样, 记录转移预测是否成功的信息。 用最近预测是否成功的信息作为是否转移的依据 当“转移历史表”是空白时,可以有两种做法: 在“转移历史表”中预置转移历史信息。 根据指令本身的偏移字段的符号来预测转移的方向 如果偏移字段为负,则预测转移成功,否则预测转移不成功 动态分支预测技术(续) 主要优点: 不必专门设置转移缓冲栈, 所记录的转移历史信息比较少。 例如: DEC公司的Alpha 21064处理机就采用了这种转移预测方法, 在它的一级指令Cache中有一个专门的“转移历史表”字段。 动态分支预测技术(续) 动态分支预测技术(续) Alpha 21064的结构框图: 2.设置转移目标地址缓冲栈 用高速缓冲栈保存最近k条转移指令的“转移历史表”和转移目标地址 当前指令地址与转移目标缓冲栈中的所有转移指令地址进行比较;如果发现有相等的,则根据所记录的历史信息预测本次转移方向。 根据某种规则修改“转移历史表”。 动态分支预测技术(续) 3.设置转移目标指令缓冲栈 把上面方法中的“转移目标地址”字段改为存放转移目标地址之后的n条指令。 预测转移方向的规则和修改“转移历史表”的规则与上面的方法相同。 动态分支预测技术(续) 提前形成条件码 必要性:对提高流水线的性能非常有效。 可能性:可在运算开始或中间产生条件码。 对于乘除法,两个源操作数的符号相同结果为正,符号相反结果为负。 对于乘法,有一个操作数为0,则乘积为0。 被除数为0,商为0; 除数为0,除法结果溢出。 同号加或异号减,结果符号与第一操作数相同。 异号加或同号减,结果的符号与绝对值大的操作数相同。 溢出及是否为0可以通过一个比较器提前产生。 只要在一个时钟周期之内产生条件码,流水线就不会“断流”。 如Amdahl470V/6在运算部件的入口处设置药有一个LOCK部件,提前形成条件码。 把产生条件码与使用条件码的指令分开 LOAD R1,NUM ;循环次数初值装入R1 LOOP:…… ;循体开始 …… DEC R1 ;循环次数减“1” BNE LOOP ;测试循环是否则结束 HALT ;程序结束 NUM: n 提前形成条件码(续) 可以编译成如下程序: LOAD R1,NUM ;循环次数装入R1中 LOOP:LDEC R1 ;一条专用的 ;循环次数减1指令 …… ;循体开始 …… LBNE LOOP ;一条专用的测试循环 ;是否结束的指令 HALT ;程序结束 NUM: n ;循环次数 指令LDEC和LBNE使用专用的条件码寄存器CCL。 CCL由LDEC设置,由LBNE使用,循环体中间的其他指令不破坏CCL 。 提前形成条件码(续) 精确断点与不精确断点 对于输入输出设备的中断服务,实际上不需要有精确断点。 比较简单的处理方法是:让已经进入流水线的所有指令都执行完成,断点就是最后进入流水线的那条指令的地址。 对于程序性错误和机器故障等引起的中断,它们出现的概率很低,处理原则:不在于缩短时间,关键是要正确保存现场和正确恢复断点。 不精确断点(Imprecise),流水线可以不断流 需要的硬件比较少,控制逻辑比较简单。 中断响应时间加长。 采用不精确断点法可能会发生如下两个问题: (1)程序的调试困难 早期的流水线处理机,多采用不精确断点法。 近期的流水线处理机一般都采用精确断点法。 精确断点与不精确断点(续) (2)程序执行的结果可能出错,例如: i:FADD R1, R2 ;(R1)+(R2)→R1 i+1:FMUL R3, R1 ;(R3)×(R1)→R3 当第i条指令执行到S6段时发现浮点加法结果溢出,于是发出中断服务申请。由于采用不精确断点法,已经进入流水线条指令将执行完成;因为第i+1条指令使用了不正确的R1,所以浮点乘法的执行结果是不正确的。 采用精确断(Precise)点法,要设置一定数量的后援寄存器,把整个流水线中所有指令的执行结果和现场都保存下来。 精确断点与不精确断点(续) 5.3 超标量处理机 5.3.1 基本结构 5.3.2 单发射与多发射 5.3.3 多流水线 超标量处理机性能 三种主流处理机: 超标量处理机 超流水线处理机 超标量超流水线处理机 超标量处理机(续) 基本结构 普通标量流水线处理机: 一条指令流水线,一个多功能操作部件, 每个时钟周期平均执行指令的条数小于1。 多操作部件标量处理机: 一条指令流水线,多个独立的操作部件, 指令级并行度小于1。 超标量处理机典型结构: 多条并行工作的指令流水线,多个独立的操作部件, 指令级并行度(ILP)大于1。 基本结构(续) Motorola公司的MC88110 有10个操作部件。 两个寄存器堆: 整数部件通用寄存器堆,32个32位寄存器。 浮点部件扩展寄存器堆,32个80位寄存器。 缓冲深度为4的先行读数栈。 缓冲深度为3的后行写数栈。 两个独立的高速Cache中,各为8KB,采用两路组相联方式。 转移目标指令Cache,用于存放另一条分支上的指令。 基本结构(续) 单发射与多发射 1.单发射处理机: 每个周期只取一条指令、只译码一条指令,只执行一条指令,只写回一个运算结果。 取指令部件和指令译码部件各设置一套; 只设置一个多功能操作部件或设置多个独立的操作部件; 操作部件中可以采用流水线结构,也可以不采用流水线结构。 目标是每个时钟周期平均执行一条指令,ILP的期望值为1。 2.多发射处理机: 每个周期同时取多条指令、同时译码多条指令,同时执行多条指令,同时写回多个运算结果。 多个取指令部件,多个指令译码部件和多个写结果部件。 设置多个指令执行部件,有些指令执行部件采用流水线结构。 目标是每个时钟周期平均执行多条指令,ILP的期望值大于1。 单发射与多发射(续) 单发射与多发射(续) 单发射与多发射(续) 单发射与多发射(续) 3.超标量处理机: 有两条或两条以上能同时工作的指令流水线 先行指令窗口:能够从指令Cache中预取多条指令,能够对窗口内的指令进行数据相关性分析和功能部件冲突检测。 例如:Intel公司的i860、i960、Pentium,Motolora公司的MC88110,IBM公司的Power 6000,TI公司生产SuperSPARC等 操作部件的个数一般多于每个周期发射的指令条数。通常为4 个至16个操作部件。 超标量处理机的指令级并行度:1<ILP<m 单发射与多发射(续) 单发射与多发射(续) 先行指令窗口类似先行指令控制技术中的先行指令缓冲栈。 可以读更多的指令,通过硬件判断哪些指令可以先发射到操作部件中去执行。 没有功能部件冲突、没有数据相关、控制相关的指令可以超越前边指令先行执行。 结合编译器的支持,可以把多条不相关指令调度到先行窗口。 先行窗口太小,调度效果不好。先行窗口太大,硬件又太复杂。一般为2-8条指令。 单发射与多发射(续) 多流水线调度 顺序发射(in-order issue)与乱序发射(out-order issue):指令发射顺序是按照程序中指令排列顺序进行的称为顺序发射 顺序完成(in-order completion)与乱序完成(out-order completion):指令完成顺序是按照程序中指令排列顺序进行的称为顺序完成 多流水线的调度主要有三种方法: 顺序发射顺序完成。 顺序发射乱序完成。 乱序发射乱序完成。 以如下6条指令组成的程序为例,说明这三种调度方法 I1:LOAD R1, A ;R1←(A) I2:FADD R2, R1 ;R2←(R2)+(R1) I3:FMUL R3, R4 ;R3←(R3)×(R4) I4:FADD R4, R5 ;R4←(R4)+(R5) I5:DEC R6 ;R6←(R6)-1 I6:FMUL R6, R7 ;R6←(R6)+(R7) 6条指令中有4个数据相关,包括2个写读相关,1个读写相关和1个写写相关。 多流水线调度(续) 多流水线.顺序发射顺序完成 共用10个时钟周期完成 还有8个空闲的时钟周期,其中5个周期纯粹为维持顺序才插入。 多流水线.顺序发射乱序完成 总的执行时间为9个时钟周期, 节省了一个时钟周期。少了5个空闲时钟周期。 多流水线. 乱序发射乱序完成(采用先行指令窗口) 没有空闲周期,功能部件得到充分利用。 总的执行时间为8个周期,节省2个周期。 资源冲突 如果操作部件采用流水线结构,发生资源冲突的可能性很小。 如果不采用流水线结构,发生资源冲突的可能性就比较大。 下面是一个由4条指令的程序例子: I1:FADD R0, R1 ;R0←(R0)+(R1) I2:FMUL R2, R3 ;R2←(R2)×(R3) I3:FADD R4, R5 ;R4←(R4)+(R5) I4:FMUL R6, R7 ;R6←(R6)+(R7) 资源冲突(续) 操作部件不采用流水线个空闲周期。 操作部件采用流水线个周期。 资源冲突(续) 操作部件采用流水线结构的原因分析 假每个周期发射m条指令,操作部件的延迟时间为k个周期, 如果操作部件不采用流水线结构,则使用同一个操作部件的两条指令应该至少相差m×k 如果操作部件采用k段流水线结构,则使用同一个操作部件的两条指令只需相差m或m以上 指令流水线之间,每个时钟周期发射的指令条数m在2至4之间。取中间值,k=7,m=3。 资源冲突(续) 为了不发生资源冲突,如果操作部件不采用流水线结构, 两条使用同一个功能部件的指令序号必须相差21或21以上。 如果操作部件采用流水线结构, 两条使用同一个功能部件的指令序号只需要相差3或3以上。 因此,在超标量处理机中,操作部件一般要采用流水线结构。 如果由于某种原因,操作部件不能采用流水线结构,则必须设置多个相同种类的操作部件 资源冲突(续) 普通标量处理机,希望相同操作连续出现。 只有连续出现相同操作的指令序列时,流水线的效率才能得到充分发挥。 超标量处理机则正好相反,希望相同操作不要连续出现。 相同操作的指令序列连续出现时,会发生资源冲突; 要求相同操作的指令能够相对均匀地分布在程序中。 超标量处理机的这种要求正好符合一般标量程序的特点。 资源冲突(续) 超标量处理机性能 单流水线普通标量处理机的指令级并行度记作(1, 1), 超标量处理机的指令级并行度记作(m, 1), 超流水线处理机的指令级并行度记作(1, n), 而超标量超流水线处理机的指令级并行度记作(m, n)。 在理想情况下,N条指令在单流水线标量处理机上的执行时间为: T(1, 1)=(k+N-1)t 在每个周期发射m条指令的超标量处理机上执行的时间为: 第一项为第一批m条指令同时通过m条指令流水线所需要的时间,第二项是剩余N-m条指令所需要的时间。 超标量处理机相对于单流水线标量处理机的加速比为: 超标量处理机的加速比的最大值为:S(m,1)MAX=m 超标量处理机性能(续) 超流水线 超流水线处理机性能 超流水线处理机的两种定义: 在一个周期内分时发射多条指令的处理机。 指令流水线的流水线处理机。 提高处理机性能的两种方法: 通过增加硬件资源来提高处理机性能——超标量处理机。 通过各部分硬件的重叠工作来提高处理机性能——超流水线处理机。 两种不同并行性: 超标量处理机采用的是空间并行性。 超流水线处理机采用的是时间并行性。 超流水线处理机(续) 指令执行时序 每隔1/n个时钟周期发射一条指令, 即处理机的流水线/n个时钟周期。 典型处理机结构 MIPS R4000处理机: 每个时钟周期包含两个流水段 是一种很标准的超流水线处理机结构。 指令流水线个流水段。 指令Cache和数据Cache的容量各8KB, 每个时钟周期可以访问Cache两次, 在一个时钟周期内可以从指令Cache中读出两条指令,从数据Cache中读出或写入两个数据。 主要运算部件有整数部件和浮点部件。 典型处理机结构(续) 典型处理机结构(续) 典型处理机结构(续) 如果在LOAD指令之后的两条指令中,任何一条指令要在它的EX流水级使用这个数据,则指令流水线要暂停一个时钟周期。 典型处理机结构(续) 超流水线处理机性能 指令级并行度为(1,n)的超流水线处理机,执行N条指令所的时间为: 超流水线处理机相对于单流水线普通标量处理机的加速比为: 加速比的最大值为:S(1, n)MAX=n K是指令流水线的功能段数或时钟周期数。 超标量超流水线处理机 超标量处理机设置多套指令执行部件,同时发射多条指令。超流水线处理机把一个时钟周期细分为多个流水线周期,每个流水线周期发送一条指令,一个周期发生多条指令。 超标量处理机需要更多数量的硬件晶体管,超流水线处理机需要更快速度的晶体管和更精确的电路设计。 结合起来就是超标量超流水线处理机,一个时钟周期发射m次,每次发射n条指令。 指令执行时序。 典型处理机结构。 超标量超流水线处理机性能。 三种处理机的性能比较。 指令执行时序 典型处理机结构 DEC公司的Alpha处理机为典型的超标量超流水线结构。 主要由四个功能部件和两个Cache组成: 整数部件EBOX 浮点部件FBOX 地址部件ABOX 中央控制部件IBOX 指令Cache和数据Cache 在EBOX内还有多条专用数据通路,可以把运算结果直接送到执行部件。 中央控制部件IBOX能够同时完成: 同时读出两条指令; 同时对两条指令进行译码,并作相关性检测; 如果资源和相关性允许,IBOX就把两条指令同时发射给EBOX、ABOX和FBOX三个执行部件中的两个。 指令流水线的控制方式: 采用顺序发射乱序完成。 在指令Cache中有一个转移历史表,实现条件转移的动态预测。 典型处理机结构(续) 典型处理机结构(续) Alpha 21064处理机共有三条指令流水线)整数操作流水线个流水段,其中,取指令2个流水段、分析指令2个流水段、运算2个流水段、写结果1个流水段。 (2)访问存储器流水线)浮点操作流水线个流水段,其中,浮点执行部件FBOX的延迟时间为6个流水段。 三条指令流水线,且每个时钟周期发射两条指令。因此,Alpha 21064处理机为超标量超流水线处理机。 典型处理机结构(续) 典型处理机结构(续) 超标量超流水线处理机的性能 指令级并行度为(m,n)的超标量超流水线处理机,连续执行N条指令所需要的时间为: 超标量超流水线处理机相对于单流水线标量处理机的加速比为: 在理想情况下,超标量超流水线处理机加速比的最大值为: S(m,n)MAX=m×n 三种标量处理机的性能比较 2.相对单流水处理机的加速比 3.实际能够达到的指令并行度 从三种标量处理机的性能曲线中,可以得出如下结论: 1.三种处理机的性能关系 超标量处理机的相对性能最高,其次是超标量超流水线处理机,超流水线处理机的相对性能最低,主要原因如下: (1)超标量处理机功能部件的冲突比超流水线处理机小。在指令执行过程中的许多功能段,超标量处理机都重复设置有多个相同的指令执行部件,而超流水线处理机只是把同一个指令执行部件分解为多个流水级。 三种标量处理机的性能比较(续) (2)条件转移等操作造成的损失,超流水线处理机要比超标量处理机大。 由于超流水线处理机采用深度流水线结构,对条件转移等操作比超标量处理机敏感。 (3)超流水线处理机的启动延迟通常要比超标量处理机大。 超标量处理机在每个时钟周期的一开始就同时发射多条指令。 超流水线处理机把一个时钟周期平均分成多个流水线周期,每个流水线周期只发射一条指令。 三种标量处理机的性能比较(续) 三种标量处理机的性能比较(续) 2.实际指令级并行度与理论指令级并行度的关系 当横坐标给出的理论指令级并行度比较低时,处理机的实际指令级并行度的提高比较快。 当理论指令级并行度进一步增加时,处理机实际指令级并行度提高的速度越来越慢。 在实际设计超标量、超流水线、超标量超流水线处理机的指令级并行度时要适当,否则,有可能造成花费了大量的硬件,但实际上处理机所能达到的指令级并行度并不高。 目前,一般认为,m 和 n 都不要超过 4。 三种标量处理机的性能比较(续) 一个特定程序由于受到本身数据相关和控制相关的限制,它的指令级并行度的最大值是确定的。这个最大值由程序自身的语义决定,与该程序在那种机器上执行无关。 对某一种程序,三条曲线收拢到一点,点的位置随程序变化而变化。 能够达到的指令并行级还和所采用的调度算法相关。实现最优调度算法很困难。 P问题、NP问题与NPC问题 1、P问题 P是一个判定问题类,这些问题可以用一个确定性算法在多项式时间内判定或解出。如果一个判定性问题的复杂度是该问题的一个实例规模n的多项式函数,这种可以在多项式时间内解决的判定性问题属于P类问题。P类问题就是所有复杂度为多项式时间的问题的集合。 NP是一个判定问题类,这些问题可以用一个确定算法在多项式时间内检查或验证出它们的解,P事实上很直观,我们通常在编程中求解的问题大多都是P类问题。比如说排序,找最短路径等。 P问题、NP问题与NPC问题 2、NP问题 然而有些问题很难找到多项式时间的算法(或许根本不存在),比如找出无向图中的哈米尔顿回路问题,但是发现如果给了该问题的一个答案,就可以在多项式时间内判断这个答案是否正确。 比如说对于哈米尔顿回路问题,给一个任意的回路,很容易判断是否是哈米尔顿回路(只要看是不是所有的顶点都在回路中就可以了)。 这种可以在多项式时间内验证一个解是否正确的问题称为NP问题。显然,所有的P类问题都是属于NP问题的,但是现在的问题是,P是否等于NP?这个问题至今还未解决。 NP这个类并不要求给出一个算法来求解问题本身,而只是要求给出一个确定性算法在多项式时间内验证它的解。 P问题、NP问题与NPC问题 3、NP完全问题 NP问题不一定都是难解的问题。 比如,简单的数组排序问题是P类问题,但是P属于NP,所以也是NP问题,但是后来人们发现还有一系列的特殊NP问题,这类问题的特殊性质使得很多人相信PNP,只不过现在还无法证明。这类特殊的NP问题就是NP完全问题(NPC问题,C代表complete)。 NP完全问题是求NP中判定问题的一个子类。 NPC问题存在着一个特殊性质,即如果一个NPC问题存在多项式时间的算法,则所有的NP问题都可以在多项式时间内求解,即P=NP成立。 这是因为,每一个NPC问题可以在多项式时间内转化成任何一个NP问题。比如哈米尔顿回路问题就是一个NPC问题。 NPC问题的历史并不久,cook在1971年找到了第一个NPC问题,此后人们又陆续发现很多NPC问题,现在可能已经有3000多个了。 一般认为NPC问题是难解的问题,因为他不太可能存在一个多项式时间的算法。类似哈米尔顿回路/路径问题,货郎担问题,集团问题,最小边覆盖问题等等很多问题都是NPC问题。 P问题、NP问题与NPC问题 4、NP困难与NP完全问题证明 多项式时间归约:设A和B是两个判定问题。如果存在一个确定性算法C,它的行为如下:当给C展示问题A的一个实例时,算法A可以把这个实例变换成问题B的一个实例,使得A的实例跟B的实例有相同的YES/NO应答,并且这个变换在多项式时间内完成。那么说A多项式时间归约到B。 事实上,可以将多项式时间归约看做是一个函数的映射,即F(A)=B。并且这个F是多项式时间内可计算的。也就是说问题A实现上可以通过它自身满足的条件,通过一些形式上的改变而变换到问题B。 P问题、NP问题与NPC问题

http://deafbook.net/xianxingzhilingzhan/209.html
锟斤拷锟斤拷锟斤拷QQ微锟斤拷锟斤拷锟斤拷锟斤拷锟斤拷锟斤拷微锟斤拷
关于我们|联系我们|版权声明|网站地图|
Copyright © 2002-2019 现金彩票 版权所有