Parallel Path Progression DAG Scheduling
Open Access
- 25 May 2023
- journal article
- research article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in International Conference on Acoustics, Speech, and Signal Processing (ICASSP)
- Vol. 72 (10), 3002-3016
- https://doi.org/10.1109/tc.2023.3280137
Abstract
Increasing performance needs of modern cyber-physical systems leads to multiprocessor architectures being increasingly utilized. To efficiently exploit their potential parallelism in hard real-time systems, appropriate task models and scheduling algorithms that allow to provide timing guarantees are required. Such scheduling algorithms and the corresponding worst-case response time analyses usually suffer from resource over-provisioning due to pessimistic analyses based on worst-case assumptions. Hence, scheduling algorithms and analyses with high resource efficiency are required. A prominent fine-grained parallel task model is the directed-acyclic-graph (DAG) task model that is composed of precedence constrained subjobs. This paper studies the hierarchical real-time scheduling problem of sporadic arbitrary-deadline DAG tasks. We propose a parallel path progression scheduling property that is implemented with only two distinct subtask priorities, which allows to quantify the parallel execution of a user chosen collection of complete paths in the response time analysis. This novel approach significantly improves the state-of-the-art response time analyses for parallel DAG tasks for highly parallel DAG structures and can provably exhaust large core numbers. Two hierarchical scheduling algorithms are designed based on this property, extending the parallel path progression properties and improve the response time analysis for sporadic arbitrary-deadline DAG task sets.Keywords
This publication has 36 references indexed in Scilit:
- Response-Time Analysis of Conditional DAG Tasks in Multiprocessor SystemsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2015
- Federated Scheduling of Sporadic DAG Task SystemsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2015
- The Federated Scheduling of Constrained-Deadline Sporadic DAG Task SystemsPublished by EDAA ,2015
- OpenMP and Timing Predictability: A Possible Union?Published by EDAA ,2015
- Response-Time Analysis of Synchronous Parallel Tasks in Multiprocessor SystemsPublished by Association for Computing Machinery (ACM) ,2014
- OmpSs: A PROPOSAL FOR PROGRAMMING HETEROGENEOUS MULTI-CORE ARCHITECTURESParallel Processing Letters, 2011
- Performance characteristics of gang scheduling in multiprogrammed environmentsPublished by Association for Computing Machinery (ACM) ,1997
- Gang scheduling performance benefits for fine-grain synchronizationJournal of Parallel and Distributed Computing, 1992
- Independence numbers of graphs-an extension of the Koenig-Egervary theoremDiscrete Mathematics, 1979
- An analysis of approximations for maximizing submodular set functions—IMathematical Programming, 1978