Mattan’s slides

()

Lecture 11: The Graphics Processing Unit (GPU)

This class introduces the Graphics Processing Unit (GPU) architecture and discusses it’s relevance in the realms of general purpose computing. The outline of the lecture is as follows:

  1. What is a GPU ?
  2. Why should we care about GPUs ?
  3. The 3D graphics pipeline
  4. Programmable graphics pipeline

Most slides are courtesy David Kirk (NVIDIA) and Wen-Mei Hwu (UICU). Some slides are courtesy Massimiliano Fatica (NVIDIA).

Introduction

What is a GPU ?

A graphics processing unit (GPU) is designed primarily to accelerate the rendering of 3D scenes. Input to the GPUs is the scene description which includes geometry, color, light, texture, effects etc. The output of the GPU is a 2D image representing the 3D scene rendered based on the description provided.

Interface between the GPU and graphics applications

The scene complexity input to the GPU is provided by standard application programming interfaces (API), like the DirectX (Microsoft) and OpenGL (open source). This is depicted in the following figure.

The API’s take the scene information from the applications and convert them into GPU commands and data streams which are sent to the GPU. The scene complexity is described in terms of:

  • Geometry (describes the objects and layouts)
    • Triangles (vertices) are used to describe the scene
      • can have millions of triangles per scene
    • Can modify triangle surfaces (e.g. bumps, ripples, waves)
    • Lights
  • Pixel Shaders (describes how to add color)
    • Colors of triangle vertices
    • Textures
    • Interpolation methods to determine color for pixels withing the triangles

Advances in GPU

State of art in 1985 took 2–3 hrs to process a single frame on Cray-1 supercomputer. Today, with the current GPU architectures, it takes 1/30th of a second on a PC. The complexity and quality of the images have improved by an order of magnitude. A summary of the GPU advances and comments is captured in the following table.

GPU’s in YearDirectX APIComments
1997DirectX 5-
1998DirectX 6-
2000DirectX 7-
2001DirectX 8First programmable graphics (Shader Model 1). Developers had to be creative with H/W
2003DirectX 9More Programmability (Shader Model 2)
2004DirectX 9.0cMore Programmability (Shader Model 3)
2006DirectX 10With full programs in pipeline (Shader Model 4)

Why should we care about GPUs ?

The complexity and quality of the images rendered by the GPU ‘s have improved by an order of magnitude. It outpaces anything we know or can do with a general purpose CPU. The relative improvement in the performance of the GPUs and general purpose CPUs in shown in the following figure.

More recently (~5 years back), GPUs have evolved to be fully programmable general purpose processor. Many application were identified which required similar programmability as that required for graphics and GPUs are being used extensively for these applications. Some of these applications are:

  • Computational Geo-science
  • Computational Modeling
  • Computational Medicine
  • Computational Chemistry
  • Computational Biology
  • Computational Finance

The following figure shows the speedup that can be achieved for some of the application on a GPU (NVIDIA GeForce 8800) as compared to a 2.2 Ghz Opteron 248 general purpose processor.

  • 10x improvement in kernel is typical, as long as the kernel can occupy enough parallel threads
  • 25x to 400x speedup can be achieved for applications whose data and control requirement suit the GPU architecture

Furthermore, a more compelling reason to care about the GPU’s is that the GPU and CPU architectures are starting to get convergent . Thus we can leverage on the advances in both to further improve performance. The advances in CPU and GPU in terms of parallelism and programmability is shown in the following table.

 CPUsGPUs
1997No explicit parallelismnot programmable
2000explicit short vectorsemerging programmability (not explicit in H/W) (2001–2002), “infinite” Data Parallel (DP)
2003explicit short vectors, explicit threading (~2)fully programmable explicit “infinite” DP, no scatter
2006explicit short vectors, explicit threading (~4)explicit vectors, explicit threading (~16)
2009 ?explicit vectors, explicit threading (>16)explicit vectors, explicit threading (>16)

The NVIDIA GeForce Graphics Pipeline

The NVIDIA GeForce graphics pipeline is shown in the following figure. A complete description of the pipeline is then developed in the upcoming subsections.

Describing an object

  1. We start with identifying the vertices of the triangles which are passed to the GPU.
  2. Lines are then added
  3. Light is added to the object to get a feel of the surface
  4. Texture is added
  5. Reflections (shining, specular lighting)
  6. Geometric details are added

This process is shown in the following figure.

Feeding the GPU

  • GPU accepts a sequence of sets of commands and data
    • Vertex positions, colors and shader parameters
    • Texture map images
    • Commands like, “draw triangles with vertices until a stop command is sent”
  • Application pushes data using the API (DirectX or OpenGL)
  • GPU can retrieve commands and data from the system memory or it’s local memory

Host Interface (Stage 1)

  • Bus interface
  • DMA (Direct Memory Access) interface to retrieve commands and data from local/system memory
  • Class interfaces (how to process these commands)
  • Controls
    • How the CPU communicates to the GPU (one-sided)
    • How the GPU communicates to the CPU (one-sided)
    • Move data back-and-forth to the CPU (dual-sided)

