TL;DR: Analyze one executed memory instruction at a time. Count every byte range it touches, preserve lane IDs when inferring stride, and report lane-requested bytes separately from distinct bytes. A broadcast can request the same four bytes 32 times; calling that 400% efficient is misleading. Sector footprint describes an address pattern, not cache misses, DRAM transactions or runtime.
How to approach it
First define the trace contract: at most 32 lane slots, None for an inactive lane and one access width for the instruction. Compute byte and sector unions. Then check whether addresses follow a constant stride per lane by dividing address differences by lane-ID differences. Show the ambiguous cases before summarizing a stream of instructions.
A strong answer
A trace analyzer reports one sector for a four-byte access starting at byte 30. It also reports efficiency above 100% for broadcasts. Both errors come from using a convenient shortcut without defining what the numerator and denominator mean.
Three quantities, three meanings
For each active lane, its byte interval is [address, address + width). The union of these intervals gives distinct requested bytes. The sum of their lengths gives lane demand, which includes duplicates. The set of 32-byte sectors intersecting the intervals gives the request footprint. The same method can count intersected 128-byte address regions, without claiming that every region causes a cache-line fill.
Memory Coalescing explains the sector model. NVIDIA's guide scopes the modern model to the relevant compute capabilities; an abstract trace does not itself prove how an unaligned source access was lowered into machine instructions. Use the actual instruction trace when matching a profiler.
A classifier with an explicit contract
This implementation accepts widths of 1, 2, 4, 8 or 16 bytes and up to 32 lane slots. It models reads. It does not certify overlapping stores as safe, infer instruction widths from source code or model caching.
from fractions import Fraction
def classify(addrs: list[int | None], width: int) -> dict:
if type(width) is not int or width not in (1, 2, 4, 8, 16):
raise ValueError("unsupported instruction width")
if len(addrs) > 32:
raise ValueError("at most 32 lane slots")
if any(a is not None and (type(a) is not int or a < 0) for a in addrs):
raise ValueError("addresses must be nonnegative integers or None")
active = [(lane, a) for lane, a in enumerate(addrs) if a is not None]
byte_union = {b for _, a in active for b in range(a, a + width)}
sectors = {b // 32 for b in byte_union}
lines = {b // 128 for b in byte_union}
stride = None
if not active:
pattern = "empty"
elif len(active) == 1:
pattern = "single"
else:
steps = {Fraction(b - a, j - i)
for (i, a), (j, b) in zip(active, active[1:])}
if len(steps) != 1:
pattern = "irregular"
else:
stride = next(iter(steps))
pattern = ("broadcast" if stride == 0 else
"contiguous" if stride == width else
"reverse-contiguous" if stride == -width else
"strided")
footprint = 32 * len(sectors)
return {"pattern": pattern, "stride_bytes_per_lane": stride,
"active_lanes": len(active), "sectors": len(sectors),
"address_regions_128b": len(lines),
"lane_bytes": len(active) * width,
"unique_bytes": len(byte_union),
"unique_fraction": len(byte_union) / footprint if footprint else 0.0}
def summarize(trace) -> dict:
sectors = unique = lane_bytes = 0
max_sectors = None
for index, (width, addresses) in enumerate(trace):
r = classify(addresses, width)
sectors += r["sectors"]
unique += r["unique_bytes"]
lane_bytes += r["lane_bytes"]
if max_sectors is None or r["sectors"] > max_sectors[1]["sectors"]:
max_sectors = (index, r)
return {"sectors": sectors, "unique_bytes_per_instruction_sum": unique,
"lane_bytes": lane_bytes,
"unique_fraction": unique / (32 * sectors) if sectors else 0.0,
"max_sector_instruction": max_sectors}
Fraction avoids floating-point comparisons when active lane gaps differ. A stride is measured per lane ID, not per surviving entry after removing inactive slots. For addresses [0, None, 8, 12] with width four, the observed active lanes follow the contiguous mapping address = 4 × lane. The missing lane says nothing about whether it would have accessed valid data; it simply contributes no request.
32 addresses 4096 + 4t, width 4: contiguous, 4 sectors, 128 unique bytes
same addresses shifted by 4: contiguous, 5 sectors, unique fraction 0.8
32 addresses 4096 + 128t: strided, 32 sectors, unique fraction 0.125
32 copies of address 4096: broadcast, 1 sector, lane bytes 128, unique bytes 4
one address 30, width 4: single, 2 sectors, unique fraction 4/64 = 0.0625
sanity: unique fraction never exceeds 1; lane demand may exceed the footprint.
A broadcast's 12.5% distinct-byte fraction is not an optimization failure: one fetched word serves many lanes. Report the pattern and both byte counts so the consumer can interpret it. A permutation of nearby addresses may be irregular in lane order yet coalesce into few sectors; “irregular” does not prove random generation or high cost.
Summaries should not invent a cache model
The reducer accepts an iterable and retains only totals plus one maximum-sector instruction. Ties retain the first. Its distinct-byte total is a sum over instructions, not the union of addresses across the entire trace. Repeated accesses are intentionally counted again because caching is a separate layer of analysis. At most 32 lanes times 16 bytes are expanded per instruction, so working memory is bounded by this contract rather than trace length.
For a frequency-compressed trace, weight each record by its execution count; the reducer above expects one record per dynamic instruction. Maximum sectors alone does not identify the best optimization: frequency, dependencies and cache misses determine the exposed cost. Nsight Compute reports hardware counters and request/miss behavior; it does not reconstruct this exact Python algorithm from a full address list.
Profiling with Nsight connects these results to the actual memory hierarchy. Compare one source instruction with the same active mask and width before interpreting disagreements. If the input contains only lane zero's address, do not manufacture the other 31 addresses: request a richer trace or state the inference assumptions. That is the point where the classifier's answer must become “insufficient data.”
Use this analyzer to identify patterns worth investigating. Reverse a proposed layout optimization when the profiler shows the sectors are mostly reused, or when reordering costs more than it saves. The classifier should produce reliable evidence, not an unsupported speedup recommendation.
What interviewers probe next
- "Why expand the byte interval?" A wide or unaligned abstract access can intersect more than its starting sector.
- "What about inactive lanes?" Preserve their slot positions for stride inference; exclude them from requested bytes.
- "Why not sort addresses?" Sorting destroys lane-to-address mapping and can turn an irregular access into an apparently contiguous one.
Common mistakes
- Counting only starting sectors or assuming every trace has four-byte accesses.
- Dividing duplicated lane bytes by fetched bytes and calling the result bounded efficiency.
- Treating the largest footprint as the slowest instruction without timing or cache evidence.
Key takeaways
- Address 30 with width four touches two sectors, not one.
- A 32-lane broadcast has 128 lane bytes but only four distinct bytes.
- Mask-aware stride uses address delta divided by lane-ID delta; sector counts remain independent of the label.