All-to-all reconfigurability with sparse and higher-order Ising machines

Area of Science:

• Computational physics
• Hardware acceleration
• Optimization algorithms

Background:

• Domain-specific hardware for hard optimization problems is a growing field.
• Ising Machines (IM) are a promising hardware approach.
• Probabilistic bits (p-bits) offer a novel component for IMs.

Purpose of the Study:

• Evaluate p-bit based Ising Machines on a representative hard optimization problem: 3-Regular 3-Exclusive OR Satisfiability (3R3X).
• Introduce and implement a novel multiplexed architecture for enhanced network functionality and parallel Gibbs sampling.
• Compare performance against existing IMs and explore methods for improving computational efficiency.

Main Methods:

• Developed a multiplexed architecture on a Field-Programmable Gate Array (FPGA).
• Employed chromatic Gibbs sampling and adaptive parallel tempering algorithms.
• Implemented higher-order interactions to enhance performance for the XORSAT problem.

Main Results:

• The FPGA-based p-bit IM demonstrated competitive algorithmic and prefactor advantages over D-Wave, Toshiba, and Fujitsu IMs.
• Higher-order interactions improved prefactors for XORSAT without altering algorithmic scaling.
• FPGA p-bit performance is currently slower than GPU-accelerated greedy algorithms.

Conclusions:

• FPGA implementations of p-bit IMs show promise for tackling hard optimization problems.
• Scaled magnetic versions of p-bit IMs hold potential for substantial future performance gains.
• P-bit IMs represent a significant advancement in specialized optimization hardware.