Past exam of the computer science course of the University of Oxford / 2015 / Computer architecture (A10402W1)

Solutions to all three questions of the examination dated 6 June 2015. The cover permits answers to two questions.^[ref]

Register forwarding supplies a later instruction with a computed value before that value has reached the register file. It removes some read-after-write hazards without changing the program's meaning. Consider these symbolic machine instructions, with the destination first:In the five-stage in-order pipeline, the addition produces its result at the end of EX. In the next cycle the subtraction is in EX, although the addition has not yet reached WB. A bypass from the addition's EX/MEM pipeline register to the subtraction's arithmetic logic unit input supplies the new r1; the old value read in ID must be overridden.

The bypass control compares source and destination processor register identifiers and selects the youngest applicable older producer. It must also check that the producer actually writes that processor register. Forward the newest available result instead of waiting for its writeback. A load instruction is different: its value is normally available only at the end of MEM, so an immediately following dependent instruction still needs a pipeline stall in this five-stage arrangement.

A store buffer holds the memory address and value of a store instruction while the memory cache or backing computer memory completes the write. The in-order pipeline can continue after enqueueing the write, rather than waiting for a possibly long memory access latency. A full store buffer eventually causes a pipeline stall; buffering hides finite delays, not an indefinitely inadequate service rate.

Without a memory management unit, the comparison can use the actual physical addresses; there is no address translation or synonym problem to solve. Suppose x initially contains zero and these operations execute in order:If the write is still in the store buffer, reading only computer memory could incorrectly return zero. The load instruction searches older buffered store instructions for an overlapping memory address. If the newest matching write covers the requested bytes and its data are ready, store-to-load forwarding returns seven directly. With several pending writes to x, the youngest older matching write wins. If the relevant data are not ready, the load instruction waits; partial overlaps require merging the covered bytes or conservatively waiting for the writes to drain.

A load instruction from an unrelated address y can bypass those buffered writes, subject to the architecture's memory model. Buffer writes to overlap them with useful execution, but preserve each load's dependence on older writes to the same bytes. Device accesses through memory-mapped input-output need their specified ordering and should not be treated as ordinary cacheable computer memory.

Speculative execution allows younger instructions to proceed while some condition on an older instruction is unresolved. Here the prediction is that a store instruction will pass its memory management unit's protection and translation checks. Successful prediction avoids waiting; failure requires discarding younger work and taking the older instruction's synchronous processor exception. A result computed speculatively must not become an irreversible architectural change before it is safe.

In the displayed five-stage in-order pipeline, the store instruction's memory address is computed in EX and its memory operation is in MEM. Take the permission check to finish at the end of MEM, with a one-cycle cache hit, no data hazards and sufficient store buffer capacity. A concrete conservative implementation without speculative execution fetches no younger instruction until this check has passed. Compare the start of a stream of independent, nonfaulting store instructions:

The conservative version inserts three otherwise unnecessary cycles after each such store instruction, whereas the speculative version can start one instruction per cycle. For $N$ stores, counting through WB, the times are $4N+1$ and $N+4$ cycles. ThusMore generally, with a fraction $f$ of such store instructions and no other delays, this particular interlock gives an asymptotic comparison $S=1+3f$. The maximum is four, not five: the permission check is resolved in MEM, so waiting for the empty store WB stage is unnecessary.

The baseline's interlock position matters. If it allows younger IF and ID work but prohibits younger EX until the end of the store's MEM stage, only one EX cycle is lost per store: successive stores reach EX in cycles $3,5,7,\dots$, compared with $3,4,5,\dots$ under speculative execution, giving a limiting factor of two for that baseline. Holding at ID instead gives two lost cycles per store and a factor of three. The fourfold figure compares against a pipeline that stops younger fetch; an implementation that already permits younger front-end work has a smaller remaining benefit. The source specifies the five stages but does not prescribe this alternative's interlock position.^[ref]

On a protection failure detected at the end of MEM, younger instructions occupy EX, ID and IF and can be invalidated before their normal WB. Younger store instructions must also be prevented from draining from a store buffer before validation. Earlier updates to processor condition flags, if any, need delayed commitment or restoration too. This is what makes the prediction compatible with a precise exception; merely continuing to execute is insufficient.

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.

In the illustrated out-of-order execution scheme without a reorder buffer, a reservation station identifier acts as the producer tag for an outstanding result. A register renaming map and waiting operands in other reservation stations can refer to that tag. The tag must remain unique until the result has been broadcast and the required register file update has occurred.

