Application of Probabilistic Spin Logic (PSL) in Detecting Satisfiability of a Boolean Function

摘要

Probabilistic Spin Logic (PSL) is a computing model that can be implemented using stochastic units (called p-bits) such as low-barrier nanomagnets. Besides computing a given Boolean function, PSL can also compute the inverse of the function. In this paper, we propose a methodology to exploit the invertibility of PSL in detecting the satisfiability (SAT) of a given Boolean function. First, we propose an algorithm to derive a PSL implementation for any Boolean function given in Conjunctive Normal Form (CNF). For a given SAT problem in CNF, we realize the given function in PSL using the proposed algorithm, clamp only the output to logic `1' and detect the satisfiability of the given function by observing the probability distribution of the possible states. We demonstrate that PSL is highly selective of the satisfiable input patterns even for tough problems where only one out of one million input patterns is satisfiable. A key parameter deciding the effectiveness of the proposed technique is the time that is allowed for PSL computation, which would ultimately depend on the characteristics of the PSL hardware implementation.