General-purpose computing on graphics processing units

From Wikipedia, the free encyclopedia
  (Redirected from Gpgpu)
Jump to: navigation, search

General-purpose computing on graphics processing units (GPGPU, rarely GPGP or GP²U) is the utilization of a graphics processing unit (GPU), which typically handles computation only for computer graphics, to perform computation in applications traditionally handled by the central processing unit (CPU).[1][2][3]

Any GPU providing a functionally complete set of operations performed on arbitrary bits can compute any computable value. Additionally, the use of multiple graphics cards in one computer, or large numbers of graphics chips, further parallelizes the already parallel nature of graphics processing.[4]

OpenCL is the currently dominant open general-purpose GPU computing language. The dominant proprietary framework is Nvidia's CUDA.[5]

Overview and history[edit]

General-purpose computing on GPUs only became practical and popular after ca. 2001, with the advent of both programmable shaders and floating point support on graphics processors. The scientific computing community's experiments with the new hardware started with a matrix multiplication routine (2001); the first scientific code that ran faster on GPUs than CPUs was an implementation of LU factorization (2005).[6]

These early efforts to use GPUs as general-purpose processors required reformulating computational problems in terms of graphics primitives, as supported by the two major APIs for graphics processors, OpenGL and DirectX. This cumbersome translation was obviated by the advent of general-purpose programming languages and APIs such as Sh/RapidMind, Brook and Accelerator.[7][8] These were followed by Nvidia's CUDA, which "ushered [sic] a new era of improved performance" and replaced "archaic terms such as texels, fragments and pixels" with more common high-performance computing concepts.[6] Newer, hardware vendor-independent offerings include Microsoft's DirectCompute and Apple/Khronos Group's OpenCL.[6]

Role of DirectX[edit]

The programmability of the pipelines have trended[clarification needed] according to Microsoft’s DirectX specification,[citation needed] with DirectX 8 introducing Shader Model 1.1, DirectX 8.1 Pixel Shader Models 1.2, 1.3 and 1.4, and DirectX 9 defining Shader Model 2.x and 3.0. Each shader model increased the programming model flexibilities and capabilities, ensuring the conforming hardware follows suit. The DirectX 10 specification introduces Shader Model 4.0 which unifies the programming specification for vertex, geometry (“Geometry Shaders” are new to DirectX 10) and fragment processing allowing for a better fit for unified shader hardware, thus providing one computational pool of programmable resource.[vague]

Data types[edit]

Pre-DirectX 9 graphics cards only supported paletted or integer color types. Various formats are available, each containing a red element, a green element, and a blue element.[citation needed] Sometimes an additional alpha value is added, to be used for transparency. Common formats are:

  • 8 bits per pixel – Sometimes palette mode, where each value is an index in a table with the real color value specified in one of the other formats. Sometimes three bits for red, three bits for green, and two bits for blue.
  • 16 bits per pixel – Usually allocated as five bits for red, six bits for green, and five bits for blue.
  • 24 bits per pixel – eight bits for each of red, green, and blue
  • 32 bits per pixel – eight bits for each of red, green, blue, and alpha

For early fixed-function or limited programmability graphics (i.e. up to and including DirectX 8.1-compliant GPUs) this was sufficient because this is also the representation used in displays. This representation does have certain limitations, however. Given sufficient graphics processing power even graphics programmers would like to use better formats, such as floating point data formats, to obtain effects such as high dynamic range imaging. Many GPGPU applications require floating point accuracy, which came with graphics cards conforming to the DirectX 9 specification.

DirectX 9 Shader Model 2.x suggested the support of two precision types: full and partial precision. Full precision support could either be FP32 or FP24 (floating point 32- or 24-bit per component) or greater, while partial precision was FP16. ATI’s R300 series of GPUs supported FP24 precision only in the programmable fragment pipeline (although FP32 was supported in the vertex processors) while Nvidia’s NV30 series supported both FP16 and FP32; other vendors such as S3 Graphics and XGI supported a mixture of formats up to FP24.

