Level 4 — ApplicationGPU Architecture

GPU Architecture

⏱ 60 minutes60 marksprintable — key stays hidden on paper

Level 4 (Application / Novel Problems) Time limit: 60 minutes Total marks: 60

Answer all questions. Show all working. Assume a CUDA-style GPU unless a question states otherwise. Where standard architectural constants are needed, state your assumptions.

Question 1 — Occupancy & Latency Hiding (12 marks)

You are tuning a kernel for an SM with the following per-SM limits:

65536 registers
65536 bytes shared memory
Max 2048 resident threads
Max 32 resident warps
Max 16 resident thread blocks
Warp size = 32

Your kernel uses 40 registers/thread, 4096 bytes shared memory/block, and a block size of 256 threads.

(a) Compute the maximum number of resident blocks per SM permitted by each of: register limit, shared-memory limit, thread limit, block limit. State the binding constraint. (6)

(b) Compute the achieved occupancy (as a percentage of the 32-warp maximum). (3)

(c) The GPU must hide a global-memory latency of 400 cycles. Each warp issues one independent long-latency instruction and then stalls. If the scheduler issues one warp per cycle and needs enough eligible warps to fully cover the latency, does your occupancy provide enough warps to hide it? Justify quantitatively. (3)

Question 2 — Coalescing & Bandwidth (14 marks)

A kernel reads a large array of 32-bit floats. Global memory transactions are serviced in 128-byte aligned segments. A warp = 32 threads.

(a) Thread i in a warp accesses element base + i. How many 128-byte transactions does one warp generate, and what is the bus utilization (useful bytes / bytes moved)? (3)

(b) Now the access pattern is base + i*stride with stride = 8 (elements). How many transactions per warp, and what is the utilization? (4)

(c) The device has a peak DRAM bandwidth of 900 GB/s. Your kernel's effective (measured) bandwidth is 300 GB/s using the pattern in (b). Estimate the effective bandwidth you would obtain by fixing the pattern to (a), assuming bandwidth scales with utilization up to the peak. State clearly why it caps. (4)

(d) Give two distinct code-level transformations (not "just coalesce") that could raise measured bandwidth for a strided-transpose-like workload, and explain the mechanism of each. (3)

Question 3 — Warp Divergence (10 marks)

Consider this device code executed by one warp (32 threads, tid = 0..31):

if (tid % 4 == 0)      A();   // costs 10 cycles
else if (tid % 4 == 1) B();   // costs 20 cycles
else                   C();   // costs 5 cycles

Assume each function is executed in lock-step by the active threads, inactive threads are masked, and branches within the warp are serialized.

(a) List the distinct execution paths taken and how many threads take each. (3)

(b) Compute the total cycle cost for this warp versus the ideal (fully converged) cost if all 32 threads had taken the cheapest common path. Express the divergence penalty as a slowdown factor relative to the divergent-free ideal of running all three bodies once. (4)

Question 4 — Bank Conflicts in Shared Memory (12 marks)

Shared memory has 32 banks, each 4 bytes wide; successive 4-byte words map to successive banks (word address mod 32).

(a) A warp accesses shmem[tid] (float array). Describe the conflict situation and the number of memory cycles (a conflict-free access = 1 cycle). (2)

(b) A warp accesses shmem[tid * 2]. Determine the bank each thread hits, the conflict degree (n-way), and cycles required. (4)

(c) A common fix is padding a tile from [32][32] to [32][33]. For a column access tile[tid][k] (fixed k, varying tid), show why the unpadded version is 32-way conflicted and the padded version is conflict-free. (4)

(d) Would padding help if the warp accessed tile[k][tid] (row access) in the unpadded array? Explain. (2)

Question 5 — Tensor Cores & Roofline Reasoning (12 marks)

A tensor core performs a 16×16×16 matrix-multiply-accumulate ( $D = A\cdot B + C$ ) per operation group.

(a) How many multiply-add operations (count a MAC as 2 FLOPs) does one such 16×16×16 MMA perform? (3)

(b) You must multiply two 1024×1024 FP16 matrices. How many 16×16×16 MMA tiles are required (assume perfect tiling, accumulation over the K dimension counted as separate MMAs)? (4)

