Randomized load balancing for tree-structured computation
- 17 December 2002
- proceedings article
- Published by Institute of Electrical and Electronics Engineers (IEEE)
Abstract
In this paper, we study the performance of a randomizedalgorithm for balancing load across a multiprocessorexecuting a dynamic irregular task tree.Specifically, we show that the time taken to explorea task tree is likely to be within a small constantfactor of an inherent lower bound for the tree instance.Our model permits arbitrary task times andoverlap between computation and load balance, andthus extends earlier work which assumed fixed costtasks and used a bulk synchronous style in...Keywords
This publication has 4 references indexed in Scilit:
- Communication complexity for parallel divide-and-conquerPublished by Institute of Electrical and Electronics Engineers (IEEE) ,2002
- A dynamic scheduling method for irregular parallel programsPublished by Association for Computing Machinery (ACM) ,1992
- Guided Self-Scheduling: A Practical Scheduling Scheme for Parallel SupercomputersIEEE Transactions on Computers, 1987
- Gröbner Bases: An Algorithmic Method in Polynomial Ideal TheoryPublished by Springer Nature ,1985