Presentation
HyCiM: A Hybrid Computing-in-Memory QUBO Solver for General Combinatorial Optimization Problems with Inequality Constraints
DescriptionComputationally challenging combinatorial optimization problems (COPs) play a fundamental role in various applications.
To tackle COPs, many Ising machines and Quadratic Unconstrained Binary Optimization (QUBO) solvers have been proposed, which typically involve direct transformation of COPs into Ising models or equivalent QUBO forms (D-QUBO).
However, when addressing COPs with inequality constraints, this D-QUBO approach introduces numerous extra auxiliary variables, resulting in a substantially larger search space, increased hardware costs, and reduced solving efficiency.
In this work, we propose HyCiM, a novel hybrid computing-in-memory (CiM) based QUBO solver framework, designed to overcome aforementioned challenges.
The proposed framework consists of
(i) an innovative transformation method (first to our known) that converts COPs with inequality constraints into an inequality-QUBO form, thus eliminating the need of expensive auxiliary variables and associated calculations;
(ii) "inequality filter", a ferroelectric FET (FeFET)-based CiM circuit that accelerates the inequality evaluation, and filters out infeasible input configurations;
(iii) a FeFET-based CiM annealer that is capable of approaching global solutions of COPs via iterative QUBO computations within a simulated annealing process.
The evaluation results show that HyCiM drastically narrows down the search space, eliminating 2^100 to 2^2536 infeasible input configurations compared to the conventional D-QUBO approach.
Consequently, the narrowed search space, reduced to 2^100 feasible input configurations, leads to a substantial hardware area overhead reduction, ranging from 88.06% to 99.96%.
Additionally, HyCiM consistently exhibits a high solving efficiency, achieving a remarkable average success rate of 98.54%, whereas D-QUBO implementatoin shows only 10.75%.
To tackle COPs, many Ising machines and Quadratic Unconstrained Binary Optimization (QUBO) solvers have been proposed, which typically involve direct transformation of COPs into Ising models or equivalent QUBO forms (D-QUBO).
However, when addressing COPs with inequality constraints, this D-QUBO approach introduces numerous extra auxiliary variables, resulting in a substantially larger search space, increased hardware costs, and reduced solving efficiency.
In this work, we propose HyCiM, a novel hybrid computing-in-memory (CiM) based QUBO solver framework, designed to overcome aforementioned challenges.
The proposed framework consists of
(i) an innovative transformation method (first to our known) that converts COPs with inequality constraints into an inequality-QUBO form, thus eliminating the need of expensive auxiliary variables and associated calculations;
(ii) "inequality filter", a ferroelectric FET (FeFET)-based CiM circuit that accelerates the inequality evaluation, and filters out infeasible input configurations;
(iii) a FeFET-based CiM annealer that is capable of approaching global solutions of COPs via iterative QUBO computations within a simulated annealing process.
The evaluation results show that HyCiM drastically narrows down the search space, eliminating 2^100 to 2^2536 infeasible input configurations compared to the conventional D-QUBO approach.
Consequently, the narrowed search space, reduced to 2^100 feasible input configurations, leads to a substantial hardware area overhead reduction, ranging from 88.06% to 99.96%.
Additionally, HyCiM consistently exhibits a high solving efficiency, achieving a remarkable average success rate of 98.54%, whereas D-QUBO implementatoin shows only 10.75%.
Event Type
Research Manuscript
TimeTuesday, June 255:00pm - 5:15pm PDT
Location3002, 3rd Floor
Design
Emerging Models of Computation