Non-Determinism: Parallelism, Time and Randomness

Part II · Module 34 · Chapter 34.6 · Non-Determinism

Everything in this module so far has compared two things: a run against its replay, a log against a pattern, tonight against last night. Every one of those comparisons assumes that two runs of the same thing produce the same result, and this chapter checks that assumption rather than relying on it.

The answer on this fixture is not where anybody looks.

1. The Simulation Is Deterministic

Five runs of the same test with the same seed, byte-compared:

$ for i in 1 2 3 4 5; do ( cd nd/r$i && vvp ../../logs/sim.vvp \
      +TESTNAME=random +SEED=1 +CYCLES=200 ) > nd/r$i/run.log 2>&1; done
$ md5 -q nd/r*/run.log | sort -u | wc -l
       1

One distinct hash from five runs. And with a waveform, which contains timestamps:

$ md5 -q nd2/r*/dump.vcd | sort -u | wc -l
       1

One distinct hash from three. The simulator is a pure function of its inputs — the image, the plusargs, the seed — and nothing about wall-clock time, process ids or scheduling reaches its output.

That is worth establishing before anything else, because it licenses the whole of Chapter 33.2: a faithful replay really does reproduce, and a difference between two runs really is informative. If the simulator varied, every comparison in Module 32 and Module 33 would need a statistical treatment instead of a diff.

And it is not something to assume. Three lines establish it, and a flow whose tool is not a pure function of its inputs needs to know that before its first comparison, not after a week of chasing a difference that was never meaningful.

2. The Build Is Not

The tool that produced the image is a different story, measured in Chapter 33.1:

  build 1: 651e3cee1cba40c42538f8fa969f8a8d  27979 bytes
  build 2: 633e04c3bd5894d8ac06e884bd9c90d0  27979 bytes
  build 3: b83008632fe347299e1982e06b0e434c  27979 bytes
  distinct: 3

Three builds of identical sources, three different digests, 1,084 of 27,979 bytes apart — because the vvp assembly names its scopes after the compiler's own heap addresses:

S_0x7a5080000 .scope module, "tb_arb" "tb_arb" 2 3;
v0x7a50743c0_0 .

So the flow contains a stage that is deterministic in its behaviour and non-deterministic in its output. Two images built from the same sources run identically and compare differently.

3. The Completion Order Changes Every Time

Four jobs at four slots, three repetitions, recording the order in which they finished:

    rep 1: smoke random b2b fairness
    rep 2: smoke fairness b2b random
    rep 3: smoke b2b random fairness

Three repetitions, three different orders. smoke is always first because it is much the shortest; the other three finish in whatever order the scheduler and the page cache produce.

This is the non-determinism that actually bites, and it does not touch any single run's result. What it changes is everything the flow builds from the runs:

A results file appended in completion order is a different file every night, so diffing two nights' results reports every line as changed. Chapter 31.6's fix is already the answer — one file per run, merged by walking the matrix — and this is the measurement that says why ordering by completion is not merely untidy.

A report that lists failures in completion order puts the same problem in a different place each night, so a reader cannot skim it.

A "first failure" heuristic picks whichever failed earliest, which is a statement about scheduling. Chapter 29.2 is about the first error within a log, where the ordering is causal; across runs it is not.

And anything that stops at the first failure stops somewhere different each time, which is Chapter 34.7's subject and a genuine tension — fail-fast and reproducible-ordering pull against each other, and the resolution is to fail fast on infrastructure and complete on results.

4. The Four Sources, and What To Do With Each

  the simulation itself        deterministic
  a dump file                  deterministic
  date in a filename           VARIES by construction
  ls / glob order              sorted, stable
  parallel completion order    VARIES

Randomness: record, never remove

Chapter 31.3's whole argument. A seed from the clock is unreproducible; a seed from a list is a recorded input. And the trap measured in Chapter 32.1 is that recording a seed is not enough if the generator does not use it well:

    first draw, low 2 bits : 0=20 1=0 2=0 3=0
    first draw, bits 17:16 : 0=5 1=6 2=5 3=4   (a strict period-4 cycle)

The low two bits of $random's first draw were identical for all twenty seeds. A test keyed on them is deterministic while appearing to be swept — the opposite problem from this chapter's, and found by the same technique of measuring rather than assuming.

Time: remove from anything compared

A timestamp in a filename is fine and necessary — Chapter 32.2's run directories are named by one. A timestamp inside a compared artifact is not:

# in a results file, a report, or anything that gets diffed
# BAD:  printf 'run at %s\n' "$(date)" >> results.tsv
# fine: put it in env.txt, which is metadata and is never diffed

The rule is the one Chapter 32.5 arrived at: metadata beside the comparison, never inside it. And when a timestamp must appear in compared output, normalise it before comparing — Chapter 33.7's t=T, anchored so it does not eat a neighbouring field.

Glob order: stable here, and do not rely on it

  ls / glob order              sorted, stable

