Recap - Streaming Model

  1. Use many slimmed down cores to run in parallel
  2. Pack core full of ALUs (by sharing instruction stream across groups of fragments). There are two options
    1. Explicit SIMD Vector instructions
    2. Implicit sharing managed by hardware - The scheduler will try and keep all cores busy as and when resources are available. This is not as efficient, but if the sw cannot explicitly do this, then the hw can help here.
  3. Avoid latency stalls by interleaving execution of many groups of fragments
    • Two things that can affect performance here
      1. Pipeline is not full
      2. Waiting on something to finish (i.e. stall)
    • If the following inequality is not satisfied, then the system will be bound by off-chip bandwitdh
      • {$ \begin{align} \frac {AI_{offchip}} {IPS_{peak}} \end{align} $} > {$ \begin{align} \frac {1} {BW_{offchip}} \end{align} $}
      • The above inequality basically says that you need to utilize your I/O well because it tends to be a high latency access.
    • You also dont want the ALU execution gate I/O accesses. In essence, you want a good balance and somehow interleave the I/O and ALU execution to keep all the components are busy as possible
    • One solution is to reorder threads in order to avoid stalls. Interleaving I/O requests with ALU kernels is a good way to keep all hardware busy
  4. Put a large amount of off-chip bandwidth
    • This obviously has a cost associated with it, and can be an option for designs that can absorb the cost.

Thread Issue in GPUs

Thread issue in GPUs is done in HW because we need high throughput and SW will not be very efficient at this. Issue needs to be quick and robust, and SW overhead would be too high. In addition, SW would have to do resource matching (manage needed resource vs available resource) and this can be very complicated in SW.

  • G80 does not support SW managed thread control

Caches

The main purpose of a cache in the GPU is to improve bandwidth. On-chip bandwidth is much higher than off-chip bandwidth, and therefore caches can provide data to multiple ALUs together, which in turn improves parallelism. Latency is not too significant of an issue for GPUs because it can hide latencies by using parallelism.

Fermi - follow-on architecture to G80

Block level diagram of the Fermi architecture.

Stream Multiprocessor

  • 512 total cores
    • 16 SMs per Fermi chip
    • 32 cores per SM (512 total)
  • L1 and L2 caches
    • 64KB of configurable L1 cache local for each SM. Non-coherent.
    • 786KB of L2 is global to all SMs and coherent.
  • Fused Multiply-Add (FMA) for Single and Double Precision ops.
  • New integer ALU optimized for 64-bit and extended precision ops
  • ECC
  • GDDR5 Memory
  • GigaThread Hardware Thread Scheduler - manages thousands of active threads simultaneously, allowing for fast context switching and overlapping execution of kernels across the SMs.

Memory Hierarchy

Fermi supports shared memory, two levels of on-chip caches and off-chip memory.

Shared memory - configurable between the L1

Each SM has 16KB of shared memory. The shared memory is divided into 16 banks of 32-bit words. CUDA uses shared memory as storage area visible to all threads in a thread block (both readable and writeable). In parallel machines, it’s common for many threads to simultaneously access memory. To reduce contention and maximize bandwidth, the G80 divides shared memory into banks. Each of these banks can service one request pre-cycle. In addition, the shared memory can service as many simultaneous memory accesses as there are banks (as long as each access is to a unique bank. Multiple accesses to the same bank result in bank conflicts and result in a serialization of accesses (unless the accesses are to the same word which results in a broadcast of the word to all requestors). Successive 32-bit words are assigned to successive banks (i.e. share-memory-address % 16 == bank-number).

The illustration above shows two possible memory access patterns that avoid bank conflicts.

The illustration above shows two possible memory access patterns with bank conflicts. It’s worth noting that bank conflicts only happen within a single half-warp. If there are no bank conflicts, shared memory can be as fast as registers. There are additional memory banking examples in the slides.

L1 - shared memory local to an SM.

  • Good fit for regular memory accesses for dense computations.
  • Low latency and high bandwidth is its biggest selling point.
  • SW managed.

L2 - global memory shared by all SMs.

  • Good for irregular patterns and communication between SMs.
  • Coherency protocol along with high bandwidth with relatively low latency is the upside here
  • Allows for faster context switching

Off-chip memory

  • GDDR5 Memory provides 2x improvement in peak speed over GDDR3

Execution core

There are 32 threads per warp, and they are executed together on one SM. This means all 32 threads must be executing the same instruction, because there’s only one sequencer for the SM, and all 32 move together. Furthermore, for each warp, its instructions are executed sequentially. In Fermi, the SM can execute 16 of these threads per cycle, and will take 2 cycles to execute all 32 threads. Since each warp essentially takes 2 cycles to compute, the scheduler has 2 cycles to figure out the next warp to schedule to the same SM again. As a result, the scheduler’s job becomes simpler. Fermi can compute two warps in parallel on each SM, there is an odd and even warp scheduler.

A thread block is essentially a collection of warps. This is also sometimes knows as a CTA (Cooperative Thread Array). A SM is given one, but potentially up to eight, thread block(s) to execute at a time. Each block an consist of a large number of threads (in the order of ~1K). However, a general rule of thumb number is 3 to 16 warps (96 to 512 threads). These warps can be executing different instructions, even though within the warp, all the threads execute the same instruction. Every cycle, one warp finished. Since there are 2 concurrent warps running, and each takes 2 cycles, the SM can issue a warp on each cycle. There is no delay when switching to a different warp at the end of the 2 cycles. The warp scheduling details are not released by NVidia, and are educated guesses.

All the thread blocks that go to the SMs execute the same program, called a kernel. (Note, this is a different notion from executing the same instruction in the program.) The GPU will execute all of the thread blocks for a given kernel, and then move on to the next kernel. Thread blocks within a kernel are arranged in a grid, and are addressed by two-dimensional indices.

Scheduling warps for execution

Each SM implements a hardware scoreboard scheduler to determine which warp to run next. (Note that because the scheduler chooses between warps, and not threads, it has much less work to do.) Warps which have all of the operands ready for its next instruction are eligible for execution. The scheduler uses a round-robin policy to select an eligible warp to execute.

The scoreboard keeps track of all register operands of all instructions in the instruction buffer to prevent hazards.

Once selected, the same instruction is executed for all 32 threads in the warp. This takes 2 cycles, because the SM has 16 SPs, which can process one thread per cycle.

In the case of a long-latency memory operation, the currently-executing warp can still proceed, as long as it doesn’t use the new data as an operand in its instructions.