Instruction Set Exercises

Approach: Compare the two formats on the six axes that matter in practice — the length of the operation code, the complexity of the hardware, the speed of execution, the use of the instruction space, the flexibility of the format, and how easy it is to extend the set.

Steps:

1. Length of the operation code: with a fixed-length opcode the length of the operation code is fixed; with an expanding opcode the length varies.
2. Hardware complexity: a fixed-length opcode decodes simply and the hardware is straightforward; an expanding opcode needs multi-level decoding and a complex hardware implementation.
3. Execution efficiency: a fixed-length opcode executes quickly and has strong parallel processing capability; an expanding opcode executes more slowly because multi-level decoding is required.
4. Space efficiency: a fixed-length opcode wastes space because some instructions do not need all the address codes; an expanding opcode uses the instruction space efficiently.
5. Flexibility: a fixed-length opcode is inflexible and hard to adapt to complicated instructions; an expanding opcode is flexible and supports instructions of different complexity.
6. Extensibility: a fixed-length opcode is hard to extend; an expanding opcode is easy to extend, so new instructions can be added without redesigning the format.

Answer: A fixed-length opcode gives a uniform, fast, simple-to-decode format at the cost of wasted encoding space and poor extensibility, while an expanding opcode packs far more instructions into the same space and scales to new instructions at the cost of a slower, more complex decoder. The choice is a trade-off between decode simplicity and encoding density.

Approach: Define each mode in terms of the address code, the instruction form, the number of memory accesses, and the address computation, and then run the same instruction over a small memory image to show the different results.

Steps:

1. Direct addressing:
   • The address code is the address of the operand
   • Format: LOAD R1, [1000]
   • Meaning: load the data at address 1000 into register R1
   • Number of memory accesses: 1
   • Address computation: the address code is used directly
2. Indirect addressing:
   • The address code holds the address of the address of the operand
   • Format: LOAD R1, [[1000]]
   • Meaning: take the contents of address 1000 as an address, then load the data at that address into register R1
   • Number of memory accesses: 2
   • Address computation: fetch the address first, then fetch the data
3. The worked example: assume the memory holds
   • Address 1000: the stored value 2000
   • Address 2000: the stored value 42
   • Direct addressing: LOAD R1, [1000] → R1 = 2000
   • Indirect addressing: LOAD R1, [[1000]] → R1 = 42

Answer: Direct addressing uses the address code as the address of the operand and costs one memory access, while indirect addressing treats the address code as a pointer to the operand and costs two. In the example the direct form loads 2000 and the indirect form loads 42.

Approach: Define each mode with its effective address formula and the role of its register, then contrast the two along the three axes that separate them.

Steps:

1. Base addressing:
   • Effective address = base register + displacement
   • The base register holds the base address
   • The displacement is given in the instruction
   • It supports program relocation
   • It widens the range of addresses
2. Indexed addressing:
   • Effective address = index register + base address
   • The index register holds the index value
   • The base address is given in the instruction
   • It supports array access
   • It makes loop control convenient
3. The differences:
   • The role of the register: in base addressing the base register holds the base address, whereas in indexed addressing the index register holds the index value.
   • Application scenarios: base addressing serves program relocation and address translation, whereas indexed addressing serves array access and loop control.
   • Address computation: base addressing computes base address + displacement, whereas indexed addressing computes base address + index value.

Answer: Base addressing adds a displacement to a base register, which makes the register the fixed anchor of a memory region and supports relocation; indexed addressing adds an index value to a base address held in the instruction, which makes the register the moving part and supports array access.

Approach: Work through the five axes on which the two architectures differ — the instructions, the hardware, the software support, the performance characteristics, and the workloads each one suits.

Steps:

1. Instruction characteristics:
   • CISC: the instructions are complicated and powerful, and their length varies
   • RISC: the instructions are simple and each does one thing, and their length is fixed
2. Hardware implementation:
   • CISC: microprogrammed control, complicated decoding, multi-cycle execution
   • RISC: hardwired control, simple decoding, single-cycle execution
3. Software support:
   • CISC: high code density, simple compilation, good compatibility
   • RISC: low code density, complicated compilation, poor compatibility
4. Performance characteristics:
   • CISC: low execution efficiency, complex hardware, hard to pipeline
   • RISC: high execution efficiency, simple hardware, pipeline friendly
5. Application scenarios:
   • CISC: desktop computing, servers, embedded systems
   • RISC: mobile devices, high-performance computing, the Internet of Things

Answer: CISC favours code density and compatibility at the cost of complex decoding and uneven timing, while RISC favours simple, uniform, pipeline-friendly execution at the cost of code length and compiler complexity. The present-day processor designs blend the two, exposing a CISC interface and executing a RISC core.

Approach: Go through the addressing modes one by one, writing the formula for the effective address in each case and noting whether the value is used directly or has to be fetched first.

