计算机系统结构第六讲.ppt

计算机系统结构 (第六讲),厦门大学计算机科学系 陆达 2004年11月20日,第五章 标量处理机,什么是标量处理机？ 只有标量数据表示和标量指令系统的处理机称为标量处理机 提高处理机指令执行速度的途径有三种： （1）、提高处理机的工作主频 （2）、采用更好的算法和设计更好的功能部件 （3）、多条指令并行执行，称为指令级并行技术 a、流水线处理机、超流水线处理机 （superpipelining） b、多操作部件处理机、超标量处理机 （superscalar） 超标量超流水线处理机（ a+b） c、超长指令字（VLIW）,本章主要内容： （1）、流水线技术（先行控制技术、流水线原理、流水线性能分析、非线性流水线的调度方法、局部数据相关和全局数据相关的处理方法） （2）、超标量处理机 （3）、超流水线处理机,5.1 先行控制技术,先行控制（look-ahead）技术 超流水线处理机、超标量处理机 缓冲技术、预处理技术 指令分析器、指令执行部件,5.1.1 指令的重叠执行方式,图5.1：一条指令的执行过程 三个阶段都可能访问存储器,指令的执行方式： （1）、顺序执行方式 图5.2(a) T=3nt,（2）、一次重叠执行方式 图5.2(b) T=(1+2n)t,（3）、二次重叠执行方式 图5.2(c) T=(2+n)t,5.1.2 先行控制方式的原理和结构,要解决两个问题： （1）、要有独立的取指令部件、指令分析部件和指令执行部件 存储控制器（存控）、指令控制器（指控）、运算控制器（运控）,（2）、要解决访问主存储器的冲突问题 a、把主存储器分成两个独立编制的存储器 指令存储器（指存）、数据存储器（数存） 指令Cache、数据Cache（哈佛结构） b、指令和数据仍然混合存放在同一个主存储器内 低位交叉存取方式,3、先行控制技术 缓冲技术：在工作速度不固定的两个功能部件之间设置缓冲栈，用以平滑它们的工作（设置四个缓冲栈） 预处理技术：把进入运算器的指令都处理成寄存器-寄存器型（R-R型）指令，它与缓冲技术相结合，为进入运算器的指令准备好所需要的全部操作数,5.1.2.1 处理机结构,图5.3：采用先行控制方式的处理机结构,图5.4：指令缓冲栈（先行指令缓冲栈）的组成 指令缓冲寄存器（存储器）堆、先行程序计数器PC1、现行程序计数器PC,图5.5：先行控制方式的一次重叠执行 这里的“分析”=前面的“取指令+分析” T重叠=(1+n)t,有三个问题需要解决： （1）、指令分析部件和指令执行部件经常要相互等待，从而造成功能部件的浪费 （2）、数据相关，控制相关，变址相关 （3）、当出现转移或转子程序指令时，程序的执行过程就不是顺序的,5.1.2.2 指令执行时序,图5.6：分析指令和执行指令时间不相等时的一次重叠执行方式,图5.7：采用先行缓冲栈的指令执行过程 先行缓冲栈：先行指令缓冲栈、先行读数栈、先行操作栈、后行写数栈,图5.8：采用先行缓冲栈时指令执行过程的一种表示方法（图5.7的另一种表示方法）,5.1.2.3 先行缓冲栈,先行指令缓冲栈（指令缓冲栈）：用于平滑主存储器和指令分析器的工作 先行操作栈：指令分析器对已经存放在先行指令缓冲栈里的指令进行预处理，把处理之后的指令送入先行操作栈；先行操作栈是指令分析器和运算控制器之间的一个缓冲存储器；先行操作栈采用先进先出（FIFO）的方式工作，它由一个先行指令寄存器堆和有关控制逻辑等组成 预处理技术（RR型、RX型、RS型、RI型 - RR*型）,先行读数栈：是主存储器与运算器之间的一种缓冲存储器，用来平滑运算器与主存储器的工作；由一组缓冲寄存器和有关控制逻辑等组成；每一个缓冲寄存器由先行地址缓冲寄存器、先行操作数缓冲寄存器和标志字段等三部分组成 后行写数栈：是主存储器和运算器之间的一个缓冲存储器；由一组缓冲寄存器和有关控制逻辑等组成；每一个缓冲寄存器由后行地址缓冲寄存器、后行数据缓冲寄存器和标志字段等三部分组成,图5.9：采用先行控制方式时一个程序的执行过程,指令控制部件：先行控制器（先行指令缓冲栈、先行读数栈、先行操作栈、后行写数栈）+指令分析器 指令执行部件：运算器+运算控制器,5.1.2.4 缓冲深度的设计,缓冲深度问题：各个缓冲栈中的缓冲寄存器个数设置多少个？ 缓冲深度的静态分析方法： （1）、先行指令缓冲栈已经完全充满 L1*t1=(L1-DI)*t2 DI=L1*(t2-t1)/t2 （2）、先行指令缓冲栈原来是空的 (L2-DI)*t1=L2*t2 DI=L2*(t1-t2)/t1 吸收型指令（如转移指令等）：在指令分析器中就直接执行完成，不需要送到运算器中执行,例：L1=9，t1=1，t2=4 DI=7 图5.10：先行指令缓冲栈的工作时间关系图,提高主存储器的访问速度，对减少缓冲深度很有效（t2减少 - DI减少） DI（先行指令缓冲栈）DC（先行操纵栈） DR（先行读数栈）DW（先行写数栈）,5.1.3 数据相关,什么是相关（correlation）? 是指在一段程序的相近指令之间有某种关系，这种关系可能影响指令的重叠执行 相关分为两大类： （1）、数据相关 （2）、控制相关 数据相关：包括指令相关、主存操作数相关、通用寄存器相关、变址相关 解决数据相关的方法： （1）、推后分析法 （2）、设置专用路径,5.1.3.1 指令相关,例：结果地址（k）=指令地址（k+1） 由于第k+1条指令本身的内容取决于第k条指令的执行结果，从而产生指令相关 判断是否发生了指令相关：把每一条指令的结果地址与先行操作栈中、指令分析器中、先行指令缓冲栈中的所有指令地址进行比较 解决指令相关的根本方法：在程序设计中不允许修改指令 IBM370，有一条“执行”指令能够解决指令相关，又允许在程序执行过程中修改指令,5.1.3.2 主存操作数相关,例：结果地址（k）=主存操作数地址（k+1） 当指令的执行结果写到主存储器，所读取的操作数也取自主存储器时，就有可能发生主存操作数相关 A1（k）=A2（k+1） A1（k）=A3（k+1） 解决主存操作数相关的方法：推后处理法,图5.11：主存操作数相关及其处理方法,对设置有先行操作栈的处理机，解决操作数相关的办法： 对于刚进入先行操作栈中的指令在向主存读操作数之前，首先要把访问主存的地址与后行写数栈中的所有主存地址进行比较，如果发现有相等的，则先行操作栈的读操作数要暂缓进行，等到发生操作数相关的指令执行完成，并把结果写回到主存之后再开始读操作数,5.1.3.3 通用寄存器数据相关,在RR型指令和RS型指令的执行过程中，可能发生通用寄存器数据相关 R1（k）=R1（k+1），称为R1数据相关 R1（k）=R2（k+1），称为R2数据相关,解决通用寄存器数据相关的方法（共有四种）： （1）、通用寄存器是用D型触发器构成的，而且在通用寄存器到运算器之间建立有直接数据通路，即不设置缓冲寄存器或锁存器，则不会发生通用寄存器数据相关 图5.12：一种典型的运算器结构,（2）、分析指令推后一个周期执行 图5.13：IBM 370机的指令分析与执行的时间关系,（3）、分析指令仅推后一个节拍 图5.14：分析指令仅推后一个节拍的时间关系,（4）、设置专用数据通路 图5.15：设置专用数据通路解决通用寄存器数据相关 设置专用数据通路是通过增加硬件为代价来解决寄存器数据相关,5.1.3.4 变址相关,把通用寄存器兼作变址寄存器使用，由于在变址寄存器中存放的变址量在指令分析过程中要用它来计算有效地址，有可能发生变址相关 R1（k）=X2（k+1），称为一次变址相关 R1（k）=X2（k+2），称为二次变址相关,图5.16：一次变址相关和二次变址相关的时间关系（当t1t2时，将发生二次变址相关）,解决变址相关的方法： （1）、推后分析 （2）、设置专用通路 图5.17：用变址相关专用通路解决变址相关,解决各种数据相关的方法： （1）、采用硬件或软件的办法尽量避免数据相关发生 （2）、在确保指令正确执行的前提下，推后指令分析（推后分析法） （3）、设置相关专用通路来解决数据相关（设置专用路径）,5.1.4 控制相关,什么是控制相关？ 因为程序的执行方向可能改变而引起的相关称为控制相关 无条件转移指令、一般条件转移指令、复合条件转移指令、子程序调用指令、中断指令 数据相关：称为局部相关 控制相关：称为全局相关 “吸收型”指令（无条件转移指令、一般条件转移指令）：在指令分析器就执行完成，不需要送入先行操作栈和指令执行部件,5.1.4.1 无条件转移,无条件转移指令一般能够在指令分析器中就执行完成 图5.18：无条件转移指令的执行时序 （无条件转移指令对程序执行速度的影响很小）,5.1.4.2 一般条件转移,条件转移指令： （1）、一般条件转移指令 （2）、复合条件转移指令 图5.19：一般条件转移指令的执行时序,一般条件转移指令称为“吸收型”指令 转移不成功对先行控制器的影响不大，而当转移成功时，不仅指令执行过程变成了完全串行，而且要作废已经取到先行指令缓冲栈中的大量指令，从而白白地增加了处理机与主存之间的通信量,5.1.4.3 复合条件转移,复合型条件转移指令不是“吸收型”指令 图5.20：复合型条件转移指令的执行时序 （如果转移成功，对先行控制器造成的影响比一般条件转移指令还要大得多）,5.1.4.4 转移预测技术,RISC关键技术： （1）、延迟转移技术（p118） （2）、指令取消技术（p119） 在采用先行控制方式的处理机中，采用的技术： （1）、软件“猜测法” （2）、硬件“猜测法” （3）、两个先行指令缓冲栈,1、软件“猜测法”,要尽量降低转移成功出现的概率 图5.21：用编译器支持条件转移指令的执行,2、硬件“猜测法”,在先行指令缓冲栈的入口处再增设一个简单的指令分析器，当这个指令分析器检测到转移指令时，就把转移目标地址L送入先行程序计数器PC1中，同时保留当前PC1中的内容到另一个寄存器中，以备猜错时恢复原来的程序执行方向 软件“猜测法”和硬件“猜测法”共同配合，软件和硬件都往同一个方向去猜测,3、两个先行指令缓冲栈,对于普通条件转移指令（如IF语句），转移成功与不成功的概率一般各为50% 在先行指令缓冲栈中增加一个先行目标缓冲栈，当指令分析器分析到条件转移指令时，按照转移成功的方向预取指令到这个先行目标缓冲栈中，原来的先行指令缓冲栈仍然按照转移不成功的方向继续预取指令 AIB：新增加的先行目标缓冲栈 IB：原来的指令缓冲栈 TR1、TR2：暂存寄存器,图5.22：两个先行指令缓冲栈的条件转移指令执行流程,5.1.4.5 短循环程序的处理,对于短循环程序，一般先行指令缓冲栈的效率很低 短循环程序满足的三个条件： （1）、循环体的长度小于等于先行指令缓冲栈的深度 （2）、循环次数的控制采用计数转移指令实现 （3）、控制循环的条件转移指令一般是向后转移的指令,必须解决好三个问题： （1）、指令分析器如何发现短循环程序 （2）、如何控制短循环程序在先行指令缓冲栈中不被清除 （3）、如何控制循环体的执行次数，即处理好循环程序的出口 两种方法： （1）、在指令系统中设置专门的短循环程序的开门指令和关门指令 短循环标志触发器TL （2）、用专门的硬件来识别短循环程序，目的是使短循环程序的处理对程序员透明 一级Cache：一级指令Cache、一级数据Cache 可以有效地提高循序程序的执行速度,5.2 流水线处理机,空间并行性： 在一个处理机内设置多个独立的操作部件，并让这些操作部件并行工作 多操作部件处理机和超标量处理机 时间并行性： 采用流水线技术 流水线的基本原理、特点、分类、性能分析；非线性流水线的调度问题；流水线中的局部相关和全局相关的处理方法,5.2.1 流水线工作原理,什么是流水线工作方式？ 把一个重复的过程分解为若干个子过程，每个子过程可以与其他子过程同时进行 指令流水线 操作部件流水线 访问主存储器部件也可以采用流水线 在处理机之间，机器之间也可以采用流水线,5.2.1.1 从重叠到流水线,图5.23：一种简单的流水线 指令分析器、指令执行部件,图5.24：一种指令流水线 一条指令分为6个子过程,图5.25：浮点加法器流水线 图5.24的执行过程分解为4个小子过程,5.2.1.2 时空图,图5.26：描述流水线工作过程的时空图 横坐标：表示时间 纵坐标：表示空间，即流水线的各个子过程 “功能段”：流水线的一个子过程,图5.27：浮点加法器流水线的时空图,5.2.1.3 流水线的特点,（1）、在流水线中处理的必须是连续任务 （2）、把一个任务（一条指令或一个操作）分解为几个有联系的子任务，每个子任务由一个专门的功能部件来实现 （3）、在流水线的每一个功能部件的后面都要有一个缓冲寄存器（锁存器、闸门寄存器），用于保存本段的执行结果 （4）、流水线中各段的时间应尽量相等，否则将引起“堵塞”、“断流”等 （5）、流水线需要有“装入时间”和“排空时间”,5.2.2 流水线的分类,5.2.2.1 线性流水线与非线性流水线,线性流水线（linear pipelining） 将流水线的各段逐个串接起来，输入数据从流水线的一端进入，从另一端输出 非线性流水线（nonlinear pipelining） 在流水线的各个功能段之间除了有串行的连接之外，还有反馈回路 非线性流水线常用于递归调用，或构成多功能流水线等,图5.28：一种简单的非线性流水线,图5.29：非线性流水线的预约表 一条非线性流水线可以有很多张预约表，一张预约表实际上仅表示了一条非线性流水线的一种工作方式,5.2.2.2 流水线的级别,（1）、功能部件级流水线（部件级流水线）： 也称运算操作流水线（arithmetic pipelining），如前面的图5.25 （2）、处理机级流水线：也称指令流水线（instruction pipelining） 流水线处理机或超流水线处理机： 在指令执行部件中采用了流水线的处理机 多操作部件处理机或超标量处理机： 在指令执行部件中设置有多个操作部件的处理机,图5.30：先行控制方式中的指令流水线 包括指令控制部件（先行控制器+指令分析器）、指令执行部件,（3）、处理机间流水线：也称宏流水线（macro pipelining） 图5.31：一种宏流水线,5.2.2.3 单功能与多功能流水线,单功能流水线（unifunction pipelining）：一条流水线只能完成一种固定的功能 Cray-1、YH-1、Pentium、Alpha 21064 多功能流水线（multifunction pipelining）：流水线的各段可以进行不同的连接，在不同时间内，或在同一时间内，通过不同的连接方式实现不同的功能 Texas仪器公司的ASC,图5.32：TI-ASC计算机的多功能流水线 图5.32(a)：8段流水线 图5.32(b)：定点乘法 图5.32(c)：浮点加法 图5.32(d)：浮点点积，实际上是一条带有反馈回路的非线性流水线 多功能流水线、设置多条专门的单功能流水线,5.2.2.4 静态流水线与动态流水线,静态流水线（static pipelining） 在同一段时间内，多功能流水线中的各个功能段只能按照一种固定的方式连接，实现一种固定的功能,图5.33：静态流水线时空图,动态流水线（dynamic pipelining） 在同一段时间内，多功能流水线中的各段可以按照不同的方式连接，同时执行多种功能,图5.34：动态流水线时空图,按照不同的数据表示方式： （1）、标量流水线：用于标量处理机中 （2）、向量流水线：用于向量处理机中 按照对流水线的控制方式不同： （1）、同步流水线： （2）、异步流水线：一般的宏流水线多采用异步流水线方式 图5.35：一种异步流水线,按照流水线输出端流出的任务与流水线输入端流入的任务的顺序是否相同： （1）、顺序流水线： （2）、乱序流水线：也称无序流水线、错序流水线、异步流水线,5.2.3 线性流水线的性能分析,衡量流水线性能的主要指标有： （1）、吞吐率 （2）、加速比 （3）、效率 （4）、流水线的最佳段数,5.2.3.1 吞吐率,吞吐率（thoughput rate，TP）：是指在单位时间内流水线所完成的任务数量或输出的结果数量 TP=n/Tk n：任务数 Tk：处理完成n个任务所用的时间,图5.36：各段执行时间均相等的流水线时空图 TP=n/(k+n-1)*t TPmax=1/t TP=n/(k+n-1)*TPmax,图5.37：各段执行时间不相等的流水线及其时空图,TPmax=1/max(t1，t2 ， ，tk) TPmax=1/(3*t),当流水线中各个功能段的执行时间不完全相等时，流水线的最大吞吐率与实际吞吐率主要是由流水线中执行时间最长的那个功能段来决定，这个功能段就成了整个流水线的“瓶颈” 解决流水线“瓶颈”问题的方法： （1）、将流水线的“瓶颈”部分再细分，如图5.38 （2）、通过重复设置“瓶颈”功能段，让多个“瓶颈”功能段并行工作，如图5.39,图5.38：“瓶颈”功能段再次细分 TPmax=1/t,图5.39：“瓶颈”功能段重复设置的流水线 TPmax=1/t,由于流水线存在有装入和排空时间，输入的任务往往不是连续的，程序本身存在有数据相关，多功能流水线在完成某一种功能时有的功能段不使用等，是流水线的实际吞吐率要低于最大吞吐率,5.2.3.2 加速比,加速比（speedup ratio）：完成一批任务，不使用流水线所用的时间与使用流水