Tomasulo 算法

概述

Tomasulo算法是一种硬件动态指令调度算法,由IBM的Robert Tomasulo于1967年为System/360 Model 91的浮点单元设计,是现代乱序执行处理器的思想源头之一。

原理

算法的核心组件包括:保留站(Reservation Station),缓存等待执行的指令及其操作数;寄存器状态表,记录每个寄存器将由哪个功能单元产生结果;公共数据总线(CDB),功能单元完成计算后把结果连同标签广播给所有等待者。指令发射时若操作数未就绪,则记下生产者的标签在保留站中等待;结果广播时匹配标签即可捕获操作数。这一机制通过标签传递隐式完成了寄存器重命名,消除了WAR与WAW假相关。

与记分牌的比较

相比CDC 6600的记分牌(Scoreboarding),Tomasulo算法支持重命名且操作数随指令分布存放,并行度更高。

影响

结合重排序缓冲区支持精确异常后,Tomasulo思想成为教科书中讲授乱序执行的标准模型,被广泛应用于现代CPU设计。