BACK TO INDEX

Publications about 'optimal synthesis'
Articles in journal or book chapters
  1. A.P. Tran, M. Ali Al-Radhawi, E. Ernst, and E.D. Sontag. Optimization of heuristic logic synthesis by iteratively reducing circuit substructures using a database of optimal implementations. 2021. Note: Submitted. Keyword(s): Heuristic logic minimizer, Boolean circuit reduction, optimal synthesis, logic optimization, synthetic biology.
    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 of 5.16% for 5-input circuits and 4.54% for 6-input circuits on outputs provided by the logic synthesis tool extit{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. In addition, the framework proposed here is likely to be adaptable to other types of circuits. An implementation of the described algorithm, HLM (Hybrid Logic Minimizer), is available at https://github.com/sontaglab/HLM/.



BACK TO INDEX




Disclaimer:

This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders.




Last modified: Thu Jun 3 23:14:09 2021
Author: sontag.


This document was translated from BibTEX by bibtex2html