Shader Model 3.0 altered the specification, increasing full precision requirements to a minimum of FP32 support in the fragment pipeline. ATI’s Shader Model 3.0 compliant R5xx generation (Radeon X1000 series) supports just FP32 throughout the pipeline while Nvidia’s NV4x and G7x series continued to support both FP32 full precision and FP16 partial precisions. Although not stipulated by Shader Model 3.0, both ATI and Nvidia’s Shader Model 3.0 GPUs introduced support for blendable FP16 render targets, more easily facilitating the support for High Dynamic Range Rendering.[citation needed]

The implementations of floating point on Nvidia GPUs are mostly IEEE compliant; however, this is not true across all vendors.[9] This has implications for correctness which are considered important to some scientific applications. While 64-bit floating point values (double precision float) are commonly available on CPUs, these are not universally supported on GPUs; some GPU architectures sacrifice IEEE compliance while others lack double-precision altogether. There have been efforts to emulate double-precision floating point values on GPUs; however, the speed tradeoff negates any benefit to offloading the computation onto the GPU in the first place.[10]

Most operations on the GPU operate in a vectorized fashion: one operation can be performed on up to four values at once. For instance, if one color <R1, G1, B1> is to be modulated by another color <R2, G2, B2>, the GPU can produce the resulting color <R1*R2, G1*G2, B1*B2> in one operation. This functionality is useful in graphics because almost every basic data type is a vector (either 2-, 3-, or 4-dimensional). Examples include vertices, colors, normal vectors, and texture coordinates. Many other applications can put this to good use, and because of their higher performance, vector instructions (SIMD) have long been available on CPUs.

In 2002, James Fung et al developed OpenVIDIA at University of Toronto, and demonstrated this work, which was later published in 2003, 2004, and 2005,[11] in conjunction with a collaboration between University of Toronto and nVIDIA. In November 2006 Nvidia launched CUDA, an SDK and API that allows using the C programming language to code algorithms for execution on Geforce 8 series GPUs. OpenCL, an open standard defined by the Khronos Group[12] provides a cross-platform GPGPU platform that additionally supports data parallel compute on CPUs. OpenCL is actively supported on Intel, AMD, Nvidia and ARM platforms. GPGPU compared, for example, to traditional floating point accelerators such as the 64-bit CSX700 boards from ClearSpeed that are used in today's supercomputers, current top-end GPUs from AMD and Nvidia emphasize single-precision (32-bit) computation; double-precision (64-bit) computation executes more slowly.[citation needed]

GPGPU programming concepts[edit]

GPUs are designed specifically for graphics and thus are very restrictive in operations and programming. Due to their design, GPUs are only effective for problems that can be solved using stream processing and the hardware can only be used in certain ways.

Stream processing[edit]

Main article: Stream processing

GPUs can only process independent vertices and fragments, but can process many of them in parallel. This is especially effective when the programmer wants to process many vertices or fragments in the same way. In this sense, GPUs are stream processors – processors that can operate in parallel by running one kernel on many records in a stream at once.

A stream is simply a set of records that require similar computation. Streams provide data parallelism. Kernels are the functions that are applied to each element in the stream. In the GPUs, vertices and fragments are the elements in streams and vertex and fragment shaders are the kernels to be run on them. Since GPUs process elements independently there is no way to have shared or static data. For each element we can only read from the input, perform operations on it, and write to the output. It is permissible to have multiple inputs and multiple outputs, but never a piece of memory that is both readable and writable.[vague]

Arithmetic intensity is defined as the number of operations performed per word of memory transferred. It is important for GPGPU applications to have high arithmetic intensity else the memory access latency will limit computational speedup.[13]

Ideal GPGPU applications have large data sets, high parallelism, and minimal dependency between data elements.

GPU programming concepts[edit]

Computational resources[edit]

There are a variety of computational resources available on the GPU:

  • Programmable processors – Vertex, primitive, and fragment pipelines allow programmer to perform kernel on streams of data
  • Rasterizer – creates fragments and interpolates per-vertex constants such as texture coordinates and color
  • Texture Unit – read only memory interface
  • Framebuffer – write only memory interface

In fact, the programmer can substitute a write only texture for output instead of the framebuffer. This is accomplished either through Render to Texture (RTT), Render-To-Backbuffer-Copy-To-Texture (RTBCTT), or the more recent stream-out.

Textures as stream[edit]

The most common form for a stream to take in GPGPU is a 2D grid because this fits naturally with the rendering model built into GPUs. Many computations naturally map into grids: matrix algebra, image processing, physically based simulation, and so on.

