Parallel Execution on GPUs: From Threads to Warp Scheduling

In the previous article, we looked at which results can be computed independently in element-wise operations, reductions, and matrix multiplication. How do we assign these divisible computations to a GPU? This time, we will explore how a common computation procedure is divided into individual executions, assigned to the GPU, and executed.

We will use NVIDIA GPUs as our reference, starting with a small vector addition example. First, we will see how each execution finds and processes its own data. We will then move through threads and blocks to the selection of instructions from ready warps.

One Computation Procedure for Many Outputs

Suppose we add values at matching positions in two vectors, A and B, and store them in a vector C. If A contains 1, 2, 3, and 4, and B contains 10, 20, 30, and 40, C will contain 11, 22, 33, and 44.

In Figure 1, the first output is computed with 1 + 10, and the second with 2 + 20. The values differ, but the procedure is the same: read two inputs at the same position, add them, and store the result at that position.

We will call the number indicating a data position an index. Numbering from 0 as in the figure, A[0] is the first value in A, and A[1] is the second. If we denote the position by i, the common procedure becomes: read A[i] and B[i], add them, and store the result in C[i].

As we saw in the previous article, computing C[1] does not require the result of C[0]. We could have one execution process all positions in sequence, but we can also divide the work into multiple executions, each responsible for a different position.

Threads: Executing the Same Procedure on Their Own Data

Let us divide the common procedure into three executions. We assign i = 0 to the first, i = 1 to the second, and i = 2 to the third. Each execution proceeds from reading the inputs at its assigned position to storing its result.

This individual flow of execution that performs a computation procedure is called a thread. Figure 2 shows three threads that perform the same procedure but process different data because their indices differ.

Thread 0 reads 1 from A[0] and 10 from B[0]. It adds them to obtain 11 and stores it in C[0]. Thread 1 follows the same procedure but uses A[1] and B[1], so it stores 22 in C[1]. We do not write a different formula for every thread; each thread determines which data position to use within the same procedure.

A function that implements this common procedure for execution on the GPU is called a kernel. When a kernel is launched, multiple threads execute its code. Each thread proceeds with its own state, including the index it uses, the values it has read, and its intermediate results.

Here, we assigned one output to each thread. A thread is an individual flow of execution, so it can also be written to compute multiple outputs. For this example, we will keep one output per thread and look at how each thread calculates its assigned index.

Blocks and Grids: Grouping Executions and Finding Assigned Positions

With 1,024 outputs, this arrangement requires 1,024 threads. When launching a kernel, the developer groups these threads into groups of a chosen size. This group of threads is called a block. Here, we will put 128 threads in each block, so processing 1,024 outputs requires eight blocks.

All the blocks belonging to one kernel execution form a grid. This execution therefore consists of one grid containing eight blocks, with 128 threads per block.

Each block has a block ID, its number within the grid. Each thread also has a thread ID, its number within its own block. Thread IDs start again from 0 in each block, so block 0 has a thread 0, and block 1 also has a thread 0. We can use both IDs together to give these two executions different data to process.

In Figure 3, block 0 handles positions 0–127, and block 1 handles positions 128–255. Each thread finds its assigned position by adding its thread ID within the block to the block’s starting position.

Assigned position i = block ID × threads per block + thread ID within the block

Let us follow thread 0 in block 1. With 128 threads per block, i = 1 × 128 + 0 = 128. The thread uses 128 for i in the common procedure: it reads A[128] and B[128], adds them, and stores the result in C[128]. The neighboring thread 1 calculates i = 129 and processes the next position.

In this way, IDs are used to locate the data each execution will process. CUDA makes a thread’s block ID, thread ID, and block size available within the kernel. The developer uses these values in calculations to determine each thread’s work.

The block size is chosen by the implementation and launch of the kernel. If we keep 128 threads per block but increase the input length to 2,048, we need 16 blocks. So far, we have defined how to organize many individual executions. Next, we will look at how the GPU assigns these blocks to SMs.

Blocks: Assignment to SMs and Resource Allocation

In our earlier discussion of GPU architecture, we saw that a GPU contains multiple SMs, each with compute units, registers, and L1 cache and shared memory. The GPU assigns blocks to SMs, and the threads of a single block execute on the same SM. Work is described as resident when it has been assigned to an SM and occupies the resources needed for execution.

In Figure 4, blocks 0 and 1 are assigned to SM 1, and blocks 2 and 3 to SM 2. An SM can have multiple resident blocks, as many as its resources allow, rather than being limited to one.

Resident work uses the SM’s storage resources. Registers hold the values and intermediate results used by each thread. In the individual executions from Figure 2, each thread needs its own input values and computed result. The physical register resources are within the SM, while the values stored in them are kept separately for each thread.

A block is a unit assigned together to an SM, and it also defines a group of threads that can cooperate. Shared memory is storage that threads in the same block can use to share data and cooperate. In our vector addition, each thread only needs to read and compute with its own inputs. In a computation where several threads produce partial sums and then combine them, they can place intermediate values in this storage.

