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.
|