Since textures are used as memory, texture lookups are then used as memory reads. Certain operations can be done automatically by the GPU because of this.

Kernels[edit]

Kernels can be thought of as the body of loops. For example, a programmer operating on a grid on the CPU might have code that looks like this:

// Input and output grids have 10000 x 10000 or 100 million elements.
 
void transform_10k_by_10k_grid(float in[10000][10000], float out[10000][10000])
{
    for (int x = 0; x < 10000; x++) {
        for (int y = 0; y < 10000; y++) {
            // The next line is executed 100 million times
            out[x][y] = do_some_hard_work(in[x][y]);
        }
    }
}

On the GPU, the programmer only specifies the body of the loop as the kernel and what data to loop over by invoking geometry processing.

Flow control[edit]

In sequential code it is possible to control the flow of the program using if-then-else statements and various forms of loops. Such flow control structures have only recently been added to GPUs.[14] Conditional writes could be accomplished using a properly crafted series of arithmetic/bit operations, but looping and conditional branching were not possible.

Recent GPUs allow branching, but usually with a performance penalty. Branching should generally be avoided in inner loops, whether in CPU or GPU code, and various methods, such as static branch resolution, pre-computation, predication, loop splitting,[15] and Z-cull[16] can be used to achieve branching when hardware support does not exist.

GPU methods[edit]

Map[edit]

The map operation simply applies the given function (the kernel) to every element in the stream. A simple example is multiplying each value in the stream by a constant (increasing the brightness of an image). The map operation is simple to implement on the GPU. The programmer generates a fragment for each pixel on screen and applies a fragment program to each one. The result stream of the same size is stored in the output buffer.

Reduce[edit]

Some computations require calculating a smaller stream (possibly a stream of only 1 element) from a larger stream. This is called a reduction of the stream. Generally a reduction can be accomplished in multiple steps. The results from the prior step are used as the input for the current step and the range over which the operation is applied is reduced until only one stream element remains.

Stream filtering[edit]

Stream filtering is essentially a non-uniform reduction. Filtering involves removing items from the stream based on some criteria.

Scatter[edit]

The scatter operation is most naturally defined on the vertex processor. The vertex processor is able to adjust the position of the vertex, which allows the programmer to control where information is deposited on the grid. Other extensions are also possible, such as controlling how large an area the vertex affects.

The fragment processor cannot perform a direct scatter operation because the location of each fragment on the grid is fixed at the time of the fragment's creation and cannot be altered by the programmer. However, a logical scatter operation may sometimes be recast or implemented with an additional gather step. A scatter implementation would first emit both an output value and an output address. An immediately following gather operation uses address comparisons to see whether the output value maps to the current output slot.

Gather[edit]

The fragment processor is able to read textures in a random access fashion, so it can gather information from any grid cell, or multiple grid cells, as desired.[vague]

Sort[edit]

The sort operation transforms an unordered set of elements into an ordered set of elements. The most common implementation on GPUs is using sorting networks.[16]

Search[edit]

The search operation allows the programmer to find a particular element within the stream, or possibly find neighbors of a specified element. The GPU is not used to speed up the search for an individual element, but instead is used to run multiple searches in parallel.[citation needed]

Data structures[edit]

A variety of data structures can be represented on the GPU:

Applications[edit]

Research: Higher Education and Supercomputing[edit]

Computational Chemistry and Biology[edit]

