Past exam of the computer science course of the University of Oxford / 2015 / Computer architecture / 1 / d

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.

Define PREFETCH [a] as a software prefetch hint: initiate a request for the cache line containing memory address a, then continue without waiting for that cache line to arrive. It produces no value in a destination processor register, changes no program data and creates no data-result dependence for later instructions. It may be ignored if resources are unavailable. A useful hint is nonfaulting for an inaccessible or untranslated target: a later real load instruction must still perform its ordinary access checks. This is a proposed contract for the instruction, rather than a guarantee that the patent abstract alone fixes every detail of its semantics.

For example, after reading the next pointer of a linked list node, prefetch that next linked list node while processing the current one. Replacing the hint by an otherwise unused ordinary load instruction on this in-order pipeline would wait in MEM on a cache miss before the current computation could start. It would also consume a destination processor register and might raise a synchronous processor exception. A harmless hint can be scheduled earlier, even on a path where the data will never be demanded. The crucial semantic difference is that cache filling may continue after the prefetch instruction itself has finished.

A software prefetch is not a memory barrier and does not establish acquire-release synchronization or promise that later accesses will hit. Its purpose is performance; correctness must survive the hint being ignored.

In IF, fetch PREFETCH normally. In ID, recognize its opcode, read the base processor register and immediate offset, and set controls selecting a prefetch request rather than a load instruction or store instruction. Ordinary register forwarding and data hazard interlocks still apply to that base processor register. In EX, use the arithmetic logic unit to form the effective memory address.

Latch that memory address and a prefetch-valid control into EX/MEM. In MEM, put the memory address and any hint information on the dedicated request computer bus, or enqueue them in a small prefetch-request queue. The cache prefetching engine handles lookup, allocation and the later cache line return independently. Do not wait for the fill or select the returned data as a register file input. In WB, disable architectural processor register and processor condition flag writes; the instruction simply leaves the in-order pipeline.

If the request path is busy, dropping the hint is compatible with the contract in part (ii), and preserves its nonblocking purpose. A design that instead stalls until queue space exists can still be correct but reduces the performance benefit. A memory management unit must not turn a speculative hint into an ordinary protection fault: discard an invalid target, or use an appropriately checked nonfaulting translation path. Suppress device transactions for memory-mapped input-output and avoid speculative writes. Use the existing address-generation datapath, add a prefetch request/control path, and disable demand-load waiting and writeback.

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.