Memory Coalescing: The Key to GPU Bandwidth

Topic Overview

Coalescing Combines Warp Requests

A modern GPU can issue hundreds of billions of floating-point operations per second, but global memory bandwidth is typically 1-2 terabytes per second. With thousands of concurrent threads, each thread gets only a thin slice of that bandwidth unless accesses are merged efficiently.

Memory coalescing is the mechanism that combines requests from threads in the same warp into as few cache-line transactions as possible. Coalescing is about transaction count, not bytes transferred.

Three Access Patterns

Consider 32 threads in a warp, each reading a 4-byte integer with 128-byte cache lines:

cCopy
Loading…

For example, in pattern (a), threads 0-31 read addresses base+0 through base+124, all within one 128-byte line. In pattern (b), each thread touches a different line despite requesting the same total bytes.

• Coalesced: adjacent threads read adjacent addresses
• Strided: large stride (column-major matrix reads) destroys coalescing
• Misaligned: unaligned base splits one logical pattern across two lines
• Fix: read row-major, stage through shared memory to transpose

For This Exercise

You will implement a transaction counter for coalesced, strided, and misaligned patterns, then compare row-major vs column-major matrix reads. This task requires you to print a summary table with efficiency percentages. The analysis you build here is the same reasoning CUDA kernel authors apply when nvcc warns about uncoalesced global loads.

Your Task

When a warp executes a load, the hardware merges its 32 threads' addresses into as few memory transactions as possible. This is coalescing: global memory moves whole 32-byte sectors, grouped in 128-byte lines. Shared memory instead has 32 banks of 4-byte words: threads hitting different words in the same bank are serialized (a bank conflict), while threads reading the same word get a broadcast. Compute both costs for common access patterns.

Input

# starts a comment.

cCopy
Loading…

Rules

• Global loads: collect the distinct sectors (byte / 32) and lines (byte / 128) covered by every active thread's byte range. Then:
  • requested = N × SIZE;
  • moved = sectors × 32;
  • efficiency = requested / moved, as a percentage rounded half up to 1 decimal. It can exceed 100% when threads read the same bytes, which the hardware serves once.
• aos prints two lines: the array-of-structs load, then struct of arrays, same field, where thread t loads the field at t × FIELD_SIZE.
• Shared loads: bank = word mod 32. For each bank, count the distinct words the active threads read. The worst bank's count is the number of passes. 1 means no conflict.

Output

cCopy
Loading…

• Bank conflicts: the reported bank is the lowest-numbered bank with the worst count.
• Plurals: thread(s), sector(s), line(s).
• Errors:
  • active: 1-32
  • strided: BASE STRIDE [SIZE 1-16]
  • aos: STRUCT_SIZE FIELD_OFFSET FIELD_SIZE (the field must fit in the struct)
  • gather: SIZE ADDR..., gather: need N addresses, gather: addresses must be >= 0
  • shared: BASE_WORD STRIDE_WORDS, transpose: TILE PAD (TILE 1-64, PAD 0-8)
  • unknown command X

Example

Input:

cCopy
Loading…

Output:

cCopy
Loading…

Requirements

1. Count distinct sectors and lines. A misaligned base shifts the warp across one extra sector and line.
2. For banks, count distinct words, not threads. Same-word reads are broadcast and never conflict.

Hidden tests cover a misaligned base, large strides, 16-byte vector loads, a broadcast (stride 0), a partial warp, a gather, padded and unpadded transposes, and argument errors.