Details:

Title	Randomized Load-Balancing for Tree-Structured Computation
Author(s)	Soumen Chakrabarti, Katherine A. Yelick
Type	Article in Conference Proceedings
Abstract	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.
Length	8
File
Language	English
Pages	666-673
Year	1994
Translation	No
Refereed	No
Conferencename	IEEE Scalable High Performance Computing Conference