Question 3 of 6: Cache Write Consistency, Instruction Encoding, and Multiplication Hardware

Question 3: Cache Write Consistency, Instruction Encoding, and Multiplication Hardware (20 marks)

Question text not reproduced: the examination questions are © Engineers and Geoscientists BC. Open the official past paper (linked at the top of this page) to read the question, then follow the worked solution below.

Given. (a) A write to a cached block that main memory does not yet reflect. (b) The two families of instruction-encoding width policy. (c) Two $n$-bit unsigned binary operands to be multiplied.

Find. (a) The policies that keep cache and memory consistent after a write. (b) Fixed- vs. variable-length encoding tradeoffs. (c) A hardware block diagram plus an algorithm flowchart for unsigned multiplication.

Approach. (a) contrast write-through and write-back (with a dirty bit); (b) weigh decode simplicity/pipeline-friendliness against code density; (c) build the classic shift-and-add multiplier — multiplicand register, shiftable multiplier/product pair, an adder, and a cycle counter — and drive it with a repeat-conditional-add-then-shift control flow.

1. Part (a) — cache/memory write consistency. Two standard policies exist. Write-through: every write to a cached block is immediately propagated to main memory as well as the cache, so memory is never stale; simple and safe (e.g. for multiprocessor coherence or DMA-shared data) but generates a memory write on every single store, which a write buffer can hide only partially under heavy write traffic. Write-back: a write updates only the cache line and sets a dirty bit; main memory is updated later, in one bulk write, only when that line is evicted (or explicitly flushed). This cuts memory traffic dramatically (repeated writes to the same line cost one eventual memory write, not many) but means memory can be stale at any moment, so any other agent that can see memory directly (another core, a DMA device) needs a coherence mechanism to either see the cache's copy or force a flush first. Write-through trades bus bandwidth for simplicity/always-consistent memory; write-back trades a dirty-bit and eviction-time bookkeeping for far less memory traffic.
2. Part (b) — fixed- vs. variable-length instruction encoding. Fixed-length: every instruction occupies the same number of bits. Pros: the fetch stage always knows exactly where the next instruction starts without first decoding the current one, decode logic is simple and fast, and pipelining is straightforward. Cons: every instruction must be as wide as the WIDEST one actually needed, so simple instructions waste bits/memory, and a fixed field width can eventually cap things like immediate size or register-file size. Variable-length: instructions are only as wide as the fields they actually need (opcode + however many operands, rounded to some minimum granularity). Pros: much better code density — the common, simple instructions stay short. Cons: the CPU cannot know where instruction $k{+}1$ begins until it has decoded (at least partially) instruction $k$, which greatly complicates fetch/decode and makes deep pipelining/superscalar issue harder, and decode hardware itself is more complex (multiple format cases). Fixed-length favours fetch/decode speed and pipelinability (the RISC choice); variable-length favours code density (the classic CISC choice).
3. Part (c) — unsigned binary multiplication: hardware and algorithm. The classic shift-and-add multiplier datapath (multiplying an $n$-bit multiplicand $M$ by an $n$-bit multiplier held in register $Q$, accumulating a $2n$-bit product across registers $A{:}Q$) is:
   Fig. 1 — Unsigned binary multiplier datapath: multiplicand register $M$, multiplier/low-product register $Q$ (shifts right, LSB $Q_0$ tested each cycle), $n$-bit adder, high-product/accumulator register $A$ (shifts right in lock-step with $Q$), and a down-counting sequence counter that ends the algorithm after $n$ cycles.
   The control algorithm repeatedly tests the multiplier's current low bit, conditionally adds the multiplicand into the accumulator, then shifts the whole $A{:}Q$ pair one place right (carrying $A$'s LSB into $Q$'s MSB), for $n$ iterations:
   Fig. 2 — Unsigned multiplication flowchart: $A\leftarrow0$, $\text{CTR}\leftarrow n$; each of the $n$ cycles conditionally adds $M$ into $A$ (when the tested bit $Q_0=1$), then right-shifts $A{:}Q$ by one bit and decrements the counter; the final $2n$-bit product is the concatenation $A{:}Q$.
   Worked micro-trace for $M=0011_2\,(3)$, $Q=0101_2\,(5)$, $n=4$: initialize $A=0000$. Cycle 1: $Q_0=1\Rightarrow A\leftarrow A+M=0011$; shift $A{:}Q\rightarrow A=0001,Q=1010$. Cycle 2: $Q_0=0$ (no add); shift $\rightarrow A=0000,Q=1101$. Cycle 3: $Q_0=1\Rightarrow A\leftarrow A+M=0011$; shift $\rightarrow A=0001,Q=1110$. Cycle 4: $Q_0=0$ (no add); shift $\rightarrow A=0000,Q=1111$. Final product $A{:}Q=00001111_2=\boxed{15}$, matching $3\times5=15$ exactly.