Skip to content

算法Algorithm

标签就绪与动态发射

Tagged ready instruction issue · Age-ordered ready issue · 标签就绪发射

根据固定源标签、操作数就绪和执行单元可用性选择最老候选,逐周期区分运算延迟、结果端口仲裁与顺序退休。

第一条乘法还要等六个周期,第三条却只是把常数7写进自己的新版本。让第三条也排着不动很浪费,但“往前挑一条能做的”必须有准确条件:它需要的值都到了吗,执行单元空着吗,结果算好后有地方发布吗?动态发射把这些条件放到每个周期重新判断。

形式陈述 ​

发射许可不是程序位置 ​

输入是按程序序经过物理寄存器重命名的有限指令流。每项保存不再改变的源标签、一个动态年龄和目的标签;物理寄存器各有ready位。等待项I可发射,当且仅当:

phase(I)=WAIT,∀p∈src(I), ready[p],unit(I) 空闲.

本页每周期至多发射一个满足条件的候选,选动态年龄最小者。较老指令若不满足条件,不阻止其他单元的就绪指令被选中;“最老就绪”不同于“无论是否就绪都只看最老一条”。官方BOOM文档区分操作数存在、端口适配与年龄选择;下面再固定一个更小的可复算机器。[1]

CONST/ADD共用ALU,MUL、DIV、STORE各用一台专属单元。每台都非流水化:从发射到结果发布一直占用,不能在前一条尚未发布时接下一条同类工作。延迟分别为1、6、2、1周期,迁移实验允许改成任意正整数。

发射时读取全部固定源的值,捕获运算输入。若在周期c发射、单元延迟为d,则最早在 c+d 进入可发布集合。这里运算结果可由模拟器立即计算,但只能到规定周期后被后续指令使用;不能把Python求值时刻当作机器的结果可用时刻。

一个结果端口与完整周期边界 ​

所有单元共享一个结果发布位置。每周期从“延迟已经到期”的运行项中选最老一项发布;其他项保留结果并继续占住单元。正常寄存器结果写入目的标签并置ready;除零只记录fault,不把一个虚构数值标成ready;STORE只保存准备好的数据,不写内存。

每周期严格依次执行四步:

阶段 至多做什么 可以看见本周期之前哪些阶段的变化
退休 队首已DONE的项退休;队首fault则恢复并结束本周期 上周期之前已经发布的结果
发布 一个到期结果变DONE,写物理值/ready或记录fault 本周期刚释放的资源
发射 一个最老可发射项开始执行 本周期刚发布的源值及空出来的单元
重命名 下一条程序指令入窗 本周期退休释放的物理位置及ROB空间

刚重命名的项最早下一周期发射;刚发布的值可以同周期供已有消费者发射;刚发布的项却不能倒回本周期已结束的退休阶段。这些规则是本文模拟器的契约,不是所有处理器的时序。完整参考器直接按这个顺序执行。

直觉

等待的理由不止一个 ​

源未就绪是数据等待:I1要p6,乘法还没把12放进去。单元忙是结构等待:另一条ADD即使源齐全,ALU还留着前一结果就不能接它。结果端口冲突是发布等待:两个单元都算好了,本周期仍只能挑一份结果。

ready也不是“已经退休”。第三条产生的7可以供第四条使用,而前面的乘法仍未退休;两条年轻操作都只写各自推测版本。最后由顺序退休决定哪些结果能被架构观察。没有这种延后承诺,单有就绪判断不足以处理异常。

明示周期中的发射、结果发布与退休
例子与边界

同一片段从13周期算到每个值 ​

使用重命名页的五条指令和初值,11个物理位置、ROB容量8。周期1重命名I0;周期2让它以3和4开始六周期乘法,并重命名I1。I1等p6,周期3无法发射,但仍可把独立I2送入窗。

指令 重命名 发射 最早可发布 实际发布 退休
I0:MUL→p6=12 1 2 8 8 9
I1:ADD→p7=15 2 8 9 9 10
I2:CONST→p8=7 3 4 5 5 11
I3:ADD→p9=11 4 5 6 6 12
I4:STORE数据15 5 9 10 10 13

周期5先发布I2的7,再发射已经在窗里的I3,所以I3读到7和4。周期8先发布I0的12,再发射I1,读到12和3。I1没有因为“现在r1代表7”而换源,它固定等p6。

发布顺序为I2、I3、I0、I1、I4,退休顺序仍是I0到I4。周期10的STORE已经DONE,内存却仍是31;到周期13退休才变15。仅打印最终寄存器无法区分这些事件,终点要求同时交付两种顺序。

两个结果同时到期怎么办 ​

把I1改为 DIV r4,r2,r0,I2改为常数99,再让I3是 STORE [0],r3、I4是 ADD r5,r2,r3。r0初值0。DIV在周期3发射、周期5到期;CONST在周期4发射,同样周期5到期。

