CPU乱序执行基础 —— Tomasulo算法及执行过程

朋友们可以关注下我的公众号，获得最及时的更新：

 

或者关注我的知乎账号 ： https://www.zhihu.com/people/zhangyachen

 

 

IBM 360/91浮点单元最先实现Tomasulo算法从而允许乱序执行。360体系只有4个双精度浮点寄存器，限制了编译器调度的有效性。而且，IBM 360/91的访存和浮点延迟都很长，如果顺序执行指令，虽然只有RAW hazard，但是后面无关的指令只能被stall。如果乱序执行，还会额外引入WAR和WAW hazard。Tomasulo算法通过Register renaming解决了这些问题。

Tomasulo算法1966年提出，设计目标是让编译器在360系列计算机中通用，不用为每台计算机专门做一个编译器。

因为乱序执行，基础的Tomasulo算法不能保证Precise Exception和Speculation，带有Reorder buffer的Tomasulo算法可以解决这个问题。

作用

• 指令顺序发射(issue/dispatch)，乱序执行(execute)，顺序提交(commit)。
• Register renaming : 通过reservation station和ROB实现。
• distributed RS : 如果多个指令同时等待一个寄存器的数据，那么可以在一个时钟周期内通过CDB传输到多个RS.
• 实现Bypassing/forwarding
• 通过CDB，数据直接从执行单元EU传输到等待该操作数的RS。
• 通过Reorder buffer（ROB），可以实现Precise exception和HW Speculation，同时由于ROB保证指令顺序提交，顺便也消除了WAR & WAW hazard.

不带ROB

图来自computer architecture —— a quantitative approach 6th edition(英文版) P198

在不带ROB的版本里，执行单元(FP adders/FP mulitipliers)产出的数据会直接写入到对应的register file和等待这个数据的RS中，不能实现Precise exception和HW Speculation，所以这里关注带有ROB版本的Tomasulo 算法。

Precise exception(精确异常) 的意思是当指令出现异常时（除0、page fault，etc），前面的指令已经完成，后面的指令不能对寄存器、内存等进行修改，即跟顺序执行的效果一样，比如：

fdiv.d f0,f2,f4
fadd.d f10,f10,f8
fsub.d f12,f12,f14

3条指令之间没有hazard，后两条指令会比除法指令先结束。如果在结束后除法指令发生了exception，操作系统在进行exception处理时，只能假设之前的指令执行完成，后面指令没有执行，exception恢复后，加法和减法指令还得再执行一次，结果就不对了。

带ROB

图来自computer architecture —— a quantitative approach 6th edition(英文版) P210

ROB的存在使得指令虽然乱序执行，但是必须顺序提交，防止不可撤销的更新操作发生（写寄存器，写内存）。

Instruction queue

FIFO queue，存取到的指令。

Reservation Station

当前面的指令由于hazard、cache miss被阻塞时，后面不相关的指令可以继续执行，被阻塞的指令临时放在RS中，不至于整个流水线被阻塞。当被阻塞指令需要的操作数通过CDB传输到对应的RS时，指令被送到EU中执行。RS包含的字段：

• Op —— 此保留站存放的指令需要执行的运算，fadd、fld、fds，etc.
• Qj，Qk —— 即将更新此源操作数的指令对应的ROB entry tag。 0意味着不存在RAW hazard，该源操作数当前可用。比如fadd f0,f1,f2; fsub f3,f0,f2; 这里针对f0存在RAW hazard，假如为fadd指令分配的ROB entry tag是#1，那么fsub的RS entry里Qj就是#1, 意思是等待ROB tag为#1的指令更新这个操作数。其实这里就是通过Register renaming减少RAW hazard。
• Vj, Vk —— 源操作数的值。对于每一个操作数，Q和V只有一个是有效的。
• A —— 在load/store指令中存放内存地址相关信息。比如fld f6, 32(x2), 32+x2是effective address，放在此字段中。
• Dest —— 此指令对应的ROB entry tag。用来更新对应ROB中的field.
• Busy —— 是否被占用。

Common data bus(CDB)

数据传输，EU -> RS、ROB -> Register File，etc。传输时还会带着更新此数据的指令对应的ROB entry tag，这样RS里就可以通过匹配tag来更新源操作数。

Reorder buffer（ROB）

FIFO queue，每一项ROB包含4个字段：

• Instruction type —— 指令类型。branch、store、load、ALU operation.
• Destination —— 对于load和ALU operation来说是目标寄存器，对于store是内存地址，branch此字段无意义。
• Value —— 指令结果值。
• Ready —— 指令是否已经完成执行。

Register File

