Snowball: A Scalable All-to-All Ising Machine with Dual-Mode Markov Chain Monte Carlo Spin Selection and Asynchronous Spin Updates for Fast Combinatorial Optimization
This work improves Ising machines for combinatorial optimization, but it is incremental as it builds on existing digital architectures and algorithms.
The paper tackled the problem of reducing time-to-solution in Ising machines for combinatorial optimization by addressing hardware topology, spin selection, and precision challenges, resulting in an 8× reduction in time-to-solution compared to a state-of-the-art Ising machine on a benchmark instance.
Ising machines have emerged as accelerators for combinatorial optimization. To enable practical deployment, this work aims to reduce time-to-solution by addressing three challenges: (1) hardware topology, (2) spin selection and update algorithms, and (3) scalable coupling-coefficient precision. Restricted topologies require minor embedding; naive parallel updates can oscillate or stall; and limited precision can preclude feasible mappings or degrade solution quality. This work presents Snowball, a digital, scalable, all-to-all coupled Ising machine that integrates dual-mode Markov chain Monte Carlo spin selection with asynchronous spin updates to promote convergence and reduce time-to-solution. The digital architecture supports wide, configurable coupling precision, unlike many analog realizations at high bit widths. A prototype on an AMD Alveo U250 accelerator card achieves an 8$\times$ reduction in time-to-solution relative to a state-of-the-art Ising machine on the same benchmark instance.