Title Patent Number Inc. Year url
Pointer chasing prediction US9116817B2 Apple Inc. 2015 https://patents.google.com/patent/US9116817B2/en

这篇专利的核心是在 OoO 核中对 pointer chasing 的 load-to-load 依赖做延迟推测：当 younger load 的地址寄存器由 older load 产生时，调度器不等生产 load 的结果写回寄存器文件或 reservation station，而是提前发射消费 load

TLDR：

  1. 提前发射的前提有两个：consumer load 确实依赖 producer load；producer load 的结果被预测为来自 L1 D-cache 命中，而不是来自 store queue 的 store-to-load forwarding。满足时，LSU 将 producer load 从 D-cache read results 读出的数据直接转发到 consumer load 的 AGU/地址生成逻辑
  2. 该设计利用已有的 LS predictor/STL predictor 反向判断“是否不像 store queue forwarding”：如果生产 load 在 LS predictor 中没有对应 entry 或 index miss，则可高置信地认为它会从 L1 D-cache 取数，从而允许 LSU-internal forwarding
  3. 错误推测通过 replay 恢复：若 producer load 实际 L1 miss、store queue CAM 命中、对齐限制等使 D-cache 到 AGU 的内部转发不可用，则 replay consumer load 以及必要的年轻依赖指令；还可维护 replay counter，超过阈值后禁止该消费 load 的早发射

背景和动机

现代微处理器为了高频和复杂乱序执行，流水线深度不断增加。深流水带来的直接问题是结果从一个流水段传到后续依赖指令的可用点需要更多周期；同时，片上布局、长连线、repeater、流水寄存器也会放大从 L1 D-cache 到寄存器文件、调度队列、执行单元的传输延迟。

专利聚焦于一种很常见但传统流水线利用不足的短延迟场景：load-to-load dependency。若较年长 load 的目的寄存器正好是较年轻 load 的地址源寄存器，则较年轻 load 是一个 consumer load，较年长 load 是 producer load。例如链表遍历中，先 load 出节点指针，再用这个指针生成下一次 load 的地址，这就是专利称为 pointer chasing 的情况

传统路径通常是：

  1. producer load 在 LSU 中访问 D-cache 或 store queue。
  2. 结果被送往 load queue、scheduler/reservation station、register file 或 bypass 网络。
  3. consumer load 等到源操作数在调度器/保留站可用后才发射，再到 AGU 生成地址。

这个路径虽然通用，但对于“producer load L1D hit 且 consumer load 的唯一缺失源正是该 load 结果”而言过长。数据已经在 LSU/D-cache 读出端附近出现，却要先绕到寄存器文件或调度结构，再返回执行/地址生成路径。链式指针访问会把这几个周期反复串行累积，导致乱序窗口也难以隐藏延迟

专利提出的动机是：如果能在早期识别这种 load-to-load 依赖，并预测 producer 的结果会从 D-cache hit 产生，那么 consumer load 可以先被调度到 LSU，等 producer 的 D-cache 结果出来时直接在 LSU 内部送到 AGU 生成 consumer 地址，从而缩短关键链。

相关引用包括：

Title Authors, From url
Systems and methods for acquiring data for loads at different access times from hierarchical sources using a load queue as a temporary storage buffer and completing the load early Apple/Meier 等，美国专利引用族 https://patents.google.com/patent/US6481251B1/en
Load/store dependency predictor optimization for replayed loads Apple/Meier 等，美国专利引用族 https://patents.google.com/patent/US20130298127A1/en
Load-store dependency predictor content management Apple/Meier 等，美国专利引用族 https://patents.google.com/patent/US20130326198A1/en

Insight

Insight 1: pointer chasing 的瓶颈

pointer chasing 的瓶颈常常是“下一地址所需的指针值已经会在 LSU 的 D-cache hit 路径上较早出现，但通用调度/写回路径没有把这个早出现点暴露给消费 load”

