Top

Automated Software Engineering

Published in:

13-07-2018

Optimizing the deployment of tree-shaped functional graphs of real-time system on distributed architectures

Authors: Asma Mehiaoui, Ernest Wozniak, Jean-Philippe Babau, Sara Tucci-Piergiovanni, Chokri Mraidha

Published in: Automated Software Engineering | Issue 1/2019

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

Recent development methodologies from the industry and the academia for complex real-time systems define a stage in which system functions are deployed onto an execution platform. The deployment consists of the placement of functions on a distributed network of nodes, the partitioning of functions in tasks and the scheduling of tasks and messages. In this paper, we present two approaches towards the efficient deployment of realistic and complex real-time systems by considering tree-shaped functional models. A formal approach to compute optimal deployment and a heuristic approach to scale to industry-size systems. The approaches consider placement, partitioning and scheduling, and are based on mixed integer linear programming (MILP) technique. Furthermore, we present a deep evaluation of the proposed deployment approaches to show the benefits and limits of a MILP-based deployment approach. A set of synthetic use-cases as well as a real-life automotive system are used to assess the quality and scalability of our deployment approaches. Considering use-cases, we show an added value with respect to end-to-end latencies optimization when solving the three stages of the deployment problem at the same time. This is done by comparing the quality of the solutions obtained with our techniques to those returned by the existing approaches.

next article Exploring output-based coverage for testing PHP web applications

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Available only for authorised users

Concurrent execution services provided by a real-time operating system (RTOS). A task in our model can be implemented as process/thread.

An algorithm for finding pareto-optimal solutions to multi-objective problems. The initial solution is chosen by solving the set of problem constraints. At each step of the improvement the same problem is addressed. This is not the case of our two-step approach.

Local Device Manager.

The consideration of time metric and constraints is not possible as tasks/messages and priorities are not present at this level.

A synchronized non-linear transaction is a non-linear transaction with exactly one sink function. It is also so-called polar graph (Pop et al. 2004).

A non-synchronized non-linear transaction is a non-linear transaction with more than one sink function.

Al Sheikh, A., Brun, O., Hladik, P.E., et al.: Partition scheduling on an IMA platform with strict periodicity and communication delays. In: Proceedings of the 18th International Conference on Real-Time and Network Systems, pp. 179–188 (2010)

Aleti, A., Buhnova, B., Grunske, L., Koziolek, A., Meedeniya, I.: Software architecture optimization methods: a systematic literature review. IEEE Trans. Softw. Eng. 39(5), 658–683 (2013)CrossRef

Autosar 4.0 specifications. http://www.autosar.org/. Accessed 2011

Azketa, E., Uribe, J., Gutiérrez, J., Marcos, M., Almeida, L.: Permutational genetic algorithm for the optimized assignment of priorities to tasks and messages in distributed real-time systems. In: Proceedings of the 10th IEEE International Conference on Trust, Security and Privacy in Computing and Communications, pp. 958–965 (2011)

Azketa, E., Uribe, J.P., Gutiérrez, J.J., Marcos, M., Almeida, L.: Permutational genetic algorithm for the optimized mapping and scheduling of tasks and messages in distributed real-time systems. In: Proceedings of the 2011IEEE 10th International Conference on Trust, Security and Privacy in Computing and Communications, TRUSTCOM (2011)

Azketa, E., Uribe, J., Marcos, M., Almeida, L., Gutiérrez, J.J.: Permutational genetic algorithm for fixed priority scheduling of distributed real-time systems aided by network segmentation. In: Proceedings of the 1st Workshop on Synthesis and Optimization Methods for Real-time Embedded Systems (SOMRES) (2011)

Bartolini, C., Lipari, G., Di Natale, M.: From functional blocks to the synthesis of the architectural model in embedded real-time applications. In: Proceedings of the 11th IEEE Real Time and Embedded Technology and Applications Symposium, pp. 458–467 (2005)

Bate, I., Emberson, P.: Incorporating scenarios and heuristics to improve flexibility in real-time embedded systems. In: Proceedings of the 12th IEEE Real-Time and Embedded Technology and Applications Symposium, pp. 221–230 (2006)

