步骤 1：乱序访存单元
难度：⭐⭐⭐⭐
阅读时间：0.5h
预计代码时间：1h
关于预计用时
这里的预计用时是助教们根据标准实现的代码长度对实现时间的一个大致估计。根据你对 Tomasulo 算法本身的理解程度，用时可能有较大的偏差。建议大家如果在预计用时的两倍时间之后仍然没有完成任务的话，及时到课程群内向助教寻求帮助。
乱序访存的原理
在开始编写 Tomasulo 算法的核心逻辑之前，我们需要首先来了解一下实验框架使用的乱序访存单元的工作原理。
实验使用的乱序访存单元为部分乱序结构，Store 指令需要严格按序执行，而 Load 指令可以以任意顺序执行。
可能这个时候，你会产生一个疑问：“Load 指令能随便做吗？顺序乱了真的不会有影响吗？”
答案很明显是有影响的，我们来看这样一个很简单的例子：
sw t1, 0(a0) # 1
lw t2, 0(a0) # 2
很明显，如果 2 号在 1 号之前执行，会发生数据错误。
为了解决这样的问题，我们使用推测执行方案进行解决。这意味着，我们可能会按照错误的顺序执行 load 指令。如果真的做错了，则从这条 load 指令开始重新取指，刷新处理器。
我们首先来看访存单元的执行流程：
- 查询 Store Buffer，查看是否有在自己之前的 Store 指令已经被执行。有转 2，没有转 3。
- 使用 Store Buffer 中的内容，构造 Load 结果，转 4。
- 访问内存，构造 Load 结果，转 4。
- 将地址，rob 编号压入 Load Buffer。
- 查询 Store Buffer，查看是否有在自己之前的 Store 指令已经被执行。有转 2，没有转 3。
- 使用 Store Buffer 中的内容，构造对齐的 Store 结果，转 4。
- 访问内存，构造对齐的 Store 结果，转 4。
- 使用 rob 编号，和访存地址查询 Load Buffer，将所有次序在自己之后的 Load 指令全部置为无效，转 5。
- 将数据，地址，rob 编号压入 Store Buffer。
而在提交阶段，访存指令也需要进行额外处理：
- 弹出 Load Buffer 项，如果失效，转 2，否则转 3。
- “跳转” 到当前 PC，重新执行 Load。
- 写入寄存器，弹出 rob 项，正常提交。
- 查询 Store Buffer 顶，写入内存，转 2。
- 弹出 Store Buffer 项和 rob 项正常提交。
根据上述流程，如果 lw 在相同地址 sw 前执行，则会在 Load Buffer 中被标记为无效，从而在提交时进行处理，保证结果正确。
Load Buffer
由于 Load 指令可能会以乱序方式执行，因此，Load Buffer 的存储结构与 ROB 相同，采用随机读写的方式进行。
为了保证跟 ROB 的一致性，Load Buffer 项目的标号与其实际的 ROB 标号相同。
而在 Load Buffer 中，还需要存储 Load 地址和指令状态。
因此 LoadBufferSlot 的结构如下：
struct LoadBufferSlot {
unsigned robIdx;
unsigned loadAddress;
bool valid;
bool invalidate;
};
实际上可以不存储 rob 编号，但为了简单起见，还是进行了存储。
而在 Store 指令查询时，会传入 Store 指令的地址和 rob 编号，以及当前的 rob pop pointer，用于判断指令顺序。
因此需要对 LoadBuffer 表项进行遍历，检查项目的合法性，访存地址，rob 顺序，并标记乱序 Load 项目。
Store Buffer
Store 指令会由保留站保证执行顺序，因此采用循环队列的方式进行实现。
Store Buffer 需要存储 Store 地址，rob 编号，和数据。
因此 StoreBufferSlot 的结构如下：
struct StoreBufferSlot {
unsigned storeAddress;
unsigned storeData;
unsigned robIdx;
bool valid;
};
在对 Store Buffer 进行查询时，会传入指令的地址和 rob 编号，以及当前的 rob pop pointer，用于判断指令顺序。
需要倒序遍历 Store Buffer 的全部项目，找到第一个 rob 顺序（注意不是序号）在当前指令之前，且地址相同的条目进行返回。
完成 std::optional<unsigned> StoreBuffer::query：
- 按照地址和顺序查询 store buffer 中“最新”的内容，命中时返回对应数值
和 void LoadBuffer::check：
-
按照规则查询顺序在该 Store 指令之后，但已经完成推测执行的 Load 指令。
-
将这些 load 指令的 load buffer 表项设置为 invalid。
两个函数即可。
这样我们就完成了第一部分的必做功能--乱序访存单元的实现了。