第五章重叠、流水和向量处理机1

1、第五章第五章 重叠、流水和向量处理机重叠、流水和向量处理机1 重叠方式重叠方式通常提高指令执行速度的途径有如下三种：通常提高指令执行速度的途径有如下三种：提高处理机的工作主频。提高处理机的工作主频。采用更好的算法和设计更好的功能部件。采用更好的算法和设计更好的功能部件。多条指令并行执行，称为指令级并行技术。多条指令并行执行，称为指令级并行技术。 可以从两个方面来开发处理机内部的并行性：可以从两个方面来开发处理机内部的并行性：空间并行性：即在一个处理机内设置多个独空间并行性：即在一个处理机内设置多个独立的操作部件，并让这些操作部件并行工作，立的操作部件，并让这些操作部件并行工作，这种处理机称为多

2、操作部件处理机或超标量这种处理机称为多操作部件处理机或超标量处理机处理机;时间并行性：就是采用流水线技术。流水线时间并行性：就是采用流水线技术。流水线技术是一种非常经济、对提高处理机的运算技术是一种非常经济、对提高处理机的运算速度非常有效的技速度非常有效的技 术。采用流水线技术可以术。采用流水线技术可以不增加硬件或只需要增加少量硬件就能够把不增加硬件或只需要增加少量硬件就能够把处理机的运算速度提高几倍处理机的运算速度提高几倍 它是目前使用非常普遍的一种并行处理它是目前使用非常普遍的一种并行处理方式。方式。 本章学习标量计算机上使用的流水加速技术。主要内本章学习标量计算机上使用的流水加速技术。主

3、要内容有流水技术的分类、流水线性能指标计算、非线性流水容有流水技术的分类、流水线性能指标计算、非线性流水线的调度算法。线的调度算法。 标量计算机指只能直接进行标量运算的计算机，与能标量计算机指只能直接进行标量运算的计算机，与能够直接进行向量运算的向量计算机相对应。够直接进行向量运算的向量计算机相对应。 流水处理方式的特征，是让多个依次启动的任务，尽流水处理方式的特征，是让多个依次启动的任务，尽量同时使用系统的不同部件，通过时间重叠来提高处理速量同时使用系统的不同部件，通过时间重叠来提高处理速率。这种技术理论上不增加成本。率。这种技术理论上不增加成本。 标量计算机上使用的流水加速技术属于指令级并

4、行技标量计算机上使用的流水加速技术属于指令级并行技术。术。 每条指令的处理过程，可以划分为取指、译码每条指令的处理过程，可以划分为取指、译码、取数、运算、送结果、取数、运算、送结果5 5个子过程，也可以分得更个子过程，也可以分得更细或更粗一些。划分的原则是各部分时间长度大细或更粗一些。划分的原则是各部分时间长度大致相等、并使用致相等、并使用CPUCPU中不同的部件，这样才有利于中不同的部件，这样才有利于多任务重叠处理。多任务重叠处理。基本名词术语基本名词术语 标量处理机，超标量处理机：标量处理机指只能进行标量处理机，超标量处理机：标量处理机指只能进行标量运算的处理机，超标量处理机指能在一个时钟

5、周标量运算的处理机，超标量处理机指能在一个时钟周期内同时发射多条指令的处理机；期内同时发射多条指令的处理机； 指令级并行技术：指能使多条指令并行执行的技术，指令级并行技术：指能使多条指令并行执行的技术，包括流水技术、多操作部件技术和超长指令字技术；包括流水技术、多操作部件技术和超长指令字技术； 流水线处理机，超流水线处理机：流水线处理机指用流水线处理机，超流水线处理机：流水线处理机指用流水作业方式并行解释多条指令的处理机，超流水线流水作业方式并行解释多条指令的处理机，超流水线处理机指能在一个时钟周期内分时发射多条指令的处处理机指能在一个时钟周期内分时发射多条指令的处理机；理机； 超长指令字技术

6、超长指令字技术VLIW：指让一条指令包含多个独立的：指让一条指令包含多个独立的操作字段，并且分别控制多个功能部件并行工作的技操作字段，并且分别控制多个功能部件并行工作的技术。术。 一重叠解释方式一重叠解释方式1.1.一条指令的几个过程段一条指令的几个过程段 1 1）取指令：根据）取指令：根据PCPC（指令计数器）从（指令计数器）从M M（存储器）（存储器）取出指令送到取出指令送到IRIR（指令寄存器）（指令寄存器） 2 2）译码分析：译出指令的操作性质，准备好所需）译码分析：译出指令的操作性质，准备好所需数据数据 3 3）执行：将准备好的数按译出性质进行处理，主）执行：将准备好的数按译出性质进

7、行处理，主要涉及要涉及ALUALU（算术逻辑运算部件）（算术逻辑运算部件） 2. 2. 对指令执行的几种方式对指令执行的几种方式1 1）顺序执行）顺序执行 ( (传统机采用传统机采用) ) 只有在前一条指令的各过程段全部完成后，才只有在前一条指令的各过程段全部完成后，才从存储器取出下一条指令从存储器取出下一条指令 2) 仅两条指令重叠：第仅两条指令重叠：第i i条指令的执行与第条指令的执行与第i+1i+1条的取指条的取指重叠。重叠。3) 三条指令重叠：第三条指令重叠：第i i条指令的执行与第条指令的执行与第i+1i+1条的译码及条的译码及第第i+2i+2条的取指重叠条的取指重叠。 取 译 执

