research-article

A two-step optimization technique for functions placement, partitioning, and priority assignment in distributed systems

Authors:

Ernest Wozniak,

Sara Tucci-Piergiovanni,

Chokri Mraidha,

Marco Di Natale,

Jean-Philippe Babau,

Laurent Lemarchand,

Sébastien GerardAuthors Info & Claims

LCTES '13: Proceedings of the 14th ACM SIGPLAN/SIGBED conference on Languages, compilers and tools for embedded systems

Pages 121 - 132

https://doi.org/10.1145/2491899.2465572

Published: 20 June 2013 Publication History

Abstract

Modern development methodologies from the industry and the academia for complex real-time systems define a stage in which application 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. None of the existing optimization techniques deal with the three stages of the deployment problem at the same time. In this paper, we present a staged approach towards the efficient deployment of real-time functions based on genetic algorithms and mixed integer linear programming techniques. Application to case studies shows the applicability of the method to industry-size systems and the quality of the obtained solutions when compared to the true optimum for small size examples.

References

[1]

http://www.omg.org/.

[2]

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

[3]

A. Aleti, B. Buhnova, L. Grunske, A. Koziolek, and I. Meedeniya. Software architecture optimization methods: A systematic literature review. IEEE Transactions on Software Engineering, To appear.

[4]

S. Anssi, S. Tucci-Piergiovanni, S. Kuntz, S. Gerard, and F. Terrier. Enabling scheduling analysis for autosar systems. Object-Oriented Real-Time Distributed Computing, IEEE International Symposium on, 0:152--159, 2011.

Digital Library

[5]

N. Audsley, A. Burns, M. Richardson, and A. Wellings. Hard realtime scheduling: The deadline monotonic approach. In Proceedings 8th IEEE Workshop on Real-Time Operating Systems and Software, pages 127--132, 1991.

[6]

E. Azketa, J. Uribe, J. Gutiírrez, M. Marcos, and L. Almeida. 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, pages 958--965, 2011.

Digital Library

[7]

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

Digital Library

[8]

I. Bate and P. Emberson. 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, pages 221--230, 2006.

Digital Library

[9]

E. Bini, M. D. Natale, and G. Buttazzo. Sensitivity analysis for fixedpriority real-time systems. In Euromicro Conference on Real-Time Systems, Dresden, Germany, June 2006.

Digital Library

[10]

R. Bosch. CAN specification, version 2.0. Stuttgart, 1991.

[11]

L. Davis, editor. Handbook of Genetic Algorithms. Van Nostrand Reinhold, 1991.

[12]

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

Digital Library

[13]

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

Digital Library

[14]

X. He, Z. Gu, and Y. Zhu. Task allocation and optimization of distributed embedded systems with simulated annealing and geometric programming. The Computer Journal, 53(7):1071--1091, 2010.

Digital Library

[15]

B. Kienhuis, E. Deprettere, P. Van Der Wolf, and K. Vissers. A methodology to design programmable embedded systems. In Embedded processor design challenges, pages 321--324. Springer, 2002.

Digital Library

[16]

S. Kodase, S. Wang, and K. Shin. 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, pages 170--175, 2003.

Digital Library

[17]

S. Kugele, W. Haberl, M. Tautschnig, and M. Wechs. Optimizing automatic deployment using non-functional requirement annotations. Leveraging Applications of Formal Methods, Verification and Validation, pages 400--414, 2009.

[18]

A. Mehiaoui. A mixed integer linear programming formulations for optimizing timing performance during the deployment phase in realtime systems design. Technical Report CEA, http://hal-cea.archivesouvertes.fr/cea-00811359, 2012.

[19]

B. L. Miller, B. L. Miller, D. E. Goldberg, and D. E. Goldberg. Genetic algorithms, tournament selection, and the effects of noise. Complex Systems, 9:193--212, 1995.

[20]

C. Mraidha, S. Tucci-Piergiovanni, and S. Gerard. Optimum: a martebased methodology for schedulability analysis at early design stages. ACM SIGSOFT Software Engineering Notes, 36(1):1--8, 2011.

Digital Library

[21]

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

Digital Library

[22]

P. Pop, P. Eles, Z. Peng, and T. Pop. Analysis and optimization of distributed real-time embedded systems. ACM Transactions on Design Automation of Electronic Systems, 11(3):593--625, 2006.

Digital Library

[23]

