A Probabilistic Compute Fabric Based on Coupled Ring Oscillators for Solving Combinatorial Optimization Problems

Ibrahim Ahmed, Po Wei Chiu, William Moy, Chris H. Kim

Research output: Contribution to journalArticlepeer-review

Abstract

Nondeterministic polynomial time hard (NP-hard) combinatorial optimization problems (COPs) are intractable to solve using a traditional computer as the time to find a solution increases very rapidly with the number of variables. An efficient alternative computing method uses coupled spin networks to solve COP. This work presents a first-of-its-kind coupled ring oscillator (ROSC)-based scalable probabilistic Ising computer to solve NP-hard COPs. An integrated coupled oscillator network was designed with 560 ROSCs that mimic a coupled spin network. Each ROSC can be coupled to any of its neighbors using programmable back-to-back (B2B) inverter-based coupling mechanism. The ROSC-based spins and B2B inverter-based coupling were optimized to work under a wide range of system noise as well as voltage and temperature variations. Randomly generated 1000 max-cut problems were mapped and solved in the hardware. The integrated Ising computer produced satisfactory solutions of max-cut problems when compared with commercial software running on a CPU. Experiments show that the integrated CMOS-based Ising computer can find the solution to NP-hard problems with an accuracy of 82%-100%. In addition, the repeated measurements of the same problem showed that the Ising computer can traverse through several local minima to find high-quality solutions under various voltage and temperature variation conditions. The experimental results show that ROSCs are a potential candidate for a dedicated hardware accelerator aiming to solve a wide range of COPs.

Original languageEnglish (US)
JournalIEEE Journal of Solid-State Circuits
DOIs
StatePublished - Sep 1 2021

Bibliographical note

Publisher Copyright:
IEEE

Keywords

  • Annealing processor
  • Computational modeling
  • Couplings
  • Hardware
  • Integrated circuit modeling
  • Ising computer
  • Ising model
  • Oscillators
  • Probabilistic logic
  • Ring oscillators
  • combinatorial optimization problem (COP)
  • oscillator-based computation.

Fingerprint

Dive into the research topics of 'A Probabilistic Compute Fabric Based on Coupled Ring Oscillators for Solving Combinatorial Optimization Problems'. Together they form a unique fingerprint.

Cite this