Decomposing Large-Scale Ising Problems on FPGAs: A Hybrid Hardware Approach

Abstract: Emerging analog computing substrates, such as oscillator-based Ising machines, offer rapid convergence times for combinatorial optimization but often suffer from limited scalability due to physical implementation constraints. To tackle real-world problems involving thousands of variables, problem decomposition is required; however, performing this step on standard CPUs introduces significant latency, preventing the high-speed solver from operating at full capacity. This work presents a heterogeneous system that offloads the decomposition workload to an FPGA, tightly integrated with a custom 28nm Ising solver. By migrating the decomposition logic to reconfigurable hardware and utilizing parallel processing elements, the system minimizes the communication latency typically associated with host-device interactions. Our evaluation demonstrates that this co-design approach effectively bridges the speed gap between digital preprocessing and analog solving, achieving nearly 2$\times$ speedup and an energy efficiency improvement of over two orders of magnitude compared to optimized software baselines running on modern CPUs.