08 Instruction Set Architectures II

Lecture from: 17.03.2023 | Video: YT

This lecture continues our exploration of Instruction Set Architectures (ISAs) and the Von Neumann model, building upon the concepts introduced in Lecture 7. Today, we delve deeper into ISA design trade-offs and examine the microarchitectural implementation of instructions, particularly within the context of the LC-3 architecture. We will explore how programmer-visible instructions are executed on a given processor design and further investigate the nuances of instruction formats and addressing modes.

Quick Review of the Von Neumann Model

Before diving into more complex topics, let’s quickly recap the key aspects of the Von Neumann model.

Core Components

The Von Neumann model is characterized by five essential components:

• Memory: A unified space for storing both instructions and data.
• Processing Unit (CPU): Responsible for executing instructions and performing computations.
• Control Unit: Orchestrates the operation of the computer, fetching and decoding instructions, and controlling data flow.
• Input: Mechanisms for feeding data and programs into the computer.
• Output: Mechanisms for presenting results and data from the computer.

Here LC-3: an example of a von Neumann machine.

Hallmarks of the Von Neumann Model

Two fundamental characteristics define the Von Neumann architecture:

• Stored Program: Instructions are stored in memory alongside data, allowing for flexibility and programmability. This unification of memory for instructions and data is a key feature.
• Sequential Instruction Processing: Instructions are executed one after another in a linear sequence, dictated by the program counter.

Programmer Visible State

The Von Neumann model exposes a specific set of architectural states that are directly accessible and manipulable by the programmer. These include:

• Memory: Viewed as an array of addressable storage locations.
• Registers: Fast, temporary storage locations within the CPU, accessed by name.
• Program Counter (PC): A register that holds the address of the next instruction to be executed.

Programmers use instructions to transform the values of this programmer-visible state, effectively controlling the computation.

Recall: Instruction Basics

Let’s briefly revisit what constitutes an instruction within a computer system.

Definition

An instruction is the fundamental unit of work for a computer. Instructions are the “words” of the machine’s language. The Instruction Set Architecture (ISA) defines the vocabulary and grammar of this language.

Language Representation

Computer instructions can be represented in two primary forms:

• Machine Language: The binary representation (0s and 1s) directly understood by the processor.
• Assembly Language: A human-readable symbolic representation of machine language, making programming more manageable.

Instruction Types

Instructions are broadly categorized into three main types:

• Operate Instructions: Perform arithmetic and logical operations within the Arithmetic Logic Unit (ALU).
• Data Movement Instructions: Transfer data between memory and registers.
• Control Flow Instructions: Alter the sequential execution flow of a program, enabling branching and looping.

Recall: Load Word Instructions and Addressing Modes

We previously explored Load Word instructions, a type of Data Movement instruction, and the concept of addressing modes.

Load Word Instructions in LC-3 and MIPS

Both LC-3 and MIPS utilize Load Word instructions to fetch data from memory into registers. These instructions often employ the base+offset addressing mode.

• LC-3 (Word-Addressable): LDR R3, R0, #2 - Loads a word from memory into register R3. The memory address is calculated as Memory[R0 + 2].
• MIPS (Word-Addressable): lw $s3, 2($s0) - Loads a word from memory into register $s3. The memory address is calculated as Memory[$s0 + 2].
• MIPS (Byte-Addressable): lw $s3, 8($s0) - In byte-addressable MIPS, the offset is scaled by the word size (4 bytes), resulting in Memory[$s0 + 8].

Instruction Format with Immediate

Instructions often include an immediate field to specify constant values or offsets directly within the instruction encoding.

• LC-3 (LDR): Instruction format includes fields for Opcode, Destination Register (DR), Base Register (BaseR), and a 6-bit offset (offset6).
• MIPS (lw): Instruction format (I-type) includes fields for Opcode, Source Register (rs), Target Register (rt), and a 16-bit immediate value (imm).

Instruction Processing Cycle: A Detailed Look

Now, let’s delve into the Instruction (Processing) Cycle, the sequence of steps a CPU takes to execute a single instruction.

