Combinatorial optimization problems (COPs) have extensive applications in real-life scenarios such as logistics, resource allocation, finance, and transportation. These problems typically belong to the class of non-deterministic polynomial-time hard (NP-hard) problems, exhibiting extremely high computational complexity. Currently, COP solvers based on traditional Von Neumann architecture face exponential growth in chip size and energy cost with problem scale, while their performance and solving capabilities exponentially decline. There is an urgent need to explore more efficient application-specific integrated circuits for solving COPs. This is also one of the key initiatives of $238 million microelectronics program announced by the United States Department of Defense last year.
Recently, researchers including Assistant Professor Xunzhao Yin, Professor Zhiguo Shi, Professor Cheng Zhuo from Zhejiang University, in collaboration with international partners, published a research paper titled Ferroelectric compute-in-memory annealer for combinatorial optimization problems in Nature Communications. The paper reports the first ferroelectric-based compute-in-memory solver for COPs, offering a promising software-hardware co-design approach.
The team proposed methods for transforming objective functions of various COPs (such as Max-Cut, graph coloring, and prime factorization problems) into quadratic unconstrained binary optimization (QUBO) forms. They fabricated a 1kb-scale ferroelectric-based compute-in-memory array, which fully leverages the three-input AND gate logic characteristics of ferroelectric FET (FeFET) to achieve single-step acceleration of vector-matrix-vector multiplication, the core operations of QUBO. The array chip thereby significantly improves the computational performance of the proposed solver framework from the perspective of hardware. Additionally, the team proposed a lossless compression method for QUBO matrices tailored to the FeFET’s three-terminal structure, along with corresponding mapping methods for asymmetric input vectors and matrix weights, effectively reducing the hardware overheads. Finally, building upon the QUBO single-iteration acceleration of the compute-in-memory chip, they introduced a multi-epoch simulated annealing algorithm, efficiently enhancing the overall quality and speed of problem-solving process.
The team's hardware-software co-design solver has reduced chip overhead by 75%, doubled the solving speed compared to traditional solvers, and improved solution quality by 27%, significantly enhancing the scalability and solving capability of combinatorial optimization solvers. This work lays the foundation for subsequent research on larger-scale, more efficient, and more universally ASIC chips for combinatorial optimization. Zhejiang University is the first affiliation, with Assistant Professor Xunzhao Yin and doctoral student Yu Qian from the College of Information Science and Electronic Engineering as joint first authors, and Professor Cheng Zhuo from Zhejiang University, Researcher Thomas Kämpfe from Fraunhofer IPMS Institute, Germany, and Professor Kai Ni from University of Notre Dame, United States as corresponding authors.
Figure 1 Framework of the combinatorial optimization solver based on a ferroelectric compute-in-memory integrated chip.
