Configuring BDD Compilation Techniques for Feature Models
Publikation: Beitrag in Buch/Konferenzbericht/Sammelband/Gutachten › Beitrag in Konferenzband › Beigetragen › Begutachtung
Beitragende
Abstract
The compilation of feature models into binary decision diagrams (BDDs) is a major challenge in the area of configurable systems analysis. Many large-scale feature models have been reported to exceed state-of-the-art compilation capabilities, e.g., for variants of the Linux kernel product line. However, experiments have been mainly conducted on standard settings of the BDD compilers themselves, not taking advanced configurations into account.
In this paper, we investigate the impact of various BDD compilation techniques for compiling feature models in conjunctive normal form. Specifically, we evaluate preprocessing techniques from satisfiability (SAT) solving, variable and clause ordering heuristics, non-incremental construction schemes, as well as parallelization of BDD construction. Our experiments on current feature models show that BDD compilation of feature models greatly benefits from these techniques, enabling to construct many previously not constructible large-scale feature models within seconds.
In this paper, we investigate the impact of various BDD compilation techniques for compiling feature models in conjunctive normal form. Specifically, we evaluate preprocessing techniques from satisfiability (SAT) solving, variable and clause ordering heuristics, non-incremental construction schemes, as well as parallelization of BDD construction. Our experiments on current feature models show that BDD compilation of feature models greatly benefits from these techniques, enabling to construct many previously not constructible large-scale feature models within seconds.
Details
Originalsprache | Englisch |
---|---|
Titel | SPLC 2024 - 28th ACM International Systems and Software Product Line Conference, Proceedings |
Redakteure/-innen | Maxime Cordy, Daniel Struber, Daniel Struber, Monica Pinto, Iris Groher, Deepak Dhungana, Jacob Kruger, Juliana Alves Pereira, Mathieu Acher, Thomas Thum, Thomas Thum, Maurice H. ter Beek, Jessie Galasso-Carbonnel, Paolo Arcaini, Mohammad Reza Mousavi, Xhevahire Ternava, Jose A. Galindo, Tao Yue, Lidia Fuentes, Jose Miguel Horcas |
Herausgeber (Verlag) | Association for Computing Machinery (ACM) |
Seiten | 209-216 |
Seitenumfang | 8 |
Band | A |
ISBN (elektronisch) | 9798400705939 |
Publikationsstatus | Veröffentlicht - 2 Sept. 2024 |
Peer-Review-Status | Ja |
Externe IDs
ORCID | /0000-0002-0645-1078/work/165454298 |
---|---|
Scopus | 85203792615 |
Schlagworte
ASJC Scopus Sachgebiete
Schlagwörter
- Binary Decision Diagrams, Knowledge Compilation, Feature Models, Configurable Systems