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

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

doi:10.11999/JEIT260780

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

doi: 10.11999/JEIT260780 cstr: 32379.14.JEIT260780

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

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

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

详细信息

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

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

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

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

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

中图分类号: TN492
计量
- 文章访问数: 555
- HTML全文浏览量: 264
- PDF下载量: 20
- 被引次数: 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^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)

摘要

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

HTML全文

图 1 伊辛机工作流程与64节点全连接问题及其伊辛交互矩阵

下载: 全尺寸图片幻灯片

图 2 离散时间模拟退火伊辛机、连续时间模拟退火伊辛机与模拟绝热分岔机

下载: 全尺寸图片幻灯片

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

下载: 全尺寸图片幻灯片

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

下载: 全尺寸图片幻灯片

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

下载: 全尺寸图片幻灯片

图 6 伊辛系统的自旋演化计算架构

下载: 全尺寸图片幻灯片

图 7 伊辛计算芯片的硬件实现与验证

下载: 全尺寸图片幻灯片

图 8 伊辛计算芯片的硬件资源开销分析

下载: 全尺寸图片幻灯片

图 9 预定义Max-Cut问题的求解过程与收敛特性

下载: 全尺寸图片幻灯片

图 10 扩展最大割问题(108 × 108)及分岔结果

下载: 全尺寸图片幻灯片

图 11 机Max-Cut问题的动态求解特性

下载: 全尺寸图片幻灯片

图 12 机Max-Cut问题的求解性能评估

下载: 全尺寸图片幻灯片

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

下载: 全尺寸图片幻灯片

1 Simulated adiabatic bifurcation

Input: J_i,j, x, p, Δt, N, T, K, t_stop
Output: sgn(x(T))
1: Random initialization of x in N
2: Random initialization of p in Np
3: while (t < t_stop)
4: 　for i = 1 to N do
5: 　　x_i(t_n+1) = x_i(t_n) + p_i(t_n)Δt
6: 　// Update Position of All Spin
7: 　end for loop
8: 　for i = 1 to N do
9: 　　Δp_i(t_n+1) = –Kx_i³(t_n+1) - Ox(t_n+1) + ΣJ_i,jx_i(t_n+1)
10: 　 p_i(t_n+1) = p_i(t_n) + Δp_i(t_n+1)Δt
11: // Update Momentum of All Spin
12: end for loop
13: 　t_n+1 = t_n + 1
14: 　// Time evolution
15: end while loop
16: output sgn(x(t_stop))

下载: 导出CSV

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

	ISSCC’23 [19]	TCAS-I’21	ISSCC’20 [11]	TCAS-II’24 [20]	本工作
工艺	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

参考文献(20)

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