PaperlayerView exact revision on arXiv

Source-linked AI summary

Differential Stochastic Simulated Annealing Processor for Fully Connected 2048-Spin Optimization

Naoya Onizawa, Md Mohaimenul Alam, Sean Smithson, Duckgyu Shin, Takahiro Hanyu

arXiv:2609.09559v1cs.AR

TL;DR

Fully connected annealers face costly bandwidth or serial work at large spin counts, and sparse approximations can distort dense problems. This paper co-designs differential stochastic annealing and hardware for a fully connected 2,048-spin processor. Post-layout estimates report 2.7 ms TTS and 0.86 mJ energy-to-solution on 2,000-spin MAX-CUT.

  • Problem

    Fully connected processors must provision quadratic weight bandwidth or revisit all spins serially, while sparse graphs and embeddings can distort dense problem structure.

    Source: §1 · pp. 1–2

  • Method

    DSSA retains a serialized datapath but recomputes interactions only for spins that flipped, with hardware scheduling and shared random resources supporting sparse activity.

    Source: §1 · p. 2, §3.3 · p. 6

  • Results

    At 2,000-spin MAX-CUT, post-layout estimates report 2.7 ms TTS and 0.86 mJ energy-to-solution at 316 mW; versus projected STATICA, power is 1.5× lower and TTS energy 3.5× lower.

    Source: §1 · p. 2, §6 · p. 22

  • Takeaways & Limitations

    The design demonstrates a fully connected 2,048-spin DSSA processor with on-chip weights and projected low per-spin power and TTS energy.

    Source: §6 · p. 22

    The reported results are post-layout estimates rather than fabricated-silicon measurements, which may differ because of implementation non-idealities.

    Source: §5.7 · p. 21

Abstract

from arXiv · show

A 2,048-spin fully connected annealing processor based on differential stochastic simulated annealing (DSSA) is presented as an architectural design in TSMC 28 nm CMOS with a 3 mm x 4 mm post-layout area. The processor closes timing at 500 MHz, integrates a 16 Mb SRAM weight memory, and amortizes stochastic noise across 16 spins with area-efficient random number generators. DSSA keeps a serialized datapath for density but recomputes interactions only for spins that flip, shrinking the effective workload to the active frontier during each annealing run. Spin-select scheduling, priority-based weight reads, and a temperature controller that skips idle steps accelerate sparse updates without sacrificing full connectivity. Post-layout simulation results show 2.7 ms time-to-solution (TTS) and 0.86 mJ energy-to- solution on 2,000-spin problems at 316 mW (0.15 mW/spin), achieving 1.5x lower power and 3.5x lower TTS energy than projected prior fully connected annealers. These results demonstrate the potential of the proposed DSSA architecture for large-scale combinatorial optimization hardware under post-layout evaluation.

1 Introduction

Fully connected annealers face steep bandwidth, cycle, and cost burdens at thousands of spins, while sparse topologies can distort dense problems. This work uses differential updates and architectural co-design to build a 2,048-spin processor, with post-layout estimates reporting 2.7 ms TTS and 0.86 mJ energy-to-solution on 2,000-spin MAX-CUT.

1 Introduction

  • Fully connected designs trade quadratic weight bandwidth against serial revisits of all spins, while sparse graphs and embeddings distort dense problem structure.For a dense 2,000-spin graph, serialization requires on the order of 2,000 cycles per temperature regardless of how many spins change.Source: §1 · pp. 1–2
  • DSSA recomputes only interaction terms affected by flipped spins, reducing redundant evaluations rather than relying on multiplexing alone.The contribution summary reports up to 30.6× fewer serialized SSA cycles than conventional full-spin sweeps while preserving full connectivity and solution quality.Source: §1 · p. 2
  • 2.7 ms TTS and 0.86 mJ energy-to-solution are reported for 2,000-spin MAX-CUT; versus projected STATICA, power is 1.5× lower and TTS energy 3.5× lower.The 2,048-spin TSMC 28 nm design closes timing at 500 MHz; reported results are post-layout estimates.Source: §1 · p. 2
  • Spin-select queuing, priority weight-memory banking, 16:1 RNG sharing, and shot-level temperature control align hardware resources with sparse activity.The co-design is intended to reduce area and power.Source: §1 · p. 2