8、取 译 执 i条 i +1条 i条取译执 i+1条取译执 i+2条取译执i 条取译执取译执 i+1条 若一条指令的过程段划分更多时，重叠组合方式更多。若一条指令的过程段划分更多时，重叠组合方式更多。 重叠解释并不能加快一条指令的实现，但能加快一段重叠解释并不能加快一条指令的实现，但能加快一段程序的解释。程序的解释。1 1）条件：设一条指令分为三个过程段，各过程段分别）条件：设一条指令分为三个过程段，各过程段分别用用t t取取、t t译译、t t执执表示。表示。 执行执行K K条指令，分别采用顺序执行、两条重叠、条指令，分别采用顺序执行、两条重叠、三条重叠。三条重叠。假设假设: :各个功能段时间

9、相同各个功能段时间相同, ,公式见教材公式见教材P231P231各个功能段时间不相同各个功能段时间不相同, ,公式见公式见顺序执行顺序执行 k k* *（t t取取+t+t译译+t+t执）执）两条重叠两条重叠 t t取取+ k+ k* * t t译译+(k-1) +(k-1) * *( t( 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执执3) 3) 例子例

10、子 当当k=200k=200，t t取取=3t=3t，t t译译=4t=4t，t t执执=5t=5t，时，分别计算上述三种执行方式的时间。时，分别计算上述三种执行方式的时间。 顺序执行：顺序执行：200200(3+4+5)=2400t(3+4+5)=2400t 两条重叠：两条重叠：3+2003+2004+(200-1)4+(200-1)5+5=1803t5+5=1803t 三条重叠：三条重叠：3+4+(200-2)3+4+(200-2)5+5+5=1007t5+5+5=1007t4 4 重叠方式需要解决的问题重叠方式需要解决的问题1 1）对存储器的频繁访问）对存储器的频繁访问 有哪些访问：取指

11、令、取操作有哪些访问：取指令、取操作数、存放执行结果数、存放执行结果, I/O, I/O通道访问通道访问. . 希望存储器为多体结构，以适希望存储器为多体结构，以适应多种访问源的需要。应多种访问源的需要。 当存储器为单体结构时，需要当存储器为单体结构时，需要将访问源排队，先后顺序为：将访问源排队，先后顺序为： 取指令、取数据、取指令、取数据、I/OI/O通道访问、存通道访问、存结果结果 先行控制（先行控制（look-ahead）技术最早在）技术最早在IBM公司研制的公司研制的STRETCH机器中采用。目前，许多处理机中都已经采机器中采用。目前，许多处理机中都已经采用了这种技术，包括超流水处理机

12、和超标量处理机等。用了这种技术，包括超流水处理机和超标量处理机等。 先行控制技术的关键是缓冲技术和预处理技术，以及两先行控制技术的关键是缓冲技术和预处理技术，以及两者的结合。者的结合。 缓冲技术是在工作速度不固定的两个功能部件之间设置缓冲技术是在工作速度不固定的两个功能部件之间设置缓冲栈，用以平滑它们的工作。缓冲栈，用以平滑它们的工作。 预处理技术是把进入运算器的指令都处理成寄存器寄预处理技术是把进入运算器的指令都处理成寄存器寄存器（存器（RR型）指令，为进入运算器的指令准备好所需要型）指令，为进入运算器的指令准备好所需要的全部操作数的全部操作数。5.1 5.1 先行控制技术先行控制技术采用先

13、行控制方式的处理机结构采用先行控制方式的处理机结构2）应具有先行控制部件）应具有先行控制部件 先行：在重叠操作中，当前一条指令在执行过程中先行：在重叠操作中，当前一条指令在执行过程中就需要提前取出后面的指令进行相应处理，这种提就需要提前取出后面的指令进行相应处理，这种提前取出后继指令进行相应处理，称为先行。前取出后继指令进行相应处理，称为先行。 先行控制部件的主要包括先行控制部件的主要包括 ）先行地址站，包括先行指令地址站和先行操作数）先行地址站，包括先行指令地址站和先行操作数地址站；地址站； ）先行指令站，用来存放多条指令；先行指令站，用来存放多条指令； ）先行操作数站先行操作数站，用来存放

14、多个操作数；用来存放多个操作数； ）先行地址形成部件，用来形成先行指令地址先行地址形成部件，用来形成先行指令地址 以及先行操作数地址；以及先行操作数地址； ）先行操作码译码站，用来完成对多条指令的先行操作码译码站，用来完成对多条指令的 译码并保留译码输出状态。译码并保留译码输出状态。 也应具有后行部件也应具有后行部件 后行部件：对指令执行后的结果进行处理的器件，称后行部件：对指令执行后的结果进行处理的器件，称 后行部件。包括：后行部件。包括：后行数地址站，提供后行数存放地址。后行数地址站，提供后行数存放地址。后行数站，存放运行的结果，并且，这些结果需送存后行数站，存放运行的结果，并且，这些结果

15、需送存 储器。储器。5.2.1 基本思想5.2 流水处理的概念5.2.2 流水技术流水技术 流水技术流水技术：将一个重复的时序过程分解成为若干个子：将一个重复的时序过程分解成为若干个子过程，而每个子过程都可有效地在其专用功能段上与其过程，而每个子过程都可有效地在其专用功能段上与其他子过程同时执行。他子过程同时执行。 时空图时空图:从时间和空间两个方面描述了流水线的工作从时间和空间两个方面描述了流水线的工作过程。时空图中，横坐标代表时间，纵坐标代表流水过程。时空图中，横坐标代表时间，纵坐标代表流水线的各个段。线的各个段。 CPU中的各个部件按流水处理顺序连接起来，就称为一中的各个部件按流水处理顺

