The Processor

CPU Performance Factors

• CPU performance is affected by:

  • Instruction count, which is determined by the instruction set architecture and the compiler used.

  • CPI (Cycles Per Instruction) and clock cycle time, which are determined by the CPU hardware.

• The lecture will cover two MIPS implementations:

  • A simplified version.

  • A more realistic pipelined version.

• Subset of instructions:

  • Memory reference: lw (load word), sw (store word).

  • Arithmetic/logical: add, sub, and, or, slt (set less than).

  • Control transfer: beq (branch if equal), j (jump).

Instruction Execution Steps

1. Fetch Instruction: PC (Program Counter) -> Instruction Memory, to fetch the instruction.

2. Read Registers: Register numbers -> Register file, to read registers.

3. Execution based on instruction type:

   • Use ALU for calculation.

     • Arithmetic result.

     • Memory address for load/store instructions.

     • Branch target address.

   • Access data memory for load/store.

4. Update PC: PC <- Target address or PC + 4.

CPU Overview

• A conceptual overview of the CPU's components and their interconnections.

Multiplexers

• Multiplexers are used to select between multiple inputs based on a control signal.

Control

• Control signals dictate the operation of the datapath elements.

Logic Design Conventions

• Information is encoded in binary (Low voltage = 0, High voltage = 1).

• Multiple bit data is encoded using multi-wire buses.

• Combinational elements operate on data, and their output is a function of their input.

• State elements (sequential) store information.

Combinational Elements

• AND gate: Y = A & B

• Multiplexer: Y = S ? I1 : I0

• Adder: Y = A + B

• Arithmetic/Logic Unit (ALU): Y = F(A, B)

Sequential Elements

• Register: Stores data in a circuit; uses a clock signal to determine when to update the stored value.

  • Edge-triggered: Updates when the clock (Clk) changes from 0 to 1.

• Register with write control: Updates on the clock edge only when the write control input is 1.

Timing Methodology

• Combinational logic transforms data during clock cycles (between clock edges).

• Input comes from state elements, and output goes to state elements.

• The longest delay determines the clock period.

Datapath Construction

• Datapath: elements that process data and addresses in the CPU (registers, ALU, multiplexers, memories).

• A MIPS datapath will be constructed step-by-step.

Instruction Fetch

• The program counter (PC) stores the address of the current instruction.

• The instruction is fetched from memory using the PC.

• The PC is incremented by 4 (address of next instruction).

R-format Instructions

• Read two operand registers.

• Perform an arithmetic/logical operation.

• Write the result to a register.

Load/Store Instructions

• Read operand register.

• Calculate memory address using the 16-bit offset.

  • Use ALU with sign-extension of the offset.

• Load: read memory and update register.

• Store: write register value to memory.

Branch Instructions

• Read operand registers.

• Compare operands using ALU (subtract and check the Zero output).

• Calculate the target address.

  • Sign-extend the displacement.

  • Left shift by 2 (word displacement).

  • Add to PC + 4 (already calculated during instruction fetch).

Branch Instructions (cont.)

• Branch instructions route write back to registers

• Sign-bit is repeated

Building Blocks

• A basic datapath executes one instruction per clock cycle.

• Each datapath element performs only one function at a time.

• Separate instruction and data memories are needed.

• Multiplexers are used when different data sources are used in different instructions.

Datapath for R-type, Load, and Store Instructions

• Diagram of the data path for R-type, load, and store instructions.

Complete Datapath

• A full data path diagram.

ALU Control

• The ALU is used for:

  • Load/Store: operation = add

  • Branch: operation = subtract

  • R-type: operation depends on the funct field

ALU Control Implementation

• A 2-bit ALUOp field is extracted from the opcode.

• Combinational logic derives the ALU control signals.

Main Control Unit

• Control signals are derived from the instruction opcode.

Datapath and Control

• Combined datapath and control unit diagram.

Control Signals

• Control signals used in the datapath.

R-type Instruction Execution

• Step-by-step execution of an R-type instruction.

Load Instruction Execution

• Step-by-step execution of a Load instruction.

Branch-on-Equal Instruction Execution

• Step-by-step execution of a Branch-on-Equal instruction.

Jump Implementation

• Jump instructions use a word address.

