The Processor
4.1 Introduction
Processor Implementation: The hardware organization that realizes an instruction set architecture.
Datapath: The processor components that store, move, and operate on instruction data.
Control Unit: Hardware that generates signals directing the datapath according to the current instruction.
Instruction Execution: The process of fetching an instruction, reading operands, performing an operation, accessing memory if required, and storing the result.
Program Counter (PC): A register containing the address of the instruction to fetch.
Multiplexor (MUX): A logic element that selects one of several input values according to a control signal.
4.2 Logic Design Conventions
1) Combinational and Sequential Logic
Combinational Element: A logic element whose output depends only on its current inputs.
State Element: A storage element whose output depends on information written during an earlier clock cycle.
Sequential Logic: Logic containing state elements, so its behavior depends on both current inputs and stored state.
2) Clocking
Clock: A periodic signal used to coordinate updates to processor state.
Clock Cycle: The interval between corresponding edges of consecutive clock pulses.
Edge-Triggered Clocking: A convention in which state elements update only at a designated clock edge.
Setup Time: The minimum time an input must remain stable before the active clock edge.
Hold Time: The minimum time an input must remain stable after the active clock edge.
Synchronous System: A system in which state changes are coordinated by a common clock.
4.3 Building a Datapath
1) Instruction Fetch
Instruction Memory: Memory that supplies the instruction stored at the address in the PC.
Sequential PC: The address of the next sequential instruction, normally calculated as in 32-bit MIPS.
2) R-Format Instructions
Register File: A collection of processor registers with ports that allow operands to be read and results to be written.
Arithmetic Logic Unit (ALU): Hardware that performs arithmetic, logical, and comparison operations.
Register Write-Back: The operation of storing an instruction result in a destination register.
3) Load and Store Instructions
Effective Address: The memory address calculated by adding a sign-extended offset to a base-register value.
Data Memory: Memory read by load instructions and written by store instructions.
Sign Extension: Increasing a signed immediate's width by copying its sign bit into the new upper bits.
4) Branch Instructions
Branch Target Address: The address calculated from and the sign-extended branch offset shifted left by two bits.
Zero Signal: An ALU output indicating that the comparison result is zero, used by equality branches.
4.4 A Simple Implementation Scheme
1) Single-Cycle Implementation
Single-Cycle Processor: A processor in which every instruction completes in one clock cycle.
Critical Path: The longest combinational path between state elements, which determines the minimum clock period.
Single-Cycle Limitation: The clock period must be long enough for the slowest instruction, causing simpler instructions to wait unnecessarily.
2) Main Control
Main Control Unit: Logic that decodes the opcode and generates control signals for the datapath.
ALU Control: Logic that combines the instruction's operation fields with the main control signal to select an ALU operation.
| Control signal | Purpose |
|---|---|
RegDst | Selects the destination-register field |
RegWrite | Enables a register-file write |
ALUSrc | Selects a register or immediate as the second ALU input |
ALUOp | Specifies the category of ALU operation |
MemRead | Enables a data-memory read |
MemWrite | Enables a data-memory write |
MemtoReg | Selects memory data or an ALU result for write-back |
Branch | Enables conditional branch selection |
Don't-Care Condition: A control input value that does not affect the result for a particular instruction and may be chosen to simplify logic.
3) Performance
Single-Cycle CPU Time: The product of instruction count and the fixed clock-cycle time when every instruction has a CPI of 1.
4.5 An Overview of Pipelining
1) Pipeline Concept
Pipelining: An implementation technique that overlaps the execution of multiple instructions by dividing execution into stages.
Instruction Throughput: The number of instructions completed per unit time.
Instruction Latency: The time required for one instruction to pass through all pipeline stages.
Pipeline Stage: One portion of instruction execution designed to complete within one clock cycle.
2) Five-Stage MIPS Pipeline
| Stage | Name | Main operation |
|---|---|---|
| IF | Instruction Fetch | Read the instruction and calculate |
| ID | Instruction Decode | Decode and read registers |
| EX | Execute | Perform an ALU operation or calculate an address |
| MEM | Memory Access | Read or write data memory |
| WB | Write Back | Write a result to the register file |
Pipeline Register: A state element that holds data and control information between adjacent pipeline stages.
Ideal Pipeline Speedup: For a large number of instructions and balanced stages, a pipeline with stages can approach a throughput improvement of .
Pipeline Imbalance: Unequal stage delays that force the clock period to match the slowest stage.
3) Pipeline Hazards
Pipeline Hazard: A condition that prevents an instruction from executing in its intended clock cycle.
Structural Hazard: A hazard caused when multiple instructions need the same hardware resource simultaneously.
Data Hazard: A hazard caused by a dependence between instructions.
Control Hazard: A hazard caused by uncertainty about the next instruction address.
Stall: A delay inserted into the pipeline until a hazard is resolved.
Bubble: An empty pipeline slot created by a stall or flushed instruction.
4.6 Pipelined Datapath and Control
1) Pipelined Datapath
IF/ID Register: Holds the fetched instruction and sequential PC value for the decode stage.
ID/EX Register: Holds decoded operands, immediate data, destination fields, and control signals for the execute stage.
EX/MEM Register: Holds the ALU result, store data, destination register, and control signals for the memory stage.
MEM/WB Register: Holds memory or ALU data and the destination register for write-back.
Pipeline State: The complete set of instructions, data, and control signals currently stored throughout the pipeline.
2) Pipelined Control
Control Propagation: Carrying each instruction's control signals through pipeline registers until the stage where they are used.
| Stage | Main control actions |
|---|---|
| EX | Select ALU inputs, ALU operation, and destination register |
| MEM | Control data-memory access and branch decision |
| WB | Select and enable register write-back |
Flush: Replacing an instruction's control signals with zeros so that it produces no architectural effect.
4.7 Data Hazards: Forwarding versus Stalling
1) Data Dependence
Read After Write (RAW) Dependence: A true data dependence in which an instruction must read a value produced by an earlier instruction.
Pipeline Data Hazard: A RAW dependence that would cause an instruction to read an operand before the earlier instruction has produced or written it.
2) Forwarding
Forwarding (Bypassing): Sending a result directly from a later pipeline stage to an earlier stage that needs it, without waiting for register write-back.
Forwarding Unit: Hardware that detects eligible dependencies and selects a forwarded value as an ALU input.
EX Hazard: A dependence satisfied by forwarding an ALU result from the EX/MEM pipeline register.
MEM Hazard: A dependence satisfied by forwarding a result from the MEM/WB pipeline register.
3) Load-Use Hazard
Load-Use Hazard: A data hazard in which an instruction immediately following a load needs the loaded value before memory access has completed.
Hazard Detection Unit: Hardware that detects a hazard requiring a stall and prevents selected pipeline state from advancing.
Pipeline Interlock: Hardware that detects a hazard and stalls dependent instructions until execution is safe.
Load-Use Stall: A one-cycle delay normally required in the basic five-stage pipeline when a load is immediately followed by a dependent instruction.
4.8 Control Hazards
1) Branch Hazards
Branch Hazard: A control hazard that occurs because the processor does not immediately know whether a branch is taken or what instruction should be fetched next.
Branch Penalty: The cycles or instructions lost while determining or recovering from a branch outcome.
Branch Resolution: The pipeline stage in which the branch condition and target address become known.
2) Branch Prediction
Static Branch Prediction: A fixed prediction policy determined without using recent runtime behavior.
Dynamic Branch Prediction: Prediction based on the recorded behavior of branches during execution.
Branch Prediction Buffer: A table indexed by branch addresses that stores recent branch behavior.
One-Bit Predictor: A predictor that records whether a branch was taken on its previous execution.
Two-Bit Predictor: A finite-state predictor that normally requires two consecutive incorrect outcomes to reverse its prediction.
Branch Target Buffer (BTB): A cache that stores predicted branch target addresses so fetching can continue without waiting for target calculation.
Misprediction: An incorrect branch prediction that requires speculative instructions to be flushed.
4.9 Exceptions
1) Exception Handling
Exception: An unexpected event generated within the processor that changes normal control flow.
Interrupt: An externally generated event that requests processor attention.
Exception Handler: Operating-system code that identifies and responds to an exception or interrupt.
Exception Program Counter (EPC): A register that stores the address of the instruction associated with an exception.
Cause Register: A system register containing information about the reason for an exception.
Exception Vector: A predefined address to which control transfers when an exception occurs.
2) Exceptions in a Pipeline
Precise Exception: An exception model in which all older instructions complete, the faulting and younger instructions have no architectural effect, and execution can be resumed consistently.
Pipeline Exception Handling: The process of recording the faulting instruction, flushing younger instructions, disabling unwanted writes, and transferring control to the handler.
Restartable Exception: An exception after which execution can safely resume at the interrupted or following instruction, according to the architecture.
4.10 Parallelism via Instructions
1) Instruction-Level Parallelism
Instruction-Level Parallelism (ILP): The parallel execution of independent instructions from one instruction stream.
Multiple Issue: A processor technique that launches more than one instruction in a clock cycle.
Issue Width: The maximum number of instructions that can be issued in one clock cycle.
Instructions Per Cycle (IPC): The average number of instructions completed or issued per clock cycle, depending on the measurement definition.
2) Static Multiple Issue
Static Multiple Issue: A design in which the compiler performs much of the instruction scheduling and hazard avoidance.
Issue Packet: A group of instructions intended to issue together in one clock cycle.
Very Long Instruction Word (VLIW): An ISA style that encodes several independent operations in one wide instruction.
Loop Unrolling: Replicating a loop body to expose more independent instructions and reduce loop-control overhead.
Register Renaming: Assigning different registers to independent values that originally reused the same register name.
Name Dependence: An apparent dependence caused by reusing a register or memory name rather than by actual data flow.
3) Dynamic Multiple Issue
Dynamic Multiple Issue: A design in which hardware decides at runtime which instructions can issue together.
Superscalar Processor: A dynamically scheduled processor capable of issuing multiple instructions per cycle.
Dynamic Scheduling: Hardware reordering of instruction execution to reduce stalls while preserving correct program behavior.
Out-of-Order Execution: Execution of ready instructions before earlier stalled instructions when dependencies permit it.
In-Order Commit: Updating architectural state in original program order even when instructions execute out of order.
4) Speculation
Speculation: Executing an instruction before it is known to be required or safe, based on a prediction.
Hardware Speculation: Speculation managed by processor hardware with mechanisms for buffering results and recovering from incorrect predictions.
Speculation Recovery: Discarding speculative results and restoring correct state after a prediction is found to be wrong.
4.11 Real Stuff: Modern Processor Pipelines
Deep Pipeline: A pipeline divided into many short stages to support a shorter clock period.
Micro-operation: A simple internal operation into which a processor may translate a more complex instruction.
Front End: Processor hardware that fetches, predicts, decodes, and prepares instructions for execution.
Execution Engine: Processor hardware containing schedulers, functional units, and mechanisms for out-of-order execution.
Retirement: The ordered commitment of a completed instruction's result to architectural state.
Reorder Buffer (ROB): Hardware that tracks in-flight instructions and supports in-order retirement and precise exceptions.
4.12 Going Faster: ILP and Matrix Multiply
Instruction Scheduling: Reordering independent instructions to reduce stalls and increase functional-unit utilization.
Software Pipelining: Scheduling operations from different loop iterations so they execute in an overlapped manner.
Loop Unrolling for ILP: Expanding several loop iterations to expose independent operations to a multiple-issue processor.
Register Pressure: Increased demand for registers caused by keeping more intermediate values active simultaneously.
ILP Limitation: Data dependencies, control dependencies, memory latency, issue width, and hardware resources restrict exploitable instruction-level parallelism.
4.13 Hardware Description Languages
Hardware Description Language (HDL): A language used to describe, simulate, and synthesize digital hardware.
Register-Transfer Level (RTL): A hardware description level that specifies registers, combinational operations, and transfers between registers on clock events.
Simulation: Executing a hardware model to verify its behavior before physical implementation.
Synthesis: Translating an HDL description into a gate-level hardware implementation.
4.14 Fallacies and Pitfalls
Pipelining-Is-Easy Fallacy: Correct pipeline design is difficult because data, control, timing, and exception interactions must all be handled consistently.
Technology-Independent Pipeline Fallacy: The best pipeline organization depends on transistor speed, memory latency, power limits, and available hardware resources.
ISA Pipeline Pitfall: Variable instruction lengths, complex addressing modes, and irregular execution times can complicate decoding, hazard detection, and pipeline balance.
Ideal-Speedup Pitfall: More pipeline stages or wider issue do not guarantee proportional performance because hazards, imbalance, mispredictions, and overhead reduce utilization.
4.15 Concluding Concepts
Datapath-Control Relationship: The datapath performs instruction operations while the control unit selects and sequences those operations.
Pipeline Performance: Pipelining primarily improves instruction throughput rather than the latency of a single instruction.
Hazard Resolution: Structural hazards require sufficient resources, data hazards use forwarding or stalls, and control hazards use prediction and recovery.
Multiple-Issue Performance: Multiple issue reduces average CPI by executing several independent instructions in the same cycle.
Dependence Limit: Data and control dependencies fundamentally limit the instruction-level parallelism available in a program.
Processor Design Trade-off: Processor implementations balance clock rate, CPI, hardware complexity, power consumption, and design correctness.