[go: up one dir, main page]
More Web Proxy on the site http://driver.im/ skip to main content
10.5555/1765871.1765904guideproceedingsArticle/Chapter ViewAbstractPublication PagesConference Proceedingsacm-pubtype
Article

Automated module composition

Published: 07 April 2003 Publication History

Abstract

We define an abstract problem of module composition (MC). In MC, modules are seen as black boxes with input and output ports. The objective is, given a set of available modules, to instantiate some of them (one or more times) and connect their ports, in order to obtain a target module. A general compatibility relation defines which ports can be connected to each other. Constraints are imposed on the number of instances of each module and the number of copies of each port. A linear objective function can be given to minimize the total cost of module instances and port copies.
The MC problem is motivated by the need to automate the composition of legacy modules used in the development of software embedded in cars. Due to the large number of modules, composition "by hand" is tedious and error-prone, and its automation would lead to significant cost reduction.
We show that the MC problem is NP-complete, by formulating an equivalent integer optimization problem. We also identify a number of special cases where the MC problem can be solved in polynomial time. Finally, we suggest techniques that can be used for the general cases.

References

[1]
R.K. Ahuja, T.L. Magnanti, and J.B. Orlin. Network Flows - Theory, Algorithms and Applications. Prentice-Hall, 1993.
[2]
K. Butts, D. Bostic, A. Chutinan, J. Cook, B. Milam, and Y. Wang. Usage scenarios for a model compiler. In EMSOFT'01. Springer, LNCS 2211, 2001.
[3]
L. de Alfaro and T.A. Henzinger. Interface theories for component-based design. In EMSOFT'01. Springer, LNCS 2211, 2001.
[4]
M. Garey and D. Johnson. Computers and Intractability: a guide to the theory of NP-completeness. Freeman, 1979.
[5]
D. Jackson. Automating first-order relational logic. In Foundations of Software Engineering, 2000.
[6]
E. Kiciman, L. Melloul, and A. Fox. Towards zero-code service composition. In 8th Workshop on Hot Topics in Operating Systems (HotOS VIII), 2001.
[7]
C. Kloukinas and V. Issarny. Automating the composition of middleware configurations. In Automated Software Engineering, 2000.
[8]
C. Kloukinas and V. Issarny. Spin-ning Software Architectures: A Method for Exploring Complex Systems. In Working IEEE/IFIP Conference on Software Architecture (WICSA2001), 2001.
[9]
E.A. Lee and Y. Xiong. System-level types for component-based design. Technical report, Technical Memorandum UCB/ERL M00/8, University of California, Berkeley, 2000.
[10]
Z. Manna and P. Wolper. Synthesis of communicating processes from temporal logic specifications. ACM TOPLAS, 6(1), January 1984.
[11]
T. Margaria and B. Steffen. Backtracking-free design planning by automatic synthesis in metaframe. In Fundamental Aspects of Software Engineering, 1998.
[12]
W. Milam and A. Chutinan. Model composition and analysis challenge problems. Technical report of Mobies project. Available at: http://vehicle.me.berkeley.edu/mobies, 2001.
[13]
G.L. Nemhauser and L.A. Wolsey. Integer and Combinatorial Optimization. Wiley, 1988.
[14]
S. R. Ponnekanti and A. Fox. Sword: A developer toolkit for web service composition. In 11th World Wide Web Conference (Web Engineering Track), 2002.
[15]
M. Shaw and D. Garlan. Software Architecture: Perspectives on an Emerging Discipline. Prentice Hall, 1996.
[16]
B. Steffen, T. Margaria, and M. von der Beeck. Automatic synthesis of linear process models from temporal constraints: An incremental approach. In ACM/SIGPLAN Int. Workshop on Automated Analysis of Software (AAS'97), 1997.
[17]
S. Tripakis. Automated composition of module chains. In ETAPS'02 Workshop on Software Composition. Volume 65, issue 4 of ENTCS, Elsevier, 2002.
[18]
R. van Ommering, F. van der Linden, J. Kramer, and J. Magee. The Koala component model for consumer electronics software. IEEE Computer, March 2000.

Cited By

View all
  • (2016)Leveraging Software Product Lines Engineering in the development of external DSLsComputer Languages, Systems and Structures10.1016/j.cl.2016.09.00446:C(206-235)Online publication date: 1-Nov-2016

Recommendations

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings
TACAS'03: Proceedings of the 9th international conference on Tools and algorithms for the construction and analysis of systems
April 2003
603 pages
ISBN:3540008985
  • Editors:
  • Hubert Garavel,
  • John Hatcliff

Publisher

Springer-Verlag

Berlin, Heidelberg

Publication History

Published: 07 April 2003

Qualifiers

  • Article

Contributors

Other Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

  • Downloads (Last 12 months)0
  • Downloads (Last 6 weeks)0
Reflects downloads up to 12 Dec 2024

Other Metrics

Citations

Cited By

View all
  • (2016)Leveraging Software Product Lines Engineering in the development of external DSLsComputer Languages, Systems and Structures10.1016/j.cl.2016.09.00446:C(206-235)Online publication date: 1-Nov-2016

View Options

View options

Login options

Media

Figures

Other

Tables

Share

Share

Share this Publication link

Share on social media