Question 1 of 6: Instruction Set Extension, Memory Traffic, and I/O

Question 1: Instruction Set Extension, Memory Traffic, and I/O (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 word-addressable, 1Mword (2²⁰-word) address space; a fixed 64-bit instruction format OP Destination, Source, nextPC whose printed field widths are 4 / 20 / 20 / 20 bits, i.e. three word-address operand fields; a first implementation using 15 of the available opcodes.

Find. (a) how many more instructions a backward-compatible, still-64-bit second implementation can add, whether it is exactly one, whether it can be ten, and whether register-using instructions are possible; (b) the minimum bytes read from memory to run a given 10-instruction program; (c) the tradeoffs of polling vs. interrupt-driven I/O.

Approach. (a) derive the opcode field width from the fixed 64-bit budget minus the three address fields, count how many opcode values the first implementation left unused, then reason about whether a narrower register-operand format can pack in more than that count; (b) add instruction-fetch bytes to data-read bytes for the given mix; (c) argue from where the "who checks the device" burden sits.

1. Part (a) — how much opcode space is left? The memory holds $1M=2^{20}$ words, so naming any one word address needs $$n_{addr}=\log_2(1{,}048{,}576)=\boxed{20\ \text{bits}}.$$ The instruction carries three such address fields (Destination, Source, nextPC): $3\times20=60$ of the 64 bits, leaving $$n_{op}=64-60=\boxed{4\ \text{bits}}\ \Rightarrow\ 2^4=16\ \text{possible opcode values}.$$ This reproduces exactly the 4 / 20 / 20 / 20 split the paper prints above the field diagram, confirming the address fields are sized to span the whole 1Mword space with nothing left over. Backward compatibility means the second implementation must keep decoding all 15 existing opcodes exactly as before — same meaning, same three 20-bit address fields — so it cannot shrink any field or reassign an opcode already in use. Since only 15 of the 16 possible 4-bit patterns are taken, there is exactly $$16-15=\boxed{1\ \text{unused opcode value}}$$ still available under this fixed field layout.
   • Can it introduce more instructions? Yes — the one leftover opcode value is free to assign to a new instruction while every existing decode path is untouched.
   • Can it introduce ONE more? Yes, exactly one, using that single remaining 4-bit pattern.
   • Can it introduce 10 more, in this same format? No — only $1$ opcode value remains ($1\lt10$); the 3×20-bit-address-field layout has no further room without either widening the instruction (not allowed — must stay 64 bits) or reassigning an opcode already committed to a first-implementation instruction (not allowed — breaks backward compatibility).
   • Can it introduce instructions that use registers? Yes, and this is exactly how far more than 10 new instructions can be added: a register index needs far fewer bits than a 20-bit memory address (e.g. $\lceil\log_2 32\rceil=5$ bits for 32 registers). Under that ONE reserved opcode, the remaining $64-4=60$ payload bits no longer need to hold three 20-bit addresses — a three-register-operand instruction spends only $3\times5=15$ of those 60 bits, leaving $$60-15=45\ \text{bits free for a secondary (sub-)opcode},$$ i.e. up to $2^{45}$ distinct register-based instructions can be packed under that single reserved top-level opcode. So while the plain memory-address format admits only 1 more instruction, switching the new instructions to register operands easily accommodates 10 more (and vastly more), all while every one of the original 15 opcodes' decode logic is left completely untouched.
2. Part (b) — minimum bytes read to execute the program. Every one of the 10 instructions must be FETCHED from memory regardless of what it does, and each is $32\text{ bits}=4$ bytes: $$\text{fetch bytes}=10\times4=\boxed{40\ \text{bytes}}.$$ In addition, the 2 memory-read instructions each pull 4 more bytes of DATA from memory: $$\text{data bytes}=2\times4=8\ \text{bytes}.$$ Assuming a straight-line pass through the program once (no repeated fetches from a taken backward branch, which would only add more), the minimum total is $$\boxed{40+8=48\ \text{bytes}}.$$
3. Part (c) — polling vs. interrupts. Polling: the processor repeatedly reads a device's status register in a loop, checking a ready/busy bit, until the device signals it is ready. Pros: simple to implement (no extra hardware, no interrupt controller), deterministic latency (the CPU notices readiness the instant its next poll executes), and it avoids the fixed per-event overhead of an interrupt (context save/restore, vectoring to a handler) — a real win for a device that is ALWAYS ready or that responds within a few cycles. Cons: the CPU is busy-waiting and cannot do other useful work while polling, wasting cycles whenever the device is slow (e.g. a keystroke or disk seek, which can be many orders of magnitude slower than a CPU cycle); polling frequency is also a tradeoff — too rare risks missing/delaying a time-sensitive event, too frequent wastes even more cycles and memory bus/bandwidth on status reads that mostly report "not ready."
   Interrupts: the device itself signals the processor asynchronously when it needs attention, and the processor executes a dedicated handler only then. Pros: the CPU is free to run other work between events instead of busy-waiting — essential for slow or unpredictably-timed devices, and it scales to many devices without the CPU having to visit each one's status register on a schedule. Cons: every interrupt costs fixed overhead (saving/restoring processor state, pipeline flush, vectoring through an interrupt table) that can exceed the cost of just polling for a device that is fast or nearly always ready; interrupts also introduce concurrency hazards (a handler can preempt code at almost any point, so shared data touched by both must be protected) and, if devices interrupt very frequently, the overhead can itself overwhelm useful CPU work (interrupt "storms"/livelock).
   Rule of thumb: poll a fast, frequently-ready device; interrupt for a slow or rarely-ready one. Real systems often combine both (e.g. polling briefly, then falling back to an interrupt if the device isn't ready quickly).