Using Extended Logical Primitives for Efficient BDD Building

David Fernandez-Amoros, Sergio Bra, Ernesto Aranda-Escolástico and Ruben Heradio
Additional contact information
David Fernandez-Amoros: Deptment of Computer Systems and Software Engineering, Universidad Nacional de Educacion a Distancia (UNED), 28040 Madrid, Spain
Sergio Bra: Deptment of Computer Systems and Software Engineering, Universidad Nacional de Educacion a Distancia (UNED), 28040 Madrid, Spain
Ernesto Aranda-Escolástico: Deptment of Computer Systems and Software Engineering, Universidad Nacional de Educacion a Distancia (UNED), 28040 Madrid, Spain
Ruben Heradio: Deptment of Computer Systems and Software Engineering, Universidad Nacional de Educacion a Distancia (UNED), 28040 Madrid, Spain

Mathematics, 2020, vol. 8, issue 8, 1-17

Abstract: Binary Decision Diagrams (BDDs) have been used to represent logic models in a variety of research contexts, such as software product lines, circuit testing, and plasma confinement, among others. Although BDDs have proven to be very useful, the main problem with this technique is that synthesizing BDDs can be a frustratingly slow or even unsuccessful process, due to its heuristic nature. We present an extension of propositional logic to tackle one recurring phenomenon in logic modeling, namely groups of variables related by an exclusive-or relationship, and also consider two other extensions: one in which at least n variables in a group are true and another one for in which at most n variables are true. We add XOR, atLeast-n and atMost-n primitives to logic formulas in order to reduce the size of the input and also present algorithms to efficiently incorporate these constructions into the building of BDDs. We prove, among other results, that the number of nodes created during the process for XOR groups is reduced from quadratic to linear for the affected clauses. the XOR primitive is tested against eight logical models, two from industry and six from Kconfig-based open-source projects. Results range from no negative effects in models without XOR relations to performance gains well into two orders of magnitude on models with an abundance of this kind of relationship.

Keywords: binary decision diagrams; software product lines; circuit testing; configurable systems (search for similar items in EconPapers)
JEL-codes: C (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
https://www.mdpi.com/2227-7390/8/8/1253/pdf (application/pdf)
https://www.mdpi.com/2227-7390/8/8/1253/ (text/html)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:gam:jmathe:v:8:y:2020:i:8:p:1253-:d:392714

Access Statistics for this article

Mathematics is currently edited by Ms. Emma He

More articles in Mathematics from MDPI
Bibliographic data for series maintained by MDPI Indexing Manager ().