Bioinformatics[17][edit]
Application Description Supported Features Expected Speed Up† GPU‡ Multi-GPU Support Release Status
BarraCUDA Sequence mapping software Alignment of short sequencing reads 6–10x T 2075, 2090, K10, K20, K20X Yes Available now Version 0.6.2
CUDASW++ Open source software for Smith-Waterman protein database searches on GPUs Parallel search of Smith-Waterman database 10–50x T 2075, 2090, K10, K20, K20X Yes Available now Version 2.0.8
CUSHAW Parallelized short read aligner Parallel, accurate long read aligner – gapped alignments to large genomes 10x T 2075, 2090, K10, K20, K20X Yes Available now Version 1.0.40
GPU-BLAST Local search with fast k-tuple heuristic Protein alignment according to blastp, multi CPU threads 3–4x T 2075, 2090, K10, K20, K20X Single only Available now Version 2.2.26
GPU-HMMER Parallelized local and global search with profile Hidden Markov models Parallel local and global search of Hidden Markov Models 60–100x T 2075, 2090, K10, K20, K20X Yes Available now Version 2.3.2
mCUDA-MEME Ultrafast scalable motif discovery algorithm based on MEME Scalable motif discovery algorithm based on MEME 4–10x T 2075, 2090, K10, K20, K20X Yes Available now Version 3.0.12
SeqNFind A GPU Accelerated Sequence Analysis Toolset Reference assembly, blast, Smith–Waterman, hmm, de novo assembly 400x T 2075, 2090, K10, K20, K20X Yes Available now
UGENE Opensource Smith–Waterman for SSE/CUDA, Suffix array based repeats finder and dotplot Fast short read alignment 6–8x T 2075, 2090, K10, K20, K20X Yes Available now Version 1.11
WideLM Fits numerous linear models to a fixed design and response Parallel linear regression on multiple similarly-shaped models 150x T 2075, 2090, K10, K20, K20X Yes Available now Version 0.1-1
Molecular Dynamics[17][edit]
Application Description Supported Features Expected Speed Up† GPU‡ Multi-GPU Support Release Status
Abalone Models molecular dynamics of biopolymers for simulations of proteins, DNA and ligands Explicit and implicit solvent, Hybrid Monte Carlo 4–29x T 2075, 2090, K10, K20, K20X Single Only Available now Version 1.8.48
ACEMD GPU simulation of molecular mechanics force fields, implicit and explicit solvent Written for use on GPUs 160 ns/day GPU version only T 2075, 2090, K10, K20, K20X Yes Available now
AMBER Suite of programs to simulate molecular dynamics on biomolecule PMEMD: explicit and implicit solvent 89.44 ns/day JAC NVE T 2075, 2090, K10, K20, K20X Yes Available now Version 12 + bugfix9
DL-POLY Simulate macromolecules, polymers, ionic systems, etc. on a distributed memory parallel computer Two-body forces, Link-cell pairs, Ewald SPME forces, Shake VV 4x T 2075, 2090, K10, K20, K20X Yes Available now, Version 4.0 source only
CHARMM MD package to simulate molecular dynamics on biomolecule. Implicit (5x), Explicit (2x) Solvent via OpenMM TBD T 2075, 2090, K10, K20, K20X Yes In development Q4/12
GROMACS Simulation of biochemical molecules with complicated bond interactions Implicit (5x), Explicit (2x) solvent 165 ns/Day DHFR T 2075, 2090, K10, K20, K20X Single only Available now version 4.6 in Q4/12
HOOMD-Blue Particle dynamics package written grounds up for GPUs Written for GPUs 2x T 2075, 2090, K10, K20, K20X Yes Available now
LAMMPS Classical molecular dynamics package Lennard-Jones, Morse, Buckingham, CHARMM, Tabulated, Course grain SDK, Anisotropic Gay-Bern, RE-squared, “Hybrid”combinations 3–18x T 2075, 2090, K10, K20, K20X Yes Available now
NAMD Designed for high-performance simulation of large molecular systems 100M atom capable 6.44 ns/days STMV 585x 2050s T 2075, 2090, K10, K20, K20X Yes Available now, version 2.9
OpenMM Library and application for molecular dynamics for HPC with GPUs Implicit and explicit solvent, custom forces Implicit: 127–213 ns/day; Explicit: 18–55 ns/day DHFR T 2075, 2090, K10, K20, K20X Yes Available now version 4.1.1

†Expected speedups are highly dependent on system configuration. GPU performance compared against multi-core x86 CPU socket. GPU performance benchmarked on GPU supported features and may be a kernel to kernel performance comparison. For details on configuration used, view application website. Speedups as per Nvidia in-house testing or ISV's documentation .

‡ Q=Quadro GPU, T=Tesla GPU. Nvidia recommended GPUs for this application. Please check with developer / ISV to obtain certification information.

The following are some of the areas where GPUs have been used for general purpose computing:

See also[edit]

