Reconfigurable Crossbar Circuit Mapping Large-scale SAT for Electronic Amoeba
Tokushi Maruoka and Seiya Kasai
Mapping of problems is an important issue for solution search hardware solving combinatorial optimization problems. In an amoeba-inspired electronic solution search system called “analog electronic amoeba”, a problem is mapped on the electronic circuit like defining an environment for the slime mold. To map a large instance of Boolean satisfiability problem (SAT) in a compact, scalable, and reconfigurable manner, we investigated the crossbar circuit with a memory array. A compact crossbar layout was derived from the logical structure of the 3-SAT function described with conjunctive normal form. The circuit simulation confirmed that the electronic amoeba with the designed circuit using diode logic could search for a solution. The result showed the feasibility of our approach to solve a large SAT instance by the analog electronic amoeba, necessary for practical applications.
Keywords: Boolean satisfiability problem (SAT), analog electronic amoeba, solution search, problem mapping, crossbar, reconfigurable, diode logic
DOI: 10.32908/ijuc.v20.maruoka