Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2410.17563 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866929555021758464 |
|---|---|
| author | Lendve, Shardul Bletsas, Konstantinos Souto, Pedro F. |
| author_facet | Lendve, Shardul Bletsas, Konstantinos Souto, Pedro F. |
| contents | Parallel real-time embedded applications can be modelled as directed acyclic graphs (DAGs) whose nodes model subtasks and whose edges model precedence constraints among subtasks. Efficiently scheduling such parallel tasks can be challenging in itself, particularly in hard real-time systems where it must be ensured offline that the deadlines of the parallel applications will be met at run time. In this paper, we tackle the problem of scheduling DAG tasks on identical multiprocessor systems efficiently, in terms of processor utilisation. We propose a new algorithm that attempts to use dedicated processor clusters for high-utilisation tasks, as in federated scheduling, but is also capable of reclaiming the processing capacity lost to fragmentation, by splitting the execution of parallel tasks over different existing clusters, in a manner inspired by semi-partitioned C=D scheduling (originally devised for non-parallel tasks). In the experiments with synthetic DAG task sets, our Segmented-Flattened-and-Split scheduling approach achieves a significantly higher scheduling success ratio than federated scheduling. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_17563 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Efficiently Scheduling Parallel DAG Tasks on Identical Multiprocessors Lendve, Shardul Bletsas, Konstantinos Souto, Pedro F. Distributed, Parallel, and Cluster Computing 68W99 C.1.2; C.1.4; D.4.7 Parallel real-time embedded applications can be modelled as directed acyclic graphs (DAGs) whose nodes model subtasks and whose edges model precedence constraints among subtasks. Efficiently scheduling such parallel tasks can be challenging in itself, particularly in hard real-time systems where it must be ensured offline that the deadlines of the parallel applications will be met at run time. In this paper, we tackle the problem of scheduling DAG tasks on identical multiprocessor systems efficiently, in terms of processor utilisation. We propose a new algorithm that attempts to use dedicated processor clusters for high-utilisation tasks, as in federated scheduling, but is also capable of reclaiming the processing capacity lost to fragmentation, by splitting the execution of parallel tasks over different existing clusters, in a manner inspired by semi-partitioned C=D scheduling (originally devised for non-parallel tasks). In the experiments with synthetic DAG task sets, our Segmented-Flattened-and-Split scheduling approach achieves a significantly higher scheduling success ratio than federated scheduling. |
| title | Efficiently Scheduling Parallel DAG Tasks on Identical Multiprocessors |
| topic | Distributed, Parallel, and Cluster Computing 68W99 C.1.2; C.1.4; D.4.7 |
| url | https://arxiv.org/abs/2410.17563 |