FLB: Fast Load Balancing for distributed-memory machines
- 20 January 2003
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 534-541
- https://doi.org/10.1109/icpp.1999.797442
Abstract
This paper describes a novel compile-time list-based task scheduling algorithm for distributed-memory systems, called Fast Load Balancing (FLB). Compared to other typical list scheduling heuristics, FLB drastically reduces scheduling time complexity to O(V(log(W)+log (P))+E), where V and E are the number of tasks and edges in the task graph, respectively, W is the task graph width and P is the number of processors. It is proven that FLB is essentially equivalent to the existing ETF scheduling algorithm of O(W(E+V)P) time complexity. Experiments also show that FLB performs equally to other one-step algorithms of much higher cost, such as MCP. Moreover, FLB consistently outperforms multi-step algorithms such as DSC-LLB that also have higher cost.Keywords
This publication has 10 references indexed in Scilit:
- FLB: Fast Load Balancing for distributed-memory machinesPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- Applications and performance analysis of a compile-time optimization approach for list scheduling algorithms on distributed memory multiprocessorsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2003
- On the complexity of list scheduling algorithms for distributed-memory systemsPublished by Association for Computing Machinery (ACM) ,1999
- Benchmarking the task graph scheduling algorithmsPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1997
- A New Approach to Scheduling Parallel Programs Using Task DuplicationPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1994
- DSC: scheduling parallel tasks on an unbounded number of processorsIEEE Transactions on Parallel and Distributed Systems, 1994
- A compile-time scheduling heuristic for interconnection-constrained heterogeneous processor architecturesIEEE Transactions on Parallel and Distributed Systems, 1993
- Hypertool: a programming aid for message-passing systemsIEEE Transactions on Parallel and Distributed Systems, 1990
- Scheduling Precedence Graphs in Systems with Interprocessor Communication TimesSIAM Journal on Computing, 1989
- Grain size determination for parallel processingIEEE Software, 1988