Optimization of heuristic logic synthesis by iteratively reducing circuit substructures using a database of optimal implementations

Abstract

Minimal synthesis of Boolean functions is an NP-hard problem, and heuristic approaches typically give suboptimal circuits. However, in the emergent field of synthetic biology, genetic logic designs that use even a single additional Boolean gate can render a circuit unimplementable in a cell. This has led to a renewed interest in the field of optimal multilevel Boolean synthesis. For small numbers (1-4) of inputs, an exhaustive search is possible, but this is impractical for large circuits. In this work, we demonstrate that even though it is challenging to build a database of optimal implementations for anything larger than 4-input Boolean functions, a database of 4-input optimal implementations can be used to greatly reduce the number of logical gates required in larger heuristic logic synthesis implementations. The proposed algorithm combines the heuristic results with an optimal implementation database and yields average improvements in fractional gate-count reduction relative to ABC of 5.16% for 5-input circuits and 4.54% for 6-input circuits on outputs provided by the logic synthesis tool ABC. In addition to the gains in the efficiency of the implemented circuits, this work also attests to the importance and practicality of the field of optimal synthesis, even if it cannot directly provide results for larger circuits. The focus of this work is on circuits made exclusively of 2-input NOR gates but the presented results are readily applicable to 2-input NAND circuits as well as (2-input) AND/NOT circuits. The framework proposed here is likely to be adaptable to other types of circuits. Moreover, a small computational pipeline is provided for integration with synthetic biology tools such as Cello. An implementation of the described algorithm, HLM (Hybrid Logic Minimizer), is available at https://github.com/sontaglab/HLM/.