2 Preliminaries and Related Work

The section introduces Ising formulations as a way to encode optimization objectives for simulated annealing, then surveys hardware approaches and their connectivity and cost tradeoffs.

2.1 Ising Formulation and SA Basics

  • A weighted MAX-CUT graph maps to spin variables, with edge weights as couplings and node biases as fields, so the Hamiltonian encodes the cut objective.The four-node illustration presents the partition objective; the conversion figure depicts the graph-to-Ising flow.Source: §2.1 · pp. 2–3, Figure 2 · p. 3, Figure 1 · p. 3
  • Simulated annealing perturbs the spin state and accepts the proposal probabilistically; high temperature permits uphill moves, while cooling reduces their probability.The section describes schedules such as T(t+1) = T(t)α.Source: §2.1 · pp. 3–4

2.2 Hardware Realizations of SA and QA

  • Quantum annealers use tunneling but require cryogenic qubits and coherent control, whereas MTJ probabilistic bits offer room-temperature stochasticity but face scaling and integration overhead.Source: §2.2 · p. 4
  • SSA uses stochastic computing to approximate tanh(·), but sparse topologies such as King’s graphs limit fidelity for dense problems.A related reconfigurable sparse and higher-order Ising machine emulates dense interactions while retaining parallel spin updates.Source: §2.2 · p. 4
  • ASIC designs trade connectivity and cost through multi-chip tiling, wide convolution engines, or serial updates that revisit all spins each step.These tradeoffs motivate differential serialization to retain full connectivity without quadratic datapaths.Source: §2.2 · pp. 4–5

3 Differential Stochastic Simulated Annealing

DSSA retains a serialized datapath but reduces work by updating only spins that flip, rather than merely time-multiplexing full spin computations. It combines this differential update with initialization and temperature scheduling to manage activity across each shot.

3.1 Area–Latency Motivation

  • When M is smaller than N, DSSA retains the serial area profile while reducing per-step cycles.High inverse temperature suppresses flips late in a shot, making M typically smaller than N.Source: §3.1 · p. 5

3.2 Initialization at t=0

  • At t=0, every spin performs a full SSA-style update to initialize the interaction state and resulting spin.Hardware sets the initial spin σi(0) to −1; ri(t) supplies stochastic perturbation whose amplitude is controlled by nrnd.Source: §3.2 · p. 5

3.3 Differential Updates for t>0

  • For later steps, DSSA recomputes interaction changes only for spins that flipped, reducing work from all N spins to M flipped spins.The update uses the difference between consecutive interaction states; unchanged spins contribute zero to the differential update.Source: §3.3 · p. 6

3.4 Temperature Scheduling and Acceptance

  • The scheduler updates I0 each step across a shot’s ramp, while high I0 suppresses flips and low I0 enables exploration.A shot spans the ramp from I0 min to I0 max, and the scheduler broadcasts I0 parameters to enforce the temperature profile.Source: Figure 4 · p. 7, §3.4 · p. 8

4 Processor Architecture and Circuits

The processor maps DSSA to a fully connected spin-gate array with shared stochastic resources and selective weight-memory access. Its serialized, event-driven datapath performs work in response to flips, reducing runtime when activity is sparse.

4.1 Top-Level Architecture

  • The top-level architecture integrates 2,048 spin-gates, 16:1 RNG sharing, and a 16 Mb, 4-bit-weight SRAM accessed only for flipped spins.The weight memory uses 64 distributed SRAM macros, while the spin-select circuit prioritizes active spins and issues their weight addresses.Source: §4.1 · p. 8

