A Ferroelectric Compute-in-Memory Annealer for Combinatorial Optimization Problems
arXiv:2309.13853 · doi:10.1038/s41467-024-46640-x
Abstract
Computationally hard combinatorial optimization problems (COPs) are ubiquitous in many applications, including logistical planning, resource allocation, chip design, drug explorations, and more. Due to their critical significance and the inability of conventional hardware in efficiently handling scaled COPs, there is a growing interest in developing computing hardware tailored specifically for COPs, including digital annealers, dynamical Ising machines, and quantum/photonic systems. However, significant hurdles still remain, such as the memory access issue, the system scalability and restricted applicability to certain types of COPs, and VLSI-incompatibility, respectively. Here, a ferroelectric field effect transistor (FeFET) based compute-in-memory (CiM) annealer is proposed. After converting COPs into quadratic unconstrained binary optimization (QUBO) formulations, a hardware-algorithm co-design is conducted, yielding an energy-efficient, versatile, and scalable hardware for COPs. To accelerate the core vector-matrix-vector (VMV) multiplication of QUBO formulations, a FeFET based CiM array is exploited, which can accelerate the intended operation in-situ due to its unique three-terminal structure. In particular, a lossless compression technique is proposed to prune typically sparse QUBO matrix to reduce hardware cost. Furthermore, a multi-epoch simulated annealing (MESA) algorithm is proposed to replace conventional simulated annealing for its faster convergence and better solution quality. The effectiveness of the proposed techniques is validated through the utilization of developed chip prototypes for successfully solving graph coloring problem, indicating great promise of FeFET CiM annealer in solving general COPs.
arXiv comment39 pages, 12 figures
References in corpus (8)
- Ising formulations of many NP problems
- Limits on Fundamental Limits to Computation
- Large-scale photonic Ising machine by spatial light modulation
- Experimental investigation of performance differences between Coherent Ising Machines and a quantum annealer
- Computational Role of Multiqubit Tunneling in a Quantum Annealer
- Coherent Ising machines -- Quantum optics and neural network perspectives
- Fast Solving Complete 2000-Node Optimization Using Stochastic-Computing Simulated Annealing
- Local Energy Distribution Based Hyperparameter Determination for Stochastic Simulated Annealing
Cited by in corpus (5)
- C-Nash: A Novel Ferroelectric Computing-in-Memory Architecture for Solving Mixed Strategy Nash Equilibrium
- FeBiM: Efficient and Compact Bayesian Inference Engine Empowered with Ferroelectric In-Memory Computing
- TReCiM: Lower Power and Temperature-Resilient Multibit 2FeFET-1T Compute-in-Memory Design
- Device-Algorithm Co-Design of Ferroelectric Compute-in-Memory In-Situ Annealer for Combinatorial Optimization Problems
- Charge-Density-Wave Oscillator Networks for Solving Combinatorial Optimization Problems