A High-Parallelism Simulated Adiabatic Bifurcation Processor for Combinatorial Optimization Problems

LI Renlong; HAO Xin; CHEN Zhuojun; DING Ding

doi:10.11999/JEIT260780

Article Contents

Article Navigation > Journal of Electronics & Information Technology > 2025 >

LI Renlong, HAO Xin, CHEN Zhuojun, DING Ding. A High-Parallelism Simulated Adiabatic Bifurcation Processor for Combinatorial Optimization Problems[J]. Journal of Electronics & Information Technology. doi: 10.11999/JEIT260780

Citation:

LI Renlong, HAO Xin, CHEN Zhuojun, DING Ding. A High-Parallelism Simulated Adiabatic Bifurcation Processor for Combinatorial Optimization Problems[J]. Journal of Electronics & Information Technology. doi: 10.11999/JEIT260780

Citation:

PDF( 2735 KB)

A High-Parallelism Simulated Adiabatic Bifurcation Processor for Combinatorial Optimization Problems

doi: 10.11999/JEIT260780 cstr: 32379.14.JEIT260780

LI Renlong^1
,,
HAO Xin¹,
CHEN Zhuojun¹,
DING Ding^{2, 3
,
,}

1.
College of Integrated Circuits, Hunan University, Changsha 410082, China
2.
School of Intelligent Engineering and Intelligent Manufacturing, Hunan University of Technology and Business, Changsha 410205, China
3.
Xiangjiang Laboratory, Changsha 410205, China

Funds: Major Scientific and Technological Research Project of Hunan Province (2025QK2007), Key Project of the Education Department of Hunan Province (25A0459), Key Project of Xiangjiang Laboratory (25XJ02003)

Received Date: 2026-06-09
Accepted Date: 2026-07-13
Rev Recd Date: 2026-07-13

Available Online: 2026-07-23

Abstract

Abstract

Objective Combinatorial Optimization Problems (COPs) arise in numerous applications, including network optimization, autonomous driving path planning, VLSI design, and computational biology. Their solution space grows exponentially with problem size, making it difficult for conventional von Neumann architectures (e.g., CPUs) to obtain high-quality solutions within practical time limits. Quantum-inspired Ising machines have emerged as a promising computing paradigm for solving COPs. However, existing CMOS-based Ising machines still face significant challenges in simultaneously achieving high speed, high energy efficiency, and high solution accuracy. Discrete-time Ising machines typically require thousands of iterations and depend on random number generators, leading to large chip area and long Time to Solution (TTS). Continuous-time Ising machines converge more rapidly but generally exhibit inferior solution quality because they are prone to becoming trapped in local minima. To address these limitations, a high-parallelism Simulated Adiabatic Bifurcation (SAB) processor is designed and fabricated using 65 nm CMOS technology. Methods The proposed processor implements the SAB algorithm, which is inspired by quantum adiabatic optimization. Unlike simulated annealing, SAB does not require Gibbs sampling or random number generators to escape local minima. The algorithm models each spin as a nonlinear oscillator and solves a set of ordinary differential equations to simulate the adiabatic evolution of a classical nonlinear Hamiltonian system exhibiting bifurcation behavior. The proposed processor adopts a hardware architecture that supports a fully connected spin topology and exploits the inherent fully parallel spin-update capability of the SAB algorithm. To enable bubble-free iterative computation, a three-stage pipelined spin-update strategy is proposed, consisting of coupling-coefficient access, momentum update, and position update. To reduce the storage overhead associated with the fully connected coupling matrix, a folded coupling-coefficient storage array is designed by exploiting matrix symmetry to eliminate redundant storage. The momentum update and position update units are implemented using 8-bit fixed-point arithmetic (2 integer bits and 6 fractional bits), enabling SAB evolution with low hardware overhead. The fabricated processor occupies an area of 0.47 × 1.25 mm² and operates at a clock frequency of 200 MHz with a 1 V supply voltage. Results and Discussions The fabricated processor consumes only 14 mW, with the spin evolution module accounting for 58% of the total power consumption. The folded coupling-coefficient storage array reduces storage area by 52% compared with full coupling-matrix storage, while its rectangular organization alleviates routing congestion and layout voids during physical implementation (Fig. 6). The parallel loading access mechanism enables all coupling coefficients to be read and distributed within a single clock cycle, eliminating the memory-access bottleneck associated with serial loading. For predefined Max-Cut problems configured as an 8 × 8 grid (64 nodes) with 2-bit coupling coefficients, the processor converges to the global optimum within five update cycles and achieves a final Ising energy (Hamiltonian) of −4 032 (Fig. 9). This result agrees with the analytical expression n4−n2, confirming the minimum TTS for these Max-Cut instances. For larger Max-Cut problems (108 × 108 nodes), the SAB algorithm achieves 100% solving accuracy relative to the theoretical ground state (Fig. 10). Monte Carlo simulations over 1,000 independent randomly generated Max-Cut instances show that SAB achieves an average Hamiltonian of –3 617.42, outperforming simulated annealing, which yields an average Hamiltonian of –3 352.12 (Fig. 11). For 3-SAT problems containing 40 clauses and 8 variables, the processor solves instances with Clause-to-Variable Ratio (CTV) values of 3, 4, and 5 in approximately 6 ms, 10 ms, and 16 ms, respectively (Fig. 12). These results agree with the theoretical phase-transition behavior and demonstrate the effectiveness of the proposed processor across problems of different complexity. Conclusions A high-parallelism SAB processor that enables fully parallel spin updates without duplicating spin replicas is presented. A three-stage pipeline integrating coupling-coefficient access, momentum update, and position update provides bubble-free parallel updating and low-latency solving. A folded coupling-coefficient storage architecture significantly reduces storage area overhead, while 8-bit fixed-point representations for momentum and position balance computational accuracy with hardware efficiency. Compared with previously reported fully connected Ising machines, the proposed processor achieves 100% solving accuracy for the evaluated benchmark problems while providing higher energy efficiency and lower hardware overhead, demonstrating strong potential for edge combinatorial optimization applications.

