💻 CSC3060 Project: Code Scheduling


Code Scheduling

这个项目的主题是 code scheduling (指令调度)：在不改变程序语义的前提下，重新排列指令顺序，让总执行周期更短。目标是在保持依赖关系前提下尽量隐藏长指令的等待时间、优先安排关键路径上的指令 。


Code Scheduling 以少量的 compile-time 为代价换来显著的 runtime 提升。说到 compilation……


  • 调度过程：解析指令、制作依赖图、计算优先级、产出最终调度方案

  • 重要性：不同指令延迟不同，例如 lw、mul 通常比 add、jal 慢。如果仅仅是按原始顺序傻等，就会产生空泡 (idle cycles, bubbles)。调度器在等待某些长延迟指令时，把其他独立指令塞进去执行。


Static Latency Model 静态延迟模型

我们假设每类指令有一个固定 latency，调度器据此估计什么时候结果可用。虽然真实硬件里同一条指令的耗时不固定，但 SLM 给调度器一个简单、稳定的简化近似，指导依赖分析和重排。

SLM 的延迟明显是一种 “平均情况” 下的估计。真实延迟的波动不太影响 SLM 的工作，一是你可以将 “延迟” 类比为 A*/Dijkstra 等最优寻路算法中的 “权重”，能反映相对代价即可；二是如果估测值粗糙的反映大体趋势 (命令之间的相对时间开销)，类似于 Amdahl’s Law，速度优化会很明显，而追求精确不仅失去泛用性，且去会出现显著边际效应。

  • 乘法可拆成“生成部分积 + 逐级相加”，通常在 3～4 周期；而除法每一位都反复比较、做减法、再移位取新一位、然后商位修正，效率很低，在十甚至数十周期量级。
  • load 指令在缓存命中情况下最优可到 5 周期，而 store 永远是 1 周期。这是因为 load 会修改寄存器，产生 RAW 依赖，即后续某些 Read 指令需等待这个前序 load 指令从主存把数据搬到寄存器。而 store 不会动寄存器，所以没有产生依赖性也不必等待。


Dependency DAG

依赖图把每条指令看成一个节点并用有向边表示指令间的依赖/顺序。例如：I0 → I3 表示 I3 依赖 I0，I0 不能排在 I3 后面。

为什么一定是 Directed Acyclic Graph?

因为依赖表示的是一种拓扑顺序关系。如果图里有环，比如：A → B, B → C, C → A，这样环中任何指令都不能先执行，调度无解。

哪里需要有边可以通过分析指令间的寄存器依赖得到——


数据流依赖：RAW (Read After Write)

RAW 表示后续的指令要读前面指令写出的寄存器值。这是一种 “真依赖” (数据依赖)，后继必须等前驱指令彻底完成，而这会带来真实的延迟。RAW 也是唯一有具体延迟的依赖 (而不是只要求有顺序性)。

例如：

I0: lw  x1, 0(x5)
I1: add x3, x1, x2
  • I1 读取 x1，而 x1 是 I0 写的，所以 I1 对 I0 有 RAW 依赖，I1 开始时间必须晚于 “I0 开始时间 +5cycles”。
  • 通常会维护一个 LastWriter[reg]，对读同一寄存器的后继建立 RAW。

反依赖：WAR (Write After Read)

WAR 表示前面的指令先读某寄存器，后面的指令又写同一个寄存器。这是一种 “反依赖”，即前序指令反过来依赖后续指令执行的足够晚。WAR 不要求等待具体时间，只要求顺序约束 (order-only dependency)。

例如：

I0: add x3, x1, x2
I1: li  x1, 0

  • 如果把 I1 提前到 I0 前面，I0 读到的就不是原来的 x1 了，所以 I1 开始时间必须晚于 “I0 开始时间”。

  • 通常是维护某种 LastReaders[reg] 结构。当遇到一个写寄存器的指令时，对之前尚需约束的所有 reader 建 WAR 边。


输出依赖：WAW (Write After Write)

WAW 表示两条指令都写同一个寄存器，必须保持写入顺序。这也是一种 “反依赖”，也是 “输出依赖”，即只依赖最终写的结果的正确性。WAW 不要求等待具体时间，只要求顺序约束 (order-only dependency)。

例如：

I0: li x1, 5
I1: li x1, 9

  • 最终程序要保留最后一次写的结果，如果乱序就会破坏最终寄存器值，所以 I1 开始时间必须晚于 “I0 开始时间”。

  • 通常会维护一个 LastWriter[reg]，对写同一寄存器的后继建立 WAW 边。


总结下来，画 DAG 要做的事情就是：（Bonus：可以一次性做完）

  • RAW：当前要 读，去找之前最近的 写，连 RAW 依赖边；
  • WAW：当前要 写，去找之前最近的 写，连 WAW 依赖边；
  • WAR：当前要 写，去找之前⚠️所有相关的读，全部连 WAR 依赖边。

为什么 WAR 要找先前全部读者？

→ 你怎么知道这些前序 “读” 指令有没有乱序？所以 WAR 通常需要的是 list of readers，而不只是单个 last reader。

为什么 WAR 和 WAW 不需要延迟？

→ WAR 和 WAW 只有顺序约束，因为它们都只保证 “覆盖寄存器” 的安全性，不需要读前序指令的结果。通过保证前序指令先开始执行，两个指令的顺序就固定了，就不需要额外等待时间。

为什么没有 RAR (Read After Read)?

→ 两个 “读” 都不会改变寄存器内容，便不存在依赖。前后交换顺序不影响正确性，就没有必要存在这种依赖边。

