Data-Locality-Aware Task Assignment and Scheduling for Distributed Job Executions
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915411731152896 |
|---|---|
| author | Zhao, Hailiang Tang, Xueyan Chen, Peng Yin, Jianwei Deng, Shuiguang |
| author_facet | Zhao, Hailiang Tang, Xueyan Chen, Peng Yin, Jianwei Deng, Shuiguang |
| contents | This paper addresses the data-locality-aware task assignment and scheduling problem for distributed job executions. Our goal is to minimize job completion times without prior knowledge of future job arrivals. We propose an Optimal Balanced Task Assignment algorithm (OBTA), which achieves minimal job completion times while significantly reducing computational overhead through efficient narrowing of the solution search space. To balance performance and efficiency, we extend the approximate Water-Filling (WF) algorithm, providing a rigorous proof that its approximation factor equals the number of task groups in a job. We also introduce a novel heuristic, Replica-Deletion (RD), which outperforms WF by leveraging global optimization techniques. To further enhance scheduling efficiency, we incorporate job ordering strategies based on a shortest-estimated-time-first policy, reducing average job completion times across workloads. Extensive trace-driven evaluations validate the effectiveness and scalability of the proposed algorithms. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2407_08584 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Data-Locality-Aware Task Assignment and Scheduling for Distributed Job Executions Zhao, Hailiang Tang, Xueyan Chen, Peng Yin, Jianwei Deng, Shuiguang Distributed, Parallel, and Cluster Computing This paper addresses the data-locality-aware task assignment and scheduling problem for distributed job executions. Our goal is to minimize job completion times without prior knowledge of future job arrivals. We propose an Optimal Balanced Task Assignment algorithm (OBTA), which achieves minimal job completion times while significantly reducing computational overhead through efficient narrowing of the solution search space. To balance performance and efficiency, we extend the approximate Water-Filling (WF) algorithm, providing a rigorous proof that its approximation factor equals the number of task groups in a job. We also introduce a novel heuristic, Replica-Deletion (RD), which outperforms WF by leveraging global optimization techniques. To further enhance scheduling efficiency, we incorporate job ordering strategies based on a shortest-estimated-time-first policy, reducing average job completion times across workloads. Extensive trace-driven evaluations validate the effectiveness and scalability of the proposed algorithms. |
| title | Data-Locality-Aware Task Assignment and Scheduling for Distributed Job Executions |
| topic | Distributed, Parallel, and Cluster Computing |
| url | https://arxiv.org/abs/2407.08584 |