zzgandClaude Opus 5.5
2a3a0284c5
A walkthrough of how a dependence DAG over a straight-line block decides which instruction orders are legal, and how a scheduler picks among them. Includes a property test that every topological order of a random program computes the same result as program order. Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com>
91 lines
3.2 KiB
Python
91 lines
3.2 KiB
Python
"""List scheduling: Kahn's algorithm with a clock and a priority.
|
|
|
|
The machine model is a single-issue, in-order pipeline: one instruction
|
|
issues per cycle, and an instruction cannot issue until every RAW producer's
|
|
latency has elapsed (see :meth:`DAG.delay`). In program order, a ``load``
|
|
followed immediately by its use stalls for 3 cycles; a scheduler fills those
|
|
cycles with independent work.
|
|
|
|
The list scheduler is Kahn's algorithm with two changes:
|
|
|
|
1. a node is *ready* only when its predecessors are emitted **and** their
|
|
results have arrived by the current cycle; if nothing is ready the
|
|
machine stalls for a cycle;
|
|
2. among ready nodes, pick the one with the longest latency-weighted path to
|
|
the end of the block (its *height*): delaying it delays everything after.
|
|
"""
|
|
|
|
from dataclasses import dataclass
|
|
from typing import Dict, List, Sequence
|
|
|
|
from .deps import DAG
|
|
|
|
|
|
def heights(dag: DAG) -> List[int]:
|
|
"""Latency-weighted longest path from each node to the end of the block."""
|
|
h = [0] * dag.n
|
|
for u in reversed(range(dag.n)): # program order is topological
|
|
h[u] = max([dag.instrs[u].latency] +
|
|
[dag.delay(u, v) + h[v] for v in dag.succ[u]])
|
|
return h
|
|
|
|
|
|
@dataclass
|
|
class Timing:
|
|
order: List[int]
|
|
issue: Dict[int, int] # instruction -> cycle it issued
|
|
cycles: int # cycle at which the last result is available
|
|
|
|
@property
|
|
def stalls(self) -> int:
|
|
"""Cycles in which nothing issued."""
|
|
return max(self.issue.values(), default=-1) + 1 - len(self.order)
|
|
|
|
def timeline(self, dag: DAG) -> str:
|
|
rows = []
|
|
prev = -1
|
|
for v in self.order:
|
|
for c in range(prev + 1, self.issue[v]):
|
|
rows.append(f" cycle {c:>2}: (stall)")
|
|
rows.append(f" cycle {self.issue[v]:>2}: {v:>2}: {dag.instrs[v].text()}")
|
|
prev = self.issue[v]
|
|
return "\n".join(rows)
|
|
|
|
|
|
def time_order(dag: DAG, order: Sequence[int]) -> Timing:
|
|
"""Simulate issuing ``order`` (which must be topological) in order."""
|
|
issue: Dict[int, int] = {}
|
|
t = 0
|
|
for v in order:
|
|
earliest = max([issue[u] + dag.delay(u, v) for u in dag.pred[v]], default=0)
|
|
issue[v] = max(t, earliest)
|
|
t = issue[v] + 1
|
|
done = max((issue[v] + dag.instrs[v].latency for v in order), default=0)
|
|
return Timing(list(order), issue, done)
|
|
|
|
|
|
def list_schedule(dag: DAG) -> Timing:
|
|
h = heights(dag)
|
|
remaining = {v: len(dag.pred[v]) for v in range(dag.n)}
|
|
avail_at: Dict[int, int] = {} # node -> first cycle its operands are ready
|
|
candidates = {v for v in range(dag.n) if remaining[v] == 0}
|
|
issue: Dict[int, int] = {}
|
|
order: List[int] = []
|
|
cycle = 0
|
|
while candidates:
|
|
ready = [v for v in candidates if avail_at.get(v, 0) <= cycle]
|
|
if not ready:
|
|
cycle += 1 # stall: everything eligible is waiting on a result
|
|
continue
|
|
u = max(ready, key=lambda v: (h[v], -v))
|
|
candidates.remove(u)
|
|
order.append(u)
|
|
issue[u] = cycle
|
|
for v in dag.succ[u]:
|
|
avail_at[v] = max(avail_at.get(v, 0), cycle + dag.delay(u, v))
|
|
remaining[v] -= 1
|
|
if remaining[v] == 0:
|
|
candidates.add(v)
|
|
cycle += 1
|
|
return time_order(dag, order)
|