Custom CMOS Ising Machine Based on Relaxed Burer-Monteiro-Zhang Heuristic
Custom CMOS Ising Machine Based on Relaxed Burer-Monteiro-Zhang Heuristic
复制标题
DOI：
10.1109/tc.2023.3272278
复制
发表时间：
2023-10
影响因子：
3.7
通讯作者：
Aditya Shukla;M. Erementchouk;P. Mazumder
中科院分区：
文献类型：
--
作者：
Aditya Shukla;M. Erementchouk;P. Mazumder
确定大型图的最大切割可能需要不切实际的长时间，需要近似算法和/或专用计算平台。Burer、Monteiro和Zhang对最大割的启发式不仅在许多方面被证明是有利的，而且也适用于其他NP完全问题。从加速计算的角度来看，启发式算法的实现挑战在于它的梯度下降动态，这可以减少到几个正弦内核操作应用到图的每个边缘。我们之前已经建立了一个宽松的动力学启发式的理论基础，类似于Burer等人提出的最大切割，但适合于自定义模拟CMOS的加速计算。在这项工作中，我们提出了第一个完全定制的模拟集成电路实现我们的启发式130纳米CMOS技术的动态。在一个计算机越来越特殊的时代，我们的算法电路协同设计，最初用于最大切割，引入了一种通用的方法，适用于各种实际的大规模NP完全问题。
Determining the maximum cut of large graphs may require impractically long time, necessitating approximate algorithms and/or specialized computing platforms. A heuristic by Burer, Monteiro and Zhang for max-cut has not only been shown to be advantageous in many respects, but is also applicable to other NP-complete problems. From the perspective of accelerated computing, the heuristic's implementational challenge lies in its gradient-descent dynamics, which could be reduced to several sinusoidal kernel operations applied to each edge of the graph. We had previously established the theoretical underpinnings of a relaxed dynamical heuristic for max-cut similar to the one proposed by Burer et al. but suited for accelerated computing on custom analog CMOS. In this work, we present the first fully custom analog integrated circuit implementing the dynamics of our heuristic on 130-nm CMOS technology. In an era of increasing specificity of computing machines, our algorithm-circuit co-design, originally for max-cut, introduces a versatile approach applicable to a diverse set of practical large-scale NP-complete problems.