发布槽优先选较老I1,记录除零。I2虽然已算完99,仍占住ALU到周期6发布。周期5可以发射别的单元上的STORE。之后:

  • 周期6,I2先于到期的I3发布;ALU腾出,同周期可发射I4
  • 周期7,I3先于I4发布,STORE数据4只被暂存
  • 周期8,更老I0的乘法到期,再次让I4推迟
  • 周期9,I0退休,I4才发布7
  • 周期10,I1到退休队首,正式报告异常并清掉全部年轻项

I4的算术延迟只有1,周期6发射,却到周期9才发布。实际完成等待由共享端口决定,不能把每条“发射+算术延迟”都当作实际发布周期。

容量只影响可重叠的工作 ​

正常五条片段保持初值和延迟不变,实际迁移为:

物理位置P ROB容量Q 总周期 前端阻塞记录
7 1 21 ROB满13周期
7 8 19 无空闲物理位置11周期
8 2 15 ROB满7周期
11 8 13 无这两类阻塞

计数器先检查ROB满,再检查空闲位置,所以同一周期不会重复记两类前端原因。表中最终寄存器和内存完全相同。扩大窗可能减少这个例子的等待,但不是“容量越大,任意程序都严格更快”的定理,也不能由周期数直接推出更高时钟频率。

推论与应用

为什么重排后的操作数仍正确 ​

重命名已保证每个源标签对应顺序程序中的最近较老写者。初始版本的值正确且ready;设某项发射时全部源ready,归纳上每个源由其正确生产者写入。发射时读到的操作数因而与顺序语义一致,确定性算术得到同样结果或同样除零条件。

物理标签在仍有读取需要时不会回收,执行单元又捕获了实际操作数,所以其延迟期间后续映射变化不改变这次计算。发布只写本项独有目的标签,不覆盖别人的结果。异常项保持目的未就绪,使依赖它的年轻项继续等待,直到前缀退休逻辑把它们取消。

证明没有要求所有完成按年龄排序。年龄只在多个同时可发射或可发布的候选之间确定选择;数据正确性来自源身份与生命周期。更换合法仲裁策略可得到不同周期表,但必须另给公平性与资源进展论证。

有限进展的条件 ​

固定有限程序、正且有限的单元延迟、无外部资源等待。若ROB非空,考虑最老未退休项:它的真正数据依赖都来自更老指令,这些指令已退休,所以它的源一定就绪,除非它本身已经完成或正在运行。

如果所需单元被年轻项占用,该项输入早已捕获,有限延迟后会进入发布集合。每次端口从到期项中取最老者;有限程序只有有限个竞争项,不会永远越过某个已经到期的项。单元最终腾出,最老项可发射、发布,然后退休或触发异常。依次推进这条论证,所有正常前缀最终完成。

前端因ROB满或无空闲标签而停,不冻结后端;后端退休会归还资源。若全部状态一起停住,就破坏了上述进展条件。无限输入流、不可取消外部运算、可永久失联的存储系统不属于这个有限证明;本页没有给真实处理器的实时截止期保证。

从扫描参考器到硬件 ​

参考器按ROB年龄顺序扫描至多Q项选择发射,每项至多两个源;四个执行单元之间选发布项是常数规模。核心选择最坏为 O(Q+1) 字操作,重命名的最小空闲编号搜索另需 O(P)。默认显式结构检查也扫描映射、物理位置和ROB,因此一周期整体保守为 O(L+P+Q+1),再乘实际经过的周期数,而不是把一次扫描当作一个“硬件周期”就声称软件常数时间。

硬件可以并行比较标签、维护存在位和用选择电路,但要付比较器、端口、布线与功耗。源文的快速唤醒还会利用确定延迟旁路,本页没有这种提前预测:只在真正发布后置ready。STORE本单元无地址计算、load或缓存等待,不能把这张表拿去评价有完整存储队列的处理器。

参考资料
  1. Berkeley Out-of-Order Machine,The Issue Unit,官方实现文档,访问于2026-10-10;Issue Slot、Issue Select Logic、Age-ordered Issue Queue、Wake-up各节。作为标签存在、单元可用及年龄仲裁依据;本文单发射/单发布/四台非流水单元均为明示教学选择。
  2. James E. Smith、Andrew R. Pleszkun,Implementing Precise Interrupts in Pipelined Processors,1988,§IV-D,印刷567页:让未退休结果提前服务消费者,同时保持架构状态的顺序边界。本文直接保留物理版本,没有复刻其ROB数据旁路电路。
关系图谱5 个相邻概念 · 2 类关系

拖动节点调整位置。

显示关系

显示:依赖

  1. 前置三跳
  2. 前置二跳
  3. 前置一跳
  4. 当前条目
  5. 后续一跳
  6. 后续二跳
  7. 后续三跳
文字版关系按与当前条目的最短距离分组
类型化关系