Vertex Control (Stage 2)

A vertex defines the “corners” of a primitive. For the NVIDIA GeForce the primitive used is a triangle.

The Vertex control stage is used to,

  • Rotate, translate and scale each object to place it correctly among the other objects that make up the scene
  • Rotate, translate and scale the entire scene based on the viewing (or camera) angle

This vertex transformation can be achieved by multiplying each vertex position by a combined 4×4 model-view matrix to get a 4D eyespace (as per the camera/eye) position, defined as [x y z w]. Here x, y, z represents the transformed location in the scene and ‘w’ is the perspective which is proportional to 1/(distance from camera).

Thus the Vertex control stage does the following operations:

  • Receives parameterized vertex data
  • Inputs data to vertex cache
  • Formats vertices for processing
  • Since data can come to the GPU in variety of formats, the Vertex Control stage organizes the vertex data into consistent hardware understandable format.

Vertex Cache

  • Vertex cache is used to temporarily store vertices, to gain higher efficiency
  • Since a vertex can be common to more than one primitive (consider adjoining triangles), re-using vertices between primitives saves AGP/PCI-E bus bandwidth and GPU computational resources. Thus it exploits commonality between triangles to generate vertex reuse
  • Unfortunately, many applications do not use efficient triangle (primitive) ordering.

VS/T&L: Vertex Shading/ Transformation & Lighting (Stage 3)

This stage perform vertex transformation and lighting effects.

  • Vertex Transform
    • Initially used to perform a fixed set of transformations like
      • Deformation
      • Warping
      • Procedural Animation
      • Range based Fog
      • Elevation based Fog
      • Lens effect
      • Morphing
      • Interpolation, etc.

Eventually, there was a need to have this programmable. This was hence called as “Vertex Shading” in general.

  • Vertex Shading
    • Programmable programs run on a per-vertex basis
    • One Vertex In [x y z w] → One Vertex Out [x’ y’ z’ w’]
      • Completely Data Parallel “Stream” Processing
  • Vertex Lighting
    • Generates a color value at each vertex.
    • Simplest: Application calculates and delivery an (R, G, B) triplet for each vertex.
    • Advanced/Typical: To accurately represent the physical world, the light sources are broken into 4-components
      • Ambient - uniform light from all directions
      • Emissive - light given off from the object itself
      • Specular - glossy, mirror like reflections
      • Diffuse - dull, matte-finish reflections

Triangle Setup (Stage 4)

  • Adds some information to every vertex so that later it can be used to determine color of fragments (pixels) within the triangle using interpolation. This step is performed per vertex to simplify per-fragment processing during rasterization.

Rasterization (Stage 5)

  • Rasterization is the process of determining which pixels (fragments) are contained in each triangle.
  • Note: Pixels within a triangle are referred to as fragments to differentiate them from pixels on the screen (or the frame buffer).
    • Reason: Different names are used since all fragments may not make it (due to blocking) on the screen.
  • Fragments are gathered using Point Sampling
    • A pixel belongs to a triangle if and only if the center of the pixel is located in the interior of the triangle
    • Evaluate 3 edge equations of the form E = Ax + By + C, where E = 0 is exactly on the line, and positive E is towards the interior of the triangle.
    • This is Data Parallel Processing
  • For each of these fragments, the rasterizer creates the necessary information for shading like,
    • Position
    • Color
    • Texture coordinates for each pixel
    • Pattern for rasterization (which helps fill the Texture Cache ahead of time)

Shading (Stage 6)

  • Operates on the set of fragments
  • Shading is assigning color values to the fragments
  • Color value can be determined by:
    • Interpolated Shading (e.g. Gouraud or Phong)
    • Texture Mapping
    • Per fragment lighting mathematics
    • Reflections
    • Complex shader programs
  • Shading also includes Texture Mapping

We now discuss some of the shading operation/methods which are used:

Gouraud Interpolation

  • Also called “smooth shading”
  • Gives a “diffused” or “plastic” look
  • Linearly vary the color values inside a triangle
  • More realistic that flat fading because the facets in the model are less obvious (due to linear interpolation)

Phong Interpolation

  • Gives a “metallic” look

Texture Mapping

  • Associate points in an image to points in a geometric object
  • A pixel in a texture image is called a “Texel”.

Mip Mapping

  • Technique to manage pixel level of detail (LOD)
  • Scaled versions of the original texture are generated and stored. These smaller stored textures are used are used for the texture samples as objects appear smaller with greater distance.
  • Complex processing can be used during mip-map generation so that simpler processing is done at run time (see below).

Various filtering techniques can be then applied to generate images (of any size) from the set of texture images we have stored.

