Anechoic: Onsager-Corrected Parallel Annealing for Sub-0.1 ms Dense Max-Cut on an FPGA

1 Introduction

• On K2000, two-thirds of SCA flips undo the same spin’s flip from the previous step, motivating subtraction of the echo from every decision.Dynamical mean-field theory identifies the echo as an Onsager reaction; its lag-one coefficient is n_lin/2T, counted with one population count per step.Source: §1 · p. 1, Figure 1 · p. 2
• SCA offers an inexpensive hardware step by deciding all spins in parallel and reading couplings only for spins that flip.The paper also reports a dense 2,000-spin RTL step of 18.1 cycles plus 0.14 cycles per flip.Source: §1 · p. 1
• 0.050 ms: twelve V80 engines reach a K2000 cut of at least 33,000 with 99% probability, 5.2× faster than the fastest published hardware.The measured system uses twelve engines on an AMD Alveo V80 and consumes 5.4 mJ per solution.Source: §1 · pp. 1–2
• Both Onsager-corrected SCA forms reach lower K2000 Ising energy at every step budget than five published binary-spin algorithms run at their papers’ settings.The correction uses either a counted coefficient or a temperature-scaled one.Source: §1 · p. 1

2 Related Work

• Digital parallel annealers include SCA, APC-SCA, TEC [14], DSSA, and graph-colored p-bit machines, which avoid synchronous conflicts through different mechanisms.The proposed correction has the functional form of pinning or time-step coupling, but uses a derived coefficient that follows the anneal.Source: §2 · p. 2
• Toshiba’s bSB is the fastest measured hardware at the 33,000-cut level, while GbSB reaches the best-known K2000 cut in 9.61 ms.Anechoic instead uses steps whose cost scales with the number of flips rather than N^2, trading against more steps or independent trials.Source: §2 · p. 2
• Dynamical mean-field theory identifies delayed self-interaction in parallel spin dynamics as an echo; prior work analyzed it, but did not subtract it inside a stochastic annealer.The Onsager reaction originates in TAP equations [39], and approximate message passing uses an analogous lag term.Source: §2 · p. 2

3.1 Ising machines and Max-Cut

• For Max-Cut, setting J_ij = −w_ij makes maximizing the cut equivalent to minimizing the Ising Hamiltonian; K2000 is a 2,000-vertex complete graph with weights in {−1, +1}.Its best-known cut is 33,337.Source: §3.1 · p. 2

3.2 Sequential and parallel Markov chain Monte Carlo

• Sequential SA updates one spin at a time and preserves the Gibbs distribution through detailed balance, whereas simultaneous updates break detailed balance and can oscillate between complementary configurations.Synchronous remedies include restricting updates to non-interacting spins, adding self-coupling, or coupling consecutive time steps.Source: §3.2 · pp. 2–3

3.3 Time-to-solution

• TTS99 converts run duration and success probability into the time needed to reach a target with 99% probability; the primary multi-engine estimator treats each round as one run.A secondary estimator treats trials on separate engines as independent and measures throughput, ignoring that work is done in whole rounds.Source: §3.3 · p. 3

4.1 Synchronous stochastic cellular automata

• SCA updates all spins independently in parallel with one field and one threshold comparison per decision, but synchronous dynamics can oscillate as flips reverse one step later.Unlike Glauber dynamics, each decision requires no exponential.Source: §4.1 · p. 3

4.2 The echo of synchronous updates

• On K2000, 67% of flips reverse the same spin’s preceding flip; dynamical mean-field theory identifies the lag-one echo as an Onsager reaction with coefficient c(t)=nlin(t)/(2T).At 2,000 spins, theory matches simulation within 3% in c on average.Source: §4.2 · p. 3, Figure 2 · p. 4

4.3 Onsager correction and its hardware cost

• The correction subtracts the estimated lag-one echo from the decision field; it weakens pinning for spins that stay put and strengthens it for spins that just flipped.Its coefficient follows c(t) over more than an order of magnitude during an anneal, with a fixed sign.Source: §4.3 · pp. 3–4
• With λ=0.7, correction reduces immediate flip-backs from 67% to 54% and allows a colder start: T0=12–15 versus 30–40 for plain SCA.The colder start shortens the flip-intensive early phase, which matters because hardware cost grows with the number of flips.Source: §4.3 · p. 4
• For plain SCA on K2000, c is nearly proportional to temperature over 8≤T≤25, so κT follows it without a population count; the best κT schedule is faster on-board.At equal projected hardware cost, the online coefficient gives a further 4–9% speed-up in projected time-to-solution.Source: §4.3 · p. 4
• Onsager-online counts nlin from existing decision flags for one population count per step, while Onsager-κT uses a temperature-scaled coefficient without that count; both forms share one engine.They differ only in two per-step tables.Source: §4.3 · p. 4

4.4 Comparison with published algorithms