16、序连接起来，就称为一条条流水线流水线。5.2.3 流水线工作原理流水线工作原理流水线方式是把一个复杂的过程分解为若干个子过流水线方式是把一个复杂的过程分解为若干个子过程，每个子过程与其他子过程同时进行。程，每个子过程与其他子过程同时进行。处理机解释程序的方式有顺序方式、重叠方式、流处理机解释程序的方式有顺序方式、重叠方式、流水方式等水方式等 顺序方式是解释完一条指令再开始解释下一条顺序方式是解释完一条指令再开始解释下一条； 流水方式是把一个重复的过程分解为若干个子过流水方式是把一个重复的过程分解为若干个子过程，每个子过程可以与其它子过程同时进行，以此程，每个子过程可以与其它子过程同时进行，以此

17、提高单位时间内解释指令的数目提高单位时间内解释指令的数目； 重叠方式是一种简单的流水方式，它把指令分成重叠方式是一种简单的流水方式，它把指令分成2个子过程个子过程 每条指令只与下一条指令相重叠每条指令只与下一条指令相重叠。 重叠方式流水线重叠方式流水线当分析部件完成上一条指令的当分析部件完成上一条指令的“分析分析”后，就立即将之送入后，就立即将之送入执行部件，同时分析部件可以开始处理下一条指令。执行部件，同时分析部件可以开始处理下一条指令。虽然从执行一条指令的全过程来看，仍需要虽然从执行一条指令的全过程来看，仍需要2t的时间，但从的时间，但从机器的输出端来看，却是每隔一个机器的输出端来看，却是

18、每隔一个t就能给出一条指令的执就能给出一条指令的执行结果。行结果。 流水线结构图 流水线工作时空图流水线工作时空图 空间（段号） 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 16 时间（拍） (a) 顺序方式 空间（段号） 1 2 3 4 1 2 3 4 10 时间（拍） (b) 重叠方式 空间（段号） 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 7 时间（拍） t (c) 流水方式 图 3.2 CPU 工作时空图 5.2.4 5.2.4 流水线的特点流水线的特点流水过程由多个相联系的子过程组成，每个子过程称流水过程由多个相联系的子过程组成，每个子过程称

19、为流水线的级或段，段的数目称为流水线的深度。为流水线的级或段，段的数目称为流水线的深度。在流水线中处理的必须是连续任务，只有不断的提供在流水线中处理的必须是连续任务，只有不断的提供任务才能充分发挥流水线的效率。任务才能充分发挥流水线的效率。把一个任务分解为几个有联系的子任务，每个子任务把一个任务分解为几个有联系的子任务，每个子任务由一个专门的功能部件来实现。由一个专门的功能部件来实现。在流水线的每一个功能部件的后面都要有一个缓冲器在流水线的每一个功能部件的后面都要有一个缓冲器，用于保存本段的执行结果。，用于保存本段的执行结果。流水线需要有流水线需要有“装入时间装入时间”和和“排空时间排空时间”

20、。5.3 5.3 流水技术的分类流水技术的分类1）按各过程段用时是否全等划分）按各过程段用时是否全等划分 均匀流水线：各过程段用时全等均匀流水线：各过程段用时全等 非均匀流水线：各过程段用时不全等（如非均匀流水线：各过程段用时不全等（如上图）上图） ）时间匹配的均匀流水线。）时间匹配的均匀流水线。 ）时间不匹配的非均匀流水线。）时间不匹配的非均匀流水线。 1t2t32t4t2）按处理的数据类型）按处理的数据类型标量流水线：用于对标量数据进行流水处标量流水线：用于对标量数据进行流水处理。理。向量流水线：用于对向量数据进行流水处向量流水线：用于对向量数据进行流水处理。（向量很适合流水处理）理。（向

21、量很适合流水处理）3）按流水线的规模）按流水线的规模操作流水线：如将一条指令划分为多个过操作流水线：如将一条指令划分为多个过程段进行流水处理。规模最小程段进行流水处理。规模最小指令流水线：以指令为单位进行处理，用指令流水线：以指令为单位进行处理，用于多进程、多任务。规模较大于多进程、多任务。规模较大 宏流水线：以程序的逻辑功能段为单位宏流水线：以程序的逻辑功能段为单位进行流水处理。规模最大进行流水处理。规模最大4）按流水线具有功能的多少）按流水线具有功能的多少 单功能流水线：各过程段之间固定连接，单功能流水线：各过程段之间固定连接，不能重新构成其它流水线不能重新构成其它流水线固定流水线固定流水

22、线 多功能流水线分：多功能流水线分： 静态流水线：各过程段之间可重新连接，静态流水线：各过程段之间可重新连接，但不同时刻只能重构成一种不同的流水线。但不同时刻只能重构成一种不同的流水线。 动态流水线：各过程段之间可重新连接，动态流水线：各过程段之间可重新连接，不同时刻可重构成多种流水线。不同时刻可重构成多种流水线。 5）按部件在同一时刻送出支路数的多少来分。）按部件在同一时刻送出支路数的多少来分。一维一维流水线：在同一时刻，部件只能向流水线：在同一时刻，部件只能向一个地方传送结果。一个地方传送结果。 阵列流水线：在同一时刻，部件可同时阵列流水线：在同一时刻，部件可同时向多个地方传送结果。向多个

23、地方传送结果。5.4.5 “5.4.5 “瓶颈瓶颈”问题及其解决方法问题及其解决方法 瓶颈：瓶颈就是瓶颈：瓶颈就是titi最大的段，它使流水线最大的段，它使流水线“流流速速”减慢。减慢。S1S1S2S2S3S3S4S4tt3t3t tttt 方法方法1 1：再细分：再细分 将瓶颈设备再细分为下一级将瓶颈设备再细分为下一级流水线流水线S1S1S2aS2aS2bS2bS2cS2cS3S3S4S4tttttttttttt 方法方法2 2：并行设置：并行设置 将瓶颈设备重复设置多套。将瓶颈设备重复设置多套。衡量流水线的主要指标有吞吐率，加速比和效率。衡量流水线的主要指标有吞吐率，加速比和效率。5.4.