4.2 Spin-Gate and Update Circuits

  • Each spin-gate combines a SIC that accumulates differential current with a SUC that compares it against a stochastic threshold to determine the next spin state.A flip raises ∆i, allowing the spin-select circuit to process a sparse vector; initialization fills SIC registers before selective updates and queue draining.Source: §4.2 · pp. 8–9, Figure 5 · p. 9

4.3 Stochastic Nonlinearity and RNG Sharing

  • The SUC uses a stochastic finite-state machine to approximate tanh without LUTs, with shared random bits feeding groups of 16 spins.The scheduler cools I0 step-by-step, while the shot counter advances only after the complete ramp from I0 min to I0 max.Source: §4.3 · p. 9

4.4 Complexity and Workload Reduction

  • After initialization, each active spin uses one weight-memory fetch and a one-cycle stochastic comparison; idle memory reads are skipped when no spins flip.The serialized datapath trades a few cycles per flip for reduced total cycles while maintaining correctness and shrinking computation to the active frontier.Source: §4.4 · pp. 9, 11

4.5 Serializer Timing and Latency

  • DSSA latency scales with the number of flips rather than total spin count, reducing serialized SSA slowdowns by up to three orders of magnitude for 2,000-spin problems.Figure 6 shows dense early updates collapsing to a few dozen cycles late in shots; Table 2 summarizes MAX-CUT results across 100 trials under fixed annealing conditions.Source: Figure 6 · p. 10, §4.5 · p. 11, Table 2 · p. 11

5 Experimental Evaluation

The evaluation uses diverse MAX-CUT benchmarks and fixed, searched hyperparameters, then examines common-parameter robustness and implementation feasibility. Hardware results are based on ASIC post-layout evaluation.

5.1 Benchmark Setup and Hyperparameter Search

  • Seven 2,000-node G-set MAX-CUT instances span random, planar, and fully connected graphs, with varied edge counts and weight patterns.The evaluation also includes seven Biq Mac Library instances to assess generality beyond the G-set, not for direct hardware comparisons.Source: §5.1 · p. 12
  • A grid search selects DSSA hyperparameters using five trials of five shots per tuple, and settings are fixed per benchmark for subsequent comparisons.The search spans I0 min, I0 max, nrnd, and τ, with β fixed at 1.Source: §5.1 · p. 12

5.2 Design and Implementation Flow

  • FPGA place-and-route verifies RTL synthesizability and implementation feasibility, while reported ASIC hardware results use post-layout evaluation.The FPGA result is not a substitute for ASIC silicon measurement.Source: §5.2 · p. 13
  • Common parameter settings provide useful solution quality across graph structures, while benchmark-specific tuning or a suitable common candidate can improve robustness.The comparison also motivates lightweight online adaptation based on runtime indicators such as flip activity.Source: §5.2 · p. 14, Figure 8 · p. 14

5.3 Solution Quality and Runtime Reduction

DSSA maintains high MAX-CUT solution quality across the evaluated G-set and Biq Mac instances. Its cycle savings depend on flip activity, with the maximum reduction not guaranteed for every instance.

5.3 Solution Quality and Runtime Reduction

  • Average cuts exceed 99% of best-known values on every G-set benchmark; G22, G23, G24, and K2000 also exceed 99% on the worst trial, while K2000 and G27 reach the optimum.Across seven Biq Mac instances, DSSA reaches the best-known cut in six; w05_100.0 is 0.668% below its best-known value.Source: §5.3 · pp. 14–15
  • Biq Mac results support DSSA applicability beyond the G-set, but their experiments do not directly measure cycle reduction.Cycle reduction depends on active-frontier size rather than graph family alone.Source: §5.3 · p. 15
  • DSSA reduces total cycles by 3.1×–30.6× and per-step cycles by 2.8×–42× versus fully serialized SSA, with the reduction governed by flipped-spin activity.For K2000, an average of 6.5% of spins flip per step, yielding a 15.4× total-cycle reduction; the maximum 30.6× reduction is benchmark- and activity-dependent.Source: §5.3 · p. 15