Bini, E., Natale, M.D., Buttazzo, G.: Sensitivity analysis for fixed-priority real-time systems. In: Euromicro Conference on Real-Time Systems. Dresden, Germany (2006)

Bøgholm, T., Kragh-Hansen, H., Olsen, P.: Model-based schedulability analysis of real-time systems. Master’s thesis, Aalborg University, pp. 1–137 (2008)

Bosch, R.: CAN specification, version 2.0. Stuttgart (1991)

Boyd, S.P., Vandenberghe, L.: Convex Optimization. Cambridge University Press, Cambridge (2004)CrossRefMATH

Burns, A., Wellings, A.J.: Real-Time Systems and Programming Languages, vol. 2097. Addison-Wesley, Boston (2010)MATH

Cplex. http://www-01.ibm.com/software/integration/optimization/cplex-optimizer/. Accessed 2012

Daghsen, A.: Methodology of analysis and optimization of real-time embedded systems: application to automotive field. Ph.D. thesis (2013)

Davis, R., Burns, A., Bril, R., Lukkien, J.: Controller area network (can) schedulability analysis: refuted, revisited and revised. Real-Time Syst. 35(3), 239–272 (2007)CrossRef

Feljan, J., Carlson, J., Seceleanu, T.: Towards a model-based approach for allocating tasks to multicore processors. In: Software Engineering and Advanced Applications (SEAA), 2012 38th EUROMICRO Conference IEEE, pp. 117–124 (2012)

García, J.G., Gutiérrez, J.C.P., Harbour, M.G.: Schedulability analysis of distributed hard real-time systems with multiple-event synchronization. In: Real-Time Systems, 2000. Euromicro RTS 2000. 12th Euromicro Conference on IEEE, pp. 15–24 (2000)

http://www.maenad.eu/. Accessed 2014

http://www.omg.org/. Accessed 2001

Hamann, A., Racu, R., Ernst, R.: Multi-dimensional robustness optimization in heterogeneous distributed embedded systems. In: Proceedings of the 13th IEEE Real Time and Embedded Technology and Applications Symposium (2007)

Hamann, A., Jersak, M., Richter, K., Ernst, R.: A framework for modular analysis and exploration of heterogeneous embedded systems. Real-Time Syst. 33(1–3), 101–137 (2006)CrossRefMATH

He, X., Gu, Z., Zhu, Y.: Task allocation and optimization of distributed embedded systems with simulated annealing and geometric programming. Comput. J. 53(7), 1071–1091 (2010)CrossRef

Jackson, D., Estler, H., Rayside, D., et al.: The guided improvement algorithm for exact, general-purpose, many-objective combinatorial optimization. Computer science and artificial intelligence laboratory technical report MIT-CSAIL-TR-2009-033, MIT CSAIL (2009)

Kienhuis, B., Deprettere, E., Van Der Wolf, P., Vissers, K.: A methodology to design programmable embedded systems. In: Embedded Processor Design Challenges, pp. 321–324. Springer (2002)

Klein, M.H., Ralya, T., Pollak, B., Obenza, R.: A Practitioner’s Handbook for Real-Time Analysis: Guide to Rate Monotonic Analysis for Real-Time Systems. Kluwer Academic Publishers, Berlin (1993)CrossRef

Kodase, S., Wang, S., Shin, K.: Transforming structural model to runtime model of embedded software with real-time constraints. In: Proceedings of the Conference on Design, Automation and Test in Europe, pp. 170–175 (2003)

Kugele, S., Haberl, W., Tautschnig, M., Wechs, M.: Optimizing automatic deployment using non-functional requirement annotations. In: Leveraging Applications of Formal Methods, Verification and Validation, pp. 400–414. Springer (2009)

Kugele, S., Pucea, G., Popa, R., Dieudonné, L., Eckardt, H.: On the deployment problem of embedded systems. In: Formal Methods and Models for Codesign (MEMOCODE), 2015 ACM/IEEE International Conference on IEEE, pp. 158–167 (2015)

Kugele, S., Pucea, G.: Model-based optimization of automotive e/e-architectures. In: Proceedings of the 6th International Workshop on Constraints in Software Testing, Verification, and Analysis, pp. 18–29. ACM (2014)