• The PC is updated by concatenating:

  • The highest 4 bits of the old PC.

  • The 26-bit jump address.

  • 00

• An additional control signal is needed from the opcode decoder.

Datapath with Jump

• Datapath diagram including jump instruction implementation.

Performance Issues

• The longest delay determines the clock period.

• Critical path: load instruction

• Instruction Memory -> Register File -> ALU -> Data Memory -> Register File

• Different clock periods for different instructions are not feasible.

• This violates the design principle: Make the common case fast."- Performance can be improved with pipelining.

Pipelining Analogy

• Pipelining overlaps execution (like an assembly line).

• Parallelism improves performance.

MIPS Pipelining

• Five stages, one step at each stage:

  • IF: Instruction Fetch from memory

  • ID: Instruction Decode & Register Read

  • EX: Execute operation or calculate address

  • MEM: Access memory operand

  • WB: Write result back to register

Pipelining Performance

• Assuming stage times are:

  • 100ps for register read or write.

  • 200ps for other stages.

• Comparing pipelined vs. single-cycle datapath:

Pipelining Performance

• Single cycle (Tc = 800ps) vs. Pipelined (Tc = 200ps)

Speedup from Pipelining

• Illustration of speedup due to pipelining.

Pipelining and Instruction Set Design

• MIPS ISA is designed for pipelining.

  • All instructions are 32 bits: simplifies fetch and decode in one cycle

  • Few and regular instruction formats: can decode and read registers in one step

  • Load/store addressing: can calculate address in 3rd stage, access memory in 4th stage

  • Alignment of memory operands: memory access takes only one cycle

Hazards

• Situations that prevent starting the next instruction in the next cycle.

  • Structure hazards: required resource is busy

  • Data hazards: need to wait for previous instruction to complete its data read/write

  • Control hazards: decision about control action depends on previous instruction

Structure Hazards

• Conflict in using a resource.

  • In the MIPS pipeline with a single memory, load/store instructions require memory access.

  • Instruction fetch would have to stall, causing a pipeline "bubble."

  • Pipelined datapath requires separate instruction/data memories or separate instruction/data caches.

Data Hazards

• An instruction depends on the completion of a data access by a previous instruction.

  • Example:
    assembly add $s0, $t0, $t1 sub $t2, $s0, $t3

Forwarding

• (Also called Bypassing).

  • Use result when it is available, instead of waiting for it to be written to a register.

  • Requires additional connections in the datapath.

Load/Use Data Hazard

• Load/Use

  • Cannot always avoid stalls with forwarding.

  • If the value is not computed when needed, forwarding is not possible.

  • Cannot forward backward in time!

Code Scheduling to Avoid Stalls

• Reorder code to avoid using the result of a load instruction in the very next instruction.

  • C code:

  A = B + E;
  C = B + F;
  

  • Assembly code with stall vs. reordered code.

  # With stall
  lw  $t1, 0($t0)
  lw  $t2, 4($t0)
  add $t3, $t1, $t2
  sw  $t3, 12($t0)
  lw  $t4, 8($t0)
  add $t5, $t1, $t4
  sw  $t5, 16($t0) # stall
  
  # Reordered code
  lw  $t1, 0($t0)
  lw  $t2, 4($t0)
  lw  $t4, 8($t0)
  add $t3, $t1, $t2
  sw  $t3, 12($t0)
  add $t5, $t1, $t4
  sw  $t5, 16($t0)
  # Cycles goes from 13 cycles to 11 cycles
  

  `

Control Hazards

• The branch determines the flow of control.

• Fetching the next instruction depends on the branch outcome.

• The pipeline cannot always fetch the correct instruction.

• In the MIPS pipeline, registers must be compared and the destination address calculated early in the pipeline (ID stage).

• Additional hardware can be added to do this in the ID stage.

Branch Delay

• Stall on branch

• Wait until the branch outcome is determined before fetching the next instruction.

Branch Prediction

• Larger pipelines cannot determine the outcome of the branch soon.

• The stall penalty becomes extremely large.

  • Predict the outcome of the Branch.

  • Stall only if Prediction was wrong.

    • Can predict a branch not to be taken. Will fetch the next instruction after the branch without any delay.

MIPS with