T. Pop, P. Eles, and Z. Peng. Design optimization of mixed time/eventtriggered distributed embedded systems. In Proc. of the First IEEE/ACM/IFIP International Conference on Hardware/Software Codesign and System Synthesis, 2003.

Digital Library

[24]

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

Digital Library

[25]

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

[26]

M. Saksena, P. Karvelas, and Y. Wang. 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, pages 360--367, 2000.

Digital Library

[27]

A. Sangiovanni-Vincentelli and G. Martin. Platform-based design and software design methodology for embedded systems. IEEE Design and Test of Computers, 18(6):23--33, 2001.

Digital Library

[28]

K. Tindell and J. Clark. Holistic schedulability analysis for distributed hard real-time systems. Microprocessing and microprogramming, 40(2-3):117--134, 1994.

Digital Library

[29]

W. Zheng, M. Di Natale, C. Pinello, P. Giusto, and A. Vincentelli. 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, pages 93--98, 2007.

Digital Library

[30]

Q. Zhu, Y. Yang, M. Di Natale, E. Scholte, and A. Sangiovanni- Vincentelli. Optimizing the software architecture for extensibility in hard real-time distributed systems. IEEE Transactions on Industrial Informatics, 6(4):621--636, 2010.

[31]

Q. Zhu, Y. Yang, E. Scholte, M. Di Natale, and A. Sangiovanni-Vincentelli. Optimizing extensibility in hard real-time distributed systems. In Proceedings of the 15th IEEE Real-Time and Embedded Technology and Applications Symposium, pages 275-284, 2009.

Digital Library

[32]

Q. Zhu, H. Zeng, W. Zheng, M. Di Natale, and A. Sangiovanni-Vincentelli. Optimization of task allocation and priority assignment in hard real-time distributed systems. ACM Transactions on Embedded Computing Systems, 11(4):85:1--85:30, 2012.

Digital Library

Cited By

Kang DJung ILee KBaek H(2022)Partitioned Real-Time Scheduling for Preventing Information LeakageIEEE Access10.1109/ACCESS.2022.315405510(22712-22723)Online publication date: 2022
https://doi.org/10.1109/ACCESS.2022.3154055
Amurrio AAzketa EGutiérrez JAldea MParra J(2019)Una revisión de técnicas para la optimización del despliegue y planificación de sistemas de tiempo real distribuidosRevista Iberoamericana de Automática e Informática industrial10.4995/riai.2019.1099716:3(249)Online publication date: 12-Jun-2019
https://doi.org/10.4995/riai.2019.10997
Zhao YZeng H(2019)The concept of Maximal Unschedulable Deadline Assignment for optimization in fixed-priority scheduled real-time systemsReal-Time Systems10.1007/s11241-019-09332-055:3(667-707)Online publication date: 31-Jul-2019
https://dl.acm.org/doi/10.1007/s11241-019-09332-0
Show More Cited By

Index Terms

A two-step optimization technique for functions placement, partitioning, and priority assignment in distributed systems
1. Software and its engineering

Recommendations

A two-step optimization technique for functions placement, partitioning, and priority assignment in distributed systems
LCTES '13

Modern development methodologies from the industry and the academia for complex real-time systems define a stage in which application functions are deployed onto an execution platform. The deployment consists of the placement of functions on a ...
A two-step optimization technique for functions placement, partitioning, and priority assignment in distributed systems
LCTES '13: Proceedings of the 14th ACM SIGPLAN/SIGBED conference on Languages, compilers and tools for embedded systems

Modern development methodologies from the industry and the academia for complex real-time systems define a stage in which application functions are deployed onto an execution platform. The deployment consists of the placement of functions on a ...
Optimizing the deployment of tree-shaped functional graphs of real-time system on distributed architectures

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 ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

LCTES '13: Proceedings of the 14th ACM SIGPLAN/SIGBED conference on Languages, compilers and tools for embedded systems

June 2013

184 pages

ISBN:9781450320856

DOI:10.1145/2491899

General Chair:
Björn Franke
University of Edinburgh, UK
,
Program Chair:
Jingling Xue
University of New South Wales, Australia

ACM SIGPLAN Notices Volume 48, Issue 5
LCTES '13
May 2013
165 pages
ISSN:0362-1340
EISSN:1558-1160
DOI:10.1145/2499369
Issue’s Table of Contents

Copyright © 2013 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 20 June 2013

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

