FA-88966 / Digital logic simulation / Open access
Arrival time taken from the earliest fanin · case 01
Reported slack is optimistic and the critical path follows a short branch.
ROOT CAUSE
Arrival propagation merges fanins with min instead of max.
VERIFIED REPAIR
Arrival at a gate is its delay plus the latest fanin arrival.
Unsuccessful approach: Averaging fanin arrivals is still optimistic whenever the fanins are unbalanced.
Case contract
Input [pis, gates, outs, period, setup]: pis maps input -> arrival time; gates are [name, delay, fanins] in topological order. arrival(g) = delay + max fanin arrival. required(g) = min over fanout gates m of (required(m) - delay(m)), plus period - setup if g is an output. Slack = required - arrival over gates. Return [worst slack, critical path, sorted [gate, slack]] where the path ends at the output with least slack (ties by name) and walks back through the fanin with the latest arrival (ties by smallest name) to a primary input.
Why this case matters
Static timing engines back-propagate required times through fanout trees; min/max confusion and delay attribution errors change the reported critical path.
1 / The failure
Exit 1"""Failure Map reference implementation. Python standard library only."""
import json
N = 1
observations = []
def solve(*args):
pis, gates, outs, period, setup = args
arr = dict(pis)
g = {name: (dl, fi) for name, dl, fi in gates}
order = [name for name, _, _ in gates]
for n in order:
dl, fi = g[n]
arr[n] = dl + min(arr[f] for f in fi)
req = {}
for n in reversed(order):
fos = [m for m in order if n in g[m][1]]
cands = [req[m] - g[m][0] for m in fos]
if n in outs:
cands.append(period - setup)
req[n] = min(cands)
slack = {n: req[n] - arr[n] for n in req}
worst = min(slack.values())
end = min(outs, key=lambda n: (slack[n], n))
path = [end]
while path[-1] in g:
fi = g[path[-1]][1]
path.append(max(sorted(fi), key=lambda f: arr[f]))
return [worst, path[::-1], [[k, slack[k]] for k in sorted(slack)]]
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[('diamond with shared fanout', [{'a': 0, 'b': 1, 'c': 1}, [['g1', 2, ['a', 'b']], ['g2', 3, ['b', 'c']], ['g3', 1, ['g1', 'g2']], ['g4', 4, ['g1']]], ['g3', 'g4'], 12, 1], [4, ['b', 'g1', 'g4'], [['g1', 4], ['g2', 6], ['g3', 6], ['g4', 4]]]), ('diamond tighter period', [{'a': 2, 'b': 0, 'c': 1}, [['g1', 2, ['a', 'b']], ['g2', 3, ['b', 'c']], ['g3', 1, ['g1', 'g2']], ['g4', 4, ['g1']]], ['g3', 'g4'], 9, 2], [-1, ['a', 'g1', 'g4'], [['g1', -1], ['g2', 2], ['g3', 2], ['g4', -1]]]), ('long branch through internal output', [{'a': 0, 'b': 1}, [['u', 5, ['a']], ['v', 1, ['b']], ['w', 2, ['v', 'u']], ['x', 1, ['w']], ['y', 6, ['v']]], ['w', 'x', 'y'], 10, 1], [1, ['a', 'u', 'w'], [['u', 1], ['v', 1], ['w', 1], ['x', 1], ['y', 1]]]), ('internal output with fanout', [{'a': 1, 'b': 1}, [['u', 5, ['a']], ['v', 1, ['b']], ['w', 2, ['v', 'u']], ['x', 1, ['w']], ['y', 6, ['v']]], ['x', 'y', 'v'], 10, 0], [1, ['a', 'u', 'w', 'x'], [['u', 1], ['v', 2], ['w', 1], ['x', 1], ['y', 2]]]), ('reconvergent unequal branches', [{'a': 0, 'c': 1}, [['p', 1, ['a', 'c']], ['q', 1, ['p']], ['r', 7, ['p']], ['s', 1, ['q', 'r']]], ['s'], 12, 1], [1, ['c', 'p', 'r', 's'], [['p', 1], ['q', 7], ['r', 1], ['s', 1]]]), ('reconvergent with late input', [{'a': 3, 'c': 1}, [['p', 1, ['a', 'c']], ['q', 1, ['p']], ['r', 7, ['p']], ['s', 1, ['q', 'r']]], ['s', 'q'], 14, 2], [0, ['a', 'p', 'r', 's'], [['p', 0], ['q', 6], ['r', 0], ['s', 0]]])], [('diamond with shared fanout', [{'a': 0, 'b': 2, 'c': 1}, [['g1', 2, ['a', 'b']], ['g2', 3, ['b', 'c']], ['g3', 1, ['g1', 'g2']], ['g4', 4, ['g1']]], ['g3', 'g4'], 12, 1], [3, ['b', 'g1', 'g4'], [['g1', 3], ['g2', 5], ['g3', 5], ['g4', 3]]]), ('diamond tighter period', [{'a': 2, 'b': 0, 'c': 2}, [['g1', 2, ['a', 'b']], ['g2', 3, ['b', 'c']], ['g3', 1, ['g1', 'g2']], ['g4', 4, ['g1']]], ['g3', 'g4'], 10, 2], [0, ['a', 'g1', 'g4'], [['g1', 0], ['g2', 2], ['g3', 2], ['g4', 0]]]), ('long branch through internal output', [{'a': 0, 'b': 2}, [['u', 5, ['a']], ['v', 1, ['b']], ['w', 2, ['v', 'u']], ['x', 1, ['w']], ['y', 6, ['v']]], ['w', 'x', 'y'], 10, 1], [0, ['b', 'v', 'y'], [['u', 1], ['v', 0], ['w', 1], ['x', 1], ['y', 0]]]), ('internal output with fanout', [{'a': 2, 'b': 1}, [['u', 5, ['a']], ['v', 1, ['b']], ['w', 2, ['v', 'u']], ['x', 1, ['w']], ['y', 6, ['v']]], ['x', 'y', 'v'], 11, 0], [1, ['a', 'u', 'w', 'x'], [['u', 1], ['v', 3], ['w', 1], ['x', 1], ['y', 3]]]), ('reconvergent unequal branches', [{'a': 0, 'c': 1}, [['p', 1, ['a', 'c']], ['q', 1, ['p']], ['r', 7, ['p']], ['s', 1, ['q', 'r']]], ['s'], 13, 1], [2, ['c', 'p', 'r', 's'], [['p', 2], ['q', 8], ['r', 2], ['s', 2]]]), ('reconvergent with late input', [{'a': 3, 'c': 2}, [['p', 1, ['a', 'c']], ['q', 1, ['p']], ['r', 7, ['p']], ['s', 1, ['q', 'r']]], ['s', 'q'], 14, 2], [0, ['a', 'p', 'r', 's'], [['p', 0], ['q', 6], ['r', 0], ['s', 0]]])], [('diamond with shared fanout', [{'a': 0, 'b': 3, 'c': 1}, [['g1', 2, ['a', 'b']], ['g2', 3, ['b', 'c']], ['g3', 1, ['g1', 'g2']], ['g4', 4, ['g1']]], ['g3', 'g4'], 12, 1], [2, ['b', 'g1', 'g4'], [['g1', 2], ['g2', 4], ['g3', 4], ['g4', 2]]]), ('diamond tighter period', [{'a': 2, 'b': 0, 'c': 3}, [['g1', 2, ['a', 'b']], ['g2', 3, ['b', 'c']], ['g3', 1, ['g1', 'g2']], ['g4', 4, ['g1']]], ['g3', 'g4'], 11, 2], [1, ['a', 'g1', 'g4'], [['g1', 1], ['g2', 2], ['g3', 2], ['g4', 1]]]), ('long branch through internal output', [{'a': 0, 'b': 0}, [['u', 5, ['a']], ['v', 1, ['b']], ['w', 2, ['v', 'u']], ['x', 1, ['w']], ['y', 6, ['v']]], ['w', 'x', 'y'], 10, 1], [1, ['a', 'u', 'w'], [['u', 1], ['v', 2], ['w', 1], ['x', 1], ['y', 2]]]), ('internal output with fanout', [{'a': 3, 'b': 1}, [['u', 5, ['a']], ['v', 1, ['b']], ['w', 2, ['v', 'u']], ['x', 1, ['w']], ['y', 6, ['v']]], ['x', 'y', 'v'], 12, 0], [1, ['a', 'u', 'w', 'x'], [['u', 1], ['v', 4], ['w', 1], ['x', 1], ['y', 4]]]), ('reconvergent unequal branches', [{'a': 0, 'c': 1}, [['p', 1, ['a', 'c']], ['q', 1, ['p']], ['r', 7, ['p']], ['s', 1, ['q', 'r']]], ['s'], 14, 1], [3, ['c', 'p', 'r', 's'], [['p', 3], ['q', 9], ['r', 3], ['s', 3]]]), ('reconvergent with late input', [{'a': 3, 'c': 3}, [['p', 1, ['a', 'c']], ['q', 1, ['p']], ['r', 7, ['p']], ['s', 1, ['q', 'r']]], ['s', 'q'], 14, 2], [0, ['a', 'p', 'r', 's'], [['p', 0], ['q', 6], ['r', 0], ['s', 0]]])], [('diamond with shared fanout', [{'a': 0, 'b': 4, 'c': 1}, [['g1', 2, ['a', 'b']], ['g2', 3, ['b', 'c']], ['g3', 1, ['g1', 'g2']], ['g4', 4, ['g1']]], ['g3', 'g4'], 12, 1], [1, ['b', 'g1', 'g4'], [['g1', 1], ['g2', 3], ['g3', 3], ['g4', 1]]]), ('diamond tighter period', [{'a': 2, 'b': 0, 'c': 4}, [['g1', 2, ['a', 'b']], ['g2', 3, ['b', 'c']], ['g3', 1, ['g1', 'g2']], ['g4', 4, ['g1']]], ['g3', 'g4'], 12, 2], [2, ['c', 'g2', 'g3'], [['g1', 2], ['g2', 2], ['g3', 2], ['g4', 2]]]), ('long branch through internal output', [{'a': 0, 'b': 1}, [['u', 5, ['a']], ['v', 1, ['b']], ['w', 2, ['v', 'u']], ['x', 1, ['w']], ['y', 6, ['v']]], ['w', 'x', 'y'], 10, 1], [1, ['a', 'u', 'w'], [['u', 1], ['v', 1], ['w', 1], ['x', 1], ['y', 1]]]), ('internal output with fanout', [{'a': 4, 'b': 1}, [['u', 5, ['a']], ['v', 1, ['b']], ['w', 2, ['v', 'u']], ['x', 1, ['w']], ['y', 6, ['v']]], ['x', 'y', 'v'], 13, 0], [1, ['a', 'u', 'w', 'x'], [['u', 1], ['v', 5], ['w', 1], ['x', 1], ['y', 5]]]), ('reconvergent unequal branches', [{'a': 0, 'c': 1}, [['p', 1, ['a', 'c']], ['q', 1, ['p']], ['r', 7, ['p']], ['s', 1, ['q', 'r']]], ['s'], 15, 1], [4, ['c', 'p', 'r', 's'], [['p', 4], ['q', 10], ['r', 4], ['s', 4]]]), ('reconvergent with late input', [{'a': 3, 'c': 4}, [['p', 1, ['a', 'c']], ['q', 1, ['p']], ['r', 7, ['p']], ['s', 1, ['q', 'r']]], ['s', 'q'], 14, 2], [-1, ['c', 'p', 'r', 's'], [['p', -1], ['q', 5], ['r', -1], ['s', -1]]])], [('diamond with shared fanout', [{'a': 0, 'b': 5, 'c': 1}, [['g1', 2, ['a', 'b']], ['g2', 3, ['b', 'c']], ['g3', 1, ['g1', 'g2']], ['g4', 4, ['g1']]], ['g3', 'g4'], 12, 1], [0, ['b', 'g1', 'g4'], [['g1', 0], ['g2', 2], ['g3', 2], ['g4', 0]]]), ('diamond tighter period', [{'a': 2, 'b': 0, 'c': 5}, [['g1', 2, ['a', 'b']], ['g2', 3, ['b', 'c']], ['g3', 1, ['g1', 'g2']], ['g4', 4, ['g1']]], ['g3', 'g4'], 13, 2], [2, ['c', 'g2', 'g3'], [['g1', 3], ['g2', 2], ['g3', 2], ['g4', 3]]]), ('long branch through internal output', [{'a': 0, 'b': 2}, [['u', 5, ['a']], ['v', 1, ['b']], ['w', 2, ['v', 'u']], ['x', 1, ['w']], ['y', 6, ['v']]], ['w', 'x', 'y'], 10, 1], [0, ['b', 'v', 'y'], [['u', 1], ['v', 0], ['w', 1], ['x', 1], ['y', 0]]]), ('internal output with fanout', [{'a': 5, 'b': 1}, [['u', 5, ['a']], ['v', 1, ['b']], ['w', 2, ['v', 'u']], ['x', 1, ['w']], ['y', 6, ['v']]], ['x', 'y', 'v'], 14, 0], [1, ['a', 'u', 'w', 'x'], [['u', 1], ['v', 6], ['w', 1], ['x', 1], ['y', 6]]]), ('reconvergent unequal branches', [{'a': 0, 'c': 1}, [['p', 1, ['a', 'c']], ['q', 1, ['p']], ['r', 7, ['p']], ['s', 1, ['q', 'r']]], ['s'], 16, 1], [5, ['c', 'p', 'r', 's'], [['p', 5], ['q', 11], ['r', 5], ['s', 5]]]), ('reconvergent with late input', [{'a': 3, 'c': 5}, [['p', 1, ['a', 'c']], ['q', 1, ['p']], ['r', 7, ['p']], ['s', 1, ['q', 'r']]], ['s', 'q'], 14, 2], [-2, ['c', 'p', 'r', 's'], [['p', -2], ['q', 4], ['r', -2], ['s', -2]]])]]
for label, args, expected in fixtures[N-1]:
check(label, solve(*args), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)
| Boundary fixture | Actual | Expected | Outcome |
|---|---|---|---|
| diamond with shared fanout | [5, ['b', 'g1', 'g4'], [['g1', 5], ['g2', 6], ['g3', 8], ['g4', 5]]] | [4, ['b', 'g1', 'g4'], [['g1', 4], ['g2', 6], ['g3', 6], ['g4', 4]]] | Failed |
| diamond tighter period | [1, ['a', 'g1', 'g4'], [['g1', 1], ['g2', 3], ['g3', 4], ['g4', 1]]] | [-1, ['a', 'g1', 'g4'], [['g1', -1], ['g2', 2], ['g3', 2], ['g4', -1]]] | Failed |
| long branch through internal output | [1, ['b', 'v', 'y'], [['u', 1], ['v', 1], ['w', 4], ['x', 4], ['y', 1]]] | [1, ['a', 'u', 'w'], [['u', 1], ['v', 1], ['w', 1], ['x', 1], ['y', 1]]] | Failed |
| internal output with fanout | [1, ['b', 'v'], [['u', 1], ['v', 2], ['w', 5], ['x', 5], ['y', 2]]] | [1, ['a', 'u', 'w', 'x'], [['u', 1], ['v', 2], ['w', 1], ['x', 1], ['y', 2]]] | Failed |
| reconvergent unequal branches | [2, ['c', 'p', 'r', 's'], [['p', 2], ['q', 8], ['r', 2], ['s', 8]]] | [1, ['c', 'p', 'r', 's'], [['p', 1], ['q', 7], ['r', 1], ['s', 1]]] | Failed |
| reconvergent with late input | [2, ['a', 'p', 'q'], [['p', 2], ['q', 8], ['r', 2], ['s', 8]]] | [0, ['a', 'p', 'r', 's'], [['p', 0], ['q', 6], ['r', 0], ['s', 0]]] | Failed |
SHA-256 / bcb2a293798f0e665c6a95ac1bb5d91530a52621fa7acf4ca753e3eb4fa12666
2 / The unsuccessful fix
Exit 1"""Failure Map reference implementation. Python standard library only."""
import json
N = 1
observations = []
def solve(*args):
pis, gates, outs, period, setup = args
arr = dict(pis)
g = {name: (dl, fi) for name, dl, fi in gates}
order = [name for name, _, _ in gates]
for n in order:
dl, fi = g[n]
arr[n] = dl + sum(arr[f] for f in fi) // len(fi)
req = {}
for n in reversed(order):
fos = [m for m in order if n in g[m][1]]
cands = [req[m] - g[m][0] for m in fos]
if n in outs:
cands.append(period - setup)
req[n] = min(cands)
slack = {n: req[n] - arr[n] for n in req}
worst = min(slack.values())
end = min(outs, key=lambda n: (slack[n], n))
path = [end]
while path[-1] in g:
fi = g[path[-1]][1]
path.append(max(sorted(fi), key=lambda f: arr[f]))
return [worst, path[::-1], [[k, slack[k]] for k in sorted(slack)]]
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[('diamond with shared fanout', [{'a': 0, 'b': 1, 'c': 1}, [['g1', 2, ['a', 'b']], ['g2', 3, ['b', 'c']], ['g3', 1, ['g1', 'g2']], ['g4', 4, ['g1']]], ['g3', 'g4'], 12, 1], [4, ['b', 'g1', 'g4'], [['g1', 4], ['g2', 6], ['g3', 6], ['g4', 4]]]), ('diamond tighter period', [{'a': 2, 'b': 0, 'c': 1}, [['g1', 2, ['a', 'b']], ['g2', 3, ['b', 'c']], ['g3', 1, ['g1', 'g2']], ['g4', 4, ['g1']]], ['g3', 'g4'], 9, 2], [-1, ['a', 'g1', 'g4'], [['g1', -1], ['g2', 2], ['g3', 2], ['g4', -1]]]), ('long branch through internal output', [{'a': 0, 'b': 1}, [['u', 5, ['a']], ['v', 1, ['b']], ['w', 2, ['v', 'u']], ['x', 1, ['w']], ['y', 6, ['v']]], ['w', 'x', 'y'], 10, 1], [1, ['a', 'u', 'w'], [['u', 1], ['v', 1], ['w', 1], ['x', 1], ['y', 1]]]), ('internal output with fanout', [{'a': 1, 'b': 1}, [['u', 5, ['a']], ['v', 1, ['b']], ['w', 2, ['v', 'u']], ['x', 1, ['w']], ['y', 6, ['v']]], ['x', 'y', 'v'], 10, 0], [1, ['a', 'u', 'w', 'x'], [['u', 1], ['v', 2], ['w', 1], ['x', 1], ['y', 2]]]), ('reconvergent unequal branches', [{'a': 0, 'c': 1}, [['p', 1, ['a', 'c']], ['q', 1, ['p']], ['r', 7, ['p']], ['s', 1, ['q', 'r']]], ['s'], 12, 1], [1, ['c', 'p', 'r', 's'], [['p', 1], ['q', 7], ['r', 1], ['s', 1]]]), ('reconvergent with late input', [{'a': 3, 'c': 1}, [['p', 1, ['a', 'c']], ['q', 1, ['p']], ['r', 7, ['p']], ['s', 1, ['q', 'r']]], ['s', 'q'], 14, 2], [0, ['a', 'p', 'r', 's'], [['p', 0], ['q', 6], ['r', 0], ['s', 0]]])], [('diamond with shared fanout', [{'a': 0, 'b': 2, 'c': 1}, [['g1', 2, ['a', 'b']], ['g2', 3, ['b', 'c']], ['g3', 1, ['g1', 'g2']], ['g4', 4, ['g1']]], ['g3', 'g4'], 12, 1], [3, ['b', 'g1', 'g4'], [['g1', 3], ['g2', 5], ['g3', 5], ['g4', 3]]]), ('diamond tighter period', [{'a': 2, 'b': 0, 'c': 2}, [['g1', 2, ['a', 'b']], ['g2', 3, ['b', 'c']], ['g3', 1, ['g1', 'g2']], ['g4', 4, ['g1']]], ['g3', 'g4'], 10, 2], [0, ['a', 'g1', 'g4'], [['g1', 0], ['g2', 2], ['g3', 2], ['g4', 0]]]), ('long branch through internal output', [{'a': 0, 'b': 2}, [['u', 5, ['a']], ['v', 1, ['b']], ['w', 2, ['v', 'u']], ['x', 1, ['w']], ['y', 6, ['v']]], ['w', 'x', 'y'], 10, 1], [0, ['b', 'v', 'y'], [['u', 1], ['v', 0], ['w', 1], ['x', 1], ['y', 0]]]), ('internal output with fanout', [{'a': 2, 'b': 1}, [['u', 5, ['a']], ['v', 1, ['b']], ['w', 2, ['v', 'u']], ['x', 1, ['w']], ['y', 6, ['v']]], ['x', 'y', 'v'], 11, 0], [1, ['a', 'u', 'w', 'x'], [['u', 1], ['v', 3], ['w', 1], ['x', 1], ['y', 3]]]), ('reconvergent unequal branches', [{'a': 0, 'c': 1}, [['p', 1, ['a', 'c']], ['q', 1, ['p']], ['r', 7, ['p']], ['s', 1, ['q', 'r']]], ['s'], 13, 1], [2, ['c', 'p', 'r', 's'], [['p', 2], ['q', 8], ['r', 2], ['s', 2]]]), ('reconvergent with late input', [{'a': 3, 'c': 2}, [['p', 1, ['a', 'c']], ['q', 1, ['p']], ['r', 7, ['p']], ['s', 1, ['q', 'r']]], ['s', 'q'], 14, 2], [0, ['a', 'p', 'r', 's'], [['p', 0], ['q', 6], ['r', 0], ['s', 0]]])], [('diamond with shared fanout', [{'a': 0, 'b': 3, 'c': 1}, [['g1', 2, ['a', 'b']], ['g2', 3, ['b', 'c']], ['g3', 1, ['g1', 'g2']], ['g4', 4, ['g1']]], ['g3', 'g4'], 12, 1], [2, ['b', 'g1', 'g4'], [['g1', 2], ['g2', 4], ['g3', 4], ['g4', 2]]]), ('diamond tighter period', [{'a': 2, 'b': 0, 'c': 3}, [['g1', 2, ['a', 'b']], ['g2', 3, ['b', 'c']], ['g3', 1, ['g1', 'g2']], ['g4', 4, ['g1']]], ['g3', 'g4'], 11, 2], [1, ['a', 'g1', 'g4'], [['g1', 1], ['g2', 2], ['g3', 2], ['g4', 1]]]), ('long branch through internal output', [{'a': 0, 'b': 0}, [['u', 5, ['a']], ['v', 1, ['b']], ['w', 2, ['v', 'u']], ['x', 1, ['w']], ['y', 6, ['v']]], ['w', 'x', 'y'], 10, 1], [1, ['a', 'u', 'w'], [['u', 1], ['v', 2], ['w', 1], ['x', 1], ['y', 2]]]), ('internal output with fanout', [{'a': 3, 'b': 1}, [['u', 5, ['a']], ['v', 1, ['b']], ['w', 2, ['v', 'u']], ['x', 1, ['w']], ['y', 6, ['v']]], ['x', 'y', 'v'], 12, 0], [1, ['a', 'u', 'w', 'x'], [['u', 1], ['v', 4], ['w', 1], ['x', 1], ['y', 4]]]), ('reconvergent unequal branches', [{'a': 0, 'c': 1}, [['p', 1, ['a', 'c']], ['q', 1, ['p']], ['r', 7, ['p']], ['s', 1, ['q', 'r']]], ['s'], 14, 1], [3, ['c', 'p', 'r', 's'], [['p', 3], ['q', 9], ['r', 3], ['s', 3]]]), ('reconvergent with late input', [{'a': 3, 'c': 3}, [['p', 1, ['a', 'c']], ['q', 1, ['p']], ['r', 7, ['p']], ['s', 1, ['q', 'r']]], ['s', 'q'], 14, 2], [0, ['a', 'p', 'r', 's'], [['p', 0], ['q', 6], ['r', 0], ['s', 0]]])], [('diamond with shared fanout', [{'a': 0, 'b': 4, 'c': 1}, [['g1', 2, ['a', 'b']], ['g2', 3, ['b', 'c']], ['g3', 1, ['g1', 'g2']], ['g4', 4, ['g1']]], ['g3', 'g4'], 12, 1], [1, ['b', 'g1', 'g4'], [['g1', 1], ['g2', 3], ['g3', 3], ['g4', 1]]]), ('diamond tighter period', [{'a': 2, 'b': 0, 'c': 4}, [['g1', 2, ['a', 'b']], ['g2', 3, ['b', 'c']], ['g3', 1, ['g1', 'g2']], ['g4', 4, ['g1']]], ['g3', 'g4'], 12, 2], [2, ['c', 'g2', 'g3'], [['g1', 2], ['g2', 2], ['g3', 2], ['g4', 2]]]), ('long branch through internal output', [{'a': 0, 'b': 1}, [['u', 5, ['a']], ['v', 1, ['b']], ['w', 2, ['v', 'u']], ['x', 1, ['w']], ['y', 6, ['v']]], ['w', 'x', 'y'], 10, 1], [1, ['a', 'u', 'w'], [['u', 1], ['v', 1], ['w', 1], ['x', 1], ['y', 1]]]), ('internal output with fanout', [{'a': 4, 'b': 1}, [['u', 5, ['a']], ['v', 1, ['b']], ['w', 2, ['v', 'u']], ['x', 1, ['w']], ['y', 6, ['v']]], ['x', 'y', 'v'], 13, 0], [1, ['a', 'u', 'w', 'x'], [['u', 1], ['v', 5], ['w', 1], ['x', 1], ['y', 5]]]), ('reconvergent unequal branches', [{'a': 0, 'c': 1}, [['p', 1, ['a', 'c']], ['q', 1, ['p']], ['r', 7, ['p']], ['s', 1, ['q', 'r']]], ['s'], 15, 1], [4, ['c', 'p', 'r', 's'], [['p', 4], ['q', 10], ['r', 4], ['s', 4]]]), ('reconvergent with late input', [{'a': 3, 'c': 4}, [['p', 1, ['a', 'c']], ['q', 1, ['p']], ['r', 7, ['p']], ['s', 1, ['q', 'r']]], ['s', 'q'], 14, 2], [-1, ['c', 'p', 'r', 's'], [['p', -1], ['q', 5], ['r', -1], ['s', -1]]])], [('diamond with shared fanout', [{'a': 0, 'b': 5, 'c': 1}, [['g1', 2, ['a', 'b']], ['g2', 3, ['b', 'c']], ['g3', 1, ['g1', 'g2']], ['g4', 4, ['g1']]], ['g3', 'g4'], 12, 1], [0, ['b', 'g1', 'g4'], [['g1', 0], ['g2', 2], ['g3', 2], ['g4', 0]]]), ('diamond tighter period', [{'a': 2, 'b': 0, 'c': 5}, [['g1', 2, ['a', 'b']], ['g2', 3, ['b', 'c']], ['g3', 1, ['g1', 'g2']], ['g4', 4, ['g1']]], ['g3', 'g4'], 13, 2], [2, ['c', 'g2', 'g3'], [['g1', 3], ['g2', 2], ['g3', 2], ['g4', 3]]]), ('long branch through internal output', [{'a': 0, 'b': 2}, [['u', 5, ['a']], ['v', 1, ['b']], ['w', 2, ['v', 'u']], ['x', 1, ['w']], ['y', 6, ['v']]], ['w', 'x', 'y'], 10, 1], [0, ['b', 'v', 'y'], [['u', 1], ['v', 0], ['w', 1], ['x', 1], ['y', 0]]]), ('internal output with fanout', [{'a': 5, 'b': 1}, [['u', 5, ['a']], ['v', 1, ['b']], ['w', 2, ['v', 'u']], ['x', 1, ['w']], ['y', 6, ['v']]], ['x', 'y', 'v'], 14, 0], [1, ['a', 'u', 'w', 'x'], [['u', 1], ['v', 6], ['w', 1], ['x', 1], ['y', 6]]]), ('reconvergent unequal branches', [{'a': 0, 'c': 1}, [['p', 1, ['a', 'c']], ['q', 1, ['p']], ['r', 7, ['p']], ['s', 1, ['q', 'r']]], ['s'], 16, 1], [5, ['c', 'p', 'r', 's'], [['p', 5], ['q', 11], ['r', 5], ['s', 5]]]), ('reconvergent with late input', [{'a': 3, 'c': 5}, [['p', 1, ['a', 'c']], ['q', 1, ['p']], ['r', 7, ['p']], ['s', 1, ['q', 'r']]], ['s', 'q'], 14, 2], [-2, ['c', 'p', 'r', 's'], [['p', -2], ['q', 4], ['r', -2], ['s', -2]]])]]
for label, args, expected in fixtures[N-1]:
check(label, solve(*args), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)
| Boundary fixture | Actual | Expected | Outcome |
|---|---|---|---|
| diamond with shared fanout | [5, ['b', 'g1', 'g4'], [['g1', 5], ['g2', 6], ['g3', 7], ['g4', 5]]] | [4, ['b', 'g1', 'g4'], [['g1', 4], ['g2', 6], ['g3', 6], ['g4', 4]]] | Failed |
| diamond tighter period | [0, ['a', 'g1', 'g4'], [['g1', 0], ['g2', 3], ['g3', 3], ['g4', 0]]] | [-1, ['a', 'g1', 'g4'], [['g1', -1], ['g2', 2], ['g3', 2], ['g4', -1]]] | Failed |
| long branch through internal output | [1, ['b', 'v', 'y'], [['u', 1], ['v', 1], ['w', 3], ['x', 3], ['y', 1]]] | [1, ['a', 'u', 'w'], [['u', 1], ['v', 1], ['w', 1], ['x', 1], ['y', 1]]] | Failed |
| internal output with fanout | [1, ['b', 'v'], [['u', 1], ['v', 2], ['w', 3], ['x', 3], ['y', 2]]] | [1, ['a', 'u', 'w', 'x'], [['u', 1], ['v', 2], ['w', 1], ['x', 1], ['y', 2]]] | Failed |
| reconvergent unequal branches | [2, ['c', 'p', 'r', 's'], [['p', 2], ['q', 8], ['r', 2], ['s', 5]]] | [1, ['c', 'p', 'r', 's'], [['p', 1], ['q', 7], ['r', 1], ['s', 1]]] | Failed |
| reconvergent with late input | [1, ['a', 'p', 'r', 's'], [['p', 1], ['q', 7], ['r', 1], ['s', 4]]] | [0, ['a', 'p', 'r', 's'], [['p', 0], ['q', 6], ['r', 0], ['s', 0]]] | Failed |
SHA-256 / 13a457439a323e35afc10951a376d334ba649e82be7bb01643798fb9676f7249
3 / The verified repair
Exit 0"""Failure Map reference implementation. Python standard library only."""
import json
N = 1
observations = []
def solve(*args):
pis, gates, outs, period, setup = args
arr = dict(pis)
g = {name: (dl, fi) for name, dl, fi in gates}
order = [name for name, _, _ in gates]
for n in order:
dl, fi = g[n]
arr[n] = dl + max(arr[f] for f in fi)
req = {}
for n in reversed(order):
fos = [m for m in order if n in g[m][1]]
cands = [req[m] - g[m][0] for m in fos]
if n in outs:
cands.append(period - setup)
req[n] = min(cands)
slack = {n: req[n] - arr[n] for n in req}
worst = min(slack.values())
end = min(outs, key=lambda n: (slack[n], n))
path = [end]
while path[-1] in g:
fi = g[path[-1]][1]
path.append(max(sorted(fi), key=lambda f: arr[f]))
return [worst, path[::-1], [[k, slack[k]] for k in sorted(slack)]]
def check(label, actual, expected):
observations.append({"check": label, "actual": actual, "expected": expected, "passed": actual == expected})
fixtures = [[('diamond with shared fanout', [{'a': 0, 'b': 1, 'c': 1}, [['g1', 2, ['a', 'b']], ['g2', 3, ['b', 'c']], ['g3', 1, ['g1', 'g2']], ['g4', 4, ['g1']]], ['g3', 'g4'], 12, 1], [4, ['b', 'g1', 'g4'], [['g1', 4], ['g2', 6], ['g3', 6], ['g4', 4]]]), ('diamond tighter period', [{'a': 2, 'b': 0, 'c': 1}, [['g1', 2, ['a', 'b']], ['g2', 3, ['b', 'c']], ['g3', 1, ['g1', 'g2']], ['g4', 4, ['g1']]], ['g3', 'g4'], 9, 2], [-1, ['a', 'g1', 'g4'], [['g1', -1], ['g2', 2], ['g3', 2], ['g4', -1]]]), ('long branch through internal output', [{'a': 0, 'b': 1}, [['u', 5, ['a']], ['v', 1, ['b']], ['w', 2, ['v', 'u']], ['x', 1, ['w']], ['y', 6, ['v']]], ['w', 'x', 'y'], 10, 1], [1, ['a', 'u', 'w'], [['u', 1], ['v', 1], ['w', 1], ['x', 1], ['y', 1]]]), ('internal output with fanout', [{'a': 1, 'b': 1}, [['u', 5, ['a']], ['v', 1, ['b']], ['w', 2, ['v', 'u']], ['x', 1, ['w']], ['y', 6, ['v']]], ['x', 'y', 'v'], 10, 0], [1, ['a', 'u', 'w', 'x'], [['u', 1], ['v', 2], ['w', 1], ['x', 1], ['y', 2]]]), ('reconvergent unequal branches', [{'a': 0, 'c': 1}, [['p', 1, ['a', 'c']], ['q', 1, ['p']], ['r', 7, ['p']], ['s', 1, ['q', 'r']]], ['s'], 12, 1], [1, ['c', 'p', 'r', 's'], [['p', 1], ['q', 7], ['r', 1], ['s', 1]]]), ('reconvergent with late input', [{'a': 3, 'c': 1}, [['p', 1, ['a', 'c']], ['q', 1, ['p']], ['r', 7, ['p']], ['s', 1, ['q', 'r']]], ['s', 'q'], 14, 2], [0, ['a', 'p', 'r', 's'], [['p', 0], ['q', 6], ['r', 0], ['s', 0]]])], [('diamond with shared fanout', [{'a': 0, 'b': 2, 'c': 1}, [['g1', 2, ['a', 'b']], ['g2', 3, ['b', 'c']], ['g3', 1, ['g1', 'g2']], ['g4', 4, ['g1']]], ['g3', 'g4'], 12, 1], [3, ['b', 'g1', 'g4'], [['g1', 3], ['g2', 5], ['g3', 5], ['g4', 3]]]), ('diamond tighter period', [{'a': 2, 'b': 0, 'c': 2}, [['g1', 2, ['a', 'b']], ['g2', 3, ['b', 'c']], ['g3', 1, ['g1', 'g2']], ['g4', 4, ['g1']]], ['g3', 'g4'], 10, 2], [0, ['a', 'g1', 'g4'], [['g1', 0], ['g2', 2], ['g3', 2], ['g4', 0]]]), ('long branch through internal output', [{'a': 0, 'b': 2}, [['u', 5, ['a']], ['v', 1, ['b']], ['w', 2, ['v', 'u']], ['x', 1, ['w']], ['y', 6, ['v']]], ['w', 'x', 'y'], 10, 1], [0, ['b', 'v', 'y'], [['u', 1], ['v', 0], ['w', 1], ['x', 1], ['y', 0]]]), ('internal output with fanout', [{'a': 2, 'b': 1}, [['u', 5, ['a']], ['v', 1, ['b']], ['w', 2, ['v', 'u']], ['x', 1, ['w']], ['y', 6, ['v']]], ['x', 'y', 'v'], 11, 0], [1, ['a', 'u', 'w', 'x'], [['u', 1], ['v', 3], ['w', 1], ['x', 1], ['y', 3]]]), ('reconvergent unequal branches', [{'a': 0, 'c': 1}, [['p', 1, ['a', 'c']], ['q', 1, ['p']], ['r', 7, ['p']], ['s', 1, ['q', 'r']]], ['s'], 13, 1], [2, ['c', 'p', 'r', 's'], [['p', 2], ['q', 8], ['r', 2], ['s', 2]]]), ('reconvergent with late input', [{'a': 3, 'c': 2}, [['p', 1, ['a', 'c']], ['q', 1, ['p']], ['r', 7, ['p']], ['s', 1, ['q', 'r']]], ['s', 'q'], 14, 2], [0, ['a', 'p', 'r', 's'], [['p', 0], ['q', 6], ['r', 0], ['s', 0]]])], [('diamond with shared fanout', [{'a': 0, 'b': 3, 'c': 1}, [['g1', 2, ['a', 'b']], ['g2', 3, ['b', 'c']], ['g3', 1, ['g1', 'g2']], ['g4', 4, ['g1']]], ['g3', 'g4'], 12, 1], [2, ['b', 'g1', 'g4'], [['g1', 2], ['g2', 4], ['g3', 4], ['g4', 2]]]), ('diamond tighter period', [{'a': 2, 'b': 0, 'c': 3}, [['g1', 2, ['a', 'b']], ['g2', 3, ['b', 'c']], ['g3', 1, ['g1', 'g2']], ['g4', 4, ['g1']]], ['g3', 'g4'], 11, 2], [1, ['a', 'g1', 'g4'], [['g1', 1], ['g2', 2], ['g3', 2], ['g4', 1]]]), ('long branch through internal output', [{'a': 0, 'b': 0}, [['u', 5, ['a']], ['v', 1, ['b']], ['w', 2, ['v', 'u']], ['x', 1, ['w']], ['y', 6, ['v']]], ['w', 'x', 'y'], 10, 1], [1, ['a', 'u', 'w'], [['u', 1], ['v', 2], ['w', 1], ['x', 1], ['y', 2]]]), ('internal output with fanout', [{'a': 3, 'b': 1}, [['u', 5, ['a']], ['v', 1, ['b']], ['w', 2, ['v', 'u']], ['x', 1, ['w']], ['y', 6, ['v']]], ['x', 'y', 'v'], 12, 0], [1, ['a', 'u', 'w', 'x'], [['u', 1], ['v', 4], ['w', 1], ['x', 1], ['y', 4]]]), ('reconvergent unequal branches', [{'a': 0, 'c': 1}, [['p', 1, ['a', 'c']], ['q', 1, ['p']], ['r', 7, ['p']], ['s', 1, ['q', 'r']]], ['s'], 14, 1], [3, ['c', 'p', 'r', 's'], [['p', 3], ['q', 9], ['r', 3], ['s', 3]]]), ('reconvergent with late input', [{'a': 3, 'c': 3}, [['p', 1, ['a', 'c']], ['q', 1, ['p']], ['r', 7, ['p']], ['s', 1, ['q', 'r']]], ['s', 'q'], 14, 2], [0, ['a', 'p', 'r', 's'], [['p', 0], ['q', 6], ['r', 0], ['s', 0]]])], [('diamond with shared fanout', [{'a': 0, 'b': 4, 'c': 1}, [['g1', 2, ['a', 'b']], ['g2', 3, ['b', 'c']], ['g3', 1, ['g1', 'g2']], ['g4', 4, ['g1']]], ['g3', 'g4'], 12, 1], [1, ['b', 'g1', 'g4'], [['g1', 1], ['g2', 3], ['g3', 3], ['g4', 1]]]), ('diamond tighter period', [{'a': 2, 'b': 0, 'c': 4}, [['g1', 2, ['a', 'b']], ['g2', 3, ['b', 'c']], ['g3', 1, ['g1', 'g2']], ['g4', 4, ['g1']]], ['g3', 'g4'], 12, 2], [2, ['c', 'g2', 'g3'], [['g1', 2], ['g2', 2], ['g3', 2], ['g4', 2]]]), ('long branch through internal output', [{'a': 0, 'b': 1}, [['u', 5, ['a']], ['v', 1, ['b']], ['w', 2, ['v', 'u']], ['x', 1, ['w']], ['y', 6, ['v']]], ['w', 'x', 'y'], 10, 1], [1, ['a', 'u', 'w'], [['u', 1], ['v', 1], ['w', 1], ['x', 1], ['y', 1]]]), ('internal output with fanout', [{'a': 4, 'b': 1}, [['u', 5, ['a']], ['v', 1, ['b']], ['w', 2, ['v', 'u']], ['x', 1, ['w']], ['y', 6, ['v']]], ['x', 'y', 'v'], 13, 0], [1, ['a', 'u', 'w', 'x'], [['u', 1], ['v', 5], ['w', 1], ['x', 1], ['y', 5]]]), ('reconvergent unequal branches', [{'a': 0, 'c': 1}, [['p', 1, ['a', 'c']], ['q', 1, ['p']], ['r', 7, ['p']], ['s', 1, ['q', 'r']]], ['s'], 15, 1], [4, ['c', 'p', 'r', 's'], [['p', 4], ['q', 10], ['r', 4], ['s', 4]]]), ('reconvergent with late input', [{'a': 3, 'c': 4}, [['p', 1, ['a', 'c']], ['q', 1, ['p']], ['r', 7, ['p']], ['s', 1, ['q', 'r']]], ['s', 'q'], 14, 2], [-1, ['c', 'p', 'r', 's'], [['p', -1], ['q', 5], ['r', -1], ['s', -1]]])], [('diamond with shared fanout', [{'a': 0, 'b': 5, 'c': 1}, [['g1', 2, ['a', 'b']], ['g2', 3, ['b', 'c']], ['g3', 1, ['g1', 'g2']], ['g4', 4, ['g1']]], ['g3', 'g4'], 12, 1], [0, ['b', 'g1', 'g4'], [['g1', 0], ['g2', 2], ['g3', 2], ['g4', 0]]]), ('diamond tighter period', [{'a': 2, 'b': 0, 'c': 5}, [['g1', 2, ['a', 'b']], ['g2', 3, ['b', 'c']], ['g3', 1, ['g1', 'g2']], ['g4', 4, ['g1']]], ['g3', 'g4'], 13, 2], [2, ['c', 'g2', 'g3'], [['g1', 3], ['g2', 2], ['g3', 2], ['g4', 3]]]), ('long branch through internal output', [{'a': 0, 'b': 2}, [['u', 5, ['a']], ['v', 1, ['b']], ['w', 2, ['v', 'u']], ['x', 1, ['w']], ['y', 6, ['v']]], ['w', 'x', 'y'], 10, 1], [0, ['b', 'v', 'y'], [['u', 1], ['v', 0], ['w', 1], ['x', 1], ['y', 0]]]), ('internal output with fanout', [{'a': 5, 'b': 1}, [['u', 5, ['a']], ['v', 1, ['b']], ['w', 2, ['v', 'u']], ['x', 1, ['w']], ['y', 6, ['v']]], ['x', 'y', 'v'], 14, 0], [1, ['a', 'u', 'w', 'x'], [['u', 1], ['v', 6], ['w', 1], ['x', 1], ['y', 6]]]), ('reconvergent unequal branches', [{'a': 0, 'c': 1}, [['p', 1, ['a', 'c']], ['q', 1, ['p']], ['r', 7, ['p']], ['s', 1, ['q', 'r']]], ['s'], 16, 1], [5, ['c', 'p', 'r', 's'], [['p', 5], ['q', 11], ['r', 5], ['s', 5]]]), ('reconvergent with late input', [{'a': 3, 'c': 5}, [['p', 1, ['a', 'c']], ['q', 1, ['p']], ['r', 7, ['p']], ['s', 1, ['q', 'r']]], ['s', 'q'], 14, 2], [-2, ['c', 'p', 'r', 's'], [['p', -2], ['q', 4], ['r', -2], ['s', -2]]])]]
for label, args, expected in fixtures[N-1]:
check(label, solve(*args), expected)
print(json.dumps({"observations": observations, "passed": all(x["passed"] for x in observations)}, ensure_ascii=False))
raise SystemExit(0 if all(x["passed"] for x in observations) else 1)
| Boundary fixture | Actual | Expected | Outcome |
|---|---|---|---|
| diamond with shared fanout | [4, ['b', 'g1', 'g4'], [['g1', 4], ['g2', 6], ['g3', 6], ['g4', 4]]] | [4, ['b', 'g1', 'g4'], [['g1', 4], ['g2', 6], ['g3', 6], ['g4', 4]]] | Passed |
| diamond tighter period | [-1, ['a', 'g1', 'g4'], [['g1', -1], ['g2', 2], ['g3', 2], ['g4', -1]]] | [-1, ['a', 'g1', 'g4'], [['g1', -1], ['g2', 2], ['g3', 2], ['g4', -1]]] | Passed |
| long branch through internal output | [1, ['a', 'u', 'w'], [['u', 1], ['v', 1], ['w', 1], ['x', 1], ['y', 1]]] | [1, ['a', 'u', 'w'], [['u', 1], ['v', 1], ['w', 1], ['x', 1], ['y', 1]]] | Passed |
| internal output with fanout | [1, ['a', 'u', 'w', 'x'], [['u', 1], ['v', 2], ['w', 1], ['x', 1], ['y', 2]]] | [1, ['a', 'u', 'w', 'x'], [['u', 1], ['v', 2], ['w', 1], ['x', 1], ['y', 2]]] | Passed |
| reconvergent unequal branches | [1, ['c', 'p', 'r', 's'], [['p', 1], ['q', 7], ['r', 1], ['s', 1]]] | [1, ['c', 'p', 'r', 's'], [['p', 1], ['q', 7], ['r', 1], ['s', 1]]] | Passed |
| reconvergent with late input | [0, ['a', 'p', 'r', 's'], [['p', 0], ['q', 6], ['r', 0], ['s', 0]]] | [0, ['a', 'p', 'r', 's'], [['p', 0], ['q', 6], ['r', 0], ['s', 0]]] | Passed |
SHA-256 / 99262df653e2096dc5e016f3a3b7068766347671f64abc0d0faf8a0eb5135479
Verification & scope
A deterministic bounded teaching model of one simulator rule set; the contract is stipulated and is not a claim of conformance to any HDL standard or commercial simulator. This reproducer isolates one failure mechanism. Results cover the supplied fixtures. Variants within a family share a test contract and should remain grouped when constructing evaluation splits. Related mechanisms with a shared evaluation_group must also remain together; these controlled models are not independent production incidents.
Observations recorded using Python 3.12.14 at 2026-09-29T14:51:12.984669+00:00.
Case digest / 8618e2c3c21aaf3ece70808037046d09a9895fe9da8e4104335d345f78803a42