指令的动态调度PPT课件

《指令的动态调度PPT课件》由会员分享，可在线阅读，更多相关《指令的动态调度PPT课件（59页珍藏版）》请在金锄头文库上搜索。

1、1614.2指令的动态调度静静态态调调度度：在在出出现现数数据据相相关关时时，为为了了消消除除或或 者减少流水线空转，编译器确定并分离出程者减少流水线空转，编译器确定并分离出程 序序中中存存在在相相关关的的指指令令，然然后后进进行行指指令令调调度度， 并对代码进行优化。并对代码进行优化。动动态态调调度度：通通过过硬硬件件重重新新安安排排指指令令的的执执行行顺顺序序， 来来调调整整相相关关指指令令实实际际执执行行时时的的关关系系，减减少少处处理理 器空转。器空转。 以硬件复杂性的显著增加为代价。以硬件复杂性的显著增加为代价。 第四章 指令级并行2614.2.1 动态调度的原理 到目前为止我们所使

2、用流水线的最大的到目前为止我们所使用流水线的最大的局限性局限性: : 指令必须顺序流出指令必须顺序流出看下面一段代码：看下面一段代码： DIVD F0 , F2 , F4; S1S1 ADDD F10 , F0 , F8; S2S2：S2S2对对S1S1数据相关数据相关, , S2 S2被阻塞被阻塞 SUBD F12 , F8 ,F14; ;S3S3：S3S3与与S1S1、S2S2都没都没 有相关有相关, ,但也被阻塞但也被阻塞4.2 指令的动态调度361为了允许乱序执行，我们将基本流水线的译码阶段为了允许乱序执行，我们将基本流水线的译码阶段 再分为两个阶段：再分为两个阶段： (1)(1)流流

3、出出（IssueIssue，ISIS）：指指令令译译码码，检检查查是是否否存存 在结构阻塞。在结构阻塞。 (2)(2)读读操操作作数数（Read Read OperandsOperands，RORO）：当当没没有有数数 据相关引发的阻塞时就读操作数。据相关引发的阻塞时就读操作数。指令乱序结束带来的指令乱序结束带来的最大问题最大问题: : 异常处理比较复杂异常处理比较复杂 ( (精确异常处理、不精确异常处理精确异常处理、不精确异常处理) ) 4.2 指令的动态调度4614.2.2 动态调度算法之一：记分牌 例：例：数据先读后写（数据先读后写（WARWAR）相关引起的阻塞）相关引起的阻塞 代码序列

4、：代码序列： DIVDF0 , F2 , F4 ADDDF10 , F0 , F8 SUBDF8 , F8 , F14 指令乱序执行时就会出现指令乱序执行时就会出现先读后写相关先读后写相关。 记分牌技术的目标：记分牌技术的目标： 在资源充足时，尽可能早地执行没有数据阻在资源充足时，尽可能早地执行没有数据阻 塞的指令，达到每个时钟周期执行一条指令。塞的指令，达到每个时钟周期执行一条指令。 4.2 指令的动态调度561 要要发发挥挥指指令令乱乱序序执执行行的的好好处处，必必须须有有多多条条指指令令 同同时时处处于于执执行行阶阶段段，这这就就要要求求有有多多个个功功能能部部件件 或功能部件流水化或者

5、两者兼有或功能部件流水化或者两者兼有。 假设：处理器采用多个功能部件。假设：处理器采用多个功能部件。 CDC 6600CDC 6600具有具有1616个功能部件：个功能部件： 4 4个个浮点部件，浮点部件， 5 5个个存储器访问部件存储器访问部件 7 7个个整数操作部件整数操作部件 在在DLXDLX中，假设有中，假设有2 2个个乘法器、乘法器、1 1个个加法器、加法器、1 1 个个除法部件和除法部件和1 1个个整数部件。整数部件。4.2 指令的动态调度DLXDLX处理器的基本结构。处理器的基本结构。 图图4.1 4.1 具有记分牌的具有记分牌的DLXDLX处理器基本结构处理器基本结构 761

6、记分牌电路负责记录资源的使用，并负责相记分牌电路负责记录资源的使用，并负责相关检测，控制指令的流出和执行。关检测，控制指令的流出和执行。 四段四段： (1) (1) 流出（流出（IssueIssue，记为，记为ISIS） 如果本指令所需的功能部件有空闲，并如果本指令所需的功能部件有空闲，并 且其它正在执行的指令使用的目的寄存器与且其它正在执行的指令使用的目的寄存器与 本指令的不同，记分牌就向功能部件流出本本指令的不同，记分牌就向功能部件流出本 指令，并修改记分牌内部的数据记录。指令，并修改记分牌内部的数据记录。 解决了指令间存在的解决了指令间存在的结构相关或写后写相关结构相关或写后写相关。 4

