Marcilio Mendonca
Andrzej Wasowski
ABSTRACT
Feature modeling is used in generative programming and software product-line engineering to capture the common and variable properties of programs within an application domain. The translation of feature models to propositional logics enabled the use of reasoning systems, such as BDD engines, for the analysis and transformation of such models and interactive configurations. Unfortunately, the size of a BDD structure is highly sensitive to the variable ordering used in its construction and an inappropriately chosen ordering may prevent the translation of a feature model into a BDD representation of a tractable size. Finding an optimal order is NP-hard and has for long been addressed by using heuristics.
We review existing general heuristics and heuristics from the hardware circuits domain and experimentally show that they are not effective in reducing the size of BDDs produced from feature models. Based on that analysis we introduce two new heuristics for compiling feature models to BDDs. We demonstrate the effectiveness of these heuristics using publicly available and automatically generated models. Our results are directly applicable in construction of feature modeling tools.
- F. A. Aloul, I. L. Markov, and K. A. Sakallah. FORCE: a fast and easy-to-implement variable-ordering heuristic. In Proc. of the 13th ACM Great Lakes symposium on VLSI, 2003. Google Scholar
Digital Library
- V. Alves, R. Gheyi, T. Massoni, U. Kulesza, P. Borba, and C. Lucena. Refactoring product lines. In GPCE, 2006. Google ScholarDigital Library
- H. R. Andersen. Binary Decision Diagrams. Technical University of Denmark, 1997. Lecture notes for 49285, Advanced Algorithms, E97.Google Scholar
- D. Batory, D. Benavides, and A. Ruiz-Cortes. Automated analysis of feature models: challenges ahead. Communications of the ACM, 2006. Google ScholarDigital Library
- D. S. Batory. Feature models, grammars, and propositional formulas. In SPLC, 2005. Google ScholarDigital Library
- D. Beuche and M. Dalgarno. Software product line engineering with feature models. In Software Acumen, 2006. http://www.methodsandtools.com/PDF/mt200604.pdf.Google Scholar
- B. Bollig and I. Wegener. Improving the variable ordering of OBDDs is NP-Complete. IEEE Transac. on Computers, 1996. Google ScholarDigital Library
- F. Brglez and H. Fujiwara. A neutral netlist of 10 combinatorial benchmark circuits and a target translator in FORTRAN. In Int. Symposium on Circuits and Systems, 1985.Google Scholar
- R. E. Bryant. Graph-based algorithms for boolean function manipulation. IEEE Transactions on Computers, 1986. Google ScholarDigital Library
- K. Czarnecki and U. W. Eisenecker. Generative Programming: Methods, Tools, and Applications. Addison-Wesley, Boston, MA, 2000. Google ScholarDigital Library
- K. Czarnecki and S. Helsen. Classification of model transformation approaches. In Proc. of the 2nd OOPSLA Workshop on Generative Techniques in the Context of MDA, 2003.Google Scholar
- K. Czarnecki and K. Pietroszek. Verifying feature-based model templates against well-formedness OCL constriants. In GPCE, 2006. Google ScholarDigital Library
- K. Czarnecki and A. WaÛsowski. Feature models and logics: There and back again. In SPLC 2007. IEEE Press. Google ScholarDigital Library
- K. Czarnecki et al. Generative programming for embedded software: An industrial experience report. In GPCE, 2002. Google ScholarDigital Library
- M. Fujita, H. Fujisawa, and N. Kawato. Evaluation and improvement of boolean comparison method based on binary decision diagrams. In ICCAD, 1988.Google ScholarCross Ref
- T. Hadzic, R. Jensen, and H. R. Andersen. Notes on calculating valid domains. Manuscript online http://www.itu.dk/~tarik/cvd/cvd.pdf, 2006.Google Scholar
- T. Hadzic et al. Fast backtrack-free product configuration using a precompiled solution space representation. In PETO Conference, 2004.Google Scholar
- T. Hadzic et al. Calculating valid domains for BDD-based interactive configuration. CoRR, abs/0704.1394, 2007.Google Scholar
- K. Kang, S. Cohen, J. Hess, W. Nowak, and S. Peterson. Feature-oriented domain analysis (FODA) feasibility study. Technical Report CMU/SEI-90-TR-21, 1990.Google ScholarCross Ref
- S. Q. Lau. Domain analysis of e-commerce systems using feature-based model templates. Master's thesis, Dept. of ECE, University of Waterloo, Canada, 2006.Google Scholar
- S. Malik, A. Wang, R. Brayton, and A. Sangiovanni-Vincentelli. Logic verification using BDDs in a logic synthesis environment. In ICCAD, 1988.Google Scholar
- C. Meinel and T. Theobald. Algorithms and Data Structures in VLSI Design. Springer-Verlag, 1998. Google ScholarDigital Library
- M. Mendonca. Efficient compilation techniques for large scale feature models, 2008. http://csg.uwaterloo.ca/~marcilio/fmcompilation/index.html. Google ScholarDigital Library
- M. Mendonca, T. T. Bartolomei, and D. Cowan. Decision making coordination in collaborative product configuration. In ACM 23rd Symposium on Applied Computing (SAC'08), 2008. Google ScholarDigital Library
- J. Moller, H. R. Andersen, and H. Hulgaard. Product configuration over the internet. http://citeseer.ist.psu.edu/531891.html.Google Scholar
- R. Rudell. Dynamic variable ordering for ordered binary decision diagrams. In ICCAD, 1993. Google ScholarDigital Library
- J. Whaley. The JavaBDD library, 2003-2008. http://javabdd.sourceforge.net/.Google Scholar
Index Terms
- Efficient compilation techniques for large scale feature models
Recommendations
Verifying feature-based model templates against well-formedness OCL constraints
GPCE '06: Proceedings of the 5th international conference on Generative programming and component engineeringFeature-based model templates have been recently proposed as a approach for modeling software product lines. Unfortunately, templates are notoriously prone to errors that may go unnoticed for long time. This is because such an error is usually exhibited ...
Automated Formalisation for Verification of Diagrammatic Models
Software engineering uses models to design and analyse systems. The current state-of-the-art, various forms of model-driven development, uses diagrams with defined abstract syntax but relatively-lose translational approaches to semantics, which makes it ...
fmp and fmp2rsm: eclipse plug-ins for modeling features using model templates
OOPSLA '05: Companion to the 20th annual ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applicationsFeature-based model templates have been proposed as a technique for modeling software product lines. We describe a set of tools supporting the technique, namely a feature model editor and feature configurator, and a model-template editor, processor, and ...
Comments