Parallel path progression DAG scheduling

Simple item page
dc.contributor.authorUeter, Niklas
dc.contributor.authorGünzel, Mario
dc.contributor.authorBrüggen, Georg von der
dc.contributor.authorChen, Jian-Jia
dc.date.accessioned2024-08-27T10:45:29Z
dc.date.available2024-08-27T10:45:29Z
dc.date.issued2023-05-25
dc.description.abstractIncreasing 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.en
dc.identifier.urihttp://hdl.handle.net/2003/42658
dc.identifier.urihttp://dx.doi.org/10.17877/DE290R-24494
dc.language.isoende
dc.relation.ispartofseriesIEEE transactions on computers;72(10)
dc.rights.urihttps://creativecommons.org/licenses/by/4.0/de
dc.subjectReal-time DAG schedulingen
dc.subjecthomogeneous multicore platformsen
dc.subjecthierarchical schedulingen
dc.subjectapproximation algorithmsen
dc.subject.ddc004
dc.subject.rswkAzyklischer gerichteter Graphde
dc.subject.rswkMehrkernprozessorde
dc.subject.rswkSchedulingde
dc.subject.rswkApproximationsalgorithmusde
dc.titleParallel path progression DAG schedulingen
dc.typeTextde
dc.type.publicationtypeArticlede
dcterms.accessRightsopen access
eldorado.openaire.projectidentifierinfo:eu-repo/grantAgreement/EC/H2020/NUMMER/EU/Property-Based Modulable Timing Analysis and Optimization for Complex Cyber-Physical Real-Time Systems/PropRT
eldorado.secondarypublicationtruede
eldorado.secondarypublication.primarycitationN. Ueter, M. Günzel, G. v. d. Brüggen and J. -J. Chen, "Parallel Path Progression DAG Scheduling," in IEEE Transactions on Computers, vol. 72, no. 10, pp. 3002-3016, Oct. 2023, doi: 10.1109/TC.2023.3280137.en
eldorado.secondarypublication.primaryidentifierhttps://doi.org/10.1109/TC.2023.3280137de

Files

Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
Parallel_Path_Progression_DAG_Scheduling.pdf
Size:
909.27 KB
Format:
Adobe Portable Document Format
Description:
DNB
Download
License bundle
Now showing 1 - 1 of 1
No Thumbnail Available
Name:
license.txt
Size:
4.85 KB
Format:
Item-specific license agreed upon to submission
Description:
Download

Collections

Entwurfsautomatisierung für Eingebettete Systeme