⚠️注意：如果一个指令既读又写同个寄存器，比如 add x1, x1, x2，不能被自动检测为自己对自己有依赖，否则就会形成自环 (loop)，导致卡死。



*项目的简化假设

我们为了把项目做得清晰、教学化，它使用了非常简化的执行模型：

  • 所有依赖都只看寄存器依赖
  • 没有 memory aliasing
  • 单线程
  • 没有控制流 / 异常 / side effects
  • 指令对内存是原子的

在这个模型里：

寄存器是唯一共享状态，因此 correctness 约束就等价于 RAW/WAR/WAW。

而因为现实世界更复杂：store / load 可能通过内存地址 alias 形成依赖、多线程里 lock / release 顺序非常关键、只看寄存器会漏掉真实约束 …… 如果没有这些简化假设，寄存器 DAG 就不够了。



Priority: Critical Path Length

为什么，怎么算 priority?

当多个节点都 ready 时，调度器要知道先发哪个，我们选用的 priority 是 Critical Path Length。 CPL (Priority) = 从当前节点到任一出口节点的最长路径长度（即时间开销）。

因为关键路径越长说明后面还有更多依赖工作在等它——越早安排它越能尽早解锁后续指令并降低总时间。

只有 RAW 是有真实延迟要求的，故 CPL 不是无脑所有边都加 latency：

  • 对 RAW successors：要加上当前节点 latency；
  • 对 WAR/WAW successors：不加当前 latency，只保留顺序关系 。


List Scheduling 列表调度

这是本项目最核心的算法部分，这是最经典的调度算法之一。

  • ready 集合：当前所有前驱约束已经满足，可以被开始的节点。
  • inflight 集合：已经开始但还没结束的节点，形式大致是：(node, finish_cycle)

算法流程

  1. 初始化 cycle = 0
  2. 把所有 unscheduled_predecessors = 0 的点放进 ready
  3. 每个 cycle：
    • 如果 ready 非空，选一个 best 节点 issue
    • 把它加入 inflight，记录 finish cycle
    • 对 WAR/WAW successors：issue 时立即释放
  4. cycle 自增
  5. 检查 inflight 中哪些节点在这个 cycle retire
    • 对这些节点的 RAW successors：finish 时释放
  6. 重复直到所有节点都 schedule 完成

再次强调——什么时候 release successor：

  • RAW successor 只能在 predecessor 完成时释放：因为后继真的需要前驱产生的数据。

  • WAR / WAW successor 可以在 predecessor 开始时释放：因为这类边只管顺序，不涉及结果返回。



完整示例

用一个 5 条指令的例子展示整个流程：

1 I0: lw x1 , 0( x5)     ; latency =5, writes x1
2 I1: lw x2 , 4( x5)     ; latency =5, writes x2
3 I2: add x3 , x6 , x7   ; latency =1, independent
4 I3: mul x4 , x1 , x2   ; latency =3, reads x1 , x2
5 I4: sw x4 , 8( x5)     ; latency =1, reads x4

分析：先是两个独立的 lw，然后一个独立 add，一个依赖两个 lw 的 mul，最后是一个依赖 mul 的 sw。

得到 DAG：I0 → I3、I1 → I3、I3 → I4、I2 独立 。

计算 CPL：priority(I4) = 1，priority(I3) = 3 + 1 = 4，priority(I0) = 5 + 4 = 9，priority(I1) = 5 + 4 = 9。所以 CPL Priority 等于 9。

⚠️ 但考虑资源约束，由于我们的前提是 single-issue scheduler，每个周期只能发射 (开始) 一个任务，I0 和 I1 必有一个在第二周期才能开始，故：max(finish_time(I0), finish_time(I1)) + latency(I3) + latency(I4) = 6 + 3 + 1 = 10，最短完成时间下界等于 10。

Scheduling：{I0, I1, I2, I3, I4}。虽然最终 issue 顺序恰好和原程序一样，但调度器把独立的 I2 塞进了 load 等待期间，从而隐藏了两周期空转。文档明确说这是在fill idle slot、hide latency。

调度优化不一定表现为“大幅改变程序顺序”，根本目的是聪明地利用空档。



Tie-Breaking Policy 同优先级时如何选择

当多个 ready node 的 priority 一样时，需要进一步决定先发谁——用三种策略做一个多级比较器 (selectBestNode())

  1. SMALLER_INDEX：选原始程序顺序里 index 更小的节点。优点：更接近原程序顺序，属于 “保守型 tie-breaker”。

  2. MOST_CHILD：选后继 (successors) 更多的节点。 优点：如果一个节点能解锁更多后续指令，先执行它会让更多节点更早 ready，提升填充延迟 bubble 的概率。

  3. LPT (Longest Processing Time)：选 latency 最长的节点。 优点：长延迟指令越早开始，后面的指令越可能填充这延迟 bubble。当 ready 集合长/短延迟都有，而后续工作能覆盖长延迟时，LPT 往往优于 Index。

比较并择优 MOST_CHILD 和 LPT，如果还相等就用 SMALLER_INDEX 做最终 tie-breaker。



Complexity Analysis

(假设有 N 个命令节点和 E 个依赖边)

1. naive list scheduling：如果每一轮都扫所有节点找 ready nodes，那么复杂度会比较高：O(N2+E)

2. recursive memoized priority calculation：CPL 如果用“递归 + 记忆化”，通常每个点和边只会被有效处理有限次，复杂度近似于 O(N+E)


comments powered by Disqus