传统流水线把 load 结果视为统一的写回事件：只有 producer 的结果到达寄存器文件、保留站或调度器后，consumer 才被认为 operand ready。
这个抽象对通用场景很合适，但在 load-to-load pointer chasing 中过于保守。
consumer 的地址生成只需要 producer 的数据值和自己的 immediate/offset；
如果 producer 的数据来自 L1 D-cache read results，且 AGU 位于 LSU 内部或可由 LSU 访问，那么可以在 LSU 内部构造一条更短的 producer-result-to-consumer-AGU bypass

Insight 2: Bypass 的核心取决于 producer load 的结果来源

  • 若 producer load 从 L1 D-cache 命中读取，那么结果在 D-cache pipeline/read results 附近可用，可以直接送 AGU。
  • 若 producer load 实际从 store queue bypass 获得，或者 L1 miss、对齐限制等情况发生，这条假设就不成立。

专利没有新建一个“D-cache-hit predictor”作为主要部件，而是复用/借用已有 LS predictor 对 store-to-load forwarding 的信息：
LS predictor 记录哪些 load 曾依赖更老 store；如果 producer load 在该预测器中没有 entry/index miss，则可推断它大概率不会从 store queue 取数，而是走 D-cache

这使得：

  1. load-to-load 依赖可在 decode/rename/mapper 阶段通过寄存器重命名关系和 dependency vector 识别
  2. producer 是否可能来自 store queue 可通过现有 LS predictor/STL predictor 查询
  3. scheduler 只需在满足条件时改变 consumer load 的 issue ready 条件，允许“源操作数尚未全局可见但预计会在 LSU 内部可见”的早发射
  4. LSU 提供内部 forwarding mux/path，从 D-cache read results 或 load queue 相关数据点到 AGU
  5. 错误时采用乱序核已有的 replay/mispredict 恢复框架

因此，它把 pointer chasing 加速拆成“早发射 + 局部转发 + 可恢复推测”，不是依赖编译器，也不要求 ISA 暴露特殊指令

核心设计

核心设计可以概括为以下流程：

  1. 在前端/rename/mapper 或 scheduler 分配阶段识别 producer load 和 younger consumer load 之间的 load-to-load 依赖：producer 的目的寄存器匹配 consumer 的地址源寄存器，并且二者之间没有其他指令覆盖该数据。
  2. 对 producer load 查询 LS predictor。若 producer 被预测为不会从 store queue forwarding 获得结果，也就是预测其结果来自 L1 D-cache，则认为满足 LSU-internal forwarding 条件。
  3. scheduler 在 consumer 的源操作数尚未写回到 scheduler/reservation station/register file 前，提前 issue consumer load 到 execution core/LSU。
  4. producer load 的 L1 D-cache hit 数据从 D-cache read results 直接转发给 LSU 内的 AGU/地址计算单元，AGU 用该数据加上 consumer load 的 offset/immediate 生成 consumer 地址。
  5. 若预测错误，执行 replay；若某条 consumer load 多次 replay，达到阈值后停止对它做早发射。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
               front-end / rename / scheduling side

I-cache -> Decode -> Mapper/Rename ------------------------------+
                       |                                         |
                       | dependency vectors, SCH#, SO#, PCs      |
                       v                                         |
                  Scheduler 20                                   |
                       |                                         |
                       | early issue consumer load               |
                       v                                         |
producer PC ----> LS predictor 19                                |
    |              |                                             |
    |              | miss / no allocated entry                   |
    |              v                                             |
    |        predict producer result from L1 D-cache             |
    |                                                            |
    +------------------------------------------------------------+

                       execution / LSU side

                +---------------- Execution Core 30 ----------------+
                |                                                   |
                |  +---------------- LSU 40 ---------------------+  |
                |  | Store Queue 42     Load Queue 44           |  |
                |  |      |               |                     |  |
                |  |      | CAM/STL       |                     |  |
                |  |      v               v                     |  |
                |  |  +---------- L1 D-cache 50 -------------+  |  |
                |  |  | Cache Array 54 -> Read Results 56    |  |  |
                |  |  +-------------------+------------------+  |  |
                |  |                      | producer data        |  |
                |  |                      v                      |  |
                |  |                 AGU 46 / addr gen           |  |
                |  |                      | consumer address     |  |
                |  +----------------------+----------------------+  |
                +-------------------------|-------------------------+
                                          v
                                 memory hierarchy

