Use __builtin_prefetch to Manually Prefetch Memory

Topic Overview

Software Prefetch Hides Latency

__builtin_prefetch (GCC/Clang) and _mm_prefetch (Intel intrinsics) hint that the CPU should load a cache line before the load instruction executes. Compilers use this in hand-tuned memcpy and graph traversals when access patterns are predictable but not contiguous enough for hardware stride prefetchers.

How Far Ahead to Prefetch

Prefetch roughly 64/128 iterations ahead for memory-bound loops. Too early evicts useful lines; too late misses RAM latency hiding.

cCopy
Loading…

• Prefetch does nothing if the address is already resident
• Use locality hint 0 (no temporal locality) for streaming scans
• Measure: prefetch helps only when the loop is memory-bound
• Hardware prefetchers often beat manual hints on pure sequential access

Working Through the Exercise

Keep the relevant documentation open while you implement. When your output disagrees with the reference, trace one failing case by hand before changing random lines.

• Trace first: walk one failing input step by step
• Read the manual: skim the official doc for the mechanism named in this task
• Compare baselines: save measurements from the prior step so speedups are honest

Why for this exercise

You will add __builtin_prefetch to a memory-bound loop and compare timings with and without hints. This exercise asks you to find the prefetch distance that helps without polluting cache.

Your Task

__builtin_prefetch(&a[i + d]) asks for data d iterations ahead, so the memory latency overlaps useful work. If d is too small, the loop still waits. If d is too large, the prefetch is wasted or arrives long before it is needed. Build a cycle-level timing model of a loop over an array, with and without software prefetch, and find the best distance. Use sequential, strided and gather (random index) access patterns; gather is the case hardware prefetchers cannot predict.

Input

cCopy
Loading…

Model

• Iteration i accesses element idx[i], which lives in line idx[i] * ELEM / LINE. For seq, idx[i] = i. For stride, idx[i] = (i * S) mod N.
• gather starts from idx[i] = i and applies a Fisher. Yates shuffle, for i = N-1 down to 1, with x = x * 1103515245 + 12345 (unsigned 32-bit, starting from SEED, default 1, where 0 means 1) and j = (x >> 8) mod (i + 1).
• A line's data arrives L cycles after it is first requested, and then stays available for the rest of the run. There is no hardware prefetcher.
• Each iteration, with the clock at t:
  1. If D > 0 and i + D < N, prefetch element idx[i + D]'s line: request it if it was never requested (otherwise count a redundant prefetch). Either way this costs 1 cycle.
  2. Demand-access element idx[i]: request its line if needed. If the data is not there yet, stall until it arrives.
  3. Compute for W cycles.
• sweep picks the distance with the fewest total cycles (the first one on a tie) and compares it with the rule of thumb ceil(L / (W + 1)).

Output

cCopy
Loading…

The pattern name is sequential, strided or gather. Errors: elements: invalid (N must be 1..100000, the sizes positive), pattern: unknown X, pattern: stride must be positive, and distance D: must be >= 0.

Example

Input:

cCopy
Loading…

Output:

cCopy
Loading…

Requirements

1. Track the arrival time of every line, so a prefetch that is still in flight shortens the stall instead of hiding it completely.
2. Generate the gather index array with exactly the given shuffle, so every learner's run is identical.

Hidden tests cover gather access with one element per line (where prefetching matters most), a strided pattern, distances far too large, a machine with little work per element, a lower-latency memory, and invalid input.