(c) A GPU sustains 150 TFLOP/s on tensor cores and has 900 GB/s memory bandwidth. For the 1024×1024×1024 GEMM (FP16 inputs, 2 bytes each; ignore output write for arithmetic-intensity), compute the arithmetic intensity (FLOP/byte) assuming each input matrix is read exactly once, and determine whether the kernel is compute-bound or memory-bound. State the ridge-point intensity. (5)

Answer keyMark scheme & solutions

Question 1 (12)

(a) (6 — 1 per correct limit + 1 for stated binding) Warps/block = 256/32 = 8.

Registers: per block = 40 × 256 = 10240 regs. 65536 / 10240 = 6.4 → 6 blocks.
Shared memory: 65536 / 4096 = 16 blocks.
Threads: 2048 / 256 = 8 blocks.
Block limit: 16 blocks. Minimum = 6 → register limit is binding. (6 blocks)

(b) (3) Resident warps = 6 blocks × 8 warps = 48 warps, but SM caps at 32 warps. Since 6 blocks would need 48 warps > 32 cap → block count is further limited by the 32-warp cap: floor(32/8) = 4 blocks. Resident warps = 4 × 8 = 32. Occupancy = 32/32 = 100%. (Award full marks for recognizing the warp cap overrides; if student reports 6 blocks→48 warps capped at 32 = 100%, accept.)

(c) (3) To hide 400 cycles at 1 warp issue/cycle you need ~400 independent warp-issue slots' worth of work; with each warp providing 1 instruction before stalling, you need enough warps so total useful issue ≥ latency. With 32 resident warps and single-issue, 32 warps cover only 32 cycles per round — but if each warp has multiple independent instructions or the round re-issues, the requirement is roughly latency/(instr per warp). With only 1 long-latency instruction/warp, 32 warps ≠ 400 → not enough to fully hide 400-cycle latency; you'd need ILP or more instructions. Full occupancy (100%) is necessary but not sufficient here. (Accept quantitative statement: 32 < 400 ⇒ under-covered.)

Question 2 (14)

(a) (3) 32 threads × 4 bytes = 128 bytes contiguous, aligned to one 128-byte segment → 1 transaction. Useful = 128, moved = 128 → utilization = 100%.

(b) (4) stride 8 elements = 32 bytes between consecutive threads. Span = 31 × 32 + 4 = 996 bytes → ~8 distinct 128-byte segments touched (each segment holds 128/32 = 4 of the accessed words). 32 words / 4 per segment = 8 transactions. Useful = 128 bytes; moved = 8 × 128 = 1024 bytes → utilization = 128/1024 = 12.5%.

(c) (4) Bandwidth scales with utilization until hitting peak. Pattern (b): 300 GB/s at 12.5% utilization → the bus is moving 300/0.125 = 2400 GB/s of raw... this exceeds peak, so instead: measured useful BW = raw × util. Under (b), raw ≈ peak-limited. Simpler valid model: useful BW ∝ utilization, capped at peak. Ratio: (a) utilization/(b) utilization = 100/12.5 = 8×. Projected = 300 × 8 = 2400 GB/s, but this caps at peak 900 GB/s. So fixing the pattern yields ≈ 900 GB/s (compute-limited by DRAM peak, cannot exceed it). (4)

(d) (3, 1.5 each for any two)

Shared-memory tiling / staging: load coalesced into shared memory, then do strided/transpose reads from shared memory — converts uncoalesced global reads into coalesced ones plus fast on-chip access.
Vectorized loads (float4): each thread loads 128 bits, increasing bytes-per-transaction and reducing instruction/transaction count, improving effective bandwidth.
(Also acceptable: change memory layout to SoA / restructure to make consecutive threads access consecutive addresses.)

Question 3 (10)

(a) (3)

tid%4==0: tids 0,4,…,28 → 8 threads run A (10 cyc).
tid%4==1: tids 1,5,…,29 → 8 threads run B (20 cyc).
else (%4==2 or 3): tids 2,3,6,7,… → 16 threads run C (5 cyc).