LCTES '13

Sponsor:

LCTES '13: SIGPLAN/SIGBED Conference on Languages, Compilers and Tools for Embedded Systems 2013

June 20 - 21, 2013

Washington, Seattle, USA

Acceptance Rates

LCTES '13 Paper Acceptance Rate 16 of 60 submissions, 27%;

Overall Acceptance Rate 116 of 438 submissions, 26%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

23
Total Citations
View Citations
271
Total Downloads

Downloads (Last 12 months)10
Downloads (Last 6 weeks)1

Reflects downloads up to 22 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Kang DJung ILee KBaek H(2022)Partitioned Real-Time Scheduling for Preventing Information LeakageIEEE Access10.1109/ACCESS.2022.315405510(22712-22723)Online publication date: 2022
https://doi.org/10.1109/ACCESS.2022.3154055
Amurrio AAzketa EGutiérrez JAldea MParra J(2019)Una revisión de técnicas para la optimización del despliegue y planificación de sistemas de tiempo real distribuidosRevista Iberoamericana de Automática e Informática industrial10.4995/riai.2019.1099716:3(249)Online publication date: 12-Jun-2019
https://doi.org/10.4995/riai.2019.10997
Zhao YZeng H(2019)The concept of Maximal Unschedulable Deadline Assignment for optimization in fixed-priority scheduled real-time systemsReal-Time Systems10.1007/s11241-019-09332-055:3(667-707)Online publication date: 31-Jul-2019
https://dl.acm.org/doi/10.1007/s11241-019-09332-0
Mehiaoui AWozniak EBabau JTucci-Piergiovanni SMraidha C(2019)Optimizing the deployment of tree-shaped functional graphs of real-time system on distributed architecturesAutomated Software Engineering10.1007/s10515-018-0244-726:1(1-57)Online publication date: 1-Mar-2019
https://dl.acm.org/doi/10.1007/s10515-018-0244-7
Boudjadar JMacedo HRisco Martín JBesada EDe Rango F(2018)Towards a schedulability-driven architecture exploration for mixed criticality multicore systemsProceedings of the 22nd International Symposium on Distributed Simulation and Real Time Applications10.5555/3330299.3330304(37-46)Online publication date: 15-Oct-2018
https://dl.acm.org/doi/10.5555/3330299.3330304
Boudjadar JMacedo H(2018)Towards a Schedulability-driven Architecture Exploration for Mixed Criticality Multicore Systems2018 IEEE/ACM 22nd International Symposium on Distributed Simulation and Real Time Applications (DS-RT)10.1109/DISTRA.2018.8600927(1-5)Online publication date: Oct-2018
https://doi.org/10.1109/DISTRA.2018.8600927
Motii AHamid BLanusse ABruel J(2016)Guiding the Selection of Security Patterns for Real-Time Systems2016 21st International Conference on Engineering of Complex Computer Systems (ICECCS)10.1109/ICECCS.2016.027(155-164)Online publication date: Nov-2016
https://doi.org/10.1109/ICECCS.2016.027
Motii ALanusse AHamid BBruel J(2016)Model-Based Real-Time Evaluation of Security Patterns: A SCADA System Case StudyComputer Safety, Reliability, and Security10.1007/978-3-319-45480-1_30(375-389)Online publication date: 1-Sep-2016
https://doi.org/10.1007/978-3-319-45480-1_30
Morelli MSeddik YNatale MMraidha CTucci-Piergiovanni S(2015)Simulation-Driven Optimization of Real-Time Control TasksProceedings of the 2015 IEEE 17th International Conference on High Performance Computing and Communications, 2015 IEEE 7th International Symposium on Cyberspace Safety and Security, and 2015 IEEE 12th International Conf on Embedded Software and Systems10.1109/HPCC-CSS-ICESS.2015.276(991-1000)Online publication date: 24-Aug-2015
https://dl.acm.org/doi/10.1109/HPCC-CSS-ICESS.2015.276
Tucci-Piergiovanni SChen DMraidha CLönn HMahmud NReiser MKolagari RYakymets NLibrino RTorchiaro SLanusse A(2014)Model-Based Analysis and Engineering of Automotive Architectures with EAST-ADLHandbook of Research on Embedded Systems Design10.4018/978-1-4666-6194-3.ch010(242-282)Online publication date: 2014
https://doi.org/10.4018/978-1-4666-6194-3.ch010
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents