Abstract
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 for rendering complex images with contemporary ray tracing algorithms, and for rendering NTSC resolution images on 128 or more computers. Strategies based on image tiling are shown to be ineffective except on very small numbers of computers. A dynamic load balancing strategy, based 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 other rendering and image processing applications.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Anderson, T. E., Culler, D. E. & Patterson, D. A. 1995. A case for NOW (Networks of Workstations). IEEE Micro, 15: 54–64.
Baskett, F. & Hennessy, J. L. 1993. Microprocessors: from desktops to supercomputers. Science, 261: 864–871.
Boden, N. J., Cohen, D., Felderman, R. E., Kulawik, A. E., Seitz, C. L., Seizovic, J. N. & Su, W. 1995. Myrinet: a gigabit per second local area network. IEEE Micro, 15: 29–36.
Cybenko, G. 1989. Dynamic load balancing for distributed memory multiprocessors. Journal of Parallel and Distributed Computing, 7: 279–301.
Delaney, H. C. 1988. Ray tracing on the Connection Machine. Proceedings of SIGGRAPH (Atlanta, August), ACM Press, pp. 659–664.
Dijkstra, E. W. & Schölten, C. S. 1980. Termination detection for diffusing computations. Information Processing Letters, 11: 1–14.
Hanrahan, P., Saltzman, D. & Aupperle, L. 1991. A rapid hierarchical radiosity algorithm. Computer Graphics, 25: 197–206.
Heirich, A. & Taylor, S. 1995. A parabolic load balancing method. Proceedings of the 24th International Conference on Parallel Processing (Milwaukee, August), CRC Press, III, pp. 192–202.
Heirich, A. 1997. A scalable diffusion algorithm for dynamic mapping and load balancing on networks of arbitrary topology. To appear in The International Journal of Foundations of Computer Science.
Heirich, A. & Arvo, J. 1997. Scalable Monte Carlo image synthesis. To appear in Parallel Computing.
Kajiya, J. T. 1986. The rendering equation. Computer Graphics, 20: 143–150.
Karypis, G. & Kumar, V. 1995. Multilevel graph partitioning schemes. Proceedings of the 24th International Conference on Parallel Processing (Milwaukee, August), CRC Press, III, pp. 113–122.
Lindgren, B. W. 1962. Statistical Theory. New York: Macmillan.
Priol, T. & Bouatouch, K. 1988. Experimenting with a parallel ray-tracing algorithm on a hypercube machine. Proceedings of Eurographics (Nice, September), North-Holland, pp. 243–259.
Salmon, J. 1988. A mathematical analysis of the scattered decomposition. Proceedings of the Third Caltech Conference on Hypercube Computers and Applications (Pasadena, January), ACM Press, pp. 239–240.
Sterling, T. L. 1996. The scientific workstation of the future may be a pile-of-pcs. Communications of the ACM, 39: 11–12.
Taubes, G. 1996. Do-it-yourself supercomputers. Science, 274: 1840.
Williams, R. D. 1991. Performance of dynamic load balancing algorithms for unstructured mesh calculations. Concurrency: Practice and Experience, 3: 457–481.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Heirich, A., Arvo, J. A Competitive Analysis of Load Balancing Strategies for Parallel Ray Tracing. The Journal of Supercomputing 12, 57–68 (1998). https://doi.org/10.1023/A:1007977326603
Issue Date:
DOI: https://doi.org/10.1023/A:1007977326603