Hybrid scheduling for parallel rendering using coherent ray tasks

ABSTRACT

Parallelising ray tracing with a data parallel approach allows rendering of arbitrarily large models, but the inherent load imbalances may lead to severe inefficiencies. To compensate for the uneven load distribution, demand-driven tasks may be split off and scheduled to processors that are less busy. We propose a hybrid scheduling algorithm which brings tasks and data together according to coherence between rays. The amount of demand-driven versus data-parallel tasks is a function of the coherence between rays and the amount of imbalance in the basic data-parallel load. Processing power, communication and memory are three resources which should be evenly used. Our current implementation is assessed against these requirements, showing good scalability and very little communication at the cost of a slightly larger memory overhead.

REFERENCES

• 1: Didier Badouel , Kadi Bouatouch , Thierry Priol, Distributing Data and Control for Ray Tracing in Parallel, IEEE Computer Graphics and Applications, v.14 n.4, p.69-77, July 1994 [doi>10.1109/38.291533]
• 2: A. Chalmers and E. Reinhard. Parallel and Distributed Photo- Realistic Rendering. ACM Siggraph, July 1998. Course notes for SIGGRAPH 98.
• 3: J G Cleary , B M Wyvill , G M Birtwistle , R Vatti, Multiprocessor ray tracing, Computer Graphics Forum, v.5 n.1, p.3-12, March 1986 [doi>10.1111/j.1467-8659.1986.tb00263.x]
• 4: Thomas W. Crockett, An introduction to parallel rendering, Parallel Computing, v.23 n.7, p.819-843, July 1997 [doi>10.1016/S0167-8191(97)00028-8]
• 5: F.C. Crow, G. Demos, J. Hardy, J. McLaugglin, and K. Sims. 3d image synthesis on the connection machine. In Proceedings Parallel Processing for Computer Vision and Display, Leeds, 1988.
• 6: Mark Dippé , John Swensen, An adaptive subdivision algorithm and parallel architecture for realistic image synthesis, Proceedings of the 11th annual conference on Computer graphics and interactive techniques, p.149-158, January 1984
• 7: A. Geist, A. Beguelin, J. Dongarra, W. Jiang, R. Manchek, and V. Sunderam. PVM 3 User's Guide and Reference Manual. Oak Ridge National Laboratory, Oak Ridge, Tennessee, May 1993. Included with the PVM 3 distribution.
• 8: S. A. Green , D. J. Paddon, Exploiting Coherence for Multiprocessor Ray Tracing, IEEE Computer Graphics and Applications, v.9 n.6, p.12-26, November 1989 [doi>10.1109/38.41466]
• 9: A. G. Hoekstra, E M. A. Sloot, F. van der Linden, M. van Muiswinkel, and J. J. J. Vesseur. Native and generic parallel programming environments on a transputer and a PowerPC platform. Concurrency: Practice and Experience, 8(1): 19-46, January-February 1996.
• 10: F.W. Jansen and A. Chalmers. Realism in real time? In M. F. Cohen, C. Puech, and F. Sillion, editors, 4th EG Workshop on Rendering, pages 27-46. Eurographics, June 1993. held in Paris, France, 14-16 June 1993.
• 11: H. Kobayashi, S. Nishimura, H. Kubota, T. Nakamura, and Y. Shigei. Load balancing strategies for a parallel ray-tracing system based on constant subdivision. The Visual Computer, 4(4):197-209, 1988.
• 12: Wilfrid Lefer, An efficient parallel ray tracing scheme for distributed memory parallel computers, Proceedings of the 1993 symposium on Parallel rendering, p.77-80, October 25-26, 1993, San Jose, California, United States [doi>10.1145/166181.166193]
• 13: Tony T. Y. Lin , Mel Slater, Stochastic ray tracing using SIMD processor arrays, The Visual Computer: International Journal of Computer Graphics, v.7 n.4, p.187-199, July 1991 [doi>10.1007/BF01900835]
• 14: Erik Reinhard , Alan Chalmers, Message Handling in Parallel Radiance, Proceedings of the 4th European PVM/MPI Users' Group Meeting on Recent Advances in Parallel Virtual Machine and Message Passing Interface, p.486-493, November 03-05, 1997
• 15: Erik Reinhard , Alan Chalmers , Frederik W. Jansen, Overview of Parallel Photo-realistic Graphics, University of Bristol, Bristol, UK, 1998
• 16: Erik Reinhard , Frederik W. Jansen, Rendering large scenes using parallel ray tracing, Parallel Computing, v.23 n.7, p.873-885, July 1997 [doi>10.1016/S0167-8191(97)00031-8]
• 17: E. Reinhard, A. J. F. Kok, and A. G. Chalmers. Cost distribution prediction for parallel ray tracing. In K. Bouatouch, A. Chalmers, and T. Priol, editors, Proceedings of the Second International Workshop on Parallel Graphics and Visualisation, pages 77-90, September 1998.
• 18: I.D. Scherson and C. Caspary. Multiprocessing for ray tracing: A hierarchical self-balancing approach. The Visual Computer, 4(4):188-196, 1988.
• 19: G.J. Ward. Adaptive shadow testing for ray tracing. In Photorealistic Rendering in Computer Graphics (Proceedings of the Second Eurographics Workshop on Rendering), pages 11- 20, New York, 1994. Springer-Verlag.
• 20: Gregory J. Ward, The RADIANCE lighting simulation and rendering system, Proceedings of the 21st annual conference on Computer graphics and interactive techniques, p.459-472, July 1994 [doi>10.1145/192161.192286]
• 21: Gregory J. Ward , Francis M. Rubinstein , Robert D. Clear, A ray tracing solution for diffuse interreflection, ACM SIGGRAPH Computer Graphics, v.22 n.4, p.85-92, Aug. 1988
• 22: M. van der Zwaan, E. Reinhard, and F. W. Jansen. Pyramid clipping for efficient ray traversal. In E Hanrahan and W. Purgathofer, editors, Rendering Techniques '95, pages 1- 10. Springer - Vienna, June 1995.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.7 Three-Dimensional Graphics and Realism
          Subjects: Raytracing

Additional Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES

General Terms:
Experimentation, Management

Keywords:
hybrid scheduling, parallel computing, ray tracing