Back to Search
Start Over
Minimizing Stretch and Makespan of Multiple Parallel Task Graphs via Malleable Allocations
- Source :
- Proceedings of the 39th International Conference on Parallel Processing (ICPP'10), 39th International Conference on Parallel Processing, 39th International Conference on Parallel Processing, Sep 2010, San Diego, United States. pp.71-80, ⟨10.1109/ICPP.2010.16⟩, ICPP
- Publication Year :
- 2010
- Publisher :
- HAL CCSD, 2010.
-
Abstract
- International audience; Many scientific applications can be structured as Parallel Task Graphs (PTGs), i.e., graphs of data-parallel tasks. Adding data-parallelism to a task-parallel application provides opportunities for higher performance and scalability, but poses scheduling challenges. We study the off-line scheduling of multiple PTGs on a single, homogeneous cluster. The objective is to optimize performance and fairness. We propose a novel algorithm that first computes perfectly fair PTG completion times assuming that each PTG is an ideal malleable job. These completion times are then relaxed so that the schedule is organized as a sequence of periods and is still close to the perfectly fair schedule. Finally, since PTGs are not perfectly malleable, the algorithm increases the execution time of all PTGs uniformly until it can successfully schedule each task in a period. Our evaluation in simulation, using both synthetic and real-world application configurations, shows that our algorithm outperforms previously proposed algorithms when considering two different performance metrics and one fairness metric.
- Subjects :
- 020203 distributed computing
Mathematical optimization
Job shop scheduling
Computer science
[INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS]
Parallel algorithm
02 engineering and technology
Parallel computing
Directed graph
Execution time
Scheduling (computing)
Scalability
0202 electrical engineering, electronic engineering, information engineering
Task analysis
Resource allocation
020201 artificial intelligence & image processing
[INFO.INFO-DC]Computer Science [cs]/Distributed, Parallel, and Cluster Computing [cs.DC]
Subjects
Details
- Language :
- English
- Database :
- OpenAIRE
- Journal :
- Proceedings of the 39th International Conference on Parallel Processing (ICPP'10), 39th International Conference on Parallel Processing, 39th International Conference on Parallel Processing, Sep 2010, San Diego, United States. pp.71-80, ⟨10.1109/ICPP.2010.16⟩, ICPP
- Accession number :
- edsair.doi.dedup.....2b68b89a314c35d773c38255d6f24ca8