A 1,968-node coupled ring oscillator circuit for combinatorial optimization problem solving

William Moy, Ibrahim Ahmed, Po wei Chiu, John Moy, Sachin S. Sapatnekar, Chris H. Kim

Research output: Contribution to journalArticlepeer-review

Abstract

Computational architectures that are optimized to solve non-deterministic polynomial-time hard or complete problems are of use in the development of machine learning, logistical planning and pathfinding. A range of quantum-, optical- and spintronic-based approaches have been explored for solving such combinatorial optimization problems, but they remain complicated to build and to scale. Here we report a scalable ring-oscillator-based integrated circuit for optimization problem solving. Our 1,968-node King’s graph ring oscillator array has five levels of coupling strengths and can achieve up to 95% accuracy for randomly generated combinatorial optimization problems. The measured average power consumption of the Ising chip is 0.042 W and it takes less than 50 oscillation cycles to resolve to the ground state. Our device is resilient to environmental and variation effects. By using a multi-phase phase measurement circuit, we also capture the true phase behaviour within a coupled-oscillator integrated circuit.

Original languageEnglish (US)
Pages (from-to)310-317
Number of pages8
JournalNature Electronics
Volume5
Issue number5
DOIs
StatePublished - May 2022

Bibliographical note

Funding Information:
I.A. and C.H.K. acknowledges the initial support of the project from the National Science Foundation under ECCS 1739635 and the Semiconductor Research Corporation (SRC) under 2759.007. For the chip testing and data analysis works, W.M. and C.H.K. have been supported in part by the SRC under 3024.001. We would like to thank SRC’s industry liaisons for their technical feedback.

Publisher Copyright:
© 2022, The Author(s), under exclusive licence to Springer Nature Limited.

Fingerprint

Dive into the research topics of 'A 1,968-node coupled ring oscillator circuit for combinatorial optimization problem solving'. Together they form a unique fingerprint.

Cite this