Distributed Load Balancing Algorithms for Parallel Volume Rendering on Cluster of PCs
 
Alexandre Coelho and Andrei Gomes Lopes and Cristiana Bentes
State University of Rio de Janeiro, Department and Systems Engineering
Rio de Janeiro, Brazil, 20555-013
cristianabentes@gmail.com

and

Maria Clicia Stelling de Castro
State University of Rio de Janeiro, Institute of Mathematics and Statistics
Rio de Janeiro, Brazil, 20555-013
clicia@ime.uerj.br

and

Ricardo Farias
COPPE/UFRJ, University Federal of Rio de Janeiro
Rio de Janeiro, Brazil, 21941-972
rfarias@cos.ufrj.br
 
Abstract
 
Distributed systems, such as clusters of PCs, are low-cost alternatives for running parallel rendering systems. Parallel rendering applications, however, usually suffer from high load imbalance during execution, and the high communication overhead of a cluster of PCs worsens this problem. In this paper we propose some general distributed load balancing algorithms that can be applied to tile-based parallel rendering system. Our goal is to provide distributed algorithms that do not overload the network with load balancing messages. We developed three different load balancing algorithms: Nearest Neighbor, Longest Queue, and Circular Distribution, providing dynamic redistribution of work in different ways. We implemented these three algorithms on top of PZSweep algorithm, and our experimental results show that the load balancing algorithms we proposed provides rendering with up to 80% of parallel efficiency and only 30% of load imbalance.
 
Keywords: Parallel Rendering, Load-Balancing, Distributed Systems.