research-article

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

Authors:

Qi Zhu,

Haibo Zeng,

Wei Zheng,

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

Get Access

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

Google Scholar

[2]

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

Google Scholar

[3]

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

Google Scholar

[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

Google Scholar

[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

Google Scholar

[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

Google Scholar

[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

Google Scholar

[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

Google Scholar

[9]

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

Google Scholar

[10]

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

Google Scholar

[11]

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

Crossref

Google Scholar

[12]

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

Google Scholar

[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

Google Scholar

[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

Google Scholar

[15]

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

Google Scholar

[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

Google Scholar

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

Google Scholar

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

Google Scholar

[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

Google Scholar

[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

Google Scholar

[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

Google Scholar

[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

Google Scholar

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

Crossref

Google Scholar

[24]

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

Crossref

Google Scholar

[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

Google Scholar

[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

Google Scholar

[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

Google Scholar

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

Crossref

Google Scholar

[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

Google Scholar

[30]

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

Google Scholar

[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

Google Scholar

[32]

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

Google Scholar

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

Google Scholar

[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

Google Scholar

[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

Google Scholar

[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

Google Scholar

[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

Google Scholar

[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

Google Scholar

[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

Google Scholar

[40]

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

Digital Library

Google Scholar

[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

Google Scholar

[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

Google Scholar

[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

Google Scholar

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

Google Scholar

[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

Google Scholar

[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

Google Scholar

Cited By

View all

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

Reviews

Reviewer: Amitabha Roy

Zhu et al. study the problem of assigning tasks and signals in an automotive environment, specifically, a vehicle consisting of sensors, actuators, and processors (engine control units, or ECUs) connected by buses. The problem is to map a set of tasks to the ECUs and map signals to message frames on the buses to meet hard real-time constraints on the response to certain events. The goal is to reduce latency in responding to events in general. This paper will be of interest to readers on multiple fronts. First, given the prevalence of distributed computing in automobiles today, many readers will appreciate this glimpse into how information processing happens in vehicles. Second, for uninitiated readers like me, the authors provide some insight into how task assignment can be formulated as a mixed integer linear programming (MILP) problem. While the text is (naturally) heavy on mathematics and thus hard to follow, there are nevertheless some clear markers that allow even the casual reader to figure out what is going on. Although I have little expertise in the application area, it does appear to me that the authors have applied their MILP formulation to an industrial-strength problem, taking five hours to solve a system with upwards of 30,000 variables. They have taken practical steps to increase the tractability of the problem by splitting it into two parts that are assumed to be independent. The solution is much better than stochastic approaches, such as simulated annealing, which takes 23 hours to converge to the same result. Finally, from the perspective of someone with a performance modeling background, the choice of minimizing the sum of latencies as the objective function (equation 70) seems to me to be an interesting approach. I had implicitly assumed that the MILP formulation was chosen purely to meet hard deadlines, but optimizing the sum of latencies using task assignment is an interesting way to approach performance. On the performance front, however, I wish the authors had provided a slightly more complete treatment of queueing delays beyond blocking and (worst-case) interference. It seems to me that this issue causes the solution to be biased toward focusing only on hard real-time deadlines. Online Computing Reviews Service

Access critical reviews of Computing literature here

Become a reviewer for Computing Reviews.

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

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

59
Total Citations
View Citations
1,000
Total Downloads

Downloads (Last 12 months)73
Downloads (Last 6 weeks)11

Reflects downloads up to 25 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

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
Burhan HAttea BAbbood AAbbas MAl-Ani M(2021)Evolutionary multi-objective set cover problem for task allocation in the Internet of ThingsApplied Soft Computing10.1016/j.asoc.2021.107097(107097)Online publication date: Jan-2021
https://doi.org/10.1016/j.asoc.2021.107097
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.

Cited By

Index Terms

Recommendations

Period optimization for hard real-time distributed automotive systems

Timing Analysis for Fixed-Priority Scheduling of Hard Real-Time Systems

Code Optimization of Periodic Preemptive Hard Real-Time Multitasking Systems

Reviews

Access critical reviews of Computing literature here