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

By Seungki Hong ¹, Kyeongwon Jeong ², Taekwang Jang ^1
1 ETH Zurich, Switzerland
² Yonsei University, Republic of Korea

Abstract

Ising machines solve combinatorial optimization problems by annealing a network of spins. On dense problems, where every spin couples to every other, the least expensive hardware step updates all spins at once: stochastic cellular automata (SCA) decide every spin in parallel and read couplings only for the spins that flip. Such synchronous updates, however, create an echo: the previous state of each spin returns to it through its neighbors. On K2000, the Max-Cut benchmark on a complete graph of 2,000 nodes, two-thirds of all flips undo a flip that the same spin made one step earlier. This paper presents Anechoic, an FPGA Ising machine that subtracts this echo from every decision. Dynamical mean-field theory identifies the echo as an Onsager reaction and gives the strength of its one-step part: the number of spins whose flip probability lies strictly between 0 and 1, divided by twice the temperature. The decision logic already flags these spins, so this Onsager correction costs one population count per step, and a temperature-scaled approximation needs no count. A hand-written RTL engine executes a dense 2,000-spin step in 18.1 cycles plus 0.14 cycles per flip, so every step and flip that the correction saves is saved time. In experiments, the counted and the temperature-scaled correction both find better K2000 cuts at every step budget than each of five published binary-spin algorithms run at its paper’s settings. Twelve engines at 250MHz on anAMDAlveo V80 reach a cut of at least 33,000 on K2000 with 99% probability in 0.05ms, 5.2× faster than the fastest published hardware, at 5.4 mJ per solution; with 2-bit couplings, the temperature-scaled form is also faster than uncorrected SCA on 48 of 51 sparse G-set graphs. On an NVIDIA GH200 GPU, the identical engine is 2.3× slower and needs 8.0× more energy persolution, though its 240 con current anneals give 2.3× higher throughput. As a GlobalFoundries 22nm ASIC routed at 1.25GHz (typical corner), twelve engines would reach the target in about 10µs, 26× faster than the fastest published hardware, with 0.20mJ of engine energy per solution. The code is available at https://github.com/skethz/anechoic.

To read the full article, click here