<  Back to the Polytechnique Montréal portal

Scheduling real-time systems with cyclic dependence using data criticality

Imane Hafnaoui, Rabeh Ayari, Gabriela Nicolescu and Giovanni Beltrame

Article (2017)

Accepted Version
Terms of Use: Tous droits réservés.
Download (1MB)
Cite this document: Hafnaoui, I., Ayari, R., Nicolescu, G. & Beltrame, G. (2017). Scheduling real-time systems with cyclic dependence using data criticality. Design Automation for Embedded Systems, 21(2), p. 117-136. doi:10.1007/s10617-017-9185-9
Show abstract Hide abstract


The increase of interdependent components in avionic and automotive software rises new challenges for real-time system integration. For instance, most scheduling and mapping techniques proposed in the literature rely on the availability of the system’s DAG representation. However, at the initial stage of system design, a dataflow graph (DFG) is generally used to represent the dependence between software components. Due to limited software knowledge, legacy components might not have fully-specified dependencies, leading to cycles in the DFG and making it difficult to determine the overall scheduling of the system as well as restrict access to DAG-based techniques. In this paper, we propose an approach that breaks cycles based on the assignment of a degree of importance and that with no inherent knowledge of the functional or temporal behaviour of the components. We define a “criticality” metric that quantifies the effect of removing edges on the system by tracking the propagation of error in the graph. The approach was reported to produce systems (56±14)% less critical than other methods. It was also validated on two case studies; a data modem and an industrial full-mission simulator, while ensuring the correctness of the system is maintained.

Uncontrolled Keywords

Execution order assignment, Real-time systems, System scheduling, System integration, Data criticality, Cyclic dependency, Directed acyclic graph

Open Access document in PolyPublie
Subjects: 2700 Technologie de l'information > 2700 Technologie de l'information
2700 Technologie de l'information > 2702 Organisation des systèmes informatiques
Department: Département de génie informatique et génie logiciel
Research Center: Non applicable
Grant number: 446057-12
Date Deposited: 29 Sep 2017 16:10
Last Modified: 08 Apr 2021 10:43
PolyPublie URL: https://publications.polymtl.ca/2546/
Document issued by the official publisher
Journal Title: Design Automation for Embedded Systems (vol. 21, no. 2)
Publisher: Springer
Official URL: https://doi.org/10.1007/s10617-017-9185-9


Total downloads

Downloads per month in the last year

Origin of downloads


Repository Staff Only