Three engineers write three scoreboards for the same router. The first checks that every output shows its packets in the order they were sent: strict, simple, and wrong for a router that interleaves inputs. The second checks only that every packet arrived somewhere at its output, in any order: tolerant, simple, and blind to a swap within a stream. The third keeps one queue per stream. All three compile, and all three pass some tests.
How should a check handle outputs that may legally arrive out of order?
The obvious choices are the extremes: exact order (too strict, lesson 2.7) or no order at all (too loose). Both are wrong for most interconnects, which promise order within something (a flow, an ID, an address) and nothing across it. The scoreboard must match by exactly that domain, and it must still catch the four ways outputs go wrong: dropped, duplicated, reordered within the domain, or delivered to the wrong place.
A model router sends 200 packets from 4 inputs to 4 outputs, interleaving flows at random but keeping each flow in order. Three scoreboards judge the legal run and four broken copies of it.
"""Checking reordered outputs: three scoreboards, one legal run and four broken ones.
A router model forwards packets from 4 inputs to 4 outputs. Within one flow (input, output)
order is kept; at each output, packets from different inputs interleave in whatever order the
arbiter picked. Three scoreboards judge the output streams:
global expects each output to show its packets in the order they were sent (by send time)
per-flow keeps one queue per (input, output) and checks each arriving packet against the
oldest expected packet of its flow; at the end, every queue must be empty
bag checks only that each output received the same set of packets, in any order
The runs: a legal run, then the same run with one packet dropped, one duplicated, two packets
of one flow swapped, and one packet sent to the wrong output.
"""
import random
rng = random.Random(5)
SENT = [(t, rng.randrange(4), rng.randrange(4)) for t in range(200)] # (seq, src, dst)
def route(sent):
"""Legal behaviour: per output, a random interleaving that keeps each flow in order."""
outs = {o: [] for o in range(4)}
for o in range(4):
flows = {s: [p for p in sent if p[1] == s and p[2] == o] for s in range(4)}
while any(flows.values()):
s = rng.choice([s for s in flows if flows[s]])
outs[o].append(flows[s].pop(0))
return outs
def global_order(sent, outs):
return all(outs[o] == [p for p in sent if p[2] == o] for o in range(4))
def per_flow(sent, outs):
exp = {}
for p in sent:
exp.setdefault((p[1], p[2]), []).append(p)
for o in range(4):
for p in outs[o]:
q = exp.get((p[1], o), [])
if not q or q[0] != p:
return False
q.pop(0)
return all(not q for q in exp.values())
def bag(sent, outs):
return all(sorted(outs[o]) == sorted(p for p in sent if p[2] == o) for o in range(4))
legal = route(SENT)
def mutate(kind):
outs = {o: list(v) for o, v in legal.items()}
o = max(range(4), key=lambda k: len(outs[k]))
if kind == "drop":
outs[o].pop(len(outs[o]) // 2)
elif kind == "duplicate":
outs[o].insert(5, outs[o][4])
elif kind == "swap within flow":
s = outs[o][0][1]
i, j = [k for k, p in enumerate(outs[o]) if p[1] == s][:2]
outs[o][i], outs[o][j] = outs[o][j], outs[o][i]
elif kind == "wrong output":
p = outs[o].pop(3)
outs[(o + 1) % 4].append(p)
return outs
runs = {"legal interleaving": legal}
for k in ["drop", "duplicate", "swap within flow", "wrong output"]:
runs[k] = mutate(k)
print(f"{'run':20s} {'global':>8s} {'per-flow':>9s} {'bag':>6s}")
verdict = {}
for name, outs in runs.items():
v = [global_order(SENT, outs), per_flow(SENT, outs), bag(SENT, outs)]
verdict[name] = v
print(f"{name:20s} " + " ".join(f"{'pass' if x else 'FAIL':>8s}" for x in v))
assert verdict["legal interleaving"] == [False, True, True] # global: a false failure
assert all(not verdict[k][1] for k in runs if k != "legal interleaving") # per-flow: catches all four
assert verdict["swap within flow"][2] # bag: misses the reordering
print("PASS: only the per-flow scoreboard passes the legal run and fails all four broken ones")It prints:
run global per-flow bag
legal interleaving FAIL pass pass
drop FAIL FAIL FAIL
duplicate FAIL FAIL FAIL
swap within flow FAIL FAIL pass
wrong output FAIL FAIL FAIL
PASS: only the per-flow scoreboard passes the legal run and fails all four broken onesHow to read it: the global-order scoreboard fails the legal run: a false failure every time the arbiter interleaves differently. The bag scoreboard passes a run where two packets of one flow were swapped: a false pass. Only the per-flow scoreboard is right on all five, which is why DCRouter's environment keeps one queue per (input, output) flow.
Interface | Order promised within | Match by |
|---|---|---|
DCRouter | A flow (input, output) | Source and destination |
AXI | Transactions with the same ID | ID |
A memory controller | Accesses to the same address | Address |
A network on chip | A virtual channel or flow | Flow ID |
An in-order bus | Everything | One queue |
Bounds, not exact cycles: "a response within 10 cycles", checked with an assertion or a timestamp per transaction (lesson 2.7).
Timestamps in the scoreboard: record when each prediction was made and check the matching output's delay against the bound.
Deadlines for everything outstanding: a prediction older than its bound is a failure, even if the output never arrives (lesson 5.7).
Fairness as bounded waiting: "at most 3 others go first", as lesson 5.10's arbitration checker does.
Practice | Purpose |
|---|---|
Scoreboards keyed by the protocol's ordering domain | Legal reordering never fails; illegal reordering always does |
Identity carried in every transaction (IDs, sequence numbers) | Unambiguous matching and clear messages |
Timestamps and timeouts on predictions | Timing bounds and lost transactions caught in the same structure |
A scoreboard (illustrative) for an AXI interconnect matched read data by address instead of ID. Two reads to the same address with different IDs could legally complete in either order; the scoreboard paired them by address, reported a mismatch whenever they crossed, and the team spent a week chasing a design bug that did not exist. Matching by the protocol's actual ordering domain, the ID, removed the false failures.
The swap within a flow: the same packets arrive at the same output, just in the wrong order, and a set comparison ignores order.
It expects each output's packets in send order across all inputs, but the router legally interleaves different inputs' packets in a different order.
Match outputs by the ordering domain the specification promises (flow, ID, address).
Strict global order gives false failures; unordered comparison gives false passes.
Check timing as bounds with timestamps, and treat overdue predictions as failures.