The Six Phases of the Instruction Cycle

The instruction cycle is typically broken down into six distinct phases:

1. FETCH: Retrieve the instruction from memory.
2. DECODE: Determine the instruction’s operation and operands.
3. EVALUATE ADDRESS: Calculate memory addresses for memory operands (if needed).
4. FETCH OPERANDS: Get the operands from registers or memory.
5. EXECUTE: Perform the operation in the ALU.
6. STORE RESULT: Write the result back to a register or memory.

It’s crucial to understand that not every instruction requires all six phases. Simpler instructions might skip certain phases.

Fetch Phase: Retrieving the Instruction

The FETCH phase is the initial step, common to all instructions. It involves:

1. Load MAR and Increment PC: The Program Counter (PC) value (address of the next instruction) is copied to the Memory Address Register (MAR). Simultaneously, the PC is incremented to point to the subsequent instruction in memory.
2. Access Memory: The memory system, using the address in MAR, retrieves the instruction from memory and places it in the Memory Data Register (MDR).
3. Load IR: The instruction from the MDR is then loaded into the Instruction Register (IR).

Decode Phase: Identifying the Instruction

The DECODE phase analyzes the instruction in the IR to:

• Identify the Instruction: Determine the opcode and the operation to be performed (using a decoder circuit, like a 4-to-16 decoder for LC-3).
• Generate Control Signals: Based on the decoded instruction, the control unit generates the necessary control signals to direct the subsequent phases of the instruction cycle. These signals dictate the behavior of various components like the ALU, registers, and memory.

Decoding FSM:

Evaluate Address Phase: Calculating Memory Addresses

The EVALUATE ADDRESS phase is necessary for instructions that access memory with addresses requiring computation, like LDR. This phase calculates the effective memory address:

• Address Calculation: For LDR, the address is computed by adding (depicted as the red ADD box in the image below) the value of a base register (BaseR) and a sign-extended offset from the instruction.
• MAR Loading: The calculated address is loaded into the Memory Address Register (MAR).

This phase is skipped for instructions like ADD where operands are directly available in registers.

Fetch Operands Phase: Getting Data for Operations

The FETCH OPERANDS phase retrieves the data (operands) required for the instruction’s execution:

• For LDR:

  1. Load MAR: The MAR is loaded with the memory address calculated in the EVALUATE ADDRESS phase.
  2. Read Memory: Memory is accessed at the MAR address, and the data is loaded into the Memory Data Register (MDR).

• For ADD:

  • Register File Access: Operands are fetched directly from the register file using the register addresses specified in the instruction.

Execute Phase: Performing the Operation

The EXECUTE phase is where the actual computation happens:

• ALU Operation: The Arithmetic Logic Unit (ALU) performs the operation specified by the instruction’s opcode (e.g., addition, XOR, etc.) using the operands fetched in the previous phase.

Store Result Phase: Writing Back the Result

The STORE RESULT phase writes the result of the operation to its designated destination:

• Destination Register: The result from the ALU (or data from memory in the case of LDR) is written back to a register specified in the instruction.
• Instruction Cycle Completion: Once the STORE RESULT phase is finished, the instruction cycle completes, and a new cycle begins with the FETCH phase for the next instruction.

Alternatively:

Instruction Cycle Repetition

The instruction cycle repeats continuously, fetching, decoding, and executing instructions one after another, forming the basis of sequential program execution in the Von Neumann model.

Changing the Sequence of Execution: Control Flow Instructions

While the default execution is sequential, control flow instructions are essential for altering this sequence, enabling branching, looping, and function calls.

Unconditional Jump (JMP) in LC-3

The JMP instruction in LC-3 provides an unconditional jump:

• Operation: The Program Counter (PC) is directly loaded with a new address, taken from a specified register.
• Addressing Mode: Register Addressing Mode - the target address is in a register.

Unconditional Jump (j) in MIPS

The j instruction in MIPS also provides an unconditional jump, but with a different addressing mode:

