一种面向组合优化问题的高并行度模拟绝热分岔处理器

李任龙; 郝昕; 陈卓俊; 丁玎

doi:10.11999/JEIT260780

一种面向组合优化问题的高并行度模拟绝热分岔处理器

doi: 10.11999/JEIT260780 cstr: 32379.14.JEIT260780

李任龙¹,
郝昕¹,
陈卓俊¹,
丁玎^{2, 3, ,}

1.
湖南大学半导体学院(集成电路学院) 长沙 410082
2.
湖南工商大学智能工程与智能制造学院长沙 410205
3.
湘江实验室长沙 410205

基金项目: 湖南省重大科技攻关项目 (2025QK2007)，湖南省教育厅重点项目(25A0459)，湘江实验室重点项目(25XJ02003)

详细信息

作者简介:
李任龙：男，博士生，研究方向为专用加速器、模拟计算等

郝昕：男，硕士生，研究方向为专用加速器、模拟计算等

陈卓俊：男，教授，研究方向为集成电路设计

丁玎：女，高工，研究方向为存算一体芯片的设计与性能研究

通讯作者:
丁玎　dingding@hutb.edu.cn

中图分类号: TN492
计量
- 文章访问数: 23
- HTML全文浏览量: 6
- PDF下载量: 6
- 被引次数: 0
出版历程
- 收稿日期: 2026-06-09
- 修回日期: 2026-07-13
- 录用日期: 2026-07-13
- 网络出版日期: 2026-07-23

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

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)

摘要

摘要: 组合优化问题巨大的解空间使得基于穷举搜索的策略难以在可行时间内找到高质量解。受量子启发的伊辛机为加速求解组合优化问题提供了新的计算范式，但实现兼具高速度、高能效和高精度的CMOS基伊辛机仍然是一项重大挑战。对这一问题，本文基于65 nm CMOS工艺设计并流片了一款面向组合优化问题的高并行度模拟绝热分岔专用处理器。该处理器利用模拟绝热分岔算法的全并行自旋更新特性，构建支持全连接拓扑的硬件架构，并提出自旋流水线更新策略，将耦合系数访问、动量更新和位置更新划分为三级流水线，实现无气泡迭代计算。为降低全连接耦合矩阵带来的存储开销，本文进一步设计折叠式耦合系数存储阵列，利用矩阵对称性减少冗余存储，使存储面积降低52%。同时，动量更新单元和位置更新单元采用定点数实现，在较低硬件开销下完成模拟绝热分岔演化。测试结果表明，该芯片在200 MHz下功耗为14 mW，求解64节点最大割问题仅需要25ns，求解40子句、8变量的SAT问题不超过16 μs，验证了所提架构在组合优化加速中的有效性。
- 组合优化问题 /
- 模拟绝热分岔 /
- 伊辛机 /
- 专用集成电路
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.
- Combinatorial optimization problems (COPs) /
- Simulated adiabatic bifurcation (SAB) /
- Ising machine /
- Application-Specific Integrated Circuit (ASIC)

HTML全文

图 1 伊辛机工作流程与64节点全连接问题及其伊辛交互矩阵。 (a) 伊辛机工作流程。 (b) 64节点全连接问题。 (c) 组合优化问题到伊辛模型的映射。

下载: 全尺寸图片幻灯片

图 2 离散时间模拟退火伊辛机、连续时间模拟退火伊辛机与模拟绝热分岔机。 (a) 离散时间与连续时间模拟退火伊辛机的计算类型。 (b) 模拟绝热分岔机

下载: 全尺寸图片幻灯片

图 3 模拟绝热分岔算法伪代码

下载: 全尺寸图片幻灯片

图 4 模拟绝热分岔机整体架构

下载: 全尺寸图片幻灯片

图 5 模拟绝热分岔机时序图

下载: 全尺寸图片幻灯片

图 6 折叠耦合系数存储矩阵

下载: 全尺寸图片幻灯片

图 7 (a) 动量演化单元和 (b) 位置演化单元原理图

下载: 全尺寸图片幻灯片

图 8 (a) 芯片显微图；(b)测试环境。

下载: 全尺寸图片幻灯片

图 9 (a) 各模块功耗占比饼状图；(b)各模块面积占比饼状图。

下载: 全尺寸图片幻灯片

图 10 (a) 预定义最大割问题：红心、黑桃、方块； (b) 随更新周期变化的能量演化。

下载: 全尺寸图片幻灯片

图 11 扩展最大割问题(108 × 108)及分岔结果。 (a) 月亮与星星原始图； (b) 月亮与星星的最大割结果；(c) 月亮与星星的能量演化； (d) 蝴蝶原始图； (e) 蝴蝶的最大割结果； (f) 蝴蝶的能量演化。

下载: 全尺寸图片幻灯片

图 12 (a) 随机生成的Max-Cut问题在演化过程的自旋状态图片；(b) 伊辛系统哈密顿量随着自旋更新周期的变化。

下载: 全尺寸图片幻灯片

图 13 (a) 在随机生成的最大割问题上，模拟绝热分岔与模拟退火各执行1000次的蒙特卡洛仿真结果对比；(b) 选取一次求解问题中自旋位置的分岔曲线。

下载: 全尺寸图片幻灯片

图 14 求解 3-SAT 问题求解时间与未满足子句数量之间的动态关系。

下载: 全尺寸图片幻灯片

表 1 与其他全连接伊辛机的性能对比

	ISSCC’23 [19]	TCAS-I’21 [20]	ISSCC’20 [11]	TCAS-II’24 [21]	本工作
工艺	40 nm	28 nm	65 nm	90 nm	65 nm
自旋数目	512	36	512	128	64
系数位宽	8 bit	4 bit	2 bit	5 bit	1-4 bit
退火算法	RPA	RAGU	SCA	SA	SAB
工作频率	320 MHz	N/A	300 MHz	100 MHz	200 MHz
芯片面积	9 mm²	N/A	12 mm²	2.15 mm²	0.59 mm²
每自旋面积	0.018 mm²	N/A	0.023 mm²	0.016 mm²	0.009 mm²
芯片功耗	151.6 mW	137.5 mW	252 mW	106 mW	14 mW
每自旋功耗	0.3 mW	3.82 mW	0.49 mW	0.83 mW	0.22 mW
是否需要随机数	需要	需要	需要	需要	不需要

下载: 导出CSV

参考文献(21)

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