由于Commit阶段存在，Register File只能由ROB通过CDB去更新，RS不能直接更新Register File. Register File存放着将要向此寄存器更新值的ROB entry tag。如果没有值或者为0，代表此寄存器的值可用，否则，意味着该寄存器的值会被前面的指令更新，用该寄存器作为源操作数的需要等待CDB将更新后的值传输过来。

Load Buffer/Store Buffer

Load Buffer存放effective address。Store Buffer的功能一般集成到了ROB中，因为Store Buffer需要的value和effective address在ROB中已经有了。

load/store指令对于相同的effective address也是存在hazard的，而且必须是effective address在execute阶段计算好后才知道是否有hazard存在。比如：

• fsd f5, 1000(f0), fld f0, 1000(f0)
• fsd f5, 1000(f0), fld f0, 1000(f1) —— 虽然base register不同，但是有可能f0和f1的值相同，计算后的effective address也相同，这就存在RAW hazard.

指令执行过程 发射(Issue)

从instruction queue取一条指令（单发射）。如果RS和ROB均有空位，则发射指令到RS，如果有一个没有空位，会stall指令发射。如果操作数对应的寄存器/ROB中的数据可用，。更新Busy字段表明此RS项被占用。为分配的ROB

执行(Execute)

如果操作数均准备好了，直接执行，可能占用多个时钟周期，如果在同一个时钟周期内有多个指令可以执行，一般策略是随机挑选。如果任一一个操作数没有准备好，监控CDB获取计算好的操作数，此步骤检查RAW hazard.

对于store指令，此步骤仅仅计算effective address.

对于load指令，除了计算effective address，还需要确保当前ROB中的Store指令没有相同的Destination时，才会去内存/cache中读数据，这里避免了针对同一effective address的RAW hazard.

写回(Write result)

计算结果和指令对应的ROB entry tag沿着CDB传输到ROB和等待此操作结果的RS项。对于store指令比较特殊，如果要存储的值已经准备好了，将其写到对应ROB entry的Value字段，否则，还需要等CDB将需要存储的值传输过来，更新Value.

注意和不带ROB的算法不同，为了之后可回退计算结果，此步骤不会直接将结果写入到Register File中。

提交(Commit)

当指令到达ROB头部且ready字段为1，根据指令类型不同，操作不同：

• normal commit —— 用Value更新Destination寄存器，并将对应的项目从ROB移除。
• store —— 和上面类似，只是根据Destination和Value更新对应的内存地址。
• branch with incorrect prediction —— 意味着branch预测错误(CPU分支预测器是另外一个很大的话题)，需要flush ROB，也就是不要提交branch预测错误后执行指令，从应该执行的指令处重新开始执行。

如果一个指令抛出了异常/预测错误，会在ROB中记录。只有在Commit阶段且指令到达ROB头部时才会识别并flush ROB。

这个是整体流程的伪代码，来自computer architecture —— a quantitative approach 6th edition(英文版) P216

• rd —— 目标寄存器，rs/rt —— 源寄存器。
• RS —— Reservation Station，r和b —— 为指令分配的Reservation Station entry和ROB entry。
• h —— ROB头部entry。
• result —— RS通过CDB传输的EU计算结果。
• RegisterStat —— 寄存器结构，Regs —— 实际寄存器。

RS和ROB的项数

可以看出RS和ROB的总项数反映出一个处理器的乱序执行能力。项数越大表明in-flight（正在执行）的指令数目越多。Intel公司的Nehamel有128项ROB，IBM公司的Power 4/5有200项ROB.

Reservation Station组织形态一般有三种：

• 独立 —— 一个EU一个RS，设计简单，只要一个写入端口和读出端口。但是利用率低，容易忙的忙死，闲的闲死。
• 分组 —— 把EU分为几组，同组的共享一个RS，需要多个写入和读出端口。分组时通常考虑定点、浮点和访问3类。MIPS R1000是定点、浮点和访问3个RS，每个各16项。Alpha 21264是定点和访存共用一个20项的RS，浮点共用一个15项的RS。
• 全局 —— 所有EU共用一个RS，读出和写入端口很多，控制比较复杂。当然使用效率最高，而且CDB只要送到全局RS。Intel P6架构的Pentium Pro、Pentuim II、Pentuim III都是类似的结构，只有一个RS，共20项。

 

Onur Mutlu的这个Lecture讲的更加详细

Digital Design & Computer Arch. - Lecture 16: Out-of-Order Execution (ETH Zürich, Spring 2021)​www.youtube.com/watch?v=mjBwrgecZPU     (完)  

朋友们可以关注下我的公众号，获得最及时的更新：