GPGPU
From Wikipedia, the free encyclopedia
General-Purpose Computing on Graphics Processing Units (GPGPU, also referred to as GPGP and to a lesser extent GP²) is a recent trend in computer science that uses the Graphics Processing Unit to perform the computations rather than the CPU. The addition of programmable stages and higher precision arithmetic to the GPU rendering pipeline have allowed software developers to use the GPU for non graphics related applications. Because of the extremely parallel nature of the graphics pipeline the GPU is especially useful for programs that can be cast as stream processing and real-time computing problems.
Contents |
[edit] GPU Improvements
For many years GPU functionality was very limited. In fact, for many years the GPU was only used to accelerate certain parts of the graphics pipeline. Some improvements were needed before GPGPU became feasible.
[edit] Programmability
Programmable vertex and fragment shaders were added to the graphics pipeline to enable game programmers to generate even more realistic effects. Vertex shaders allow the programmer to alter per-vertex attributes, such as position, color, texture coordinates, and normal vector. Fragment shaders are used to calculate the color of a fragment, or per-pixel. Programmable fragment shaders allow the programmer to substitute, for example, a lighting model other than those provided by default by the graphics card, typically simple Gouraud shading. Shaders have enabled graphics programmers to create lens effects, displacement mapping, and depth of field.
The programmability of the pipelines have trended according the Microsoft’s DirectX specification[citation needed] , with DirectX8 introducing Shader Model 1.1, DirectX8.1 Pixel Shader Models 1.2, 1.3 and 1.4, and DirectX9 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 DirectX10 specification unifies the programming specification for vertex, geometry (“Geometry Shaders” are new to DirectX10) and fragment processing allowing for a better fit for unified shader hardware, thus providing a single computational pool of programmable resource.[vague]
[edit] Data types
Pre DirectX9 graphics cards only supported paletted or integral color types[vague]. 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 - Palette mode[vague], where each value is an index into a table with the real color value specified in one of the other formats. Possibly 2 bits for red, 3 bits for green, and 3 bits for blue.
- 16 bits per pixel - Usually allocated as 5 bits for red, 6 bits for green, and 5 bits for blue.
- 24 bits per pixel - 8 bits for each of red, green, and blue
- 32 bits per pixel - 8 bits for each of red, green, blue, and alpha
For early fixed function or limited programmability graphics (i.e. up to and including DirectX8.1 compliant GPU's) 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, in order to obtain effects such as high dynamic range imaging. Many GPGPU applications require floating point accuracy, which came with graphics cards conforming to the DirectX9 specification.
DirectX9 Shader Model 2.x suggested the support of two precision types: full and partial precision. Full precision support could either be and FP24 (floating point 24-bit per component) or greater, while partial precision was FP16. ATI’s R300 series of GPU’s 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 GPU’s introduced support for blendable FP16 render targets, easier facilitating the support for High Dynamic Range Rendering[citation needed].
The implementations of floating point on GPUs are generally not IEEE compliant[citation needed], and generally do not match across vendors. 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 currently available on GPUs. Some applications require at least double precision floating point values and thus cannot currently be ported to GPUs[vague]. There have been efforts to emulate double precision floating point values on GPUs.
Most operations on the GPU operate in a vectorized fashion: a single 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 a single 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 this vector instructions (SIMD) have already been added to CPUs[vague].
In November 2006 NVIDIA launched GeForce 8800 that uses CUDA™ (Compute Unified Device Architecture), a SDK and API that allows a programmer to use the C programming language to code algorithms for execution on the GPU. ATI/AMD offers a similar SDK for their ATI-based GPUs and that SDK and technology is called CTM™ (Close to Metal™), designed to compete directly with NVIDIA's CUDA™, CTM provides a hardware interface thin (thin hardware interface). AMD has also announced the AMD Stream Processor product line (combining a CPU and a GPU technology on one chip. Compared, for example, to traditional floating point accelerators such as the 64-bit CSX600 boards from Clearspeed that is used in today's supercomputers, the current GPUs from NVIDIA and AMD/ATI are only running on 32-bit, providing only single-precision data capability – instead of the double-precision (64-bit) capability of todays supercomputers[1]. NVIDIA however stated in the CUDA Release Notes Version 0.8 file that NVIDIA GPUs supporting (64-bit) Double Precision Floating Point arithmetic in hardware will become available in late 2007.[2]. Still, even without true Double Precision Floating Point arithmetic in hardware, CUDA™ and CTM™ are a great step toward a broader use of GPGPU technology.
[edit] GPGPU programming concepts
GPUs are designed specifically for graphics and thus are very restrictive in terms of operations and programming. Because of their nature GPUs are only effective at tackling problems that can be solved using stream processing and the hardware can only be used in certain ways.
[edit] 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 a single 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 operations performed per word of memory transferred. It is important for GPGPU applications to have high arithmetic intensity or memory access latency will limit computation speed.[citation needed]
Ideal GPGPU applications have large data sets, high parallelism, and minimal dependency between data elements.
[edit] GPU programming concepts
[edit] Computational resources
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 texure 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.
[edit] Textures as stream
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.
[edit] Kernels
Kernels can be thought of as the body of loops. For example, if the programmer was operating on a grid on the CPU he might have code that looked like this:
/* Pseudocode */
x = 10e8
y = 10e8
make array x by y
for each "x" { // Loop this block 10e8 times
for each "y" { // Loop this block 10e8 times
do_some_hard_work(x, y) // This is done 10e16 times (10 000 000 000 000 000)
}
}
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.
[edit] Flow control
In regular programs 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.[citation needed] Conditional writes could be accomplished using a series of simpler instructions[vague], 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 techniques, such as static branch resolution, pre-computation, and Z-cull can be used to achieve branching when hardware support does not exist.
[edit] GPU techniques
[edit] Map
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.
[edit] Reduce
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 previous 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.
[edit] Stream filtering
Stream filtering is essentially a non-uniform reduction. Filtering involves removing items from the stream based on some criteria.
[edit] Scatter
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.
[edit] Gather
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].
[edit] Sort
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.
[edit] Search
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]
[edit] Data structures
A variety of data structures can be represented on the GPU:
- Dense Arrays
- Sparse Arrays - static or dynamic
- Adaptive Structures
[edit] Applications
The following are some of the non-graphics areas where GPUs have been used for general purpose computing:
- Computer clusters or a variation of a parallel computing (utilizing GPU cluster technology) for highly calculation-intensive tasks:
- High-performance clusters (HPC) (often refered to as supercomputers)
- including cluster technologies like Message Passing Interface, and Single-system image (SSI), Distributed computing, and Beowulf
- Grid computing (a form of Distributed computing) (networking many heterogeneous computers to create a virtual computer architecture)
- Load-balancing clusters (sometimes referred to as a server farm)
- High-performance clusters (HPC) (often refered to as supercomputers)
- Physical based simulation and physics engines (usually based on Newtonian physics models)
- Conway's Game of Life, Cloth simulation, incompressible fluid flow by solution of Navier-Stokes equations
- Segmentation - 2D and 3D
- Level-set methods
- CT reconstruction
- Fast Fourier Transform
- Tone mapping
- Audio signal processing
- Audio and Sound Effects Processing, to use a GPU as a for DSP (Digital Signal processing)
- Analog signal processing
- Speech processing
- Digital image processing
- Video Processing
- Hardware Accelerated Video Decoding and post-processing
- Deinterlacing
- Color correction
- Hardware Accelerated Video Encoding and pre-processing
- Raytracing
- Global Illumination - Photon Mapping, Radiosity, Subsurface Scattering
- Geometric Computing - Constructive Solid Geometry (CSG), Distance Fields, Collision Detection, Transparency Computation, Shadow Generation
- Scientific computing
- Weather forecasting
- Climate research ((including research into global warming)
- Molecular modeling
- Quantum mechanical physics
- Bioinformatics
- Computational finance
- Medical imaging
- Computer vision
- Digital signal processing / Signal processing
- Control engineering
- Neural Networks
- Database operations
- Lattice Boltzmann methods
- Cryptography and cryptanalysis
[edit] References
- ^ 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.
- ^ Survey paper (to appear in Computer Graphics Forum 2007; revision of Eurographics STAR, August 2005): 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, 2007. To appear.
[edit] See also
- Graphics Processing Unit
- Stream Processor
- Stream programming
- Shader
- HLSL2GLSL
- Sh, a GPGPU library for C++
- Physics engine is a computer program or that simulates Newtonian physics (on CPU, GPU or PPU)
- OPAL (Open Physics Abstraction Layer), a free (LGPL and BSD licensed) and open source cross platform physics engine API abstraction system.
- Havok Physics / Havok FX, commercial physics engine middleware SDK for computer and video games
- PhysX SDK, commercial realtime physics engine middleware SDK developed by AGEIA
- CTM (Close To Metal), AMD/ATI's competing GPGPU technology for ATI Rade-based GPUs
- CUDA (Compute Unified Device Architecture), NVIDIA's competing GPGPU technology for NVIDIA GeForce-based GPUs
- Audio_Processing_Unit (APU) (DSP can also be done on a GPU with GPGPU technology)
[edit] External links
- http://www.gpgpu.org
- GPGPU Wiki
- SIGGRAPH 2005 GPGPU Course Notes
- IEEE VIS 2005 GPGPU Course Notes
- http://developer.nvidia.com
- http://www.atitech.com/developer
- Hijacking the GPU (APC Magazine article on GPGPU computing)
- Slideshow for ATI GPGPU physics demonstration by Stanford grad student Mike Houston See p.13 for overview of mapping of conventional program tasks to GPU hardware.
- Tech Report article: "ATI stakes claims on physics, GPGPU ground" by Scott Wasson
- http://www.acceleware.com
|
|
|
|
Categories: Articles with unsourced statements since February 2007 | All articles with unsourced statements | Wikipedia articles needing clarification | Computational science | Computer graphics | Graphics hardware | Graphics cards | Microprocessors | Parallel computing | Video game development | Computer language stubs