7、.2 指令的动态调度861(2) (2) 读操作数（读操作数（Read OperandRead Operand，记为，记为RORO）。）。 记分牌需要监测源操作数寄存器中数据的记分牌需要监测源操作数寄存器中数据的 有效性，如果前面已流出的还在运行的指令不有效性，如果前面已流出的还在运行的指令不 对本指令的源操作数寄存器进行写操作，或者对本指令的源操作数寄存器进行写操作，或者 一个正在工作的功能部件已经完成了对这个寄一个正在工作的功能部件已经完成了对这个寄 存器的写操作，那么此操作数有效。当操作数存器的写操作，那么此操作数有效。当操作数 有效后，记分牌将启动本指令的功能部件读操有效后，记分牌将启

8、动本指令的功能部件读操 作数并开始执行。作数并开始执行。 解决了数据的解决了数据的先写后读（先写后读（RAWRAW）相关）相关。 通过以上步骤，记分牌动态解决了结构相通过以上步骤，记分牌动态解决了结构相 和数据相关引发的阻塞，指令可能乱序流出。和数据相关引发的阻塞，指令可能乱序流出。 4.2 指令的动态调度961(3) (3) 执行（执行（ExecutionExecution，记为，记为EXEX）。）。(4) (4) 写结果（写结果（Write ResultWrite Result，记为，记为WRWR）。）。 记分牌知道指令执行完毕后，如果目标记分牌知道指令执行完毕后，如果目标 寄存器空闲，就

9、将结果写入到目标寄存器中，寄存器空闲，就将结果写入到目标寄存器中， 然后释放本指令使用的所有资源。然后释放本指令使用的所有资源。 检测先读后写（检测先读后写（WARWAR）相关相关 在出现以下的情况时，就不允许指令写结果在出现以下的情况时，就不允许指令写结果: : 前面的某条指令（按顺序流出）还没有读取操作数；前面的某条指令（按顺序流出）还没有读取操作数； 其中某个源操作数寄存器与本指令的目的寄存器相同。其中某个源操作数寄存器与本指令的目的寄存器相同。4.2 指令的动态调度1061 存在一个问题存在一个问题: :就是功能部件到寄存器文件的就是功能部件到寄存器文件的数据总线宽度是有限的，当流水线

10、中进入读操作数据总线宽度是有限的，当流水线中进入读操作数段（数段（RORO）和写结果段（和写结果段（WBWB）的功能部件总数超的功能部件总数超过可用总线的数目，这会导致过可用总线的数目，这会导致结构阻塞结构阻塞。 3. 3. 记分牌需要纪录的信息分为三部分：记分牌需要纪录的信息分为三部分： (1) (1) 指令状态表指令状态表 记录正在执行的各条指令已经进入记记录正在执行的各条指令已经进入记 分牌分牌DLXDLX流水线四段中的哪一段。流水线四段中的哪一段。4.2 指令的动态调度1161(2)(2) 功能部件状态表功能部件状态表 纪录各个功能部件的状态。每个功能部件纪录各个功能部件的状态。每个功

11、能部件 在状态表中都由以下在状态表中都由以下九个域九个域来纪录：来纪录： BusyBusy： 指示功能部件是否在工作指示功能部件是否在工作 OpOp： 功能部件当前执行的操作功能部件当前执行的操作 FiFi： 目的寄存器编号目的寄存器编号 FjFj，fkfk：源寄存器编号源寄存器编号 QjQj，QkQk：向向RjRj，RkRk中写结果的功能部件中写结果的功能部件 RjRj，RkRk：表示表示FjFj，FkFk是否就绪，是否就绪， 是否已经被使用是否已经被使用4.2 指令的动态调度1261(3) (3) 结果寄存器状态表结果寄存器状态表 每个寄存器在表中有一个域，用于纪录写每个寄存器在表中有一个

12、域，用于纪录写 入本寄存器的功能部件（编号）。如果当前正入本寄存器的功能部件（编号）。如果当前正 在运行的功能部件没有需要写入本寄存器的，在运行的功能部件没有需要写入本寄存器的， 则相应域置为空。则相应域置为空。4. 4. DLXDLX记分牌所要维护的数据结构记分牌所要维护的数据结构 给出下列代码运行过程中记分牌保存的信息给出下列代码运行过程中记分牌保存的信息. . 4.2 指令的动态调度1361LD F6 , 34(R2)LD F2 , 45(R3)MULTDF0 , F2 , F4SUBD F8 , F6 , F2DIVD F10 , F0 , F6ADDDF6 , F8 , F24.2

13、指令的动态调度1461指 令 指令状态表 IS RO EX WR LD F6 , 34(R2) LD F2 , 45(R3) MULTDF0 , F2 , F4 SUBDF8 , F6 , F2 DIVDF10 , F0 , F6 ADDDF6 , F8 , F2 图图4.2 DLX4.2 DLX记分牌信息组成和记录的信息记分牌信息组成和记录的信息 4.2 指令的动态调度部件名称 功能部件状态表 Busy Op Fi Fj Fk Qj Qk Rj Rk整数 yes LD F2 R3 no乘法1 yes MULTD F0 F2 F4 整数 no yes乘法2 no加法 yes SUBD F8 F

