Decentralized list scheduling
From MaRDI portal
Publication:367649
DOI10.1007/S10479-012-1149-7zbMATH Open1273.90086arXiv1107.3734OpenAlexW2029265412MaRDI QIDQ367649FDOQ367649
Nicolas Gast, Marc Tchiboukdjian, Denis Trystram
Publication date: 16 September 2013
Published in: Annals of Operations Research (Search for Journal in Brave)
Abstract: Classical list scheduling is a very popular and efficient technique for scheduling jobs in parallel and distributed platforms. It is inherently centralized. However, with the increasing number of processors, the cost for managing a single centralized list becomes too prohibitive. A suitable approach to reduce the contention is to distribute the list among the computational units: each processor has only a local view of the work to execute. Thus, the scheduler is no longer greedy and standard performance guarantees are lost. The objective of this work is to study the extra cost that must be paid when the list is distributed among the computational units. We first present a general methodology for computing the expected makespan based on the analysis of an adequate potential function which represents the load unbalance between the local lists. We obtain an equation on the evolution of the potential by computing its expected decrease in one step of the schedule. Our main theorem shows how to solve such equations to bound the makespan. Then, we apply this method to several scheduling problems, namely, for unit independent tasks, for weighted independent tasks and for tasks with precendence constraints. More precisely, we prove that the time for scheduling a global workload W composed of independent unit tasks on m processors is equal to W/m plus an additional term proportional to log_2 W. We provide a lower bound which shows that this is optimal up to a constant. This result is extended to the case of weighted independent tasks. In the last setting, precedence task graphs, our analysis leads to an improvement on the bound of Arora et al. We finally provide some experiments using a simulator. The distribution of the makespan is shown to fit existing probability laws. The additive term is shown by simulation to be around 3 log_2 W confirming the tightness of our analysis.
Full work available at URL: https://arxiv.org/abs/1107.3734
Recommendations
- A tighter analysis of work stealing
- On the Expected Relative Performance of List Scheduling
- Probabilistic Bounds on the Performance of List Scheduling
- A probabilistic analysis of multiprocessor list scheduling: the erlang case
- Analysis of the list scheduling algorithm for precedence constrained parallel tasks
Cites Work
- Title not available (Why is that?)
- Scheduling multithreaded computations by work stealing
- Thread scheduling for multiprogrammed multiprocessors
- Title not available (Why is that?)
- On weighted balls-into-bins games
- Balanced Allocations
- Bounds on Multiprocessing Timing Anomalies
- Distributed Selfish Load Balancing
- Title not available (Why is that?)
- On-line hierarchical job scheduling on grids with admissible allocation
- Scheduling for parallel processing
- Scheduling Precedence Graphs in Systems with Interprocessor Communication Times
- Online scheduling of parallel programs on heterogeneous systems with applications to Cilk
- Title not available (Why is that?)
- An efficient approximation algorithm for minimizing makespan on uniformly related machines.
- A Tighter Analysis of Work Stealing
- The Natural Work-Stealing Algorithm is Stable
Cited In (1)
Uses Software
This page was built for publication: Decentralized list scheduling
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q367649)
