Design Optimization of Mixed-Criticality Real-Time Embedded Systems
- 30 April 2015
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Embedded Computing Systems
- Vol. 14 (3), 1-29
- https://doi.org/10.1145/2700103
Abstract
In this article, we are interested in implementing mixed-criticality real-time embedded applications on a given heterogeneous distributed architecture. Applications have different criticality levels, captured by their Safety-Integrity Level (SIL), and are scheduled using static-cyclic scheduling. According to certification standards, mixed-criticality tasks can be integrated onto the same architecture only if there is enough spatial and temporal separation among them. We consider that the separation is provided by partitioning, such that applications run in separate partitions, and each partition is allocated several time slots on a processor. Tasks of different SILs can share a partition only if they are all elevated to the highest SIL among them. Such elevation leads to increased development costs, which increase dramatically with each SIL. Tasks of higher SILs can be decomposed into redundant structures of lower SIL tasks. We are interested to determine (i) the mapping of tasks to processors, (ii) the assignment of tasks to partitions, (iii) the decomposition of tasks into redundant lower SIL tasks, (iv) the sequence and size of the partition time slots on each processor, and (v) the schedule tables, such that all the applications are schedulable and the development costs are minimized. We have proposed a Tabu Search-based approach to solve this optimization problem. The proposed algorithm has been evaluated using several synthetic and real-life benchmarks.Keywords
Funding Information
- Advanced Research & Technology for Embedded Intelligence and Systems (ARTEMIS) within the project “RECOMP,” support code 01IS10001A, agreement no. 100202
This publication has 42 references indexed in Scilit:
- Analysis and Optimisation of Hierarchically Scheduled Multiprocessor Embedded SystemsInternational Journal of Parallel Programming, 2007
- Timing analysis of the FlexRay communication protocolReal-Time Systems, 2007
- A Comparison of Partitioning Operating Systems for Integrated SystemsLecture Notes in Computer Science, 2007
- Analysis and optimization of distributed real-time embedded systemsACM Transactions on Design Automation of Electronic Systems, 2004
- Optimal utilization bounds for the fixed-priority scheduling of periodic task systems on identical multiprocessorsInternational Conference on Acoustics, Speech, and Signal Processing (ICASSP), 2004
- A Comparison of Eleven Static Heuristics for Mapping a Class of Independent Tasks onto Heterogeneous Distributed Computing SystemsJournal of Parallel and Distributed Computing, 2001
- Incorporating cost modeling in embedded-system designIEEE Design & Test of Computers, 1997
- On satisfying timing constraints in hard-real-time systemsIEEE Transactions on Software Engineering, 1993
- NP-complete scheduling problemsJournal of Computer and System Sciences, 1975
- A comparison of list schedules for parallel processing systemsCommunications of the ACM, 1974