Presentation
C-Nash: A Novel Ferroelectric Computing-in-Memory Architecture for Solving Mixed Strategy Nash Equilibrium
DescriptionThe concept of Nash equilibrium (NE), pivotal within game theory, has garnered widespread attention across numerous industries.
However, verifying the existence of NE poses a significant computational challenge, classified as an NP-complete problem.
Recent advancements introduced several quantum Nash solvers aimed at identifying pure strategy NE solutions (i.e., binary solutions) by integrating slack terms into the objective function, commonly referred to as slack-quadratic unconstrained binary optimization (S-QUBO).
However, incorporation of slack terms into the quadratic optimization results in changes of the objective function, which may cause incorrect solutions.
Furthermore, these quantum solvers only identify a limited subset of pure strategy NE solutions, and fail to address mixed strategy NE (i.e., decimal solutions), leaving many solutions undiscovered.
In this work, we propose C-Nash, a novel ferroelectric computing-in-memory (CiM) architecture that can efficiently handle both pure and mixed strategy NE solutions.
The proposed framework consists of
(i) a transformation method that converts quadratic optimization into a MAX-QUBO form without introducing additional slack variables, thereby avoiding objective function changes;
(ii) a ferroelectric FET (FeFET) based bi-crossbar structure for storing payoff matrices and accelerating the core vector-matrix-vector (VMV) multiplications of QUBO form;
(iii) A winner-takes-all (WTA) tree implementing the MAX form and a two-phase based simulated annealing (SA) logic for searching NE solutions.
Evaluations demonstrate that C-Nash has up to 68.6% increase in the success rate for identifying NE solutions, finding all pure and mixed NE solutions rather than only a portion of pure NE solutions, compared to D-Wave based quantum approaches.
Moreover, C-Nash boasts a reduction up to 157.9X/79.0X in time-to-solutions in comparison to D-Wave 2000 Q6 and D-Wave Advantage 4.1, respectively.
However, verifying the existence of NE poses a significant computational challenge, classified as an NP-complete problem.
Recent advancements introduced several quantum Nash solvers aimed at identifying pure strategy NE solutions (i.e., binary solutions) by integrating slack terms into the objective function, commonly referred to as slack-quadratic unconstrained binary optimization (S-QUBO).
However, incorporation of slack terms into the quadratic optimization results in changes of the objective function, which may cause incorrect solutions.
Furthermore, these quantum solvers only identify a limited subset of pure strategy NE solutions, and fail to address mixed strategy NE (i.e., decimal solutions), leaving many solutions undiscovered.
In this work, we propose C-Nash, a novel ferroelectric computing-in-memory (CiM) architecture that can efficiently handle both pure and mixed strategy NE solutions.
The proposed framework consists of
(i) a transformation method that converts quadratic optimization into a MAX-QUBO form without introducing additional slack variables, thereby avoiding objective function changes;
(ii) a ferroelectric FET (FeFET) based bi-crossbar structure for storing payoff matrices and accelerating the core vector-matrix-vector (VMV) multiplications of QUBO form;
(iii) A winner-takes-all (WTA) tree implementing the MAX form and a two-phase based simulated annealing (SA) logic for searching NE solutions.
Evaluations demonstrate that C-Nash has up to 68.6% increase in the success rate for identifying NE solutions, finding all pure and mixed NE solutions rather than only a portion of pure NE solutions, compared to D-Wave based quantum approaches.
Moreover, C-Nash boasts a reduction up to 157.9X/79.0X in time-to-solutions in comparison to D-Wave 2000 Q6 and D-Wave Advantage 4.1, respectively.
Event Type
Research Manuscript
TimeTuesday, June 254:15pm - 4:30pm PDT
Location3002, 3rd Floor
Design
Emerging Models of Computation