(b) (4) Divergent serialized cost = A + B + C = 10 + 20 + 5 = 35 cycles (each path runs once, masked). Ideal fully-converged (cheapest common path, all 32 do one body) = 5 cycles if all took C. Slowdown vs that ideal = 35/5 = 7×. Relative to "run all three bodies once with no serialization overhead" the ideal is also 35 (since three disjoint groups must each execute its body) — so the inherent divergence penalty here is that the three bodies serialize instead of overlapping: 35 cycles serial vs 20 cycles if bodies could overlap in one pass (max of the three = 20). Penalty ≈ 35/20 = 1.75×. (Accept 7× against single-path ideal or 1.75× against max-body ideal, with reasoning.)

(c) (3) Sort/partition threads by branch outcome so that each warp contains threads taking the same path (e.g., stream-compaction / reorder data by tid%4 class). Then each warp is converged and pays only its single body's cost (10, 20, or 5). Resulting per-warp cost = that path's cost; no serialization → converged execution.

Question 4 (12)

(a) (2) shmem[tid]: thread t → bank t mod 32, all distinct banks 0–31. Conflict-free, 1 cycle.

(b) (4) shmem[tid*2]: bank = (2·tid) mod 32 = 0,2,4,…,62 mod 32 → banks 0,2,…,30,0,2,…,30. Each even bank hit by 2 threads → 2-way conflict → 2 cycles.

(c) (4) Unpadded tile[32][32]: element tile[r][c] at linear word r·32 + c; bank = (r·32+c) mod 32 = c mod 32. Column access tile[tid][k] varies r=tid, fixed c=k → bank = k for all 32 threads → 32-way conflict, 32 cycles. Padded tile[32][33]: linear word r·33 + c; bank = (r·33 + k) mod 32 = (r + k) mod 32 (since 33 mod 32 = 1). As r=tid ranges 0–31, (tid+k) mod 32 is a permutation → all distinct banks → conflict-free, 1 cycle.

(d) (2) Row access tile[k][tid]: bank = (k·W + tid) mod 32. In unpadded (W=32) → tid mod 32, already all-distinct → conflict-free; padding is unnecessary (and adds waste). So padding does not help / is not needed for row access — it targets column-access conflicts.

Question 5 (12)

(a) (3) 16×16×16 MMA computes a 16×16 output; each output element = sum of 16 MACs. Total MACs = 16·16·16 = 4096. FLOPs = 2 × 4096 = 8192 FLOPs.

(b) (4) Output 1024×1024 in 16×16 tiles: (1024/16)² = 64² = 4096 output tiles. K dimension = 1024/16 = 64 MMAs per output tile. Total = 4096 × 64 = 262144 MMA tiles. (Check: 262144 × 8192 FLOPs = 2.147×10⁹ = 2·1024³ ✓.)

(c) (5) FLOPs = 2·N³ = 2·1024³ = 2.147×10⁹ FLOP. Bytes read = 2 matrices × 1024² × 2 bytes = 2 × 1048576 × 2 = 4194304 bytes ≈ 4.19 MB. Arithmetic intensity = 2.147×10⁹ / 4.194×10⁶ = 512 FLOP/byte. Ridge point = peak compute / peak BW = 150×10¹² / 900×10⁹ = 166.7 FLOP/byte. Since 512 > 166.7 → compute-bound.

[
  {"claim":"Q1a register-limited blocks = 6","code":"regs=40*256; blocks=65536//regs; result=(blocks==6)"},
  {"claim":"Q1b achieved occupancy 100% (warp-cap limited to 4 blocks)","code":"warps_per_block=256//32; blocks=32//warps_per_block; occ=(blocks*warps_per_block)/32; result=(occ==1.0)"},
  {"claim":"Q2b strided transactions=8, utilization=12.5%","code":"trans=32//(128//32); util=128/(trans*128); result=(trans==8 and abs(util-0.125)<1e-9)"},
  {"claim":"Q3b divergent serialized cost=35 cycles","code":"result=(10+20+5==35)"},
  {"claim":"Q5a one MMA = 8192 FLOPs","code":"result=(2*16*16*16==8192)"},
  {"claim":"Q5b total MMA tiles = 262144","code":"tiles=(1024//16)**2 * (1024//16); result=(tiles==262144)"},
  {"claim":"Q5c arithmetic intensity 512 and ridge 166.67; compute-bound","code":"flops=2*1024**3; bytes=2*1024*1024*2; ai=flops/bytes; ridge=150e12/900e9; result=(abs(ai-512)<1e-6 and ai>ridge)"}
]