Source-linked AI summary
Batch Before You Time: Decision-Scoped Proxy Execution for Timing-Aware Logic Rewriting
Pujun Su
TL;DR
SDF-annotated simulation distinguishes delay-dependent activity among equivalent rewrites, but evaluating every candidate repeats expensive timing and replay work, while candidate-wise proxies can also cost more than the timed work they save. BBYT batches candidates within one rewrite decision and uses a gap gate to choose between a proxy winner and the unchanged timed chain. Across 12 counterbalanced holdout sequences, it reduces complete selection time by 18.05% on average and matches all 250 exhaustive timed selections while removing 32.52% of timed candidate evaluations.
Problem
SDF-annotated evaluation captures delay-dependent activity among equivalent rewrites, but applying the timing chain to every candidate repeats static timing analysis, delay annotation, compilation, and replay; candidate-wise proxy generation can also cost more than the timed work it removes.
Source: §I · p. 1Method
BBYT compiles and replays one scoped zero-delay image for all candidates in a rewrite decision, then commits a separated proxy winner or invokes the unchanged exhaustive timed chain.
Source: §I · p. 1Results
Across 12 counterbalanced holdout sequences, complete candidate-selection time falls by 18.05% on average; BBYT matches all 250 exhaustive timed selections and removes 32.52% of timed candidate evaluations.
Source: §I · p. 1Takeaways & Limitations
For on-demand timing-aware rewriting, proxy execution and fidelity continuation should use the same decision scope.
Source: §VII · p. 6
Abstract
from arXiv · showhide
Standard Delay Format (SDF)-annotated switching simulation distinguishes delay-dependent activity among functionally equivalent rewrites, but evaluating every candidate repeats timing, compilation, and replay. A zero-delay proxy can remove timed evaluations, but generating that proxy candidate by candidate can cost more than the timed work it saves. We present Batch Before You Time (BBYT), which compiles all candidates of one rewrite decision into one scoped zero-delay image and either commits a well-separated proxy winner or invokes the unchanged timed chain. Across 12 counterbalanced holdout sequences, BBYT reduces complete candidate-selection time by 18.05% on average; the design-level reductions are 5.84% and 30.25%, with both confidence intervals above zero. On a counterbalanced 8,192-transition C6288 workload, BBYT is 9.24% faster than the same gate executed with candidate-wise proxy launches. In the five-workload corpus, BBYT removes 32.52% of timed candidate evaluations and matches exhaustive timed selection on all 250 evaluated decisions. For on-demand timing-aware rewrite selection, proxy execution and fidelity continuation should use the same decision scope.
I. Introduction
Timing-aware evaluation of equivalent rewrites repeats static timing analysis, delay annotation, compilation, and replay; candidate-wise proxy execution can also cost more than the timed work it removes. BBYT batches the candidates of one rewrite decision, then commits a separated proxy winner or invokes the unchanged exhaustive timed chain.
I. Introduction
- Applying the SDF timing chain to every candidate repeats static timing analysis, delay annotation, compilation, and replay on the selection critical path.Candidate-wise proxy generation can remove accurate evaluations yet increase complete selection time.Source: §I · p. 1
- BBYT compiles and replays one scoped zero-delay image per rewrite decision, recovering candidate-local scores for either a proxy commitment or the original exhaustive timed fallback.The candidate set, objective, gate, and fallback remain unchanged.Source: §I · p. 1
- The paper derives a complete-cost condition for savings and shows that candidate-wise proxy launches can reverse the expected benefit.The contributions distinguish the overall counterbalanced result from the controlled packing comparison.Source: §I · p. 1
- 18.05% average complete-flow reduction across 12 counterbalanced sequences; BBYT also matches all 250 exhaustive timed selections while removing 32.52% of timed candidate evaluations.On the controlled workload, decision-scoped packing is 9.24% faster than candidate-wise proxy execution.Source: §I · p. 1
II. Motivation and Related Work
The paper evaluates candidate selection from the point where on-demand candidates are available through proxy preparation, any timed continuation, and the final write. Its comparison separates the fidelity policy from the execution scope used to obtain proxy scores.
A. The Complete Candidate-Selection Boundary
- Complete candidate-selection cost includes proxy preparation, compilation, replay, parsing, the gate, timed continuation, and final write.The boundary includes work before and after the gate rather than beginning with precomputed proxy scores.Source: A. The Complete Candidate-Selection… · pp. 1–2
- In the streaming flow, candidates are generated on demand, so BBYT creates and consumes one decision image before advancing rather than relying on precomputed scores.Exhaustively materializing proxy scores would change the online workflow.Source: A. The Complete Candidate-Selection… · p. 2
- The gate helps only when removed timed work exceeds proxy and control cost; candidate-wise and decision-scoped flows share the all-or-none timed continuation but differ in proxy launches.The matched boundaries distinguish the gate-plus-packing comparison with exhaustive timing from the packing comparison with candidate-wise execution.Source: A. The Complete Candidate-Selection… · p. 2, Table I · p. 2
B. Timing-Aware Rewriting and Multi-Fidelity Selection
BBYT changes how proxy queries for one rewrite decision are executed, while retaining the candidate set and fidelity gate. Its decision-level gate commits a proxy winner only when the relative gap clears a fixed threshold; otherwise it uses timed energy for every candidate.
B. Timing-Aware Rewriting and Multi-Fidelity Selection
- BBYT batches proxy queries within one rewrite decision, unlike prior approaches that predict block timing, prune search choices, or share simulation across tests, cycles, or repeated structure.The candidate set and gate remain fixed.Source: B. Timing-Aware Rewriting and… · p. 2
A. Decision-Level Fidelity Gate
- A unique, nonzero proxy minimum is committed only when its relative gap exceeds the fixed threshold τ=0.13; ties, zero minima, and other ambiguous cases enter the accurate chain for every candidate.The relative gap is formed from the lowest and second-lowest sorted proxy energies.Source: A. Decision-Level Fidelity Gate · p. 2
- Zero-delay and timed fidelities use the same switching-energy objective, differing only in how each mapped signal’s transition count is obtained.The calculation uses mapped load, transition count, and library voltage.Source: A. Decision-Level Fidelity Gate · p. 2
B. One Packed Image per Decision
BBYT builds one zero-delay image for a rewrite decision, scores its candidates separately, then writes the proxy winner or calls the existing timed path for all candidates. This packed execution preserves candidate-level transitions while sharing compilation and replay.
B. One Packed Image per Decision
- One compiler invocation builds a packed image and one replay produces a scoped transition trace for each candidate under the same stimulus.The parser dispatches transitions by candidate scope and applies each candidate’s original loads.Source: B. One Packed Image per Decision · p. 2
- The decision-local image keeps scores from different rewrite decisions separate and routes the result to either the unique proxy winner or the unchanged timed chain for all candidates.Only one decision image is live at a time.Source: B. One Packed Image per Decision · p. 2, Figure 1 · p. 3
- All 454 direct packed-versus-candidate-wise proxy energies agree, validating the packed naming-and-scoping implementation.Source: B. One Packed Image per Decision · p. 3
- For k candidates, BBYT uses one proxy launch rather than k candidate-wise compilations and replays, trading a larger decision-local image for fewer launches.Transition demultiplexing is linear in the event stream, ranking costs O(k log k), and streaming state remains bounded.Source: B. One Packed Image per Decision · p. 3
C. Complete-Cost Break-Even View
The complete-cost comparison uses a shared boundary from ready candidates, loads, and stimulus to the selected candidate. BBYT breaks even when skipped timed work exceeds packed proxy and control costs.
C. Complete-Cost Break-Even View
- BBYT is faster when removed timed candidate work exceeds the added packed-proxy and control costs.The comparison starts with mapped candidates, loads, and stimulus ready, and ends when the selected candidate is written.Source: C. Complete-Cost Break-Even View · p. 3
- Candidate-wise execution can remove the same timed candidates, but pays per-candidate proxy launches instead of one packed proxy image per decision.As candidate count grows, the number of avoided launches grows while BBYT still emits one image per decision.Source: C. Complete-Cost Break-Even View · p. 3
IV. Experimental Methodology
The experiments evaluate a serial timing-aware rewrite flow on five workloads and use counterbalanced sequences to compare complete-flow timing. The sequence, rather than an individual decision or arm, is the runtime observation.
A. Benchmarks, Toolchain, and Configuration
- Five workloads contain 250 fixed decisions and 532 mapped candidates, drawn from 11 ISCAS85 and EPFL combinational circuits.Six circuits establish implementation consistency; C6288 and EPFL-i2c are counterbalanced holdouts, and three additional workloads extend the corpus.Source: A. Benchmarks, Toolchain, and… · p. 3
- The flow uses Yosys and ABC for mapping and equivalence, OpenSTA for delays, and Icarus Verilog/VVP for zero-delay and SDF simulation.Simulation workloads execute serially; runs use Ubuntu 22.04 on eight logical processors with 7.6 GiB memory.Source: A. Benchmarks, Toolchain, and… · p. 3
B. Counterbalanced Complete-Flow Confirmation
- Counterbalanced holdout sequences compare BBYT and exhaustive timed evaluation using fixed candidate sets, gate, and timed objective.Each sequence has four arms; arm order is mirrored, and a complete sequence is the timing sample.Source: B. Counterbalanced Complete-Flow… · p. 3, Table II · p. 4
- Design-level intervals use six sequence effects, while saved-time intervals use the corresponding absolute sequence differences.This preserves the repeated unit and avoids treating decisions within one process execution as independent runtime observations.Source: B. Counterbalanced Complete-Flow… · pp. 3–4
C. Packing Attribution and Candidate Multiplicity
A controlled C6288 experiment isolates the effect of decision-scoped packing from gate actions and timed work. A separate multiplicity study compares proxy execution on fixed nested prefixes of two natural decisions.
C. Packing Attribution and Candidate Multiplicity
- The C6288 attribution experiment compares exhaustive timing, candidate-wise proxy execution, and BBYT on the same 8,192-transition workload.All six condition orders are run, and the packing contrast is candidate-wise time minus BBYT time within a complete sequence.Source: C. Packing Attribution and Candidate… · p. 4
- The packing contrast holds threshold, candidates, actions, and timed fallback constant, and requires identical timed work and selected candidates.Every comparison records identical actions, timed work, and final selections; all 36 sequences and 138 arms completed.Source: C. Packing Attribution and Candidate… · p. 4
- The multiplicity study compares candidate-wise and decision-scoped execution on nested prefixes with k=2, 3, and 4 candidates from two natural EPFL-cavlc decisions.It subtracts recorded timed-wall contribution before comparing proxy work because timed continuation is unchanged.Source: C. Packing Attribution and Candidate… · p. 4
V. Quality, Work, and Complete-Flow Time
Under the unchanged gate, BBYT reduces timed candidate evaluations while matching exhaustive timed selections across the five-workload corpus. The number of removed evaluations depends on committed-decision candidate multiplicities, and the fixed threshold has a broad zero-mismatch range in the observed scan.
A. Timed Work and Selection Quality
- 32.52% of timed candidate evaluations are removed, with the same mapped candidate selected as exhaustive timing on all 250 decisions.BBYT runs 359 of 532 candidate-level timed evaluations; observed timed-energy regret is zero.Source: A. Timed Work and Selection Quality · p. 4, Table III · p. 4
- The comparison uses one global threshold; under that condition, decision count alone does not predict the work removed, so counts alone cannot identify which work is removed.Source: A. Timed Work and Selection Quality · p. 4
- 173 removed evaluations come from 81 directly committed decisions, while 169 fallback decisions retain all candidate evaluations.A direct commit removes every timed candidate evaluation in that decision; a fallback retains them all.Source: A. Timed Work and Selection Quality · p. 4
- Zero selection mismatch appears across observed gap breakpoints from 0.084555 through 0.18, including the fixed 0.13 threshold.The scan finds that 0.13 is not an isolated zero-mismatch breakpoint in this corpus.Source: A. Timed Work and Selection Quality · p. 4
B. Counterbalanced Holdout Results
Across both holdouts, BBYT reduced complete-flow time in every sequence, with positive design-level confidence intervals. On the controlled C6288 workload, decision-scoped packing outperformed candidate-wise proxy execution while leaving selection work unchanged.
B. Counterbalanced Holdout Results
- 18.05% was the combined mean reduction across 12 sequence effects, with interval [9.78%, 26.32%].The two design-level intervals remain the primary holdout results.Source: B. Counterbalanced Holdout Results · pp. 4–5
- 5.84% on C6288 and 30.25% on EPFL-i2c were the mean complete-flow reductions, with both design-level intervals above zero.Every sequence was positive; the intervals were [3.90%, 7.78%] and [26.61%, 33.90%], respectively.Source: B. Counterbalanced Holdout Results · p. 4, Figure 2 · p. 5
- The BBYT-first and exhaustive-first strata averaged 18.72% and 17.38%, while the gate removed 15 C6288 and 48 EPFL-i2c timed candidates.The measured benefit was present under both mirrored run orders; the larger skipped-work term on EPFL-i2c explains its larger absolute saving.Source: B. Counterbalanced Holdout Results · p. 5
A. Direct Packing Increment
- 9.24% was the reduction in candidate-wise complete-flow time from decision-scoped packing, with interval [8.39%, 10.10%].All six sequence contrasts were positive; the paired proxy-time difference was 20.02 s.Source: A. Direct Packing Increment · p. 5
- Candidate-wise execution was 17.65 s slower than exhaustive timing, while BBYT was 2.38 s faster, with the 20.02-s contrast attributable to proxy execution scope.The proxy conditions had identical actions, timed work, and selections.Source: A. Direct Packing Increment · p. 5
B. Natural Candidate Multiplicity
On two natural four-candidate decisions and their fixed prefixes, the measured packing advantage increased with candidate multiplicity. The system implications distinguish savings from fewer timed evaluations from the added proxy-launch cost that decision-scoped execution reduces.
B. Natural Candidate Multiplicity
- Complete-wall packing advantages were 0.329, 0.665, and 1.023 s at k=2, 3, and 4, increasing monotonically with actions, timed work, and selections unchanged.The scope is two natural four-candidate decisions and their fixed prefixes.Source: B. Natural Candidate Multiplicity · p. 5
C. System Design Implication
- The 32.52% timed-candidate reduction measures fidelity allocation, whereas the 9.24% paired contrast measures packing’s additional contribution.The gate controls removed timed work; decision-scoped execution controls added proxy cost, and multiplicity controls avoided launches.Source: C. System Design Implication · p. 5
- BBYT generates scoped scores for one decision and either returns the proxy winner or calls the existing all-candidate timed evaluator, preserving streaming order and bounded live state.The relevant regime is on-demand proxy generation with repeated compilation and replay; compatible scores already available at no marginal cost can be consumed directly.Source: C. System Design Implication · pp. 5–6
B. Natural Candidate Multiplicity
- Candidate-wise minus BBYT proxy time was 0.352 s at k=2, 0.716 s at k=3, and 1.059 s at k=4 on two natural decisions.All six sequence effects at every prefix were positive.Source: B. Natural Candidate Multiplicity · p. 5, Figure 3 · p. 6
VII. Conclusion
BBYT batches zero-delay proxy execution at the rewrite-decision level and retains the existing timed chain for ambiguous decisions. It reduces selection time on the counterbalanced holdouts, while matching exhaustive timed selections across the evaluated corpus.
VII. Conclusion
- BBYT uses one zero-delay image per timing-aware rewrite decision and reserves the unchanged SDF-annotated chain for proxy-ambiguous decisions.The proxy scores jointly determine whether that decision continues to timing.Source: §VII · p. 6
- 18.05% was the average complete candidate-selection time reduction across 12 counterbalanced holdout sequences; BBYT matched all 250 exhaustive timed selections and removed 32.52% of timed candidate evaluations.On the controlled 8,192-transition workload, decision-scoped packing contributed 9.24% relative to candidate-wise proxy execution.Source: §VII · p. 6
- For on-demand simulation-in-the-loop rewriting, proxy scores should be generated at the same decision scope that controls timed continuation.On the evaluated natural four-candidate decisions and fixed prefixes, the packing advantage increased from k=2 to k=4.Source: §VII · p. 6