References[edit]

  1. ^ Fung etal, "Mediated Reality Using Computer Graphics Hardware for Computer Vision", Proceedings of the International Symposium on Wearable Computing 2002 (ISWC2002), Seattle, Washington, USA, 7–10 Oct 2002, pp. 83–89.
  2. ^ An EyeTap video-based featureless projective motion estimation assisted by gyroscopic tracking for wearable computer mediated reality, ACM Personal and Ubiquitous Computing published by Springer Verlag, Vol.7, Iss. 3, 2003.
  3. ^ "Computer Vision Signal Processing on Graphics Processing Units", Proceedings of the IEEE International Conference on Acoustics, Speech, and Signal Processing (ICASSP 2004): Montreal, Quebec, Canada, 17–21 May 2004, pp. V-93 – V-96
  4. ^ "Using Multiple Graphics Cards as a General Purpose Parallel Computer: Applications to Computer Vision", Proceedings of the 17th International Conference on Pattern Recognition (ICPR2004), Cambridge, United Kingdom, 23–26 August 2004, volume 1, pages 805–808.
  5. ^ http://www.hpcwire.com/hpcwire/2012-02-28/opencl_gains_ground_on_cuda.html "As the two major programming frameworks for GPU computing, OpenCL and CUDA have been competing for mindshare in the developer community for the past few years."
  6. ^ a b c Du, Peng; Weber, Rick; Luszczek, Piotr; Tomov, Stanimire; Peterson, Gregory; Dongarra, Jack (2012). "From CUDA to OpenCL: Towards a performance-portable solution for multi-platform GPU programming". Parallel Computing 38 (8): 391–407. doi:10.1016/j.parco.2011.10.002.  edit
  7. ^ Tarditi, David; Puri, Sidd; Oglesby, Jose (2006). "Accelerator: using data parallelism to program GPUs for general-purpose uses". ACM SIGARCH Computer Architecture News 34 (5). 
  8. ^ Che, Shuai; Boyer, Michael; Meng, Jiayuan; Tarjan, D.; Sheaffer, Jeremy W.; Skadron, Kevin (2008). "A performance study of general-purpose applications on graphics processors using CUDA". J. Parallel and Distributed Computing 68 (10): 1370–1380. 
  9. ^ Mapping computational concepts to GPUs: Mark Harris. Mapping computational concepts to GPUs. In ACM SIGGRAPH 2005 Courses (Los Angeles, California, 31 July – 4 August 2005). J. Fujii, Ed. SIGGRAPH '05. ACM Press, New York, NY, 50.
  10. ^ Double precision on GPUs (Proceedings of ASIM 2005): Dominik Goddeke, Robert Strzodka, and Stefan Turek. Accelerating Double Precision (FEM) Simulations with (GPUs). Proceedings of ASIM 2005 – 18th Symposium on Simulation Technique, 2005.
  11. ^ James Fung, Steve Mann, Chris Aimone, "OpenVIDIA: Parallel GPU Computer Vision", Proceedings of the ACM Multimedia 2005, Singapore, 6–11 Nov. 2005, pages 849–852
  12. ^ [1]:OpenCL at the Khronos Group
  13. ^ Asanovic, K., Bodik, R., Demmel, J., Keaveny, T., Keutzer, K., Kubiatowicz, J., Morgan, N., Patterson, D., Sen, K., Wawrzynek, J., Wessel, D., Yelick, K.: A view of the parallel computing landscape. Commun. ACM 52(10) (2009) 56–67
  14. ^ GPU Gems – Chapter 34, GPU Flow-Control Idioms
  15. ^ [2]: Future Chips. "Tutorial on removing branches", 2011
  16. ^ a b GPGPU survey paper: John D. Owens, David Luebke, Naga Govindaraju, Mark Harris, Jens Krüger, Aaron E. Lefohn, and Tim Purcell. "A Survey of General-Purpose Computation on Graphics Hardware". Computer Graphics Forum, volume 26, number 1, 2007, pp. 80–113.
  17. ^ a b http://www.nvidia.com/docs/IO/123576/nv-applications-catalog-lowres.pdf
  18. ^ "MATLAB Adds GPGPU Support". 20 September 2010. 
  19. ^ Fast k-nearest neighbor search using GPU. In Proceedings of the CVPR Workshop on Computer Vision on GPU, Anchorage, Alaska, USA, June 2008. V. Garcia and E. Debreuve and M. Barlaud.
  20. ^ M. Cococcioni, R. Grasso, M. Rixen, Rapid prototyping of high performance fuzzy computing applications using high level GPU programming for maritime operations support, in Proceedings of the 2011 IEEE Symposium on Computational Intelligence for Security and Defense Applications (CISDA), Paris, 11–15 April 2011
  21. ^ Wilson, Ron (3 September 2009). "DSP brings you a high-definition moon walk". EDN. Retrieved 3 September 2009. "Lowry is reportedly using Nvidia Tesla GPUs (graphics-processing units) programmed in the company's CUDA (Compute Unified Device Architecture) to implement the algorithms. Nvidia claims that the GPUs are approximately two orders of magnitude faster than CPU computations, reducing the processing time to less than one minute per frame." 
  22. ^ E. Alerstam, T. Svensson & S. Andersson-Engels, "Parallel computing with graphics processing units for high speed Monte Carlo simulation of photon migration" [3], J. Biomedical Optics 13, 060504 (2008) [4]
  23. ^ http://www.astro.lu.se/compugpu2010/
  24. ^ Schatz, M.C., Trapnell, C., Delcher, A.L., Varshney, A. (2007) High-throughput sequence alignment using Graphics Processing Units. BMC Bioinformatics 8:474.
  25. ^ Svetlin A. Manavski, Giorgio Valle (2008). "CUDA compatible GPU cards as efficient hardware accelerators for Smith-Waterman sequence alignment url=http://www.biomedcentral.com/1471-2105/9/S2/S10". BMC Bioinformatics 9 (Suppl. 2): S10. doi:10.1186/1471-2105-9-s2-s10. 
  26. ^ GPU-based Sorting in PostgreSQL Naju Mancheril, School of Computer Science – Carnegie Mellon University
  27. ^ AES on SM3.0 compliant GPUs. Owen Harrison, John Waldron, AES Encryption Implementation and Analysis on Commodity Graphics Processing Units. In proceedings of CHES 2007.
  28. ^ AES and modes of operations on SM4.0 compliant GPUs. Owen Harrison, John Waldron, Practical Symmetric Key Cryptography on Modern Graphics Hardware. In proceedings of USENIX Security 2008.
  29. ^ RSA on SM4.0 compliant GPUs. Owen Harrison, John Waldron, Efficient Acceleration of Asymmetric Cryptography on Graphics Hardware. In proceedings of AfricaCrypt 2009.
  30. ^ "Teraflop Troubles: The Power of Graphics Processing Units May Threaten the World's Password Security System". Georgia Tech Research Institute. Retrieved 7 November 2010. 
  31. ^ "Want to deter hackers? Make your password longer". MSNBC. 19 August 2010. Retrieved 7 November 2010. 
  32. ^ Lerner, Larry (9 April 2009). "Viewpoint: Mass GPUs, not CPUs for EDA simulations". EE Times. Retrieved 3 May 2009. 
  33. ^ "W2500 ADS Transient Convolution GT". "accelerates signal integrity simulations on workstations that have NVIDIA Compute Unified Device Architecture (CUDA)-based Graphics Processing Units (GPU)" 
  34. ^ GrAVity: A Massively Parallel Antivirus Engine. Giorgos Vasiliadis and Sotiris Ioannidis, GrAVity: A Massively Parallel Antivirus Engine. In proceedings of RAID 2010.
  35. ^ "Kaspersky Lab utilizes NVIDIA technologies to enhance protection". Kaspersky Lab. 14 December 2009. "During internal testing, the Tesla S1070 demonstrated a 360-fold increase in the speed of the similarity-defining algorithm when compared to the popular Intel Core 2 Duo central processor running at a clock speed of 2.6 GHz." 
  36. ^ Gnort: High Performance Network Intrusion Detection Using Graphics Processors. Giorgos Vasiliadis et al, Gnort: High Performance Network Intrusion Detection Using Graphics Processors. In proceedings of RAID 2008.
  37. ^ Regular Expression Matching on Graphics Hardware for Intrusion Detection. Giorgos Vasiliadis et al, Regular Expression Matching on Graphics Hardware for Intrusion Detection. In proceedings of RAID 2009.
  38. ^ Open HMPP

External links[edit]