14、6 F2 整数 yes no除法 yes DIVD F10 F0 F6 乘法1 no yes 结果寄存器状态表 F0 F2 F4 F6 F8 F10 F30部件名称 乘法1 整数 加法 除法1661 假设浮点流水线中执行的延迟如下：假设浮点流水线中执行的延迟如下： 加法需加法需2 2个个时钟周期时钟周期 乘法需乘法需1010个个时钟周期时钟周期 除法需除法需4040个个时钟周期时钟周期 代代码码段段和和记记分分牌牌信信息息的的起起始始点点状状态态。分分别别给给出出MULTDMULTD和和DIVDDIVD准备写结果之前的记分牌状态。准备写结果之前的记分牌状态。 解：解： 在分析记分牌状态之前，首

15、先需要分析指令之在分析记分牌状态之前，首先需要分析指令之间存在的相关性，因为相关性会影响指令进入记分间存在的相关性，因为相关性会影响指令进入记分牌牌DLXDLX流水线的相应段。流水线的相应段。 4.2 指令的动态调度1761(1) (1) 第二个第二个LDLD指令到指令到MULDMULD和和SUBDSUBD、MULTDMULTD到到DIVDDIVD 之间以及之间以及SUBDSUBD到到ADDDADDD之间存在着先写后读相关；之间存在着先写后读相关；(2) (2) DIVDDIVD和和ADDDADDD之间存在着先读后写相关；之间存在着先读后写相关；(3) (3) ADDDADDD和和SUBDSU

16、BD指令关于浮点加法部件还存在着结指令关于浮点加法部件还存在着结 构相关。构相关。 和分别给出了和分别给出了MULTDMULTD指令和指令和DIVDDIVD 指令将要写结果时记分牌的状态。指令将要写结果时记分牌的状态。 4.2 指令的动态调度1861指 令 指令状态表 IS RO EX WR LD F6 , 34(R2) LD F2 , 45(R3) MULTDF0 , F2 , F4 SUBDF8 , F6 , F2 DIVDF10 , F0 , F6 ADDDF6 , F8 , F2 图图4.3 4.3 程序段执行到程序段执行到MULTDMULTD将要写结果时记分牌的状态将要写结果时记分牌

17、的状态 4.2 指令的动态调度部件名称 功能部件状态表 Busy Op Fi Fj Fk Qj Qk Rj Rk整数 no 乘法1 yes MULTD F0 F2 F4 no no乘法2 no加法 yes ADDD F6 F8 F2 no no除法 yes DIVD F10 F0 F6 乘法1 no yes 结果寄存器状态表 F0 F2 F4 F6 F8 F10 F30部件名称 乘法1 加法 除法2061指 令 指令状态表 IS RO EX WRLD F6 , 34(R2) LD F2 , 45(R3) MULTD F0 , F2 , F4 SUBD F8 , F6 , F2 DIVD F10

18、 , F0 , F6 ADDD F6 , F8 , F2 图图4.4 4.4 程程序段执行到序段执行到DIVDDIVD将要写结果时记分牌的状态将要写结果时记分牌的状态 4.2 指令的动态调度部件名称 功能部件状态表 Busy Op Fi Fj Fk Qj Qk Rj Rk整数 no 乘法1 no乘法2 no加法 no除法 yes DIVD F10 F0 F6 no no 结果寄存器状态表 F0 F2 F4 F6 F8 F10 F30部件名称 除法22615.5.分析记分牌是如何控制指令执行的。分析记分牌是如何控制指令执行的。 操作在记分牌流水线中前进时，记分牌必须操作在记分牌流水线中前进时，记

19、分牌必须 记录与操作有关的信息，如寄存器号等。记录与操作有关的信息，如寄存器号等。 约定：约定： FjFj（FUFU）S1 S1 ：将将寄寄存存器器S1S1的的名名字字送送入入FjFj（FUFU） FU FU ： 指令使用的功能部件指令使用的功能部件 D D ： 目的寄存器的名字目的寄存器的名字 S1S1和和S2S2： 源操作数寄存器的名字，源操作数寄存器的名字， OpOp： 进行的操作进行的操作 FjFj（FUFU）：）： 功能部件功能部件FUFU的的FjFj域域 resultresult（D D）：）：结果寄存器状态表中对应于寄存器结果寄存器状态表中对应于寄存器D D的内容，为产生寄存器的

20、内容，为产生寄存器D D中结果的功能部件名。中结果的功能部件名。 4.2 指令的动态调度2361 流出流出（ISIS） (1) (1) 进入条件进入条件 not Busy(FU) and not result(D)not Busy(FU) and not result(D)； / /判断结构阻塞和写后写判断结构阻塞和写后写 (2) (2) 计分牌记录内容计分牌记录内容 Busy(FU)yes;Busy(FU)yes; OP(FU)Op OP(FU)Op； Fi Fi(FU)D(FU)D； Fj Fj(FU)S1(FU)S1； FkFk(FU)S2(FU)S2； 4.2 指令的动态调度2461

