A Reconfigurable CMOS Ising Machine With Three-Body Spin Interactions for Solving Boolean Satisfiability With Direct Mapping
Yuqi Su, Tony Tae-Hyoung Kim, Bongjin Kim · IEEE Solid-State Circuits Letters · 2023
Ising machines have recently emerged as efficient computers for nondeterministic polynomial-time hard (NPhard) combinatorial optimization problems (COPs). While most prior works have built their Ising machines with spins arranged in a graph with only two-body interactions, many real-world COPs, including a popular Boolean satisfiability problem (SAT), often involve many-body spin interactions. This letter presents a novel Ising machine that can directly map and solve 3-SAT problems (i.e., SAT problems with at most three literals per clause). The proposed Ising machine eliminates the hardware overhead due to the ancillary spins required for approximate mapping used for the prior Ising machines with two-body interactions only. For evaluation, a prototype chip is fabricated using 65nm and solved 3-SAT problems and their variants (a weighted max 3-SAT). The 65nm chip occupies 0.345mm2 for 128-1024 embedded spins with 8-bit interaction coefficients and consumes 3.73μW per spin at 1.2V and 64MHz.