第4章-流水技术与向量处理.pptx

2024/4/24周三1第第4 4章章 流水技术与向量处理流水技术与向量处理 4.1 标量流水工作原理标量流水工作原理4.2 标量流水中的障碍及控制标量流水中的障碍及控制 4.3 流水线的调度技术流水线的调度技术4.4 先进的流水技术先进的流水技术4.5 Pentium微微处处理理器器中中的的流流水水技技术术4.6 向量流水技术向量流水技术2024/4/24周三2本章学习要求掌握标量流水的性能分析及障碍的处理方法掌握非线性流水调度技术掌握向量流水机的结构特征、向量指令并行性分析了解标量流水、超标量流水、超流水及超长指令字计算机的基本工作原理2024/4/24周三3提高指令执行速度的主要途径：提高指令执行速度的主要途径：(1)(1)提高处理机的工作主频提高处理机的工作主频(2)(2)采用更好的算法和设计更好的功能采用更好的算法和设计更好的功能部件部件(3)(3)采用指令级并行技术采用指令级并行技术三种指令级并行处理机：三种指令级并行处理机：(1)(1)流水线处理机和超流水线流水线处理机和超流水线(Super-(Super-pipelining)pipelining)处理机处理机(2)(2)超标量超标量(Superscalar)(Superscalar)处理机处理机(3)(3)超长指令字超长指令字(VLIW:Very Long(VLIW:Very Long Instruction Word)Instruction Word)处理机处理机2024/4/24周三44.1 标量流水工作原理标量流水工作原理什么是流水线？什么是流水线？考虑设计一个洗衣机的工作流程，假定它有三道考虑设计一个洗衣机的工作流程，假定它有三道工序：洗涤、清洗、甩干。每个环节为工序：洗涤、清洗、甩干。每个环节为5 5分钟分钟。需要完成的任务为需要完成的任务为3 3批，则考虑下述工作方式的工批，则考虑下述工作方式的工作效率作效率：第一种：串行工作方式，即按照如下方式工作：第一种：串行工作方式，即按照如下方式工作：第第1批批洗涤洗涤第第1批批清洗清洗第第1批批甩干甩干第第2批批洗涤洗涤第第2批批清洗清洗第第2批批甩干甩干第第3批批洗涤洗涤第第3批批清洗清洗第第3批批甩干甩干3批衣服的整个工作时间为批衣服的整个工作时间为3*3*5=45分钟分钟2024/4/24周三5第二种：重叠工作方式，设计三个部件，可以同时第二种：重叠工作方式，设计三个部件，可以同时工作，每个部件只做一样工作，操作方式如下图：工作，每个部件只做一样工作，操作方式如下图：第第1批洗涤批洗涤第第1批清洗批清洗第第1批甩干批甩干第第2批洗涤批洗涤 第第2批清洗批清洗第第2批甩干批甩干第第3批洗涤批洗涤第第3批清洗批清洗第第3批甩干批甩干Tttttt3 3批衣服的工作时间为批衣服的工作时间为5*5=255*5=25分钟，节省分钟，节省2020分钟。分钟。2024/4/24周三6引出下述关于洗衣机工作的有关性能特点：引出下述关于洗衣机工作的有关性能特点：吞吐率：单位时间内完成的任务数吞吐率：单位时间内完成的任务数TP=n/TTP=n/T 加速比：串行方式与流水线方式的时间比：上述为加速比：串行方式与流水线方式的时间比：上述为 45/25=1.845/25=1.8 效率：即洗衣机的利用率，上述洗衣机的效率是效率：即洗衣机的利用率，上述洗衣机的效率是9/15=3/5=60%9/15=3/5=60%将一条指令的执行分为几个阶段，让几条指令按重将一条指令的执行分为几个阶段，让几条指令按重叠或流水方式工作，以提高程序的执行速度。这就叠或流水方式工作，以提高程序的执行速度。这就引出了计算机中的流水线技术。引出了计算机中的流水线技术。2024/4/24周三7指令的重叠解释与先行控制计算机系统中广泛存在着重叠工作方式指令的解释方式一般只有三种：顺序、重叠和流水重叠和流水给指令的执行带来了高的吞吐率和加速比，同时也给系统增加了障碍2024/4/24周三8指令的解释过程指令的解释过程ALULOAD/STOREIF取指取指取指取指ID译码、读寄存器堆译码、读寄存器堆译码、读寄存器堆译码、读寄存器堆EX执行执行计算访存有效地址计算访存有效地址MEM-访存（读或写）访存（读或写）WB结果写回寄存器堆结果写回寄存器堆将读出的数据写入寄存器堆将读出的数据写入寄存器堆2024/4/24周三9一、指令的重叠解释方式一、指令的重叠解释方式1 1、顺序执行方式、顺序执行方式 一条指令的执行过程：一条指令的执行过程：取指令取指令-分析分析-执行执行执行执行n n条指令所用的时间为：条指令所用的时间为：如每段时间都为如每段时间都为t t，则执行，则执行n n条指令所用的时间为：条指令所用的时间为：T=3ntT=3nt主要优点：主要优点：控制简单，节省设备。控制简单，节省设备。主要缺点：主要缺点：执行指令的速度慢，功能部件的利用率很低。执行指令的速度慢，功能部件的利用率很低。取指令k 分析k 执行k 取指令k+1 分析k+1执行k+12024/4/24周三10 2 2、重叠执行方式、重叠执行方式(最简单的流水线方式最简单的流水线方式)如果每个过程的时间相等，则执行如果每个过程的时间相等，则执行n n条指令的条指令的时间为：时间为：T=(1+2n)tT=(1+2n)t 主要优点：主要优点：指令的执行时间缩短指令的执行时间缩短 功能部件的利用率明显提高功能部件的利用率明显提高 主要缺点：主要缺点：需要增加一个需要增加一个IBRIBR取指 分析 执行取指 分析 执行取指 分析 执行2024/4/24周三113、更高重叠度的重叠解释方式、更高重叠度的重叠解释方式把取第把取第k+1条指令提前到分析第条指令提前到分析第k条指令同时执行条指令同时执行如果三个过程的时间相等，执行如果三个过程的时间相等，执行n n条指令的时间条指令的时间为：为：T=(2+n)tT=(2+n)t理想情况下同时有三条指令在执行理想情况下同时有三条指令在执行处理机的结构要作比较大的改变，必须采用先行处理机的结构要作比较大的改变，必须采用先行控制方式控制方式取指k+2 分析k+2 执行k+2取指k+1 分析k+1 执行k+1取指k分析k执行k2024/4/24周三121访存冲突访存冲突 分析与取指均要访问主存分析与取指均要访问主存 解决：解决：1）采用两个独立编制的存贮器）采用两个独立编制的存贮器 数据数据/指令指令 但增加了复杂性但增加了复杂性 2）采用多体交叉存贮器）采用多体交叉存贮器 3）指令缓冲寄存器指令缓冲寄存器2功能部件的冲突功能部件的冲突 解决：解决：设置独立的分析部件和执行部件设置独立的分析部件和执行部件 重叠方式对计算机组成的要求重叠方式对计算机组成的要求2024/4/24周三133同步同步 分析与执行所需的时间不同，要求的是一次分析与执行所需的时间不同，要求的是一次重叠重叠 一一次次重重叠叠：任任何何时时间间都都是是“分分析析K+1”与与“执执行行K”的重叠的重叠 =相邻两条指令的重叠相邻两条指令的重叠分析分析K执行执行K分析分析K+1 执行执行K+1T=(n+1)t2024/4/24周三144转移转移 无无条条件件转转移移/条条件件转转移移当当转转移移成成功功时时，重重叠叠预预取无效，变为顺序执行取无效，变为顺序执行 应尽可能不使用或少使用条件转移指令应尽可能不使用或少使用条件转移指令5相关相关 邻邻近近指指令令之之间间出出现现某某种种关关联联，为为避避免免出出错错而而不不能能同时执行的现象。同时执行的现象。局部性相关、全局性相关局部性相关、全局性相关2024/4/24周三152024/4/24周三16先行控制技术先行控制技术基本思想：使分析和执行部件分别连续不断地运行，使部基本思想：使分析和执行部件分别连续不断地运行，使部件空闲状态减至最低。件空闲状态减至最低。(a)重叠方式分析分析k+1分析分析k执行执行k执行执行k+1分析分析k+2执行执行k+2分析部件空闲执行部件空闲分析分析k+1分析分析k执行执行k分析分析k+2(b)先行控制执行执行k+1执行执行k+22024/4/24周三17关键：缓冲技术预处理技术缓冲技术：在工作速度不固定的两个功能部件之间设置缓冲栈，用以平滑它们的工作预处理技术：把进入运算器的指令都预处理成R-R型指令，与缓冲技术相结合，为进入运算器的指令准备好所需的全部操作数先行控制方式使运算器可专注于运算，从而可大幅度提高程序的执行速度 硬件要求：增设指令缓冲栈，消除取指过程；增设数据缓冲栈，保证不同指令的读、写操作并行；增设先行操作栈，保证执行部件能连续执行。2024/4/24周三18工作原理主主 存存存存 控控指令分析器指令分析器先行先行指令栈指令栈先行读先行读数栈数栈后行写后行写数栈数栈执行执行部件部件先行操作栈先行操作栈数据缓冲栈数据缓冲栈 栈的深度要求：栈的深度要求：D D指缓指缓D D操作操作 D D读栈读栈 D D写栈写栈2024/4/24周三19二、标量流水工作原理二、标量流水工作原理基本思想：基本思想：流水是重叠的进一步延伸，流水是重叠的进一步延伸，使指令解释过程进一步细化，提高各部使指令解释过程进一步细化，提高各部件的利用率，以提高指令执行速度。件的利用率，以提高指令执行速度。流水线的表示方法：流水线的表示方法：连接图、时空图、连接图、时空图、预约表预约表2024/4/24周三201 1、简单流水线的连接图表示、简单流水线的连接图表示 流水线的每一个阶段称为流水段、流水线流水线的每一个阶段称为流水段、流水线阶段、阶段、流水功能段流水功能段、功能段、流水级、流水、功能段、流水级、流水节拍等。一个流水阶段与另一个流水阶段相节拍等。一个流水阶段与另一个流水阶段相连形成流水线。连形成流水线。有些复杂指令，在执行阶段也采用流水线有些复杂指令，在执行阶段也采用流水线方式工作，称为操作流水线。方式工作，称为操作流水线。取指取指访存访存执行执行译码译码写回写回IFIDEXMEMWBS1S2S3S4S5输入输入输出输出2024/4/24周三21 一种指令流水线一种指令流水线一般一般4 4至至1212个流水段，等于及大于个流水段，等于及大于8 8个流水段的称为超流水个流水段的称为超流水线处理机线处理机2 2、流水线的时空图、流水线的时空图采用采用“时空图时空图”表示流水线的工作过程。表示流水线的工作过程。一条简单流水线一条简单流水线的时空图的时空图：取指形成操作数地址译码取操作数执行保存结果2024/4/24周三22一个浮点加法器流水线的时空图一个浮点加法器流水线的时空图(由求阶差、对阶、由求阶差、对阶、尾数加和规格化尾数加和规格化4 4个流水段组成个流水段组成)：ED1时间空间0t1t2t3t4t5ED2 ED3 ED4 ED5EA1 EA2 EA3 EA4 EA5MA1 MA2 MA3 MA4 MA5NL1 NL2 NL3 NL4 NL5t6t7t8NL：规格化MA：尾数加EA：对阶ED：求阶差EDEAMANLmt2024/4/24周三233、流水线的预约表时间流水段1234567S1XXXS2XXS3XXS4X2024/4/24周三24三、流水线工作方式三、流水线工作方式取指取指访存访存执行执行译码译码写回写回IFIDEXMEMWBS1S2S3S4S5输入输入输出输出指令的流水处理指令的流水处理 流流水水线线的的基基本本结结构构中中主主要要包包括括三三大大部部分分：锁锁存存器器、时时钟钟、功能段。功能段。流流水水线线中中每每个个段段都都是是由由一一些些执执行行算算术术和和逻逻辑辑功功能能的的组组合合逻逻辑辑线线路路组组成成的的，它它们们可可以以互互相相独独立立地地对对流流过过的的信信息息进进行行某某种种操操作作，相相邻邻两两站站由由高高速速锁锁存存器器（latch）隔隔开开，信信息息在在各各段段间间的的流流动靠同时送到各站的时钟信号来控制。动靠同时送到各站的时钟信号来控制。1 1、流水线的结构、流水线的结构2024/4/24周三25S1S2Sm输入输入 输出输出流水线的基本结构流水线的基本结构.时钟时钟2024/4/24周三26121321nn-1.43215432.543.54.5nn-1.n-1.nn-1 n1234tt0 0 t t0 0 t t0 0 t t0 0T T0=0=m m t t0 0n n t t0 0T T(m-1)t(m-1)t0 0(n-1)t(n-1)t0 0填入填入 正常正常 排空排空 流水时空图流水时空图空间空间时间时间建立时间、正常流动时间、排空时间。建立时间、正常流动时间、排空时间。2 2、流水线工作的三个时间、流水线工作的三个时间2024/4/24周三273 3、流水线的分级、分类、流水线的分级、分类分级分级：（处理的级别分类）：（处理的级别分类）v 部件级部件级(操作流水线操作流水线)：将复杂的算逻运算组成流水工作方式；：将复杂的算逻运算组成流水工作方式；v指令级：指令级把一条指令解释过程分成多个子过程把一条指令解释过程分成多个子过程；v处理机级：每个处理机完成某一专门任务，各个处理机所得到的处理机级：每个处理机完成某一专门任务，各个处理机所得到的结果需存放在与下一个处理机所共享的存储器中结果需存放在与下一个处理机所共享的存储器中 2024/4/24周三28其他分类：其他分类：功能：单功能流水线（如功能：单功能流水线（如CRAY-1CRAY-1）、多功能流水线（如）、多功能流水线（如TI-TI-ASCASC）工作方式：静态流水线、动态流水线工作方式：静态流水线、动态流水线 连接方式：线性、非线性连接方式：线性、非线性 处理数据：标量流水、向量流水处理数据：标量流水、向量流水1234出出入入非线性流水线非线性流水线2024/4/24周三291)ASC算术运算流水线（多功能）算术运算流水线（多功能）输入输入减阶减阶对阶移位对阶移位相加相加规格化规格化相乘相乘累加累加输出输出123456784 4、流水线举例、流水线举例输入输入减阶减阶对阶移位对阶移位相加相加规格化规格化输出输出123458加加输入输入相乘相乘累加累加输出输出1678乘乘2024/4/24周三30.1234.n-1 n.1234.n-1 n.1234.n-1n.1234.n-1 n12345867.1234.n-1 n.1234.n-1 n时间时间空间空间(段号段号)加法加法一一 二二 三三 四四二二 三三一一二二一一一一乘法乘法.静态多功能流水线时静态多功能流水线时-空图空图静态流水线：静态流水线：只有当进入的是一串相同运算的指令时，流水的只有当进入的是一串相同运算的指令时，流水的效能才得以发挥，才能使各个功能段并行地对多条指令的数据效能才得以发挥，才能使各个功能段并行地对多条指令的数据进行流水处理。进行流水处理。2024/4/24周三31区区别别：如如果果从从软软硬硬功功能能分分配配的的观观点点上上来来看看，静静态态流流水水线线其其实实是是把把功功能能负负担担较较多多地地加加到到软软件件上上，以以简简化化硬硬件件；动动态态流流水水线线则则是是把功能负担较多地加在硬件上，以提高流水的效能。把功能负担较多地加在硬件上，以提高流水的效能。.12345.n-1 n.12345.n-1 n.12345.n-1 n.12345.n-1 n12345867.12345.n-1 n.12345.n-1 n时间时间加法加法乘法乘法一一二二三三 四四 五五 六六一一二二三三 四四 五五 六六七七一一二二三三 四四 五五一一二二三三 四四动态多功能流水线时动态多功能流水线时-空图空图m2024/4/24周三32四、标量流水线性能分析四、标量流水线性能分析衡量流水线处理机的性能主要是衡量流水线处理机的性能主要是吞吐率、加速比和效率吞吐率、加速比和效率。1吞吞吐吐率率：单单位位时时间间内内能能处处理理的的指指令令条条数数或或能能输输出出的的数数据据量量。吞吞吐吐率率越越高高，计计算算机机系系统统的的处处理理能能力力就就越越强强。就就流流水水线线而而言言，吞吐率就是单位时间内能流出的任务数或能流出的结果数。吞吐率就是单位时间内能流出的任务数或能流出的结果数。最大吞吐率：流水线达到稳定状态后可获得的吞吐率。最大吞吐率：流水线达到稳定状态后可获得的吞吐率。（1）Tpmax=1/t（2）TPmax=1/max t1，t2，t3，t4 “瓶颈瓶颈”子过程：子过程：1234 t t 3 t t 2024/4/24周三33子过程子过程3为瓶颈段的时空图为瓶颈段的时空图最大吞吐率最大吞吐率TPmax=1/3 t mTS1S2S3S4t1t2t3t4t5t6t7t8t9t10t12t13t14t151234t11123412341234输出输出2024/4/24周三34131232334 2 1 4 3a 3b 3c 333瓶颈段细分瓶颈段细分重复设置瓶颈流水段重复设置瓶颈流水段解决瓶颈有两种方法解决瓶颈有两种方法A：B：2024/4/24周三35T重复设置瓶颈流水段后的工作时空图重复设置瓶颈流水段后的工作时空图mS1S2S3aS3cS3bS41 2 3546 7 8 9 10 11121 2 3546 7 8 9 10 11121471025811369121 2 3546 7 8 9 10 11 12t1t12t172024/4/24周三36实际吞吐率实际吞吐率（1）完成）完成n条指令的解释共需时间条指令的解释共需时间 可可以以看看出出不不仅仅实实际际的的吞吞吐吐率率总总是是小小于于最最大大的的吞吞吐吐率率，而而且且只只有有当当nm时时，实实际际的的吞吞吐吐率率才才能能接接近近于于理理想想的最大吞吐率。的最大吞吐率。(2)各功能段时间不相等各功能段时间不相等2024/4/24周三372.效率：设备的利用率，直接反映了处理机结构有效程度。流水线有建立时间、排空时间，不总是满负载工作。各段时间相等：各段时间相等：各段时间不等：各段时间不等：2024/4/24周三38各段时间相等各段时间相等:各段时间不等各段时间不等:3.加速比加速比：M段流水线的速度与等效的非流水线的速段流水线的速度与等效的非流水线的速度之比。度之比。2024/4/24周三39K=6K=10任务个数加速比10246811 248 16 32 64 128因为因为因此：因此：E=TP E=TP t t，S=kES=kE流水线的吞吐率、加速比与效率的关系流水线的吞吐率、加速比与效率的关系2024/4/24周三40例例1.有一四段线性流水线,每功能段延时时间分别是：t1=t3=t4=t,t2=3t。现在这个流水线上分别执行4个任务和40个任务。求实际吞吐率、效率和加速比。解法一：解法一：时空图分析法时空图分析法时间时间12343111223234123123123444443t3t3t3t空间空间152024/4/24周三41Tp=4/(15t)E=24t/(4*15t)=40%Sp=4*6t/15t=1.6完成4个任务时：完成40个任务时，如何画时空图呢？方法二，公式分析法。当流水线中各功能段的执行时间不相等时，有2024/4/24周三422024/4/24周三43例2、以浮点加法运算为例（四段）各段时间相等，求Z=A+B+C+D+E+F+G+H的TP、E、Sp。时间时间空间空间Z=A+B+C+D+E+F+G+H1234567TP=7/15ttE E=7*4/(15*4)=7/15Sp=4*7/15=28/15=1.871111222233334444555566667777152024/4/24周三44例例3.ASC计算机功能算术运算流水线各段时间相等，6次浮点加、5次定点乘的吞吐率、效率和加速比。1,2,3,4,5,8组成加法流水1,6,7,8组成乘法流水12345678对阶减阶输出相加规格化相乘累加输入ASC计算机的流水线2024/4/24周三45分析：分析：T T加加=6+(6-1)*1=11 T=6+(6-1)*1=11 T乘乘=4+(5-1)*1=8=4+(5-1)*1=8 TP=11/(11+8)t=11/19 tTP=11/(11+8)t=11/19 tE=(6*6+5*4)t/(19*8t)=11.54%E=(6*6+5*4)t/(19*8t)=11.54%Sp=56 t/19 t=2.94Sp=56 t/19 t=2.941 234561 234561 234561 23456123458671 234561 23456时间时间浮加浮加定点乘定点乘一一二二三三 四四 五五一一二二三三 四四 五五一一二二三三 四四五五一一二二三三 四四五五2024/4/24周三464.2 4.2 标量流水中的障碍及控制标量流水中的障碍及控制保持流水线性能条件：保持流水线性能条件：不能停顿或断流。不能停顿或断流。影响流水线性能因素：影响流水线性能因素：相关和功能切换。相关和功能切换。相关类型：相关类型：全局相关：转移指令引起的相关全局相关：转移指令引起的相关结果：结果：流水线断流，流水线中后续指令全部作流水线断流，流水线中后续指令全部作废。废。局部相关：资源或结构相关；指令相关；数据相局部相关：资源或结构相关；指令相关；数据相关。关。结果：结果：流水线停顿，流水线中后续指令有效。流水线停顿，流水线中后续指令有效。2024/4/24周三47一、资源相关资源相关：功能部件、主存资源当有多条指令进入流水线后在同一机器周期内争用同一功能部件所引起的相关（冲突）当有多条指令进入流水线后在同一机器周期内同时访问主存资源2024/4/24周三48例例1：两条指令同时要用一个加法器两条指令同时要用一个加法器ALULOAD/STOREIF取指取指取指取指ID译码、读寄存器堆译码、读寄存器堆译码、读寄存器堆译码、读寄存器堆EX执行执行计算访存有效地址计算访存有效地址MEM-访存（读或写）访存（读或写）WB结果写回寄存器堆结果写回寄存器堆将读出的数据写入寄将读出的数据写入寄存器堆存器堆指指 令令流水段流水段不同类型指令中各流水段进行的操作不同类型指令中各流水段进行的操作2024/4/24周三49两条指令同时访存造成资源相关两条指令同时访存造成资源相关MEMEXIDIF指令指令i+4WBMEMEXIDIF指令指令i+3WBMEMEXIDIF指令指令i+2WBMEMEXIDIF指令指令i+1WBMEMEXIDIFLoad指令指令87654321 时钟时钟指令指令冲突冲突取指取指 译码译码 执行执行 访存访存 写回写回例例2：2024/4/24周三50EXIDIF指令指令i+4MEM EXIDIF停顿停顿指令指令i+3WBMEMEXIDIF指令指令i+2WBMEMEXIDIF指令指令i+1WBMEMEXIDIFLoad指令指令87654321 时时钟钟指令指令9WBMEM使使i+3指令停顿一拍进入流水线，以解决访存相关；指令停顿一拍进入流水线，以解决访存相关；或重复设置一个存储器；采用或重复设置一个存储器；采用先行控制技术先行控制技术解决方法：解决方法：2024/4/24周三51二、指令相关后续指令的内容取决于当前指令执行的结果，即指令允许修改引起的相关解决相关：不准修改指令、变指令相关为数据相关EXR1D2B2X2IBM370中的“执行”指令2024/4/24周三52三、数据相关由于流水线中的各条指令间的重叠解释，使得原来对操作数的访问顺序发生了变化，从而导致了数据之间的相关。这种相关有三类：先写后读（改用相关）、先读后写（用改相关）、写写相关（改改相关）。设有i和j两条指令，i指令在前，j指令在后，则三种不同类型的数据相关的含义为：2024/4/24周三53 RAW读写读写(先写后读)-指令j试图在指令i写入寄存器前就读出该寄存器内容，这样，指令j就会错误地读出该寄存器旧的内容。i:R1+R2-R3 j:R3*R4-R5 WAR写读写读(先读后写)-指令j试图在指令i读出寄存器之前就写入该寄存器，这样，指令i就错误地读得该寄存器新的内容。i:R3*R4-R5 j:R1+R2-R3 WAW写写写写(先写后写)-指令j试图在指令i写寄存器之前就写入该寄存器，这样，两次写的先后次序被颠倒，就会错误地使由指令i写入的值成为该寄存器内容。i:R1*R2-R3 j:R4+R5-R32024/4/24周三54解决数据相关的办法用软件和硬件技术：解决数据相关的办法用软件和硬件技术：v时间推后法时间推后法v旁路技术或相关专用通路技术旁路技术或相关专用通路技术例：例：n:load A IF ID EX WR n+1:load B IF ID EX WR n+2:add A,B IF ID 气泡气泡 EX WR n+3:store C IF ID 气泡气泡 EX WR n+4:jump K IF ID EX WR n+5:load E 停顿停顿 停顿停顿 停顿。停顿。n+6 停停顿。顿。K:IF ID EX 例中有资源相关、有控制转移相关，这将影响流水线的性能。例中有资源相关、有控制转移相关，这将影响流水线的性能。2024/4/24周三55IF ID EX MEM WB IF ID EX WB IF ID EX WB IF ID EX WB IF ID EX WB ADD R1,R2,R3SUB R4,R1,R5AND R6,R1,R7OR R8,R1,R9XOR R10,R1,R11定向传递定向传递R1值值数据相关和定向传递指令数据相关和定向传递指令写写R1完完成成MEM MEM MEM MEM 2024/4/24周三56ALU运算结果运算结果写写RF RF读读RFALU操作数寄存器操作数寄存器专用通路（旁路）专用通路（旁路）旁路旁路RFALUBufferMultMult2024/4/24周三57四、全局性相关由转移指令（条件/无条件）引起的相关转移指令在程序中所占比例约为20-25%，不可忽视解决这种相关的方法：猜测法、加快和提前形成条件码、加快短循环程序的处理、采用延迟转移技术2024/4/24周三581 1、猜测法：、猜测法：选取发生概率较高的分支为猜测选取发生概率较高的分支为猜测方向，若猜对，继续执行；否则方向，若猜对，继续执行；否则,作废猜测作废猜测方向的执行，返回实际转移处。方向的执行，返回实际转移处。（1 1）如何提高猜测命中率）如何提高猜测命中率 静态猜测法：静态猜测法：猜测不成功方向。由程序猜测不成功方向。由程序员和编译程序把发生概率高的分支安排在猜员和编译程序把发生概率高的分支安排在猜测方向。测方向。动态猜测法：动态猜测法：根据转移历史猜测。根据转移历史猜测。I-1I-2I+4I+1I2I+3IK+3K+2K+1kbranch成功不成功2024/4/24周三59转移目标缓冲器(BTB)利用BTB(BranchTargetBuffer)硬件，动态地预测转移方向转移指令地址转移指令地址转移目标地址转移目标地址状态状态欲取指令的欲取指令的PC查找查找预测预测PC值值=按正常顺按正常顺序执行序执行NY2024/4/24周三60转移预测原理：转移预测原理：用用2位二进制数记录实际转位二进制数记录实际转移状态移状态(历史位历史位)，高位为，高位为1时预测转移发生，时预测转移发生，高位为高位为0时预测转移不发生。时预测转移不发生。注意：注意：初始状态、状态修改、猜测方向表示初始状态、状态修改、猜测方向表示预测发生11预测发生10预测不发生01预测不发生00转移1不转移0不转移0不转移0转移1转移1转移1不转移02024/4/24周三61（2 2）猜测的后续处理）猜测的后续处理 分支现场的保护及恢复：分支现场的保护及恢复：猜测执行只完成译码、取操作数或执行但不写结果；采用后援寄存器保存可能被破坏的状态。预防猜不中时的加速处理：预防猜不中时的加速处理：预取猜测方向的另一方向的前几条指令，放到缓冲器中，加速猜不中时回头速度。I-1I-2I+4I+1I+2I+3IK+3K+2K+1kbranch成功不成功2024/4/24周三622 2、加快和提前形成条件码、加快和提前形成条件码单条指令的条件码并不一定要等执行完成单条指令的条件码并不一定要等执行完成得到运算结果后才能形成得到运算结果后才能形成循环程序判断的提前形成循环程序判断的提前形成 3 3、优化延迟转移技术、优化延迟转移技术 a.a.将转移指令前的那条指令调度到延迟槽中；将转移指令前的那条指令调度到延迟槽中；b.b.将转移目标处的那条指令调度到延迟槽中；将转移目标处的那条指令调度到延迟槽中；c.c.将转移不发生时该执行的那条指令调度到将转移不发生时该执行的那条指令调度到延迟槽中。延迟槽中。4 4、加快短循环处理、加快短循环处理2024/4/24周三63五、流水线中的中断处理流水机器处理中断的关键不在于如何缩短断流时间，而是如何处理好断点现场及中断后的恢复问题不精确断点法不精确断点法：不论第i条指令在流水线的哪一段发出中断申请，都不再允许那时还未进入流水线的后续指令再进入。断点就是最后进入流水线的那条指令2024/4/24周三64S1S8S7S6S5S4S3S2输入输入输出输出i+5ii-1i+1i+2i+3i+4i-2PC：不精确断点申请中断申请中断精确断点精确断点特点：特点：硬件开销小，控制简单，适用于常规的I/O操作。2024/4/24周三65 精确断点法：精确断点法：不论第i条指令是在流水线中哪一段发出的中断申请，给中断处理程序的现场全都是对应第i条的。适用于程序性错误和机器故障等产生的中断精确断点法中对原有现场的恢复，要增加后援寄存器，以保留各功能段状态i:FADDR1,R2;(R1)+(R2)R1i+1:FMULR3,R1;(R3)*(R1)R3S6：加法：加法结果溢出结果溢出精确断点法有利于程序调试2024/4/24周三66例4在一条单流水线处理机上执行下面的程序。每条指令都要经过“取指”,“译码”,“执行”和“写结果”4个流水段。每个流水段的延迟时间都是5ns。在“执行”流水段,LS部件完成LOAD或STORE操作,其它操作都在ALU部件中完成,两个操作部件的输出端有直接数据通路与任一操作部件的输入端相连,ALU部件产生的条件码也能够直接送入控制器。2024/4/24周三671SUBR0,R0;R002:LOADR1,#8;向量长度83:LOOP:LOADR2,A;R2A向量的一个元素4:MULR2,R1;R2(R2)*(R1)5:ADDR0,R2;R0(R0)+(R2)6:DJNER1,LOOP;R1(R1)-1若(R1)0则转7:STORER0,S;保存结果(1)采用静态分支预测技术,每次都预测转移不成功。画出指令流水线的时空图。计算流水线的吞吐率和加速比。并分别计算出译码部件和ALU部件的使用效率。(2)采用静态分支预测技术,每次都预测转移成功。计算指令流水线的吞吐率和加速比。并分别计算出译码部件和ALU部件的使用效率。2024/4/24周三685211211 23223334 54445556666取指写回ALULS译码33334444 5555666633334444 5555666633334444 555566667777.重复8次m(1)解:每次预测转移不成功,流水线时空图如下:2024/4/24周三6911211 23223334 54445556666取指写回ALULS译码33334444 5555666633334444 555566667777.重复8次m(2)解:每次预测转移成功,流水线时空图如下:2024/4/24周三704.3流水线的调度技术静态调度静态调度：借助软件对指令执行顺序进行调度，以减少由于流水线中存在相关冲突而引起流水线的停顿时间。动态调度动态调度：通过硬件重新安排指令的执行顺序以减少流水的停顿。有集中式和分布式两种。2024/4/24周三71一、静态调度技术静态调度静态调度：借助软件对指令执行顺序进行调度，以减少由于流水线中存在相关冲突而引起流水线的停顿时间。非线性流水线中存在着前（反）馈回路，必然会引起功能段的冲突而发生流水线停顿。调度方法会减少停顿时间。调度方案是基于二维预约表和状态图来进行分析2024/4/24周三72非线性流水线的连接图非线性流水线的连接图时间流水段1234567S1XXXS2XXS3XXS4X非线性流水线的预约表非线性流水线的预约表S1S2S3S4输出输入反馈线2024/4/24周三73某流水线结构如下：某流水线结构如下：非线性流水线调度举例非线性流水线调度举例 S1S2S3S4S5入入出出 流水线调度方案如下：流水线调度方案如下：2024/4/24周三74（1）形成预约表）形成预约表指令总拍数为指令总拍数为n，流水线有，流水线有k个段，则形成个段，则形成nk的预约表，段的使用情况用的预约表，段的使用情况用“”表示。表示。预约表如下：预约表如下：543 2198765438271tS2024/4/24周三75（2）由预约表形成禁止表）由预约表形成禁止表FF=各段中冲突间隔拍数各段中冲突间隔拍数-功能段1的禁止间隔拍数为8；-功能段2的禁止间隔拍数为5和6；-功能段3的无禁止间隔拍数；-功能段4的禁止间隔拍数为1；-功能段5的禁止间隔拍数为1。F=1 F=1，5 5，6 6，88（3 3）由禁止表）由禁止表F F形成初始冲突向量形成初始冲突向量C C0 0C C0 0=（1011000110110001），），c ci i=1=1冲突，冲突，0 0不冲突。不冲突。2024/4/24周三76（4 4）由初始冲突向量）由初始冲突向量C C0 0形成状态转换图形成状态转换图a.a.取取C C0 0分别间隔分别间隔2 2、3 3、4 4、7 7拍，且将拍，且将C C0 0分别逻分别逻辑右移辑右移2 2、3 3、4 4、7 7位，高位补位，高位补0 0后再与后再与C C0 0按位按位“或或”，形成新的冲突向量，形成新的冲突向量C C1 1、C C2 2 和和C C3 3；10110001101101111011110110111011初始状态初始状态3427C0C1C2C32024/4/24周三77b.再分别取再分别取C1间隔间隔2、7拍；取拍；取C2间隔间隔4、7拍；拍；取取C3间隔间隔3、7拍。方法同上，直至全部完拍。方法同上，直至全部完成。成。注意：注意：向量向量C Ci i右移后，总是与原始向量右移后，总是与原始向量C C0 0作逻辑作逻辑加。加。1011000110110111101111011011101110111111初始状态初始状态34422777C0C1C2C3C4772024/4/24周三78（5 5）根据状态图写出调度方案）根据状态图写出调度方案 每一个每一个闭合回路闭合回路就是一个调度方案（策略）就是一个调度方案（策略）1011000110110111101111011011101110111111初始状态初始状态34422777C0C1C2C3C47732024/4/24周三79本例中调度方案如下：本例中调度方案如下：调度策略平均间隔拍数调度策略平均间隔拍数(2,7)4.50(4,3)3.50(2,2,7)3.67(4,3,7)4.67(3,4)3.50(4,7)5.00(3,7)5.00(7)7.00(3,4,7)4.67 平均延时最小的调度方案为最佳平均延时最小的调度方案为最佳调度方案，本例调度方案，本例为（为（3，4）和（）和（4，3）。）。对非对非C0开始的调度方案由开始的调度方案由流水线控制器流水线控制器完成控制完成控制的过渡。的过渡。2024/4/24周三80调度方案的验证原理：二维预约表方法：给定任务数，使用每一种可能的调度方案进行调度验证：调度过程中有无功能段的冲突？2024/4/24周三8112345678910 11 12 13 1415S1 S2S3S4S5例如，按(3,4)调度方案，连续输入3个任务的调度过程如下：2024/4/24周三82按（4，3）调度方案连续输入6个任