StreamRay: a stream filtering architecture for coherent ray tracing

ABSTRACT

The wide availability of commodity graphics processors has made real-time graphics an intrinsic component of the human/computer interface. These graphics cores accelerate the z-buffer algorithm and provide a highly interactive experience at a relatively low cost. However, many applications in entertainment, science, and industry require high quality lighting effects such as accurate shadows, reflection, and refraction. These effects can be difficult to achieve with z-buffer algorithms but are straightforward to implement using ray tracing. Although ray tracing is computationally more complex, the algorithm exhibits excellent scaling and parallelism properties. Nevertheless, ray tracing memory access patterns are difficult to predict and the parallelism speedup promise is therefore hard to achieve.

This paper highlights a novel approach to ray tracing based on stream filtering and presents StreamRay, a multicore wide SIMD microarchitecture that delivers interactive frame rates of 15-32 frames/second for scenes of high geometric complexity and exhibits high utilization for SIMD widths ranging from eight to 16 elements. StreamRay consists of two main components: the ray engine, which is responsible for stream assembly and employs address generation units that generate addresses to form large SIMD vectors, and the filter engine, which implements the ray tracing operations with programmable accelerators. Results demonstrate that separating address and data processing reduces data movement and resource contention. Performance improves by 56% while simultaneously providing 11.63% power savings per accelerator core compared to a design which does not use separate resources for address and data computations.

REFERENCES

