Randomized Load Balancing for Tree-structured Computation

Soumen Chakrabarti, Abhiram Ranade, and Katherine Yelick

In this paper, we study the performance of a randomized
algorithm for balancing load across a multiprocessor executing a
dynamic irregular task tree.  Specifically, we show that the
time taken to explore a task tree is likely to be within a small
constant factor of an inherent lower bound for the tree
instance.  Our model permits arbitrary task times and overlap
between computation and load balance, and thus extends earlier
work which assumed fixed cost tasks and used a bulk synchronous
style in which the system alternated between distinct computing
and load balancing steps.  Our analysis is supported by
experiments with application codes, demonstrating that the 
efficiency is high enough to make this method practical.