“Brook for GPUs: stream computing on graphics hardware” by Buck, Foley, Horn, Sugerman, Fatahalian, et al. …

  • ©Ian Buck, Tim Foley, Daniel Horn, Jeremy Sugerman, Kayvon Fatahalian, Michael (Mike) Houston, and Patrick (Pat) Hanrahan




    Brook for GPUs: stream computing on graphics hardware



    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.


    1. ATI, 2004. Hardware image processing using ARB_fragment_program. http://www.ati.com/developer/sdk/RadeonSDK/Html/Samples/OpenGL/HW_Image_Processing.html.Google Scholar
    2. ATI, 2004. Radeon X800 product site. http://www.ati.com/products/radeonx800.Google Scholar
    3. BOLZ, J., FARMER, I., GRINSPUN, E., ANDSCHRÖDER, P. 2003. Sparse matrix solvers on the GPU: conjugate gradients and multigrid. ACM Trans. Graph. 22, 3, 917–924. Google ScholarDigital Library
    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. Google ScholarDigital Library
    5. BROOK, 2004. Brook project web page. http://brook.sourceforge.net.Google Scholar
    6. BUCK, I. 2004. Brook specification v.0.2. Tech. Rep. CSTR 2003-04 10/31/03 12/5/03, Stanford University.Google Scholar
    7. CARR, N. A., HALL, J. D., AND HART, J. C. 2002. The Ray Engine. In Proceedings of Graphics hardware, Eurographics Association, 37–46. Google ScholarDigital Library
    8. CHAN, E., NG, R., SEN, P., PROUDFOOT, K., AND HANRAHAN, P. 2002. Efficient partitioning of fragment shaders for multipass rendering on programmable graphics hardware. In Proceedings of Graphics hardware, Eurographics Association, 69–78. Google ScholarDigital Library
    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.Google ScholarCross Ref
    10. DALLY, W. J., HANRAHAN, P., EREZ, M., KNIGHT, T. J., LABONT, F., AHN, J.-H., JAYASENA, N., KAPASI, U. J., DAS, A., GUMMARAJU, J., AND BUCK, I. 2003. Merrimac: Supercomputing with Streams. In Proceedings of SC2003, ACM Press. Google ScholarDigital Library
    11. DONGARRA, J. 2004. Performance of various computers using standard linear equations software. Tech. Rep. CS-89-85, University of Tennessee, Knoxville TN. Google ScholarDigital Library
    12. ENGLAND, N. 1986. A graphics system architecture for interactive application-specific display functions. In IEEE CGA, 60–70. Google ScholarDigital Library
    13. FLISAKOWSKI, S., 2004. cTool library. http://ctool.sourceforge.net.Google Scholar
    14. FRIGO, M., AND JOHNSON, S. G., 2003. benchFFT home page. http://www.fftw.org/benchfft.Google Scholar
    15. FUCHS, H., POULTON, J., EYLES, J., GREER, T., GOLDFEATHER, J., ELLSWORTH, D., MOLNAR, S., TURK, G., TEBBS, B., AND ISRAEL, L. 1989. Pixel-Planes 5: a heterogeneous multiprocessor graphics system using processor-enhanced memories. In Computer Graphics (Proceedings of ACM SIGGRAPH 89), ACM Press, 79–88. Google ScholarDigital Library
    16. GOKHALE, M., AND GOMERSALL, E. 1997. High level compilation for fine grained fpgas. In Proceedings of IEEE Workshop on FPGAs for Custom Computing Machines, 165–173. Google ScholarDigital Library
    17. HARRIS, M. J., BAXTER, W. V., SCHEUERMANN, T., AND LASTRA, A. 2003. Simulation of cloud dynamics on graphics hardware. In Proceedings of Graphics hardware, Eurographics Association, 92–101. Google ScholarDigital Library
    18. INTEL, 2003. Intel software development products. http://www.intel.com/software/products/compilers.Google Scholar
    19. INTEL, 2004. Intel math kernel library. http://www.intel.com/software/products/mkl.Google Scholar
    20. KAPASI, U., DALLY, W. J., RIXNER, S., OWENS, J. D., AND KHAILANY, B. 2002. The Imagine Stream Processor. Proceedings of International Conference on Computer Design (September). Google ScholarDigital Library
    21. KESSENICH, J., BALDWIN, D., AND ROST, R., 2003. The OpenGL Shading Language. http://www.opengl.org/documentation/oglsl.html.Google Scholar
    22. KHAILANY, B., DALLY, W. J., RIXNER, S., KAPASI, U. J., MATTSON, P., NAMKOONG, J., OWENS, J. D., TOWLES, B., AND CHAN, A. 2001. IMAGINE: Media processing with streams. In IEEE Micro. IEEE Computer Society Press. Google ScholarDigital Library
    23. KOZYRAKIS, C. 1999. A media-enhance vector architecture for embedded memory systems. Tech. Rep. UCB/CSD-99-1059, Univ. of California at Berkeley. Google ScholarDigital Library
    24. KRÜGER, J., AND WESTERMANN, R. 2003. Linear algebra operators for GPU implementation of numerical algorithms. ACM Trans. Graph. 22, 3, 908–916. Google ScholarDigital Library
    25. LABONTE, F., HOROWITZ, M., AND BUCK, I., 2004. An evaluation of graphics processors as stream co-processors. Unpublished.Google Scholar
    26. LAWSON, C. L., HANSON, R. J., KINCAID, D. R., AND KROGH, F. T. 1979. Basic Linear Algebra Subprograms for Fortran usage. ACM Trans. on Mathematical Software 5, 3 (Sept.), 308–323. Google ScholarDigital Library
    27. LINDHOLM, E., KLIGARD, M. J., AND MORETON, H. 2001. A user-programmable vertex engine. In Proceedings of SIGGRAPH 2001, ACM Press/Addison-Wesley Publishing Co., 149–158. Google ScholarDigital Library
    28. MARK, W. R., GLANVILLE, R. S., AKELEY, K., AND KILGARD, M. J. 2003. Cg: A system for programming graphics hardware in a C-like language. ACM Trans. Graph. 22, 3, 896–907. Google ScholarDigital Library
    29. MATTSON, P. 2002. A Programming System for the Imagine Media Processor. PhD thesis, Stanford University. Google ScholarDigital Library
    30. MCCOOL, M. D., QIN, Z., AND POPA, T. S. 2002. Shader metaprogramming. In Proceedings of Graphics hardware, Eurographics Association, 57–68. Google ScholarDigital Library
    31. McCOOL, M., DU TOIT, S., POPA, T., CHAN, B., AND MOULE, K. 2004. Shader algebra. ACM Trans. Graph. Google ScholarDigital Library
    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.Google Scholar
    33. MOLNAR, S., EYLES, J., AND POULTON, J. 1992. PixelFlow: High-speed rendering using image composition. In Proceedings of ACM SIGGRAPH 92, ACM Press, 231–240. Google ScholarDigital Library
    34. MORELAND, K., AND ANGEL, E. 2003. The FFT on a GPU. In Proceedings of Graphics hardware, Eurographics Association, 112–119. Google ScholarDigital Library
    35. NVIDIA, 2004. GeForce 6800: Product overview. http://nvidia.com/page/geforce_6800.html.Google Scholar
    36. OWENS, J. D., DALLY, W. J., KAPASI, U. J., RIXNER, S., MATTSON, P., AND MOWERY, B. 2000. Polygon rendering on a stream architecture. In Proceedings of Graphics hardware, ACM Press, 23–32. Google ScholarDigital Library
    37. PEERCY, M. S., OLANO, M., AIREY, J., AND UNGAR, P. J. 2000. Interactive multi-pass programmable shading. In Proceedings of ACM SIGGRAPH 2000, ACM Press/Addison-Wesley Publishing Co., 425–432. Google ScholarDigital Library
    38. PERCY, J., 2003. OpenGL Extensions. http://mirror.ati.com/developer/SIGGRAPH03/Percy_OpenGL_Extensions_SIG03.pdf.Google Scholar
    39. PERONA, P., AND MALIK, J. 1990. Scale-space And Edge Detection Using Anisotropic Diffusion. IEEE Trans. on Pattern Analysis and Machine Intelligence 12, 7 (June), 629–639. Google ScholarDigital Library
    40. PURCELL, T. J., BUCK, I., MARK, W. R., AND HANRAHAN, P. 2002. Ray tracing on programmable graphics hardware. ACM Trans. Graph., 703–712. Google ScholarDigital Library
    41. RUSSELL, R. 1978. The Cray-1 computer system. In Comm. ACM, 63–72. Google ScholarDigital Library
    42. SANKARALINGAM, K., NAGARAJAN, R., LIU, H., HUH, J., KIM, C., D. BURGER, KECKLER, S., AND MOORE, C. 2003. Exploiting ILP, TLP, and DLP using polymorphism in the TRIPS architecture. In 30th Annual International Symposium on Computer Architecture (ISCA), 422–433. Google ScholarDigital Library
    43. SHERBONDY, A., HOUSTON, M., AND NAPEL, S. 2003. Fast volume segmentation with simultaneous visualization using programmable graphics hardware. IEEE Visualization. Google ScholarDigital Library
    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.Google Scholar
    45. TAYLOR, M. B., KIM, J., MILLER, J., WENTZLAFF, D., GHODRAT, F., GREENWALD, B., HOFFMANN, H., JOHNSON, P., LEE, J.-W., LEE, W., MA, A., SARAF, A., SENESKI, M., SHNIDMAN, N., STRUMPEN, V., FRANK, M., AMARASINGHE, S., AND AGARWAL, A. 2002. The raw microprocessor: A computational fabric for software circuits and general purpose programs. In IEEE Micro. Google ScholarDigital Library
    46. THOMPSON, C. J., HAHN, S., AND OSKIN, M. 2002. Using modern graphics architectures for general-purpose computing: A framework and analysis. International Symposium on Microarchitecture. Google ScholarDigital Library
    47. WALD, I. 2004. Realtime Ray Tracing and Interactive Global Illumination. PhD thesis, Saarland University.Google Scholar
    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.Google ScholarCross Ref
    49. WOO, M., NEIDER, J., DAVIS, T., SHREINER, D., AND OPENGL ARCHITECTURE REVIEW BOARD, 1999. OpenGL programming guide.Google Scholar

ACM Digital Library Publication: