Improvements to Satisfiability-Based Boolean Function Bi-Decomposition

Abstract : Boolean function bi-decomposition is pervasive in logic synthesis. Bi-decomposition entails the decomposition of a Boolean function into two other functions connected by a simple two-input gate. Existing solutions are based on Binary Decision Diagrams (BDDs) and, more recently, on Boolean Satisfiability (SAT). Recent work exploited the identification of Minimally Unsatisfiable Subformulas (MUSes) for computing the sets of variables to use in Boolean function bi-decomposition. This paper develops new techniques for improving the use of MUSes in function bi-decomposition. The first technique exploits structural properties of the function being decomposed, whereas the second technique exploits group-oriented MUSes. Experimental results obtained on representative benchmarks from logic synthesis demonstrate significant improvements both in performance and in the quality of decompositions.
Type de document :
Communication dans un congrès
Salvador Mir; Chi-Ying Tsui; Ricardo Reis; Oliver C. S. Choy. 19th International Conference on Very Large Scale Integration (VLSISOC), Oct 2011, Hong Kong, China. Springer, IFIP Advances in Information and Communication Technology, AICT-379, pp.52-72, 2012, VLSI-SoC: Advanced Research for Systems on Chip. 〈10.1007/978-3-642-32770-4_4〉
Liste complète des métadonnées

Littérature citée [43 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01519765
Contributeur : Hal Ifip <>
Soumis le : mardi 9 mai 2017 - 11:39:56
Dernière modification le : vendredi 1 décembre 2017 - 01:15:58
Document(s) archivé(s) le : jeudi 10 août 2017 - 12:41:15

Fichier

978-3-642-32770-4_4_Chapter.pd...
Fichiers produits par l'(les) auteur(s)

Licence


Distributed under a Creative Commons Paternité 4.0 International License

Identifiants

Citation

Huan Chen, Joao Marques-Silva. Improvements to Satisfiability-Based Boolean Function Bi-Decomposition. Salvador Mir; Chi-Ying Tsui; Ricardo Reis; Oliver C. S. Choy. 19th International Conference on Very Large Scale Integration (VLSISOC), Oct 2011, Hong Kong, China. Springer, IFIP Advances in Information and Communication Technology, AICT-379, pp.52-72, 2012, VLSI-SoC: Advanced Research for Systems on Chip. 〈10.1007/978-3-642-32770-4_4〉. 〈hal-01519765〉

Partager

Métriques

Consultations de la notice

70

Téléchargements de fichiers

26