锐客网

  1. 首页 > it技术 > >

动态调度算法:记分牌算法&Tomasulo算法

动态调度：
通过硬件在程序执行时重新安排代码的执行序列来减少竞争引起的流水线停顿时间
动态调度流水线具备以下功能：
(1)允许按序取多条指令和发射多条指令----取指(IF)流水级允许按顺序取多条指令进入单口暂存器(single-entry latch)或队列(queue), 指令然后从latch或queue取出，进入ID节拍。
(2)能检查并消除hazards----将ID流水级分为独立的两级：Issue级和Read operand级：
Issue级功能
----指令译码，检查是否存在结构竞争(即在这一流水级解决结构竞争问题）；
【动态调度算法:记分牌算法&Tomasulo算法】 Read operands级功能
----等到无数据竞争(RAW)后，读出操作数，即在这一流水级解决数据竞争问题


记分牌算法具体设计:
动态调度技术需要将ID译码段分成两个阶段：1是发射，2是读取操作数。发射阶段对指令进行译码，检查结构冒险（例如有四个运算器：整数运算、加法器、乘法器、除法器，检查该指令需要使用的运算器是否正在被占用）读取操作数阶段检查数据冒险（读之前检查寄存器的值是否已经写回，或者是否会覆盖了之前的值）。数据冒险的解决方法（读写冒险(RAW)：将指令和操作数保存起来，然后只能在读操作数阶段进行读取；写写冒险(WAW)：检测是否有其它指令会写回到相同的寄存器（检测到冒险），有则等待，直到其它的完成）
发射阶段：假如检测到没有结构冒险和数据冒险，那么记分板将会将指令发射到相关的运算器，假如结构冒险或者写写冒险发生了，那么该指令将会等待，直到冒险消失为止。
读取操作数：没有数据相关了以后（之前的指令不会写回源寄存器或者正在写寄存器的情况时，读写冒险），读取操作数。读取操作数后将交给运算器，之后开始运算。发送到运算器的顺序可能是乱序的。
之后就是执行段以及写回段了。没啥好说的。执行段在完成计算以后会通知记分板。记分板直到计算已经完成了，那么它进行读写冒险检验（即写之前是否已经读取了寄存器的值，例如 ADD F10,F0,F8 SUB F8,F8,F14，这里SUB指令写回时要检查ADD指令的F8是否已经读取了，仅此而已）假如检测到冒险，则等待，不然就可以写寄存器了。
记分板由三个部分组成
part1 指令状态：记录指令究竟处于4个阶段中的哪一个阶段
part2 运算器单元FU状态：有9个域，分别是：
a) Busy 标识该器件是否正被使用
b) OP 该器件正在执行的运算 例如 + - * / 等等
c) FI 目标寄存器
d) Fj, Fk, 源操作寄存器
e) Qj Qk functional units producing source registers FJ FK （源操作寄存器正在被什么单元所处理）
f) Rj, Rk 表示Fj Fk 是否准备好的标志位
part3 寄存器结果状态：标识哪一个存储器将会被写回。
以下是记分板流水线的控制流程



Tomasulo算法
由于记分牌算法只能检测竞争(WAR,WAW)并不能消除这两种竞争，所以将记分牌算法改进为Tomasulo算法。
Tomasulo算法的基本思想：
Tomasulo算法采用寄存器重命名（Renaming）方法，将记分牌中的寄存器用一大组虚拟寄存器名来代替，即用虚拟寄存器集来代替真是的FP寄存器组，由于虚拟寄存器集合所含有的寄存器数目远大于真是的寄存器组，所以可以用虚拟寄存器集来实现寄存器重命名。
虚拟寄存器组由三部分组成：
1.每个功能单元（FU）都带有的保留站（Reservation station）
2.取数缓冲区（Load buffers）----保存被访问的存储单元的数据和地址
3.存数缓冲区（Store buffers）
另外，如图所示：


浮点寄存器（FP）通过一对总线与每一个功能单元（FU）相连接，这一对总线分别对应两个操作数，并通过一条总线与存数缓冲区（Load buffer）相连接。
功能单元（FU）的输出和存数缓冲区（Load Buffer）的输出汇总在CDB与浮点寄存器（FP）的输入相连接。
公共数据总线（Common data bus）CDB：CDB与FP，Reservation station，store buffer等输入相连接，唯一无连接关系的是Load Buffer的输入。
由于保留站和Buffer都有对应的标识符，所以这里实现了重命名。


Tomasulo每一级流水功能
1.发射级（Issue）
若是一条FP操作指令，如果保留站有空，则将其送至保留站，如果该指令的操作数已在FP寄存器，将操作数的值送往保留站。
若是一条Load或者Store指令，如果Buffer有空，将其送往相应的Buffer
如果保留站或者Buffer没有空，则存在结构竞争，停顿该指令，知道对应的保留站或者Buffer有空为止。
这一级完成了重命名，因为在保留站中的操作数不在使用寄存器号。
2.执行级（Execute）
若有一个或几个操作数未就绪，等待该操作数，并同时监控CDB。一旦操作数就绪，立即存入相应的保留站，若两个操作数均已就绪，则执行该操作，此级检查了是否存在RAW竞争。
3.写回级（Write Back）
当结果计算出来之后，将其写入CDB，并从CDB写入目的寄存器以及等待此结果的保留站，当连续写同一寄存器时，只有最后一次才能写入，消除了WAW竞争。


流水级的形式化描述：







Tomasulo法和记分牌法的异同
相同之处：
两者消除RAW竞争的思想相同。Tomasulo方法采用了记分牌方法的动态调度的核心思想，多条指令处于发射状态，等待条件成熟，可以不按顺序执行，不按顺序完成的思想，即为动态调度来消除RAW竞争。
不同之处：
Tomasulo方法通过寄存器换名过程可以消除WAR和WAW竞争。
记分牌方法能检测WAR和WAW竞争，一旦检测到存在WAR和WAW竞争，通过插入停顿周期来解决这一竞争。所以，记分牌方法不能消除WAR和WAW竞争。
硬件组织上有两点不同：
1.检测竞争和控制指令执行方式的不同：
Tomasulo方法检测竞争和控制指令执行两方面功能是通过分布在每一功能单元的保留站来进行的，因此Tomasulo方法是一种分布式方法。
记分牌方法的上述功能是通过统一的记分牌来实现的，因此记分牌方法是一种集中式方法。
2.写结果的方法不同：
Tomasulo方法通过CDB直接将功能单元输出的结果送往需要该结果的所有保留站，而不必经过寄存器这一中间环节。
记分牌方法是将结果写入FP寄存器, 因而可能造成等待这一结果的指令都出现停顿现象，之后，所有相关指令的功能单元在读FP 寄存器时又可能出现竞争现象。
Tomasulo方法的流水级功能与记分牌比较：
Tomasulo方法中无检查WAW和WAR竞争功能，因为在指令发射过程中，由issue logic结合保留站完成了register operands的改名过程，即消除了这两种竞争。
CDB起到广播结果的作用，不必通过register file直接结果送到所有需要该结果的保留站和buffers.
Load和Store buffers相当于基本功能单元



    推荐阅读


    上一篇：【CSP考前复习】关于考试时的注意事项

    下一篇：高中化学|【笔记总结】高中化学——【选四 Ⅰ】原电池&电解池