For example, issue a slow multiplication producing r1 into reservation station S, then an addition r4 := r1 + r5 into another reservation station. The addition records S as the unresolved source of r1. Even after the multiplier has accepted its operands, the multiplication can take many cycles; S cannot be reassigned merely because its operands have left the reservation station. If an independent short instruction is assigned S and broadcasts first, the addition would mistake that unrelated value for the multiplication's result. A later multiplication result could likewise corrupt the new instruction's register renaming mapping.

Finishing execution is also insufficient if the result is waiting for common data bus access: consumers and the register file still name S until writeback. Keep the producer tag allocated through broadcast/writeback, so no younger result can masquerade as the outstanding producer. With a separate persistent producer tag, such as a reorder buffer entry or a physical register, a design can release the scheduling slot earlier; this changes the tag-ownership arrangement in the question.

A reorder buffer records instructions in program order, including those with no destination processor register. Each entry needs a completion state before instruction retirement can pass it. Thus a store instruction must report that its memory address and data are ready and whether execution detected a fault, even though it has no ordinary register file result.

Suppose an older division occupies the head of the reorder buffer, followed by a store instruction and an addition. The latter two can finish first. The store instruction's completion message identifies its reorder buffer entry, carries or identifies the buffered memory address and data, and supplies its status. The entry is then ready, but its write remains private until it is the oldest instruction allowed to commit. When the division retires successfully, the store instruction can commit to the store buffer or memory system, and the addition can subsequently retire. If the division faults, the younger store instruction is discarded without changing visible computer memory.

If the store instruction never reported completion, its reorder buffer entry would remain unready and block instruction retirement indefinitely. Conversely, treating it as completed at issue could commit missing data or suppress its later fault. The common data bus carries tagged completion information as well as register values. A false-predicated instruction also needs a completion indication even when it changes no data.

This answer uses the diagram's shared result/completion path. An architecture can instead provide a dedicated store queue completion path to the reorder buffer; there is no universal requirement to send store data over the same physical wires as arithmetic results. What is essential is delivery of the tagged completion and exception status before instruction retirement.

Consider a slow load instruction controlling one conditional addition, followed by independent work. The following is schematic A32 assembly language; the plain ADD and MUL forms shown do not update processor condition flags:Without branch prediction, the unresolved conditional branch prevents fetching beyond it until the load instruction, comparison and branch resolution complete. The multiplication does not depend on r0, yet the out-of-order execution machinery cannot execute it if it has not been fetched and issued.

Conditional execution removes that branch:ADDEQ adds one exactly when the zero flag from CMP is set; otherwise it preserves r2. The instruction stream has a known sequential continuation, so the CPU can fetch and issue the multiplication while the load instruction is outstanding. With available reservation stations and a free multiplier, independent multiplication overlaps the load instruction's latency.

Predication removes a control-flow obstacle to finding independent work; it does not resolve the slow load or its dependent condition earlier. The conditional addition must still select the correct result after the processor condition flags become known. The gain is especially useful for a short conditional region, since instructions whose predicates are false still occupy fetch and issue resources. On a strictly blocking in-order pipeline, a slow demand load instruction would still stop later work in MEM; the overlap here uses the question's out-of-order execution setting and a nonblocking memory path.

Treat the condition as another instruction operand. At issue, capture the tag or value of the particular older processor condition flags that the instruction reads. Later flag writers must not redirect that dependence. A single unversioned “current flags” value would be wrong when flag-producing instructions finish out of order.

Without a reorder buffer. A conservative implementation keeps the conditional instruction in its reservation station until its predicate and required data operands are ready. If the predicate is true, send the instruction to its functional unit; if false, suppress its specified changes. Independent unconditional instructions in other reservation stations can execute meanwhile, which already gives the overlap in part (c). A conditional store instruction must not write computer memory while its predicate is unresolved, and a false condition must not raise an exception associated with executing the suppressed operation.

Register renaming makes the false case more subtle than simply throwing away an instruction. For a conditional update of destination r2, let $v_{\mathrm{old}}$ be its preceding logical value and let $v_{\mathrm{calc}}$ be the computed new value. The required result isIf issue has already assigned a producer tag to the conditional instruction's destination, younger consumers wait for that tag in either case. Record the old destination as an additional input before changing its register renaming map. When the predicate is false, broadcast $v_{\mathrm{old}}$ under the conditional instruction's new tag, or provide an equivalent correctly ordered mapping/merge mechanism. Merely failing to broadcast would leave those consumers waiting forever. Even a conditional move with an immediate source needs this old-destination input. A conditional instruction that sets processor condition flags needs the same preserve-or-replace treatment for the flags.

