research-article

Optimization of task allocation and priority assignment in hard real-time distributed systems

Authors:

Marco DI Natale,

Alberto Sangiovanni-VincentelliAuthors Info & Claims

ACM Transactions on Embedded Computing Systems (TECS), Volume 11, Issue 4

Article No.: 85, Pages 1 - 30

https://doi.org/10.1145/2362336.2362352

Published: 01 January 2013 Publication History

Abstract

The complexity and physical distribution of modern active safety, chassis, and powertrain automotive applications requires the use of distributed architectures. Complex functions designed as networks of function blocks exchanging signal information are deployed onto the physical HW and implemented in a SW architecture consisting of a set of tasks and messages. The typical configuration features priority-based scheduling of tasks and messages and imposes end-to-end deadlines. In this work, we present and compare formulations and procedures for the optimization of the task allocation, the signal to message mapping, and the assignment of priorities to tasks and messages in order to meet end-to-end deadline constraints and minimize latencies. Our formulations leverage worst-case response time analysis within a mixed integer linear optimization framework and are compared for performance against a simulated annealing implementation. The methods are applied for evaluation to an automotive case study of complexity comparable to industrial design problems.

References

[1]

Aström, K. J. and Wittenmark, B. 1990. Computer-Controlled Systems: Theory and Design 2nd ed. Prentice-Hall, Inc., Upper Saddle River, NJ.

Digital Library

[2]

AUTOSAR. 2010a. Autosar release 4.0 os specifications. http://www.autosar.org/download/R4.0/5AUTOSAR_SWS_OS.pdf.

[3]

AUTOSAR. 2010b. Autosar release 4.0 specifications. http://www.autosar.org/.

[4]

Bate, I. and Emberson, P. 2006. Incorporating scenarios and heuristics to improve flexibility in real-time embedded systems. In Proceedings of the 12th IEEE RTAS Conference. 221--230.

Digital Library

[5]

Benveniste, A., Caspi, P., Edwards, S., Halbwachs, N., Guernic, P. L., and de Simone, R. 2003. The synchronous languages 12 years later. Proc. IEEE 91.

Digital Library

[6]

Bini, E. and Buttazzo, G. C. 2002. The space of rate monotonic schedulability. In Proceedings of the 23^rd IEEE Real-Time Systems Symposium. 169--178.

Digital Library

[7]

Bini, E., Huyen Châu Nguyen, T., Richard, P., and Baruah, S. K. 2009. A response-time bound in fixed-priority scheduling with arbitrary deadlines. IEEE Trans. Comput. 58, 2, 279--286.

Digital Library

[8]

Bini, E., Natale, M. D., and Buttazzo, G. 2006. Sensitivity analysis for fixed-priority real-time systems. In Proceedings of the Euromicro Conference on Real-Time Systems.

Digital Library

[9]

Bosch, R. 1991. Can specification, version 2.0.

[10]

Boyd, S., Kim, S., Vandenberghe, L., and Hassibi, A. 2006. A tutorial on geometric programming. Optimiz. Engin. To appear.

[11]

Brook, D. 2000. Embedded real time operating systems and the osek standard. In Proceedings of the SAE World Congress.

[12]

Casparsson, L., Rajnak, A., Tindell, K., and Malmberg, P. 1999. Volcano, a revolution in on-board communications. Tech. rep. Volvo Technology.

[13]

Davis, R. I. and Burns, A. 2009. Priority assignment for global fixed priority pre-emptive scheduling in multiprocessor real-time systems. In Proceedings of the 30th IEEE Real-Time Systems Symposium. 398--409.

Digital Library

[14]

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

Digital Library

[15]

Flexray. 2006. Protocol specification v2.1 rev. a. http://www.flexray.com.

[16]

Gerber, R., Hong, S., and Saksena, M. 1995. Guaranteeing real-time requirements with resource-based calibration of periodic processes. IEEE Trans. Soft. Engin. 21, 7, 579--592.

Digital Library

[17]

Gutiérrez, J. P., García, J. J. G., and Harbour, M. G. 1997. On the schedulability analysis for distributed hard real-time systems. In Proceedings of 9th Euromicro Workshop on Real-Time Systems. 136--143.

[18]

Hamann, A., Henia, R., Jerzak, M., Racu, R., Richter, K., and Ernst, R. 2004. SymTA/S symbolic timing analysis for systems. http://www.symta.org.

[19]

Hamann, A., Racu, R., and Ernst, R. 2006. A formal approach to robustness maximization of complex heterogeneous embedded systems. In Proceedings of the CODES/ISSS Conference.

Digital Library

[20]

Hamann, A., Racu, R., and Ernst, R. 2007. Multi-dimensional robustness optimization in heterogeneous distributed embedded systems. In Proceedings of the 13th IEEE RTAS Conference.

Digital Library

[21]

Harbour, M. G., Klein, M., and Lehoczky, J. 1994. Timing analysis for fixed-priority scheduling of hard real-time systems. IEEE Trans. Softw. Engin. 20, 1.

Digital Library

[22]

He, X., Gu, Z., and Zhu, Y. 2009. Task allocation and optimization of distributed embedded systems with simulated annealing and geometric programming. Computer J.

