Processor Architecture introduction

• The Big Picture
• CPU Basics
• Clocks
• ISA (Instruction Set Architecture)
  • Instruction Processing
  • Instruction Execution
  • Instruction Formats
  • Addressing Modes
  • RISC vs. CISC
    • RISC Characteristics
  • Architecture Implementation
• uArch
  • Pipelining
    • What Is Pipelining
    • Instruction-Level Pipelining
    • The Five Stages of Load
    • Pipeline Hurdles
    • Insert “Bubble” into the Pipeline
    • Data hazards
  • Predict Branch
  • Out-of-order execution
  • Register renaming
  • Parallelism
  • Superscalar
    • Superscalar Execution
  • Superpipelined
  • VLIW - Very long instruction word
  • Multithreading
  • Cache
    • Memory Hierarchy
    • Cache
    • Cache Design
    • Cache Line
    • Three Major Placement Schemes
    • Direct-Mapped Cache
    • Two-Way Set-Associative Cache
    • Replacement Strategies
    • Writing to Memory
    • Cache Coherence

The article is converted from a PPT which was written by me in 2013 used to train our team software engineers.

The Big Picture

CPU Basics

• The computer’s CPU fetches, decodes, and executes program instructions.

• The two principal parts of the CPU are the datapath and the control unit.

  • The datapath consists of an arithmetic-logic unit and storage units (registers) that are interconnected by a data bus that is also connected to main memory.
  • Various CPU components perform sequenced operations according to signals provided by its control unit.
  • The control unit determines which actions to carry out according to the values in a program counter register and a status register.

Clocks

• Every computer contains at least one clock that synchronizes the activities of its components.

• A fixed number of clock cycles are required to carry out each data movement or computational operation.

• The clock frequency, measured in megahertz or gigahertz, determines the speed with which all operations are carried out.

• Typical Intel and typical PIC clocks look like this:
  • 2 GHz clock has a cycle time of 0.5 nanoseconds.
  • 8 MHz clock has a cycle time of 0.125 microseconds.
• One master clock has multiple frequencies used for various parts of the system.

ISA (Instruction Set Architecture)

• Instruction Set Architecture is the structure of a computer that a machine language programmer (or a compiler) must understand to write a correct (timing independent) program for that machine.

• ISA is the set of all instructions that the microprocessor can execute

• The set of instructions executed by a modern processor may include:
  • Data transfer instructions
    • data movement (load, store, push, pop, move, swap - registers)
  • Data operation instructions
    • arithmetic and logical (negate, extend, add, subtract, multiply, divide, and, or, shift)
  • Program control instructions
    • control transfer (jump, call, trap - jump into the operating system, return - from call or trap, conditional branch)

Instruction Processing

• The datapath based on data transfers required to perform instructions
• A controller causes the right transfers to happen

Instruction Execution

Instruction Formats

In designing an instruction set, consideration is given to:

• Instruction length.
  • Whether short, long, or variable.
• Number of operands.
• Number of addressable registers.
• Memory organization.
  • Whether byte - or word addressable.
• Addressing modes.
  • Choose any or all: direct, indirect or indexed

Addressing Modes

Instructions can specify many different ways to obtain their data

• data in instruction
• data in register
• address of data in instruction
• address of data in register
• address of data computed from two or more values contained in the instruction and/or registers

On a RISC machine, arithmetic/logic instructions use only the first two of these ADDRESSING MODES

On a CISC machine, all addressing modes are generally available to all instructions

RISC vs. CISC

• The believe that better performance would be obtained by reducing the number of instruction required to implement a program, lead to design of processors with very complex instructions (CISC)

  CISC – Complex Instruction Set Computers

• As compiler technologies improved, researchers started to wonder if CISC architectures really delivered better performances than architectures with simpler instruction set

  RISC – Reduced Instruction Set Computers

• Addition of two operands from memory, with result written in memory, in RISC and CISC architectures

• Having an operation broken into small instructions (RISC) allows the compiler to optimize the code > i.e. between the two LD instructions (memory is slow) the compiler can add some instructions that don’t need memory access

• The CISC instruction has no option but to wait for its operands to come from the memory, potentially delaying other instructions

RISC Characteristics

• One instruction per cycle
• Register to register operations
• Few, simple addressing modes
• Few, simple instruction formats
• Hardwired design (no microcode)
• Fixed instruction format
• More compile time/effort

Architecture Implementation

uArch

Pipelining

What Is Pipelining

• Pipelining doesn’t help latency of single task, it helps throughput of entire workload
• Pipeline rate limited by slowest pipeline stage
• Multiple tasks operating simultaneously
• Potential speedup = Number pipe stages
• Unbalanced lengths of pipe stages reduces speedup
• Time to “fill” pipeline and time to “drain” it reduces speedup

Instruction-Level Pipelining

