1.与记分牌算法的比较
1.1 重新审视数据冒险
假数据冒险影响了记分牌算法的乱序性能。
那么什么是假数据冒险呢？
我们都知道，数据冒险有WAW,WAR,RAR,RAW这四种，而其中RAR其实在流水线中并没有影响指令的执行，所以可以把它忽略。
在剩下三个之中，只有RAW“写后读”才是真冒险，而WAR和WAW都是假冒险。为什么呢？因为这两种冒险都是在第一个操作后进行写操作，说明写操作的目标寄存器是被使用的状态，所以必须阻塞自己才能不引发冲突。而解决方法其实很简单，只要把写操作的目标寄存器改变成没有冲突的寄存器就可以解决。
但是RAW是无解的，因为后续指令读取的数据必须由前序指令算的，有明显的数据依赖，所以才是”真冒险”
这三种冒险的差别就出现在”数据依赖方面”。读后写”和“写后写”通过改写寄存器名字就可以消除冒险，这表明这两种冒险其实没有数据依赖，即发生冒险的指令之间其实没有数据流动。想要挖掘出指令的乱序潜力，理解这一点非常重要。
综上所述，“写后写”和“读后写”冒险不是真冒险，没必要为他们阻塞指令的流动
例子：
首先看“写后写”WAW冒险，可以看到第一条、第三条指令都要写R3寄存器，犯了“写后写”冒险。在记分牌中如果遇到这种情况，后序的AND指令因为和ADD指令发生“写后写”冒险，所以无法发射，流水线在发射阶段堵塞。
但是如果把AND指令的目的寄存器改写成R10，那么冒险就消除了，AND指令可以发射，只不过写回的目的寄存器是R10而不是R3。
同样的，审视“读后写”WAR冒险。第一条指令和第二条指令关于R3发生了“读后写”冒险，在记分牌中如果碰到这种情况，第二条指令在写回阶段时会检测到第一条指令需要读取R3旧值，所以第二条指令会卡在写回阶段，直到第一条指令读取完R3并且通知到自己为止。
如果把第二条指令的R3改写成R10，冒险就又解决了，第一条指令可以去读R3，第二条指令的更新结果存在R10，不会覆盖R3的旧值。
1.2 Tomasulo算法与记分牌
记分牌存在巨大的缺点，每个运算部件只有一个译码信息流水段寄存器，这意味着多配置处理器中的每一条配置通路同一时间只能存在一条指令，如果某一配置通路被占据，那么后面所有的指令都要被阻塞。
而且记分牌为了乱序执行指令，在碰到写后写、读后写这两个冒险的时候也会暂停流水线（为什么这里不提写后读呢，见后文），而这其实是不必要的，因此记分牌算法还是没有最大限度地挖掘出指令的乱序潜力。而且记分牌的“写回”是乱序的，乱序完成指令不利于处理器处理中断、异常等情况，不利于程序员debug程序。
Tomasulo采用了许多记分牌中的理念
两个较大的差异
Tomasulo算法中，冲突检测和执行控制是分布的，利用保留站实现
Tomasulo算法不用检查WAR和WAW相关，已经使用算法本身消除掉了
寄存器重命名
消除假数据相关的主要方法是寄存器重命名。
寄存器重命名其实就是修改寄存器的名字，防止寄存器冲突。那么就意味着需要在原来寄存器的基础上额外有寄存器。
实现额外寄存器的方法有两种
可以在逻辑寄存器（MIPS指令集规定了32个逻辑寄存器）之外额外有一组物理寄存器，结构如图。假如逻辑寄存器正要被改写或被读，就置Busy位为1，并通过Tag指示最新数据将被写到哪一个物理寄存器。通过这样的方法，我们可以在新数据计算完毕时立刻写回，同时也允许前序指令读取寄存器旧值（因为旧值没有被覆盖，它还存在于逻辑寄存器中）。
上面这种方法把逻辑寄存器和物理寄存器分离开，其实完全可以把两者混合起来，即为处理器提供超过逻辑寄存器数量的寄存器，如MIPS指令集要求32个逻辑寄存器，那就设计40个物理寄存器给处理器，至于哪些寄存器是ISA要求的32个寄存器，则视程序运行情况而定，相关信息可以用一个表格存储起来，理论上任何一个物理寄存器都可能是任何一个逻辑寄存器。
上面简单说明了两种寄存器重命名的方法，Tomasulo算法采用了第一种，但是不彻底，说Tomasulo算法蕴含寄存器重命名的思想则更合适。
2. Tomasulo算法
2.1 Tomasulo算法产生的背景
IBM 360/91比CDC6600(记分牌算法)晚三年推出
商业计算机使用cache技术之前
整个360系列仅一个指令系统和一个编译器
要求具有很高的浮点性能，但不是通过高端机器的专用的编译器实现
只有四个双精度浮点寄存器，编译器调度的有效性受到很大限制
访存时间和浮点计算时间都很长
可支持循环的多次迭代重叠执行
2.2 Tomasulo算法的结构
Tomasulo最大的特点就是通过借助重命名的思想消除了假数据冒险，从而提高了机器的乱序性能。
先看这个结构：
- 首先是FP OP Queue，这里是浮点指令队列，指令在这里等待发射；
- 青绿色模块是加法单元和乘法单元的保留站（保留站是什么？保留站保留已经发射的指令的信息和缓冲下来的数据。关于保留站，后文会有更多介绍）；
- 蓝绿色的Address Unit是地址计算单元，在这个算法中存储指令在执行前会先计算好存储地址；
- Memory Unit则是存储单元；
- CDB是数据广播总线，它可以直达寄存器堆（用来更新通用寄存器）、加法乘法存储单元的保留站（输送保留站中指令需要的数据）。
要解读Tomasulo算法，就要搞清楚这个算法运用了哪些信息来调度指令，然后要分清楚算法的调度步骤。接下来首先解释Tomasulo算法利用了哪些信息，然后讲解算法的调度步骤。
2.2.1 保留站和寄存器结果状态表
保留站是Tomasulo算法的精髓，不同于记分牌每一个配置通路前面的译码信息流水段寄存器，记分牌中每一条配置通路只能存放一条指令，而Tomasulo算法则为每一条通路配置了一组缓冲。就像上图中的绿色模块，其中浮点加法单元拥有能够缓冲三条指令的保留站。保留站存储的信息和记分牌有点类似。
保留站的结构有点像cache，可能有多行数据，每一行都对应一条被发射到保留站的指令。保留站每一行都有Busy位，指示这一行是否现存有指令；Vj和Vk与记分牌不同，记分牌的Vj和Vk会记录源寄存器的编号，而保留站则直接把能读取的数据直接拷贝到保留站中，可想而知，一旦数据进入保留站，那对应的寄存器就和这条指令没瓜葛了；Qj和Qk的信息和记分牌一样，记录尚不能读取的数据将由哪条指令算出；A是存储指令的地址，用于存放立即数和计算得到的地址数据。
看上去保留站和记分牌非常相似，但是两者其实有很大的不同。以上图的Add为例，保留站中有三行Add信息，这三行数据对应的是同一个加法单元，而在记分牌中这代表着三个加法单元。记分牌那样的一条通路只对应一条信息的做法容易造成指令堵塞、无法发射，而保留站则为每条通路预留了缓冲区，指令可以在加法单元忙碌的时候发射到保留站的缓冲区待命。
其次，保留站会直接把读取的数据缓冲下来，而不像记分牌一样只记录一个寄存器编号，只记录编号的话会造成读后写阻塞，因为一条指令在正式执行前一直在监控着它的源寄存器，源寄存器的值是不能改变的，因此后续指令无法写回，只能阻塞流水，而保留站则贯彻了“数据一旦准备完毕，就立马执行指令”的思想，指令一旦发现有数据可读，就立马读下来，读下来之后，那个源寄存器的写与不写就不关己事了。
记分牌和保留站相同的地方是都记录了Qj和Qk，即一旦需要的数据被算出来，就通过Qj和Qk捕捉广播数据，这样的做法其实就是重命名，即用保留站的编号而不是寄存器编号来标记数据源。
除了保留站数据结构之外，Tomasulo同样要记录寄存器结果状态，记录信息如图6.和记分牌一样，Tomasulo也会记录寄存器将被哪条指令更新，这个信息在指令寻找源数据时被使用。
2.2.2 调度流程
MIPS五阶段的流水线的改造
ID和EX阶段被以下三个阶段代替
1.流出(Issue)
2.执行(Execute)
3.结果写回(Write result)
流出(Issue)
1.从浮点指令队列中取出一条指令
2.如果存在一个空的保留站，就流出这条指令
3.如果操作数在寄存器中，就送到该指令对应的保留站
4.存储器取/存指令只要有空闲的缓存就可以流出
5.如果没有空闲的保留站或者缓存，就存在结构相关，指令暂停，直到有空闲的保留站或者缓存
执行(Execute)
1.如果缺少一个或者多个操作数，就监听CBD
这个阶段实际是检测和自动维护RAW相关
2.如果两个操作数都就绪，这条指令就可以执行
结果写回(Write result)
1.如果结果已经产生，将其写到CBD上
2.通过CDB,把这个结果写到目标寄存器和等待这个结果的所有功能单元的保留站