Liu, C.L., Layland, J.W.: Scheduling algorithms for multiprogramming in a hard-real-time environment. J. ACM 20(1), 46–61 (1973)MathSciNetCrossRefMATH

Long, R., Li, H., Peng, W., Zhang, Y., Zhao, M.: An approach to optimize intra-ECU communication based on mapping of autosar runnable entities. In: Embedded Software and Systems, 2009. ICESS’09. International Conference on IEEE, pp. 138–143 (2009)

Mehiaoui, A., Tucci-Piergiovanni, S., Babau, J., Lemarchand, L.: Optimizing the deployment of distributed real-time embedded applications. In: Embedded and Real-Time Computing Systems and Applications (RTCSA), 2012 IEEE 18th International Conference on IEEE, pp. 400–403 (2012)

Mehiaoui, A., Tucci-Piergiovanni, S., Mraidha, C., Babau, J.P.: Extending response-time analysis for the automatic synthesis of functional graphs into fixed-priority distributed systems. In: Industrial Embedded Systems (SIES), 2014 9th IEEE International Symposium on IEEE, pp. 122–132 (2014)

Mehiaoui, A., Wozniak, E., Tucci-Piergiovanni, S., Mraidha, C., Di Natale, M., Zeng, H., Babau, J.P., Lemarchand, L., Gerard, S.: A two-step optimization technique for functions placement, partitioning, and priority assignment in distributed systems. In: Proceedings of the 14th ACM SIGPLAN/SIGBED Conference on Languages, Compilers and Tools for Embedded Systems, pp. 121–132. ACM (2013)

OSEK/VDX. http://www.osek-vdx.org/. Accessed 1994

Palencia, J.C., Harbour, M.G.: Exploiting precedence relations in the schedulability analysis of distributed real-time systems. In: Proceedings of the 20th IEEE Real-Time Systems Symposium (1999)

Peng, W., Li, H., Yao, M., Sun, Z.: Deployment optimization for autosar system configuration. In: Computer Engineering and Technology (ICCET), 2010 2nd International Conference on IEEE, vol. 4, pp. V4–189 (2010)

Peraldi-Frati, M.A., Karlsson, D., Hamann, A., Kuntz, S., Nordlander, J., et al.: The timmo-2-use project: Time modeling and analysis to use. In: ERTS2012 International Congres on Embedded Real Time Software and Systems (2012)

Pohl, K., Broy, M., Daembkes, H., Hönninger, H.: Advanced model-based engineering of embedded systems. In: Advanced Model-Based Engineering of Embedded Systems, pp. 3–9. Springer (2016)

Pop, P., Eles, P., Peng, Z., Pop, T.: Analysis and optimization of distributed real-time embedded systems. In: ACM Transactions on Design Automation of Electronic Systems (TODAES), vol. 11, pp. 593–625. ACM (2004)

Pop, T., Eles, P., Peng, Z.: Design optimization of mixed time/event-triggered distributed embedded systems. In: Proceedings of the First IEEE/ACM/IFIP International Conference on Hardware/Software Codesign and System Synthesis (2003)

Racu, R., Jersak, M., Ernst, R.: Applying sensitivity analysis in real-time distributed systems. In: Proceedings of the 11th IEEE Real Time on Embedded Technology and Applications Symposium, pp. 160–169 (2005)

Richard, M., Richard, P., Cottet, F.: Allocating and scheduling tasks in multiple fieldbus real-time systems. In: Proceedings of the IEEE Conference on Emerging Technologies and Factory Automation. IEEE (2003)

Saksena, M., Karvelas, P., Wang, Y.: Automatic synthesis of multi-tasking implementations from real-time object-oriented models. In: Proceedings of 3rd IEEE International Symposium on Object-Oriented Real-Time Distributed Computing, pp. 360–367 (2000)

Sangiovanni-Vincentelli, A., Martin, G.: Platform-based design and software design methodology for embedded systems. IEEE Des. Test Comput. 18(6), 23–33 (2001)CrossRef

Sorel, Y.: Syndex: system-level cad software for optimizing distributed real-time embedded systems. J. ERCIM News 59(68–69), 31 (2004)

