A Probabilistic Self-annealing Compute Fabric based on 560 Hexagonally Coupled Ring Oscillators for Solving Combinatorial Optimization Problems

被引：37

作者：

Ahmed, Ibrahim ^{[1
]}

Chiu, Po-Wei ^{[1
]}

Kim, Chris H. ^{[1
]}

机构：

[1] Univ Minnesota, Dept ECE, 200 Union St SE, Minneapolis, MN 55455 USA

来源：

2020 IEEE SYMPOSIUM ON VLSI CIRCUITS | 2020年

关键词：

Annealing processor; Ising machine; oscillator-based computation; max-cut;

D O I：

10.1109/vlsicircuits18222.2020.9162869

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

NP-hard combinatorial optimization problems (COPs) are very expensive to solve with traditional computers. COPs can be mapped to a coupled spin network where the ground state of the system is the solution. We propose a scalable truly coupled CMOS oscillator-based integrated system mimicking a spin network to solve COPs in hardware. Our simple latch-based coupling design finds solutions of max-cut problems with 85%-100% accuracy 104-106 times faster than commercial software running on a CPU.

引用

页数：2

共 7 条

[1]

Dutta S., 2019, IEDM, P911

[2] Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming [J].

Goemans, MX ;

Williamson, DP .

JOURNAL OF THE ACM, 1995, 42 (06) :1115-1145

[3] Quantum annealing with manufactured spins [J].

Johnson, M. W. ;

Amin, M. H. S. ;

Gildert, S. ;

Lanting, T. ;

Hamze, F. ;

Dickson, N. ;

Harris, R. ;

Berkley, A. J. ;

Johansson, J. ;

Bunyk, P. ;

Chapple, E. M. ;

Enderud, C. ;

Hilton, J. P. ;

Karimi, K. ;

Ladizinsky, E. ;

Ladizinsky, N. ;

Oh, T. ;

Perminov, I. ;

Rich, C. ;

Thom, M. C. ;

Tolkacheva, E. ;

Truncik, C. J. S. ;

Uchaikin, S. ;

Wang, J. ;

Wilson, B. ;

Rose, G. .

NATURE, 2011, 473 (7346) :194-198

[4] Ising formulations of many NP problems [J].

Lucas, Andrew .

FRONTIERS IN PHYSICS, 2014, 2 :1-14

[5] Large-Scale Photonic Ising Machine by Spatial Light Modulation [J].

Pierangeli, D. ;

Marcucci, G. ;

Conti, C. .

PHYSICAL REVIEW LETTERS, 2019, 122 (21)

[6]

Takemoto T, 2019, ISSCC DIG TECH PAP I, V62, P52, DOI 10.1109/ISSCC.2019.8662517

[7] A 20k-Spin Ising Chip to Solve Combinatorial Optimization Problems With CMOS Annealing [J].

Yamaoka, Masanao ;

Yoshimura, Chihiro ;

Hayashi, Masato ;

Okuyama, Takuya ;

Aoki, Hidetaka ;

Mizuno, Hiroyuki .

IEEE JOURNAL OF SOLID-STATE CIRCUITS, 2016, 51 (01) :303-309

← 1 →