• 1: ATI. ATI products from AMD. http://ati.amd.com/products/index.html.
• 2: C. Benthin. Realtime Ray Tracing on Current CPU Architectures. PhD thesis, Saarland University, 2006.
• 3: Solomon Boulos , Dave Edwards , J. Dylan Lacewell , Joe Kniss , Jan Kautz , Peter Shirley , Ingo Wald, Packet-based whitted and distribution ray tracing, Proceedings of Graphics Interface 2007, May 28-30, 2007, Montreal, Canada [doi>10.1145/1268517.1268547]
• 4: S. Boulos, I. Wald, and P. Shirley. Geometric and arithmetic culling methods for entire ray packets. Technical Report UUCS-06-10, University of Utah, 2006.
• 5: David Brooks , Vivek Tiwari , Margaret Martonosi, Wattch: a framework for architectural-level power analysis and optimizations, Proceedings of the 27th annual international symposium on Computer architecture, p.83-94, June 2000, Vancouver, British Columbia, Canada
• 6: D. Burger and T. M. Austin. The simplescalar toolset, version 2.0. Technical Report TR-97-1342, University of Wisconsin-Madison, June 1997.
• 7: Edwin Earl Catmull, A subdivision algorithm for computer display of curved surfaces., The University of Utah, 1974
• 8: J. Cleary, B. Wyvill, G. Birtwistle, and R. Vatti. A parallel ray tracing computer. In Proceedings of the Association of Simulat Users Conference, pages 77--80, 1983.
• 9: William J. Dally , Francois Labonte , Abhishek Das , Patrick Hanrahan , Jung-Ho Ahn , Jayanth Gummaraju , Mattan Erez , Nuwan Jayasena , Ian Buck , Timothy J. Knight , Ujval J. Kapasi, Merrimac: Supercomputing with Streams, Proceedings of the 2003 ACM/IEEE conference on Supercomputing, p.35, November 15-21, 2003
• 10: M. Ernst and G. Greiner. Multi bounding volume hierarchies. In 2008 IEEE/Eurographics Symposium on Interactive Ray Tracing, pages 35--40.
• 11: C. P. Gribble and K. Ramani. Coherent ray tracing via stream filtering. In 2008 IEEE/Eurographics Symposium on Interactive Ray Tracing, pages 59--66, August 2008.
• 12: P Hanrahan, Using caching and breadth-first search to speed up ray-tracing, Proceedings on Graphics Interface '86/Vision Interface '86, p.56-61, August 1986, Vancouver, British Columbia, Canada
• 13: James T. Kajiya, The rendering equation, Proceedings of the 13th annual conference on Computer graphics and interactive techniques, p.143-150, August 1986
• 14: Brucek Khailany , William J. Dally , Ujval J. Kapasi , Peter Mattson , Jinyung Namkoong , John D. Owens , Brian Towles , Andrew Chang , Scott Rixner, Imagine: Media Processing with Streams, IEEE Micro, v.21 n.2, p.35-46, March 2001 [doi>10.1109/40.918001]
• 15: J. Mahovsky and B. Wyvill. Memory-conserving bounding volume hierarchies with coherent raytracing. Computer Graphics Forum, 25(2):173--182, 2006.
• 16: E. Mansson, J. Munkberg, and T. Akenine-Moller. Deep coherent ray tracing. In 2007 IEEE Symposium on Interactive Ray Tracing, pages 79--85, September 2007.
• 17: Binu Mathew , Al Davis , Mike Parker, A low power architecture for embedded perception, Proceedings of the 2004 international conference on Compilers, architecture, and synthesis for embedded systems, September 22-25, 2004, Washington DC, USA [doi>10.1145/1023833.1023842]
• 18: Koji Nakamaru , Yoshio Ohno, Breadth-First Ray Tracing Utilizing Uniform Spatial Subdivision, IEEE Transactions on Visualization and Computer Graphics, v.3 n.4, p.316-328, October 1997 [doi>10.1109/2945.646235]
• 19: P. Navratil, D. Fussell, C. Lin, and W. R. Mark. Dynamic ray scheduling for improved system performance. In 2007 IEEE Symposium on Interactive Ray Tracing, pages 95--104, September 2007.
• 20: NVIDIA. NVIDIA GeForce 8800 GPU Architectural Overview. November 2006.
• 21: Steven Parker , William Martin , Peter-Pike J. Sloan , Peter Shirley , Brian Smits , Charles Hansen, Interactive ray tracing, Proceedings of the 1999 symposium on Interactive 3D graphics, p.119-126, April 26-29, 1999, Atlanta, Georgia, United States [doi>10.1145/300523.300537]
• 22: Matt Pharr , Craig Kolb , Reid Gershbein , Pat Hanrahan, Rendering complex scenes with memory-coherent ray tracing, Proceedings of the 24th annual conference on Computer graphics and interactive techniques, p.101-108, August 1997 [doi>10.1145/258734.258791]
• 23: Karthik Ramani , Al Davis, Application driven embedded system design: a face recognition case study, Proceedings of the 2007 international conference on Compilers, architecture, and synthesis for embedded systems, September 30-October 03, 2007, Salzburg, Austria [doi>10.1145/1289881.1289902]
• 24: K. Ramani and A. Davis. Automating the Design of Embedded Domain Specific Accelerators. Technical report, University of Utah, 2008.
• 25: K. Ramani, A. Ibrahim, and D. Shimizu. PowerRed: A Flexible Modeling Framework for Power Efficiency Exploration in GPUs. In Proceedings of the Workshop on General Purpose Processing on GPUs, GPGPU'07.
• 26: A. Reshetov. Omnidirectional ray tracing traversal algorithm for kd-trees. In 2006 IEEE Symposium on Interactive Ray Tracing, pages 57--60, September 2006.
• 27: Alexander Reshetov, Faster ray packets - triangle intersection through vertex culling, ACM SIGGRAPH 2007 posters, August 05-09, 2007, San Diego, California [doi>10.1145/1280720.1280906]
• 28: Alexander Reshetov , Alexei Soupikov , Jim Hurley, Multi-level ray tracing algorithm, ACM Transactions on Graphics (TOG), v.24 n.3, July 2005
• 29: Jörg Schmittler , Ingo Wald , Philipp Slusallek, SaarCOR: a hardware architecture for ray tracing, Proceedings of the ACM SIGGRAPH/EUROGRAPHICS conference on Graphics hardware, September 01-02, 2002, Saarbrucken, Germany
• 30: Larry Seiler , Doug Carmean , Eric Sprangle , Tom Forsyth , Michael Abrash , Pradeep Dubey , Stephen Junkins , Adam Lake , Jeremy Sugerman , Robert Cavin , Roger Espasa , Ed Grochowski , Toni Juan , Pat Hanrahan, Larrabee: a many-core x86 architecture for visual computing, ACM Transactions on Graphics (TOG), v.27 n.3, August 2008
• 31: I. Wald, C. Benthin, and S. Boulos. Getting rid of packets -- efficient simd single-ray traversal using multi-branching bvhs. In 2008 IEEE/Eurographics Symposium on Interactive Ray Tracing, pages 49--57, August 2008.
• 32: I. Wald, C. Benthin, M. Wagner, and P. Slusallek. Interactive rendering with coherent ray tracing. Computer Graphics Forum, 20(3):153--164, September 2001.
• 33: Ingo Wald , Solomon Boulos , Peter Shirley, Ray tracing deformable scenes using dynamic bounding volume hierarchies, ACM Transactions on Graphics (TOG), v.26 n.1, p.6-es, January 2007 [doi>10.1145/1189762.1206075]
• 34: Turner Whitted, An improved illumination model for shaded display, Communications of the ACM, v.23 n.6, p.343-349, June 1980 [doi>10.1145/358876.358882]
• 35: Sven Woop , Jörg Schmittler , Philipp Slusallek, RPU: a programmable ray processing unit for realtime ray tracing, ACM Transactions on Graphics (TOG), v.24 n.3, July 2005

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.1 Hardware architecture
          Subjects: Graphics processors

Additional Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.2 Multiple Data Stream Architectures (Multiprocessors)
          Subjects: Multiple-instruction-stream, multiple-data-stream processors (MIMD)

General Terms:
Algorithms, Design, Performance

Keywords:
graphics processors, interactive rendering, ray tracing, wide simd architectures