Operation Cache(AMD US10606599B2)[2020]: OPERATION CACHE

Title	Patent Number	Inc.	Year	url
OPERATION CACHE	US10606599B2	Advanced Micro Devices, Inc.	2020	https://patents.google.com/patent/US10606599B2/en

TLDR：
该专利提出一种 operation cache (OC)，缓存已经从 variable-length instruction 解码成 fixed-width canonical format 的 ops，使前端在命中时绕过传统 instruction cache fetch + instruction decode pipeline

1. OC entry 面向 x86 这类变长 ISA 的前端瓶颈设计：每个 entry 最多保存 8 个 ops，同时可携带 Imm/Disp 和 micro-code entry point。
2. OC 采用 physical index/tag，允许不同线程共享相同物理指令对应的 decoded ops，避免只按虚拟地址组织时的跨线程重复与别名问题。
3. OC 通过 SequentialOffset/SequentialBasicBlock 在多个 way/entry 间 chaining，使一个 cache line 内数量不固定的指令可以由多个 OC entry 连续服务。
4. OC 的存储布局将 op storage 与 immediate/displacement storage 部分共享；当 Imm/Disp 较多时牺牲高编号 op slot，从而提高总体容量利用率。
5. 专利还给出 micro-tag 快速预测、OC tag 精确判定、IC/OC mode 切换、OC build pipeline，以及基于 instruction cache access count 的选择性构建策略。

背景和动机

该专利面向高性能处理器前端，尤其是 x86 这类 variable-width instruction ISA。
传统 pipeline 通常先从 instruction cache 取字节流，再经过 instruction parsing/decode 才能得到内部 fixed-width ops。与 fixed-length ISA 相比，变长指令需要判断指令边界、解析 prefix/opcode/ModRM/SIB/Imm/Disp 等字段；如果希望每周期解码多条指令，硬件复杂度、流水级数和功耗都会上升。

专利指出，当 taken branch 或 mispredicted branch 导致 fetch redirect 时，额外的取指/解码流水级会增加 redirect latency。redirect 后的新指令需要重新经过 fetch/decode pipeline 才能到达 dispatch，期间前端或后端部分流水级可能空转，降低 IPC 并浪费功耗。

已有 decoded instruction cache / micro-op cache 思路可以减少重复解码，但工程上仍需要解决几个问题：

1. 如何适配 x86 变长指令和 cache line 边界
2. 如何在多线程间共享 decoded instructions
3. 如何用有限容量同时存储 ops、Imm/Disp 和 micro-code entry
4. 如何在 IC pipeline 与 OC pipeline 之间低延迟切换

相关工作：

Title	Authors, From	url
Micro-Operation Cache: A Power Aware Frontend for Variable Instruction Length ISA	Solomon et al., IEEE TVLSI, 2003	PDF references
Instruction Decode and uop Cache, Intel’s Sandy Bridge Microarchitecture	David Kanter, Real World Tech, 2010	http://www.realworldtech.com/sandy-bridge/4/
DIA: A Complexity-Effective Decoding Architecture	Santana et al., IEEE Transactions on Computers, 2009	PDF references
Improving CISC Instruction Decoding Performance Using a Fill Unit	Smotherman et al., MICRO, 1995	PDF references
Decoded Instruction Cache for Variable Instruction Length Computers	Intrater et al., IEEE Israel conference, 1989	PDF references

---

Insight

Insight 1: decoded op cache 的价值来自 redirect latency 与 decode power 的同时降低

OC 命中后，前端不再需要重新从 instruction byte stream 中确定边界、拆分字段并生成内部 op，而是直接从 OC 输出固定宽度的 decoded ops

这样既减少重复解码功耗，也减少 branch redirect 后新路径到达 OPQ 的流水延迟

该专利强调的收益是让高带宽 dispatch 可以绕过最复杂、最耗能的 variable-length decode 逻辑。

Insight 2: OC 按 basic block 和 cache line 边界组织

专利将 OC 内容组织为 basic block：从 branch target 或 cache line 顺序入口开始，到 taken branch 或 cache line 末尾结束

• 如果 basic block 跨越 cache line，则在 cache line boundary 处分裂为 target basic block 和 sequential basic block
• 这样做的原因是前端 fetch address 与 branch predictor 通常以 cache line 和 branch target 为粒度工作，OC 也必须能从这些地址自然进入，并能在 cache line 边界处继续串接。

Insight 3: physical index/tag 使 decoded ops 可以跨线程共享

如果 OC 只按虚拟地址或线程局部上下文组织，同一物理代码页在多个线程中可能产生重复 decoded entries，或者需要复杂的别名处理

专利做法：

1. OC entries 使用 PIPT 组织，使相同物理指令对应的 decoded ops 可以被线程共享
2. OC tag 还包含执行模式相关条件，例如 64-bit mode 标记和 TSFault 条件，避免不同 decode 语义下错误命中

Insight 4: 容量效率来自“不均匀 payload”的共享存储

OC entry 中多数指令不一定都需要大量 Imm/Disp，也不一定包含 micro-coded instruction。

