Question 6 of 6: Branch Prediction, Addressing Modes, Shift Types, and Non-Volatile Memory Families

Question 6: Branch Prediction, Addressing Modes, Shift Types, and Non-Volatile Memory Families (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 pipelined CPU that must fetch past unresolved conditional branches. (b) Four common operand-addressing modes. (c) The two families of bit-shift operation. (d) Three related non-volatile, electrically-reprogrammable memory technologies.

Find. (a) The common branch-prediction approaches. (b) How each addressing mode locates its operand, with pros/cons. (c) Arithmetic vs. logical shift. (d) The distinguishing features of EPROM, EEPROM, and flash.

Approach. Survey the standard taxonomy for each: prediction schemes by how much history they use, addressing modes by where the operand actually lives, shifts by what they do to the sign bit, and the three memory types by their erase/write granularity.

1. Part (a) — branch prediction approaches.
   • Static prediction: a fixed rule decided at compile time or design time and never changes at run time — e.g. "always predict not-taken," "always predict taken," or "predict taken for backward branches (loops), not-taken for forward branches." Cheap (no run-time history hardware) but cannot adapt to a branch's actual behaviour.
   • Dynamic prediction using a Branch History Table / 1-bit predictor: a small table indexed by (part of) the branch's address records whether it was taken last time, and predicts the same outcome again. Simple hardware, but mispredicts twice at the boundaries of a loop (entry and exit).
   • 2-bit saturating counter prediction: each table entry is a 2-bit counter that must miss twice in a row before the prediction flips, which absorbs a single "off-pattern" branch outcome without immediately flipping the prediction — substantially more accurate than 1-bit for loop-like code.
   • Correlating (two-level/global-history) predictors: the prediction is indexed by the outcomes of several RECENT branches (a global or per-branch history register) as well as the branch's own address, capturing patterns where one branch's outcome is correlated with another's (e.g. "if the last two branches were both taken, this one usually is too").
   • Branch Target Buffer (BTB): caches not just taken/not-taken but the TARGET address of a previously-taken branch, so on a predicted-taken branch the pipeline can start fetching from the target immediately rather than waiting for the target to be computed.
   Prediction schemes trade hardware cost for adaptiveness: static rules cost nothing but never adapt; per-branch history (1-bit, 2-bit) adapts to that branch's own pattern; correlating predictors additionally exploit cross-branch patterns; a BTB removes the target-computation delay on top of any of these.
2. Part (b) — addressing modes.
   • (1) Immediate addressing: the operand VALUE itself is encoded directly in the instruction (no memory/register access needed to fetch it). Advantage: fastest possible operand access (already in hand once the instruction is decoded); no extra memory reference. Disadvantage: the operand's size is capped by the instruction's immediate field width, so it cannot represent large or run-time-computed values.
   • (2) Direct addressing: the instruction contains the full memory ADDRESS of the operand; the CPU fetches the operand from that address. Advantage: simple, single extra memory access to get the operand. Disadvantage: the address field must be as wide as the full address space, consuming instruction bits, and the addressed location is fixed at compile/assembly time (poor for position-independent or dynamically-relocated code).
   • (3) Register addressing: the instruction names a REGISTER that holds the operand. Advantage: fastest access after immediate (registers are on-chip and far faster than any memory access), and register fields are short (few bits) since there are few registers. Disadvantage: limited by the small number of registers available, so it cannot address the vastly larger memory space directly.
   • (4) Register indirect addressing: the instruction names a register that holds the ADDRESS of the operand (not the operand itself); the CPU reads the register to get an address, then accesses memory at that address. Advantage: supports pointer-based/dynamic addressing (the address can be computed or updated at run time, e.g. for array traversal or dynamic data structures) while keeping the instruction field short (just a register number). Disadvantage: requires an extra memory access compared to direct register addressing (register read, then memory read), so it is slower.
   The four modes form a speed/flexibility ladder: immediate (fastest, least flexible) → register (fast, small operand space) → direct (one memory access, fixed address) → register indirect (one memory access, but the address itself is run-time-computed — most flexible of the four).
3. Part (c) — arithmetic shift vs. logical shift. A logical shift moves every bit left or right by the specified count and fills the vacated bit positions with 0s, with NO regard for the value's sign; a logical right shift of a negative two's-complement number destroys its sign (turns it positive-looking) because the sign bit is shifted out and 0s are shifted into the MSB. An arithmetic shift is sign-aware: an arithmetic LEFT shift is identical to a logical left shift (fills with 0s; both are used for multiplying by powers of two, though the top bit(s) can be lost to overflow), but an arithmetic RIGHT shift fills the vacated MSB positions with COPIES of the original sign bit (sign extension), so a right-shifted negative number remains negative — this correctly implements division by a power of two (rounding toward $-\infty$) for signed two's-complement values. Logical shifts treat the bit pattern as unsigned (always fill with 0); arithmetic right shift preserves the sign by replicating it into the vacated bits, which logical shift never does.
4. Part (d) — EPROM vs. EEPROM vs. flash. All three are non-volatile, electrically-programmable memories built on floating-gate (or similar charge-trapping) transistor cells, but they differ in how they are ERASED and at what GRANULARITY they can be rewritten.
   • EPROM (Erasable Programmable ROM): programmed electrically (byte at a time) but erased only by exposing the entire chip's die to strong ultraviolet light through a quartz window, which resets EVERY cell at once. Erasure requires physically removing the chip from the circuit and takes many minutes under a UV lamp; there is no way to erase just part of it.
   • EEPROM (Electrically Erasable PROM): both programmed AND erased electrically, in-circuit, at the granularity of an individual BYTE (or a small number of bytes) at a time, with no UV light or chip removal needed. Much more convenient than EPROM but historically slower and more expensive per bit, since each byte-erase cycle involves more complex on-chip charge-pump circuitry.
   • Flash memory: a descendant of EEPROM that is also electrically erasable in-circuit, but erases in larger fixed-size BLOCKS or SECTORS (not individual bytes) at a time, trading fine-grained erase flexibility for much higher density, lower cost per bit, and faster erase/write throughput — the basis of USB drives, SSDs, and firmware/BIOS storage today.
   The progression EPROM → EEPROM → flash is a steady improvement in erase convenience and granularity: whole-chip/UV → byte-level/electrical → block-level/electrical, each step trading some erase granularity for density, speed, and cost.