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

Open Access document in PolyPublie
Open Access to the full text of this document
Accepted Version
Terms of Use: Tous droits réservés
Download (753kB)
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

Subjects: 2700 Information technology > 2700 Information technology
2700 Information technology > 2702 Computer systems organization
Department: Department of Computer Engineering and Software Engineering
Grant number: 446057-12
PolyPublie URL: https://publications.polymtl.ca/2546/
Journal Title: Design Automation for Embedded Systems (vol. 21, no. 2)
Publisher: Springer
DOI: 10.1007/s10617-017-9185-9
Official URL: https://doi.org/10.1007/s10617-017-9185-9
Date Deposited: 29 Sep 2017 16:10
Last Modified: 05 Apr 2024 19:58
Cite in APA 7: 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), 117-136. https://doi.org/10.1007/s10617-017-9185-9


Total downloads

Downloads per month in the last year

Origin of downloads


Repository Staff Only

View Item View Item