Precision meets speed through an FPGA-based natively sparse Ising machine for combinatorial optimization.

Area of Science:

• Computer Engineering
• Computational Science
• Hardware Acceleration

Background:

• Ising machines offer a framework for solving combinatorial optimization problems using dynamical systems.
• Current FPGA-based Ising machines face limitations in problem scale due to memory constraints and multi-FPGA network complexity.

Purpose of the Study:

• To propose a high-accuracy, scalable FPGA-based Ising machine design.
• To achieve state-of-the-art solution speeds on integrated hardware for large-scale optimization problems.

Main Methods:

• Introduction of a sparse data format, tiled coordinate list, for efficient memory usage and matrix-vector operations.
• Implementation of an 8-bit integer quantization mechanism to scale problem sizes without accuracy loss.
• Co-optimization of data flow and hardware design for accelerated performance and reduced computational cost.

Main Results:

• A single FPGA unit capable of handling optimization problems with up to 20,000 variables.
• Significant acceleration of the Ising machine through optimized data flow and hardware design.
• Demonstrated 10- to 68-fold speedups on Max-Cut problems compared to prior FPGA-based Ising machines.

Conclusions:

• The proposed FPGA-based Ising machine design offers a scalable and high-accuracy solution for complex optimization tasks.
• This advancement overcomes previous limitations in problem scale and computational efficiency for FPGA Ising machines.
• The design achieves state-of-the-art performance, paving the way for practical applications in combinatorial optimization.