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 104-106 times faster than commercial software running on a CPU.
Original language | English (US) |
---|---|
Title of host publication | 2020 IEEE Symposium on VLSI Circuits, VLSI Circuits 2020 - Proceedings |
Publisher | Institute of Electrical and Electronics Engineers Inc. |
ISBN (Electronic) | 9781728199429 |
DOIs | |
State | Published - Jun 2020 |
Event | 2020 IEEE Symposium on VLSI Circuits, VLSI Circuits 2020 - Honolulu, United States Duration: Jun 16 2020 → Jun 19 2020 |
Publication series
Name | IEEE Symposium on VLSI Circuits, Digest of Technical Papers |
---|---|
Volume | 2020-June |
Conference
Conference | 2020 IEEE Symposium on VLSI Circuits, VLSI Circuits 2020 |
---|---|
Country/Territory | United States |
City | Honolulu |
Period | 6/16/20 → 6/19/20 |
Bibliographical note
Funding Information:We measure and reprogram the chip 100 times using the same graph shown in Fig. 5a. Fig. 5b shows the probability of a unit cell changing the state between iterations. Interestingly, Fig. 5c shows each iteration produces very similar results as max-cut can have multiple similar solutions. Hence, despite the solutions of different iterations are not the same, the quality of the result is surprisingly consistent. The distribution of Hamming distances between iterations, as shown in Fig. 5d, confirms the solutions are indeed widely different from each other, which proves the chip’s ability to converge to different local minima rather than finding deterministic solutions. The probabilistic nature of the chip and traversing through multiple local minima is a very crucial characteristic to solve COPs. Measured COP Results We map COPs with various levels of “difficulty” to the chip as shown in Fig. 6. We compare our results with a commercial COP software, LocalSolver, which is 104-106 times slower than our chip with roughly 4 orders of magnitude higher power consumption. The measured solutions for “easy” COPs have an accuracy between 98%-100%. Similarly, we mapped “difficult” COPs with various graph dimensions to the chip. For each dimension, we measured 150 problems. We compared the measured results with LocalSolver, as well as 1 million Monte-Carlo solutions sampled from the entire solution-space. The chip accuracy increases with annealing. We anneal the chip only three times to reduce delay. Fig. 7 shows the distribution of “difficult” max-cut results measured from the chip under nominal VDD and room temperature, and the sampled solutions normalized with software solution. The chip results are consistently better than the best solution from Monte-Carlo runs. For smaller graphs, such as 6×6, the chip finds cut values within 95% of LocalSolver. For larger graph, such as 26×18, the chip finds an average cut value within 86% of the software solution. A common heuristic finds max-cut solution within 88% of optimal result [7] indicating the chip solutions are satisfactory for practical applications. We compare prior works with our design in Fig. 8. The lack of details and accuracy statistics of previous proposals makes it difficult to fully compare various approaches. We measured 1000 problems with various difficulty levels in this work. Additionally, compared to quantum computers, our design does not require a special process and can work at room temperature. Fig. 9 shows the chip photo and summary. Acknowledgement This work was supported in part by the Center for Probabilistic Spin Logic for Low-Energy Boolean and Non-Boolean Computing (CAPSL), one of the Nanoelectronic Computing Research (nCORE) Centers as task 2759.007, a Semiconductor Research Corporation (SRC) program sponsored by the NSF through ECCS 1739635. References [1] A. Lucas, Front. Phys., vol. 2, pp. 1-15, 2014. [2] M. Johnson, Nature, vol. 473, pp. 194-198, 2011. [3] M. Yamaoka, JSSC, vol. 51, pp. 303-309, 2016. [4] T. Takemoto, ISSCC, pp. 52-54, 2019. [5] D. Pierangeli, PRL, vol. 122, 213902, 2019. [6] S. Dutta, IEDM, pp. 911-914, 2019. [7] M. X., Goemans, JACM, vol. 42, pp. 1115-1145, 1995.
Publisher Copyright:
© 2020 IEEE.
Keywords
- Annealing processor
- Ising machine
- max-cut
- oscillator-based computation