• Operation: The Program Counter (PC) is updated with a target address calculated using a pseudo-direct addressing scheme.
• Addressing Mode: Pseudo-Direct Addressing Mode - the target address is derived from a combination of the current PC and a part of the instruction itself.

Finite State Machine Control

The entire instruction cycle is orchestrated by a Finite State Machine (FSM) within the Control Unit. The FSM transitions through states corresponding to each phase of the instruction cycle, generating appropriate control signals in each state to direct the data path elements.

LC-3 and MIPS Instruction Set Architectures: Deeper Dive

Let’s now return to a broader discussion of ISAs, focusing on LC-3 and MIPS and their design choices.

The Instruction Set Defines the ISA

The Instruction Set is the cornerstone of the ISA. It defines:

• Opcodes: The operations the processor can perform.
• Data Types: The types of data the processor can manipulate (integers, floating-point, etc.).
• Addressing Modes: How operands are located in memory or registers.

The Instruction Set Architecture: The Software-Hardware Interface

The ISA acts as the critical interface between software and hardware. It is the contract that software relies upon and hardware must implement.

The ISA specification encompasses:

• Memory Organization
• Register Set
• Instruction Set

Opcodes

LC-3

LC-3b

MIPS

Instruction Types

R-Type Instructions

Instructions (Opcodes) - Trade-offs

The design of opcodes involves trade-offs between simplicity and complexity.

• Complex Instructions: Can perform more work per instruction, potentially reducing code size and simplifying compilation. Examples include instructions for matrix multiplication or graph operations.
• Simple Instructions: Are easier to implement in hardware and can be combined to perform complex tasks, offering more flexibility for compiler optimization.

Data Types - Trade-offs

The choice of data types supported by an ISA also involves trade-offs:

• More Data Types: Can better map to high-level language constructs, potentially simplifying programming and improving performance for specific applications. However, this increases hardware complexity.
• Fewer Data Types: Simplify hardware implementation but may require software to emulate more complex data types, potentially impacting performance.

Semantic Gap

The semantic gap represents the difference in abstraction level between high-level programming languages and the ISA.

• Small Semantic Gap (Complex ISA): ISAs with complex instructions and data types are closer to high-level languages, reducing the translation effort for compilers but increasing hardware complexity.
• Large Semantic Gap (Simple ISA): ISAs with simple instructions and data types are further from high-level languages, requiring more complex compilers to bridge the gap but potentially simplifying hardware.

Difference between complex and simple ISA:

Addressing Modes - Trade-offs

The number and type of addressing modes in an ISA also present design choices:

• More Addressing Modes: Can provide more efficient ways to access memory for different data structures and access patterns, potentially reducing code size and improving performance. However, they increase hardware complexity and compiler complexity.
• Fewer Addressing Modes: Simplify hardware implementation but may require compilers to use more instructions to achieve complex memory accesses.

Operate Instructions: Examples and Implementation

Let’s examine Operate Instructions in more detail, considering examples in LC-3 and MIPS.

NOT Instruction in LC-3

The NOT instruction in LC-3 is a unary operation, performing bitwise negation. Its implementation is relatively straightforward.

Notably, MIPS does not have a dedicated NOT instruction. Instead, the nor instruction with register zero is used to achieve the same effect. This is a deliberate design choice to minimize the instruction set and simplify hardware.

ADD and AND Instructions with Literals in LC-3

LC-3 extends its ADD and AND instructions to support immediate operands (literals). This is achieved by using a steering bit within the instruction format to distinguish between register and immediate operands.

ADD Immediate Instruction in MIPS

MIPS provides the addi instruction for adding an immediate value to a register. This is an example of an I-type instruction format.

Subtraction: MIPS vs. LC-3

Comparing subtraction implementation in MIPS and LC-3 highlights the trade-offs between ISA complexity and code efficiency.

• MIPS: Has a dedicated sub instruction for direct subtraction.
• LC-3: Requires a sequence of instructions (NOT and ADD) to perform subtraction using two’s complement arithmetic.

This demonstrates that simpler ISAs may require more instructions to achieve the same functionality as more complex ISAs.

Continue here: 09 ISA & Microarchitecture