A Probabilistic Compute Fabric Based on Coupled Ring Oscillators for Solving Combinatorial Optimization Problems
A Probabilistic Compute Fabric Based on Coupled Ring Oscillators for Solving Combinatorial Optimization Problems
复制标题
DOI：
10.1109/jssc.2021.3062821
复制
发表时间：
2021-09-01
影响因子：
5.4
通讯作者：
Kim, Chris H.
中科院分区：
文献类型：
--
作者：
Ahmed, Ibrahim;Chiu, Po-Wei;Kim, Chris H.
非确定性多项式时间困难（NP-hard）组合优化问题（COPs）是难以使用传统计算机求解的，因为找到解的时间随着变量的数量非常迅速地增加。一种有效的替代计算方法使用耦合自旋网络来求解COP。这项工作提出了一个第一个的同类耦合环形振荡器（ROSC）为基础的可扩展的概率伊辛计算机解决NP难COP。设计了一个集成耦合振荡器网络，具有560个ROSC，模拟耦合自旋网络。每个ROSC可以使用基于可编程背靠背（B2B）逆变器的耦合机制耦合到其任何邻居。基于ROSC的自旋和基于B2B反相器的耦合进行了优化，以在宽范围的系统噪声以及电压和温度变化下工作。随机生成的1000个最大割问题被映射并在硬件中求解。与运行在CPU上的商业软件相比，集成的伊辛计算机产生了令人满意的最大切割问题的解决方案。实验表明，集成的基于CMOS的Ising计算机能够以82%-100%的精度找到NP难问题的解。此外，对同一问题的重复测量表明，伊辛计算机可以遍历几个局部极小值，在各种电压和温度变化条件下找到高质量的解决方案。实验结果表明，ROSC是一个潜在的候选人专用硬件加速器，旨在解决广泛的COP。
Nondeterministic polynomial time hard (NP-hard) combinatorial optimization problems (COPs) are intractable to solve using a traditional computer as the time to find a solution increases very rapidly with the number of variables. An efficient alternative computing method uses coupled spin networks to solve COP. This work presents a first-of-its-kind coupled ring oscillator (ROSC)-based scalable probabilistic Ising computer to solve NP-hard COPs. An integrated coupled oscillator network was designed with 560 ROSCs that mimic a coupled spin network. Each ROSC can be coupled to any of its neighbors using programmable back-to-back (B2B) inverter-based coupling mechanism. The ROSC-based spins and B2B inverter-based coupling were optimized to work under a wide range of system noise as well as voltage and temperature variations. Randomly generated 1000 max-cut problems were mapped and solved in the hardware. The integrated Ising computer produced satisfactory solutions of max-cut problems when compared with commercial software running on a CPU. Experiments show that the integrated CMOS-based Ising computer can find the solution to NP-hard problems with an accuracy of 82%-100%. In addition, the repeated measurements of the same problem showed that the Ising computer can traverse through several local minima to find high-quality solutions under various voltage and temperature variation conditions. The experimental results show that ROSCs are a potential candidate for a dedicated hardware accelerator aiming to solve a wide range of COPs.