专利利用这个统计特性，让 entry 固定支持常见情况，同时允许 Imm/Disp 占用高编号 op slot 的 bit storage。当 Imm/Disp 很多时，entry 可容纳的 op 数减少；当 Imm/Disp 较少时，更多空间用于 ops。该设计比完全分离的固定配额更贴近实际 instruction mix。

---

核心设计

专利核心是一个连接 branch predictor、instruction cache/decode pipeline 和 operation queue 的 operation cache 前端

1. OC 在传统 decode pipeline 生成 ops 时被填充
2. 之后遇到相同 fetch path 时，前端先用 OC micro-tag 快速判断是否可能命中
3. 再用 OC tag 精确判定，命中则读出 OC data array 并输出到 OPQ/IDQ/EAQ，未命中则 redirect 回 instruction cache pipeline

设计点 1: OC entry 格式

针对的问题: decoded ops、Imm/Disp 和 micro-code entry point 的数量在不同 x86 指令序列中变化很大，如果全部固定分区，容量利用率低。

解决的思路: 单个 OC entry 以固定大小承载常见 decode 结果，并允许部分字段共享 bit storage。

设计：

• 一个 OC entry 在实施例中为 74 bytes / 592 bits
• 每个 entry 最多保存 8 个 operations，每个 op 编码为 56 bits
• entry information 包含 NumOps 和 parity 等 per-entry metadata
• 每个 entry 专用保存最多 4 个 32-bit Imm/Disp；额外 Imm/Disp 最多扩展到 8 个，但会从最高编号 op slot 开始占用 storage。
• 当存在 8 个 Imm/Disp 时，entry 最多只能保存 5 个 operations。
• micro-code entry point 使用 op slot 4 的位置存储 1-4 个 micro-code EP；如果 entry 含 micro-coded instruction，则只有 op 0-3 可以保存有效 operations，op 5-7 仍可用于 Imm/Disp。

OC Entry (conceptual)

+------------+-------------------------------+---------------------+
| EntryInfo  | Op0 Op1 Op2 Op3 Op4 Op5 Op6 Op7 | Imm/Disp shared area |
+------------+-------------------------------+---------------------+
                         ^
                         |
               Op4 may hold micro-code EPs

High-numbered op slots can be reused by extra Imm/Disp fields.

设计点 2: micro-tag 与 full tag 两级判定

针对的问题: 每次 fetch 都访问完整 OC tag/data 会增加功耗和前端复杂度；但只用小 tag 又可能误判

解决的思路: 用 micro-tag 作为早期 hint，用 full OC tag 做精确 hit/miss 判定

设计：

• OC micro-tag array 与 OC data array / full tag array 有相同 indexing 和 ways，但物理上分离，在 pipeline 较早阶段使用。
• micro-tag 包含 valid bit 和 physical address hash，用于快速判断某 fetch address 是否“可能在 OC 中”。
• micro-tag 命中后，前端从 IC mode 切换到 OC mode；真正的 hit/miss 仍由 full OC tag 比较决定。
• full tag 包含 physical address bits、Offset、CS64、TSFault、SequentialBasicBlock、SequentialOffset 等字段。
• x86 特定 Bits
  • CS64 bit 用于区分 32-bit mode 与 64-bit mode 下的 decode 结果
  • TSFault bit 用于在 CR0.TS = 1 时强制相关 entry miss，从而走传统 decode/fault 路径

设计点 3: basic block、cache line 边界与 chaining

针对的问题: x86 指令长度不固定，一个 64B cache line 内可能包含任意数量的 instructions；basic block 也可能跨越 cache line。固定“一行一个 entry”难以稳定服务完整指令流。

解决的思路: 将 basic block 拆成一个或多个 OC entries，并用 tag 中的 sequential metadata 将它们串接。

设计：

• basic block 从 branch target 或顺序进入 cache line 的起点开始
• basic block 到 taken branch 的最后字节或 cache line 末尾结束
• 如果 instruction 跨越 64B boundary，则该 instruction 归属到包含其 end byte 的 cache line / basic block；因此跨 cacheline instruction 会作为后续 entry 的第一条 instruction。
• SequentialOffset 表示当前 entry 最后一个 op 对应 instruction 之后的 next sequential instruction 的起始偏移。
• SequentialBasicBlock 表示 next sequential instruction 是否落在下一 64B block。
• 通过 SequentialOffset 和 SequentialBasicBlock，OC 可以在多个 entries/ways 间 chaining，服务 cache line 内可变数量的 instructions，也可以从一个 basic block 连接到下一个 sequential basic block。

设计点 4: IC mode 与 OC mode 的切换

针对的问题: 前端需要在传统 instruction cache/decode pipeline 与 OC pipeline 之间切换，同时不能让两个 pipeline 的 ops 乱序写入 OPQ

解决的思路: branch prediction/fetch 产生地址后，先用 micro-tag 判断是否进入 OC mode；如果 OC full tag miss，再 redirect 回 IC mode。

设计：

