ThinkLab

本文档旨在全面解析现代处理器中的指令级并行（Instruction-Level Parallelism, ILP）可视化技术，并深入探讨 MIPS R10K 架构的核心设计、数据结构及流水线机制。

1. 计算机指令级并行（ILP）的可视化

在现代超标量处理器中，理解指令的执行流和流水线停顿至关重要。通过图解框架，可以清晰地分析不同的硬件约束对指令执行的影响。

1.1 图解框架与基本假设

为了直观地展示指令的执行与调度，分析模型引入了以下图解规则与简化假设：

颜色编码机制：每一条指令都被赋予特定的颜色。颜色相同的指令代表它们在循环的第一次迭代中于同一个时钟周期内被发射（Issue）。
迭代表示：浅色区域通常表示当前循环的执行，而较暗的背景区域则用于标识循环的下一次迭代。
依赖关系指示：
- 黑色箭头：表示迭代内部（Intra-iteration）的指令数据依赖关系。
- 红色箭头：表示跨迭代（Inter-iteration）的指令数据依赖关系。
执行简化条件：模型在初期假定指令仅存在一个执行阶段（EX），即指令为单周期执行（直到引入功能单元争用模型）。同时，假定分支预测完美无误（无预测失败），且循环必定包含下一次迭代。

1.2 基本块结构与处理器约束模型

在分析中，使用了一个典型的 RISC-V 风格的基本块，其中包含算术逻辑指令（ALU）、内存读写指令（LS）、乘法指令（MULT）以及分支指令（BR）。指令的踪迹图（Trace Diagram）在不同的迭代中必须保持同构性。

随着分析的深入，逐步引入各种物理约束以观察其对执行周期的影响：

理想处理器模型（无限制、无分支预测机制）：假设具备无限的取指（Fetch）和发射（Issue）带宽。此时主要的性能瓶颈在于分支指令引发的停顿。由于分支的存在，下一次迭代的准备指令会提前执行，迭代间会产生明显的执行间隙。
取指与发射宽度限制模型：例如引入无限取指但限制 4 宽发射（4-wide issue），或者 8 宽取指结合 4 宽发射。在完美预测的情况下，处理器能够高效地利用发射窗口（Issue Width, IW），当上一次迭代接近完成时，下一次迭代的指令可以迅速填满发射窗口，实现指令的高效交错。
功能单元争用模型（FU Contention）：当处理器的硬件资源（如 ALU、乘法器或内存访问单元）数量有限时，即使取指和发射带宽充足，也会由于多个指令同时请求同一个功能单元而导致结构性冒险与流水线停顿。

2. MIPS R10K 架构核心概念

MIPS R10K 是一款经典的乱序执行（Out-of-Order Execution）超标量处理器。其核心优势在于通过寄存器重命名和高度并行的调度机制来消除假数据依赖并最大化指令吞吐量。

2.1 寄存器重命名（Register Renaming）

寄存器重命名是消除写后写（WAW）和读后写（WAR）等名称依赖（假依赖）的关键技术。

在 R10K 中，指令集架构中定义的架构寄存器（Architectural Registers，如 r1, r2 等）会在指令解码阶段被动态映射到数量更多的物理寄存器（Physical Registers，如 p1, p2 等）。
通过使用映射表（Map Table），处理器实时追踪每个架构寄存器当前对应的物理寄存器，确保后续依赖该寄存器的指令能够准确获取最新的数据。

2.2 核心硬件数据结构

R10K 的乱序执行引擎依赖于几个相互配合的关键数据结构。值得注意的是，与某些架构（如 Tomasulo 算法中的原始保留站）不同，R10K 的重排序缓冲区（ROB）、保留站（RS）和通用数据总线（CDB）中不存储实际的数值，所有数据值均统一存放在物理寄存器堆中。

标签（Tags）：即物理寄存器编号（PR#），用于在流水线各阶段唯一标识操作数位置。
重排序缓冲区（ROB - Reorder Buffer）：
- 使用头指针（Head）和尾指针（Tail）来维护指令在程序中的原始顺序。尾指针用于新指令分发入队，头指针用于指令按序退休（Retire）。
- 记录每个指令的输出属性：T 代表分配给当前指令逻辑输出的新物理寄存器；Told 代表在此之前映射到该逻辑输出的旧物理寄存器。
保留站（RS - Reservation Station）：
- 缓存等待执行的指令。包含操作码（Op）以及目的物理寄存器 T、源物理寄存器 T1 和 T2。
映射表（Map Table）：
- 记录架构寄存器到物理寄存器的实时映射关系。条目形式为 T+，其中 + 是一个就绪位（Ready Bit），用于指示该物理寄存器中的数据是否已被计算完毕并可供读取。
架构映射表（Architectural Map Table）：
- 记录已安全退休指令的架构寄存器状态。它表示程序的精确状态，便于在发生异常或分支预测错误时进行状态恢复。
空闲列表（Free List）：
- 维护当前未被任何架构寄存器映射或未分配给未退休指令的物理寄存器池。

3. R10K 流水线阶段详解

R10K 的流水线生命周期包含六个关键阶段，各个阶段紧密衔接，共同管理指令的乱序执行与按序提交：

取指（F - Fetch）：从指令缓存中获取指令。
分发（D - Dispatch）：
- 处理器首先检查是否存在结构冒险：即评估保留站（RS）、重排序缓冲区（ROB）、加载存储队列（LSQ）或物理寄存器（Free List）是否有足够的空闲条目。若资源不足，则流水线在此停顿。
- 为指令分配 RS、ROB 和 LSQ 条目，并从 Free List 中取出一个新的物理寄存器分配给指令的输出结果（标记为 T）。
- 查询 Map Table，将该架构寄存器之前的物理映射记录为 Told，并用新的 T 更新 Map Table。
- 推进 ROB 的尾指针（Tail）。
调度/发射（S - Schedule/Issue）：指令在保留站中等待，直到其源操作数的所有就绪位均置为 1 且所需功能单元空闲。
执行（X - Execute）：指令从保留站进入功能单元开始计算，同时将该指令对应的条目从保留站中移除。
完成（C - Complete）：
- 计算结果写入目标物理寄存器。
- 在 Map Table 中，将该目标物理寄存器对应的条目标记为已就绪（添加 +）。
- 唤醒保留站中依赖该结果的其他后续指令。
退休（R - Retire）：
- 处理器检查 ROB 头部的指令是否已完成（Complete）。若未完成，则退休阶段停顿等待。
- 如果发生异常，在此阶段进行统一处理，确保程序状态的精确性。
- 将 ROB 头指令记录的 Told（旧物理寄存器）归还到空闲列表（Free List），因为此后没有任何合法途径会再次读取该旧值。
- 将 ROB 头指令的目标物理寄存器 T 记录到架构映射表中，确认其为最终的架构状态。
- 对于 Store 指令，在此时将数据从 LSQ 写回数据缓存（D-Cache）。
- 最终释放相应的 ROB 和 LSQ 条目，并推进 ROB 的头指针（Head）。

通过上述严密的流水线分工和精巧的数据结构协作，MIPS R10K 能够在充分发掘指令级并行潜力的同时，确保程序逻辑的严谨性和异常处理的安全性。每一次寄存器状态的流转（从分配 T 到释放 Told）都是维持乱序执行引擎高效稳定运行的基础。

指令级并行与MIPS-R10K架构