Efficient compilation techniques for large scale feature models

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.

REFERENCES

• 1: Fadi A. Aloul , Igor L. Markov , Karem A. Sakallah, FORCE: a fast and easy-to-implement variable-ordering heuristic, Proceedings of the 13th ACM Great Lakes symposium on VLSI, April 28-29, 2003, Washington, D. C., USA [doi>10.1145/764808.764839]
• 2: Vander Alves , Rohit Gheyi , Tiago Massoni , Uirá Kulesza , Paulo Borba , Carlos Lucena, Refactoring product lines, Proceedings of the 5th international conference on Generative programming and component engineering, October 22-26, 2006, Portland, Oregon, USA [doi>10.1145/1173706.1173737]
• 3: H. R. Andersen. Binary Decision Diagrams. Technical University of Denmark, 1997. Lecture notes for 49285, Advanced Algorithms, E97.
• 4: Don Batory , David Benavides , Antonio Ruiz-Cortes, Automated analysis of feature models: challenges ahead, Communications of the ACM, v.49 n.12, December 2006 [doi>10.1145/1183236.1183264]
• 5: D. S. Batory. Feature models, grammars, and propositional formulas. In SPLC, 2005.
• 6: D. Beuche and M. Dalgarno. Software product line engineering with feature models. In Software Acumen, 2006. http://www.methodsandtools.com/PDF/mt200604.pdf.
• 7: Beate Bollig , Ingo Wegener, Improving the Variable Ordering of OBDDs Is NP-Complete, IEEE Transactions on Computers, v.45 n.9, p.993-1002, September 1996 [doi>10.1109/12.537122]
• 8: 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.
• 9: Randal E. Bryant, Graph-Based Algorithms for Boolean Function Manipulation, IEEE Transactions on Computers, v.35 n.8, p.677-691, August 1986 [doi>10.1109/TC.1986.1676819]
• 10: Krzysztof Czarnecki , Ulrich W. Eisenecker, Generative programming: methods, tools, and applications, ACM Press/Addison-Wesley Publishing Co., New York, NY, 2000
• 11: 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.
• 12: Krzysztof Czarnecki , Krzysztof Pietroszek, Verifying feature-based model templates against well-formedness OCL constraints, Proceedings of the 5th international conference on Generative programming and component engineering, October 22-26, 2006, Portland, Oregon, USA [doi>10.1145/1173706.1173738]
• 13: Krzysztof Czarnecki , Andrzej Wasowski, Feature Diagrams and Logics: There and Back Again, Proceedings of the 11th International Software Product Line Conference, p.23-34, September 10-14, 2007 [doi>10.1109/SPLC.2007.19]
• 14: Krzysztof Czarnecki , Thomas Bednasch , Peter Unger , Ulrich W. Eisenecker, Generative Programming for Embedded Software: An Industrial Experience Report, Proceedings of the 1st ACM SIGPLAN/SIGSOFT conference on Generative Programming and Component Engineering, p.156-172, October 06-08, 2002
• 15: M. Fujita, H. Fujisawa, and N. Kawato. Evaluation and improvement of boolean comparison method based on binary decision diagrams. In ICCAD, 1988.
• 16: T. Hadzic, R. Jensen, and H. R. Andersen. Notes on calculating valid domains. Manuscript online http://www.itu.dk/~tarik/cvd/cvd.pdf, 2006.
• 17: T. Hadzic et al. Fast backtrack-free product configuration using a precompiled solution space representation. In PETO Conference, 2004.
• 18: T. Hadzic et al. Calculating valid domains for BDD-based interactive configuration. CoRR, abs/0704.1394, 2007.
• 19: 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.
• 20: 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.
• 21: S. Malik, A. Wang, R. Brayton, and A. Sangiovanni-Vincentelli. Logic verification using BDDs in a logic synthesis environment. In ICCAD, 1988.
• 22: Christoph Meinel , Thorsten Theobald, Algorithms and Data Structures in VLSI Design, Springer-Verlag New York, Inc., Secaucus, NJ, 1998
• 23: Marcilio Mendonca , Andrzej Wasowski , Krzysztof Czarnecki , Donald Cowan, Efficient compilation techniques for large scale feature models, Proceedings of the 7th international conference on Generative programming and component engineering, October 19-23, 2008, Nashville, TN, USA [doi>10.1145/1449913.1449918]
• 24: Marcílio Mendonça , Thiago Tonelli Bartolomei , Donald Cowan, Decision-making coordination in collaborative product configuration, Proceedings of the 2008 ACM symposium on Applied computing, March 16-20, 2008, Fortaleza, Ceara, Brazil [doi>10.1145/1363686.1363715]
• 25: J. Moller, H. R. Andersen, and H. Hulgaard. Product configuration over the internet. http://citeseer.ist.psu.edu/531891.html.
• 26: Richard Rudell, Dynamic variable ordering for ordered binary decision diagrams, Proceedings of the 1993 IEEE/ACM international conference on Computer-aided design, p.42-47, November 07-11, 1993, Santa Clara, California, United States
• 27: J. Whaley. The JavaBDD library, 2003-2008. http://javabdd.sourceforge.net/.

INDEX TERMS

Primary Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.2 Design Tools and Techniques
          Subjects: Computer-aided software engineering (CASE)

General Terms:
Design

Keywords:
configuration, feature modeling, formal verification, model-driven development, software-product lines