• At every step budget, both corrected forms reach the lowest mean energy among binary-spin methods; at 500 steps, they hit the 33,000-cut target in 87% (κT) and 82% (online) of runs.Only bSB needs fewer steps to solution; at 4,000 steps, both corrected forms finish at lower energy than bSB.Source: Figure 3 · p. 5, §4.4 · p. 5
• At S=4000, both corrected forms end at lower energy, with mean cuts of 33,236 and 33,233, compared with bSB at 33,209 and dSB at 33,215.Only bSB needs fewer steps to solution than either corrected form. It reaches the lowest energy for S≤2000, then stalls.Source: §4.4 · p. 5

5 Engine and System Architecture

• The hand-written RTL engine keeps spin and field state on chip once, uses no handshakes, and accesses one coupling row per flipped spin.A small HLS front end moves data; earlier HLS versions were timing-limited by duplicated loop state and handshakes.Source: §5 · p. 5

5.1 Data layout and decisions

• 32 banks each hold 64 fields and eight decision lanes; eight rounds of 256 parallel decisions complete a step.Each lane evaluates the decision in Q16.16 and flags linear decisions; their count and a stored coefficient determine the correction.Source: §5.1 · p. 5

5.2 Flip extraction and field update

• Eight extractors drain flips while later rounds decide, broadcasting up to eight flips per cycle for local field updates by population counts.Each group updates its 64 fields without multipliers; the count of linear decisions supplies the correction coefficient.Source: §5.2 · pp. 5–6, Figure 4 · p. 6

5 Engine and System Architecture

• 18.1 cycles per step plus 0.14 cycles per flip models trial cost; a 280-step, approximately 47,400-flip trial took 12,371 cycles on board.Eight extractors and four coupling copies reduced cycles per trial by 28–32% for 15% more LUTs, with identical results.Source: §5.2 · p. 6

5.3 Front end and multi-engine system

• Twelve engines run at 250 MHz, four per SLR; resident couplings and tables mean later launches move only a two-beat header.The HBM and NoC are supplied by the AVED shell, and timing closure required changes including pipelined scoring and physical optimization.Source: §5.3 · p. 6

5.4 Verification

• The board image passed exact seeded-trial checks, and versions v4–v6 returned identical results for all 41,040 common trials.RTL simulation also matched a C++ reference bit for bit across protocol configurations.Source: §5.4 · p. 6

5.5 Multi-bit couplings and bias

• The multi-bit engine stores signed coupling magnitudes in bit planes, supports per-spin bias through initial fields, and masks unused spins at runtime.At K=2, twelve engines close timing at 250 MHz; at K=4, six engines close timing at 225 MHz, including with bias.Source: §5.5 · p. 7

6.1 Experimental methodology

• The evaluation froze configurations, seeds, trial counts, estimators, and quantitative predictions before data collection; each configuration ran 2,052 trials.For the 12-engine system, the O1 time prediction was 0.051 ms versus 0.050 ms measured; earlier 9-engine predictions failed because the model omitted per-launch table streaming.Source: §6.1 · p. 7

6.2 Time-to-solution

• 0.050 ms primary TTS99 (O1) and 0.018 ms secondary TTS99 (O5); against STATICA, O1 is 4.6× faster primary and O5 3.7× faster secondary.Against this work’s plain-SCA and TEC-style schedules, primary speedups are 2.8× and 2.7×, and secondary speedups are 3.4× and 4.2×.Source: Table 2 · p. 7, §6.2 · p. 7
• Table 4 compares K2000 TTS99 with a CPU baseline and hardware Ising machines ordered by publication; CMOS and ReRAM entries are simulations.The cited publications supply the other machines’ values.Source: Table 4 · p. 8, §6.2 · p. 8
• Corrected forms succeed less often per trial than B1–B3 (0.33–0.34 versus 0.39–0.46) but take rounds 25–43% as long.Against STATICA’s B5, they succeed 2.5 times as often per trial and take rounds 53–62% as long.Source: Figure 5 · p. 8

6.3 Comparison with the state of the art

• 5.2× faster than bSB on the primary estimator, with a 95% confidence lower bound of 4.2×, at the 33,000 target.The comparison mixes targets: bSB reports time to target for a cut of at least 33,004.Source: §6.3 · p. 8
• 293 steps for bSB versus 830 for Onsager-κT, but the FPGA engine’s 0.15–0.18 µs steps and twelve-engine parallelism yield faster hardware TTS.One engine would need about 0.22 ms with schedule O5; twelve engines succeed in every 50 µs O1 round.Source: §6.3 · p. 8
• At a cut of 33,337, GbSB reaches the target in 9.61 ms, while the best Onsager-online schedule takes 54 ms on twelve engines.That schedule needs 16,000 steps, beyond the 4,096-entry table; the best pre-registered schedule within the table takes 105 ms.Source: §6.3 · p. 8

6.4 Hardware cost and energy

