Multi-Phase Coupled CMOS Ring Oscillator based Potts Machine
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866915229717233664 |
|---|---|
| author | Gonul, Yilmaz Ege Taskin, Baris |
| author_facet | Gonul, Yilmaz Ege Taskin, Baris |
| contents | This paper presents a coupled ring oscillator based Potts ma chine to solve NP-hard combinatorial optimization problems
(COPs). Potts model is a generalization of the Ising model, cap turing 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 imple ments the Potts model with interacting spins represented by cou pled 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 pro posed 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2504_04223 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Multi-Phase Coupled CMOS Ring Oscillator based Potts Machine Gonul, Yilmaz Ege Taskin, Baris Hardware Architecture Emerging Technologies This paper presents a coupled ring oscillator based Potts ma chine to solve NP-hard combinatorial optimization problems (COPs). Potts model is a generalization of the Ising model, cap turing 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 imple ments the Potts model with interacting spins represented by cou pled 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 pro posed 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. |
| title | Multi-Phase Coupled CMOS Ring Oscillator based Potts Machine |
| topic | Hardware Architecture Emerging Technologies |
| url | https://arxiv.org/abs/2504.04223 |