A Probabilistic Self-Annealing Compute Fabric Based on 560 Hexagonally Coupled Ring Oscillators for Solving Combinatorial Optimization Problems
Ibrahim Ahmed, Po-Wei Chiu, Chris H. Kim
Abstract
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 10 <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">4</sup> -10 <sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">6</sup> times faster than commercial software running on a CPU.
Topics & Concepts
ScalabilitySimulated annealingProbabilistic logicComputer scienceSoftwareCombinatorial optimizationRing (chemistry)Theoretical computer scienceAlgorithmComputational scienceArtificial intelligenceProgramming languageOperating systemChemistryOrganic chemistryQuantum Computing Algorithms and ArchitectureComplexity and Algorithms in GraphsVLSI and FPGA Design Techniques