{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,4]],"date-time":"2025-03-04T18:10:24Z","timestamp":1741111824083,"version":"3.38.0"},"reference-count":29,"publisher":"Walter de Gruyter GmbH","issue":"1","license":[{"start":{"date-parts":[[2011,1,1]],"date-time":"2011-01-01T00:00:00Z","timestamp":1293840000000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2011,1,1]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>Software evolution is critical to extending the utility and life of distributed real-time and embedded (DRE) systems. Determining the optimal set of software and hardware components to evolve that (1) incorporate cutting-edge technology and (2) satisfy DRE system resource constraints, such as memory, power, and CPU usage is an NP-Hard problem. This article provides four contributions to evolving legacy DRE system configurations. First, we present the Software Evolution Analysis with Resources (SEAR) technique for converting legacy DRE system configurations, external resource availabilities, and candidate replacement components into multiple-choice multidimension knapsack problems (MMKP). Second, we present a formal methodology for assessing the validity of evolved system configurations. Third, we apply heuristic approximation algorithms to determine low-cost, high value evolution paths in polynomial time. Finally, we analyze results of experiments that apply these techniques to determine which technique is most effective for given system parameters. Our results show that constraint solvers can only evolve small system configurations, whereas approximation techniques are needed to evolve larger system configurations.<\/jats:p>","DOI":"10.2478\/s13537-011-0006-0","type":"journal-article","created":{"date-parts":[[2011,3,24]],"date-time":"2011-03-24T15:25:25Z","timestamp":1300980325000},"source":"Crossref","is-referenced-by-count":0,"title":["Automated software and hardware evolution analysis for distributed real-time and embedded systems"],"prefix":"10.2478","volume":"1","author":[{"given":"Brian","family":"Dougherty","sequence":"first","affiliation":[]},{"given":"Jules","family":"White","sequence":"additional","affiliation":[]},{"given":"Douglas","family":"Schmidt","sequence":"additional","affiliation":[]}],"member":"374","reference":[{"key":"6_CR1","volume-title":"Classical and Object-Oriented Software Engineering","author":"S.R. Schach","year":"1995","unstructured":"Schach S.R., Classical and Object-Oriented Software Engineering, McGraw-Hill Professional, New York USA, 1995"},{"key":"6_CR2","doi-asserted-by":"crossref","first-page":"493","DOI":"10.1109\/32.799945","volume":"25","author":"C.F. Kemerer","year":"2002","unstructured":"Kemerer C.F., Slaughter S., An empirical approach to studying software evolution, IEEE T SOFTWARE ENG, 2002, 25, 493\u2013509","journal-title":"IEEE T SOFTWARE ENG"},{"key":"6_CR3","doi-asserted-by":"crossref","unstructured":"Ng C.S.P., Chan G.T., An ERP maintenance model, In: Sprague R.H (Ed.), Proceedings of the 36th Annual Hawaii International Conference on System Sciences (2003, Hilton Waikoloa Village, USA), IEEE Computer Society, 2003, 234\u2013242","DOI":"10.1109\/HICSS.2003.1174609"},{"key":"6_CR4","doi-asserted-by":"crossref","first-page":"88","DOI":"10.1109\/2.976923","volume":"35","author":"G. Leen","year":"2002","unstructured":"Leen G., Heffernan D., Expanding Automotive Electronic Systems, COMPUTER, 2002, 35, 88\u201393","journal-title":"COMPUTER"},{"key":"6_CR5","doi-asserted-by":"crossref","unstructured":"Dougherty B., White J., Thompson C., Schmidt D., Automating Hardware and Software Evolution Analysis, In: Bapty T. (Ed.), International Conference and Workshop on the Engineering of Computer Based Systems (ECBS) (November 2009, San Francisco, USA), IEEE Computer Society, 2009, 265\u2013274","DOI":"10.1109\/ECBS.2009.22"},{"key":"6_CR6","doi-asserted-by":"crossref","first-page":"57","DOI":"10.1007\/BF02249046","volume":"1","author":"B. Boehm","year":"1995","unstructured":"Boehm B., Clark B., Horowitz E., Westland C., Madachy R., Selby R., Cost models for future software life cycle processes: COCOMO 2.0, ANN SOFTW ENG, 1995, 1, 57\u201394","journal-title":"ANN SOFTW ENG"},{"key":"6_CR7","unstructured":"Gu X., Yu P.S., Nahrstedt K., Optimal Component Composition for Scalable Stream Processing, In: Arora A. (Ed.), 25th IEEE International Conference on Distributed Computing Systems. ICDCS 2005. Proceedings. (2005, Columbus, USA), IEEE Computer Society, 2005, 773\u2013782"},{"key":"6_CR8","first-page":"582","volume":"80","author":"M. Moser","year":"1997","unstructured":"Moser M., Jokanovic D.P., Shiratori N., An algorithm for the multidimensional multiple-choice knapsack problem, IEICE T FUND ELECTR, 1997, 80, 582\u2013589","journal-title":"IEICE T FUND ELECTR"},{"key":"6_CR9","volume-title":"Knapsack problems: algorithms and computer implementations","author":"S. Martello","year":"1990","unstructured":"Martello S., Toth P., Knapsack problems: algorithms and computer implementations, Wiley, New York, 1990"},{"key":"6_CR10","doi-asserted-by":"crossref","unstructured":"Ulfat-Bunyadi N., Kamsties E., Pohl K., Considering Variability in a System Family\u2019s Architecture During COTS Evaluation, In: Franch X., Port D., Proceedings ofthe 4th International Conference on COTS-Based Software Systems (ICCBSS) (2005, Bilbao, Spain), Springer, 2005, 223\u2013235","DOI":"10.1007\/978-3-540-30587-3_32"},{"key":"6_CR11","doi-asserted-by":"crossref","unstructured":"Srinivasan S., Jha N.K., Hardware-software co-synthesis of fault-tolerant real-time distributed embedded systems, In: Bryan T.P (Ed.), Design Automation Conference, 1995, with EURO-VHDL, Proceedings EURO-DAC\u201995 (2002, San Francscio, USA), IEEE Computer Society, 2002, 334\u2013339","DOI":"10.1109\/EURDAC.1995.527426"},{"key":"6_CR12","unstructured":"White J., Dougherty B., Schmidt D.C., ASCENT: An Algorithmic Technique for Designing Hardware and Software in Tandem, ISIS-Vanderbilt University, ISIS-08-907, August 2008"},{"key":"6_CR13","first-page":"280","volume":"36","author":"E.Y.H. Lin","year":"1998","unstructured":"Lin E.Y.H., A Biblographical Survey on Some Wellknown Non-Standard Knapsack Problems, INFORMATION SCIENCE AND OPERATIONAL RESEARCH, 1998, 36, 280\u2013283","journal-title":"INFORMATION SCIENCE AND OPERATIONAL RESEARCH"},{"key":"6_CR14","doi-asserted-by":"crossref","first-page":"1323","DOI":"10.1057\/palgrave.jors.2601796","volume":"12","author":"M. Hifi","year":"2004","unstructured":"Hifi M., Michrafy M., Sbihi A., Heuristic algorithms for the multiple-choice multidimensional knapsack problem, J OPER RES SOC, 2004, 12, 1323\u20131332","journal-title":"J OPER RES SOC"},{"key":"6_CR15","doi-asserted-by":"crossref","first-page":"358","DOI":"10.1007\/978-3-540-73460-4_31","volume":"4589","author":"J.S. Her","year":"2007","unstructured":"Her J.S., Choi S.W., Cheun DW, Bae JS, Kim SD, A Component-Based Process for Developing Automotive ECU Software, LECT NOTES COMPUT SC, 2007, 4589, 358\u2013373","journal-title":"LECT NOTES COMPUT SC"},{"key":"6_CR16","doi-asserted-by":"crossref","first-page":"257","DOI":"10.1007\/s11227-007-0144-2","volume":"43","author":"A.Z.M. Shahriar","year":"2008","unstructured":"Shahriar A.Z.M., Akbar M.M., Rahman M.S., Newton M.A.H., A multiprocessor based heuristic for multi-dimensional multiple-choice knapsack problem, J SUPERCOMPUT, 2008, 43, 257\u2013280","journal-title":"J SUPERCOMPUT"},{"key":"6_CR17","doi-asserted-by":"crossref","first-page":"271","DOI":"10.1007\/s10589-005-3057-0","volume":"33","author":"M. Hifi","year":"2006","unstructured":"Hifi M., Michrafy M., Sbihi A., A Reactive Local Search-Based Algorithm for the Multiple-Choice Multi-Dimensional Knapsack Problem, COMPUT OPTIM APPL, 2006, 33, 271\u2013285","journal-title":"COMPUT OPTIM APPL"},{"key":"6_CR18","doi-asserted-by":"crossref","first-page":"659","DOI":"10.1007\/3-540-45718-6_71","volume":"2074","author":"M.M. Akbar","year":"2001","unstructured":"Akbar M.M., Manning E.G., Shoja G.C., Khan S., Heuristic Solutions for the Multiple-Choice Multi-dimension Knapsack Problem, LECT NOTES COMPUT SC, 2001, 2074, 659\u2013668","journal-title":"LECT NOTES COMPUT SC"},{"key":"6_CR19","doi-asserted-by":"crossref","first-page":"495","DOI":"10.1504\/IJOR.2007.014176","volume":"2","author":"C.S. Hiremath","year":"2007","unstructured":"Hiremath C.S., Hill R.R., New greedy heuristics for the Multiple-choice Multi-dimensional Knapsack Problem, INTERNATIONAL JOURNAL OF OPERATIONAL RESEARCH, 2007, 2, 495\u2013512","journal-title":"INTERNATIONAL JOURNAL OF OPERATIONAL RESEARCH"},{"key":"6_CR20","doi-asserted-by":"crossref","first-page":"143","DOI":"10.1023\/A:1018980625587","volume":"5","author":"K.C. Kang","year":"1998","unstructured":"Kang K.C., Kim S., Lee J., Kim K., Shin E., Huh M., FORM: A Feature-Oriented Reuse Method with Domain-specific Reference Architectures, ANN SOFTW ENG, 1998, 5, 143\u2013168","journal-title":"ANN SOFTW ENG"},{"key":"6_CR21","unstructured":"Benavides D., Trinidad P., Ruiz-Cortes A., Automated Reasoning on Feature Models, In: Pastor O., Falcao e Cunha J. (Eds.), 17th Conference on Advanced Information Systems Engineering, Springer, 2005, 491\u2013503"},{"key":"6_CR22","doi-asserted-by":"crossref","unstructured":"White J., Czarnecki K., Schmidt D.C., Lenz G., Wienands C., Wuchner E., Fiege L., Automated Model-based Configuration of Enterprise Java Applications, In: Blake M.B., Spies M. (Eds.), EDOC (October 2007, Annapolis, Maryland, USA), IEEE Computer Society, 2007, 301\u2013312","DOI":"10.1109\/EDOC.2007.4384002"},{"key":"6_CR23","doi-asserted-by":"crossref","unstructured":"Mannion M., Using First-order Logic for Product Line Model Validation, In: Chastek G.J. (Ed.), Proceedings of the Second International Conference on Software Product Lines (2002, San Diego, USA), Springer, 2002, 176\u2013187","DOI":"10.1007\/3-540-45652-X_11"},{"key":"6_CR24","unstructured":"Batory D., Feature Models, Grammars, and Prepositional Formulas, In: Obbink H., Pohl K. (Eds.), Software Product Lines: 9th International Conference (26\u201329 September 2005, Rennes, France), Springer, 2005, 7\u201320"},{"key":"6_CR25","doi-asserted-by":"crossref","first-page":"28","DOI":"10.1109\/54.844331","volume":"17","author":"F. Slomka","year":"2000","unstructured":"Slomka F., Dorfel M., Munzenberger R., Hofmann R., Hardware\/software codesign and rapid prototyping of embedded-systems, IEEE DES TEST COMPUT, 2000, 17, 28\u201338","journal-title":"IEEE DES TEST COMPUT"},{"key":"6_CR26","doi-asserted-by":"crossref","DOI":"10.1093\/oso\/9780195099713.001.0001","volume-title":"Evolutionary Algorithms in Theory and Practice: Evolution Strategies, Evolutionary Programming, Genetic Algorithms","author":"T. B\u00e4ck","year":"1996","unstructured":"B\u00e4ck T., Evolutionary Algorithms in Theory and Practice: Evolution Strategies, Evolutionary Programming, Genetic Algorithms, Oxford University Press, USA, 1996"},{"key":"6_CR27","doi-asserted-by":"crossref","first-page":"26","DOI":"10.1109\/6.819926","volume":"37","author":"D.B. Fogel","year":"2000","unstructured":"Fogel D.B., Inc N.S., La Jolla C.A., What is Evolutionary Computation?, IEEE SPECTRUM, 2000, 37, 26\u201328","journal-title":"IEEE SPECTRUM"},{"key":"6_CR28","doi-asserted-by":"crossref","unstructured":"Kennedy J., Eberhart R., Particle Swarm Optimization, In: Vamplew P., Adams A. (Eds.), IEEE International Conference on Neural Networks (1995, Perth, Australia), IEEE Computer Society, 1995, 1942\u20131948","DOI":"10.1109\/ICNN.1995.488968"},{"key":"6_CR29","first-page":"1948","volume-title":"Proceedings of the 1999 Congress on Evolutionary Computation (1999, Washington D.C., USA)","author":"Y. Shi","year":"1999","unstructured":"Shi Y., Eberhart R.C., Empirical Study of Particle Swarm Optimization, In: Punch B. (Ed.), Proceedings of the 1999 Congress on Evolutionary Computation (1999, Washington D.C., USA), NJ: IEEE Service Center, 1999, 1948\u20131950"}],"container-title":["Open Computer Science"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.2478\/s13537-011-0006-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.2478\/s13537-011-0006-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.2478\/s13537-011-0006-0","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,3,4]],"date-time":"2025-03-04T17:28:15Z","timestamp":1741109295000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.degruyter.com\/document\/doi\/10.2478\/s13537-011-0006-0\/html"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,1,1]]},"references-count":29,"journal-issue":{"issue":"1"},"URL":"https:\/\/doi.org\/10.2478\/s13537-011-0006-0","relation":{},"ISSN":["2299-1093"],"issn-type":[{"type":"electronic","value":"2299-1093"}],"subject":[],"published":{"date-parts":[[2011,1,1]]}}}