Question 2 of 6: Cache Block Size, I/O Drawbacks, and Parallelism

Question 2: Cache Block Size, I/O Drawbacks, and Parallelism (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) The claim that block (line) size affects cache hit ratio. (b) The two simplest I/O transfer techniques. (c) Two related but distinct notions of parallelism at the instruction level.

Find. (a) Agree/disagree with justification. (b) The drawbacks of programmed I/O and of interrupt-driven I/O. (c) ILP vs. machine parallelism, and the major issue policies.

Approach. (a) reason from spatial locality and the fixed-overhead-per-miss tradeoff; (b) contrast what each technique costs the CPU; (c) separate the property of the CODE (ILP) from the property of the HARDWARE that exploits it (machine parallelism), then classify issue policies by ordering discipline.

1. Part (a) — does block size influence hit ratio? Agree. A larger block exploits spatial locality: when one word is fetched, its neighbours (very likely to be referenced soon, e.g. the rest of a loop body or an array row) are pulled in "for free" in the same miss, which can markedly raise the hit ratio for programs with strong sequential/array access patterns. However, the relationship is not monotonic: for a FIXED total cache capacity, increasing block size also *reduces the number of blocks* the cache can hold, which lowers the number of independent regions of memory resident at once. Beyond a certain block size, the hit ratio degrades because useful blocks are evicted to make room for large blocks whose extra words are never actually referenced (wasted fetch bandwidth and cache space) — this is sometimes called the "pollution" effect. Larger blocks also increase the miss penalty (more data to transfer per miss), so even where hit ratio still improves slightly, average access time can worsen. Block size absolutely influences hit ratio — positively up to a point (locality capture), then negatively (fewer distinct blocks resident, more pollution) — so there is an optimum block size for a given capacity and workload, not a "bigger is better" rule.
2. Part (b) — drawbacks of programmed I/O and interrupt-driven I/O. Programmed I/O (polling): the CPU must repeatedly poll the device's status register in a busy-wait loop until it is ready, executing no useful work while waiting. For a slow device this wastes an enormous number of CPU cycles, and the CPU is entirely unavailable for other tasks during the transfer — there is no concurrency between I/O and computation at all. Interrupt-driven I/O: the CPU is freed to do other work between transfers, but every single data item transferred (unless batched) costs a fixed interrupt overhead — saving/restoring processor state, vectoring to the interrupt-service routine, and returning — which can dominate the actual transfer time for high-bandwidth or high-frequency devices. Frequent interrupts also disrupt pipelining/cache locality of the interrupted program and, without careful priority handling, can lead to missed or delayed service if interrupts arrive faster than they can be serviced. Programmed I/O wastes CPU cycles busy-waiting; interrupt-driven I/O saves CPU time between transfers but pays a fixed per-transfer servicing cost that scales badly with transfer frequency — both are inferior to DMA for large/fast transfers.
3. Part (c) — instruction-level parallelism vs. machine parallelism, and issue policies. Instruction-level parallelism (ILP) is a property of the PROGRAM (or of the compiler's scheduling of it): the degree to which the instructions in a piece of code are independent of one another and could, in principle, execute simultaneously or out of order without changing the result. It is bounded above by true data and control dependencies in the code — no hardware can extract parallelism that isn't there. Machine parallelism is a property of the HARDWARE: its ability to actually detect and exploit whatever ILP is present — how many instructions it can fetch/decode/execute per cycle, how many functional units it has, and how aggressively it can reorder, rename, and speculate. A program with abundant ILP still runs serially on a machine with no machine parallelism (e.g. a simple scalar in-order pipeline), and a superscalar machine with high machine parallelism gains nothing on code with no exploitable ILP (e.g. a tight dependency chain). Performance requires BOTH: enough ILP in the code and enough machine parallelism in the hardware to exploit it.

   The major instruction-issue policies (how a machine selects and dispatches multiple instructions per cycle) are:

   • In-order issue, in-order completion: instructions are issued to functional units strictly in program order and must also complete in that order. Simplest to build and easiest to reason about (state updates always match program order) but stalls the entire issue stage whenever the next instruction isn't ready, wasting available parallelism.
   • In-order issue, out-of-order completion: instructions still issue in program order, but once dispatched to (possibly multiple) functional units of different latency, they may finish in a different order. Allows a long-latency instruction (e.g. a divide) to run alongside faster ones without stalling them, but issue can still stall on a dependency at the head of the queue, and out-of-order completion requires hazard detection (WAR/WAW) on the register file.
   • Out-of-order issue, out-of-order completion (dynamic scheduling): instructions may issue as soon as their operands are ready, regardless of program order (e.g. Tomasulo's algorithm, reservation stations, register renaming), and complete out of order too. Extracts far more ILP by looking past a stalled instruction to find independent, ready work, but needs substantial extra hardware (renaming, scoreboarding/reservation stations) and, for correct exception behaviour, typically a reorder buffer to commit results in program order despite executing out of order.
   ILP is a ceiling set by the code; machine parallelism is how much of that ceiling the hardware can reach; the three issue policies are successively more aggressive (and more hardware-costly) ways of climbing toward it.