Filtering Techniques

  • Point Sampling
    • Pixel values are calculated by choosing one texture pixel (texel) color.
    • Also known as “Nearest” filtering
    • “1 texel → 1 texel”
    • Problem: If we have a coarse texture (two pixels far off), then it produces bad results
  • Bilinear Filtering
    • Individual texel colors are interpolated from the 4 nearest texels of the closest mip-map
    • “4 texels → 1 texel”
    • Gives a smoothing (somewhat “blurry”) effect and makes the scene look more natural. Prevents abrupt transitions between adjacent pixels.
  • Trilinear Filtering
    • Individual texel colors are interpolated from bilinear interpolations of nearest adjacent mip-maps
    • “8 texels → 1 texel”
    • Prevents moving objects from displaying a distracting “sparkle” caused by abrupt transitions between mip-maps.
  • Anisotropic Filtering
    • A pixel is not really a point but has some dimensions too.
    • Interpolates and filters multiple samples from one or more mip-maps to better approximate very distorted textures
    • Gives a sharper effect when severe perspective correction is used
    • “multiple(16/32) texels → 1 texel”

The reason we can do Mip-Mapping and Filtering is because we can do it for different texels in parallel, i.e. Data Parallel Processing possible. Furthermore, we can exploit locality by using a texture cache. As long as we are in the same triangle, we get great locality (~75% hit rate). This large amount of parallelism enables efficient and effective hardware to accelerate the texture mapping process.

Pixel Shading

  • Direct X 7 (1999)
    • Applications could select from a few simple combinations of texture and interpolated color.
  • Direct X 9
    • Fully programmable
    • Program executes for every pixel with a nearly unlimited number of interpolated inputs, texture lookups and math operations
    • Can afford to perform sophisticated lighting calculations at every pixel

Texture Cache

  • Stores temporally local texel values to reduce bandwidth requirements
  • Due to nature of texture filtering, high degrees of efficiency are possible
  • Efficient texture caches can achieve 75% or better hit rates
  • Reduces a texture (memory) bandwidth by a factor of 4 for bilinear filtering
  • Uses word formations. Entire texture is cached at a time
  • Indexed by a “Texture ID” which contains, “Name, Level”.

Question: Textures of all levels (resolutions) are fetched from the GPU memory to the Texture cache. Why do we need to do this since we could effectively do mip-mapping with a higher resolution texture?

Answer: Although, this was initially done to save transfers, it turns out it actually gives better images. We are no longer saving on transfers (since we fetch all levels), but we gain on image quality.

ROP: Raster Operations (Stage 7)

  • Multiple texels can fall on the same pixel (overlapping objects etc). ROP stage combines the texels to form the actual pixels.
    • C-ROP performs frame buffer blending
      • Combinations of colors and transparency
      • Anti-Aliasing
        • Accounts for the contribution of all the primitives that intersect that pixel.
        • Avoid abrupt changes at primitive boundaries
      • Read/Modify/Write the color buffer
    • Z-ROP performs the hiding pixels
      • Determines the visible pixels and discards the occluded pixels
      • Read/Modify/Write the Z-buffer
    • ROP on GeForce also performs
      • “Coalescing” of transactions
      • Z-buffer compression/decompression

Alpha Blending

  • Used to render translucent objects
  • Pixels alpha component determines its opacity.
  • Pixel_Out = Alpha * Pixel_Src + (1 - Alpha) * Pixel_Dest
  • Read/Modify/Write operation to the color frame buffer

FBI: Frame Buffer Interface (Stage 8)

  • Manages reading and writing to the frame buffer
  • Turns out to be a very critical part since we have to render upto ~3 million pixels, 60 times a second.
  • GeForce’s FBI is a crossbar

The frame buffer and frame buffer interface form the main memory system of the GPU.

Color Frame Buffer “Display”

  • This is the primary determinant of graphics performance other than the GPU
  • Memory bandwidth is a key
  • It has
    • 2D array of R, G, B color pixel values
    • 8bits (256) levels per color components, i.e. 24 bit pixels
    • 16 million colors including 256 shades of gray
    • 4th component alpha used for alpha-blending
    • resolution upto 2048 x 1536
    • required refresh time ~60 fps

Programming GPUs

The two key steps where programmability can be added are vertex processing and fragment processing. A programmable GPU data/control flow is as shown below.

The vertex and fragment processing occur at different rates for different images and must be load balanced. Load balancing the hardware at design time yields suboptimal utilization leading GPU architects to adopt a unified set of processing elements(PEs) that can handle both vertices and fragments and be load balanced dynamically. Hence, we just need to load balance between the vertex and fragment processing in terms of the number of PEs working on each.

This concept of having a programmable fabric was embraced by both NVIDIA than AMD (ATI). Since, we have a programmable fabric, we can extend the GPU architecture to perform general computations.

Note: CUDA is a programming models for NVIDIA devices.

The following figure shows the programmable fabric architecture of the NVIDIA G80 GPU in the GeForce 8 series.

Further discussion on the GPU architecture would be done in subsequent lectures.

Summary + Next Lecture

Summary

This lecture provided an overview of what has happened in graphics and to learn how to leverage that for general purpose processors. The aim is to exploit locality and data parallelism to the greatest extent.

Next Lecture

  • NVIDIA GeForce 8800 architecture
  • CUDA programming model