Question 3 of 6: Cache Write Policy, Instruction Encoding Length, and Binary Division Hardware

Question 3: Cache Write Policy, Instruction Encoding Length, and Binary Division 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 cache whose lines can be modified by CPU writes. (b) The two families of instruction-encoding width policy. (c) Two unsigned binary operands (dividend, divisor) to be divided by hardware.

Find. (a) The common write policies and their performance impact. (b) Fixed- vs. variable-length encoding tradeoffs. (c) A flowchart (with supporting hardware) for unsigned binary division, explained step by step.

Approach. (a) contrast write-through/write-back and write-allocate/no-write-allocate; (b) weigh decode simplicity/pipelining against code density; (c) build the classic restoring-division datapath — remainder register $A$, dividend/quotient register $Q$, divisor register $M$, a subtractor, and a cycle counter — driven by a shift/subtract/test/restore control loop.

1. Part (a) — cache write policies and performance impact. Two independent design choices govern writes:
   • Write-through vs. write-back — on a write HIT, write-through updates both the cache line and main memory immediately, keeping memory always current at the cost of a memory transaction on every store (a write buffer can hide some of this, but heavy write traffic still saturates memory bandwidth). Write-back updates only the cache line and marks it with a dirty bit, deferring the memory write until the line is evicted; this cuts memory traffic dramatically (many writes to the same line cost one eventual memory write) but requires extra dirty-bit bookkeeping and a coherence mechanism if any other agent can see memory directly.
   • Write-allocate vs. no-write-allocate — on a write MISS, write-allocate fetches the block into the cache first, then writes it (so a later read/write to the same block hits); no-write-allocate writes straight through to memory without bringing the block into the cache. Write-allocate is usually paired with write-back (captures spatial/temporal locality of the newly-written block), and no-write-allocate with write-through (avoids polluting the cache with a block that may never be read again).
   Write-through+no-write-allocate favours simplicity and always-consistent memory at the cost of bus bandwidth; write-back+write-allocate favours performance (far less memory traffic, locality captured) at the cost of dirty-bit/coherence complexity — the latter is the dominant choice in modern CPU caches.
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/fast, and pipelining (including superscalar fetch of multiple instructions per cycle) is straightforward. Cons: every instruction must be as wide as the widest one actually needed, so simple instructions waste bits (and total code size grows), and the fixed field width caps things like immediate size, opcode space, or register-file size. Variable-length: instructions occupy only as many bits as the fields they need. Pros: markedly better code density — common, simple instructions stay short, reducing program memory footprint and instruction-cache pressure. Cons: the CPU cannot know where instruction $k{+}1$ begins until it has at least partially decoded instruction $k$, which complicates fetch/decode, makes deep pipelining and multi-issue fetch much harder, and requires more complex (multi-format) decode hardware. Fixed-length favours fetch/decode speed and pipelinability (the RISC choice); variable-length favours code density (the classic CISC choice) at the cost of decode complexity.
3. Part (c) — unsigned binary division: hardware and flowchart. The classic restoring division datapath divides an $n$-bit dividend held in register $Q$ by an $n$-bit divisor held in register $M$, using an $n$-bit remainder register $A$ (initialized to 0) that shifts left in lock-step with $Q$, an adder/subtractor, and a down-counting cycle counter:
   Fig. 1 — Restoring-division datapath: divisor register $M$, remainder register $A$ (shifts left together with $Q$), dividend/quotient register $Q$ (shifts left, LSB $Q_0$ set from the sign test), and a down-counting sequence counter that ends the algorithm after $n$ cycles.
   The control algorithm repeatedly shifts $A{:}Q$ one place left, subtracts the divisor from $A$, and tests the sign: if $A$ went negative the subtraction is undone (restored) and the quotient bit is 0; otherwise the subtracted value is kept and the quotient bit is 1.
   Fig. 2 — Restoring unsigned-division flowchart: initialize $A=0$, $\text{CTR}=n$; each of the $n$ cycles shifts $A{:}Q$ left, subtracts $M$ from $A$, and either restores $A$ (quotient bit 0) or keeps the subtracted $A$ (quotient bit 1), decrementing the counter until it reaches 0.
   Worked micro-trace for $M=0010_2\,(2)$, $Q=1001_2\,(9)$, $n=4$: initialize $A=0000$.
   Cycle 1: shift $A{:}Q\rightarrow A=0001,Q=0010$; $A-M=0001-0010<0$ ⇒ restore, $Q_0=0$: $A=0001,Q=0010$.
   Cycle 2: shift $\rightarrow A=0010,Q=0100$; $A-M=0010-0010=0000\ge0$ ⇒ keep, $Q_0=1$: $A=0000,Q=0101$.
   Cycle 3: shift $\rightarrow A=0000,Q=1010$; $A-M=0000-0010<0$ ⇒ restore, $Q_0=0$: $A=0000,Q=1010$.
   Cycle 4: shift $\rightarrow A=0001,Q=0100$; $A-M=0001-0010<0$ ⇒ restore, $Q_0=0$: $A=0001,Q=0100$.
   Final quotient $Q=0100_2=\boxed{4}$, remainder $A=0001_2=\boxed{1}$, matching $9=2\times4+1$ exactly.