Digital Library

[23]

Henriksson, D., Cervin, A., and Årzén, K.-E. 2002. Truetime: Simulation of control loops under shared computer resources. In Proceedings of the 15th IFAC World Congr. Automatic Control.

[24]

Joseph, M. and Pandya, P. K. 1986. Finding response times in a real-time system. Computer J. 29, 5, 390--395.

[25]

Kienhuis, B., Deprettere, E. F., van der Wolf, P., and Vissers, K. A. 2002. A methodology to design programmable embedded systems - the Y-chart approach. In Embedded Processor Design Challenges: Systems, Architectures, Modeling, and Simulation-(SAMOS), E. F. Deprettere, J. Teich, and S. Vassiliadis, Eds., Lecture Notes in Computer Science, vol. 2268, Springer, 18--37.

Digital Library

[26]

Kopetz, H., Damm, A., Koza, C., Mulazzani, M., Schwabla, W., Senft, C., and Zainlinger, R. 1989. Distributed fault-tolerant real-time systems: The mars approach. IEEE Micro 9, 1.

Digital Library

[27]

Lakshmanan, K., Niz, D. d., and Rajkumar, R. 2009. Coordinated task scheduling, allocation and synchronization on multiprocessors. In Proceedings of the 30th IEEE Real-Time Systems Symposium. 469--478.

Digital Library

[28]

Lehoczky, J. P. 1990. Fixed priority scheduling of periodic task sets with arbitrary deadline. In Proceedings of the 11^th IEEE Real-Time Systems Symposium. 201--209.

[29]

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

Digital Library

[30]

Liu, J. W. S. 2000. Real-Time Systems. Prentice Hall.

[31]

Metzner, A. and Herde, C. 2006. Rtsat-- an optimal and efficient approach to the task allocation problem in distributed architectures. In Proceedings of the 27th IEEE International Real-Time Systems Symposium. IEEE Computer Society, Los Alamitos, CA, 147--158.

Digital Library

[32]

OSEK. 2006. Osek os version 2.2.3 specification. http://www.osek-vdx.org.

[33]

Padmanabhan, K. Z., Pillai, P., and Shin, K. G. 1999. Emeralds-osek: A small real-time operating system for automotive control and monitoring. In Proceedings of the SAE International Congress and Exhibition.

[34]

Palencia, J. C. and Harbour, M. G. 1998. Schedulability analysis for tasks with static and dynamic offsets. In Proceedings of the 19th IEEE RTSS Conference. 26.

Digital Library

[35]

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

Digital Library

[36]

Pop, T., Eles, P., and Peng, Z. 2002. Holistic scheduling and analysis of mixed time/event-triggered distributed embedded systems. In Proceedings of the 10th International Symposium on Hardware/Software Codesign. 187--192.

Digital Library

[37]

Pop, T., Eles, P., and Peng, Z. 2003. Design optimization of mixed time/event-triggered distributed embedded systems. In Proceedings of the 1st IEEE/ACM/IFIP International Conference on Hardware/Software Codesign and System Synthesis. ACM Press, New York, NY, 83--89.

Digital Library

[38]

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

Digital Library

[39]

Ramamritham, K., Fohler, G., and Adan, J. M. 1993. Issues in the static allocation and scheduling of complex periodic tasks. In Proceedings of the 10th IEEE Workshop on Real-Time Operating Systems and Software. IEEE Computer Society, 11--16.

Digital Library

[40]

Saket, R. and Navet, N. 2006. Frame packing algorithms for automotive applications. J. Embed. Comput. 2, 1, 93--102.

Digital Library

[41]

Saksena, M. and Hong, S. 1996. Resource conscious design of distributed real-time systems -- an end-to-end approach. In Proceedings of the IEEE International Conference on Engineering of Complex Computer Systems.

Digital Library

[42]

Sandstrom, K., Norstom, C., and Ahlmark, M. 2000. Frame packing in real-time communication. Proceedings of the 7th International Conference on Real-Time Computing Systems and Applications. 399--403.

Digital Library

[43]

Sha, L., Rajkumar, R., and Lehoczky, J. P. 1990. Priority inheritance protocols: An approach to real-time synchronization. IEEE Trans. Comput. 39, 9.

Digital Library

[44]

Tindell, K. W. 1993. Holistic schedulability analysis for distributed hard real-time systems. Tech. rep. YCS 197, Department of Computer Science, University of York.

[45]

Zheng, W., Zhu, Q., Natale, M. D., and Vincentelli, A. S. 2007. Definition of task allocation and priority assignment in hard real-time distributed systems. In Proceedings of the 28th IEEE International Real-Time Systems Symposium. 161--170.

Digital Library

[46]

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

Digital Library

Cited By

