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 > 2026 >

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( 2632 KB)

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

doi: 10.11999/JEIT260780 cstr: 32379.14.JEIT260780

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

1.
College of Semiconductors (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) and 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) are widely encountered in fields such as network optimization, autonomous driving path planning, VLSI design, and computational biology. The solution space of these problems grows exponentially with problem size, making it impossible for traditional von Neumann architectures (e.g., CPUs) to find high-quality solutions within a feasible time. Quantum-inspired Ising machines have emerged as a promising computing paradigm for accelerating COP solving. However, existing CMOS-based Ising machines still face significant challenges in simultaneously achieving high speed, high energy efficiency, and high accuracy. Discrete-time Ising machines often require thousands of iterations and rely heavily on random number generators, leading to large chip area and long solving times. Continuous-time Ising machines suffer from poor solution quality, frequently getting trapped in local minima. To address these limitations, this paper designs and fabricates a high-parallelism simulated adiabatic bifurcation application-specific processor for combinatorial optimization problems in 65 nm CMOS technology. Methods The proposed processor adopts the simulated adiabatic bifurcation (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 phenomena. The processor builds a hardware architecture that supports fully connected spin topologies and leverages the inherent fully parallel spin update characteristic of the SAB algorithm. To achieve bubble-free iterative computation, a three-stage pipelined spin update strategy is proposed, dividing the update process into coupling coefficient access, momentum update, and position update. To reduce the storage overhead introduced by the fully connected coupling matrix, a folded coupling coefficient storage array is designed, exploiting matrix symmetry to eliminate redundant storage. The momentum update unit and position update unit are implemented using 8-bit fixed-point arithmetic (2 bits for integer, 6 bits for fractional part) to achieve SAB evolution with low hardware overhead. The chip is fabricated in 65 nm CMOS technology, occupying an area of 0.47 × 1.25 mm² and operating at a 200 MHz clock frequency and 1 V supply voltage. Results and Discussions The chip achieves a total power consumption of only 14 mW, with the spin evolution module consuming 58% of the total power. The folded coupling coefficient storage array reduces storage area by 52% compared to full matrix storage, and the rectangular restructuring avoids irregular shapes in physical layout, reducing routing congestion and layout voids (Fig.6). The parallel loading access mechanism allows all coupling coefficients to be read and distributed within a single clock cycle, eliminating the memory access bottleneck inherent in serial reading. For predefined Max-Cut problems configured as 8×8 grid structures (64 nodes) with coupling coefficients quantized to 2-bit precision, the chip converges to the global optimum within only 5 computing cycles, achieving a final Ising energy of –4032 (Fig.9). This energy follows the analytical expression (n4−n2)(n4−n2), confirming that the chip solves Max-Cut problems with the shortest solving time. For larger extended Max-Cut problems (108×108 nodes), the simulated adiabatic bifurcation algorithm achieves 100% accuracy relative to the theoretical ground state (Fig.10). Monte Carlo simulations over 1,000 independent trials on randomly generated Max-Cut problems demonstrate that simulated adiabatic bifurcation achieves an average Hamiltonian of –3617.42, significantly outperforming simulated annealing which achieves only –3352.12 (Fig.11). For 3-SAT problems with 40 clauses and 8 variables, the chip solves instances with clause-to-variable ratios of 3, 4, and 5 in approximately 6 μs, 10 μs, and 16 μs, respectively (Fig.12). These results align perfectly with theoretical phase transition predictions, confirming the processor's effectiveness across varying problem complexities. Conclusions This work proposes an simulated adiabatic bifurcation machine that enables fully parallel updates without duplicating spin copies. To improve throughput, a three-stage pipeline strategy is designed that integrates coupling-coefficient access, momentum update, and position update, achieving bubble-free parallel updating and low-latency solving. For sparse coupling coefficients, a folded storage scheme is adopted to significantly reduce memory area overhead. Both momentum and position variables are represented in 8-bit fixed-point format, ensuring sufficient computational accuracy while balancing resource efficiency. Compared with previous fully connected Ising machines, the proposed bifurcation machine achieves 100% solving accuracy, along with higher energy efficiency and lower hardware overhead, demonstrating substantial application prospects in edge-side combinatorial optimization.

FullText(HTML)

References(21)

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]	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.
[21]	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.