• 108 W board input power with schedule O1 corresponds to 5.4 mJ per solution; twelve 2-bit engines use 126 W and 6.4 mJ per solution.Block RAM is the scarcest resource at 89%, because each engine stores its couplings four times.Source: §6.4 · p. 8

6.5 The same engine on a GPU

• The GH200 version reproduces the reference model bit-exactly in 424 of 424 traced trials, with up to 240 independent anneals running concurrently.Each chain runs on eight thread blocks that hold the coupling matrix in registers and exchange flip masks through distributed shared memory.Source: §6.5 · p. 8
• The V80 reaches the target 2.3× sooner and uses 8.0× less energy per solution than the GH200 on primary TTS99.The GPU’s 240 concurrent chains give it 2.3× lower secondary TTS99, but more chains cannot shorten primary TTS99 because twelve V80 engines already succeed each round.Source: §6.5 · p. 8

6.6 ASIC estimate

• The ASIC variant stores each coupling once in single-port SRAM, reducing storage from 16 to 4 Mbit per engine versus the FPGA implementation.The variant reproduces the FPGA engine bit- and cycle-exactly on eight test sets; after routing, smaller SRAM macros keep coupling reads to one cycle.Source: §6.6 · p. 9
• SRAM and flip-flops account for about 70% of ASIC power, as every applied flip reads a full 2,048-bit coupling row and only 29% of flip-flops are clock-gated.The Figure 6 caption identifies the physical layout, clock tree, and power breakdown at the typical corner.Source: §6.6 · p. 9, Figure 6 · p. 9
• At 1.25 GHz, twelve estimated ASIC engines reach the K2000 target in 10.1 µs with 0.20 mJ per solution, 26× below bSB’s 0.26 ms.These are ASIC estimates, not silicon measurements.Source: §6.6 · p. 9

6.7 Platform trade-offs

• The FPGA has the lowest measured primary TTS99 and energy per solution, and one board runs variants up to K=4 with bias.Its fabric runs at 250 MHz, and on-chip memory limits it to twelve engines, or six with K=4.Source: §6.7 · p. 9
• The GPU needs no hardware design and has the highest measured throughput, but inter-multiprocessor round trips make each solution slower and more energy-intensive.Most of the FPGA’s 108 W draw is idle power.Source: §6.7 · p. 10
• The ASIC would be fastest and most energy-efficient, but its coupling width is fixed at fabrication and each extra bit costs area.The ASIC performance figures are estimates rather than silicon measurements.Source: §6.7 · p. 10

6.8 Combinatorial optimization problems

• With extended grids from a pre-registered amendment, the method was faster on 49 and 42 instances (2.17× and 1.68×), with geometric-mean TTS99 of 0.11 ms versus 0.24 and 0.19 ms.Source: §6.8 · p. 10
• On Max-Cut software tests, only bSB needs fewer steps than corrected rules on the five commonly solved instances; across all 20, SA and dSB need 0.44–0.62 times as many.Plain SCA and TEC, at their K2000 settings, miss the target on 9 and 1 instances, respectively.Source: §6.8 · p. 10
• For graph partitioning, only 4–5% of corrected runs end balanced; on TSP, corrected rules return valid tours of quality 0.47–0.48, but only ReAIM ASA and bSB reach the target.Neither plain SCA nor a corrected rule reaches the target on GP or TSP in software or with the 4-bit GPU kernel.Source: §6.8 · p. 10

6.9 Limitations

• Synchronous rules fail on constrained GP and TSP problems whose penalties couple all spins, causing many to flip together and overshoot.The ASIC results are simulations, not silicon measurements.Source: §6.9 · p. 10

• At every K2000 step budget, both Anechoic forms reach lower Ising energy than five published binary-spin algorithms at their papers’ settings.Source: §7 · p. 10
• 0.05 ms: twelve AMD V80 engines reach the K2000 target, 5.2× faster than the fastest published hardware and 4.6× faster than STATICA’s schedules on the same board.The engine takes 18.1 cycles per step plus 0.14 per flip.Source: §7 · p. 10
• On an NVIDIA GH200, the engine needs 2.3× more time and 8.0× more energy per solution, but its 240 anneals provide 2.3× higher throughput.Source: §7 · p. 10
• With 2-bit couplings, Onsager-κT is faster than plain SCA on 48 of 51 G-set instances.Source: §7 · p. 10
• About 10 µs: a projected twelve-engine GlobalFoundries 22 nm ASIC reaches the target, 26× faster than bSB, at 0.20 mJ of engine energy per solution.Source: §7 · p. 11

• AI tools proofread the manuscript and checked related work and theory, including machine-checked proofs in Section 4.2.Source: Use of AI Tools · p. 11
• AI tools were used to reimplement published algorithms for comparison in Section 4.4.Source: Use of AI Tools · p. 11
• Values reported by other papers, including Table 4 values, were quoted directly from the cited publications.Source: Use of AI Tools · p. 11