设计点 1: load-to-load / pointer chasing 依赖识别

解决的思路：
在 decode/rename/mapper 阶段利用寄存器依赖关系识别 producer load 和 consumer load。专利明确提到，producer load 的 destination register 匹配 consumer load 的 source/address register，且二者之间没有 intervening instruction 修改或存储 producer 的结果数据。mapper 可生成 dependency vectors，向 scheduler 提供每条 op 依赖的 op 集合

一个抽象化的依赖链如下：

1
2
3
4
5
6
7
8
9
10
line 16: R7  <- LD 8(R3)      ; producer load, predicted L1D hit
line 19: R10 <- LD 4(R7)      ; consumer load, address source is R7

traditional:
  LD16 -> L1D read -> writeback/bypass to scheduler/RF -> issue LD19 -> AGU

patent:
  LD16 -> L1D read results --------------------------+
                                                     v
                 early-issued LD19 already in LSU -> AGU -> LD19 address

微架构上，consumer load 的早发射的主要目的是：提前进入 LSU/执行路径，占好流水线位置，等待 producer 的 D-cache read results 在 LSU 内部出现后立即生成地址，省掉“先回调度/寄存器再重新发射”的延迟

设计点 2: 用 LS predictor 预测 producer 的结果来源

针对的问题：
producer load 的结果不一定来自 L1 D-cache。若它从 store queue forwarding 获得数据，那么 D-cache read results 到 AGU 的路径不存在或不是正确来源；若错误地提前 issue consumer，就会产生错误地址或源数据不可用，需要 replay。问题是：调度器在早期如何知道 producer 结果是否可能来自 D-cache？

解决的思路：
复用已有 load-store predictor。LS predictor 原本用于预测 store-to-load dependency 和 store queue forwarding。它保存曾经依赖 older store 的 load PC、相关 older store PC，以及 store 数据是否已到达 store queue 的指示。专利反向使用该信息：若 producer load 查 LS predictor 没有命中/没有分配 entry，则认为它大概率不是从 store queue 来，而是从 L1 D-cache 来

设计：
producer load 的 PC 或其一部分输入 hash function，生成 index 访问 LS predictor。hash 输入还可包含 history information，类似分支预测器索引生成。

结果：

  1. LS predictor miss：预测 producer misses store queue，即 producer result resides in / is available from L1 D-cache，允许 consumer load 早发射
  2. LS predictor hit：producer 可能涉及 STL forwarding，consumer 不走这种早发射；等待源操作数从 store queue/ALU/scheduler/RF 等常规路径准备好
1
2
3
4
5
6
7
8
9
10
11
producer load PC
      |
      v
  hash/index --------------+
      |                    |
      v                    |
 LS predictor 19           |
      |                    |
      +-- hit  ----------> likely store-queue/STL case -> no early issue
      |
      +-- miss/no entry --> likely L1 D-cache case ----> allow early issue

这个设计的工程价值在于无需完全准确预测 D-cache hit/miss，只要把明显不适合 LSU 内部 D-cache forwarding 的 store-queue cases 过滤掉。真正的 L1D hit/miss 和 store queue CAM 结果在执行阶段 resolve，错了用 replay 收敛。

设计点 3: scheduler 的早发射条件

针对的问题：
传统 scheduler 的 ready 逻辑通常要求所有源操作数 ready 或可经标准 bypass 在发射时可用。consumer load 的地址源数据尚未回到 scheduler/RF 时，ready bit 可能仍为 false，导致无法 issue，从而错过 LSU 内部短路径。

解决的思路：
为特定 load consumer 增加一种推测 ready 条件：当它依赖 producer load，且 producer load 被预测为可从 D-cache/LSU 内部提供结果时，scheduler 可在 result data available 之前 issue consumer。

