Question 2 of 6: Cache Replacement, I/O Techniques, and RISC Design

Question 2: Cache Replacement, I/O Techniques, and RISC Design (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 full, associative cache that must evict a block to make room for a new one. (b) The general problem of moving data between the CPU and peripheral devices. (c) The RISC design philosophy as opposed to CISC.

Find. (a) Four common block-replacement policies, explained. (b) Three I/O techniques, each in 3–4 sentences. (c) The core principles underlying RISC architectures.

Approach. Survey the standard taxonomy for each sub-question: replacement policies by what history they track, I/O techniques by who initiates/services the transfer, and RISC principles by what they trade off against CISC.

1. Part (a) — four cache replacement algorithms.
   • Least Recently Used (LRU): evicts the block that has gone the longest without being referenced, on the (locality) assumption that a block untouched for a long time is unlikely to be needed again soon. Gives excellent hit rates in practice but needs per-block "recency" bookkeeping (counters or a stack) that gets expensive to implement exactly as associativity grows, so most real caches use a cheap approximation (e.g. a "not recently used"/clock bit).
   • First-In-First-Out (FIFO): evicts whichever block has been resident the longest, regardless of how recently it was used, tracked with a simple round-robin/queue pointer per set. Much cheaper than true LRU but can perform poorly if an old block is still being reused heavily (and famously can suffer Belady's anomaly, where adding cache capacity increases the miss count).
   • Least Frequently Used (LFU): evicts the block with the smallest access count since it entered the cache, on the idea that rarely-used blocks are the best eviction candidates. Requires a counter per block (and usually periodic decay/aging so old bursts of popularity don't permanently protect a now-cold block), adding more hardware than FIFO.
   • Random: picks a victim block uniformly at random (or via a cheap pseudo-random hash), needing essentially no extra state. Surprisingly competitive with LRU on many workloads and immune to pathological access patterns that defeat a fixed policy, at the cost of no guarantee of good behaviour on any specific program.
2. Part (b) — three I/O techniques.
   • Programmed I/O (polling): the CPU executes a tight loop that repeatedly reads a device's status register, testing a ready/busy bit until the device signals it can accept or supply data. The CPU then performs the actual data transfer itself, one word at a time, entirely under program control. It is simple to implement and has no interrupt-handling overhead, but it wastes CPU cycles busy-waiting whenever the device is slow relative to the processor.
   • Interrupt-driven I/O: the CPU issues a request (or simply waits) and continues executing other instructions; when the device becomes ready, it raises an interrupt signal that causes the processor to suspend its current program, save state, and run a dedicated interrupt-service routine to move the data. This frees the CPU for useful work between transfers but adds fixed per-event overhead (context save/restore, vectoring) for every single word transferred, which can dominate for very high-bandwidth devices.
   • Direct Memory Access (DMA): a dedicated DMA controller is programmed by the CPU (with a source/destination address and a byte count) and then autonomously transfers an entire block of data directly between the device and main memory over the system bus, interrupting the CPU only once when the whole block is complete. This removes the CPU almost entirely from the data-movement path, making it by far the most efficient technique for large, high-speed transfers (disk, network), at the cost of extra dedicated hardware and bus-arbitration logic.
3. Part (c) — basic principles of RISC design. RISC (Reduced Instruction Set Computer) design rests on the observation that a small set of simple, uniformly-encoded instructions, executed very fast, usually outperforms a large set of complex instructions executed slowly — especially once an optimizing compiler is doing the instruction selection rather than a human. The recurring principles are:
   • Fixed, uniform instruction length and format — every instruction is the same width (e.g. 32 bits) with a small number of encoding formats, which lets the fetch/decode stage be simple and fast and makes pipelining straightforward (no need to first discover how long an instruction is before decoding the next one).
   • Load/store architecture — only explicit LOAD and STORE instructions touch memory; all arithmetic/logic operations work purely on registers. This keeps every other instruction's timing predictable (register-to-register operations complete in one cycle) and confines the unpredictable memory-latency cost to a small, identifiable set of instructions.
   • Simple addressing modes — few, easily-decoded addressing modes (vs. CISC's many, some requiring multi-step address computation), again keeping per-instruction latency short and uniform.
   • Large general-purpose register file — more registers reduce how often the compiler must spill values to memory, compensating for the load/store restriction.
   • Hardwired (not micro-programmed) control — the simple, regular instruction formats make it practical to implement the control unit directly in combinational logic, which is faster than fetching micro-instructions from a control store.
   • Single-cycle-per-stage, pipeline-friendly design — most instructions execute in one cycle per pipeline stage, and the uniform format/limited addressing modes make deep, efficient pipelining feasible.
   • Compiler-centric philosophy — complexity (instruction scheduling, addressing, optimization) is pushed into the compiler once, at compile time, rather than into hardware that pays a decode/complexity cost on every single execution.
   Net effect: RISC trades instruction-count richness for per-instruction speed, uniformity, and pipelinability — betting that a fast simple core executing more (simpler) instructions beats a slower complex core executing fewer (richer) ones.