Question 1 of 6: Instruction Encoding and Memory Addressing

Question 1: Instruction Encoding and Memory Addressing (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 32K-word, word-addressable memory; a fixed 64-bit instruction format OP Destination, Source, nextPC with three word-address operand fields; separately, a 4GB (2³²-byte) byte-addressable machine where the 32-bit pattern 0x1ABCDEF0 sits at address 0x04000000.

Find. (a) the number of distinct instructions the 64-bit format supports; (b) advantages/disadvantages of fixed- vs. variable-length instruction encoding; (c) whether the given 32-bit pattern can be an instruction, data, or both.

Approach. For (a), compute the address-field width from the memory size, subtract the three operand fields from the total instruction width, and the remainder is the opcode field; (b) and (c) are argued from first principles of the stored-program (von Neumann) model.

1. Part (a) — opcode space. The memory holds $32K=2^{15}$ words, so naming any one word needs $$n_{addr}=\log_2\!\left(32\times1024\right)=15\ \text{bits}.$$ The instruction carries three such address fields (Destination, Source, nextPC), consuming $3\times15=45$ of the 64 available bits, leaving the rest for the operation code: $$n_{op}=64-3(15)=64-45=19\ \text{bits}.$$ Each of those 19 bits is independently 0 or 1, so the number of distinct instructions (distinct operations, for this fixed operand-triple format) is $$N=\boxed{2^{19}=524{,}288}.$$
2. Part (b) — fixed vs. variable instruction length. A fixed-length encoding (e.g. every instruction 32 bits) places every field at the same bit offset in every instruction. Advantages: the fetch unit always knows exactly where the next instruction starts (PC += constant), so fetch/decode is single-cycle and predictable, and several instructions can be fetched and decoded in parallel (needed for superscalar issue) because instruction boundaries never depend on decoding a prior instruction; branch-target arithmetic is simple. Disadvantages: every instruction pays for the widest field any instruction might need, so small operands (a short immediate, a single register move) still cost a full word — code density suffers — and immediates/addresses too wide to fit force multi-instruction sequences (e.g. load-upper then add) to build one constant.
   A variable-length encoding (1–17 bytes) lets each instruction spend only the bytes its own opcode and operands need. Advantages: much better code density (fewer bytes fetched per instruction, smaller executables, better instruction-cache behaviour); an operand is encoded at exactly the width it needs; richer addressing modes can be added without bloating every instruction. Disadvantages: the decoder cannot know where instruction $k{+}1$ begins until instruction $k$'s own length is fully decoded — this serializes fetch/decode, complicates parallel superscalar decode (at real hardware cost, e.g. x86 predecode/μop caches), and makes disassembly/branch-target validation ambiguous if control ever jumps into the middle of what was meant to be one instruction's bytes.
3. Part (c) — instruction, data, or both? On this von Neumann (stored-program) machine, instructions and data occupy one undifferentiated byte-addressable memory: no tag bit or reserved bit pattern on a stored word marks it "code" versus "data." Whether 0x1ABCDEF0 at 0x04000000 is an instruction or data is decided entirely by how the processor accesses that address, not by the bits themselves:
   • if the Program Counter points at 0x04000000 and control fetches through the instruction path, hardware decodes those same 32 bits as an opcode plus operand fields and executes whatever operation that encoding specifies — so yes, it can be an instruction (unless the ISA happens to reserve that exact bit pattern as illegal);
   • if instead a load/store instruction names 0x04000000 as an operand address, the identical 32 bits are simply read as a 32-bit integer/bit-pattern value — so yes, it can equally be data.
   The two readings never collide at a single instant (a fetch cycle and a data-access cycle are distinct events), but the memory cell itself is agnostic — this ambiguity (and the security exposure it creates, e.g. code injected into a data buffer that is later executed) is exactly what a Harvard architecture avoids by physically separating instruction memory from data memory.