Ortiz LGuasque ABalbastre PSimó J(2024)Allocation algorithms for multicore partitioned mixed-criticality real-time systemsPeerJ Computer Science10.7717/peerj-cs.260910(e2609)Online publication date: 20-Dec-2024
https://doi.org/10.7717/peerj-cs.2609
Askaripoor HMueller TKnoll A(2024)E/E Designer: A Framework to Design and Synthesize Vehicle E/E ArchitectureIEEE Transactions on Intelligent Vehicles10.1109/TIV.2023.33246179:7(5204-5221)Online publication date: Jul-2024
https://doi.org/10.1109/TIV.2023.3324617
Deng XRaja SZhao YZeng H(2024)Priority Assignment for Global Fixed Priority Scheduling on MultiprocessorsIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2024.337658843:9(2538-2550)Online publication date: 13-Mar-2024
https://dl.acm.org/doi/10.1109/TCAD.2024.3376588
Show More Cited By

Index Terms

Optimization of task allocation and priority assignment in hard real-time distributed systems

Recommendations

Period optimization for hard real-time distributed automotive systems
DAC '07: Proceedings of the 44th annual Design Automation Conference

The complexity and physical distribution of modern active-safety automotive applications requires the use of distributed architectures. These architectures consist of multiple electronic control units (ECUs) connected with standardized buses. The most ...
Timing Analysis for Fixed-Priority Scheduling of Hard Real-Time Systems

This paper presents a timing analysis for a quite general hard real-time periodic task set on a uniprocessor using fixed-priority methods. Periodic tasks are composed of serially executed subtasks, where each subtask is characterized by an execution ...
Code Optimization of Periodic Preemptive Hard Real-Time Multitasking Systems
ISORC '15: Proceedings of the 2015 IEEE 18th International Symposium on Real-Time Distributed Computing

In hard real-time systems, each task has to provably finish its execution within its respective deadline. Compiler optimizations can be used to improve each task's timing behavior. However, current compilers do not consider tasks' deadlines and can ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Transactions on Embedded Computing Systems

ACM Transactions on Embedded Computing Systems Volume 11, Issue 4

December 2012

459 pages

ISSN:1539-9087

EISSN:1558-3465

DOI:10.1145/2362336

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]

Publisher

Association for Computing Machinery

New York, NY, United States

Journal Family

ACM Journals for the Design of Smart and Connected Systems

Publication History

Published: 01 January 2013

Accepted: 01 November 2010

Revised: 01 August 2010

Received: 01 February 2010

Published in TECS Volume 11, Issue 4

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

60
Total Citations
View Citations
1,013
Total Downloads

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

Reflects downloads up to 05 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Ortiz LGuasque ABalbastre PSimó J(2024)Allocation algorithms for multicore partitioned mixed-criticality real-time systemsPeerJ Computer Science10.7717/peerj-cs.260910(e2609)Online publication date: 20-Dec-2024
https://doi.org/10.7717/peerj-cs.2609
Askaripoor HMueller TKnoll A(2024)E/E Designer: A Framework to Design and Synthesize Vehicle E/E ArchitectureIEEE Transactions on Intelligent Vehicles10.1109/TIV.2023.33246179:7(5204-5221)Online publication date: Jul-2024
https://doi.org/10.1109/TIV.2023.3324617
Deng XRaja SZhao YZeng H(2024)Priority Assignment for Global Fixed Priority Scheduling on MultiprocessorsIEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems10.1109/TCAD.2024.337658843:9(2538-2550)Online publication date: 13-Mar-2024
https://dl.acm.org/doi/10.1109/TCAD.2024.3376588
Zhong MZeng ZHong ZChen C(2024)Research on Distributed Heterogeneous Factory Task Assignment Problem With Loading Efficiency Constraints: A Case StudyIEEE Access10.1109/ACCESS.2024.349225712(164427-164443)Online publication date: 2024
https://doi.org/10.1109/ACCESS.2024.3492257
Rivas JGutiérrez JGuasque ABalbastre P(2024)Gradient descent algorithm for the optimization of fixed priorities in real-time systemsJournal of Systems Architecture: the EUROMICRO Journal10.1016/j.sysarc.2024.103198153:COnline publication date: 1-Aug-2024
https://dl.acm.org/doi/10.1016/j.sysarc.2024.103198
Hu FMehta KMishra SAlMutawa MFu SCarnevale LRana OVillari M(2023)Distributed Edge AI SystemsProceedings of the IEEE/ACM 16th International Conference on Utility and Cloud Computing10.1145/3603166.3632546(1-6)Online publication date: 4-Dec-2023
https://dl.acm.org/doi/10.1145/3603166.3632546
Bi CGao F(2023)Task Pre-Assignment Method for UAV Swarm Based on Generative Adversarial Network2023 China Automation Congress (CAC)10.1109/CAC59555.2023.10450908(7566-7570)Online publication date: 17-Nov-2023
https://doi.org/10.1109/CAC59555.2023.10450908
Wang DZhang DWang DZhang D(2023)Further ReadingsSocial Edge Computing10.1007/978-3-031-26936-3_8(155-163)Online publication date: 20-Feb-2023
https://doi.org/10.1007/978-3-031-26936-3_8
Wang DZhang DWang DZhang D(2023)Rational Social Edge ComputingSocial Edge Computing10.1007/978-3-031-26936-3_3(29-48)Online publication date: 20-Feb-2023
https://doi.org/10.1007/978-3-031-26936-3_3
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
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 Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Issue’s Table of Contents