FullText(HTML)

References(20)

References

[1]	潘钰, 胡航, 金虎, 等. 非授权频段下无人机辅助通信的轨迹与资源分配优化[J]. 电子与信息学报, 2024, 46(11): 4287–4294. doi: 10.11999/JEIT240275. PAN Yu, HU Hang, JIN Hu, et al. Trajectory and resource allocation optimization for unmanned aerial vehicles assisted communications in unlicensed bands[J]. Journal of Electronics & Information Technology, 2024, 46(11): 4287–4294. doi: 10.11999/JEIT240275.
[2]	赖李洋, 郑锫骏, 梁海成, 等. 路径规划算法的高层综合设计研究[J]. 电子与信息学报, 2024, 46(11): 4132–4140. doi: 10.11999/JEIT240210. LAI Liyang, ZHENG Peijun, LIANG Haicheng, et al. Case study of high level synthesis on path planning algorithm[J]. Journal of Electronics & Information Technology, 2024, 46(11): 4132–4140. doi: 10.11999/JEIT240210.
[3]	陈家瑞, 吴昭怡, 游勇杰, 等. 基于概率模型的集成电路寄生参数提取算法[J]. 电子与信息学报, 2025, 47(9): 3198–3207. doi: 10.11999/JEIT250458. CHEN Jiarui, WU Zhaoyi, YOU Yongjie, et al. A probability-based parasitic extraction algorithm for global-routed VLSI designs[J]. Journal of Electronics & Information Technology, 2025, 47(9): 3198–3207. doi: 10.11999/JEIT250458.
[4]	钱煜, 杨泽禹, 王然然, 等. 铁电基的存算一体组合优化求解器[J]. 电子与信息学报, 2025, 47(9): 3104–3115. doi: 10.11999/JEIT250369. QIAN Yu, YANG Zeyu, WANG Ranran, et al. Ferroelectric FET-based compute-in-memory solver for combinatorial optimization problems[J]. Journal of Electronics & Information Technology, 2025, 47(9): 3104–3115. doi: 10.11999/JEIT250369.
[5]	洪庆辉, 孙辰, 肖平旦, 等. 复值Hopfield神经网络的信号盲检测一步计算电路[J]. 电子与信息学报, 2024, 46(11): 4123–4131. doi: 10.11999/JEIT240224. HONG Qinghui, SUN Chen, XIAO Pingdan, et al. One-step calculation circuit of blind signal detection using complex-valued hopfield neural network[J]. Journal of Electronics & Information Technology, 2024, 46(11): 4123–4131. doi: 10.11999/JEIT240224.
[6]	FU Fangfa, LOU Binglei, CHEN Yukun, et al. Improving reliability in NOCs by reconstructing location distribution of management cores[J]. Microelectronics Journal, 2019, 90: 133–140. doi: 10.1016/j.mejo.2019.06.001.
[7]	LI Tonghui, DUAN Xiaofeng, LIU Kai, et al. Parameter extraction for photodiode equivalent circuit model based on hybrid genetic algorithm[J]. Microelectronics Journal, 2024, 143: 106017. doi: 10.1016/j.mejo.2023.106017.
[8]	CHEN Jingyang, YU Zhiping, and ZHU Xiaolei. A 28 nm Ising machine with adaptive majority voter and reduction algorithms for high-performance combinatorial optimization[J]. Microelectronics Journal, 2025, 159: 106621. doi: 10.1016/j.mejo.2025.106621.
[9]	SU Yuqi, KIM T T H, and KIM B. FlexSpin: A CMOS Ising machine with 256 flexible spin processing elements with 8-b coefficients for solving combinatorial optimization problems[J]. IEEE Journal of Solid-State Circuits, 2024, 59(8): 2659–2670. doi: 10.1109/JSSC.2024.3352907.
[10]	XIE Shanshan, RAMAN S R S, NI Can, et al. Ising-CIM: A reconfigurable and scalable compute within memory analog Ising accelerator for solving combinatorial optimization problems[J]. IEEE Journal of Solid-State Circuits, 2022, 57(11): 3453–3465. doi: 10.1109/JSSC.2022.3176610.
[11]	YAMAMOTO K, KAWAMURA K, ANDO K, et al. STATICA: A 512-spin 0.25M-weight annealing processor with an all-spin-updates-at-once architecture for combinatorial optimization with complete spin-spin interactions[J]. IEEE Journal of Solid-State Circuits, 2020, 56(1): 165–178. doi: 10.1109/JSSC.2020.3027702.
[12]	LIU Yixuan, WU Qiqiao, YANG Honghu, et al. Enhancing all-to-all RRAM Ising machines with randomized granular update strategies for solving combinatorial optimization problems[J]. IEEE Transactions on Circuits and Systems I: Regular Papers, 2025, 72(9): 4877–4890. doi: 10.1109/TCSI.2024.3523999.
[13]	GRIMALDI A, MAZZA L, RAIMONDO E, et al. Evaluating spintronics-compatible implementations of Ising machines[J]. Physical Review Applied, 2023, 20(2): 024005. doi: 10.1103/PhysRevApplied.20.024005.
[14]	YAMAOKA M, YOSHIMURA C, HAYASHI M, et al. A 20k-spin Ising chip to solve combinatorial optimization problems with CMOS annealing[J]. IEEE Journal of Solid-State Circuits, 2016, 51(1): 303–309. doi: 10.1109/JSSC.2015.2498601.
[15]	SU Yuqi, KIM H, and KIM B. CIM-spin: A scalable CMOS annealing processor with digital in-memory spin operators and register spins for combinatorial optimization problems[J]. IEEE Journal of Solid-State Circuits, 2022, 57(7): 2263–2273. doi: 10.1109/JSSC.2021.3139901.
[16]	AHMED I, CHIU P W, and KIM C H. A probabilistic self-annealing compute fabric based on 560 hexagonally coupled ring oscillators for solving combinatorial optimization problems[C]. 2020 IEEE Symposium on VLSI Circuits, Honolulu, USA, 2020: 1–2. doi: 10.1109/VLSICircuits18222.2020.9162869.
[17]	BAE J, OH W, KOO J, et al. CTLE-Ising: A 1440-spin continuous-time latch-based Isling machine with one-shot fully-parallel spin updates featuring equalization of spin states[C]. 2023 IEEE International Solid-State Circuits Conference (ISSCC), San Francisco, USA, 2023: 142–144. doi: 10.1109/ISSCC42615.2023.10067622.
[18]	TATSUMURA K, YAMASAKI M, and GOTO H. Scaling out Ising machines using a multi-chip architecture for simulated bifurcation[J]. Nature Electronics, 2021, 4(3): 208–217. doi: 10.1038/s41928-021-00546-4.
[19]	KAWAMURA K, YU J, OKONOGI D, et al. Amorphica: 4-replica 512 fully connected spin 336MHz metamorphic annealer with programmable optimization strategy and compressed-spin-transfer multi-chip extension[C]. 2023 IEEE International Solid-State Circuits Conference (ISSCC), San Francisco, USA, 2023: 42–44. doi: 10.1109/ISSCC42615.2023.10067504.
[20]	CHEN Y H, CHOU C A, NIEN C F, et al. Design and implementation of a VLSI-based annealing accelerator for efficiently solving combinatorial optimization problems[J]. IEEE Transactions on Circuits and Systems II: Express Briefs, 2024, 71(9): 4291–4295. doi: 10.1109/TCSII.2024.3380609.