《重叠流水和向量处理机.pptx》由会员分享，可在线阅读，更多相关《重叠流水和向量处理机.pptx（118页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、 本章学习标量计算机上使用的流水加速技术。主要内容有流水技术的分类、流水线性能指标计算、非线性流水线的调度算法。标量计算机指只能直接进行标量运算的计算机，与能够直接进行向量运算的向量计算机相对应。流水处理方式的特征，是让多个依次启动的任务，尽量同时使用系统的不同部件，通过时间重叠来提高处理速率。这种技术理论上不增加成本。标量计算机上使用的流水加速技术属于指令级并行技术。每条指令的处理过程，可以划分为取指、译码、每条指令的处理过程，可以划分为取指、译码、取数、运算、送结果取数、运算、送结果5 5个子过程，也可以分得更细个子过程，也可以分得更细或更粗一些。划分的原则是各部分时间长度大致或更粗一些。
2、划分的原则是各部分时间长度大致相等、并使用相等、并使用CPUCPU中不同的部件，这样才有利于多中不同的部件，这样才有利于多任务重叠处理。任务重叠处理。第1页/共118页基本名词术语基本名词术语标量处理机，超标量处理机：标量处理机指只能进行标标量处理机，超标量处理机：标量处理机指只能进行标量运算的处理机，超标量处理机指能在一个时钟周期量运算的处理机，超标量处理机指能在一个时钟周期内同时发射多条指令的处理机；内同时发射多条指令的处理机；指令级并行技术：指能使多条指令并行执行的技术，包指令级并行技术：指能使多条指令并行执行的技术，包括流水技术、多操作部件技术和超长指令字技术；括流水技术、多操作部件技
3、术和超长指令字技术；流水线处理机，超流水线处理机：流水线处理机指用流流水线处理机，超流水线处理机：流水线处理机指用流水作业方式并行解释多条指令的处理机，超流水线处水作业方式并行解释多条指令的处理机，超流水线处理机指能在一个时钟周期内分时发射多条指令的处理理机指能在一个时钟周期内分时发射多条指令的处理机；机；超长指令字技术超长指令字技术VLIW：指让一条指令包含多个独立的：指让一条指令包含多个独立的操作字段，并且分别控制多个功能部件并行工作的技操作字段，并且分别控制多个功能部件并行工作的技术。术。第2页/共118页 一重叠解释方式一重叠解释方式1.1.一条指令的几个过程段一条指令的几个过程段 1
4、 1）取取指指令令：根根据据PCPC（指指令令计计数数器器）从从M M（存存储储器器）取出指令送到取出指令送到IRIR（指令寄存器）（指令寄存器）2 2）译译码码分分析析：译译出出指指令令的的操操作作性性质质，准准备备好好所所需数据需数据 3 3）执执行行：将将准准备备好好的的数数按按译译出出性性质质进进行行处处理理，主要涉及主要涉及ALUALU（算术逻辑运算部件）（算术逻辑运算部件）2.2.对指令执行的几种方式对指令执行的几种方式第3页/共118页1 1）顺序执行）顺序执行 (传统机采用传统机采用)只只有有在在前前一一条条指指令令的的各各过过程程段段全全部部完完成成后后，才才从从存储器取出下
5、一条指令存储器取出下一条指令 2)仅仅两两条条指指令令重重叠叠：第第i i条条指指令令的的执执行行与与第第i+1i+1条条的的取取指指重重叠。叠。3)三三条条指指令令重重叠叠：第第i i条条指指令令的的执执行行与与第第i+1i+1条条的的译译码码及及第第i+2i+2条的取指重叠条的取指重叠。取 译 执 取 译 执 i条 i+1条 i条取译执 i+1条取译执 i+2条取译执i 条取译执取译执 i+1条第4页/共118页 若一条指令的过程段划分更多时，重叠组合方式更多。若一条指令的过程段划分更多时，重叠组合方式更多。重重叠叠解解释释并并不不能能加加快快一一条条指指令令的的实实现现，但但能能加加快快
6、一一段段程序的解释。程序的解释。3.重叠方式中所需时间表达式及所需时间计算重叠方式中所需时间表达式及所需时间计算1 1）条条件件：设设一一条条指指令令分分为为三三个个过过程程段段，各各过过程程段段分分别别用用t t取取、t t译译、t t执执表示。表示。执执行行K K条条指指令令，分分别别采采用用顺顺序序执执行行、两两条条重重叠叠、三条重叠。三条重叠。假设假设:各个功能段时间相同各个功能段时间相同,公式见教材公式见教材P231P231第5页/共118页各个功能段时间不相同各个功能段时间不相同,公式见公式见顺序执行顺序执行 k*k*（t t取取+t+t译译+t+t执）执）两条重叠两条重叠 t t
7、取取+k*t+k*t译译+(k-1)*(t+(k-1)*(t取取,t,t执执)max+t)max+t执执三条重叠三条重叠 t t取取+(t+(t译译,t,t取取)max+(k-2)*)max+(k-2)*（t t取取,t,t译译,t ,t 执）执）max+(tmax+(t执执,t,t译译)max+t)max+t执执第6页/共118页3)3)例子例子 当当k=200k=200，t t取取=3t=3t，t t译译=4t=4t，t t执执=5t=5t，时，分别计算上述三种执行方式的时间。，时，分别计算上述三种执行方式的时间。顺序执行：顺序执行：200(3+4+5)=2400t200(3+4+5)=2
8、400t 两条重叠：两条重叠：3+2004+(200-1)5+5=1803t3+2004+(200-1)5+5=1803t 三条重叠：三条重叠：3+4+(200-2)5+5+5=1007t3+4+(200-2)5+5+5=1007t第7页/共118页4 4 重叠方式需要解决的问题重叠方式需要解决的问题1 1）对存储器的频繁访问）对存储器的频繁访问 有有哪哪些些访访问问：取取指指令令、取取操操作作数数、存存放放执执行行结结果果,I/OI/O通通道道访访问问.希希望望存存储储器器为为多多体体结结构构，以以适适应多种访问源的需要。应多种访问源的需要。当当存存储储器器为为单单体体结结构构时时，需需要要
9、将访问源排队，先后顺序为：将访问源排队，先后顺序为：取指令、取数据、取指令、取数据、I/OI/O通道访问、存结果通道访问、存结果第8页/共118页先行控制（look-ahead）技术最早在IBM公司研制的STRETCH机器中采用。目前，许多处理机中都已经采用了这种技术，包括超流水处理机和超标量处理机等。先行控制技术的关键是缓冲技术和预处理技术，以及两者的结合。缓冲技术是在工作速度不固定的两个功能部件之间设置缓冲栈，用以平滑它们的工作。预处理技术是把进入运算器的指令都处理成寄存器寄存器（RR型）指令，为进入运算器的指令准备好所需要的全部操作数。5.1 5.1 先行控制技术第9页/共118页采用先
10、行控制方式的处理机结构第10页/共118页2）应具有先行控制部件 先行：在重叠操作中，当前一条指令在执行过程中就需要提前取出后面的指令进行相应处理，这种提前取出后继指令进行相应处理，称为先行。先行控制部件的主要包括）先行地址站，包括先行指令地址站和先行操作数地址站；）先行指令站，用来存放多条指令；）先行操作数站，用来存放多个操作数；）先行地址形成部件，用来形成先行指令地址 以及先行操作数地址；）先行操作码译码站，用来完成对多条指令的 译码并保留译码输出状态。第11页/共118页也应具有后行部件 后行部件：对指令执行后的结果进行处理的器件，称 后行部件。包括：后行数地址站，提供后行数存放地址。后
11、行数站，存放运行的结果，并且，这些结果需送存 储器。第12页/共118页5.2.1 基本思想5.2 流水处理的概念第13页/共118页第14页/共118页第15页/共118页5.2.2 流水技术 流水技术：将一个重复的时序过程分解成为若干个子过程，而每个子过程都可有效地在其专用功能段上与其他子过程同时执行。时空图:从时间和空间两个方面描述了流水线的工作过程。时空图中，横坐标代表时间，纵坐标代表流水线的各个段。CPU中的各个部件按流水处理顺序连接起来，就称为一条流水线。第16页/共118页5.2.3 流水线工作原理流水线工作原理流水线方式是把一个复杂的过程分解为若干个子过流水线方式是把一个复杂的
12、过程分解为若干个子过程，每个子过程与其他子过程同时进行。程，每个子过程与其他子过程同时进行。处理机解释程序的方式有顺序方式、重叠方式、流处理机解释程序的方式有顺序方式、重叠方式、流水方式等水方式等 顺序方式是解释完一条指令再开始解释下一条；顺序方式是解释完一条指令再开始解释下一条；流水方式是把一个重复的过程分解为若干个子过程，流水方式是把一个重复的过程分解为若干个子过程，每个子过程可以与其它子过程同时进行，以此提高每个子过程可以与其它子过程同时进行，以此提高单位时间内解释指令的数目；单位时间内解释指令的数目；重叠方式是一种简单的流水方式，它把指令分成重叠方式是一种简单的流水方式，它把指令分成2
13、个子过程个子过程 每条指令只与下一条指令相重叠。每条指令只与下一条指令相重叠。第17页/共118页 重叠方式流水线当分析部件完成上一条指令的当分析部件完成上一条指令的“分析分析”后，就立即将之送入后，就立即将之送入执行部件，同时分析部件可以开始处理下一条指令。执行部件，同时分析部件可以开始处理下一条指令。虽然从执行一条指令的全过程来看，仍需要虽然从执行一条指令的全过程来看，仍需要2t的时间，但从的时间，但从机器的输出端来看，却是每隔一个机器的输出端来看，却是每隔一个t就能给出一条指令的执就能给出一条指令的执行结果。行结果。第18页/共118页 流水线结构图 流水线工作时空图第19页/共118页
14、第20页/共118页 5.2.4 5.2.4 流水线的特点1.流水过程由多个相联系的子过程组成，每个子过程称流水过程由多个相联系的子过程组成，每个子过程称为流水线的级或段，段的数目称为流水线的深度。为流水线的级或段，段的数目称为流水线的深度。2.在流水线中处理的必须是连续任务，只有不断的提供在流水线中处理的必须是连续任务，只有不断的提供任务才能充分发挥流水线的效率。任务才能充分发挥流水线的效率。3.把一个任务分解为几个有联系的子任务，每个子任务把一个任务分解为几个有联系的子任务，每个子任务由一个专门的功能部件来实现。由一个专门的功能部件来实现。4.在流水线的每一个功能部件的后面都要有一个缓冲器
15、，在流水线的每一个功能部件的后面都要有一个缓冲器，用于保存本段的执行结果。用于保存本段的执行结果。5.5.各个功能段所需时间应尽量相等，否则时间长的功能各个功能段所需时间应尽量相等，否则时间长的功能各个功能段所需时间应尽量相等，否则时间长的功能各个功能段所需时间应尽量相等，否则时间长的功能段将成为流水线的段将成为流水线的段将成为流水线的段将成为流水线的“瓶颈瓶颈瓶颈瓶颈”，会造成流水线的，会造成流水线的，会造成流水线的，会造成流水线的“堵塞堵塞堵塞堵塞”和和和和“断流断流断流断流”。这个时间一般为一个时钟周期（节拍）。这个时间一般为一个时钟周期（节拍）。这个时间一般为一个时钟周期（节拍）。这个
16、时间一般为一个时钟周期（节拍）。6.流水线需要有流水线需要有“装入时间装入时间”和和“排空时间排空时间”。第21页/共118页5.3 5.3 流水技术的分类1）按各过程段用时是否全等划分 均匀流水线：各过程段用时全等 非均匀流水线：各过程段用时不全等（如上图）时间匹配的均匀流水线。）时间不匹配的非均匀流水线。第22页/共118页2）按处理的数据类型标量流水线：用于对标量数据进行流水处理。向量流水线：用于对向量数据进行流水处理。（向量很适合流水处理）3）按流水线的规模操作流水线：如将一条指令划分为多个过程段进行流水处理。规模最小指令流水线：以指令为单位进行处理，用于多进程、多任务。规模较大 宏流
17、水线：以程序的逻辑功能段为单位进行流水处理。规模最大第23页/共118页4）按流水线具有功能的多少 单功能流水线：各过程段之间固定连接，不能重新构成其它流水线固定流水线 多功能流水线分：静态流水线：各过程段之间可重新连接，但不同时刻只能重构成一种不同的流水线。动态流水线：各过程段之间可重新连接，不同时刻可重构成多种流水线。5）按部件在同一时刻送出支路数的多少来分。一维流水线：在同一时刻，部件只能向一个地方传送结果。阵列流水线：在同一时刻，部件可同时向多个地方传送结果。第24页/共118页5.4.5“5.4.5“瓶颈瓶颈”问题及其解决方法问题及其解决方法瓶颈：瓶颈就是瓶颈：瓶颈就是titi最大的
18、段，它使流水线最大的段，它使流水线“流速流速”减慢。减慢。S1S1S2S2S3S3S4S4tt3t3t tttt方法方法1 1：再细分：再细分 将瓶颈设备再细分为下一将瓶颈设备再细分为下一级流水线级流水线S1S1S2aS2aS2bS2bS2cS2cS3S3S4S4tttttttttttt方法方法2 2：并行设置：并行设置 将瓶颈设备重复设置多将瓶颈设备重复设置多套。套。第25页/共118页衡量流水线的主要指标有吞吐率，加速比和效率。衡量流水线的主要指标有吞吐率，加速比和效率。5.4.1 5.4.1 吞吐率吞吐率TPTP吞吐率（吞吐率（TP ThroughPut）指流水线在单位时间内执行的任务数
19、，）指流水线在单位时间内执行的任务数，可以用输入任务数或输出任务数表示。可以用输入任务数或输出任务数表示。其中其中k表示流水线划分的段数。表示流水线划分的段数。当满足当满足 条件时，有条件时，有。5.4 5.4 线性流水线性能分析第26页/共118页 S4 1 2 3 4 N-1 N S3 1 2 3 4 N-1 N S2 1 2 3 4 N-1 N S1 1 2 3 4 N-1 N 时间 KT (N-1)T NT (K-1)T Tk第27页/共118页 流水线产生流水线产生n n个结果所需要的时间：个结果所需要的时间：实际吞吐率实际吞吐率：最大吞吐率：最大吞吐率：最大吞吐率与实际吞吐率的关系
20、：最大吞吐率与实际吞吐率的关系：（1 1）流水线各段的执行时间相等流水线各段的执行时间相等第28页/共118页 实际吞吐率：实际吞吐率：最大吞吐率：最大吞吐率：（2 2）流水线各段的执行时间不等流水线各段的执行时间不等第29页/共118页5.4.2 5.4.2 加速比（即吞吐率之比，）不使用流水线所用的时间与使用流水线所用的时间之比不使用流水线所用的时间与使用流水线所用的时间之比一般表示：一般表示：s=Ts=T0 0/T/TK K其中其中 实际加速比：实际加速比：最大加速比：最大加速比：第30页/共118页段效率：，各段平均效率：其中 表示第i段设备量占整条流水线全部设备量的百分比当满足 条件
21、（即等长、等权）时，有：5.4.3 5.4.3 效率（设备利用率）上式指出，S=Ek，就是说当效率达到100%时，流水方式（一个任务/t）吞吐率为顺序方式（一个任务/(kt)）的k倍。第31页/共118页实际效率：最大效率：第32页/共118页瓶颈问题用两种方法改进后的效率和吞吐率瓶颈问题用两种方法改进后的效率和吞吐率第33页/共118页静态双功能流水线的效率与吞吐率静态双功能流水线的效率与吞吐率教材P241第34页/共118页非线性流水线的吞吐率和效率教材P291第35页/共118页 5.5 5.5 流水线中的相关流水线中的相关相关的定义：相关的定义：流水线中的相关是指相邻或相近的指令因存在
22、某种关联，流水线中的相关是指相邻或相近的指令因存在某种关联，后面的指令不能在原指定的时钟周期开始执行。后面的指令不能在原指定的时钟周期开始执行。一般来说，流水线中的相关主要分为如下三种类型：一般来说，流水线中的相关主要分为如下三种类型：1.1.结构相关：当硬件资源满足不了指令重叠执行的要求，结构相关：当硬件资源满足不了指令重叠执行的要求，而发生资源冲突时，就发生了结构相关。而发生资源冲突时，就发生了结构相关。2.2.数据相关：当一条指令需要用到前面指令的执行结果，数据相关：当一条指令需要用到前面指令的执行结果，而这些指令均在流水线中重叠执行时，就可能引起数据而这些指令均在流水线中重叠执行时，就
23、可能引起数据相关。相关。3.3.控制相关：当流水线遇到分支指令和其它能够改变控制相关：当流水线遇到分支指令和其它能够改变 PC PC 值的指令时，就会发生控制相关。值的指令时，就会发生控制相关。第36页/共118页一旦流水线中出现相关，必然会给指令在流水线一旦流水线中出现相关，必然会给指令在流水线中的顺利执行带来许多问题，如果不能很好地中的顺利执行带来许多问题，如果不能很好地解决相关问题，轻则影响流水线的性能，重则解决相关问题，轻则影响流水线的性能，重则导致错误的执行结果。消除相关的基本方法是导致错误的执行结果。消除相关的基本方法是让流水线暂停执行某些指令，而继续执行其它让流水线暂停执行某些指
24、令，而继续执行其它一些指令。一些指令。在后面的讨论中，我们约定：当一条在后面的讨论中，我们约定：当一条指令被暂停时，在该暂停指令之后发射的所有指令被暂停时，在该暂停指令之后发射的所有指令都要被暂停，而在该暂停之前发射的指令指令都要被暂停，而在该暂停之前发射的指令则可继续进行，在暂停期间，流水线不会取新则可继续进行，在暂停期间，流水线不会取新的指令的指令。第37页/共118页 5.5.1 5.5.1 结构相关如果某些指令组合在流水线中重叠执行时，产生如果某些指令组合在流水线中重叠执行时，产生资源冲突，则称该流水线有结构相关。为了能够资源冲突，则称该流水线有结构相关。为了能够在流水线中顺利执行指令
25、的所有可能组合，而不在流水线中顺利执行指令的所有可能组合，而不发生结构相关，通常需要采用流水化功能单元的发生结构相关，通常需要采用流水化功能单元的方法或资源重复的方法。方法或资源重复的方法。第38页/共118页许多流水线机器都是将数据和指令保存在同一存许多流水线机器都是将数据和指令保存在同一存储器中。如果在某个时钟周期内，流水线既要储器中。如果在某个时钟周期内，流水线既要完成某条指令对数据的存储器访问操作，又要完成某条指令对数据的存储器访问操作，又要完成取指令的操作，那么将会发生存储器访问完成取指令的操作，那么将会发生存储器访问冲突问题冲突问题 产生结构相关。为了解决这个问题，产生结构相关。为
26、了解决这个问题，可以让流水线完成前一条指令对数据的存储器可以让流水线完成前一条指令对数据的存储器访问时，暂停取后一条指令的操作。该周期称访问时，暂停取后一条指令的操作。该周期称为流水线的一个暂停周期。暂停周期一般也称为流水线的一个暂停周期。暂停周期一般也称为流水线气泡，或简称为为流水线气泡，或简称为“气泡气泡”。在流水线。在流水线中插入暂停周期可以消除这种结构相关。中插入暂停周期可以消除这种结构相关。第39页/共118页 结构相关举例访存冲突结构相关举例访存冲突第40页/共118页 为为消除结构相关插入流水气泡消除结构相关插入流水气泡第41页/共118页 时空图来表示暂停情况时空图来表示暂停情
27、况第42页/共118页分析分析 为消除结构相关而引入的暂停将影响流水线为消除结构相关而引入的暂停将影响流水线的性能。为了避免结构相关，可以考虑采用资的性能。为了避免结构相关，可以考虑采用资源重复的方法。比如，在流水线机器中设置相源重复的方法。比如，在流水线机器中设置相互独立的指令存储器和数据存储器；也可以将互独立的指令存储器和数据存储器；也可以将 Cache Cache 分割成指令分割成指令 Cache Cache 和数据和数据 CacheCache。第43页/共118页 假设不考虑流水线其它因素对流水线性能假设不考虑流水线其它因素对流水线性能的影响，显然如果流水线机器没有结构相关，的影响，显
28、然如果流水线机器没有结构相关，那么其那么其 CPI CPI 也较小。然而，为什么有时流水线也较小。然而，为什么有时流水线设计者却允许结构相关的存在呢？主要有两个设计者却允许结构相关的存在呢？主要有两个原因：一是为了减少硬件代价，二是为了减少原因：一是为了减少硬件代价，二是为了减少功能单元的延迟。如果为了避免结构相关而将功能单元的延迟。如果为了避免结构相关而将流水线中的所有功能单元完全流水化，或者设流水线中的所有功能单元完全流水化，或者设置足够的硬件资源，那么所带来的硬件代价必置足够的硬件资源，那么所带来的硬件代价必定很大。定很大。第44页/共118页 5.5.2 5.5.2 数据相关数据相关当
29、指令在流水线中重叠执行时，流水线有可能改变指令当指令在流水线中重叠执行时，流水线有可能改变指令读读/写操作数的顺序，使得读写操作数的顺序，使得读/写操作顺序不同于它们非流写操作顺序不同于它们非流水实现的顺序，这将导致数据相关。水实现的顺序，这将导致数据相关。ADD R1，R2，R3SUBR4，R5，R1AND R6，R1，R7ORR8，R1，R9XORR10，R1，R11第45页/共118页 ADD ADD指令后的所有指令都要用到指令后的所有指令都要用到ADDADD指令的计算结果，指令的计算结果，ADD ADD 指令在指令在 WB WB 段才段才将计算结果写入寄存器将计算结果写入寄存器 R1
30、R1 中，但是中，但是 SUB SUB 指令在其指令在其 ID ID 段就要从寄存器段就要从寄存器 R1 R1 中读取该计算结果，这种情况就叫做数据相关。除非有措施防止这一情况出现，中读取该计算结果，这种情况就叫做数据相关。除非有措施防止这一情况出现，否则否则 SUB SUB 指令读到的是错误的值。所以，为了保证上述指令序列的正确执行，指令读到的是错误的值。所以，为了保证上述指令序列的正确执行，流水线只好暂停流水线只好暂停 ADD ADD 指令之后的所有指令，直到指令之后的所有指令，直到 ADD ADD 指令将计算结果写入寄指令将计算结果写入寄存器存器 R1 R1 之后，再启动之后，再启动 A
31、DD ADD 指令之后的指令继续执行。指令之后的指令继续执行。第46页/共118页数据相关举例数据相关举例第47页/共118页例子分析例子分析 从上图还可以看到，从上图还可以看到，AND AND 指令同样也将受到这种相关关指令同样也将受到这种相关关系的影响。系的影响。ADD ADD 指令只有到第五个时钟周期末尾才能结束对指令只有到第五个时钟周期末尾才能结束对寄存器寄存器 R1 R1 的写操作，所以的写操作，所以 AND AND 指令在第四个时钟周期从寄指令在第四个时钟周期从寄存器存器 R1 R1 中读出的值也是错误的。而中读出的值也是错误的。而 XOR XOR 指令则可以正常操指令则可以正常操
32、作，因为它是在第六个时钟周期读寄存器作，因为它是在第六个时钟周期读寄存器 R1 R1 的内容。的内容。另外，利用流水线的一种简单技术，可以使流水线顺利执另外，利用流水线的一种简单技术，可以使流水线顺利执行行 OR OR 指令。这种技术就是：在流水线中，约定在时钟周期的指令。这种技术就是：在流水线中，约定在时钟周期的后半部分进行寄存器文件的读操作，而在时钟周期的前半部分后半部分进行寄存器文件的读操作，而在时钟周期的前半部分进行寄存器文件的写操作。在图中，我们将寄存器文件的边框进行寄存器文件的写操作。在图中，我们将寄存器文件的边框适当地画成虚线来表示这种技术。适当地画成虚线来表示这种技术。第48页
33、/共118页通过定向技术减少数据相关带来的暂停通过定向技术减少数据相关带来的暂停数据相关问题可以采用一种称为定向（也称为旁路数据相关问题可以采用一种称为定向（也称为旁路或短路）的简单技术来解决或短路）的简单技术来解决 。定向技术的主要思。定向技术的主要思想是：在某条指令（如图中的想是：在某条指令（如图中的 ADD ADD 指令）产生一指令）产生一个计算结果之前，其它指令（如图中的个计算结果之前，其它指令（如图中的 SUB SUB 和和 AND AND 指令）并不真正需要该计算结果，如果能够将指令）并不真正需要该计算结果，如果能够将该计算结果从其产生的地方（寄存器文件该计算结果从其产生的地方（寄
34、存器文件 EX/MEMEX/MEM）直接送到其它指令需要它的地方（）直接送到其它指令需要它的地方（ALU ALU 的的输入寄存器），那么就可以避免暂停输入寄存器），那么就可以避免暂停.第49页/共118页基于这种考虑，定向技术的要点可以归纳为：基于这种考虑，定向技术的要点可以归纳为：寄存器文件寄存器文件 EX/MEM EX/MEM 中的中的 ALU ALU 的运算结果总是回送到的运算结果总是回送到 ALU ALU 的输入寄存器；的输入寄存器；当定向硬件检测到前一个当定向硬件检测到前一个 ALU ALU 运算结果的写入寄存器就是当前运算结果的写入寄存器就是当前 ALU ALU 操作操作的源寄存器
35、时，那么控制逻辑将前一个的源寄存器时，那么控制逻辑将前一个 ALU ALU 运算结果定向到运算结果定向到 ALU ALU 的输入的输入端，后一个端，后一个 ALU ALU 操作就不必从源寄存器中读取操作数。操作就不必从源寄存器中读取操作数。流水线中的指令所需要的定向结果可能并不仅仅是前一条指令的计算结果，而且流水线中的指令所需要的定向结果可能并不仅仅是前一条指令的计算结果，而且还有可能是前面与其不相邻指令的计算结果还有可能是前面与其不相邻指令的计算结果第50页/共118页采用定向技术消除数据相关采用定向技术消除数据相关第51页/共118页定向技术的推广定向技术的推广上述定向技术可以推广到更一般
36、的情况，可以将上述定向技术可以推广到更一般的情况，可以将一个结果直接传送到所有需要它的功能单元。也一个结果直接传送到所有需要它的功能单元。也就是说，一个结果不仅可以从某一功能单元的输就是说，一个结果不仅可以从某一功能单元的输出定向到其自身的输入，而且还可以从某一功能出定向到其自身的输入，而且还可以从某一功能单元的输出定向到其它功能单元的输入单元的输出定向到其它功能单元的输入 。前面的一些数据相关的实例均是有关寄存器操作前面的一些数据相关的实例均是有关寄存器操作数的，但是数据相关也有可能发生在一对指令对数的，但是数据相关也有可能发生在一对指令对存储器同一单元进行读写的时候。不过，本章仅存储器同一
37、单元进行读写的时候。不过，本章仅讨论有关寄存器的数据相关。讨论有关寄存器的数据相关。第52页/共118页到数据存储器和到数据存储器和ALUALU的定向路径的定向路径第53页/共118页数据相关分类数据相关分类根据指令对寄存器的读写顺序，可以将数据相关分为三根据指令对寄存器的读写顺序，可以将数据相关分为三类。习惯上，这些相关是根据流水线所必须保持的访问类。习惯上，这些相关是根据流水线所必须保持的访问顺序来命名的。考虑流水线中的两条指令顺序来命名的。考虑流水线中的两条指令 i i 和和 j j，且，且 i i 在在 j j 之前进入流水线，由此可能带来的数据相关有：之前进入流水线，由此可能带来的数
38、据相关有：第54页/共118页写后读相关（写后读相关（Read After Write，RAW）：）：j 的执行要的执行要用到用到 i 的计算结果，当它们在流水线中重叠执行时，的计算结果，当它们在流水线中重叠执行时，j 可能在可能在 i 写入其计算结果之前就先行对保存该结果的寄写入其计算结果之前就先行对保存该结果的寄存器进行读操作，从而得到错误的值。这是最常见的存器进行读操作，从而得到错误的值。这是最常见的一种数据相关，采用定向技术消除的数据相关就属于一种数据相关，采用定向技术消除的数据相关就属于这种类型。这种类型。第55页/共118页写后写相关（写后写相关（Write After Write
39、Write After Write，WAWWAW）：）：j j 和和 i i 的目的寄存器相同，当它们在流水线中重的目的寄存器相同，当它们在流水线中重叠执行时，叠执行时，j j 可能在可能在 i i 写入其计算结果之前就写入其计算结果之前就先行对该结果寄存器进行写操作，从而导致写先行对该结果寄存器进行写操作，从而导致写入顺序错误，在目的寄存器中留下的是入顺序错误，在目的寄存器中留下的是 i i 写入写入的值，而不是的值，而不是 j j 写入的值。写入的值。如果在流水线中不只一个段可以进行写操作，如果在流水线中不只一个段可以进行写操作，或者当流水线暂停某条指令时，允许该指令之或者当流水线暂停某条
40、指令时，允许该指令之后的指令继续前进，就可能会产生这种类型的后的指令继续前进，就可能会产生这种类型的数据相关。数据相关。读后写相关（读后写相关（Write After ReadWrite After Read，WARWAR）：）：j j 可能在可能在 i i 读取某个源寄存器的内容之前就先对读取某个源寄存器的内容之前就先对该寄存器进行写操作，导致该寄存器进行写操作，导致 i i 后来读取到的值后来读取到的值是错误的。是错误的。第56页/共118页需要暂停的数据相关需要暂停的数据相关前面我们讨论了如何利用定向技术消除由于数据相关带前面我们讨论了如何利用定向技术消除由于数据相关带来的暂停。但是，并
41、不是所有数据相关带来的暂停都可来的暂停。但是，并不是所有数据相关带来的暂停都可以通过定向技术消除。以通过定向技术消除。第57页/共118页对数据相关的编译器调度方法流水线常常会遇到许多种类型的暂停。比如，采用典型的代码流水线常常会遇到许多种类型的暂停。比如，采用典型的代码生成方法对生成方法对A=BC这种常用的表达式进行处理，可以得到如图这种常用的表达式进行处理，可以得到如图所示的指令序列。从图中可以看出，在所示的指令序列。从图中可以看出，在 ADD 指令的流水过程中指令的流水过程中必须插入一个暂停时钟周期，以保证变量必须插入一个暂停时钟周期，以保证变量C的读入值有效。既然的读入值有效。既然定向
42、无法消除指令序列中所包含的这种暂停，那么能否让编译定向无法消除指令序列中所包含的这种暂停，那么能否让编译器在进行代码生成时就消除这些潜在的暂停呢？器在进行代码生成时就消除这些潜在的暂停呢？第58页/共118页指令级调度指令级调度实际上，编译器的确可以通过重新组织代码顺序来消除实际上，编译器的确可以通过重新组织代码顺序来消除这种暂停。通常称这种重新组织代码顺序消除暂停的技这种暂停。通常称这种重新组织代码顺序消除暂停的技术为流水线调度（术为流水线调度（pipeline schedulingpipeline scheduling）或指令调度）或指令调度（instruction schedulingi
43、nstruction scheduling）。）。第59页/共118页 5.5.3 5.5.3 控制相关控制相关在流水线上执行分支指令时，在流水线上执行分支指令时，PC 值有两种可能值有两种可能的变化情况。一种是的变化情况。一种是 PC 值发生改变（为分支转值发生改变（为分支转移的目标地址）；一种是移的目标地址）；一种是 PC 值保持正常。如果值保持正常。如果一条分支指令将一条分支指令将PC值改变为分支转移的目标地值改变为分支转移的目标地址，那么我们称分支转移成功；如果分支转移条址，那么我们称分支转移成功；如果分支转移条件不成立，件不成立，PC 值保持正常，我们称分支转移失值保持正常，我们称分
44、支转移失败。败。第60页/共118页第61页/共118页处理分支指令最简单的方法是：一旦在流水线中处理分支指令最简单的方法是：一旦在流水线中检测到某条指令是分支指令，就暂停执行该分支检测到某条指令是分支指令，就暂停执行该分支指令之后的所有指令，直到分支指令到达流水线指令之后的所有指令，直到分支指令到达流水线的的 MEM 段，确定了新的段，确定了新的 PC 值为止。我们当然值为止。我们当然不希望流水线还没有确定某条指令是分支指令之不希望流水线还没有确定某条指令是分支指令之前就暂停执行指令，所以对分支指令而言，当流前就暂停执行指令，所以对分支指令而言，当流水线完成其译码操作（水线完成其译码操作（I
45、D段）之后才会暂停执行段）之后才会暂停执行其后继指令。其后继指令。根据上述处理分支指令的方法，可以得到如根据上述处理分支指令的方法，可以得到如图所示流水线时空图图所示流水线时空图。从图中可以看出，在流水。从图中可以看出，在流水线中插入了两个暂停周期，当分支指令在线中插入了两个暂停周期，当分支指令在 MEM 段确定新的段确定新的 PC 值后，流水线作废分支直接后继值后，流水线作废分支直接后继指令的指令的 IF 周期（相当于一个暂停周期），按照周期（相当于一个暂停周期），按照新的有效新的有效 PC 值取指令。值取指令。第62页/共118页第63页/共118页减少分支暂停时钟周期数减少流水线处理分支
46、指令时的暂停时钟周期数有如下减少流水线处理分支指令时的暂停时钟周期数有如下两种途径：两种途径：1.在流水线中尽早判断出分支转移是否成功；在流水线中尽早判断出分支转移是否成功；2.尽早计算出分支转移成功时的尽早计算出分支转移成功时的 PC 值（即分支的目值（即分支的目标地址）。标地址）。为了优化处理分支指令，在流水线中应该同时为了优化处理分支指令，在流水线中应该同时采用上述两条途径，缺一不可。即使知道分支转移采用上述两条途径，缺一不可。即使知道分支转移的目标地址，而不知道分支转移是否成功对减少暂的目标地址，而不知道分支转移是否成功对减少暂停是徒劳的；知道分支转移是否成功，而不知道分停是徒劳的；知
47、道分支转移是否成功，而不知道分支转移的目标地址，同样对降低分支损失毫无帮助。支转移的目标地址，同样对降低分支损失毫无帮助。下面让我们看看如何基于这些思想，从硬件上改进下面让我们看看如何基于这些思想，从硬件上改进流水线，达到降低分支损失的目的。流水线，达到降低分支损失的目的。第64页/共118页在流水线中，分支指令通常需要测试分支条件寄在流水线中，分支指令通常需要测试分支条件寄存器的值是否为存器的值是否为0，所以可以把测试分支条件寄，所以可以把测试分支条件寄存器的操作移到存器的操作移到 ID 段完成，从而使得在段完成，从而使得在 ID 周期周期末就完成分支转移成功与否的检测。末就完成分支转移成功
48、与否的检测。另外，由于要尽早计算出两个另外，由于要尽早计算出两个 PC 值（分支值（分支转移成功和失败时的转移成功和失败时的 PC 值），也可以将计算分值），也可以将计算分支目标地址的操作移到支目标地址的操作移到 ID 段完成。为此，需要段完成。为此，需要在在 ID 段增设一个加法器（注意，为了避免结构段增设一个加法器（注意，为了避免结构相关，不能用相关，不能用EX段的段的 ALU 功能部件来计算分支功能部件来计算分支转移目标地址）。下图是对流水线进行上述改进转移目标地址）。下图是对流水线进行上述改进后的流水线数据通路。容易看出，基于上述改进后的流水线数据通路。容易看出，基于上述改进后的流水线
49、数据通路，处理分支指令只需要一个后的流水线数据通路，处理分支指令只需要一个时钟周期的暂停。时钟周期的暂停。第65页/共118页第66页/共118页减少分支暂停时钟周期数减少分支暂停时钟周期数降低流水线分支损失的方法有许多种。前面论降低流水线分支损失的方法有许多种。前面论述了改进流水线硬件减少流水线暂停周期的方述了改进流水线硬件减少流水线暂停周期的方法。这里主要从编译技术的角度，论述四种降法。这里主要从编译技术的角度，论述四种降低流水线分支损失的简单方法。首先需要说明低流水线分支损失的简单方法。首先需要说明的是，这些方法对分支转移成功与否进行的预的是，这些方法对分支转移成功与否进行的预测都是静态
50、的，并在整个程序的执行过程中保测都是静态的，并在整个程序的执行过程中保持这种预测结论，即：要么总是认为分支转移持这种预测结论，即：要么总是认为分支转移成功，要么总是认为分支转移失败。成功，要么总是认为分支转移失败。第67页/共118页1.1.冻结（冻结（freezefreeze）或排空（）或排空（flushflush）流水线的方）流水线的方法法在流水线中，处理分支最简单的方法是冻结在流水线中，处理分支最简单的方法是冻结或排空流水线，保持或清除流水线在分支指或排空流水线，保持或清除流水线在分支指令之后读入的任何指令，直到知道分支指令令之后读入的任何指令，直到知道分支指令的目标地址以及分支转移是否