An FPGA-based Max-K-Cut Accelerator Exploiting Oscillator Synchronization Model

In this work, we demonstrate a one of its kind FPGA-based compute engine that uses new computational models inspired by the synchronization dynamics of coupled oscillators to solve the general form of the computationally intractable Max-K-Cut combinatorial optimization problem (COP). Prior work on developing oscillator-inspired models for solving COPs, namely oscillator Ising machines, only directly map the MaxCut (K=2) problem. Solving other COPs (e.g., K>2) using such models entails graph decomposition and the use of auxiliary variables that effectively increase the graph size that must be solved by the hardware. This not only increases the computation time but also degrades the solution quality. In contrast, our model offers a generalized formulation that can directly solve the general form of the Max-K-Cut problem for any value of K without the need for auxiliary variables. Subsequently, by mapping the models on an FPGA platform in a way that exploits its fine-grained parallelism, we accelerate the Max-K-Cut problem (K=2, 3, and 4 shown here) on graphs with up to 10,000 nodes. When benchmarking against the state-of-the-art simulated bifurcation machine (SBM) that only uses the Ising model, our implementation offers an average 17× speedup for the Max-2-Cut and up to 390× average speedup for the Max-3-Cut and Max-4-Cut problems for similar solution quality in all cases.