Publication Details

SAT-Based Generation of Optimum Circuits with Polymorphic Behavior Support

FIŠER Petr, HÁLEČEK Ivo, SCHMIDT Jan and ŠIMEK Václav. SAT-Based Generation of Optimum Circuits with Polymorphic Behavior Support. Journal of Circuits, Systems and Computers, vol. 28, no. 1, 2019, pp. 1-29. ISSN 1793-6454. Available from: https://www.worldscientific.com/doi/10.1142/S0218126619400103
Czech title
Generování optimálních obvodů s podporou polymorfního chování na bázi metodiky SAT
Type
journal article
Language
english
Authors
Fišer Petr, doc. Ing., Ph.D. (FIT CTU)
Háleček Ivo (FIT CTU)
Schmidt Jan, doc. Ing. (FIT CTU)
Šimek Václav, Ing. (DCSY FIT BUT)
URL
Keywords

Boolean functions, logic synthesis, SAT, PBO, optimum implementation, exact synthesis, polymorphic circuits.

Abstract

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.

Published
2019
Pages
1-29
Journal
Journal of Circuits, Systems and Computers, vol. 28, no. 1, ISSN 1793-6454
Publisher
World Scientific Publishing Co Pte Ltd
DOI
UT WoS
000503001600011
EID Scopus
BibTeX
@ARTICLE{FITPUB12249,
   author = "Petr Fi\v{s}er and Ivo H\'{a}le\v{c}ek and Jan Schmidt and V\'{a}clav \v{S}imek",
   title = "SAT-Based Generation of Optimum Circuits with Polymorphic Behavior Support",
   pages = "1--29",
   journal = "Journal of Circuits, Systems and Computers",
   volume = 28,
   number = 1,
   year = 2019,
   ISSN = "1793-6454",
   doi = "10.1142/S0218126619400103",
   language = "english",
   url = "https://www.fit.vut.cz/research/publication/12249"
}
Back to top