TL;DR: For each warp-level memory instruction you have up to 32 addresses (some lanes inactive) and an access width. Two computations answer everything. First, sectors touched: map each active address to its 32-byte sector (
addr // 32), take the set, and the size is the number of memory transactions; the useful bytes are active lanes × width; efficiency is useful ÷ (sectors × 32). Second, the pattern: sort active addresses by lane, take consecutive deltas; if all deltas equal the width it is contiguous (coalesced); if all deltas are equal to some other constant it is strided with that stride; otherwise random. Report both, because the label alone misleads: a contiguous access that is misaligned costs 5 sectors instead of 4, and a "random" access whose addresses all fall in two sectors is cheap. The classifier is 30 lines of Python; the edge cases are inactive lanes (skip them, do not count deltas across them), 8- and 16-byte accesses (the width changes the ideal sector count), and instructions where lanes hit the same address (broadcast, one sector).
How to approach it
Restate the input format and what you will output. Compute sectors first because it is pattern-independent. Then the delta test with the tolerance rules. Write the code. Then walk three examples through it and discuss the edge cases and what a summary over a whole trace looks like.
A strong answer
A typical situation: the interviewer pastes a trace of a few warp instructions with 32 hex addresses each and asks for the pattern of each, then asks the candidate to code it and to say which instruction is the most expensive.
The two computations:
input per instruction: width (4, 8 or 16 bytes), a list of 32 entries: address or None (inactive lane)
sectors: S = |{ a // 32 : a in active }|; also lines L = |{ a // 128 }|
useful bytes U = |active| × width; fetched bytes F = S × 32; efficiency E = U / F
ideal sectors for a fully active warp: 32 × width / 32 = width (4 for 4-byte, 8 for 8-byte, 16 for 16-byte)
pattern from deltas: take active (lane, addr) pairs in lane order; d_k = addr_{k+1} − addr_k over adjacent active lanes
all d_k == width → contiguous (and check alignment: addr_0 % 32 == 0 → aligned, else misaligned)
all d_k == c, c != width → strided, stride c bytes (c / width elements); note c < width means overlapping,
c == 0 means broadcast (all lanes same address, 1 sector)
else → irregular; report S so the cost is still known
sanity: a contiguous 32-lane load of 4-byte elements touches 128 B = 4 sectors; the same warp
strided by 32 elements touches 32 sectors, 8x the traffic for the same 128 B of useful data
The code:
from dataclasses import dataclass
@dataclass
class Result:
pattern: str # "contiguous" | "strided" | "broadcast" | "irregular"
stride_bytes: int | None
sectors: int
lines: int
useful_bytes: int
efficiency: float
aligned: bool
def classify(addrs: list[int | None], width: int) -> Result:
active = [(lane, a) for lane, a in enumerate(addrs) if a is not None]
if not active:
return Result("empty", None, 0, 0, 0, 0.0, True)
sectors = {a // 32 for _, a in active}
lines = {a // 128 for _, a in active}
useful = len(active) * width
eff = useful / (len(sectors) * 32)
aligned = (active[0][1] % 32) == 0
deltas = [active[k + 1][1] - active[k][1] for k in range(len(active) - 1)]
if not deltas: # one active lane
return Result("contiguous", width, len(sectors), len(lines), useful, eff, aligned)
if all(d == 0 for d in deltas):
return Result("broadcast", 0, len(sectors), len(lines), useful, eff, aligned)
if all(d == width for d in deltas):
return Result("contiguous", width, len(sectors), len(lines), useful, eff, aligned)
if all(d == deltas[0] for d in deltas):
return Result("strided", deltas[0], len(sectors), len(lines), useful, eff, aligned)
return Result("irregular", None, len(sectors), len(lines), useful, eff, aligned)
def summarize(trace: list[tuple[int, list[int | None]]]) -> dict:
"""trace: [(width, addrs), ...]; returns totals and the worst instruction."""
total_sectors = total_useful = 0
worst = None
for idx, (width, addrs) in enumerate(trace):
r = classify(addrs, width)
total_sectors += r.sectors
total_useful += r.useful_bytes
if worst is None or r.sectors > worst[1].sectors:
worst = (idx, r)
return {"sectors": total_sectors, "useful_bytes": total_useful,
"efficiency": total_useful / (32 * total_sectors) if total_sectors else 0.0,
"worst_instruction": worst}
Three examples through it:
1. width 4, addrs = [0x1000 + 4t for t in 0..31]
deltas all 4 → contiguous; sectors {0x80..0x83} = 4; useful 128; efficiency 1.0; aligned (0x1000 % 32 == 0)
2. width 4, addrs = [0x1000 + 128t] (column of a 32-float-wide row-major matrix)
deltas all 128 → strided, 128 bytes = 32 elements; sectors 32; useful 128; efficiency 0.125
3. width 4, addrs = [0x1004 + 4t] (contiguous but misaligned by 4 bytes)
contiguous; sectors: 0x1004..0x1080 spans sectors 0x80..0x84 → 5; efficiency 128/160 = 0.8; aligned False
4. width 4, addrs random within one 128-byte line
irregular by deltas; sectors ≤ 4; efficiency up to 1.0 → the label says irregular and the cost says cheap,
which is why both are reported
Memory Coalescing is the model the classifier implements; Memory Coalescing and How to See It (the companion question) has the profiler's version of the same numbers.
Edge cases the interviewer will raise, and the handling:
inactive lanes: excluded from both computations; deltas are between adjacent active lanes only (a gap of one inactive
lane between contiguous addresses shows a delta of 2 × width; the strict rule calls it strided; a tolerant rule
accepts deltas of width × (lane gap) as contiguous; state which you chose)
widths: 8-byte and 16-byte accesses have ideal sector counts of 8 and 16; efficiency is the fair comparison across widths
partial sectors at the ends: a contiguous but misaligned access touches one extra sector; the classifier reports it
through the sector count and the aligned flag
same address across lanes (broadcast): one sector; common for reading a scalar from global memory; cheap
stores: same arithmetic; partially written sectors cost a read-modify-write at L2, so efficiency understates the cost
multiple instructions to one line: the L1 cache may serve the second from the first's fill; the classifier counts per
instruction and a cache model is a separate step; say so rather than over-claim
trace scale: millions of instructions; the summary streams and keeps running totals plus a top-k of expensive
instructions by sectors, not a list of every result
Profiling with Nsight is where the same numbers come from in practice (sectors per request), and the classifier is what the profiler computes from hardware counters; the interview version exists to check the candidate can derive it.
The reversal condition: if the trace records only the first lane's address per instruction (some tools do), the sector computation is impossible and the pattern must be inferred from consecutive instructions in a loop; the candidate should ask what the trace contains before writing code.
What interviewers probe next
- "Which instruction should the engineer fix first?" The one with the most sectors weighted by how many times it executes; the summary's worst-instruction plus an execution count from the trace.
- "How do you tell a coalesced access of a 2D tile from a strided one?" Within one warp instruction, a 32 × 4-byte row is contiguous; the tile shape shows across instructions. The classifier is per instruction by design.
- "What about shared memory?" A different model (banks, not sectors); the same delta logic with a 4-byte bank width and modulo 32 finds bank conflicts, which is a good follow-up to offer.
- "Can you do it in the kernel itself?" Yes, with warp intrinsics: each lane shares its address via shuffles and lane 0 computes the sector set; useful for instrumentation builds.
Common mistakes
- Labeling by deltas only and never computing sectors, so a misaligned contiguous access reads as free.
- Counting deltas across inactive lanes and mislabeling a masked contiguous access as strided.
- Assuming 4-byte width for every instruction.
- A per-instruction list as the output for a trace with millions of entries.
Key takeaways
- Sectors touched is the cost; efficiency = useful bytes ÷ (sectors × 32); compute it first.
- Pattern from lane-ordered deltas between active lanes: equal to width is contiguous, constant otherwise is strided, else irregular; zero is broadcast.
- Handle inactive lanes, access width, alignment and broadcast explicitly.
- Summarize with totals and the most expensive instructions, not a list.