More Web Proxy on the site http://driver.im/

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

ACM SIGPLAN Notices, Volume 48, Issue 5

Pages 121 - 132

https://doi.org/10.1145/2499369.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

Barzegaran MPop P(2022)Extensibility-aware Fog Computing Platform configuration for mixed-criticality applicationsJournal of Systems Architecture10.1016/j.sysarc.2022.102776133(102776)Online publication date: Dec-2022
https://doi.org/10.1016/j.sysarc.2022.102776
Kamni SOuhammou YBertout AGrolleau E(2020)Towards a Model-based Multi-Objective Optimization Approach For Safety-Critical Real-Time Systems2020 Design, Automation & Test in Europe Conference & Exhibition (DATE)10.23919/DATE48585.2020.9116388(634-637)Online publication date: Mar-2020
https://doi.org/10.23919/DATE48585.2020.9116388
Lakhdhar WMzid RKhalgui MLi ZFrey GAl-Ahmari A(2019)Multiobjective Optimization Approach for a Portable Development of Reconfigurable Real-Time Systems: From Specification to ImplementationIEEE Transactions on Systems, Man, and Cybernetics: Systems10.1109/TSMC.2017.278146049:3(623-637)Online publication date: Mar-2019
https://doi.org/10.1109/TSMC.2017.2781460
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: 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 ...
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 SIGPLAN Notices

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

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

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]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 20 June 2013

Published in SIGPLAN Volume 48, Issue 5

Check for updates

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

23
Total Citations
View Citations
271
Total Downloads

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

Reflects downloads up to 12 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Barzegaran MPop P(2022)Extensibility-aware Fog Computing Platform configuration for mixed-criticality applicationsJournal of Systems Architecture10.1016/j.sysarc.2022.102776133(102776)Online publication date: Dec-2022
https://doi.org/10.1016/j.sysarc.2022.102776
Kamni SOuhammou YBertout AGrolleau E(2020)Towards a Model-based Multi-Objective Optimization Approach For Safety-Critical Real-Time Systems2020 Design, Automation & Test in Europe Conference & Exhibition (DATE)10.23919/DATE48585.2020.9116388(634-637)Online publication date: Mar-2020
https://doi.org/10.23919/DATE48585.2020.9116388
Lakhdhar WMzid RKhalgui MLi ZFrey GAl-Ahmari A(2019)Multiobjective Optimization Approach for a Portable Development of Reconfigurable Real-Time Systems: From Specification to ImplementationIEEE Transactions on Systems, Man, and Cybernetics: Systems10.1109/TSMC.2017.278146049:3(623-637)Online publication date: Mar-2019
https://doi.org/10.1109/TSMC.2017.2781460
Bouaziz RLemarchand LSinghoff FZalila BJmaiel M(2018)Multi-objective design exploration approach for Ravenscar real-time systemsReal-Time Systems10.1007/s11241-018-9299-654:2(424-483)Online publication date: 1-Apr-2018
https://dl.acm.org/doi/10.1007/s11241-018-9299-6
Zhang XMohan NTorngren MAxelsson JChen D(2017)Architecture exploration for distributed embedded systems: a gap analysis in automotive domain2017 12th IEEE International Symposium on Industrial Embedded Systems (SIES)10.1109/SIES.2017.7993377(1-10)Online publication date: Jun-2017
https://doi.org/10.1109/SIES.2017.7993377
Lakhdhar WMzid RKhalgui MTreves N(2017)A New Approach for Automatic Development of Reconfigurable Real-Time SystemsSoftware Technologies10.1007/978-3-319-62569-0_2(22-44)Online publication date: 12-Jul-2017
https://doi.org/10.1007/978-3-319-62569-0_2
Zhang XFeng LTörngren MChen D(2016)Formulating customized specifications for resource allocation problem of distributed embedded systems2016 IEEE/ACM International Conference on Computer-Aided Design (ICCAD)10.1145/2966986.2967042(1-8)Online publication date: 7-Nov-2016
https://dl.acm.org/doi/10.1145/2966986.2967042
Sayuti MIndrusiak L(2015)Simultaneous Optimisation of Task Mapping and Priority Assignment for Real-Time Embedded NoCsProceedings of the 2015 23rd Euromicro International Conference on Parallel, Distributed, and Network-Based Processing10.1109/PDP.2015.84(692-695)Online publication date: 4-Mar-2015
https://dl.acm.org/doi/10.1109/PDP.2015.84
Bouaziz RLemarchand LSinghoff FZalila BJmaiel M(2015)Architecture Exploration of Real-Time Systems Based on Multi-objective OptimizationProceedings of the 2015 20th International Conference on Engineering of Complex Computer Systems (ICECCS)10.1109/ICECCS.2015.11(1-10)Online publication date: 9-Dec-2015
https://dl.acm.org/doi/10.1109/ICECCS.2015.11
Zhang XFeng LChen DTörngren M(2015)Design-Space Reduction for Architectural Optimization of Automotive Embedded SystemsProceedings 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.298(1103-1109)Online publication date: 24-Aug-2015
https://dl.acm.org/doi/10.1109/HPCC-CSS-ICESS.2015.298
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 Issue’s Table of Contents