21、Qjresult(S1)Qjresult(S1)；/处理处理S1S1的的FUFU Qkresult(S2)Qkresult(S2)；/处理处理S2S2的的FUFU Rjnot QjRjnot Qj； /Rj /Rj是否可用？是否可用？ Rknot QkRknot Qk； /Rk /Rk是否可用？是否可用？ result(D)FUresult(D)FU； /D /D被被FUFU用作目用作目的寄存器的寄存器读操作数（读操作数（RORO） (1) (1)进入条件进入条件 RjRjRkRk; ; /解决先写后读，两个源操作数须同时就绪解决先写后读，两个源操作数须同时就绪 4.2 指令的动态调度2561

22、 (2) (2)计分牌记录内容计分牌记录内容 RjnoRjno；/已经读走了就绪的数据已经读走了就绪的数据RjRj RknoRkno；/已经读走了就绪的数据已经读走了就绪的数据RkRk Qj0Qj0；/不再等待其它不再等待其它FUFU的计算结果的计算结果 Qk0Qk0； 执行（执行（EXEX） (1) (1)结束条件结束条件 功能部件操作结束功能部件操作结束4.2 指令的动态调度2661写结果（写结果（WRWR） (1) (1)进入条件进入条件 f(f(FjFj(f)(f) FiFi(FU) or(FU) or Rj Rj(f)=no)(f)=no) and ( and (FkFk(f)(f)

23、 FiFi(FU) or(FU) or Rk Rk(f)=no);(f)=no); / /检查是否存在先读后写检查是否存在先读后写 (2) (2)计分牌记录内容计分牌记录内容 f(iff(if Qj Qj(f)=FU then(f)=FU then Rj Rj(f)yes)(f)yes)； / /有等结果的指令，则数据可用有等结果的指令，则数据可用 f(iff(if Qk Qk(f)=FU then(f)=FU then Rk Rk(f)yes)(f)yes)； result(result(FiFi(FU)0(FU)0； / /没有没有FUFU使用寄存器使用寄存器FiFi为目的寄存器为目的寄存

24、器 busy(FU)=nobusy(FU)=no/释放释放FUFU4.2 指令的动态调度27616. 6. 记分牌的性能受限于以下几个方面：记分牌的性能受限于以下几个方面： (1) (1) 程序指令中可开发的并行性，即是否存在程序指令中可开发的并行性，即是否存在 可以并行执行的不相关的指令。可以并行执行的不相关的指令。 (2) (2) 记分牌容量。记分牌的容量决定了流水线记分牌容量。记分牌的容量决定了流水线 能在多大范围内寻找不相关指令。能在多大范围内寻找不相关指令。 流水线中可以同时容纳的指令数量又流水线中可以同时容纳的指令数量又 称为称为指令窗口指令窗口。 (3) (3) 功能部件的数目和

25、种类。功能部件的总数功能部件的数目和种类。功能部件的总数 决定了结构冲突的严重程度。决定了结构冲突的严重程度。 (4) (4) 反相关和输出相关。引起计分牌中先读后反相关和输出相关。引起计分牌中先读后 写和写后写阻塞。写和写后写阻塞。4.2 指令的动态调度28614.2.3 动态调度算法之二：Tomasulo算法 TomasuloTomasulo算法将记分牌的关键部分和寄存器换名算法将记分牌的关键部分和寄存器换名 技术结合在一起。技术结合在一起。 基基本本核核心心：通通过过寄寄存存器器换换名名来来消消除除写写后后写写和和先先读读 后写相关而可能引发的流水线阻塞。后写相关而可能引发的流水线阻塞。

26、 下面的讨论是基于下面的讨论是基于DLXDLX的浮点流水线功能部件。的浮点流水线功能部件。 TomasuloTomasulo算算法法中中，寄寄存存器器换换名名是是通通过过保保留留站站来来实实 现现，它它保保存存等等待待流流出出和和正正在在流流出出指指令令所所需需要要的的操操 作数。作数。 TomasuloTomasulo算法的基本思想算法的基本思想4.2 指令的动态调度2961 只只要要操操作作数数有有效效，就就将将其其取取到到保保留留站站，避避免免指令流出时才到寄存器中取数据。指令流出时才到寄存器中取数据。指指令令的的执执行行结结果果直直接接送送到到等等待待数数据据的的其其它它保保留站中去。

27、留站中去。一一条条指指令令流流出出时时，存存放放操操作作数数的的寄寄存存器器名名被被换成为对应于该寄存器保留站的名称。换成为对应于该寄存器保留站的名称。 除了寄存器换名技术，除了寄存器换名技术，TomasuloTomasulo算法和记分牌在算法和记分牌在 结构上还有两处显著的不同：结构上还有两处显著的不同： 4.2 指令的动态调度3061 冲突检测和指令执行控制机制分开。冲突检测和指令执行控制机制分开。 计算的结果通过相关专用通路直接从功能部件计算的结果通过相关专用通路直接从功能部件 进入对应的保留站进行缓冲，而不一定是写到进入对应的保留站进行缓冲，而不一定是写到 寄存器。寄存器。 （相关专用

28、通路通过一条数据总线来实现）（相关专用通路通过一条数据总线来实现） 4.2 指令的动态调度TomasuloTomasulo算法的算法的DLXDLX浮点部件的基本结构浮点部件的基本结构 3261 保留站保留站中保存已流出并等待到本功能部件执行的中保存已流出并等待到本功能部件执行的 操作（指令）；还保存指令执行所需的控制信息。操作（指令）；还保存指令执行所需的控制信息。 如如果果该该操操作作的的源源操操作作数数在在寄寄存存器器中中已已经经就就绪绪，刚将该操作数取来，保存到保留站中；刚将该操作数取来，保存到保留站中；如如果果操操作作数数还还没没有有计计算算出出来来，则则保保留留站站中中记记录录这这个

29、个操操作作数数将将由由谁谁计计算算出出来来，即即指指明明它它由由哪个功能部件产生。哪个功能部件产生。 取取缓缓冲冲和和存存缓缓冲冲保保存存的的是是读读/ /写写存存储储器器的的数数据据或或 地址。地址。4.2 指令的动态调度3361浮浮点点寄寄存存器器通通过过一一对对操操作作数数总总线线连连到到功功能能部部件件，通通过过其其中中一一条条总总线线连连到到公公共共数数据据总总线线，再再送送到到存缓冲。存缓冲。功功能能部部件件的的计计算算结结果果和和从从存存储储器器读读取取的的数数据据都都送送到到公公用用数数据据总总线线上上，除除了了取取缓缓冲冲的的输输入入和和存存缓缓冲冲的输出以外，所有部分均与公

30、用数据总线相连。的输出以外，所有部分均与公用数据总线相连。两个运算功能部件两个运算功能部件 浮点乘法器完成乘法和除法操作浮点乘法器完成乘法和除法操作 浮点加法器完成加法和减法操作浮点加法器完成加法和减法操作4.2 指令的动态调度3461 使用使用TomasuloTomasulo算法的流水线需三段：算法的流水线需三段： (1) (1) 流出（流出（IssueIssue）：从浮点操作队列中取一条指令。）：从浮点操作队列中取一条指令。 (2) (2) 执行（执行（ExecuteExecute） (3) (3) 写结果（写结果（Write ResultWrite Result） 3.3.这些步骤和记分

31、牌基本上类似，但有以下以下几点这些步骤和记分牌基本上类似，但有以下以下几点 不同：不同： (1)(1)无需任何操作来检查数据无需任何操作来检查数据写后写写后写和和先读后写先读后写相关相关 的过程，在指令流出过程中操作数寄存器换名已的过程，在指令流出过程中操作数寄存器换名已 将其消除。将其消除。 4.2 指令的动态调度3561(2)(2)通通过过公公共共数数据据总总线线来来广广播播结结果果，将将结结果果送送到到 等待此结果作为操作数的保留站，目标寄存器也等待此结果作为操作数的保留站，目标寄存器也 相相当当于于一一个个需需要要结结果果的的保保留留站站，而而不不是是将将结结果果 写回到寄存器中。写回

32、到寄存器中。(3)(3)存储器存和取都作为基本的功能部件。存储器存和取都作为基本的功能部件。(4)(4)由于保留站技术能够有效地解决先写后读，而由于保留站技术能够有效地解决先写后读，而 无需特殊处理，因此，记分牌流水线中用于完无需特殊处理，因此，记分牌流水线中用于完 成判断先写后读的成判断先写后读的“取操作数取操作数”段也被消掉。段也被消掉。 4.2 指令的动态调度36614. 4. 定义有关的术语和数据结构定义有关的术语和数据结构 标志（标志（tagstags） 指缓冲或产生结果的保留站（功能部件）。指缓冲或产生结果的保留站（功能部件）。 每个保留站有以下每个保留站有以下6 6个个域：域：

33、OpOp：对源操作数对源操作数S1S1和和S2S2所进行的操作。所进行的操作。 QjQj，QkQk：产生结果的保留站号。等于产生结果的保留站号。等于0 0表示表示 操作数操作数在在VjVj和和VkVk中或不需要操作数。中或不需要操作数。 VjVj，VkVk：两个源操作数的值。操作数项中，两个源操作数的值。操作数项中，V V或或 Q Q域最多只有一个有效。域最多只有一个有效。 BusyBusy：标示本保留站和相应的功能部件是否空标示本保留站和相应的功能部件是否空 闲。闲。 4.2 指令的动态调度3761 每个寄存器和存缓冲有每个寄存器和存缓冲有1 1个个QiQi域：结果要存入本寄存域：结果要存入

34、本寄存 器或存缓冲的保留站号。器或存缓冲的保留站号。 如果如果QiQi空，表示当前没有指令要将结果写入此空，表示当前没有指令要将结果写入此 寄存器或存缓冲。寄存器或存缓冲。 当寄存器空闲时，当寄存器空闲时，QiQi域空。域空。 存缓冲和取缓冲还各有存缓冲和取缓冲还各有1 1个个BusyBusy域和域和1 1个个AddressAddress域域 BusyBusy：标示缓冲是否空闲。标示缓冲是否空闲。 A A：地址域，用于记录存或取的存储器地址。地址域，用于记录存或取的存储器地址。 存缓冲还有存缓冲还有1 1个个V V域：保存要存入存储器的数据。域：保存要存入存储器的数据。 4.2 指令的动态调度

35、38615. 5. 对于下列代码，保留站的信息：对于下列代码，保留站的信息： LD F6 , 34(R2)LD F2 , 45(R3)MULTDF0 , F2 , F4SUBD F8 , F2 , F6DIVD F10 , F0 , F6ADDDF6 , F8 , F24.2 指令的动态调度3961图图 给出的是采用给出的是采用TomasuloTomasulo算法算法时保留站、存缓冲、时保留站、存缓冲、 取缓冲和寄存器的标志等信息。取缓冲和寄存器的标志等信息。 指 令 指令状态表 流出 执行 写结果 LD F6 , 34(R2) LD F2 , 45(R3) MULTDF0 , F2 , F4

36、 SUBD F8 , F6 , F2 DIVDF10 , F0 , F6 ADDD F6 , F8 , F2 4.2 指令的动态调度名称 保留站 Load1Load2Add1Add2Add3Mult1Mult2Busy no yes yes yes no yes yesOp LD SUBD ADDD MULTD DIVDVj Vk MEM34+REGSR2 REGF4 MEM34+REGSR2Qj Load2 Add1 Load2 Mult1Qk Load2A 45+RegsR3 寄存器状态表 F0 F2 F4 F6 F8 F10 F30 Qi Mult1 Load2 Add2 Add1 Mu

37、lt2 域41616.6.TomasuloTomasulo算法相对于记分牌技术主要的算法相对于记分牌技术主要的优点优点： (1) (1)具有分布的阻塞检测机制；具有分布的阻塞检测机制； (2)(2)消消除除了了数数据据的的写写后后写写和和先先读读后后写写相相关关导导致致的的 阻塞。阻塞。 假设浮点部件的延迟为：假设浮点部件的延迟为： 加法加法2 2个个时钟周期，时钟周期， 乘法乘法1010个个时钟周期，时钟周期， 除法除法4040个个时钟周期。时钟周期。 执执 行行 的的 代代 码码 同同 上上 ， 给给 出出 MULTDMULTD准准 备备 写写 结结 果时的状态表的信息。果时的状态表的信息

38、。 解解 结果如图结果如图4.74.7所示。所示。 4.2 指令的动态调度4261指 令 指令状态表 流出 执行 写结果LD F6 , 34(R2) LD F2 , 45(R3) MULTD F0 , F2 , F4 SUBD F8 , F6 , F2 DIVD F10 , F0 , F6 ADDD F6 , F8 , F2 4.2 指令的动态调度名称 保留站 Load1Load2Add1Add2Add3Mult1Mult2Busy no yes yes yes no yes yesOp MultD DIVD VjMEM45+REGSR3 Vk REGF4 MEM34+REGSR2Qj Mul

39、t1Qk A 寄存器状态表 F0 F2 F4 F6 F8 F10 F30 Qi Mult1 Mult2 域44617. 7. TomasuloTomasulo算法中指令执行的主要条件、步骤和记录算法中指令执行的主要条件、步骤和记录 其中：其中： rdrd：目的寄存器目的寄存器 rsrs和和rtrt：操作数寄存器号操作数寄存器号 immimm：符号扩展的立即数符号扩展的立即数 r r：分配给相应指令的保留站或者缓冲分配给相应指令的保留站或者缓冲 RSRS：保留站数据结构，由保留站或取缓冲返保留站数据结构，由保留站或取缓冲返 回的值为回的值为resultresult。 RegisterStatRe

40、gisterStat：寄存器状态的数据结构寄存器状态的数据结构 （寄存器文件用（寄存器文件用Regs Regs 表示）表示）4.2 指令的动态调度4561 指令流出（指令流出（IssueIssue） (1) (1) 进入条件进入条件 对于浮点操作：有空闲保留站对于浮点操作：有空闲保留站r r 对于取对于取/ /存操作：有空闲缓冲存操作：有空闲缓冲r r(2) (2) 记录内容记录内容 对于浮点操作：对于浮点操作： if (RegisterStatrs.Qi if (RegisterStatrs.Qi 0) 0)/第一操作数第一操作数 RSr.Qj RSr.Qj RegisterStatrs.Q

41、i RegisterStatrs.Qi / /操作数寄存器操作数寄存器rsrs未就绪，进行寄存器换名未就绪，进行寄存器换名 else else RSr.Vj RSr.Vj Regrs; Regrs; / /把寄存器把寄存器rsrs中的操作数取到保留站中的操作数取到保留站 RSr.Qj RSr.Qj 0 0 ; ;/数据数据VjVj有效有效 4.2 指令的动态调度4661if (RegisterStatrt.Qi if (RegisterStatrt.Qi 0) 0) /第二操作数第二操作数 RSr.Qj RSr.Qj RegisterStatrt.Qi RegisterStatrt.Qi /

42、/操作数寄存器操作数寄存器rtrt未就绪，进行寄存器换名未就绪，进行寄存器换名elseelse RSr.Vk RSr.Vk Regrt; Regrt; / /把寄存器把寄存器rsrs中的操作数取到保留站中的操作数取到保留站 RSr.Qk RSr.Qk 0 0 ; ; / /数据数据VkVk有效有效RSr.Busy RSr.Busy yes yes；/本保留站忙本保留站忙RSr.Op RSr.Op Op Op；/设置本保留站的操作类型设置本保留站的操作类型 RegisterStatrd.Qi RegisterStatrd.Qi r r； / /寄存器寄存器rdrd是本指令的目标寄存器是本指令的目

43、标寄存器 4.2 指令的动态调度4761 对于存对于存/ /取操作：取操作： if (RegisterStatrs.Qi if (RegisterStatrs.Qi 0) 0) RSr.Qj RSr.Qj RegisterStatrs.Qi RegisterStatrs.Qi / /操作数寄存器操作数寄存器rsrs未就绪，进行寄存器换名未就绪，进行寄存器换名elseelse RSr.Vj RSr.Vj Regrs; Regrs; / /把寄存器把寄存器rsrs中的操作数取到保留站中的操作数取到保留站 RSr.Qj RSr.Qj 0 0 ; ; / /数据数据VjVj有效有效RSr.Busy R

44、Sr.Busy yes yes； /本保留站忙本保留站忙RSr.A RSr.A Imm Imm； / /设置本保留站的操作类型设置本保留站的操作类型4.2 指令的动态调度4861 对于取操作：对于取操作： RegisterStatrd.Qi RegisterStatrd.Qi r r； / /寄存器寄存器rdrd是本指令的目标寄存器是本指令的目标寄存器 对于存操作：对于存操作： if (RegisterStatrt.Qi if (RegisterStatrt.Qi 0) 0) RSr.Qk RSr.Qk RegisterStatrt.Qi RegisterStatrt.Qi / /操作数寄存器

45、操作数寄存器rtrt未就绪，进行寄存器换名未就绪，进行寄存器换名 else else RSr.Vk RSr.Vk Regrt; Regrt; / /把寄存器把寄存器rtrt中的操作数取到存缓冲中的操作数取到存缓冲 RSr.Qk RSr.Qk 0 0 ; ;/数据数据VkVk有效有效4.2 指令的动态调度4961 执行（执行（ExecutionExecution） (1)(1) 进入条件进入条件 对于浮点操作：对于浮点操作： (RSr.Qj = 0) and (RSr.Qk = 0);(RSr.Qj = 0) and (RSr.Qk = 0); / /两个源操作数就绪两个源操作数就绪 对于取对于

46、取/ /存操作第存操作第1 1步：步： (RSr.Qj = 0) and (r(RSr.Qj = 0) and (r到达取到达取/ /存缓冲队列的头部存缓冲队列的头部) ) 对于取操作第对于取操作第2 2步：步： 取操作第取操作第1 1步执行结束步执行结束4.2 指令的动态调度5061（2 2）记录内容）记录内容 对于浮点操作：对于浮点操作：产生计算结果产生计算结果 对于取对于取/ /存操作第存操作第1 1步：步： RSr.A RSr.A RSr.Vj + RSr.A; RSr.Vj + RSr.A; / /计算有效地址计算有效地址 对于取操作第对于取操作第2 2步：步： 读取数据读取数据Me

47、mRSr.A;MemRSr.A; / /从存储器中读取数据从存储器中读取数据4.2 指令的动态调度5161 写结果（写结果（Write ResultWrite Result） （1 1）进入条件）进入条件 对于浮点操作或取操作：对于浮点操作或取操作： 保保 留留 站站 r r执执 行行 结结 束束 ， 且且 公公 共共 数数 据据 总总 线线 （CDBCDB）可用（空闲）可用（空闲） 对于存操作：对于存操作： 保留站保留站r r执行结束，且执行结束，且RSr.Rk = 0RSr.Rk = 0 / /存的数据已经就绪存的数据已经就绪 （2 2）记录内容）记录内容 对于浮点操作或取操作：对于浮点操

48、作或取操作： 4.2 指令的动态调度5261 x (if(RegisterStatx.Qi = r)x (if(RegisterStatx.Qi = r) fx fx result; result; /向浮点寄存器写结果（所有的向浮点寄存器写结果（所有的fxfx）RegisterStatx.Qi RegisterStatx.Qi 0 0 ; ; /相应的目标寄存器中结果有效相应的目标寄存器中结果有效 x (if(RSx.Qj = r)x (if(RSx.Qj = r) RSx.Vj RSx.Vj result; result; /使用本结果作为第一操作数的保留站使用本结果作为第一操作数的保留站

49、RSx.Qj RSx.Qj 0 0 ););/相应的操作数有效相应的操作数有效4.2 指令的动态调度5361 x (if(RSx.Qk = r)x (if(RSx.Qk = r) RSx.Vk RSx.Vk result; result; /使用本结果作为第二操作数的保留站使用本结果作为第二操作数的保留站RSx.Qk RSx.Qk 0 0 );); /相应的操作数有效相应的操作数有效RSr.Busy RSr.Busy no; no; /释放保留站释放保留站, , 置保留站空闲置保留站空闲 对于存操作：对于存操作：MemRSr.A MemRSr.A RSr.Vk RSr.Vk/数据送存储器数据送

50、存储器 RSr.Busy RSr.Busy no; no; /释放保留站释放保留站, , 置保留站空闲置保留站空闲 4.2 指令的动态调度5461例：例：一个将数组中的元素与一个将数组中的元素与F2F2中的标量相乘的代码：中的标量相乘的代码： LoopLoop：LDLDF0,0(R1)F0,0(R1) MULTD MULTDF4,F0,F2F4,F0,F2 SDSD0(R1),F40(R1),F4 SUBI SUBIR1,R1,#8R1,R1,#8 BNEZ BNEZR1,LoopR1,Loop 现在假设将连续两遍循环的所有指令全都流出，但现在假设将连续两遍循环的所有指令全都流出，但所有的浮点

51、存、取及运算操作全都没完成。给出状态表所有的浮点存、取及运算操作全都没完成。给出状态表的信息。的信息。 4.2 指令的动态调度5561 解：解：保留站、寄存器状态表以及此时的存取缓冲保留站、寄存器状态表以及此时的存取缓冲 如所示。如所示。 忽略整数部件忽略整数部件ALUALU的操作，假设转移成功，乘的操作，假设转移成功，乘法操作可在法操作可在4 4个个时钟周期内完成，一旦系统达到此时钟周期内完成，一旦系统达到此状态则两遍循环同时执行，状态则两遍循环同时执行，CPICPI将达到接近。如果将达到接近。如果忽略循环的开销，且有足够的寄存器，那么性能忽略循环的开销，且有足够的寄存器，那么性能可达到通过

52、编译器循环展开并调度后的水平。可达到通过编译器循环展开并调度后的水平。 4.2 指令的动态调度5661指 令 指令状态表 循环遍次 流出 执行 写结果 LD F0 , 0(R1) 1 MULTD F4 , F0 , F2 1 SD 0(R1) , F4 1 LD F0 , 0(R1) 2 MULTD F4 , F0 , F2 2 SD 0(R1) , F4 2 4.2 指令的动态调度 寄存器状态表 F0 F2 F4 F6 F8 F10 F30 Qi Load2 Mult2 域名称 保留站 Load1Load2Add1Add2Add3Mult1Mult2Store1store2Busy yes

53、yes no no no yes yes yes yesOp LD LD MULTD MULTD SD SD VjRegsR1RegsR1-8Vk RegsF2RegsF2Qj Load1 Load2Qk Mult1Mult2ARegsR1RegsR1-85861 在此例中有在此例中有TomasuloTomasulo算法的另一个关键技术：算法的另一个关键技术： 动态存储器地址判别动态存储器地址判别 如果分支操作的开销不大，如果分支操作的开销不大，TomasuloTomasulo算法的动态算法的动态调度机制能得到非常高的性能。这种方法的主要调度机制能得到非常高的性能。这种方法的主要缺缺点点是是T

54、omasuloTomasulo算法实现的复杂性，实现它需要大量算法实现的复杂性，实现它需要大量的硬件，尤其是保存大量相关中间结果的高速缓冲的硬件，尤其是保存大量相关中间结果的高速缓冲寄存器和复杂的控制逻辑。此外，性能还受限于公寄存器和复杂的控制逻辑。此外，性能还受限于公共数据总线，因为它是单总线，如果增加公共数据共数据总线，因为它是单总线，如果增加公共数据总线的数量，与总线连接的缓冲和保留站的接口硬总线的数量，与总线连接的缓冲和保留站的接口硬件将会加倍。件将会加倍。 4.2 指令的动态调度59618.8.TomasuloTomasulo算法结合了两种不同的技术：算法结合了两种不同的技术： （1 1）寄存器换名寄存器换名 可以获得一个更大的虚拟寄存器空间。可以获得一个更大的虚拟寄存器空间。 （2 2）对寄存文件中源操作数缓存对寄存文件中源操作数缓存 解决了寄存器中的有效操作数相关引起的阻塞。解决了寄存器中的有效操作数相关引起的阻塞。TomasuloTomasulo算法提高指令级并行的关键技术是：算法提高指令级并行的关键技术是： 指令动态调度指令动态调度 寄存器换名寄存器换名 动态存储器地址判别动态存储器地址判别4.2 指令的动态调度