Bash sorts glob expansions, and ls sorts by default — so nd3/* gave nd3/a nd3/b nd3/c regardless of creation order. That is dependable on this machine and not dependable in general: the sort is affected by the locale, so LC_ALL=C and a system default collation can order the same filenames differently, which matters the moment a name contains an underscore or a capital.

LC_ALL=C   # in any script whose output is compared

One line, and it removes a class of difference that appears only when somebody runs the flow with a different locale.

5. What Cannot Be Removed

Two things, and both become recordings rather than removals.

The machine. Chapter 33.8 measured which facts about a node are gone within seconds — load, limits, free memory, PATH — and built the snapshot. A flow cannot make two nodes identical; it can make a difference between two runs attributable.

And contention. Chapter 31.5 measured eight heavy runs at 9.8 s against 43.8 s for one at a time, and the light-job sweep where the noise exceeded the effect — a 2.7× spread within one configuration. A runtime is not a reproducible number, and a flow that compares runtimes between nights is comparing two different machine loads.

Which gives the practical boundary for any comparison a flow makes:

The right-hand column is not "never look at these" — a runtime trend over ninety nights is exactly Chapter 32.8's subject. It is "do not treat a difference in these as a finding", which is a different and much weaker claim.

6. The Four Measurements, As One Tool

#!/bin/bash
# determinism -- the four measurements that say what a flow may compare.
# Run once per flow; record the answers in the flow's own documentation.
set -u
root=$(cd "$(dirname "$0")/.." && pwd)
w=$root/det; rm -rf "$w"; mkdir -p "$w"
hash_of() { md5 -q "$@" 2>/dev/null || md5sum "$@" | cut -d' ' -f1; }

printf '1. the same run, five times\n'
for i in 1 2 3 4 5; do
  mkdir -p "$w/r$i"
  ( cd "$w/r$i" && vvp "$root/logs/sim.vvp" +TESTNAME=random +SEED=1 +CYCLES=200 ) > "$w/r$i/run.log" 2>&1
done
n=$(hash_of "$w"/r*/run.log | sort -u | grep -c .)
printf '   %s distinct log hash(es) of 5 -> %s\n' "$n" \
  "$([ "$n" -eq 1 ] && echo 'the run is a function of its inputs' || echo 'THE RUN VARIES -- diffs are not meaningful')"

printf '2. the same sources, three builds\n'
for i in 1 2 3; do iverilog -o "$w/b$i.vvp" "$root/tb/tb_arb.v" "$root/rtl/arb.v" 2>/dev/null; done
n=$(hash_of "$w"/b*.vvp | sort -u | grep -c .)
printf '   %s distinct image hash(es) of 3 -> %s\n' "$n" \
  "$([ "$n" -eq 1 ] && echo 'the build is reproducible' || echo 'the build is NOT reproducible -- record source digests')"

printf '3. four parallel jobs, three repetitions\n'
for r in 1 2 3; do
  : > "$w/order$r.txt"
  # the paths go in as ARGUMENTS, not interpolated into the command string:
  # interpolating them made xargs refuse with "command line cannot be
  # assembled, too long", and the step then reported 0 orders as if clean.
  printf 'smoke\nfairness\nrandom\nb2b\n' \
    | xargs -P 4 -I{} /bin/bash -c '
        w=$1; root=$2; r=$3; t=$4
        mkdir -p "$w/p$t"
        ( cd "$w/p$t" && vvp "$root/logs/sim.vvp" +TESTNAME="$t" +SEED=1 +CYCLES=200 ) >/dev/null 2>&1
        printf "%s " "$t" >> "$w/order$r.txt"' _ "$w" "$root" "$r" {}
  [ -s "$w/order$r.txt" ] || { echo "   determinism: rep $r produced no output -- the probe failed" >&2; exit 2; }
  printf '   rep %s: %s\n' "$r" "$(cat "$w/order$r.txt")"
done
n=$(for r in 1 2 3; do cat "$w/order$r.txt"; echo; done | sort -u | grep -c .)
[ "$n" -gt 0 ] || { echo "   determinism: no orders recorded -- refusing to report" >&2; exit 2; }
printf '   %s distinct order(s) of 3 -> %s\n' "$n" \
  "$([ "$n" -eq 1 ] && echo 'completion order is stable here' || echo 'do NOT assemble artifacts in completion order')"

printf '4. one run alone against four in parallel\n'
t0=$(date +%s); ( cd "$w/r1" && vvp "$root/logs/sim.vvp" +TESTNAME=random +SEED=1 +CYCLES=200 ) >/dev/null 2>&1; t1=$(date +%s)
printf '   alone: %ss   (a runtime is not a reproducible number)\n' "$((t1-t0))"

1. the same run, five times
   1 distinct log hash(es) of 5 -> the run is a function of its inputs
2. the same sources, three builds
   3 distinct image hash(es) of 3 -> the build is NOT reproducible -- record source digests
3. four parallel jobs, three repetitions
   rep 1: smoke random fairness b2b
   rep 2: b2b fairness random smoke
   rep 3: b2b smoke random fairness
   3 distinct order(s) of 3 -> do NOT assemble artifacts in completion order
