Optimal and heuristic algorithms to synthesize lattices of four-terminal switches

M. Ceylan Morgül*, Mustafa Altun

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

7 Citations (Scopus)


In this work, we study implementation of Boolean functions with nano-crossbar arrays where each crosspoint behaves as a four-terminal 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.

Original languageEnglish
Pages (from-to)60-70
Number of pages11
Publication statusPublished - Jan 2019

Bibliographical note

Publisher Copyright:
© 2018 Elsevier B.V.


This work is supported by the EU-H2020-RISE project NANOxCOMP # 691178 and the TUBITAK-Career project # 113E760 .

FundersFunder number
Horizon 2020 Framework Programme691178


    • Logic synthesis
    • Nano-crossbar arrays
    • Satisfiability
    • Switching lattices


    Dive into the research topics of 'Optimal and heuristic algorithms to synthesize lattices of four-terminal switches'. Together they form a unique fingerprint.

    Cite this