专利还指出，处理窗口可能同时包含 producer 与 consumer。对于链表遍历，producer 和 consumer 在编译后的程序中通常距离很近，降低了早期识别的硬件复杂度

早发射本质上改变的是 load issue 的许可逻辑，不改变程序语义。consumer load 的地址仍由 producer 数据计算，预测错误则 replay

设计点 4: LSU 内部 D-cache read results 到 AGU 的 forwarding

针对的问题：
即使通用 bypass 网络能把 load result 转给 dependent instruction，仍可能需要跨越 D-cache、load queue、register file、scheduler、integer execution/AGU 的长路径。片上布局造成的连线和流水寄存器成本会让“理论上已经可用”的数据晚几个周期被使用

解决的思路：
把 producer load 的 D-cache read results 作为 consumer load 地址生成的直接输入。若 AGU 在 LSU 内，这条路径完全局部；若地址计算原本在 integer/FP execution units 中，也可在 LSU 中加入 dedicated AGU 处理这种情形。

关键数据通路如下：

1
2
3
4
5
6
7
8
9
10
11
producer LD address -> DTLB / D-cache lookup
                              |
                              v
                        D-cache read results
                              |
                              | local forwarding in LSU
                              v
consumer LD already issued -> AGU -> consumer effective address
                              |
                              v
                     D-cache / store queue dependency checks

设计点 5: 错误推测 replay

错误预测场景：

  1. producer load 实际 L1 D-cache miss，read results 没有按预期周期可用
  2. producer load 实际 store queue CAM hit，正确数据来自 store queue
  3. 对齐限制或其他微架构条件使 D-cache read results 到 AGU 的 forwarding 不可用
  4. consumer load 到 AGU 时 dependent data 不可用

解决的思路：
提前发射后 resolve prediction；若需要 replay，则 replay load 以及更年轻依赖指令，并清除 scheduler 中 picked/issued 等状态

replay 有两种方式：

  1. replay producer 之后所有 younger instructions；
  2. 使用 dependency information 只取消/重放依赖 producer 的年轻指令 (后者更精确，但依赖跟踪和取消逻辑更复杂)

为了避免某些 PC 或动态实例反复错误推测，专利还提出 replay count 阈值:

  • 计数可维护在 scheduler 、LSU 或 execution core 中，可统计连续 replay
  • 在正确预测时 reset，也可每次 replay 加一、正确预测减一，或者按时间窗口维护
  • 达到阈值后，阻止对应 consumer load 在 producer result available 前发射，回退到保守调度

微架构时序

可以把普通路径和专利路径按周期抽象比较：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
普通保守路径:

Cycle N:     producer LD issued to LSU
Cycle N+1:   DTLB/D-cache pipeline
Cycle N+2:   L1D hit data appears in read results
Cycle N+3:   data forwarded/written toward scheduler/RF/load queue
Cycle N+4:   consumer LD becomes ready and issues
Cycle N+5:   consumer AGU generates address

专利路径:

Cycle N:     producer LD issued; consumer LD also early-issued/picked for LSU path
Cycle N+1:   producer DTLB/D-cache pipeline; consumer waits for internal operand
Cycle N+2:   producer L1D hit data appears in read results
Cycle N+2/3: data forwarded locally to AGU; consumer address generated

实际周期取决于管线切分，但关键差异是：consumer 的 issue/pick 不再等待 producer 结果全局写回，AGU 输入来自 LSU 内部短旁路。

与预取器的关系

专利中提到 LSU 可包含 adaptive/history-dependent hardware prefetcher，该专利与 pointer-chasing prefetcher 的关系是互补的：

  1. 预取器试图在程序真正执行 load 前把数据放进 cache。
  2. 本专利假设 producer load 结果来自 D-cache hit 时，缩短 producer result 到 consumer address generation 的核心依赖链
  3. 如果预取器提升了 producer load 的 L1D hit 率，本机制更容易触发并收益更稳定；但本机制本身不要求预测未来地址序列