5.4 Ablation: RNG Sharing and Differential Serialization

The ablations assess shared random-number generation and differential serialization. Sharing 16 spins per RNG improves RNG area efficiency, while disabling differential scheduling removes the reported cycle savings.

5.4 Ablation: RNG Sharing and Differential Serialization

  • 16:1 RNG sharing maintains solution quality within a narrow statistical range and improves RNG area efficiency eightfold over a non-shared design.The evaluation uses 100 trials across random seeds 0–99, with five shots per trial and 95% confidence intervals.Source: §5.4 · pp. 15, 17
  • Disabling the differential scheduler restores the N^2 interaction cost and erases the 3.1×–30.6× cycle reductions reported for DSSA.Excessive RNG sharing also reduces entropy diversity across spins and degrades exploration.Source: §5.4 · p. 17

5.5 Hardware Validation and Comparison

Post-layout evaluation reports a 2,048-spin, fully connected processor at 500 MHz and compares its hardware and K2000 performance with prior systems. The comparison requires attention to evaluation scope and target topology.

5.5 Hardware Validation and Comparison

  • The 2,048-spin processor closes timing at 500 MHz with estimated power of 316.1 mW, or 0.15 mW per spin, in post-layout evaluation.The 3 mm × 4 mm die integrates a 16 Mb weight memory; the floorplan distributes 64 SRAM macros around the spin-gate array.Source: §5.5 · p. 17
  • DSSA retains 2,048 fully connected spins and all weights on one die, while prior fully connected chips cap spins at 512 or use multi-chip tiling.Its 0.15 mW per-spin power is 8.5× lower than the JSSC’21 fully connected chip at similar VDD.Source: §5.5 · pp. 17, 19
  • At P=0.99, DSSA reaches 0.86 mJ energy-to-solution on K2000, 3.5× below projected STATICA and five orders of magnitude below the GPU baseline.DSSA balances runtime and success probability, yielding the lowest TTS(0.99) energy among the three compared systems.Source: §5.5 · p. 19
  • Absolute TTS is not a topology-independent ranking because sparse parallel machines and fully connected DSSA target different problem classes.Topology, connectivity, coefficient precision, validation method, and target formulation should be considered together.Source: §5.5 · p. 19
  • The GPU comparison uses a straightforward conventional SSA implementation, so it is a reference point rather than an upper bound on GPU performance.GPU runtime and power include computation and memory overhead; DSSA figures cover only annealing, excluding initialization and temperature scheduling.Source: §5.5 · pp. 19–20

5.6 Scalability and Applicability to Other Problem Classes

DSSA’s runtime workload can scale with flipped spins, but fully connected weight storage remains the principal scaling constraint. Its cycle advantage depends on temporal flip sparsity, while sparse or structured problems may allow memory-footprint reductions.

5.6 Scalability and Applicability to Other Problem Classes

  • 16 Mb of weight memory for 2,048 spins projects to 64 Mb for 4,096 spins and 256 Mb for 8,192 spins under the same 4-bit storage model.These are first-order projections, not implemented results; weight memory scales quadratically, while the spin-gate array, scheduler, and control logic scale approximately linearly.Source: §5.6 · p. 20
  • DSSA scales interaction updates with flipped spins M rather than N, and M remains a small fraction of N on large MAX-CUT instances, particularly in later annealing stages.The effective cycle count per step is sublinear in practice despite full connectivity; weight-memory accesses and interaction accumulation also occur only when spins flip.Source: §5.6 · p. 20
  • DSSA applies to Ising or QUBO problems with pairwise interactions, but its cycle advantage diminishes when strong global constraints keep flip activity high.When M ≈ N, DSSA approaches conventional serialized SSA cycle counts without loss of correctness.Source: §5.6 · pp. 20–21
  • Seven additional Biq Mac Library MAX-CUT instances support DSSA’s applicability beyond the G-set suite, but are not directly comparable with prior ASIC annealers.Comparable hardware results on Biq Mac instances are unavailable.Source: §5.6 · p. 21
  • Sparse encoding, structured sparse matrices, block-sparse storage, compression, and hierarchical or external memories can alleviate quadratic memory growth when coefficients are zero or structured.For arbitrary dense fully connected problems, O(N^2) weight-memory complexity remains an inherent worst-case limitation.Source: §5.6 · p. 21
  • Adaptive scheduling policies or hybrid update strategies that exploit problem-specific structure remain future-work directions.Source: §5.6 · p. 21

