Publication Details
SAT-Based Generation of Optimum Circuits with Polymorphic Behavior Support
Boolean functions, logic synthesis, SAT, PBO, optimum implementation, exact
synthesis, polymorphic circuits.
This paper presents a method for generating optimum multi-level implementations
of Boolean functions based on Satisfiability (SAT) and Pseudo-Boolean
Optimization (PBO) problems solving. The method is able to generate one or
enumerate all optimum implementations, while the allowed target gate types and
gates costs can be arbitrarily specified. Polymorphic circuits represent a newly
emerging computation paradigm, where one hardware structure is capable of
performing two or more different intended functions, depending on instantaneous
conditions in the target operating environment. In this paper we propose the
first method ever, generating provably size-optimal polymorphic circuits.
Scalability and feasibility of the method are documented by providing
experimental results for all NPN-equivalence classes of four-input functions
implemented in AND-Inverter and AND-XOR-Inverter logics without polymorphic
behavior support being used and for all pairs of NPN-equivalence classes of
three-input functions for polymorphic circuits. Finally, several smaller
benchmark circuits were synthesized optimally, both in standard and polymorphic
logics.
@article{BUT163428,
author="FIŠER, P. and HÁLEČEK, I. and SCHMIDT, J. and ŠIMEK, V.",
title="SAT-Based Generation of Optimum Circuits with Polymorphic Behavior Support",
journal="JOURNAL OF CIRCUITS SYSTEMS AND COMPUTERS",
year="2019",
volume="28",
number="1",
pages="1--29",
doi="10.1142/S0218126619400103",
issn="1793-6454",
url="https://www.worldscientific.com/doi/10.1142/S0218126619400103"
}