• For every clock cycle, one small step is carried out, and the stages are overlapped.

• S1. Fetch instruction.
• S2. Decode opcode.
• S3. Calculate effective address of operands.
• S4. Fetch operands.
• S5. Execute.
• S6. Store result.

The Five Stages of Load

• Ifetch: Instruction Fetch
  • Fetch the instruction from the Instruction Memory
• Reg/Dec: Registers Fetch and Instruction Decode
• Exec: Calculate the memory address
• Mem: Read the data from the Data Memory
• Wr: Write the data back to the register file

Pipeline Hurdles

Limits to pipelining: Hazards prevent next instruction from executing during its designated clock cycle.

• Structural hazards: HW cannot support this combination of instructions
  • two different instructions use same h/w in same cycle
• Data hazards: Instruction depends on result of prior instruction still in the pipeline
  • two different instructions use same storage
  • must appear as if the instructions execute in correct order
• Control hazards: Pipelining of branches & other instructions that change the PC
  • one instruction affects which instruction is next
• Common solution is to stall the pipeline until the hazard is resolved, inserting one or more “bubbles” in the pipeline

Insert “Bubble” into the Pipeline

Data hazards

Predict Branch

• Advantages
  • The main purpose of predication is to avoid jumps over very small sections of program code, increasing the effectiveness of pipelined execution and avoiding problems with the cache.
• Disadvantages
  • Predication’s primary drawback is in increased encoding space.
• 1-bit Prediction
• 2-bit Prediction

Out-of-order execution

Processor executes instructions in an order governed by the availability of input data, rather than by their original order in a program

Register renaming

Parallelism

• Instruction Level Parallelism
  • Superscalar
  • VLIW
• Data Level Parallelism
  • SIMD (Single Instruction Multiple Data)
  • MMX
• Thread Level Parallelism
  • Multithreading
  • Multicore
  • Multiprocessor

Superscalar

• Common instructions (arithmetic, load/store, conditional branch) can be initiated and executed independently
  • Improve these operations by executing them concurrently in multiple pipelines
  • Requires multiple functional units
  • Requires re-arrangement of instructions

Superscalar Execution

Superpipelined

• Many pipeline stages need less than half a clock cycle
• Double internal clock speed gets two tasks per external clock cycle

VLIW - Very long instruction word

• Why
  • To overcome the difficulty of finding parallelism in machine-level object code.
  • In a VLIW processor, multiple instructions are packed together and issued in parallel to an equal number of execution units.
  • The compiler (not the processor) checks that there are only independent instructions executed in parallel.
• characteristics
  • VLIW contains multiple primitive instructions that can be executed in parallel by functional units of a processor.
  • The compiler packs a number of primitive, non-interdependent instructions into a very long instruction word
  • Since multiple instructions are packed in one instruction word, the instruction words are much larger than CISC and RISC’s.

Multithreading

Cache

• The goal of a cache in computing is to keep the expensive CPU as busy as possible by minimizing the wait for reads and writes to slower memory.

Memory Hierarchy

Cache

• Processor does all memory operations with cache.
• Miss – If requested word is not in cache, a block of words containing the requested word is brought to cache, and then the processor request is completed.
• Hit – If the requested word is in cache, read or write operation is performed directly in cache, without accessing main memory.
• Block – minimum amount of data transferred between cache and main memory.

Cache Design

The level’s design is described by four behaviors:

• Block Placement:
  • Where could a new block be placed in the given level?
• Block Identification:
  • How is a existing block found, if it is in the level?
• Block Replacement:
  • Which existing block should be replaced, if necessary?
• Write Strategy:
  • How are writes to the block handled?

Cache Line

Three Major Placement Schemes

Direct-Mapped Cache

Two-Way Set-Associative Cache

Replacement Strategies

• Which existing block do we replace, when a new block comes in?

• With a direct-mapped cache:
  • There’s only one choice! (Same as placement)
• With a (fully- or set-) associative cache:
  • If any “way” in the set is empty, pick one of those
  • Otherwise, there are many possible strategies:
    • Random: Simple, fast, and fairly effective
    • FIFO
    • Least-Recently Used (LRU)

Writing to Memory

• Cache and memory become inconsistent when data is written into cache, but not to memory – the cache coherence problem.
• Strategies to handle inconsistent data:
  • Write-through -Write to memory and cache simultaneously always.
    • Write to memory is ~100 times slower than to (L1) cache.
  • Write-back
    • Write to cache and mark block as “dirty”.
    • Write to memory occurs later, when dirty block is cast-out from the cache to make room for another block

Cache Coherence

• Also, before a DMA transfer, need to determine if information in main memory is up-to-date with information in cache. (write back protocol)

• One solution is to always flush the cache by forcing the dirty data to be written back to memory before a DMA transfer takes place

• MESI