5.7 Limitations

The reported timing, area, and power are post-layout estimates rather than fabricated-silicon measurements. Silicon testing across process, voltage, and temperature conditions remains future work.

5.7 Limitations

  • Post-layout simulation does not replace fabricated-silicon measurement, so the reported results are estimates rather than measured chip results.Source: §5.7 · p. 21
  • Process variation, supply noise, clock jitter, on-chip noise, IR drop, clock-distribution non-idealities, and realistic memory access may shift measured performance and power from estimates.Source: §5.7 · p. 21
  • Fabricating the processor and measuring it across process, voltage, and temperature conditions remains future work.Source: §5.7 · p. 21

5.8 Discussion

DSSA reorganizes interaction computation while preserving serialized SSA state-transition probabilities under stated equivalence conditions. Scheduling and idle-step skipping avoid redundant work without changing the Markov chain; the method adds control overhead and no new convergence guarantees.

5.8 Discussion

  • Under the stated assumptions, DSSA implements the same Markov chain as conventional serialized SSA.Each spin is evaluated once per step, its local field matches full recomputation, and the stochastic acceptance probability remains unchanged.Source: §5.8 · p. 21
  • Differential updates preserve each spin’s full-recomputation local field at probabilistic evaluation, preserving the transition probability.The update accumulates exact contributions from flipped spins while retaining previously stored interaction terms.Source: §5.8 · p. 21
  • Spin-select scheduling and priority-based weight reads reorder interaction computations without changing which spins are evaluated or their acceptance rule.Each spin is still updated once per annealing step.Source: §5.8 · pp. 21–22
  • When no spins flip, skipping recomputation preserves the deterministic self-loop and removes no valid state transition.All local fields remain unchanged in that annealing step.Source: §5.8 · p. 22
  • DSSA adds no theoretical convergence guarantees beyond classical simulated annealing, and when M ≈ N it degenerates to conventional serialized SSA behavior without loss of correctness.Source: §5.8 · p. 22
  • The spin-select circuit and priority encoder add control overhead, but occupy a small fraction of die area dominated by on-chip weight memory.The overhead is outweighed by reduced weight-memory accesses and interaction computations when flip activity is sparse.Source: §5.8 · p. 22

6 Conclusion

The 2,048-spin fully connected DSSA processor was evaluated using post-layout simulation, with reported MAX-CUT results and comparisons against recent ASIC annealers and a GPU SSA. Additional Biq Mac results indicate high solution quality beyond the G-set suite.

6 Conclusion

  • At 500 MHz, the processor reports 0.15 mW/spin estimated power, 2.7 ms TTS, and 0.86 mJ energy-to-solution for 2,000-spin MAX-CUT.Comparisons indicate lower per-spin power and the best projected TTS energy at P=0.99 against recent ASIC annealers and a GPU SSA.Source: §6 · p. 22
  • The 2,048-spin fully connected processor was designed in TSMC 28 nm and evaluated using post-layout simulation.Source: §6 · p. 22
  • The additional Biq Mac Library evaluation indicates that DSSA maintains high solution quality beyond the G-set benchmark suite.Source: §6 · p. 22
Loading 2609.09559v1…