Before a thread reads a partial sum produced by another thread, that value must be ready. Coordinating execution so that the required work is complete before moving to the next step is called synchronization. Threads in the same block can share data and synchronize to divide up a computation.

The L1 cache serves memory accesses from multiple blocks on the same SM. Shared memory and the L1 cache divide the unified storage we discussed earlier, but they have different roles: one is used explicitly by threads to share data, while the other is a hardware-managed cache.

An SM’s resources are limited. If work already assigned to it uses many registers or a large amount of shared memory, there may not be enough room for another block. Blocks 4 through 7 at the top of the figure have not yet been assigned. When a running block completes and releases its resources, another waiting block can be assigned. Therefore, having many blocks in a grid does not mean that they all reside on SMs at the same time. The number that can be resident depends on hardware limits on blocks and threads as well as resource usage.

Warps: Executing Instructions Across 32 Threads

Once a block has been assigned to an SM, how do its threads execute? NVIDIA GPUs schedule instructions in units called warps, each grouping 32 threads from the same block. In Figure 5, a block of 128 threads is divided into four warps.

In a block with threads arranged in one dimension, as in this example, thread IDs 0–31 belong to warp 0, and 32–63 to warp 1. Within the developer’s 128-thread block, the GPU executes instructions in groups of 32.

Let us zoom in on four threads in warp 0. Thread 0 computes 1 + 10, and thread 1 computes 2 + 20. The other two threads also add their own inputs. The instruction is the same addition, but the values it uses and the results it produces differ for each thread.

The GPU applies a common instruction to multiple threads in this way. This is called SIMT (Single Instruction, Multiple Threads). All threads can participate in the same addition, as in the figure, or only some may participate in an instruction depending on a conditional branch.

In Figure 2, we viewed reading inputs through storing the result as the flow of one thread. Figure 5 shows the moment when an addition instruction within that flow is applied to multiple threads together. A thread is an execution flow that performs computation, while a CUDA Core is a physical compute unit that processes instructions. Each thread does not occupy its own dedicated CUDA Core.

Putting this together, blocks are the units assigned to SMs, and warps are the units used to schedule instructions within an SM. When multiple warps reside on an SM, which warp’s instruction should execute next?

Warp Scheduling: Selecting a Ready Next Instruction

Inside the SM, a warp scheduler selects a warp that is ready to execute its next instruction from among the warps it manages. Sending the selected instruction to an execution unit is called instruction issue. The result of an issued instruction becomes available later, after execution.

An SM has multiple warp schedulers. Figure 6 shows four warps managed by one of them and the selection of the next instruction.

Warp A is waiting for a value to be read from memory. If its next addition needs that value, it cannot execute the addition yet. Warp C is waiting at a synchronization point for work by other threads to be ready. B and D, in contrast, are ready to proceed with their next instructions.

At this moment, four warps are resident, but only two are eligible for execution. The scheduler selects B and issues its next instruction. D is also ready but is not selected this time. Waiting for a condition to proceed, as A and C are doing, differs from being ready but not selected, as D is. To be eligible for execution, a warp needs both the required inputs and results of earlier computations, as well as an available execution resource to process the instruction.

The selection is for the next instruction a warp will perform. The scheduler does not have to keep executing B until all of B’s work is complete. After issuing B’s instruction, it may select D from the ready candidates at the next opportunity. Whether another instruction can be issued while an earlier one is still in progress depends on instruction dependencies and execution resources.

The register values and execution state of waiting warps also remain within the SM. The scheduler selects the next instruction from warps whose state is maintained there. When the conditions a waiting warp needs to proceed are satisfied, it becomes eligible again.

Latency Hiding: Making Progress While Waiting

Let us connect this to memory access latency. Time passes between requesting a value from memory and being able to use it. Even if the computation that needs the value is waiting, computations in other ready warps can proceed.

In the top half of Figure 7, A requests a memory read. Its next addition requires that input, so it waits for the data to arrive. Meanwhile, the scheduler issues instructions from the ready warps B and D. Once A’s input is ready, A’s addition can also be selected for execution.

In the bottom half, the other warps are all waiting along with A. With no eligible candidates, the scheduler cannot issue a new instruction. Previously issued memory requests or computations may still be in progress, but this scheduler has no additional instruction to send to an execution unit.

We assume that A waits for its data for the same amount of time in both cases. The difference is whether other work makes progress during that time. Reducing the impact of a wait by executing other work is called latency hiding.

More resident warps provide opportunities to select other work. But if all those warps are waiting at the same time, there are no eligible candidates. To understand GPU execution, we therefore need to consider both how much work has been assigned and how much of it can make progress right now. This is why grouping and managing many threads and selecting instructions from ready warps matters.

In the next article, we will use this execution structure to examine how to divide work to use the GPU more efficiently. We will connect the amount of computation assigned to each piece of work, the data movement it requires, and reuse of the data brought in, using element-wise operations and matrix multiplication.