Parameterized Task Graph Scheduling Algorithm for Comparing Algorithmic Components
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866910364192473088 |
|---|---|
| author | Coleman, Jared Agrawal, Ravi Vivek Hirani, Ebrahim Krishnamachari, Bhaskar |
| author_facet | Coleman, Jared Agrawal, Ravi Vivek Hirani, Ebrahim Krishnamachari, Bhaskar |
| contents | Scheduling distributed applications modeled as directed, acyclic task graphs to run on heterogeneous compute networks is a fundamental (NP-Hard) problem in distributed computing for which many heuristic algorithms have been proposed over the past decades. Many of these algorithms fall under the list-scheduling paradigm, whereby the algorithm first computes priorities for the tasks and then schedules them greedily to the compute node that minimizes some cost function. Thus, many algorithms differ from each other only in a few key components (e.g., the way they prioritize tasks, their cost functions, where the algorithms consider inserting tasks into a partially complete schedule, etc.). In this paper, we propose a generalized parametric list-scheduling algorithm that allows mixing and matching different algorithmic components to produce 72 unique algorithms. We benchmark these algorithms on four datasets to study the individual and combined effects of different algorithmic components on performance and runtime. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2403_07112 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Parameterized Task Graph Scheduling Algorithm for Comparing Algorithmic Components Coleman, Jared Agrawal, Ravi Vivek Hirani, Ebrahim Krishnamachari, Bhaskar Distributed, Parallel, and Cluster Computing Scheduling distributed applications modeled as directed, acyclic task graphs to run on heterogeneous compute networks is a fundamental (NP-Hard) problem in distributed computing for which many heuristic algorithms have been proposed over the past decades. Many of these algorithms fall under the list-scheduling paradigm, whereby the algorithm first computes priorities for the tasks and then schedules them greedily to the compute node that minimizes some cost function. Thus, many algorithms differ from each other only in a few key components (e.g., the way they prioritize tasks, their cost functions, where the algorithms consider inserting tasks into a partially complete schedule, etc.). In this paper, we propose a generalized parametric list-scheduling algorithm that allows mixing and matching different algorithmic components to produce 72 unique algorithms. We benchmark these algorithms on four datasets to study the individual and combined effects of different algorithmic components on performance and runtime. |
| title | Parameterized Task Graph Scheduling Algorithm for Comparing Algorithmic Components |
| topic | Distributed, Parallel, and Cluster Computing |
| url | https://arxiv.org/abs/2403.07112 |