A COMPETITIVE ANALYSIS OF LOAD BALANCING STRATEGIES FOR PARALLEL RAY-TRACING

This paper examines the effectiveness of load balancing strategies for ray tracing on large parallel computer systems and cluster computers. Popular static load balancing strategies are shown to be inadequate f or rendering complex images with contemporary ray tracing algorithms, and for rendering NTSC resolution images on 128 or more computers. Str ategies based on image tiling are shown to be ineffective except on ve ry small numbers of computers. A dynamic load balancing strategy, base d on a diffusion model, is applied to a parallel Monte Carlo rendering system. The diffusive strategy is shown to remedy the defects of the static strategies. A hybrid strategy that combines static and dynamic approaches produces nearly optimal performance on a variety of images and computer systems. The theoretical results should be relevant to ot her rendering and image processing applications.