Logo image
Back
Multi-phase Coupled CMOS Ring Oscillator based Potts Machine
Conference proceeding   Open access

Multi-phase Coupled CMOS Ring Oscillator based Potts Machine

Yilmaz Ege Gonul and Baris Taskin
Proceedings of the 43rd IEEE/ACM International Conference on Computer-Aided Design, pp 1-9
09 Apr 2025
DOI: https://doi.org/10.1145/3676536.3676720
Featured in Collection :   Research Supported by Drexel Libraries' OA Programs
url
https://doi.org/10.1145/3676536.3676720View
Published, Version of Record (VoR)Open Access via Drexel Libraries Read and Publish Program 2025CC BY V4.0,  Open

Abstract

Hardware -- Emerging technologies -- Analysis and design of emerging devices and systems -- Emerging architectures
This paper presents a coupled ring oscillator based Potts machine to solve NP-hard combinatorial optimization problems (COPs). Potts model is a generalization of the Ising model, capturing multivalued spins in contrast to the binary-valued spins allowed in the Ising model. Similar to recent literature on Ising machines, the proposed architecture of Potts machines implements the Potts model with interacting spins represented by coupled ring oscillators. Unlike Ising machines which are limited to two spin values, Potts machines model COPs that require a larger number of spin values. A major novelty of the proposed Potts machine is the utilization of the N-SHIL (Sub-Harmonic Injection Locking) mechanism, where multiple stable phases are obtained from a single (i.e. ring) oscillator. In evaluation, 3-coloring problems from the DIMACS SATBLIB benchmark and two randomly generated larger problems are mapped to the proposed architecture. The proposed architecture is demonstrated to solve problems of varying size with 89% to 92% accuracy averaged over multiple iterations. The simulation results show that there is no degradation in accuracy, no significant increase in solution time, and only a linear increase in power dissipation with increasing problem sizes up to 2000 nodes.

Metrics

4 Record Views

Details

Logo image