An official website of the United States government
In this paper, we report new results on a novel Ising machine technology for solving combinatorial optimization problems using networks of coupled self-sustaining oscillators. Specifically, we present several working hardware prototypes using CMOS electronic oscillators, built on bread-boards/perfboards and PCBs, implementing Ising machines consisting of up to 240 spins with programmable couplings. We also report that, just by simulating the differential equations of such Ising machines of larger sizes, good solutions can be achieved easily on benchmark optimization problems, demonstrating the effectiveness of oscillator-based Ising machines.
more »
« less
Performance of Oscillator Ising Machines on Realistic MU-MIMO Decoding Problems
Ising machines have recently been attracting attention due to their apparent ability to solve5 difficult combinatorial problems using analog operational principles. Oscillator Ising Machines6 (OIM) are especially attractive because they can be implemented easily as integrated circuits (ICs)7 in standard CMOS electronics. We explore the performance of OIM for decoding noisy Multi-User8 MIMO signals, a problem of considerable interest in modern telecommunications. Our results9 indicate that OIM-based decoding achieves error rates almost as good as the optimal Maximum10 Likelihood method, over a wide range of practical signal-to-noise (SNR) values. At high SNR11 values, OIM achieves ~20x fewer errors than LMMSE, a decoding method used widely in industry12 today. We also investigate the influence of parameter precision on decoding performance, finding13 that using 6 or more bits of precision largely retains OIM’s advantages across all SNR values. We14 estimate that straightforward CMOS OIM implementations can easily solve MU-MIMO decoding15 problems in under 10ns, more than 100x faster than current industrial requirements. We conclude16 that oscillator Ising machines can be effective for real-world applications, possibly serving as an17 important enabler for future telecommunication standards. Our results and data provide guidance18 for designing hardware OIM prototypes specialized for MU-MIMO decoding.
more »
« less
- PAR ID:
- 10562149
- Publisher / Repository:
- Research Square
- Date Published:
- Journal Name:
- Research Square Preprint
- ISSN:
- 2693-5015
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Nonlinear dynamical systems such as coupled oscillators are being actively investigated as Ising machines for solving computationally hard problems in combinatorial optimization. Prior works have established the equivalence between the global minima of the cost function describing the coupled oscillator system and the ground state of the Ising Hamiltonian. However, the properties of the oscillator Ising machine (OIM) from a nonlinear control viewpoint, such as the stability of the OIM solutions, remain unexplored. Therefore, in this work, using nonlinear control-theoretic analysis, we (i) identify the conditions required to ensure the functionality of the coupled oscillators as an Ising machine, (ii) show that all globally optimal phase configurations may not always be stable, resulting in some configurations being more favored over others and, thus, creating a biased OIM, and (iii) elucidate the impact of the stability of locally optimal phase configurations on the quality of the solution computed by the system. Our work, fostered through the unique convergence between nonlinear control theory and analog systems for computing, provides a new toolbox for the design and implementation of dynamical system-based computing platforms.more » « less
-
Abstract Many combinatorial problems can be mapped to Ising machines, i.e., networks of coupled oscillators that settle to a minimum-energy ground state, from which the problem solution is inferred. This work proposes DROID, a novel event-driven method for simulating the evolution of a CMOS Ising machine to its ground state. The approach is accurate under general delay-phase relations that include the effects of the transistor nonlinearities and is computationally efficient. On a realistic-size all-to-all coupled ring oscillator array, DROID is nearly four orders of magnitude faster than a traditional HSPICE simulation and two orders of magnitude faster than a commercial fast SPICE solver in predicting the evolution of a coupled oscillator system and is demonstrated to attain a similar distribution of solutions as the hardware.more » « less
-
Abstract A prominent approach to solving combinatorial optimization problems on parallel hardware is Ising machines, i.e., hardware implementations of networks of interacting binary spin variables. Most Ising machines leverage second-order interactions although important classes of optimization problems, such as satisfiability problems, map more seamlessly to Ising networks with higher-order interactions. Here, we demonstrate that higher-order Ising machines can solve satisfiability problems more resource-efficiently in terms of the number of spin variables and their connections when compared to traditional second-order Ising machines. Further, our results show on a benchmark dataset of Booleank-satisfiability problems that higher-order Ising machines implemented with coupled oscillators rapidly find solutions that are better than second-order Ising machines, thus, improving the current state-of-the-art for Ising machines.more » « less
-
This work advances the understanding of oscillator Ising machines (OIMs) as a nonlinear dynamic system for solving computationally hard problems. Specifically, we classify the infinite number of all possible equilibrium points of an OIM, including non-0/π ones, into three types based on their structural stability properties. We then employ the stability analysis techniques from control theory to analyze the stability property of all possible equilibrium points and obtain the necessary and sufficient condition for their stability. As a result of these analytical results, we establish, for the first time, the threshold of the binarization in terms of the coupling strength and strength of the second harmonic signal. Furthermore, we provide an estimate of the domain of attraction of each asymptotically stable equilibrium point by employing the Lyapunov stability theory. Finally, we illustrate our theoretical conclusions by numerical simulation.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Journal Article:
- The DOI is not currently available.
