dbglab's random test fails on seed 17: the scoreboard reads an unknown value from RAM word 816 at cycle 7949. Suppose you have not yet walked back from it (the symptom, fault and cause lesson does). An engineer spends the morning trying things. Every run below is real:
$ tb/run.sh random 17
dbglab: test=random seed=17
FAIL test=random seed=17 cycle=7949: SCOREBOARD: RAM word 816 (address 00001cc0) read xxxxxxxx, expected 00000000 (last written by DMA run #4)
$ tb/run.sh random 17
dbglab: test=random seed=17
FAIL test=random seed=17 cycle=7949: SCOREBOARD: RAM word 816 (address 00001cc0) read xxxxxxxx, expected 00000000 (last written by DMA run #4)
$ tb/run.sh random 17 verilator
dbglab: test=random seed=17
PASS test=random seed=17 cycles=18442 time=184416 ns
$ tb/run.sh random 18
dbglab: test=random seed=18
PASS test=random seed=18 cycles=19229 time=192286 ns
$ tb/run.sh random 17 icarus +OPS=3000
dbglab: test=random seed=17
FAIL test=random seed=17 cycle=7949: SCOREBOARD: RAM word 816 (address 00001cc0) read xxxxxxxx, expected 00000000 (last written by DMA run #4)Five runs, and the engineer's notes say: fails in Icarus only, seed-dependent, maybe a simulator issue. What did those five runs actually rule out?
Changing something to see what happens feels like progress, because every run produces output. But a run is only worth the surprise in its result. Look at the five again:
Experiment | What you could predict before running it | What it ruled out |
|---|---|---|
Rerun seed 17 | FAIL, identically: the bench is deterministic | nothing |
Rerun seed 17 again | the same | nothing |
Seed 17 in Verilator | unclear, so a real question | something real (the result depends on how the simulator starts unreset flip-flops), but it was read as "an Icarus bug" |
Seed 18 | nothing about seed 17: different stimulus | nothing about this failure |
Seed 17 with 3,000 operations | FAIL at the same cycle: the failure is already inside the first 1,500 | nothing |
Four of the five had a result you could have written down in advance. The fifth carried real information and was misread because it changed two things at once (the simulator and, with it, how unknown values behave). None of them reduced the list of places the bug could be. This is guessing: experiments chosen because they are easy, not because of what they could tell you.
A run that ends in PASS or FAIL answers one yes-or-no question. If, before running it, you think FAIL has probability p, the information you can expect from it is
which is 1 bit when p = 0.5 and close to 0 when you are nearly sure: about 0.008 bits for a 1-in-1,500 chance. Each bit halves the suspects. So N equally likely suspects need at least
and you get there only if every run is a fair coin toss. The rules that follow from this:
Write the suspects down as a list or a range: cycles, operations, commits, modules, seeds. A search needs a space.
Before each run, predict. Say what PASS would rule out and what FAIL would rule out. If one answer is nearly certain, pick another experiment.
Split the suspects evenly. The run whose two outcomes each leave half the suspects is worth a full bit, the most a yes-or-no run can give.
Change one thing at a time. A run that changes two things gives one answer to two questions.
Make the question monotone. Halving works when "wrong by point n" stays true for every later point. Check the two ends before you start.
Automate it. A halving search is mechanical. A script runs it while you think about the result.
Random pokes start well: when almost everything is a suspect, any test cuts something. Then they stall. With two suspects left, only one length in 1,500 tells them apart, so each poke has a 1-in-1,500 chance of being useful. Halving never stalls, because it always tests the middle of what is left.
The random test runs 1,500 operations, and +OPS=<n> stops it after n. At the end of every test the bench compares the whole RAM against its model, so a run with +OPS=n asks: is the state already wrong after n operations? Once the state is wrong it stays wrong, so the question is monotone. The suspects are operations 1 to 1,500; the one we want is the first after which the answer is yes.
Check the ends first. +OPS=0 runs no operations and passes (10 cycles); 1,500 fails, as reported. Then search:
# not-run: drives dbglab's tb/run.sh, so it must run from a dbglab checkout (output below is from a real run)
"""Find the shortest prefix of a failing random test that still fails.
usage: ops_search.py halve|poke <seed> <ops> (run from the dbglab folder)
Each experiment is one real run: tb/run.sh random <seed> $SIM +OPS=<n> (SIM defaults to icarus).
The suspects are the operations 1..<ops>: the one whose run first leaves the design wrong.
halve: test the middle of the suspects that are left.
poke: test a random length each time, ignoring what earlier runs said."""
import os, random, subprocess, sys
mode, seed, ops = sys.argv[1], int(sys.argv[2]), int(sys.argv[3])
def fails(n):
r = subprocess.run(["tb/run.sh", "random", str(seed), os.environ.get("SIM", "icarus"), f"+OPS={n}"],
capture_output=True, text=True)
return r.returncode == 1
lo, hi = 0, ops # known: OPS=lo passes (0 runs nothing), OPS=hi fails
runs = 0
rng = random.Random(1)
while hi - lo > 1:
n = (lo + hi) // 2 if mode == "halve" else rng.randint(1, ops)
runs += 1
bad = fails(n)
if bad and n < hi: hi = n
if not bad and n > lo: lo = n
if mode == "halve" or os.environ.get("ALL") or runs % 100 == 0 or hi - lo == 1:
print(f"run {runs:4d}: OPS={n:4d} {'FAIL' if bad else 'pass'} suspects left: {hi - lo:4d} (ops {lo + 1}..{hi})")
print(f"{runs} runs: operation {hi} is the first that leaves the design wrong")$ python3 ../search/ops_search.py halve 17 1500
run 1: OPS= 750 FAIL suspects left: 750 (ops 1..750)
run 2: OPS= 375 FAIL suspects left: 375 (ops 1..375)
run 3: OPS= 187 FAIL suspects left: 187 (ops 1..187)
run 4: OPS= 93 FAIL suspects left: 93 (ops 1..93)
run 5: OPS= 46 FAIL suspects left: 46 (ops 1..46)
run 6: OPS= 23 pass suspects left: 23 (ops 24..46)
run 7: OPS= 34 pass suspects left: 12 (ops 35..46)
run 8: OPS= 40 pass suspects left: 6 (ops 41..46)
run 9: OPS= 43 pass suspects left: 3 (ops 44..46)
run 10: OPS= 44 pass suspects left: 2 (ops 45..46)
run 11: OPS= 45 FAIL suspects left: 1 (ops 45..45)
11 runs: operation 45 is the first that leaves the design wrongRead the column of suspects: 750, 375, 187, 93, 46, 23, 12, 6, 3, 2, 1. Every run halved it, whether it passed or failed. Eleven runs, close to the 10.6 the formula promised, and each Icarus run of a short prefix takes a fraction of a second.
Now the same knob, poked at random:
$ python3 ../search/ops_search.py poke 17 1500
run 100: OPS= 90 FAIL suspects left: 26 (ops 20..45)
run 200: OPS= 792 FAIL suspects left: 10 (ops 36..45)
run 300: OPS= 546 FAIL suspects left: 2 (ops 44..45)
run 400: OPS= 82 FAIL suspects left: 2 (ops 44..45)
run 500: OPS= 66 FAIL suspects left: 2 (ops 44..45)
run 600: OPS= 952 FAIL suspects left: 2 (ops 44..45)
run 670: OPS= 44 pass suspects left: 1 (ops 45..45)
670 runs: operation 45 is the first that leaves the design wrongThe same answer, 61 times the runs. Between run 212 and run 670 the pokes were down to operations 44 and 45, and only OPS=44 could split them. Most of those 458 runs had a result you could have predicted: FAIL.
Look at what the eleventh run printed, because a search result is a new, much smaller report:
$ tb/run.sh random 17 icarus +OPS=44
dbglab: test=random seed=17
PASS test=random seed=17 cycles=484 time=4836 ns
$ tb/run.sh random 17 icarus +OPS=45
dbglab: test=random seed=17
FAIL test=random seed=17 cycle=535: SCOREBOARD (final sweep): RAM word 810 (address 00001ca8) holds xxxxxxxx, expected 00000000 (last written by DMA run #4)Operation 45 starts DMA run #4. After 44 operations (484 cycles) the RAM is right; after 45 it holds an X at word 810, the first word of that run. The failure that showed up at cycle 7949 is now pinned to one DMA run starting near cycle 484, and the next experiment is obvious: look at what run #4 was told to do. That is the walk back the symptom lesson takes, and it lands on the FILL register.
The same halving works on every axis you can order and test automatically. On dbglab's 16 commits, bisection in history finds a guilty commit in four runs; Part 3 halves time, the design hierarchy and the stimulus.
Halving needs about log2 200, so 8 runs, 4 hours unattended, with a guaranteed answer. Checking five likely commits costs 5 runs, and if the guess is wrong it rules out only 5 of 200 and you still need about 8 more. A hunch is worth testing first only when you would bet heavily on it; otherwise it is a 1-in-40 poke.
It carries about 0.29 bits (H(0.95)), so less than a third of a halving step. Run it only if the 5% outcome would change your plan, or if it costs almost nothing. Otherwise design an experiment whose outcome you genuinely cannot predict.
dbglab at HEAD 49c5f04 (rebuilt with dbglab/build-history.sh), Icarus Verilog 13.0 and Verilator 5.048, 2026-10-17. Guesses: tb/run.sh random 17 twice (FAIL at cycle 7949 both times), tb/run.sh random 17 verilator (PASS), tb/run.sh random 18 (PASS), tb/run.sh random 17 icarus +OPS=3000 (FAIL at cycle 7949).
Search: python3 ops_search.py halve 17 1500 (the script shown, run from the dbglab folder) made 11 runs and named operation 45; python3 ops_search.py poke 17 1500 (random lengths from random.Random(1)) made 670 runs and named operation 45, and a second run gave the same 670. Check: +OPS=44 passes (484 cycles), +OPS=45 and +OPS=46 fail at cycle 535.
Limits: one failure, one knob. The poke count depends on the random generator's seed; the expected count is what matters, and it grows with N while halving grows with log2 N. The engineer's guesses in the scene are illustrative; their runs are real.