A new memory controller returns read data out of order, as its protocol allows: reads with different IDs may complete in any order. The testbench's scoreboard, written for the old in-order controller, compares each response with the oldest outstanding read. It now reports hundreds of mismatches per test. Hidden among them are two real bugs. Nobody can find them, because the scoreboard is wrong about what "correct" means.
How does a scoreboard match responses to requests when the protocol allows them to return out of order?
The obvious scoreboard keeps one queue of expected responses in request order and pops the head for each response. It encodes an ordering rule the protocol does not make. With out-of-order completion, nearly every response is compared with the wrong expectation. Loosening it the other way, by searching all outstanding requests for any match, is worse: it accepts responses delivered to the wrong ID, duplicates and reorderings the protocol forbids.
Reference model: predicts each request's correct response (data, status) from the request and the model's state.
Find the matching rule in the specification. Two kinds of label look alike but match differently. A unique tag (DCLink, PCIe) names one transaction: at most one request holds it at a time, so the scoreboard keeps one expectation per tag and a response must match that one. A shared ID (AXI) names an ordering domain: many transactions may carry it at once and must complete in order, so the scoreboard keeps one queue per ID and a response matches the oldest entry in its queue.
Match: each response is compared with the expectation its label selects: the tag's single entry, or the head of the ID's queue.
Report: data mismatches, responses with no expectation (duplicates, wrong IDs), and, at the end of the test, expectations never satisfied (lost responses).
The model issues 400 reads, at most four outstanding, each taking a free tag (0 to 3) that its completion returns; the responder answers after a random delay, so completions come back in any order. Three bugs are planted: one completion with wrong data, one delivered twice, and one never delivered. Both scoreboards check the same stream of monitored requests and completions.
"""DCLink step 12c: an ordering-aware scoreboard for tagged reads.
The requester issues reads using tags 0-3 from a free list (DCLink step 5): a tag is
unique while its read is outstanding, and the completion that answers it frees it.
The responder answers each read after a random delay, so completions return in any
order. Monitors turn both directions into one stream of events in time order, and a
reference model predicts each read's data. Two scoreboards check the same stream:
in-order: compares each completion with the oldest outstanding read
by-tag: keeps the one outstanding read of each tag, checks each completion
against it, and at the end of the test reports every read still waiting
The responder is correct except for three injected bugs: one completion carries wrong
data, one is delivered twice, and one is never delivered.
"""
import random
rng = random.Random(7)
N = 400
def ref_data(addr):
return (addr * 2654435761) & 0xFFFF # the reference model's prediction
# Requester and responder, cycle by cycle, recording what the monitors see
free, pending, events = [0, 1, 2, 3], [], [] # events: ("req", tag, addr) or ("cpl", tag, data)
issued = delivered = 0
for cyc in range(100000):
if issued < N and free: # issue one read if a tag is free
tag, addr = free.pop(0), rng.randrange(1 << 12)
events.append(("req", tag, addr)); issued += 1
pending.append((cyc + rng.randrange(2, 12), tag, addr))
for p in [p for p in pending if p[0] <= cyc]: # responder: deliver what is due
pending.remove(p)
_, tag, addr = p
data = ref_data(addr)
delivered += 1
if delivered == 100:
data ^= 0x0004 # bug 1: wrong data
if delivered == 300:
continue # bug 3: completion lost; its tag stays in use
events.append(("cpl", tag, data))
if delivered == 200:
events.append(("cpl", tag, data)) # bug 2: delivered twice
free.append(tag) # the requester frees the tag
if issued == N and not pending:
break
def in_order(evs):
outstanding, errors = [], 0
for kind, tag, val in evs:
if kind == "req":
outstanding.append((tag, val))
elif not outstanding:
errors += 1
else:
t, addr = outstanding.pop(0)
if t != tag or ref_data(addr) != val:
errors += 1
return errors + len(outstanding) # leftovers count too
def by_tag(evs):
expected, errors, n, k = {}, [], 0, -1 # expected: tag -> (read number, addr)
for kind, tag, val in evs:
k += kind == "cpl" # k: completion number
if kind == "req":
if tag in expected:
errors.append((f"read {n}", tag, "tag reused while outstanding"))
expected[tag] = (n, val); n += 1
elif tag not in expected:
errors.append((f"completion {k}", tag, "unexpected: no read outstanding on this tag"))
else:
seq, addr = expected.pop(tag)
if ref_data(addr) != val:
errors.append((f"completion {k}", tag, f"data mismatch for read {seq}"))
for tag, (seq, _) in sorted(expected.items()): # end of test: drain check
errors.append(("end of test", tag, f"missing completion for read {seq}"))
return errors
cpls = sum(1 for e in events if e[0] == "cpl")
ino, bt = in_order(events), by_tag(events)
print(f"reads issued: {N}, completions seen: {cpls}")
print(f"in-order scoreboard: {ino} errors reported")
print(f"by-tag scoreboard: {len(bt)} errors reported")
for where, tag, why in bt:
print(f" {where} (tag {tag}): {why}")
assert ino > 100 # swamped by false mismatches
assert [why.split(" ")[0] for _, _, why in bt] == ["data", "unexpected:", "missing"]
print("PASS: the in-order scoreboard drowns in false errors; matching by unique tag reports exactly the three injected bugs")It prints:
reads issued: 400, completions seen: 400
in-order scoreboard: 255 errors reported
by-tag scoreboard: 3 errors reported
completion 99 (tag 0): data mismatch for read 97
completion 200 (tag 1): unexpected: no read outstanding on this tag
end of test (tag 0): missing completion for read 299
PASS: the in-order scoreboard drowns in false errors; matching by unique tag reports exactly the three injected bugsThe in-order scoreboard reports 255 errors, almost all false: it assumes completions come back in request order, which DCLink never promised. The tag scoreboard reports exactly three, one per bug. The wrong data is a mismatch against read 97. The duplicate arrives when tag 1 has nothing outstanding, so it is unexpected. The lost completion produces no event at all, so no per-completion check can see it; only the end-of-test drain check, which lists every read still waiting, finds it. A scoreboard without that last loop passes a test in which a response vanished.
Scoreboard | Accepts | Problem |
|---|---|---|
Single in-order queue | Only fully in-order responses | False errors when reordering is allowed |
Search all outstanding | Any response that matches any request | Misses wrong-ID, duplicate and illegal reorder bugs |
One queue per shared ID | Exactly the reorderings the protocol allows | Must know the ordering rules (IDs, channels); right for AXI |
One entry per unique tag | Responses carrying a tag that is outstanding | Right only when tags are unique while outstanding (DCLink, PCIe); flag a tag reused while outstanding |
Protocol | Matching rule |
|---|---|
AXI | A queue per ID: same-ID transactions complete in order, different IDs in any order (fact A20) |
PCI Express | Completions matched by tag; the parts of one split read arrive in address order (facts P24, P25) |
DCLink | One outstanding read per tag (step 5), so one entry per tag, plus an end-of-test drain check: this model |
The opening controller (illustrative) was being verified with a scoreboard that someone had "fixed" by searching all outstanding reads for a match. Its error count dropped to zero. It also stopped detecting a real bug: responses for ID 2 occasionally overtook earlier ID 2 responses, which the protocol forbids. Rebuilding it with one queue per ID found the bug on the first run.
Legal: different IDs may reorder. The ID 2 response matches ID 2's only read; the two ID 1 responses match ID 1's reads in issue order.
by_tag. What does the model report now?Two errors, and the lost completion goes unnoticed: a completion that never arrives triggers no comparison. Only the drain check (or a response timeout) can see something that did not happen.
A mismatch against the next read in ID 3's queue, and then a mismatch for every later ID 3 response, because the queue is now one step out. Report the first as the cause and count the rest separately. DCLink's unique tags avoid this: the duplicate finds nothing outstanding and is reported once as unexpected.
A scoreboard compares responses with a reference model's predictions, matched exactly as the protocol orders them.
Match by unique tag, or one queue per shared ID, as the protocol defines; report mismatches, unexpected responses and, at the end, missing ones.
Too strict gives false errors; too loose accepts illegal behaviour.