With a reorder buffer. Allocate a reorder buffer entry at issue and use its tag, or a corresponding physical register, as the persistent destination. The CPU may use the same wait-for-predicate policy. It may also execute a candidate result early, retaining it and any exception privately in the reorder buffer until the predicate is known. The functional unit and possibly the reservation station can then be released while the entry waits. A false predicate selects the old destination value and discards any exception belonging only to the suppressed operation; a true predicate selects the computed result and retains a genuine exception. Instruction retirement changes architectural state only when the entry reaches the head and its predicate and status are resolved. Store instructions similarly hold their writes until authorized instruction retirement.

A reorder buffer by itself does not remove the destination ambiguity. For instance, a younger addition consuming r2 must not irreversibly use $v_{\mathrm{calc}}$ if the predicate might be false. It can wait for the merged $v_{\mathrm{out}}$. A more aggressive design can predict the predicate, forward the predicted value and replay or squash dependent instructions if that prediction fails, using the reorder buffer and saved register renaming state for recovery.

Performance comparison. Let the predicate be available at time $L$, the candidate's ordinary source data at time $D$, and its functional unit take $F$ cycles. Ignoring issue and selection overhead, waiting before execution gives a selected result at about $\max (L,D)+F$. Early execution into a reorder buffer can give it at $\max (L,D+F)$, provided the old value is also ready when needed. For $D=0$, $L=50$ and $F=20$, that is $70$ versus $50$ cycles. Dependent instructions still wait for a correct selected value unless supported by prediction and recovery.

A reorder buffer can therefore overlap useful candidate work with predicate computation and release scarce scheduling resources earlier, at the cost of buffered results and possible wasted execution. Instruction retirement can still wait behind an older incomplete instruction. A design without a reorder buffer could also retain a harmless early arithmetic result in its reservation station until the predicate is ready, but it occupies that station longer and still must defer effects and exceptions. The fundamental requirements are versioned predicate dependence, preservation of false-case values, and controlled commitment; the reorder buffer makes speculative completion and recovery more systematic.

A small memory cache close to the CPU can be accessed quickly, but cannot hold the entire useful data set. Increasing its capacity usually increases lookup, wiring and energy costs. A cache hierarchy combines a small fast first level with progressively larger levels that reduce the number of accesses reaching slow main computer memory.

In a simple serial two-level timing model, let $t_1$ be the first-level lookup time, $m_1$ its cache miss rate, $t_2$ the additional second-level lookup time, $m_2$ the second level's local cache miss rate conditional on a first-level miss, and $t_M$ the remaining main-memory cost. ThenThis average memory access time combines the common fast path with a rarer large-capacity path. Several levels balance hit latency, capacity, cost and traffic; making one cache very large does not preserve a tiny first-level hit time. Temporal locality and spatial locality make this arrangement useful.

Use two different shared locations x and y, initially zero, and two CPU cores. The following are architectural memory operations, with each result kept in its own processor register:

Each CPU core can retire its write into its own store buffer. Before either write drains, Core 0's load instruction misses its own store buffer because it asks for y, while Core 1's asks for x. Both can read the old shared values. Afterwards the buffers drain and both locations become one. ThusThere is no contradiction with cache coherence: each location still has an agreed write order. The unusual observation concerns ordering across two different locations. This is the standard store-buffering example, also permitted by total store order.^[ref]

On a single CPU core executing the two logical participants in an ordinary thread interleaving, the same pair of zero observations is impossible under the usual shared-buffer and own-write-forwarding behavior. To read y=0, Core-0's logical read must precede the other participant's write of y; to read x=0, the other read must precede the write of x. Combining these requirements with each participant's program order gives the impossible cycleIf a write is still buffered across a context switch on that single CPU core, a later read of the same address sees it through store-to-load forwarding rather than returning an older value. Hence separate store buffers on different CPU cores enable the observation; the comparison assumes ordinary coherent cacheable computer memory and no device accesses or additional writes. A locally completed store need not yet be visible to another core.

With O1, even readers must acquire and release the same mutex. Acquiring it normally uses an atomic read-modify-write on the lock's cache line; releasing writes that cache line again. As different CPU cores repeatedly read the data, ownership of the lock's cache line moves among them, causing cache coherence traffic and serializing the protected operations. If the lock shares a cache line with otherwise stable data, false sharing can also invalidate useful reader data. The actual data need not change for this lock traffic to occur.

With O2 and correctly ordered publication, readers perform only load instructions: copy p once into a processor register, then read that version of the data. Multiple CPU cores can keep read-only shared copies of its cache lines. No per-reader exclusive ownership transfer is needed. During an update, a writer fills newly allocated computer memory privately; the old version's cache lines remain unchanged for readers already using it. Publishing the new pointer writes p and invalidates cached copies of that pointer's cache line, but this occurs only on updates.

