BSGP: bulk-synchronous GPU programming

ABSTRACT

We present BSGP, a new programming language for general purpose computation on the GPU. A BSGP program looks much the same as a sequential C program. Programmers only need to supply a bare minimum of extra information to describe parallel processing on GPUs. As a result, BSGP programs are easy to read, write, and maintain. Moreover, the ease of programming does not come at the cost of performance. A well-designed BSGP compiler converts BSGP programs to kernels and combines them using optimally allocated temporary streams. In our benchmark, BSGP programs achieve similar or better performance than well-optimized CUDA programs, while the source code complexity and programming time are significantly reduced. To test BSGP's code efficiency and ease of programming, we implemented a variety of GPU applications, including a highly sophisticated X3D parser that would be extremely difficult to develop with existing GPU programming languages.

REFERENCES

• 1: ARTIS, 2004. X3DToolKit homepage. http://artis.imag.fr/Software/X3D/.
• 2: ATI, 2006. Researcher CTM documentation. http://ati.amd.com/companyinfo/researcher/documents.html.
• 3: Ian Buck , Tim Foley , Daniel Horn , Jeremy Sugerman , Kayvon Fatahalian , Mike Houston , Pat Hanrahan, Brook for GPUs: stream computing on graphics hardware, ACM Transactions on Graphics (TOG), v.23 n.3, August 2004
• 4: Ron Cytron , Jeanne Ferrante , Barry K. Rosen , Mark N. Wegman , F. Kenneth Zadeck, Efficiently computing static single assignment form and the control dependence graph, ACM Transactions on Programming Languages and Systems (TOPLAS), v.13 n.4, p.451-490, Oct. 1991 [doi>10.1145/115372.115320]
• 5: Tim Foley , Jeremy Sugerman, KD-tree acceleration structures for a GPU raytracer, Proceedings of the ACM SIGGRAPH/EUROGRAPHICS conference on Graphics hardware, July 30-31, 2005, Los Angeles, California [doi>10.1145/1071866.1071869]
• 6: Ford, L. R., and Fulkerson, D. R. 1962. Flows in Networks. Princeton University Press.
• 7: Steven Fortune , James Wyllie, Parallelism in random access machines, Proceedings of the tenth annual ACM symposium on Theory of computing, p.114-118, May 01-03, 1978, San Diego, California, United States [doi>10.1145/800133.804339]
• 8: Gress, A., and Zachmann, G. 2006. GPU-ABiSort: optimal parallel sorting on stream architectures. In Parallel and Distributed Processing Symposium, 45--54.
• 9: Harris, M., Owens, J., Sengupta, S., Zhang, Y., and Davidson, A., 2007. CUDPP homepage. http://www.gpgpu.org/developer/cudpp/.
• 10: Jonathan M. D. Hill , Bill McColl , Dan C. Stefanescu , Mark W. Goudreau , Kevin Lang , Satish B. Rao , Torsten Suel , Thanasis Tsantilas , Rob H. Bisseling, BSPlib: The BSP programming library, Parallel Computing, v.24 n.14, p.1947-1980, Dec. 1998 [doi>10.1016/S0167-8191(98)00093-3]
• 11: Daniel Reiter Horn , Jeremy Sugerman , Mike Houston , Pat Hanrahan, Interactive k-d tree GPU raytracing, Proceedings of the 2007 symposium on Interactive 3D graphics and games, April 30-May 02, 2007, Seattle, Washington [doi>10.1145/1230100.1230129]
• 12: Laxmikant V. Kale , Sanjeev Krishnan, CHARM++: a portable concurrent object oriented system based on C++, ACM SIGPLAN Notices, v.28 n.10, p.91-108, Oct. 1, 1993
• 13: William R. Mark , R. Steven Glanville , Kurt Akeley , Mark J. Kilgard, Cg: a system for programming graphics hardware in a C-like language, ACM SIGGRAPH 2003 Papers, July 27-31, 2003, San Diego, California
• 14: Michael McCool , Stefanus Du Toit, Metaprogramming GPUs with Sh, AK Peters Ltd, 2004
• 15: 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
• 16: Michael McCool , Stefanus Du Toit , Tiberiu Popa , Bryan Chan , Kevin Moule, Shader algebra, ACM Transactions on Graphics (TOG), v.23 n.3, August 2004
• 17: Henry Moreton, Watertight tessellation using forward differencing, Proceedings of the ACM SIGGRAPH/EUROGRAPHICS workshop on Graphics hardware, p.25-32, August 2001, Los Angeles, California, United States [doi>10.1145/383507.383520]
• 18: NVIDIA, 2007. CUDA homepage. http://developer.nvidia.com/object/cuda.html.
• 19: Marc Olano , Anselmo Lastra, A shading language on graphics hardware: the pixelflow shading system, Proceedings of the 25th annual conference on Computer graphics and interactive techniques, p.159-168, July 1998 [doi>10.1145/280814.280857]
• 20: Tony Parisi, Flux: lightweight, standards-based Web graphics in XML, ACM SIGGRAPH 2003 Web Graphics, July 27-31, 2003, San Diego, California [doi>10.1145/965333.965338]
• 21: 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]
• 22: Popov, S., Günther, J., Seidel, H.-P., and Slusallek, P. 2007. Stackless kd-tree traversal for high performance gpu ray tracing. In Proceedings of Eurographics'07, 415--424.
• 23: Kekoa Proudfoot , William R. Mark , Svetoslav Tzvetkov , Pat Hanrahan, A real-time procedural shading system for programmable graphics hardware, Proceedings of the 28th annual conference on Computer graphics and interactive techniques, p.159-170, August 2001 [doi>10.1145/383259.383275]
• 24: Shubhabrata Sengupta , Mark Harris , Yao Zhang , John D. Owens, Scan primitives for GPU computing, Proceedings of the 22nd ACM SIGGRAPH/EUROGRAPHICS symposium on Graphics hardware, August 04-05, 2007, San Diego, California
• 25: Skillicorn, D. B., Hill, J. M. D., and McColl, W. F. 1997. Questions and Answers about BSP. Scientific Programming 6, 3, 249--274.
• 26: David Tarditi , Sidd Puri , Jose Oglesby, Accelerator: using data parallelism to program GPUs for general-purpose uses, Proceedings of the 12th international conference on Architectural support for programming languages and operating systems, October 21-25, 2006, San Jose, California, USA
• 27: Leslie G. Valiant, A bridging model for parallel computation, Communications of the ACM, v.33 n.8, p.103-111, Aug. 1990 [doi>10.1145/79173.79181]
• 28: Mark N. Wegman , F. Kenneth Zadeck, Constant propagation with conditional branches, ACM Transactions on Programming Languages and Systems (TOPLAS), v.13 n.2, p.181-210, April 1991 [doi>10.1145/103135.103136]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.6 Methodology and Techniques
          Subjects: Languages

Additional Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.3 Concurrent Programming
          Subjects: Parallel programming
  D.3 PROGRAMMING LANGUAGES
      D.3.2 Language Classifications
          Subjects: Specialized application languages

  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.1 Hardware architecture
          Subjects: Parallel processing
      I.3.4 Graphics Utilities
          Subjects: Software support

General Terms:
Design, Languages, Theory

Keywords:
bulk synchronous parallel programming, programable graphics hardware, stream processing, thread manipulation