• reset 后 pipeline 默认处于 IC mode，所有 fetch 走传统 instruction cache fetch 和 decode。
• fetch address 输入 OC micro-tag，同时写入 decoupling queue (DQ)，DQ 解耦 branch prediction pipeline 与 IC/OC pipeline。
• micro-tag 匹配只针对 branch target fetch 和 redirect target fetch，因为这些场景下 fetch pipeline 知道 instruction start position。
• micro-tag 命中时，前端切换到 op-cache mode；OC pipeline 等待传统 fetch/decode pipeline 清空后才向 OPQ 交付 ops，避免旧模式和新模式的 ops 交叉。
• OCQ 缓冲 OC fetch requests；如果 OC tag miss，则通过 OC Fetch Redirect 回到 IC pipeline。
• redirect 和 resync 优先于普通 mode transition；某些 resync 会强制 IC mode，以便 fused instructions 在异常处理场景中按原始指令分别 decode/dispatch。
• 一旦 OC 命中一个 entry, 且该entry 后续有顺序的 entry 可以连接起来，则依旧保持在 OC Mode ，下一 Cycle 继续从 OC 中取，直到从 OC 取完一个完整的 block 后再判断下一次的 fetch pc 的 tag 是否匹配 micro-tag (进入 OC Mode 还是 IC Mode)

flowchart TD
    A[Predicted fetch address] --> B[Compare OC micro-tags]
    A --> C[Write DQ]
    B -->|micro-tag hit| D[Switch / stay in OC mode]
    B -->|miss| E[IC mode]
    D --> F[Write fetch address to OCQ]
    F --> G[Read OC full tag]
    G -->|tag hit| H[Read OC data array]
    G -->|tag miss| I[OC fetch redirect to IC]

设计点 5: OC fetch 输出路径

OC 命中后需要把 entry 中混合存放的 op、Imm/Disp 和 micro-code entry point 转换成后续流水线可消费的队列格式。

设计：

• OC fetch pipeline 从 OCQ 或 bypass path 取得 fetch address。
• 使用 physical address bits 10:6 选择 set，并比较 8 ways 的 full tag。
• tag hit 后读取 OC data array，entry 最多包含 8 个 ops。
• decode stage 对 OC entry 做简单解释，输出到三个队列：
  • OPQ: operation queue，向 register renaming / dispatch pipeline 供给 decoded ops。
  • IDQ: immediate/displacement queue，保存 Imm/Disp payload。
  • EAQ: entry address queue，保存 micro-code entry point。
• OPQ 作为 OC pipeline 或传统 decode pipeline 与 dispatch pipeline 之间的 decoupling buffer，使上游可以在下游暂不可推进时继续暂存 ops。

设计点 6: OC 训练构建 pipeline

OC 需要在传统 decode 产生可信 decoded ops 后构建 entry，同时避免污染缓存或浪费容量。

设计：

• decoder 每周期最多输出 4 个 decoded instructions，以及对应 Imm/Disp 或 micro-code entry point。
• OC entry accumulator 聚合这些 decode 结果，形成 OC entry contents 和对应 fetch address。
• OC build queue (OCBQ) 缓冲若干 entries 和 tags，再分别写入 OC micro-tag writer、OC tag writer、OC data writer。
• build 在以下条件中最早发生者处停止：
  1. 第 8 个 operation
  2. 第 8 个 Imm/Disp
  3. op 与 Imm/Disp shared space 冲突
  4. 存在 micro-coded instruction 时达到第 4 个 operation
  5. 遇到跨过 cache line 末尾的 instruction
  6. 遇到 predicted-taken branch
  7. 或超过两个 instructions 带有关联 branch predictions
• 当 fetch window 包含 predicted-taken branch 时，fetch address 携带 window termination offset；OC fetch 时该 offset 可让 dispatch 在 entry 中间提前停止
• 如果 entry 构建时 conditional branch 被预测 taken，但后续 fetch 时预测 not taken，顺序 fall-through 指令不在该 entry 中，OC 会 miss 并 redirect 到 IC pipeline，为 fall-through path 构建新 entry

OC 输入过滤: 选择性构建 frequently-used cache lines

针对的问题: 对所有经过 decode 的指令都写入 OC 会增加功耗，并可能用冷代码污染有限的 OC 容量

解决的思路: 使用 instruction cache access count 作为 build qualifier，只为更可能复用的 cache line 构建 OC entry

设计：

方案 1: 每个 icache entry 增加一个 access counter bit

• 对 demand/prefetch 从上层 memory hierarchy 填入 instruction cache 的 fetch，access count 视为 0
• 后续命中 instruction cache 的 fetch，access count 视为 1

方案2: 简化实现直接用 icache tag hit 作为 access count 的 proxy：tag miss 对应 0，tag hit 对应 1

• 无需在 icache tag 中额外存储 count bits

• 但在 tag aliasing 时可能存在近似误差

• build 开始条件包括：

  1. IC mode 下取到 branch target
  2. decode redirect target 或 OC redirect target
  3. 对应 cache line 满足 access count build qualification

• build 停止条件包括：

  1. 切换到 OC mode
  2. cache line 不满足 build qualification
  3. resync target
  4. processor operating mode 改变影响 decode
  5. 检测到 illegal/incomplete instruction
  6. invalidating probe 命中 build pipeline 中 in-flight instructions