Load Balancing in a Parallel Graph Reducer

Hans-Wolfgang Loidl
SFP'01 - Scottish Functional Programming Workshop, University of Stirling, Scotland, August 22--24, 2001. Trends in Functional Programming, vol. 3, Intellect.

Parallel graph reducers such as GUM use dynamic techniques to manage resources during execution. One important aspect of the dynamic behaviour is the distribution of work. The load balancing mechanism, which controls this aspect, should be flexible, to adjust the distribution of work to hardware characteristics as well as dynamic program characteristics, and scalable, to achieve high utilisation of all processors even on massively parallel machines.

In this paper we study the behaviour of GUM's load balancing mechanism on a high-latency Beowulf multi-processor. We present modifications to the basic load balancing mechanism and discuss runtime measurements, which indicate that these modifications can significantly enhance the scalability of the system.

 title={{Load Balancing in a Parallel Graph Reducer}},
 author={H-W. Loidl},
 booktitle={Trends in Functional Programming},
 editor={Kevin Hammond and Sharon Curtis},
 address={Bristol, UK},

Available in: ps, ps.gz

GPH Papers | GPH