Optimal and Heuristic Algorithms to Synthesize Lattices of Four-Terminal Switches

Abstract

In this work, we study implementation of Boolean functions with nano-crossbar arrays where each crosspoint behaves as a fourterminal switch controlled by a Boolean literal. These types of arrays are commonly called as switching lattices. We propose optimal and heuristic algorithms that minimize lattice sizes to implement a given Boolean function. The algorithms are mainly constructed on a technique that finds Boolean functions of lattices having independent inputs. This technique works recursively by using transition matrices representing columns and rows of the lattice. It performs symbolic manipulation of Boolean literals as opposed to using truth tables that allows us to successfully find Boolean functions having up to 81 variables corresponding to a 9×9-lattice. With a Boolean function of a certain sized lattice, we check if a given function can be implemented with this lattice size by defining the problem as a satisfiability problem. This process is repeated until a desired solution is found. Additionally, we fix the previously proposed algorithm that is claimed to be optimal. The fixed version guarantees optimal sizes. Finally, we perform synthesis trials on standard benchmark circuits to evaluate the proposed algorithms by considering lattice sizes and runtimes in comparison with the recently proposed three algorithms.