Steps:

1. Immediate addressing: effective address = the immediate value in the instruction; no computation is needed, the value is used directly.
2. Direct addressing: effective address = the address code; the address code is used directly as the address.
3. Indirect addressing: effective address = [address code]; the contents of the address code are fetched first and used as the address.
4. Register addressing: effective address = the contents of the register; the register value is used directly.
5. Register indirect addressing: effective address = [register contents]; the register contents are fetched first and used as the address.
6. Base addressing: effective address = base register + displacement; the base register contents are added to the displacement.
7. Indexed addressing: effective address = index register + base address; the index register contents are added to the base address.
8. Relative addressing: effective address = PC + displacement; the program counter is added to the displacement.

Answer: The effective address is always computed from the instruction’s address code, a register, or the program counter, according to the addressing mode. The modes differ only in where the components come from and in how many memory accesses the computation costs.

Approach: Rank the addressing modes by how many memory accesses each one costs, note the application each one fits, and then draw out the optimisation guidance that follows from the ranking.

Steps:

1. Immediate addressing:
   • Efficiency: the highest, since no memory access is needed
   • Application: constant assignment, immediate arithmetic
   • Limitation: the size of the operand is limited
2. Register addressing:
   • Efficiency: very high, since no memory access is needed
   • Application: data that is accessed frequently
   • Limitation: the number of registers is limited
3. Direct addressing:
   • Efficiency: moderate, since one memory access is needed
   • Application: accessing data at a fixed address
   • Limitation: the range of addresses is limited
4. Register indirect addressing:
   • Efficiency: moderate, since one memory access is needed
   • Application: array access, pointer operations
   • Advantage: supports dynamic addresses
5. Indirect addressing:
   • Efficiency: lower, since two memory accesses are needed
   • Application: pointer operations, dynamic addressing
   • Advantage: supports complicated address computation
6. Base addressing:
   • Efficiency: moderate, since one memory access is needed
   • Application: program relocation, address translation
   • Advantage: supports program relocation
7. Indexed addressing:
   • Efficiency: moderate, since one memory access is needed
   • Application: array processing, loop control
   • Advantage: supports array access
8. Relative addressing:
   • Efficiency: moderate, since one memory access is needed
   • Application: jump instructions, branch instructions
   • Advantage: supports program relocation

Optimisation advice:

• Prefer immediate addressing and register addressing
• Use registers sensibly in order to reduce the number of memory accesses
• Choose the addressing mode that suits the characteristics of the application

Answer: The immediate and register modes are the most efficient because they need no memory access at all; the single-access modes sit in the middle; and indirect addressing is the most expensive because it needs two. The optimisation rule that follows is to keep operands in registers wherever the application allows it.

Approach: Use the number of bit patterns a field of n bits can hold, and apply the rule to the operation code and the address code in turn.

Steps:

1. The number of instructions:
   • Number of operation code bits: 8
   • Number of instructions supported: 2^8 = 256 instructions
2. The range of addresses:
   • Number of address code bits: 24
   • Range of addresses: 0 to 2^24 - 1 = 0 to 16,777,215
   • Address space: 16MB
3. The instruction format:

   [Opcode (8 bits)] [Address (24 bits)]

4. The analysis:
   • The number of instructions is moderate and meets the basic requirements
   • The range of addresses is large and supports large programs
   • The format is simple and easy for the hardware to implement

Answer: The 8-bit operation code supports 256 instructions and the 24-bit address code covers the addresses 0 to 16,777,215, which is a 16MB address space.

Approach: Design the register file first, then the instruction format, then the addressing modes, then show a few instructions that exercise the modes, and finally list what the design buys.

Steps:

1. The register design:

   • Base register: BR (Base Register)
   • Index register: IR (Index Register)
   • General-purpose registers: R0-R15

2. The instruction format:

   [Opcode (8 bits)] [Destination register (4 bits)] [Base register (4 bits)] [Index register (4 bits)] [Displacement (12 bits)]

3. The addressing modes:

   • Base addressing: effective address = BR + displacement
   • Indexed addressing: effective address = IR + base address
   • Base plus index addressing: effective address = BR + IR + displacement

4. Example instructions:

   ; Base addressing
   LOAD R1, BR, 100    ; R1 = [BR + 100]
   
   ; Indexed addressing
   LOAD R2, IR, 200    ; R2 = [IR + 200]
   
   ; Base plus index addressing
   LOAD R3, BR, IR, 50 ; R3 = [BR + IR + 50]

5. The advantages:

   • It supports array access
   • It supports program relocation
   • It supports loop control
   • The address computation is flexible

Answer: A design with a base register, an index register, and general-purpose registers, using a format that carries a destination register, a base register, an index register, and a 12-bit displacement, gives a single instruction set that covers base, indexed, and base-plus-index addressing and therefore covers array access, relocation, and loop control.