For many reads and rare updates, O2 avoids lock-line contention and permits concurrent readers, so it can be substantially faster. The costs are heap allocation, construction or copying of a whole replacement, first accesses to its newly populated cache lines, and deferred memory reclamation. Frequent updates or very large replacements can reverse the comparison. O1 can modify a small field in place and may then save copying and computer memory. These are workload-dependent comparisons, not a claim that removing every mutex always accelerates an operation.

O1 supplies mutual exclusion over each complete operation. A reader sees the protected state from a serial order of readers and writers; a writer can safely mutate the existing object while holding the common mutex. If an update reads the old state and modifies it, the entire read-modify-write can be protected against a lost update.

O2 has different semantics. Assume an indivisible aligned access to p, correct publication ordering, and no later mutation of a published version. A reader chooses one version when it loads p; the subsequent load instructions use the same saved pointer, so an overlapping writer need not block that reader. The reader may continue observing the old complete version after the writer has published the new one. A sufficiently specified snapshot read can still be linearizable, with the load of p as its linearization point: a read overlapping a write is allowed to come before that write in the abstract order. Thus reading an old version during overlap does not by itself prove failure of linearizability.

Multiple writers can each construct a valid replacement and race to publish it. If the operation is simply “replace the whole object”, atomic pointer stores give a last-publication order. If each writer instead computes a change from the previously published state, O2 alone does not preserve both changes. Two writers can both read a counter value zero, independently build a version containing one, and publish their respective versions; the final counter is one. A writer mutex or compare-and-swap with retry is needed when the required operation must avoid that lost update. Memory barriers alone do not provide this exclusion.

Releasing the old object's computer memory immediately after publishing a replacement is unsafe. For example:The final operation is a use-after-free: it may crash, see allocator metadata, or read a different object that reuses the same memory address. An atomic update of p does not update the reader's already copied pointer. Freeing the new object immediately would of course also invalidate p itself.

Publication and reclamation are separate: publish a fully initialized version, and retain every old version until all readers that might hold it have finished. A read-copy-update grace period or a suitable hazard pointer protocol can provide that lifetime guarantee; naive reference-count acquisition after loading an unprotected pointer can itself race with freeing. Correct memory barriers in part (iii) ensure visibility, not object lifetime.

Separate the two required orders. A writer must make all initialization store instructions to a fresh version visible before another CPU core can use the publication of its address. A reader must load p before the load instructions of fields addressed through the saved pointer. Assume ordinary coherent cacheable computer memory, atomic aligned pointer accesses, immutable published versions, and the lifetime guarantee from part (ii). The sequences below are architectural operations; a compiler must preserve the stated accesses and dependencies.

TSO. Total store order preserves store-to-store order, so initialization writes cannot become visible after the later pointer publication. It also preserves load-to-load order, so reading the pointer precedes reading its fields. Its store-to-load relaxation, illustrated in part (b), does not break either required ordering. ThereforeNo drain of every reader's store buffer and no explicit cache flush is required. This statement is about hardware ordering; unsynchronized ordinary C or C++ accesses to p would still need the language's atomic operation and acquire-release synchronization facilities to avoid a data race and unwanted compiler transformations.

Power/ARM. These weaker memory models can expose a new pointer before all the writer's initialization store instructions are visible. Put a write-ordering memory barrier between the last initialization write and the store of p. A sufficient sequence uses lwsync on POWER architecture or an appropriately scoped DMB, such as DMB ISH, on the ARMv7 ARM architecture family:The scope must include every participating CPU core. A broader full barrier is sufficient but can cost more. Without the writer barrier, observing the new p and stale initialization data is exactly the unwanted message-passing outcome.^[ref]

For the reader as actually specified, the saved pointer is an address dependency: the loaded value directly determines each subsequent field's memory address.Both POWER architecture and the relevant ARM memory models respect such dependent reads. Thus no additional reader hardware fence is needed when every data access retains this real address dependency. The writer's publication barrier together with the dependent reads supplies the necessary ordering. A mere test of p followed by unrelated fixed-address reads would be a control dependency, which is not sufficient here.^[ref]

If that address dependency is not retained, use an acquire operation or an explicit read-ordering memory barrier after loading p and before reading fields. DMB ISH on ARMv7 or lwsync on POWER architecture is a conservative sufficient choice for this load-to-load ordering; a suitable conditional branch followed by isync is another POWER acquire implementation. On later ARM instruction sets an acquire load instruction can express the reader requirement directly. Such stronger forms are often convenient even though they are not minimal for the dependent sequence in this question.

The minimal answer is a writer publication barrier on Power/ARM, with the stated reader's address dependence doing the read-side ordering; TSO needs neither extra hardware fence. None of these choices repairs an invalid pointer, premature memory reclamation, or a lost update between writers.