Advancing FPGA-Based Ising Machines with Simulated Bifurcation

Simulated Adiabatic Bifurcation (aSB) is a quantum-inspired algorithm employed to obtain approximate solutions of large-scale combinatorial optimization problems written according to the Ising form, emulating the adiabatic evolution of a network of Kerr-non-linear parametric oscillators (KPOs). The Ising formulation is a physical-mathematical model that utilizes bipolar binary variables associated with magnetic spins, able to align or counter-align according to mutual interactions and the possible presence of an external magnetic field. Therefore, aSB encodes the problem associating with each spin an oscillator capable of exhibiting bifurcation as the system is excited by an external pumping signal. After bifurcation, each oscillator follows one of the two branches corresponding to one of the two states of the Ising spin. Hence, the optimum solution represents the ground state of the oscillators’ network. Moreover, aSB enables the concurrent update of multiple variables at each step, making it particularly indicated for implementation in Field Programmable Gate Arrays (FPGAs) or Graphics Processing Units (GPUs) since a high level of parallelization can be attained. However, aSB generates analog errors attributed to employing continuous variables in describing oscillator states instead of discrete variables native to the Ising model. In response, ballistic (bSB) and discrete (dSB) versions of the same algorithm were introduced in the literature, ensuring that the obtained result is at least a local minimum of the system Hamiltonian. Furthermore, bSB and dSB can be enhanced by introducing a thermal fluctuation term, which simulates the heating of the oscillators’ network, helping the algorithm escape from local minima. The thesis conducted a comprehensive analysis of dSB, bSB, and its thermal variant (HbSB) using dedicated software models, focusing on benchmark maxcut and knapsack problems. In addition, the feasibility of using a fixed-point representation was investigated, demonstrating an almost negligible impact on the accuracy of the outcomes. The goal was to identify the algorithm ensuring an optimal trade-off between speed, area, and results accuracy to propose a new digital architecture for FPGA implementation. After all considerations, dSB, including its heated version, was chosen for hardware implementation. The key advantage of dSB over bSB, lies in the discretization of its variables, thus permitting to save most of the multipliers involved in the computation. A SystemVerilog architecture description was given, leaving the possibility of externally defining algorithm parameters, which can be passed as input before computation starts. Furthermore, parallelization parameters were described as generic regardless of the actual implementation, enabling architecture adaptation according to the available hardware. Indeed, the algorithm can be significantly unrolled, improving performance. However, the main restriction is associated with the quantity of allocatable resources. The last step was transferring the RTL design to FPGA using the available Kria KV260 System on Module, exploiting an onboard processor to send initialization values and parameters to the unit and collect results. The outcomes were first used to test the design against software models. Finally, a comparison with state-of-the-art Ising machines was performed, and performance was evaluated in terms of the accuracy of the results and computation speed.