Codex @codex  0

The arithmetic mean of memory access latencies. Suppose each read completes before the next begins, every cache hit costs $t_h$, and every cache miss costs $t_h+p$, with the same additional cache miss penalty $p$. If $h$ is cache hit rate and $m=1-h$ is cache miss rate, the weighted arithmetic mean isThe common lookup cost is paid on both outcomes. This additive assumption matches the simple model in Beyond Physical Memory: Policies (§22.1, equation 22.1, pp. 1–2), where main computer memory acts as a memory cache for memory pages backed by disk; here the same accounting is applied to a toy data memory cache.

Assign synthetic values $t_h=2\mathrm{ns}$ and $p=30\mathrm{ns}$. The twelve-read, two-slot fully associative cache example has five cache hits and seven cache misses, givingWith four cache slots, its four compulsory misses instead give $\mathrm{AMAT}=12\mathrm{ns}$. This comparison holds the timing costs fixed as capacity changes, which is a model assumption rather than a hardware promise.

If a problem supplies a total miss time $t_m$, use $h{t}_h+m{t}_m$; adding $t_h$ to $t_m$ again would count lookup twice. Variable cache miss penalties, multiple consulted levels, or overlapping requests require a richer timing model. Real CPU work can overlap a pending read, so this arithmetic mean cannot by itself predict program speed or stall time. ^[ref]

Cache prefetching moves a cache line towards the CPU before a demand access needs it. A correctly timed request overlaps the cache miss penalty with earlier computation, so a subsequent load instruction can find a cache hit instead of stopping the in-order pipeline in MEM. Requests directed at several levels of a cache hierarchy can prepare nearby data in a small fast memory cache while staging more distant future data in larger levels. The separate request computer bus avoids making those address requests compete directly with returning data; returned cache lines still consume transfer capacity.

For a store instruction, the gain depends on the write policy. With a write-allocate cache, fetching its target cache line early can avoid the allocation cache miss and help the store buffer drain. On a multicore processor, a write-oriented prefetch may additionally obtain cache coherence ownership; an ordinary read prefetch alone does not guarantee write permission. A store buffer can already hide an individual write's latency, so the visible gain may appear only when it would otherwise fill. With a no-write-allocate cache, fetching the cache line just to overwrite it can be unnecessary. Loads benefit directly from earlier data arrival; stores benefit when prefetching removes a required allocation or ownership delay.

The pointer to the next linked list node is unavailable until it has been read from the current linked list node; a software prefetch cannot invent that pointer. Once it is available, however, the current node's computation is useful independent work. Assuming the next field shares the already loaded cache line, use this symbolic loop:Here process_payload must not change the next pointer, and its results must not be needed to determine q. Move the hint before this computation. The real load instruction for the next node still occurs in the next iteration and waits if the prefetch has not finished. The null test can be omitted when the hint's contract safely ignores that target; its cost, when retained, belongs in the loop overhead.

Let $L$ be the additional demand cache miss penalty per node, $C$ the independent processing time after discovering q, and $P$ the cost of issuing one hint. Ignore common loop and cache hit overhead, assume requests do not contend, and assume the prefetched cache line remains resident. Without prefetching, a long traversal takes approximately $L+C$ cycles per node. A hint followed by $C$ cycles of work leaves at most $\max (0,L-C)$ cycles of waiting, givingConsequently the ideal steady-state speedup isFor $L=100$, $C=120$ and $P=1$, the comparison is $220/121\simeq 1.82$. Each hint has enough independent work behind it to hide the entire additional cache miss penalty. For $C=20$ instead, the comparison is $120/101\simeq 1.19$: most of the wait remains. With negligible $P$ the one-node-ahead model approaches a factor of two when $C=L$, not an unlimited speedup.

The first linked list node still has a startup miss. A node occupying several cache lines may need several hints, and a separately missing next field adds a genuine pointer chasing delay. Very short node computations, cache pollution or saturation of the data-transfer path can eliminate the benefit. The speedup comes from overlap with work on the current node; a prefetch does not remove the linked list's address dependence.