Logic synthesis for networks of four-terminal switches.

Abstract

We develop a synthesis method to implement Boolean functions with lattices of four-terminal switches. Each switch is controlled by a Boolean literal. We address the synthesis problem of how best to assign literals to switches in a lattice in order to implement a given target Boolean function, with the goal of minimizing the lattice size, measured in terms of the number of switches. We present an efficient algorithm for this task. The algorithm has polynomial time complexity. It produces lattices with a size that grows linearly with the number of products of the target Boolean function. We evaluate our synthesis method on standard benchmark circuits and compare the results to a lower-bound calculation on the lattice size. Although not tied to any particular technology, we comment that our synthesis results are applicable to emerging technologies such as nanowire crossbar arrays and magnetic switch-based structures. We address the problem of implementing Boolean functions with lattices of four-terminal switches in the presence of defects. We assume that such defects occur probabilistically. Our approach is predicated on the mathematical phenomenon of percolation. With random connectivity, percolation gives rise to a sharp non-linearity in the probability of global connectivity as a function of the probability of local connectivity. We exploit this phenomenon to compute Boolean functions robustly. A significant tangent for this work is its mathematical contribution: lattice-based implementations present a novel view of the properties of Boolean function duality. We study the applicability of these properties to the famous problem of testing whether two monotone Boolean functions in irredundant sum-of-products form are dual. This is one of the few problems in circuit complexity whose precise tractability status is unknown.