Optimizing load balancing and data-locality with data-aware scheduling
- 1 October 2014
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 119-128
Abstract
Load balancing techniques (e.g. work stealing) are important to obtain the best performance for distributed task scheduling systems that have multiple schedulers making scheduling decisions. In work stealing, tasks are randomly migrated from heavy-loaded schedulers to idle ones. However, for data-intensive applications where tasks are dependent and task execution involves processing a large amount of data, migrating tasks blindly yields poor data-locality and incurs significant data-transferring overhead. This work improves work stealing by using both dedicated and shared queues. Tasks are organized in queues based on task data size and location. We implement our technique in MATRIX, a distributed task scheduler for many-task computing. We leverage distributed key-value store to organize and scale the task metadata, task dependency, and data-locality. We evaluate the improved work stealing technique with both applications and micro-benchmarks structured as direct acyclic graphs. Results show that the proposed data-aware work stealing technique performs well.Keywords
This publication has 31 references indexed in Scilit:
- Achieving Efficient Distributed Scheduling with Message Queues in the Cloud for Many-Task Computing and High-Performance Computing2014
- Using simulation to explore distributed key-value stores for extreme-scale system services2013
- Sparrow2013
- Modeling Many-Task Computing Workloads on a Petaflop IBM Blue Gene/P Supercomputer2013
- Hierarchical Load Balancing for Charm++ Applications on Large Supercomputers2010
- SLAW2010
- Scalable work stealing2009
- Quincy2009
- Dynamo2007
- Dryad2007