The sort-first rendering architecture for high-performance graphics

ABSTRACT

Interactive graphics applications have long been challenging graphics system designers by demanding machines that can provide ever increasing polygon rendering performance. Another trend in interactive graphics is the growing use of display devices with pixel counts well beyond what is usually considered “high-resolution.” If we examine the architectural space of high-performance rendering systems, we discover only one architectural class that promises to deliver high polygon performance with very-high-resolution displays and do so in an efficient manner. It is known as “sort-first.”We investigate the sort-first architecture, starting with a comparison to its architectural class mates (sort-middle and sort-last). We find that sort-first has an inherent ability to take advantage of the frame-to-frame coherence found in interactive applications. We examine this ability through simulation with a set of test applications and show how it reduces sort-first's communication needs and therefore its parallel overhead. We also explore the issue of load-balancing with sort-first and introduce a new adaptive algorithm to solve this problem. Additional simulations demonstrate the effectiveness of this algorithm. Finally, we touch on a variety of issues that must be resolved in order to fulfill sort-first's ultimate promise: millions of polygons for zillions of pixels.

REFERENCES

• 1: Kurt Akeley, Reality Engine graphics, Proceedings of the 20th annual conference on Computer graphics and interactive techniques, p.109-116, September 1993 [doi>10.1145/166117.166131]
• 2: James H. Clark, Hierarchical geometric models for visible surface algorithms, Communications of the ACM, v.19 n.10, p.547-554, Oct. 1976 [doi>10.1145/360349.360354]
• 3: Thomas W. Crockett , Tobias Orloff, A MIMD rendering algorithm for distributed memory architectures, Proceedings of the 1993 symposium on Parallel rendering, p.35-42, October 25-26, 1993, San Jose, California, United States [doi>10.1145/166181.166186]
• 4: Franklin C. Crow, Summed-area tables for texture mapping, Proceedings of the 11th annual conference on Computer graphics and interactive techniques, p.207-212, January 1984
• 5: Carolina Cruz-Neira , Daniel J. Sandin , Thomas A. DeFanti, Surround-screen projection-based virtual reality: the design and implementation of the CAVE, Proceedings of the 20th annual conference on Computer graphics and interactive techniques, p.135-142, September 1993 [doi>10.1145/166117.166134]
• 6: Michael F. Deering , Scott R. Nelson, Leo: a system for cost effective 3D shaded graphics, Proceedings of the 20th annual conference on Computer graphics and interactive techniques, p.101-108, September 1993 [doi>10.1145/166117.166130]
• 7: DeFoe. Douglas, Kaiser Electra-Optics, Inc., WWW URL http://esto.sysplan.com/ESTO/Displays/HMD-TDS/ Fact:sheets/Immersion.html.
• 8: David Ellsworth , Howard Good , Brice Tebbs, Distributing display lists on a multicomputer, Proceedings of the 1990 symposium on Interactive 3D graphics, p.147-154, February 1990, Snowbird, Utah, United States
• 9: David A. Ellsworth, A New Algorithm for Interactive Graphics on Multicomputers, IEEE Computer Graphics and Applications, v.14 n.4, p.33-40, July 1994 [doi>10.1109/38.291529]
• 10: James D. Foley , Andries van Dam , Steven K. Feiner , John F. Hughes, Computer graphics: principles and practice (2nd ed.), Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1990
• 11: Henry Fuchs , John Poulton , John Eyles , Trey Greer , Jack Goldfeather , David Ellsworth , Steve Molnar , Greg Turk , Brice Tebbs , Laura Israel, Pixel-planes 5: a heterogeneous multiprocessor graphics system using processor-enhanced memories, Proceedings of the 16th annual conference on Computer graphics and interactive techniques, p.79-88, July 1989
• 12: LaCroix, Michel and James Melzer. Helmet-Mou.nted Displays for Flight Simulators. Proceedings of the 1994 Image WI Conference, June I994. pp. 34-40.
• 13: Steven Edward Molnar, Image-composition architectures for real-time image generation, University of North Carolina at Chapel Hill, Chapel Hill, NC, 1992
• 14: Steven Molnar , John Eyles , John Poulton, PixelFlow: high-speed rendering using image composition, Proceedings of the 19th annual conference on Computer graphics and interactive techniques, p.231-240, July 1992
• 15: Steven Molnar , Michael Cox , David Ellsworth , Henry Fuchs, A Sorting Classification of Parallel Rendering, IEEE Computer Graphics and Applications, v.14 n.4, p.23-32, July 1994 [doi>10.1109/38.291528]
• 16: National Computer Graphics Association Picture-Level Benchmark, GPC Quarterly Reporl2.4 (1992).
• 17: Roble, Douglas. A Load Balanced Parallel Scanline Z- Buffer Algorithm for the iPSC Hypercube. Proceedings of Pixim '88. Paris, France, October 1988, pp. 177-192.
• 18: Ivan E. Sutherland , Robert F. Sproull , Robert A. Schumacker, A Characterization of Ten Hidden-Surface Algorithms, ACM Computing Surveys (CSUR), v.6 n.1, p.1-55, March 1974 [doi>10.1145/356625.356626]
• 19: Daniel S. Whelan, Animac: a multiprocessor architecture for real-time computer animation (graphics, shadows, vlsi), 1985
• 20: Scott Whitman, Multiprocessor methods for computer graphics rendering, A. K. Peters, Ltd., Natick, MA, 1992
• 21: Scott Whitman, Dynamic Load Balancing for Parallel Polygon Rendering, IEEE Computer Graphics and Applications, v.14 n.4, p.41-48, July 1994 [doi>10.1109/38.291530]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.1 Hardware architecture
          Subjects: Parallel processing

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sorting and searching

  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.1 Hardware architecture
          Subjects: Raster display devices

General Terms:
Algorithms, Performance