Tindell, K., Clark, J.: Holistic schedulability analysis for distributed hard real-time systems. Microprocess. Microprogram 40(2), 117–134 (1994)CrossRef

Wang, S., Merrick, J.R., Shin, K.G.: Component allocation with multiple resource constraints for large embedded real-time software design. In: Real-Time and Embedded Technology and Applications Symposium, 2004. Proceedings of RTAS 2004, 10th IEEE, pp. 219–226 (2004)

Wang, S., Shin, K.: Task construction for model-based design of embedded control software. Softw. Eng. IEEE Trans. 32(4), 254–264 (2006)CrossRef

Wozniak, E., Mehiaoui, A., Mraidha, C., Tucci-Piergiovanni, S., Gerard, S.: An optimization approach for the synthesis of autosar architectures. In: Emerging Technologies & Factory Automation (ETFA), 2013 IEEE 18th Conference on IEEE, pp. 1–10 (2013)

Wozniak, E., Mehiaoui, A., Mraidha, C., Tucci-Piergiovanni, S., Gerard, S.: An optimization approach for the synthesis of autosar architectures. In: Emerging Technologies Factory Automation (ETFA), 2013 IEEE 18th Conference, pp. 1–10 (2013). https://doi.org/10.1109/ETFA.2013.6647952

Zeller, M., Prehofer, C., Weiss, G., Eilers, D., Knorr, R.: Towards self-adaptation in real-time, networked systems: efficient solving of system constraints for automotive embedded systems. In: Self-adaptive and Self-Organizing Systems (SASO), 2011 Fifth IEEE International Conference on IEEE, pp. 79–88 (2011)

Zhang, M., Gu, Z.: Optimization issues in mapping autosar components to distributed multithreaded implementations. In: Rapid System Prototyping (RSP), 2011 22nd IEEE International Symposium on IEEE, pp. 23–29 (2011)

Zheng, W., Di Natale, M., Pinello, C., Giusto, P., Vincentelli, A.S.: Synthesis of task and message activation models in real-time distributed automotive systems. In: Proceedings of the Conference on Design, Automation and Test in Europe, EDA Consortium, pp. 93–98 (2007)

Zheng, W., Zhu, Q., Di Natale, M., Vincentelli, A.S.: Definition of task allocation and priority assignment in hard real-time distributed systems. In: Real-Time Systems Symposium, 2007, RTSS 2007, 28th IEEE International IEEE, pp. 161–170 (2007)

Zhu, Q., Yang, Y., Scholte, E., Di Natale, M., Sangiovanni-Vincentelli, A.: Optimizing extensibility in hard real-time distributed systems. In: Real-Time and Embedded Technology and Applications Symposium, 2009, RTAS 2009, 15th IEEE, pp. 275–284 (2009)

Zhu, Q., Yang, Y., Natale, M., Scholte, E., Sangiovanni-Vincentelli, A.: Optimizing the software architecture for extensibility in hard real-time distributed systems. IEEE Trans. Ind. Inf. 6(4), 621–636 (2010)CrossRef

Zhu, Q., Zeng, H., Zheng, W., Di Natale, M., Sangiovanni-Vincentelli, A.: Optimization of task allocation and priority assignment in hard real-time distributed systems. ACM Trans. Embed. Comput. Syst. 11(4), 85:1–85:3 (2012)CrossRef

Title: Optimizing the deployment of tree-shaped functional graphs of real-time system on distributed architectures
Authors: Asma Mehiaoui
Ernest Wozniak
Jean-Philippe Babau
Sara Tucci-Piergiovanni
Chokri Mraidha
Publication date: 13-07-2018
Publisher: Springer US
Published in: Automated Software Engineering / Issue 1/2019
Print ISSN: 0928-8910
Electronic ISSN: 1573-7535
DOI: https://doi.org/10.1007/s10515-018-0244-7

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Other articles of this Issue 1/2019

Collaborative feature location in models through automatic query expansion

Cost-aware scheduling for ensuring software performance and reliability under heterogeneous workloads of hybrid cloud

Exploring output-based coverage for testing PHP web applications

Efficient elicitation of software configurations using crowd preferences and domain knowledge

Fragment-based spreadsheet debugging

Premium Partner