Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

In this paper, we present Brook for GPUs, a system for general-purpose computation on programmable graphics hardware. Brook extends C to include simple data-parallel constructs, enabling the use of the GPU as a streaming co-processor. We present a compiler and runtime system that abstracts and virtualizes many aspects of graphics hardware. In addition, we present an analysis of the effectiveness of the GPU as a compute engine compared to the CPU, to determine when the GPU can outperform the CPU for a particular algorithm. We evaluate our system with five applications, the SAXPY and SGEMV BLAS operators, image segmentation, FFT, and ray tracing. For these applications, we demonstrate that our Brook implementations perform comparably to hand-written GPU code and up to seven times faster than their CPU counterparts.

REFERENCES

• 1: ATI, 2004. Hardware image processing using ARB_fragment_program. http://www.ati.com/developer/sdk/RadeonSDK/Html/Samples/OpenGL/HW_Image_Processing.html.
• 2: ATI, 2004. Radeon X800 product site. http://www.ati.com/products/radeonx800.
• 3: Jeff Bolz , Ian Farmer , Eitan Grinspun , Peter Schröoder, Sparse matrix solvers on the GPU: conjugate gradients and multigrid, ACM Transactions on Graphics (TOG), v.22 n.3, July 2003 [doi>10.1145/882262.882364]
• 4: BOVE, V., AND WATLINGTON, J. 1995. Cheops: A reconfigurable data-flow system for video processing. IEEE Trans. on Circuits and Systems for Video Technology (April), 140--149.
• 5: BROOK, 2004. Brook project web page. http://brook.sourceforge.net.
• 6: BUCK, I. 2004. Brook specification v.0.2. Tech. Rep. CSTR 2003-04 10/31/03 12/5/03, Stanford University.
• 7: Nathan A. Carr , Jesse D. Hall , John C. Hart, The ray engine, Proceedings of the ACM SIGGRAPH/EUROGRAPHICS conference on Graphics hardware, September 01-02, 2002, Saarbrucken, Germany
• 8: Eric Chan , Ren Ng , Pradeep Sen , Kekoa Proudfoot , Pat Hanrahan, Efficient partitioning of fragment shaders for multipass rendering on programmable graphics hardware, Proceedings of the ACM SIGGRAPH/EUROGRAPHICS conference on Graphics hardware, September 01-02, 2002, Saarbrucken, Germany
• 9: COOLEY, J. W., AND TUKEY, J. W. 1965. An algorithm for the machine calculation of complex Fourier series. Mathematics of Computation 19 (April), 297--301.
• 10: 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
• 11: Jack J. Dongarra, Performance of Various Computers Using Standard Linear Equations Software, University of Tennessee, Knoxville, TN, 1989
• 12: Nick England, A graphics system architecture for interactive application-specific display functions, IEEE Computer Graphics and Applications, v.6 n.1, p.60-70, Jan.1986 [doi>10.1109/MCG.1986.276612]
• 13: FLISAKOWSKI, S., 2004. cTool library. http://ctool.sourceforge.net.
• 14: FRIGO, M., AND JOHNSON, S. G., 2003. benchFFT home page. http://www.fftw.org/benchfft.
• 15: 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 [doi>10.1145/74333.74341]
• 16: M. Gokhale , D. Gomersall, High level compilation for fine grained FPGAs, Proceedings of the 5th IEEE Symposium on FPGA-Based Custom Computing Machines, p.165, April 16-18, 1997
• 17: Mark J. Harris , William V. Baxter , Thorsten Scheuermann , Anselmo Lastra, Simulation of cloud dynamics on graphics hardware, Proceedings of the ACM SIGGRAPH/EUROGRAPHICS conference on Graphics hardware, July 26-27, 2003, San Diego, California
• 18: INTEL, 2003. Intel software development products. http://www.intel.com/software/products/compilers.
• 19: INTEL, 2004. Intel math kernel library. http://www.intel.com/software/products/mkl.
• 20: The Imagine Stream Processor, Proceedings of the 2002 IEEE International Conference on Computer Design: VLSI in Computers and Processors (ICCD'02), p.282, September 16-18, 2002
• 21: KESSENICH, J., BALDWIN, D., AND ROST, R., 2003. The OpenGL Shading Language. http://www.opengl.org/documentation/oglsl.html.
• 22: 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]
• 23: Christoforos Kozyrakis, A Media-Enhanced Vector Architecture for Embedded Memory Systems, University of California at Berkeley, Berkeley, CA, 1999
• 24: Jens Krüger , Rüdiger Westermann, Linear algebra operators for GPU implementation of numerical algorithms, ACM Transactions on Graphics (TOG), v.22 n.3, July 2003 [doi>10.1145/882262.882363]
• 25: LABONTE, F., HOROWITZ, M., AND BUCK, I., 2004. An evaluation of graphics processors as stream co-processors. Unpublished.
• 26: C. L. Lawson , R. J. Hanson , D. R. Kincaid , F. T. Krogh, Basic Linear Algebra Subprograms for Fortran Usage, ACM Transactions on Mathematical Software (TOMS), v.5 n.3, p.308-323, Sept. 1979 [doi>10.1145/355841.355847]
• 27: Erik Lindholm , Mark J. Kligard , Henry Moreton, A user-programmable vertex engine, Proceedings of the 28th annual conference on Computer graphics and interactive techniques, p.149-158, August 2001 [doi>10.1145/383259.383274]
• 28: William R. Mark , R. Steven Glanville , Kurt Akeley , Mark J. Kilgard, Cg: a system for programming graphics hardware in a C-like language, ACM Transactions on Graphics (TOG), v.22 n.3, July 2003 [doi>10.1145/882262.882362]
• 29: Peter Raymond Mattson , William J. Dally, A programming system for the imagine media processor, 2002
• 30: Michael D. McCool , Zheng Qin , Tiberiu S. Popa, Shader metaprogramming, Proceedings of the ACM SIGGRAPH/EUROGRAPHICS conference on Graphics hardware, September 01-02, 2002, Saarbrucken, Germany
• 31: Michael McCool , Stefanus Du Toit , Tiberiu Popa , Bryan Chan , Kevin Moule, Shader algebra, ACM Transactions on Graphics (TOG), v.23 n.3, August 2004 [doi>10.1145/1015706.1015801]
• 32: MICROSOFT, 2003. High-level shader language. http://msdn.microsoft.com/library/default.asp?url=/library/enus/directx9_c/directx/graphics/reference/Shaders/HighLevelShaderLanguage.asp.
• 33: 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 [doi>10.1145/133994.134067]
• 34: Kenneth Moreland , Edward Angel, The FFT on a GPU, Proceedings of the ACM SIGGRAPH/EUROGRAPHICS conference on Graphics hardware, July 26-27, 2003, San Diego, California
• 35: NVIDIA, 2004. GeForce 6800: Product overview. http://nvidia.com/page/geforce_6800.html.
• 36: John D. Owens , William J. Dally , Ujval J. Kapasi , Scott Rixner , Peter Mattson , Ben Mowery, Polygon rendering on a stream architecture, Proceedings of the ACM SIGGRAPH/EUROGRAPHICS workshop on Graphics hardware, p.23-32, August 21-22, 2000, Interlaken, Switzerland [doi>10.1145/346876.346883]
• 37: Mark S. Peercy , Marc Olano , John Airey , P. Jeffrey Ungar, Interactive multi-pass programmable shading, Proceedings of the 27th annual conference on Computer graphics and interactive techniques, p.425-432, July 2000 [doi>10.1145/344779.344976]
• 38: PERCY, J., 2003. OpenGL Extensions. http://mirror.ati.com/developer/SIGGRAPH03/Percy_OpenGL_Extensions_SIG03.pdf.
• 39: P. Perona , J. Malik, Scale-Space and Edge Detection Using Anisotropic Diffusion, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.12 n.7, p.629-639, July 1990 [doi>10.1109/34.56205]
• 40: Timothy J. Purcell , Ian Buck , William R. Mark , Pat Hanrahan, Ray tracing on programmable graphics hardware, ACM Transactions on Graphics (TOG), v.21 n.3, July 2002 [doi>10.1145/566654.566640]
• 41: Richard M. Russell, The CRAY-1 computer system, Communications of the ACM, v.21 n.1, p.63-72, Jan. 1978 [doi>10.1145/359327.359336]
• 42: Karthikeyan Sankaralingam , Ramadass Nagarajan , Haiming Liu , Changkyu Kim , Jaehyuk Huh , Doug Burger , Stephen W. Keckler , Charles R. Moore, Exploiting ILP, TLP, and DLP with the polymorphous TRIPS architecture, Proceedings of the 30th annual international symposium on Computer architecture, June 09-11, 2003, San Diego, California [doi>10.1145/859618.859667]
• 43: Anthony Sherbondy , Mike Houston , Sandy Napel, Fast Volume Segmentation With Simultaneous Visualization Using Programmable Graphics Hardware, Proceedings of the 14th IEEE Visualization 2003 (VIS'03), p.23, October 22-24, 2003 [doi>10.1109/VISUAL.2003.1250369]
• 44: SULLIVAN, W., WERTHIMER, D., BOWYER, S., COBB, J., GEDYE, D., AND ANDERSON, D. 1997. A new major SETI project based on Project Serendip data and 100,000 personal computers. In Astronomical and Biochemical Origins and the Search for Life in the Universe, Proceedings of the Fifth International Conference on Bioastronomy, Editrice Compositori, C. Cosmovici, S. Bowyer, and D. Wertheimer, Eds.
• 45: Michael Bedford Taylor , Jason Kim , Jason Miller , David Wentzlaff , Fae Ghodrat , Ben Greenwald , Henry Hoffman , Paul Johnson , Jae-Wook Lee , Walter Lee , Albert Ma , Arvind Saraf , Mark Seneski , Nathan Shnidman , Volker Strumpen , Matt Frank , Saman Amarasinghe , Anant Agarwal, The Raw Microprocessor: A Computational Fabric for Software Circuits and General-Purpose Programs, IEEE Micro, v.22 n.2, p.25-35, March 2002 [doi>10.1109/MM.2002.997877]
• 46: Chris J. Thompson , Sahngyun Hahn , Mark Oskin, Using modern graphics architectures for general-purpose computing: a framework and analysis, Proceedings of the 35th annual ACM/IEEE international symposium on Microarchitecture, November 18-22, 2002, Istanbul, Turkey
• 47: WALD, I. 2004. Realtime Ray Tracing and Interactive Global Illumination. PhD thesis, Saarland University.
• 48: WHALEY, R. C., PETITET, A., AND DONGARRA, J. J. 2001. Automated empirical optimizations of software and the ATLAS project. Parallel Computing 27, 1--2, 3--35.
• 49: WOO, M., NEIDER, J., DAVIS, T., SHREINER, D., AND OPENGL ARCHITECTURE REVIEW BOARD, 1999. OpenGL programming guide.

INDEX TERMS

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

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications
          Subjects: Concurrent, distributed, and parallel languages

Keywords:
Data Parallel Computing, GPU Computing, Brook, Programmable Graphics Hardware, Stream Computing