Multiprocessor Scheduling with Memory Constraints: Fundamental Properties and Finding Optimal Solutions
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915406202011648 |
|---|---|
| author | Papp, Pál András Böhnlein, Toni Yzelman, A. N. |
| author_facet | Papp, Pál András Böhnlein, Toni Yzelman, A. N. |
| contents | We study the problem of scheduling a general computational DAG on multiple processors in a 2-level memory hierarchy. This setting is a natural generalization of several prominent models in the literature, and it simultaneously captures workload balancing, communication, and data movement due to cache size limitations. We first analyze the fundamental properties of this problem from a theoretical perspective, such as its computational complexity. We also prove that optimizing parallelization and memory management separately, as done in many applications, can result in a solution that is a linear factor away from the optimum.
On the algorithmic side, we discuss a natural technique to represent and solve the problem as an Integer Linear Program (ILP). We develop a holistic scheduling algorithm based on this approach, and we experimentally study its performance and properties on a small benchmark of computational tasks. Our results confirm that the ILP-based method can indeed find considerably better solutions than a baseline which combines classical scheduling algorithms and memory management policies. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2507_17411 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Multiprocessor Scheduling with Memory Constraints: Fundamental Properties and Finding Optimal Solutions Papp, Pál András Böhnlein, Toni Yzelman, A. N. Distributed, Parallel, and Cluster Computing 90B35, 90C10, 68Q10, 68W10 C.1.4 We study the problem of scheduling a general computational DAG on multiple processors in a 2-level memory hierarchy. This setting is a natural generalization of several prominent models in the literature, and it simultaneously captures workload balancing, communication, and data movement due to cache size limitations. We first analyze the fundamental properties of this problem from a theoretical perspective, such as its computational complexity. We also prove that optimizing parallelization and memory management separately, as done in many applications, can result in a solution that is a linear factor away from the optimum. On the algorithmic side, we discuss a natural technique to represent and solve the problem as an Integer Linear Program (ILP). We develop a holistic scheduling algorithm based on this approach, and we experimentally study its performance and properties on a small benchmark of computational tasks. Our results confirm that the ILP-based method can indeed find considerably better solutions than a baseline which combines classical scheduling algorithms and memory management policies. |
| title | Multiprocessor Scheduling with Memory Constraints: Fundamental Properties and Finding Optimal Solutions |
| topic | Distributed, Parallel, and Cluster Computing 90B35, 90C10, 68Q10, 68W10 C.1.4 |
| url | https://arxiv.org/abs/2507.17411 |