24、1 5.4.1 吞吐率吞吐率TPTP吞吐率（吞吐率（TP ThroughPut）指流水线在单位时间内执行的任务数，）指流水线在单位时间内执行的任务数，可以用输入任务数或输出任务数表示。可以用输入任务数或输出任务数表示。 其中其中k表示流水线划分的段数。表示流水线划分的段数。 当满足当满足 条件时，有条件时，有 。5.4 5.4 线性流水线性能分析线性流水线性能分析kTnTP ttitknTk) 1( 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 流水线产

25、生流水线产生n n个结果所需要的时间：个结果所需要的时间： 实际吞吐率实际吞吐率： 最大吞吐率：最大吞吐率： 最大吞吐率与实际吞吐率的关系：最大吞吐率与实际吞吐率的关系：（1 1）流水线各段的执行时间相等流水线各段的执行时间相等(1 )kTknt(1 )nT Pkntm a x1(1 )nnT PL imtknt m a x(1 )nT PT Pkn 实际吞吐率：实际吞吐率： 最大吞吐率：最大吞吐率： （2 2） 流水线各段的执行时间不等流水线各段的执行时间不等121(1) m ax(,)kikiT Ptntttn12m axm ax(,)1kT Pttt5.4.2 5.4.2 加速比（即吞吐

26、率之比，）加速比（即吞吐率之比，）koTTS kiiotnT1不使用流水线所用的时间与使用流水线所用的时间之比不使用流水线所用的时间与使用流水线所用的时间之比一般表示：一般表示：s=Ts=T0 0/T/TK K其中其中 实际加速比：实际加速比：最大加速比：最大加速比：(1)1kntknSkntkn m a x(1 )nknSL imkkn kiiotnT1段效率：，各段平均效率：其中 表示第i段设备量占整条流水线全部设备量的百分比当满足 条件（即等长、等权）时，有：5.4.3 5.4.3 效率（设备利用率）效率（设备利用率）kiiTtnEkiiiEE1)(kttii1和ikSTkTtTknEk

27、Ekikikoiki11)(1上式指出，S=Ek，就是说当效率达到100%时，流水方式（一个任务/t）吞吐率为顺序方式（一个任务/(kt)）的k倍。实际效率：实际效率：最大效率：最大效率：(1)1kntnEkkntkn max11nnELimkn瓶颈问题用两种方法改进后的效率瓶颈问题用两种方法改进后的效率和吞吐率和吞吐率静态双功能流水线的效率与吞吐率 教材P241非线性流水线的吞吐率和效率 教材P291 5.5 5.5 流水线中的相关流水线中的相关相关的定义：相关的定义： 流水线中的相关是指相邻或相近的指令因存在某种关联，流水线中的相关是指相邻或相近的指令因存在某种关联，后面的指令不能在原指定

28、的时钟周期开始执行。后面的指令不能在原指定的时钟周期开始执行。一般来说，流水线中的相关主要分为如下三种类型：一般来说，流水线中的相关主要分为如下三种类型：结构相关：当硬件资源满足不了指令重叠执行的要求，结构相关：当硬件资源满足不了指令重叠执行的要求，而发生资源冲突时，就发生了结构相关。而发生资源冲突时，就发生了结构相关。数据相关：当一条指令需要用到前面指令的执行结果，数据相关：当一条指令需要用到前面指令的执行结果，而这些指令均在流水线中重叠执行时，就可能引起数据而这些指令均在流水线中重叠执行时，就可能引起数据相关。相关。 3. 3. 控制相关：当流水线遇到分支指令和其它能够改变控制相关：当流水

29、线遇到分支指令和其它能够改变 PC PC 值的指令时，就会发生控制相关。值的指令时，就会发生控制相关。 一旦流水线中出现相关，必然会给指令在流水线中一旦流水线中出现相关，必然会给指令在流水线中的顺利执行带来许多问题，如果不能很好地解决的顺利执行带来许多问题，如果不能很好地解决相关问题，轻则影响流水线的性能，重则导致错相关问题，轻则影响流水线的性能，重则导致错误的执行结果。消除相关的基本方法是让流水线误的执行结果。消除相关的基本方法是让流水线暂停执行某些指令，而继续执行其它一些指令。暂停执行某些指令，而继续执行其它一些指令。 在后面的讨论中，我们约定：当一条指在后面的讨论中，我们约定：当一条指令

30、被暂停时，在该暂停指令之后发射的所有指令令被暂停时，在该暂停指令之后发射的所有指令都要被暂停，而在该暂停之前发射的指令则可继都要被暂停，而在该暂停之前发射的指令则可继续进行，在暂停期间，流水线不会取新的指令续进行，在暂停期间，流水线不会取新的指令。 5.5.1 5.5.1 结构相关结构相关如果某些指令组合在流水线中重叠执行时，产如果某些指令组合在流水线中重叠执行时，产生资源冲突，则称该流水线有结构相关。为了生资源冲突，则称该流水线有结构相关。为了能够在流水线中顺利执行指令的所有可能组合，能够在流水线中顺利执行指令的所有可能组合，而不发生结构相关，通常需要采用流水化功能而不发生结构相关，通常需要

31、采用流水化功能单元的方法或资源重复的方法。单元的方法或资源重复的方法。 许多流水线机器都是将数据和指令保存在同一存储许多流水线机器都是将数据和指令保存在同一存储器中。如果在某个时钟周期内，流水线既要完成器中。如果在某个时钟周期内，流水线既要完成某条指令对数据的存储器访问操作，又要完成取某条指令对数据的存储器访问操作，又要完成取指令的操作，那么将会发生存储器访问冲突问题指令的操作，那么将会发生存储器访问冲突问题 产生结构相关。为了解决这个问题，可以让流水产生结构相关。为了解决这个问题，可以让流水线完成前一条指令对数据的存储器访问时，暂停线完成前一条指令对数据的存储器访问时，暂停取后一条指令的操作

32、。该周期称为流水线的一个取后一条指令的操作。该周期称为流水线的一个暂停周期。暂停周期一般也称为流水线气泡，或暂停周期。暂停周期一般也称为流水线气泡，或简称为简称为“气泡气泡”。在流水线中插入暂停周期可以。在流水线中插入暂停周期可以消除这种结构相关。消除这种结构相关。 结构相关举例访存冲突结构相关举例访存冲突 为为消除结构相关插入流水气泡消除结构相关插入流水气泡 时空图来表示暂停情况时空图来表示暂停情况分析分析 为消除结构相关而引入的暂停将影响流水线为消除结构相关而引入的暂停将影响流水线的性能。为了避免结构相关，可以考虑采用资的性能。为了避免结构相关，可以考虑采用资源重复的方法。比如，在流水线机

33、器中设置相源重复的方法。比如，在流水线机器中设置相互独立的指令存储器和数据存储器；也可以将互独立的指令存储器和数据存储器；也可以将 Cache Cache 分割成指令分割成指令 Cache Cache 和数据和数据 CacheCache。 假设不考虑流水线其它因素对流水线性能的假设不考虑流水线其它因素对流水线性能的影响，显然如果流水线机器没有结构相关，那么影响，显然如果流水线机器没有结构相关，那么其其 CPI CPI 也较小。然而，为什么有时流水线设计者也较小。然而，为什么有时流水线设计者却允许结构相关的存在呢？主要有两个原因：一却允许结构相关的存在呢？主要有两个原因：一是为了减少硬件代价，二

34、是为了减少功能单元的是为了减少硬件代价，二是为了减少功能单元的延迟。如果为了避免结构相关而将流水线中的所延迟。如果为了避免结构相关而将流水线中的所有功能单元完全流水化，或者设置足够的硬件资有功能单元完全流水化，或者设置足够的硬件资源，那么所带来的硬件代价必定很大。源，那么所带来的硬件代价必定很大。 5.5.2 5.5.2 数据相关数据相关当指令在流水线中重叠执行时，流水线有可能改变指令当指令在流水线中重叠执行时，流水线有可能改变指令读读/写操作数的顺序，使得读写操作数的顺序，使得读/写操作顺序不同于它们非写操作顺序不同于它们非流水实现的顺序，这将导致数据相关。流水实现的顺序，这将导致数据相关。

35、 ADD R1，R2，R3SUBR4，R5，R1AND R6，R1，R7ORR8，R1，R9XORR10，R1， R11 ADD ADD指令后的所有指令都要用到指令后的所有指令都要用到ADDADD指指令的计算结果，令的计算结果，ADD ADD 指令在指令在 WB WB 段才将计段才将计算结果写入寄存器算结果写入寄存器 R1 R1 中，但是中，但是 SUB SUB 指令指令在其在其 ID ID 段就要从寄存器段就要从寄存器 R1 R1 中读取该计中读取该计算结果，这种情况就叫做数据相关。除非算结果，这种情况就叫做数据相关。除非有措施防止这一情况出现，否则有措施防止这一情况出现，否则 SUB SU

36、B 指令指令读到的是错误的值。所以，为了保证上述读到的是错误的值。所以，为了保证上述指令序列的正确执行，流水线只好暂停指令序列的正确执行，流水线只好暂停 ADD ADD 指令之后的所有指令，直到指令之后的所有指令，直到 ADD ADD 指令指令将计算结果写入寄存器将计算结果写入寄存器 R1 R1 之后，再启动之后，再启动 ADD ADD 指令之后的指令继续执行。指令之后的指令继续执行。 数据相关举例数据相关举例例子分析例子分析 从上图还可以看到，从上图还可以看到， AND AND 指令同样也将受到这种相关关指令同样也将受到这种相关关系的影响。系的影响。 ADD ADD 指令只有到第五个时钟周期

37、末尾才能结束对指令只有到第五个时钟周期末尾才能结束对寄存器寄存器 R1 R1 的写操作，所以的写操作，所以 AND AND 指令在第四个时钟周期从寄指令在第四个时钟周期从寄存器存器 R1 R1 中读出的值也是错误的。而中读出的值也是错误的。而 XOR XOR 指令则可以正常操指令则可以正常操作，因为它是在第六个时钟周期读寄存器作，因为它是在第六个时钟周期读寄存器 R1 R1 的内容。的内容。另外，利用流水线的一种简单技术，可以使流水线顺利另外，利用流水线的一种简单技术，可以使流水线顺利执行执行 OR OR 指令。这种技术就是：在流水线中，约定在时钟周指令。这种技术就是：在流水线中，约定在时钟周

38、期的后半部分进行寄存器文件的读操作，而在时钟周期的前期的后半部分进行寄存器文件的读操作，而在时钟周期的前半部分进行寄存器文件的写操作。在图中，我们将寄存器文半部分进行寄存器文件的写操作。在图中，我们将寄存器文件的边框适当地画成虚线来表示这种技术。件的边框适当地画成虚线来表示这种技术。通过定向技术减少数据相关带来的暂停通过定向技术减少数据相关带来的暂停数据相关问题可以采用一种称为定向（也称为旁数据相关问题可以采用一种称为定向（也称为旁路或短路）的简单技术来解决路或短路）的简单技术来解决 。定向技术的主要。定向技术的主要思想是：在某条指令（如图中的思想是：在某条指令（如图中的 ADD ADD 指令

39、）产生指令）产生一个计算结果之前，其它指令（如图中的一个计算结果之前，其它指令（如图中的 SUB SUB 和和 AND AND 指令）并不真正需要该计算结果，如果能够指令）并不真正需要该计算结果，如果能够将该计算结果从其产生的地方（寄存器文件将该计算结果从其产生的地方（寄存器文件 EX/MEMEX/MEM）直接送到其它指令需要它的地方（）直接送到其它指令需要它的地方（ALU ALU 的输入寄存器），那么就可以避免暂停的输入寄存器），那么就可以避免暂停. . 基于这种考虑，定向技术的要点可以归纳基于这种考虑，定向技术的要点可以归纳为：为： 寄存器文件寄存器文件 EX/MEM EX/MEM 中的中

40、的 ALU ALU 的运算结果总的运算结果总是回送到是回送到 ALU ALU 的输入寄存器；的输入寄存器；当定向硬件检测到前一个当定向硬件检测到前一个 ALU ALU 运算结果的写运算结果的写入寄存器就是当前入寄存器就是当前 ALU ALU 操作的源寄存器时，操作的源寄存器时，那么控制逻辑将前一个那么控制逻辑将前一个 ALU ALU 运算结果定向到运算结果定向到 ALU ALU 的输入端，后一个的输入端，后一个 ALU ALU 操作就不必从源操作就不必从源寄存器中读取操作数。寄存器中读取操作数。 流水线中的指令所需要的定向结果可能并流水线中的指令所需要的定向结果可能并不仅仅是前一条指令的计算结

41、果，而且还不仅仅是前一条指令的计算结果，而且还有可能是前面与其不相邻指令的计算结果有可能是前面与其不相邻指令的计算结果采用定向技术消除数据相关采用定向技术消除数据相关定向技术的推广定向技术的推广上述定向技术可以推广到更一般的情况，可以将上述定向技术可以推广到更一般的情况，可以将一个结果直接传送到所有需要它的功能单元。也一个结果直接传送到所有需要它的功能单元。也就是说，一个结果不仅可以从某一功能单元的输就是说，一个结果不仅可以从某一功能单元的输出定向到其自身的输入，而且还可以从某一功能出定向到其自身的输入，而且还可以从某一功能单元的输出定向到其它功能单元的输入单元的输出定向到其它功能单元的输入

42、。前面的一些数据相关的实例均是有关寄存器操作前面的一些数据相关的实例均是有关寄存器操作数的，但是数据相关也有可能发生在一对指令对数的，但是数据相关也有可能发生在一对指令对存储器同一单元进行读写的时候。不过，本章仅存储器同一单元进行读写的时候。不过，本章仅讨论有关寄存器的数据相关。讨论有关寄存器的数据相关。到数据存储器和到数据存储器和ALUALU的定向路径的定向路径数据相关分类数据相关分类根据指令对寄存器的读写顺序，可以将数据相关分为三根据指令对寄存器的读写顺序，可以将数据相关分为三类。习惯上，这些相关是根据流水线所必须保持的访问类。习惯上，这些相关是根据流水线所必须保持的访问顺序来命名的。考虑

43、流水线中的两条指令顺序来命名的。考虑流水线中的两条指令 i i 和和 j j ，且，且 i i 在在 j j 之前进入流水线，由此可能带来的数据相关有：之前进入流水线，由此可能带来的数据相关有： 写后读相关（写后读相关（Read After Write，RAW）：）：j 的执行要的执行要用到用到 i 的计算结果，当它们在流水线中重叠执行时，的计算结果，当它们在流水线中重叠执行时，j 可能在可能在 i 写入其计算结果之前就先行对保存该结果的寄写入其计算结果之前就先行对保存该结果的寄存器进行读操作，从而得到错误的值。这是最常见的存器进行读操作，从而得到错误的值。这是最常见的一种数据相关，采用定向技

44、术消除的数据相关就属于一种数据相关，采用定向技术消除的数据相关就属于这种类型。这种类型。 写后写相关（写后写相关（Write After WriteWrite After Write，WAWWAW）：）：j j 和和 i i 的目的寄存器相同，当它们在流水线中重叠执的目的寄存器相同，当它们在流水线中重叠执行时，行时，j j 可能在可能在 i i 写入其计算结果之前就先行对写入其计算结果之前就先行对该结果寄存器进行写操作，从而导致写入顺序错该结果寄存器进行写操作，从而导致写入顺序错误，在目的寄存器中留下的是误，在目的寄存器中留下的是 i i 写入的值，而不写入的值，而不是是 j j 写入的值。写

45、入的值。如果在流水线中不只一个段可以进行写操作，或如果在流水线中不只一个段可以进行写操作，或者当流水线暂停某条指令时，允许该指令之后的者当流水线暂停某条指令时，允许该指令之后的指令继续前进，就可能会产生这种类型的数据相指令继续前进，就可能会产生这种类型的数据相关。关。 读后写相关（读后写相关（Write After ReadWrite After Read，WARWAR）：）：j j 可可能在能在 i i 读取某个源寄存器的内容之前就先对该寄读取某个源寄存器的内容之前就先对该寄存器进行写操作，导致存器进行写操作，导致 i i 后来读取到的值是错误后来读取到的值是错误的。的。需要暂停的数据相关需

46、要暂停的数据相关前面我们讨论了如何利用定向技术消除由于数据相关带前面我们讨论了如何利用定向技术消除由于数据相关带来的暂停。但是，并不是所有数据相关带来的暂停都可来的暂停。但是，并不是所有数据相关带来的暂停都可以通过定向技术消除。以通过定向技术消除。对数据相关的编译器调度方法对数据相关的编译器调度方法流水线常常会遇到许多种类型的暂停。比如，采用典型的代码流水线常常会遇到许多种类型的暂停。比如，采用典型的代码生成方法对生成方法对A=BC这种常用的表达式进行处理，可以得到如图这种常用的表达式进行处理，可以得到如图所示的指令序列。从图中可以看出，在所示的指令序列。从图中可以看出，在 ADD 指令的流水

47、过程中指令的流水过程中必须插入一个暂停时钟周期，以保证变量必须插入一个暂停时钟周期，以保证变量C的读入值有效。既然的读入值有效。既然定向无法消除指令序列中所包含的这种暂停，那么能否让编译定向无法消除指令序列中所包含的这种暂停，那么能否让编译器在进行代码生成时就消除这些潜在的暂停呢？器在进行代码生成时就消除这些潜在的暂停呢？指令级调度指令级调度实际上，编译器的确可以通过重新组织代码顺序来消除实际上，编译器的确可以通过重新组织代码顺序来消除这种暂停。通常称这种重新组织代码顺序消除暂停的技这种暂停。通常称这种重新组织代码顺序消除暂停的技术为流水线调度（术为流水线调度（pipeline schedul

48、ingpipeline scheduling）或指令调度）或指令调度（instruction schedulinginstruction scheduling）。）。 5.5.3 5.5.3 控制相关控制相关在流水线上执行分支指令时，在流水线上执行分支指令时，PC 值有两种可能值有两种可能的变化情况。一种是的变化情况。一种是 PC 值发生改变（为分支转值发生改变（为分支转移的目标地址）；一种是移的目标地址）；一种是 PC 值保持正常。如果值保持正常。如果一条分支指令将一条分支指令将PC值改变为分支转移的目标地值改变为分支转移的目标地址，那么我们称分支转移成功；如果分支转移址，那么我们称分支转移

49、成功；如果分支转移条件不成立，条件不成立，PC 值保持正常，我们称分支转移值保持正常，我们称分支转移失败。失败。处理分支指令最简单的方法是：一旦在流水线中处理分支指令最简单的方法是：一旦在流水线中检测到某条指令是分支指令，就暂停执行该分支检测到某条指令是分支指令，就暂停执行该分支指令之后的所有指令，直到分支指令到达流水线指令之后的所有指令，直到分支指令到达流水线的的 MEM 段，确定了新的段，确定了新的 PC 值为止。我们当然值为止。我们当然不希望流水线还没有确定某条指令是分支指令之不希望流水线还没有确定某条指令是分支指令之前就暂停执行指令，所以对分支指令而言，当流前就暂停执行指令，所以对分支

50、指令而言，当流水线完成其译码操作（水线完成其译码操作（ID段）之后才会暂停执行段）之后才会暂停执行其后继指令。其后继指令。根据上述处理分支指令的方法，可以得到如根据上述处理分支指令的方法，可以得到如图所示流水线时空图图所示流水线时空图 。从图中可以看出，在流水。从图中可以看出，在流水线中插入了两个暂停周期，当分支指令在线中插入了两个暂停周期，当分支指令在 MEM 段确定新的段确定新的 PC 值后，流水线作废分支直接后继值后，流水线作废分支直接后继指令的指令的 IF 周期（相当于一个暂停周期），按照周期（相当于一个暂停周期），按照新的有效新的有效 PC 值取指令。值取指令。减少分支暂停时钟周期数

51、减少分支暂停时钟周期数减少流水线处理分支指令时的暂停时钟周期数有如下减少流水线处理分支指令时的暂停时钟周期数有如下两种途径：两种途径：在流水线中尽早判断出分支转移是否成功；在流水线中尽早判断出分支转移是否成功；尽早计算出分支转移成功时的尽早计算出分支转移成功时的 PC 值（即分支的目值（即分支的目标地址）。标地址）。 为了优化处理分支指令，在流水线中应该同时为了优化处理分支指令，在流水线中应该同时采用上述两条途径，缺一不可。即使知道分支转移采用上述两条途径，缺一不可。即使知道分支转移的目标地址，而不知道分支转移是否成功对减少暂的目标地址，而不知道分支转移是否成功对减少暂停是徒劳的；知道分支转移

52、是否成功，而不知道分停是徒劳的；知道分支转移是否成功，而不知道分支转移的目标地址，同样对降低分支损失毫无帮助。支转移的目标地址，同样对降低分支损失毫无帮助。下面让我们看看如何基于这些思想，从硬件上改进下面让我们看看如何基于这些思想，从硬件上改进流水线，达到降低分支损失的目的。流水线，达到降低分支损失的目的。在流水线中，分支指令通常需要测试分支条件寄在流水线中，分支指令通常需要测试分支条件寄存器的值是否为存器的值是否为0，所以可以把测试分支条件寄，所以可以把测试分支条件寄存器的操作移到存器的操作移到 ID 段完成，从而使得在段完成，从而使得在 ID 周期周期末就完成分支转移成功与否的检测。末就完

53、成分支转移成功与否的检测。另外，由于要尽早计算出两个另外，由于要尽早计算出两个 PC 值（分支值（分支转移成功和失败时的转移成功和失败时的 PC 值），也可以将计算分值），也可以将计算分支目标地址的操作移到支目标地址的操作移到 ID 段完成。为此，需要段完成。为此，需要在在 ID 段增设一个加法器（注意，为了避免结构段增设一个加法器（注意，为了避免结构相关，不能用相关，不能用EX段的段的 ALU 功能部件来计算分支功能部件来计算分支转移目标地址）。下图是对流水线进行上述改进转移目标地址）。下图是对流水线进行上述改进后的流水线数据通路。容易看出，基于上述改进后的流水线数据通路。容易看出，基于上述

54、改进后的流水线数据通路，处理分支指令只需要一个后的流水线数据通路，处理分支指令只需要一个时钟周期的暂停。时钟周期的暂停。减少分支暂停时钟周期数减少分支暂停时钟周期数降低流水线分支损失的方法有许多种。前面论降低流水线分支损失的方法有许多种。前面论述了改进流水线硬件减少流水线暂停周期的方述了改进流水线硬件减少流水线暂停周期的方法。这里主要从编译技术的角度，论述四种降法。这里主要从编译技术的角度，论述四种降低流水线分支损失的简单方法。首先需要说明低流水线分支损失的简单方法。首先需要说明的是，这些方法对分支转移成功与否进行的预的是，这些方法对分支转移成功与否进行的预测都是静态的，并在整个程序的执行过程

55、中保测都是静态的，并在整个程序的执行过程中保持这种预测结论，即：要么总是认为分支转移持这种预测结论，即：要么总是认为分支转移成功，要么总是认为分支转移失败。成功，要么总是认为分支转移失败。冻结（冻结（freezefreeze）或排空（）或排空（flushflush）流水线的方法）流水线的方法在流水线中，处理分支最简单的方法是冻结或在流水线中，处理分支最简单的方法是冻结或排空流水线，保持或清除流水线在分支指令之排空流水线，保持或清除流水线在分支指令之后读入的任何指令，直到知道分支指令的目标后读入的任何指令，直到知道分支指令的目标地址以及分支转移是否成功为止。这种方法优地址以及分支转移是否成功为止

56、。这种方法优点在于其对硬件和软件的要求都十分简单，我点在于其对硬件和软件的要求都十分简单，我们前面采用的就是这种方法。们前面采用的就是这种方法。预测分支失败的方法预测分支失败的方法 如果流水线采用预测分支失败的方法处理分支如果流水线采用预测分支失败的方法处理分支指令，那么当流水线译码到一条分支指令时，流水指令，那么当流水线译码到一条分支指令时，流水线继续取指令，并允许该分支指令后的指令继续在线继续取指令，并允许该分支指令后的指令继续在流水线中流动。当流水线确定分支转移成功与否以流水线中流动。当流水线确定分支转移成功与否以及分支的目标地址之后，如果分支转移成功，流水及分支的目标地址之后，如果分支

57、转移成功，流水线必须将在分支指令之后取出的所有指令转化为空线必须将在分支指令之后取出的所有指令转化为空操作，并在分支的目标地址处重新取出有效的指令；操作，并在分支的目标地址处重新取出有效的指令；如果分支转移失败，那么可以将分支指令看作是一如果分支转移失败，那么可以将分支指令看作是一条普通指令，流水线正常流动，无需将在分支指令条普通指令，流水线正常流动，无需将在分支指令之后取出的所有指令转化为空操作。之后取出的所有指令转化为空操作。预测分支成功的方法预测分支成功的方法另一种降低流水线分支损失的方法便是预测分另一种降低流水线分支损失的方法便是预测分支成功，一旦流水线译码到一条指令是分支指支成功，一

58、旦流水线译码到一条指令是分支指令，且完成了分支目标地址的计算，我们就假令，且完成了分支目标地址的计算，我们就假设分支转移成功，并开始在分支目标地址处取设分支转移成功，并开始在分支目标地址处取指令执行。指令执行。 在某些流水线中，特别是那些具有隐含在某些流水线中，特别是那些具有隐含设置条件码或分支条件更复杂指令的流水线机设置条件码或分支条件更复杂指令的流水线机器中，在确定分支转移成功与否之前，便可以器中，在确定分支转移成功与否之前，便可以知道分支的目标地址，这时采用这种方法便可知道分支的目标地址，这时采用这种方法便可以降低这些流水线的分支损失。以降低这些流水线的分支损失。 4.4.延迟分支（延迟

59、分支（delayed branchdelayed branch）方法）方法 为降低流水线分支损失而采用的第四种方法就是延迟分为降低流水线分支损失而采用的第四种方法就是延迟分支方法。其主要思想是从逻辑上支方法。其主要思想是从逻辑上“延长延长”分支指令的执行时分支指令的执行时间。延迟长度为间。延迟长度为 n n 的分支指令的执行顺序是：的分支指令的执行顺序是： 分支指令分支指令 顺序后继指令顺序后继指令1 1顺序后继指令顺序后继指令 n n如果分支成功，分支目标处指令如果分支成功，分支目标处指令 所有顺序后继指令都处于分支延迟槽（所有顺序后继指令都处于分支延迟槽（branch-branch-del

60、ay slotsdelay slots）中，无论分支成功与否，流水线都会执行这些）中，无论分支成功与否，流水线都会执行这些指令。指令。 基于延迟分支方法，无论分支成功与基于延迟分支方法，无论分支成功与否，其流水线时空图所描述的流水线的行否，其流水线时空图所描述的流水线的行为是类似的，流水线中均没有插入暂停周为是类似的，流水线中均没有插入暂停周期，从而极大地降低了流水线分支损失。期，从而极大地降低了流水线分支损失。从图中可以看出，实际上是处于分支延迟从图中可以看出，实际上是处于分支延迟槽中的指令槽中的指令“掩盖掩盖”了流水线原来所必需了流水线原来所必需插入的暂停周期。插入的暂停周期。5.6 5.