Analysis of Scalable Algorithms for Dynamic Load Balancing and Mapping with Application to Photo-realistic Rendering
Creators: name: Heirich, Alan
Publisher: name: California Institute of Technology
Year: 1997

description: This thesis presents and analyzes scalable algorithms for dynamic load balancing and mapping in distributed computer systems. The algorithms are distributed and concurrent, have no central thread of control, and require no centralized communication. They are derived using spectral properties of graphs: graphs of physical network links among computers in the load balancing problem, and graphs of logical communication channels among processes in the mapping problem. A distinguishing characteristic of these algorithms is that they are scalable: the expected cost of execution does not increase with problem scale. This is proven in a scalability theorem which shows that, for several simple disturbance models, the rate of convergence to a solution is independent of scale. This property is extended through simulated examples and informal argument to general and random disturbances. A worst case disturbance is presented and shown to occur with vanishing probability as the problem scale increases. To verify these conclusions the load balancing algorithm is deployed in support of a photo-realistic rendering application on a parallel computer system based on Monte Carlo path tracing. The performance and scaling of this application, and of the dynamic load balancing algorithm, are measured on different numbers of computers. The results are consistent with the predictions of scalability, and the cost of load balancing is seen to be non-increasing for increasing numbers of computers. The quality of load balancing is evaluated and compared with the quality of solutions produced by competing approaches for up to 1,024 computers. This comparison shows that the algorithm presented here is as good as or better than the most popular competing approaches for this application. The thesis then presents the dynamic mapping algorithm, with simulations of a model problem, and suggests that the pair of algorithms presented here may be an ideal complement to more expensive algorithms such as the well-known recursive spectral bisection.
description: © 1998 Alan Heirich, California Institute of Technology. 

Submitted May 1997. 

The material in this thesis has previously appeared in four journals and four conference proceedings  the journals Parallel Computing. The Journal of Supercomputing  The International Journal of Foundations of Computer Science and The International Journal of Advances in Engineering Software and proceedings of the International Conference on Parallel Processing Eurographics workshop on programming paradigms in graphics the First Eurographics workshop on parallel rendering and visualization and the 4th National Symposium on Large Scale Analysis and Design on High Performance Computers and Workstations. For support in addition to the NSF Center for Research in Parallel Computation I have to thank Paul Messina of Caltech's Center for Advanced Computing Research and Don Greenberg of the Program of Computer Graphics at Cornell University For everything else I have to thank my chairman Jim Arvo, and thesis committee Al Barr Mani Chandy, Carl Kesselman, Peter Schröder, and Steve Wiggins, each of whom has made my experience of Caltech remarkable in a different way previous committees and or advisors Steve Taylor, Christof Koch, Dan Meiron, Yaser Abu-Mustafa, and Alain Martin; others who have made Caltech unforgettable  Herb Keller, Andrew Conley, Michael Holst, Roy Williams, Cheryl Carey, Eric van de Velde, Peter Hofstee, Jan van de Snepscheut, Joel Franklin, and Thomas Caughey; my parents for showing me the value of advanced education Michele Titus for putting up with me and our children Laura Nicole and John for teaching the things that we forget as we get older.
description: Submitted - CSTR1997.pdf
Submitted - postscript.ps