4. one run alone against four in parallel
   alone: 0s   (a runtime is not a reproducible number)

Three things about that script are worth more than its output.

It states a conclusion, not a number. 1 distinct log hash(es) of 5 -> the run is a function of its inputs is readable by somebody who did not write it, and that matters because this is a tool run once a year and consulted far more often.

It refuses on no data. Two lines:

[ -s "$w/order$r.txt" ] || { echo "   determinism: rep $r produced no output -- the probe failed" >&2; exit 2; }
…
[ "$n" -gt 0 ] || { echo "   determinism: no orders recorded -- refusing to report" >&2; exit 2; }

Both were added after the first version did exactly what Chapter 34.7 warns against.

And it is a single command. determinism is the kind of thing that gets skipped if it is four separate procedures in a document, and run if it is one script that prints four conclusions.

Practice

1. Run one test five times and compare the logs byte for byte.
2. Do the same with a waveform and compare those.
3. Say what the result licenses in the rest of your flow.
4. Build the same sources three times and compare the output digests.
5. If they differ, find where and identify what the compiler embedded.
6. Classify each stage of your flow into the three answers to "is the output a function of the input?"
7. Say what getting the second case wrong produces, and the third.
8. Run four jobs at four slots three times and record the completion order.
9. Explain why the shortest job is always first.
10. Name four things the flow builds that completion order makes unstable.
11. Build a results file in completion order, diff two runs of it, and count the changed lines.
12. Fix it by walking the matrix and diff again.
13. Record a seed explicitly rather than taking it from the clock.
14. Measure your generator's first draw across twenty consecutive seeds.
15. Put a timestamp inside a compared artifact and then diff two runs.
16. Move it to metadata and diff again.
17. Normalise a timestamp in something that must contain one.
18. Check your glob order with and without LC_ALL=C.
19. Set LC_ALL=C in a script whose output is compared, and say what it removes.
20. Snapshot the machine and list which facts are gone within seconds.
21. Time one heavy run alone and eight in parallel, and compute the ratio.
22. Write down which quantities your flow may compare and which it may not.
23. Do all four establishing measurements and record the answers in your flow's documentation.

Check Your Understanding

1. What assumption does every comparison in this module rest on?
2. What did five runs of the same simulation produce?
3. What about three runs with a waveform?
4. What does that license?
5. Why is it worth establishing rather than assuming?
6. What did three builds of identical sources produce, and why?
7. So which stage is deterministic in behaviour but not in output?
8. State the question to ask of any flow stage.
9. Give the three possible answers and their consequences.
10. What does getting the second case wrong produce? And the third?
11. What did three repetitions of four parallel jobs produce?
12. Why is one job always first?
13. Name four things the flow builds that this destabilises.
14. Why is a "first failure across runs" heuristic a statement about scheduling?
15. What tension does fail-fast have with reproducible ordering, and how is it resolved?
16. For randomness, is the answer to remove or record?
17. What was measured about $random's first draw, and why does recording a seed not fix it?
18. Where may a timestamp appear, and where may it not?
19. What is the rule about metadata?
20. Is glob order stable here? Is it dependable in general?
21. What does LC_ALL=C remove?
22. Which two sources cannot be removed, and what replaces removal?
23. Why is a runtime not a reproducible number?
24. Give four quantities a flow may compare and four it may not.
25. What is the weaker claim about the second list?
26. Give the four establishing measurements.

7. Remember

• Measure determinism; do not assume it. Five runs of this simulation were byte-identical, and so were three waveforms.
• That result licenses every diff in the flow — and a flow whose tool varies needs to know before its first comparison.
• The compiler is not reproducible: three builds, three digests, 1,084 bytes apart, because the output embeds heap addresses.
• Ask of every stage: is the output a function of the input? Yes → the digest is an identity. No but the behaviour is → record the inputs. Neither → a diff is meaningless.
• Parallel completion order changed on all three repetitions. It does not affect a run's result and destabilises everything the flow assembles from runs.
• One file per run, merged by walking the matrix — the fix, and this is why it is not merely tidiness.
• Record randomness, remove time. A seed from a list, never the clock — and check that the generator actually uses it.
• Timestamps in filenames and metadata, never inside compared artifacts.
• Set LC_ALL=C in anything whose output is compared: glob order is sorted here and locale-dependent in general.
• The machine and contention cannot be removed, only recorded. A runtime is not a reproducible number.
• Compare verdicts, counts, signatures and the matrix. Do not treat differences in runtimes, ordering or artifact bytes as findings.
• Four measurements, ten minutes: repeat a run, repeat a build, repeat a parallel batch, and time alone against loaded.

8. What Is Next

Chapter 34.7 closes the module with the habit all six of the others depend on: stopping at the first unrecoverable problem with a message that names it. It measures two flows on a source that does not compile — one that says so and returns 4, and one that prints RESULT: PASS.