重叠流水和向量流水处理机计算机软件及应用it计算机专业资料.pptx

5.1 重叠方式重叠方式 重叠原理和一次重叠重叠原理和一次重叠 图图 5.1 对一条机器指令的解释对一条机器指令的解释 取指令分析执行。t t一、顺序解释一、顺序解释（sequence）：一条指令执行完再取下一条指令。）：一条指令执行完再取下一条指令。若各阶段执行时间相等，则共需若各阶段执行时间相等，则共需3 n t t 优点：优点：控制简单，节省设备；控制简单，节省设备；缺点：缺点：速度慢，机器各部件的利用率很低。速度慢，机器各部件的利用率很低。取k k分析k k执行k k取k+1k+1分析k+1k+1执行k+1k+1指令的解释方式一般分为顺序、重叠、流水三种。设指令工作方式分成取指令、分析、执行指令阶段第1页/共120页执行n条指令需：T=（1+2n）t；优点：指令执行时间缩短了近1/2；功能部件的利用率也有所提高；缺点：需要增加一些部件，控制也要复杂些；取k分析k执行k分析k+1取k+1执行k+1取k+2分析k+2执行k+2二、重叠（Overlap）：在两条相近指令的解释过程中，某些不同解释阶段在时间上存在重叠部分。1.上一条指令的执行阶段与下一条指令的取指阶段完全重叠；取k分析k执行k分析k+1取k+1执行k+1取k+2分析k+2执行k+22.将相邻两条指令的重叠时间再往前提前一个阶段；第2页/共120页执行执行n n条指令需要：条指令需要：T=T=（2+n2+n）t t指令的执行时间缩短了近指令的执行时间缩短了近2/32/3，是一种比较理想的指令执行方式；，是一种比较理想的指令执行方式；这这种种执执行行方方式式存存在在着着访访存存冲冲突突，要要解解决决访访主主存存的的冲冲突突问问题题,通通常常采采用用以以下下几种方式：几种方式：（1 1）主主存存分分成成两两个个独独立立编编址址的的存存储储器器，一一个个专专门门存存放放指指令令，一一个个专专门门存存放放操操作数；作数；（2 2）指指令令和和数数据据仍仍然然混混存存在在一一个个存存储储器器中中，采采用用多多体体交交叉叉主主存存结结构构，不不能能根根本解决本解决;(3(3）采用先行控制技术，增设采用先进先出方式工作的指令缓冲寄存器）采用先行控制技术，增设采用先进先出方式工作的指令缓冲寄存器。第3页/共120页3 3 一次重叠：一次重叠：把取指令操作隐含在分析、执行指令过程中，则把取指令操作隐含在分析、执行指令过程中，则在任何时候只允许上条指令在任何时候只允许上条指令“执行执行”与下条指令与下条指令“分析分析”相重叠。相重叠。分析k执行k执行k+1分析k+1连续执行连续执行n n条指令所需时间为：条指令所需时间为：T=T=（1+n1+n）t t；实际达到这个速度是很难得，存在几个问题：实际达到这个速度是很难得，存在几个问题：（1 1）各种类型的指令）各种类型的指令“分析分析”与与“执行执行”所需时间差别很大；所需时间差别很大；从而导致相互等待。从而导致相互等待。（2 2）当出现转移指令或转移子程序指令时，程序的执行过）当出现转移指令或转移子程序指令时，程序的执行过程就不是顺序的了，那么指缓中的内容以及已经分析完的程就不是顺序的了，那么指缓中的内容以及已经分析完的下一条指令都将作废；下一条指令都将作废；（3 3）数据相关以及控制相关；）数据相关以及控制相关；第4页/共120页三、先行控制三、先行控制 使分析和执行部件分别连续不断地运行，使部件空闲状态减使分析和执行部件分别连续不断地运行，使部件空闲状态减至最低。至最低。(a)重叠方式分析k+1分析k执行k执行k+1分析k+2执行k+2分析部件空闲执行部件空闲分析k+1分析k执行k分析k+2(b)先行控制执行k+1执行k+21.1.工作原理工作原理第5页/共120页 结果：结果：解决了分析与执行时间不等长问题。解决了分析与执行时间不等长问题。与重叠区别：与重叠区别：分析和执行部件可同时处理两条不相分析和执行部件可同时处理两条不相邻指令。邻指令。2.2.硬件要求硬件要求 增设指令缓冲栈，消除取指过程；增设指令缓冲栈，消除取指过程；增设数据缓冲栈，保证不同指令的读、写操作并行；增设数据缓冲栈，保证不同指令的读、写操作并行；增设先行操作栈，保证执行部件能连续执行。增设先行操作栈，保证执行部件能连续执行。第6页/共120页 硬件结构：硬件结构：主主 存存存存 控控指令分析器指令分析器 指令缓冲指令缓冲栈栈读数据缓冲读数据缓冲区区执行执行部件部件先行操作栈先行操作栈数据缓冲栈数据缓冲栈写数据缓冲写数据缓冲区区第7页/共120页相关处理相关处理 1.转移指令的处理转移指令的处理 采用延迟转移技术，将转移指令与条件转移无关的第采用延迟转移技术，将转移指令与条件转移无关的第k-1条指条指令交换一下位置，即使转移成功也不会使重叠效率下降。令交换一下位置，即使转移成功也不会使重叠效率下降。2.指令相关的处理指令相关的处理 “执行执行”指令是指令是IBM 370机器为此设置的一条指令，其形式为机器为此设置的一条指令，其形式为 执行R1X2B2D2当当执执行行到到“执执行行”指指令令时时，按按第第二二操操作作数数(X2)+(B2)+D2地地址址取出操作数区中单元的内容作为指令来执行，参见图取出操作数区中单元的内容作为指令来执行，参见图5.5。第8页/共120页图图 5.5 IBM 370“执行执行”指令的执行指令的执行 第9页/共120页3.主存空间数相关的处理主存空间数相关的处理 图图 5.6 主存空间数相关的处理主存空间数相关的处理 第10页/共120页4.通用寄存器组相关的处理通用寄存器组相关的处理设机器的基本指令格式为设机器的基本指令格式为 操作码L3L1B2d2或 操作码L3L1L2第11页/共120页图图 5.7 指令解释过程中与通用寄存器内容有关的微操作时间关系指令解释过程中与通用寄存器内容有关的微操作时间关系第12页/共120页图图 5.8 “执行执行k”、“分析分析k+1”重叠时，访问通用寄存器组的时间关系重叠时，访问通用寄存器组的时间关系（1）通用寄存器组数相关处理）通用寄存器组数相关处理第13页/共120页图图 5.9 用相关用相关专用通路解决专用通路解决通用寄存器组通用寄存器组的数相关的数相关 处理方法：处理方法：a.推后下一条指令的分析。推后下一条指令的分析。b.设置相关专用通路设置相关专用通路第14页/共120页（2）通用寄存器组基址值和变址值相关的处理）通用寄存器组基址值和变址值相关的处理图图 5.10 B一次相关与二次相关一次相关与二次相关 第15页/共120页图图 5.11 B一次、一次、二次相关的推后处理二次相关的推后处理 处理方法：处理方法：a.推后分析推后分析第16页/共120页图图 5.12 B相关专用通路法相关专用通路法 b.设置相关专用通路设置相关专用通路第17页/共120页5.2 流流 水水 方方 式式 基本概念基本概念 1.1.工作原理(重叠的进一步延伸)一种典型的指令流水线 流水线中每一个子过程还可以再进一步分解成更小的子过程将浮点加法器分解为求阶差、对阶、尾数加和规格化4个子过程。图5.13一种典型的指令流水线图5.14浮点数加法器流水线第18页/共120页流水线工作方式：指令一条接着一条从输入端流入，经过各个子过程后从输出端流出。时空图：描述流水线工作过程的二维坐标。对应图5.13所示的流水线的时空图如图5.15所示。图5.15对应图5.13流水线的时空图m t(n-1)t1 1）时空图第19页/共120页图5.16是对应5.14浮点数加法器流水线的时空图图5.16浮点数加法器流水线的时空图从横坐标方向看，流水线中的各个功能部件在逐个连续地完成自己的任务。从纵坐标方向看，在同一个时间段内有多个流水段在同时工作，执行不同的任务。第20页/共120页（2）流水线特点）流水线特点：1）流水一定重叠，比重叠更苛刻。）流水一定重叠，比重叠更苛刻。2）一条流水线通常有多个流水段组成。）一条流水线通常有多个流水段组成。3）每段有专用功能部件，各部件顺序连接，不断）每段有专用功能部件，各部件顺序连接，不断流。流。4）流水线有建立时间、满载时间、排空时间。）流水线有建立时间、满载时间、排空时间。5）各段时间尽量短、一致；不一致时最慢子过程）各段时间尽量短、一致；不一致时最慢子过程为瓶颈。为瓶颈。6）给出指标如最大吞吐率，为满负载最佳指标。）给出指标如最大吞吐率，为满负载最佳指标。第21页/共120页2 流水线分类分级：（处理的级别分类）分级：（处理的级别分类）部件级：指部件内各子部件间的流水，将复杂的部件级：指部件内各子部件间的流水，将复杂的算逻运算组成流水工作方式；算逻运算组成流水工作方式；处理机级：指构成处理机的各部件之间的流水，处理机级：指构成处理机的各部件之间的流水，如取指、分析、执行部件间的流水如取指、分析、执行部件间的流水 ；系统（处理机间）级：构成计算机系统的每个处系统（处理机间）级：构成计算机系统的每个处理机完成某一专门任务，各个处理机所得到的结果理机完成某一专门任务，各个处理机所得到的结果需存放在与下一个处理机所共享的存储器中需存放在与下一个处理机所共享的存储器中 。按流水具有的功能多少：按流水具有的功能多少：A.A.单单功功能能流流水水线线：指指流流水水线线内内各各段段固固定定连连接接，同同一一时间内只能完成单一的一种功能。时间内只能完成单一的一种功能。第22页/共120页TI-ASC运算器流水线（多功能）运算器流水线（多功能）输入输入减阶减阶对阶移位对阶移位相加相加规格化规格化相乘相乘累加累加输出输出12345678输入输入减阶减阶对阶移位对阶移位相加相加规格化规格化输出输出123458浮加、减浮加、减输入输入相乘相乘累加累加输出输出1678定乘定乘 B.B.多功能流水线：流水线中各段可以有多种不同的连接方式，以实现多种不同的运算和功能；第23页/共120页按工作方式分为：A.A.静态流水线：在某一时间内各段只能按一种功能连接流水，只有等流水线全部流空后，才能切换为另一种功能；B.B.动态流水线：各个段可以同时为不同的功能服务，也就是说各功能段在同一时间内可以按不同运算或功能连接；第24页/共120页浮加排空完，再进行定乘浮加未排空完，已输入定乘。为什么？产生冲突产生冲突第25页/共120页按流水线中各功能段是否有反馈回路，分为：A.A.线性流水线：各段串行联接，没有反馈回路，各个段只经过一次；B.B.非线性流水线：除有串行联接通路外，还有某种反馈回路，需多次经过某个段或越过某个段；按机器所具有的数据表示分为：标量流水机和向量流水机1234+出出入入非线性流水线非线性流水线+特点：动态流水线必是多功能流水线；单功能流水线必是静态流水线第26页/共120页 一、吞吐率、加速比和效率。一、吞吐率、加速比和效率。流水线处理机的主要性能流水线处理机的主要性能 1.1.吞吐率（吞吐率（Thoughput rateThoughput rate，TPTP）指在单位时间内流水线完成的任务数或输出的结果数。其中：n表示任务数，Tk表示完成n个任务所用的时间第27页/共120页（1）各段时间均相等的流水线各段时间均相等的流水线时空图 S1 S2 S3 S4tttt时间4t(n-1)t完成n个任务n个任务所需要的时间第28页/共120页流水线完成n个连续任务所需要的总时间为（假设一条k k段线性流水线）TkTkk kt t(n n-1)-1)t t(k kn n-1)-1)t t 流水线的实际吞吐率最大吞吐率TP=n(k+n-1)tTPmax=n(k+n-1)tlimn=1t第29页/共120页最大吞吐率与实际吞吐率的关系流水线的实际吞吐率小于最大吞吐率，它除了与每个段的时间有关外，还与流水线的段数k k以及输入到流水线中的任务数n n等有关。只有当n nk k时，才有TPTPTPTPmaxmax。第30页/共120页流水线中各个段的执行时间不完全相等，流水线出现“瓶颈”部件。时空图（a）各段执行时间不相等的流水线（b）各段执行时间不相等的时空图图5.17各段流水线不相等的流水线和时空图第31页/共120页流水线各段执行时间不相等的情况下的实际吞吐率为：流水线各段执行时间不相等的情况下的最大吞吐率为：对于图5.17所示的例子，流水线的最大吞吐率为：第32页/共120页解决流水线“瓶颈”问题有两种方法：一种方法：将流水线的“瓶颈”部分再细分（a）瓶颈功能段细分的流水线连接图（b）瓶颈功能段细分的时空图图5.18瓶颈功能部件细分的流水线和时空图流水线的最大吞吐率为：第33页/共120页另一种方法：将流水线的“瓶颈”子部件设置多套并联（a）重置瓶颈功能部件的流水线（b）重置瓶颈功能部件的时空图 图5.19重置瓶颈段的流水线和时空图流水线的最大吞吐率为：第34页/共120页2.2.加速比加速比 指流水线加速比是指完成一批任务时，不采用流水线所用的时间与采用流水线所用的时间之比 其中：用T0表示采用顺序方式下的执行时间；用T表示采用流水线的执行时间；用S表示流水线的加速比第35页/共120页（1）各个功能段执行时间均相等的k段流水线上完成n个连续任务的实际加速比为：在k个功能段相等的流水线中，最大加速比为：第36页/共120页（2）如果流水线上各个功能段的执行时间不相等，则流水线的加速比为：计算图5.17、图5.18所示的流水线的加速比？第37页/共120页3.3.效率效率 指流水线的设备利用率。其中：kTK：表示k段流水线完成n个任务的总的时空区；T0：表示流水线完成n个任务所使用的总时间；E：表示k段流水线的效率；即：在时空图上，流水线的效率为n个任务占用的时空区与k个功能段总的时空区之比。第38页/共120页（1）在流水线的各功能段执行时间相等连续输入n个任务的情况下，一条k段流水线的效率为：流水线的最高效率为：流水线效率与吞吐率的关系式：E=TPt 流水线效率与加速比的关系式：第39页/共120页（2）流水线的各段执行时间不相等连续执行n个任务时的流水线效率为：计算图5.17(b)的时空图所示，整个流水线的效率E？在图5.18和图5.19中分别采用的细分瓶颈功能部件和重置瓶颈功能部件的效率？第40页/共120页二二.标量流水线的性能举例标量流水线的性能举例【例5.1】采用前面图5.14所示的4段浮点数加法器流水线计算下面式子的8个浮点数的和，画出流水线的时空图，并求出流水线吞吐率、加速比和效率。Z=A+B+C+D+E+F+G+H解：Z=（A+B）+（C+D）+（E+F）+（G+H）按照数学计算顺序的方法从左到右一个一个计算上式，先计算（A+B），其结果出来后再开始计算（A+B）与C的加法，依次类推。第41页/共120页第42页/共120页流水线的实际吞吐率TP为：流水线的加速比Sp为：流水线的效率E为：第43页/共120页【例5.2】设向量A和B各有4个元素，图5.20为静态双功能的流水线连接图，其中，1235组成加法流水线，145组成乘法流水线，设每个流水线所经过的时间均为t，则计算向量点积画出完成上面运算流水线的时空图，并求出静态双功能流水线的实际吞吐率、加速比和效率。按照数学运算优先级顺序进行(a1b1)+(a2b2)+(a3b3)+(a4b4)的运算，分别用任务1到7表示。解：加加14325乘乘图5.20第44页/共120页第45页/共120页流水线的实际吞吐率TP为：流水线的加速比Sp为：流水线的效率E为：第46页/共120页【例5.3】假设图5.20表示的双功能流水线为动态双功能流水线，则重新计算向量点积要求画出完成上面运算流水线的时空图，并求出动态双功能流水线的实际吞吐率、加速比和效率。解：动态多功能流水线在不发生功能部件冲突前提下，同一时间可以按不同运算进行不同功能的连接。因此，只要任务1、任务2、任务3和任务4的结果输出，任务5和任务6就可以输入流水线。下图为在动态流水线下执行向量点积的时空图。第47页/共120页图6-17动态双功能流水线的时空图第48页/共120页流水线的实际吞吐率TP为：流水线的加速比Sp为：流水线的效率E为：第49页/共120页课堂练习有一个乘、加双功能的静态流水线，“乘”由1236完成，“加”由1456完成，各段如下图所示。若要计算：AB=（a1+b1）（a2+b2）（a3+b3）问：（1）完成全部运算所需时间是多少？画时空图计算此流水线的使用效率和吞吐率。（2）与顺序运算方式相比，加速比是多少？1234562t2t2t2ttt第50页/共120页一、局部性相关处理一、局部性相关处理（1 1）资源冲突（相关）资源冲突（相关）原因：原因：许多指令争抢同一功能部件。如访存许多指令争抢同一功能部件。如访存流水机器的相关处理和控制机构流水机器的相关处理和控制机构 1 1、各种局部性相关的处理包括资源或结构相关、指令相关、数据相关。两条指令同时访存造成资源相关两条指令同时访存造成资源相关MEMEXIDIF指令i+4WBMEMEXIDIF指令i+3WBMEMEXIDIF指令i+2WBMEMEXIDIF指令i+1WBMEMEXIDIFLoad指令87654321时钟指令冲突冲突取指取指 译码译码 执行执行 访存访存 写回写回例：例：第51页/共120页 解决方法：解决方法：a.时间方法时间方法-后续指令冲突部件推后一拍执行；后续指令冲突部件推后一拍执行；b.b.空间方法空间方法-重复设置资源。重复设置资源。EXIDIF指令i+4MEMEXIDIF停顿指令i+3WBMEMEXIDIF指令i+2WBMEMEXIDIF指令i+1WBMEMEXIDIFLoad指令87654321时钟指令9WBMEM使使i+3指令停顿一拍进入流水线，以解决访存相关指令停顿一拍进入流水线，以解决访存相关或重复设置一个存储器或重复设置一个存储器第52页/共120页（2 2）指令相关）指令相关 原因：原因：由指令可修改引起。由指令可修改引起。解决方案：解决方案：a.a.禁止方法禁止方法-指令不允许修改；指令不允许修改；b.b.转换方法转换方法-把新指令作为把新指令作为“执行执行”指令的指令的操作数，使指令相关变成数据相关。操作数，使指令相关变成数据相关。第53页/共120页（3 3）数据相关）数据相关原因：原因：对主存数据或通用寄存器数据的操作引起的相关。对主存数据或通用寄存器数据的操作引起的相关。相关类型一：相关类型一：RAW（先写后读）（先写后读）有针对存储器有针对存储器RAWRAW和针对通用寄存器和针对通用寄存器RAWRAW两种。两种。IFIDEXMEMWBSUBIFIDEXMEMWBADD123456指令指令时钟时钟写写R1读读R1例：ADDR1，R2，R3；R2+R3R1SUBR4，R1，R5；R1-R5R4第54页/共120页 相关类型一解决方案：相关类型一解决方案：a.a.延迟执行法（后推法）延迟执行法（后推法）不同拍之间相关时，停顿后继指令的运行，直到前面不同拍之间相关时，停顿后继指令的运行，直到前面指令结果生成；（指令结果生成；（R R或或M M相关）相关）同一拍中相关时，采用推后读、提前写方法同一拍中相关时，采用推后读、提前写方法（后半拍后半拍读、前半拍写）；读、前半拍写）；（R R或或M M相关）相关）RISCRISC指令的装载延迟，采用联锁硬件检测，并使流水指令的装载延迟，采用联锁硬件检测，并使流水线停顿，直到相关消除。线停顿，直到相关消除。第55页/共120页 b.b.相关专用通路法相关专用通路法 执行结果除写寄存器外，可直接送到执行结果除写寄存器外，可直接送到ALUALU的操作数保的操作数保存栈中。（存栈中。（R R相关）相关）多路开关多路开关ALUR4R1寄存器堆RF旁路旁路旁路旁路缓冲寄存器缓冲寄存器2缓冲寄存器缓冲寄存器1第56页/共120页 c.c.异步流动法异步流动法 让流水线中相关指令的后续不相关指令先执行，自动消让流水线中相关指令的后续不相关指令先执行，自动消除相关。除相关。读读段段写写段段入入出出段号：段号：1 2 3 4 5 6 7 8相关专用通路相关专用通路 n j m l k i h （异步流动的）（异步流动的）k j 空空 空空 空空 i h （顺序流动的）（顺序流动的）指令地址：指令地址：k j i h （判出（判出j,h相关）相关）绝大多数系统均采用异步流动的方法。绝大多数系统均采用异步流动的方法。异步流动会产生新的数据相关类型，使其控制很复杂。异步流动会产生新的数据相关类型，使其控制很复杂。第57页/共120页 相关类型二：相关类型二：WAR(WAR(先读后写先读后写)、WAW(WAW(写写写写)这两种相关只有在异步流动流水线中才会产生。这两种相关只有在异步流动流水线中才会产生。RAWRAW（先写后读）相关在任何流水线中都会出现。（先写后读）相关在任何流水线中都会出现。WARWAR（读（读写）：写）：在先的指令先读，在后的指令才能写的关在先的指令先读，在后的指令才能写的关联，称联，称“先读后写先读后写”相关。相关。如：如：1 MOV AL1 MOV AL，2000H2000H 2 MOV 2000H 2 MOV 2000H，BLBLWAWWAW（写（写写）：写）：在先的指令先写入，在后的指令才能写的关在先的指令先写入，在后的指令才能写的关联，称联，称“写写写写”相关。相关。如：如：1 MOV 2000H1 MOV 2000H，ALAL 2 MOV 2000H 2 MOV 2000H，BLBL 相关类型二解决方案：相关类型二解决方案：使用分布式动态调度方式检测和处理相关。使用分布式动态调度方式检测和处理相关。第58页/共120页2.2.局部相关的分布式控制和管理局部相关的分布式控制和管理目的：目的：解决异步流动的解决异步流动的WAR和和WAW相关。相关。关键技术：关键技术：动态调度、寄存器重命名和动态存储器地址判别技术动态调度、寄存器重命名和动态存储器地址判别技术 IBM360/91 IBM360/91的浮点运算器部分包括了以下主要部件：的浮点运算器部分包括了以下主要部件：（1 1）运算部件运算部件（2 2）保存站保存站（3 3）浮点操作栈（浮点操作栈（FLOSFLOS）（4 4）浮点操作数缓冲器（浮点操作数缓冲器（FLBFLB）（5 5）存储数据缓冲器（存储数据缓冲器（SDBSDB）（6 6）浮点寄存器（浮点寄存器（FLRFLR）：）：寄存器号寄存器号F0F7F0F7，每个寄存器设置，每个寄存器设置一个一个“忙位忙位”，只要寄存器，只要寄存器FiFi正在使用，正在使用，“忙位忙位”就置为就置为“1 1”，使用完就清，使用完就清0 0。若。若某个操作命令使用某个操作命令使用FiFi，先检查，先检查“忙位忙位”是否为是否为“1 1”，若为，若为1 1则发生相关。则发生相关。（7 7）公共数据总线（公共数据总线（CDBCDB）第59页/共120页结构框图：结构框图：浮点浮点操作数操作数缓冲器缓冲器(FLB)控控浮点浮点操作栈操作栈(FLOS)忙忙制制位位站号站号源源1控制控制站号站号源源2站号站号源源1站号站号源源2控制控制控控制制号号站站存数存数缓冲器缓冲器(SDB)加法器乘/除法器译码器站站号号浮点浮点寄存器寄存器(FLR)M1M2A1A2A3101010111100FLB 总线总线FLR总线总线10001001CDB公共数公共数据总线据总线指令处理部件指令处理部件存储器总线存储器总线654321站号：站号：01100001F76543F21F0保存站保存站第60页/共120页a.利用公共数据总线作为相关专用通路；利用公共数据总线作为相关专用通路；b.利用利用FLR“忙忙”位，检测位，检测REG的的RAW相关；相关；c.利用修改站号（寄存器重命名），检测和消除利用修改站号（寄存器重命名），检测和消除REG的的WAR和和WAW相关；相关；d.利用存数缓冲器的动态存储器地址判别技术，检测和消除利用存数缓冲器的动态存储器地址判别技术，检测和消除MEM的的RAW、WAR和和WAW相关。相关。应用举例：S1：(FLB1)F0 S2：(F0)*(FLB2)F0 S3：(F0)+(FLB4)F0工作原理：工作原理：第61页/共120页二、全局性相关处理二、全局性相关处理 原因：原因：由转移指令由转移指令(占总指令的占总指令的1/4)1/4)引起的相关。引起的相关。解决方法：解决方法：程序执行时：程序执行时：停顿停顿加速生成结果加速生成结果猜测结果猜测结果程序生成时：程序生成时：优化延迟转移优化延迟转移1.1.加快和提前形成条件码加快和提前形成条件码 对转移指令的条件码，部分可提前生成；对转移指令的条件码，部分可提前生成；加快单条指令或循环内条件码形成。加快单条指令或循环内条件码形成。第62页/共120页2.2.猜测法猜测法 选取发生概率较高的分支为猜测方向，运行但不写回结果。选取发生概率较高的分支为猜测方向，运行但不写回结果。若猜对，继续执行；否则若猜对，继续执行；否则,作废猜测方向的执行，返回实际转移作废猜测方向的执行，返回实际转移处。处。（2 2）实现方法：）实现方法：a.a.根据转移指令根据转移指令PCPC值检索值检索BTBBTB；BTB BTB包含转移指令包含转移指令PCPC值、有效位、历史位、转移目标值、有效位、历史位、转移目标PCPC值项。值项。b.b.命中时，根据历史位取得转移的猜测方向，猜测为转移时，命中时，根据历史位取得转移的猜测方向，猜测为转移时，取得转移目标取得转移目标PCPC值，预取指令送入指令队列头，否则，顺序执值，预取指令送入指令队列头，否则，顺序执行；行；（1 1）硬件要求：）硬件要求：增设转移目标缓冲器增设转移目标缓冲器BTB,BTB,加快另一分支的流动加快另一分支的流动第63页/共120页指令预取器转移指令地址有效位历史位转移目标地址指令译码1（D1）(PC+2)顺序取顺序取取指令取指令转移取转移取指令队列指令队列查找查找执行（EX）控制逻辑加入新项加入新项猜测发生错误猜测发生错误命中与否命中与否实情执行情况实情执行情况更新旧项更新旧项 c.c.根据转移指令实际结果，增加或修改根据转移指令实际结果，增加或修改BTBBTB相关相关指令项，更新其有效位、转移目标指令项，更新其有效位、转移目标PCPC、历史位。、历史位。第64页/共120页3.3.延迟转移技术延迟转移技术 是一种静态调度方法，由编译程序实现。是一种静态调度方法，由编译程序实现。实现方法实现方法（转移前指令与转移指令关系）：（转移前指令与转移指令关系）：无相关：无相关：转移前指令入槽；转移前指令入槽；相相 关：关：空指令入槽。空指令入槽。结果：结果：50%50%以上指令可进入延迟槽，其余为空指令。以上指令可进入延迟槽，其余为空指令。4.4.设置特殊循环指令，加快短循环处理设置特殊循环指令，加快短循环处理第65页/共120页三、流水机器的中断处理三、流水机器的中断处理 1.解决问题如何处理好中断现场的保存与恢复。2.解决方法（1）不精确断点法不论第i条指令在流水线的哪一段发出中断申请，都不再允许那时还未进入流水线的后续指令再进入。已在流水线的指令仍继续流完，然后才转入中断处理程序。特点：硬件开销小，控制简单，程序排错不方便。第66页/共120页（2 2）精确断点法：不论第i条指令是在流水线中哪一段发的中断申请，给中断处理程序的现场全都是对应第i条的，在第i条之后进入流水线的所有指令的原有现场都能保存和恢复。中断处理方法：平时采用一定数量的后援寄存器，把流水线中所有指令的执行现场保存下来，中断产生时可实现精确断点现场保护与恢复。特点：效果理想，硬件代价高，控制复杂。现在的流水都采用了精确断点法。第67页/共120页练习题一、选择1.指令间的“一次重叠”是指（）A.执行K与取指K+1重叠B.分析K+1与执行K重叠C.取指K+1与分析K重叠D.分析K与执行K+1重叠2一次重叠中消除“指令相关”最好的方法是（）A.不准在程序执行过程中修改指令B.增设相关专用通路C.推后执行下一条指令D.推后下条指令的分析3.在流水线的相关处理中，会发生“写写”相关和“先读后写”相关的是（）A.猜测法B.顺序流动C.异步流动D.相关专用通路二、填空1.为同时解释相邻两条或多条指令，常用的控制方式是（）和（）。2.解决重叠和流水中的操作数相关，不外乎是（）法和（）法两种。3.流水机器对中断的处理有（）断点和（）断点，IBM360/91用的是前者，Amdahl470/V6用的是后者。第68页/共120页三、判断1.指令的重叠解释，既可加快程序的解释，又能加快指令的解释。（）2、要使线性流水线的实际吞吐率接近于理想的最大吞吐率，应将子过程数分得越多越好。（）3、流水机器处理中断应着眼于解决断点现场如何保存和恢复，并不在于如何缩短断流的时间，去追求流水的高吞吐率和高效率。（）第69页/共120页四四.流水线调度流水线调度 1、单功能非线性流水线调度、单功能非线性流水线调度非线性流水线：由于段间有前馈和反馈通路任务,执行过程中可能会多次通过同一流水段,发生几个任务同时争用同一流水段的现象,这就是功能段的使用冲突。S1S2S3S4S5入入出出 某流水线结构如下：某流水线结构如下：第70页/共120页解决方法：非线性流水线上输入任务时，在不发生功能段冲突，又能使流水线有较高的吞吐率和效率的情况下，应该如何选择输入任务的间隔时间？非线性流水线调度的任务就是找出一个最佳调度方案，按照这个调度方案向流水线输入任务，流水线的各个功能段都不会发生冲突。同时，非线性流水线的吞吐率和效率最高。流水线调度方案步骤如下：流水线调度方案步骤如下：形成预约表；形成预约表；由预约表形成禁止表；由预约表形成禁止表；由禁止表形成初始冲突向量；由禁止表形成初始冲突向量；由初始冲突向量形成状态转换图；由初始冲突向量形成状态转换图；由状态转换图中找出最佳调度方案。由状态转换图中找出最佳调度方案。第71页/共120页图5-21是一条由4个功能段组成非线性流水线的连接图，它有两条反馈线和一条前馈线，输出端在第一个功能段S1。图5-21非线性流水线连接图（1 1）形成预约表）形成预约表第72页/共120页预约表的横坐标表示流水线工作的时间周期，纵坐标表示流水线功能段，功能段在某个时钟周期处于工作状态用“”表示，空白的地方表示该功能段在对应的时间周期内不工作。图5-22与图5-21对应的一张预约表第73页/共120页一张非线性流水线的预约表可能与多个非线性流水线的连接图相对应；一个非线性流水线的连接图也可能与多个非线性流水线的预约表相对应。图5-23与图5-21对应的另一张预约表第74页/共120页图5-24是非流水线预约表5-22对应的另一种连接图。图5-24与图5-22对应的另一张连接图非线性流水线连接图5-21和对应的预约表图5-22可以唯一确定非线性流水线的工作过程。第75页/共120页图5-25启动距离为2的流水线冲突情况在图5-21和图5-22所确定的非线性流水线，当启动距离为2时，有关功能段的冲突情况如图5-25所示。第76页/共120页（2 2）由预约表形成禁止表）由预约表形成禁止表F F 所对应的禁止向量为所对应的禁止向量为F=（3,4,6），若不想发生冲突，两个任务，若不想发生冲突，两个任务送入流水线的间隔拍数不属于送入流水线的间隔拍数不属于F，F的拍数禁止使用。的拍数禁止使用。（3 3）由禁止表）由禁止表F F形成初始冲突向量形成初始冲突向量C C0 0把预约表的每一行中任意两个“”之间的距离都计算出来，去掉重复的，将这些数组成一个数列。第77页/共120页初始冲突向量用一个m位的二进制数表示，其中m表示禁止向量中的最大值。对于一张k列的预约表，有m k-1。通常禁止向量用C0=(CmCm-1C1)来表示，如果i在禁止向量中，则Ci为1，否则Ci为0。上例中预约表的初始冲突向量C0=（101100）（4 4）由初始冲突向量C C0 0形成状态转换图a.a.C C0 0每过一拍逻辑右移一位，若移出0 0，则允许后续指令进入流水线，再与C C0 0按位“或”，形成新的冲突向量C Ci i=修改后的冲突向量初始冲突向量；1拍后，C C0 0右移1位，左边补0形成修改的冲突向量结果结果 010110010110101100右移1位0修改的冲突向量与原始冲突向量“或”第78页/共120页 010110+101100=111110=C1，即为新的冲突向量。同理，我们可计算出C2=101111，C5=101101，用冲突向量可画出流水线状态转换图：（1）冲突向量中，位=0表示不发生冲突，其位置号是不发生冲突的间隔拍数。（2）从初始状态开始，检查冲突向量中为0的位，有几个0，就会有几个新的冲突向量。（3）逐次计算新的冲突向量，并用有向图连接。（4）有向弧上的数字表示产生新的冲突向量所用的间隔拍数101100101111111110101101初始状态初始状态2517第79页/共120页 b.b.各各C Ci i再每过一拍逻辑右移一位，若移出再每过一拍逻辑右移一位，若移出0 0，允许后，允许后续指令进入，再与续指令进入，再与C C0 0按位按位“或或”，形成新的冲突向量，形成新的冲突向量C Cijij=C=Ci i C C0 0 ；说明：说明：C Cijij为第为第i+j拍后流水线的冲突向量，若此时流拍后流水线的冲突向量，若此时流水线中已有三条指令，水线中已有三条指令，C Cijij用于判断第四条指令的进入。用于判断第四条指令的进入。对对C C5 5，再，再2 2拍后，拍后，C C2 2右移右移2位，左边补位，左边补0形成修改的冲形成修改的冲突向量突向量101101 右移2位0结果结果 001011001011修改的冲突向量与原始冲突向量“或”001011+001011+101100=101111=C C5252，即为新的冲突向量。第80页/共120页 c.c.重复上一步骤，直到不再生成新的冲突向量为止。重复上一步骤，直到不再生成新的冲突向量为止。图5-26与图5-22预约表对应的状态转换图第81页/共120页（5 5）找出最佳调度方案）找出最佳调度方案 从各个从各个闭合回路闭合回路中找出平均间隔最小的一个。中找出平均间隔最小的一个。a.从初始状态出发，沿箭头方向，每走一个闭环，从初始状态出发，沿箭头方向，每走一个闭环，即为一个方案。即为一个方案。b.若中间遇到小闭环，每个小闭环也可作为一个方若中间遇到小闭环，每个小闭环也可作为一个方案。案。c.遍历初始状态中的遍历初始状态中的Ci每一个回路。每一个回路。第82页/共120页本例中调度方案如下：本例中调度方案如下：调度策略调度策略平均间隔拍数平均间隔拍数调度策略调度策略平均间隔拍数平均间隔拍数（1，7）4（5，7）6（1，1，7）3（5）5（2，7）4.5（7）7（2，5）3.5（5，2）3.5（2，5，7）4.7（5，2，7）7.7对对于于非非等等间间隔隔调调度度方方案案，找找出出每每种种调调度度法法的的平平均均间间隔隔拍拍数数，然然后后找找出出最最小小者者，就就是是最最佳佳调调度度方方案案。本本例例子子平平均均间间隔隔拍拍数数最最小小的调度方案有的调度方案有(1,1,7).(1,1,7).平均间隔拍数=循环周期/任务数第83页/共120页非线性流水线的各个功能段在任何周期中都不会发生冲突的流水线预约表如图5-27所示。图5-27最佳调度方案（1，1，7）的流水线预约表第84页/共120页最大吞吐率Tpmax=1/(3 t)照最佳调度方案（1，1，7）连续输入9个任务，求流水线的实际执行时间、吞吐率和效率。完成任务的总时间=建立时间+（n-1）个任务流出时间 =（7+1+1+7+1+1+7+1+1）t=27t其中，（n-1）个任务的流出时间示意如下：任务1 2 3 4 5 6 7 8 9 9个任务可以在27个周期内完成。吞吐率=9/(27 t)=1/(3 t)=33%/t 效率=8*9/(4*27)=2