Concept summary

Foundations and performance

Computer architecture

The design and organization of a computer system, including its instruction set and the hardware that carries it out.

ISA vs microarchitecture

The instruction set is the contract software relies on; the microarchitecture is one hardware design that implements it.

CPI

Average clock cycles per instruction. CPU time = instruction count × CPI × cycle time.

Amdahl's law

Speeding up part of a task is limited by the part you cannot speed up.

Dennard scaling

Shrinking transistors once kept power density constant; when it ended, clock speeds stopped rising and designs turned to parallelism.

Memory wall

Processors got faster much more quickly than memory, so memory access time dominates without caches.

Instruction sets

RISC

Simple, fixed-length instructions designed to pipeline well and execute quickly. Examples: Arm, RISC-V.

CISC

Complex, variable-length instructions that can work on memory directly and may take multiple cycles. Example: x86.

Load–store architecture

Only loads and stores touch memory; arithmetic uses registers.

Addressing mode

The rule an instruction uses to compute a memory address, such as base + offset.

Instruction encoding

Every instruction has a fixed number of bits to share among the opcode, registers and constants.

Pipelining

Pipelining

Overlapping the execution of several instructions in stages, like an assembly line. It increases throughput, not the speed of any one instruction.

Five-stage pipeline

Fetch, decode, execute, memory access and write back.

Hazard

Anything that stops the next instruction from starting on time; it causes a stall (an empty slot, or bubble).

Structural hazard

Two instructions need the same hardware resource at the same time.

Data hazard

An instruction needs the result of a previous instruction that is not ready yet.

Control hazard

The next instruction depends on a branch that has not been resolved.

RAW, WAR, WAW

Dependences between instructions: read after write is a true data flow; WAR and WAW only reuse a register name.

Forwarding

Passing a result directly to a later instruction instead of waiting for it to be written back, avoiding most data-hazard stalls.

Branch prediction

Guessing a branch's outcome so the pipeline keeps fetching instead of stalling.

Superpipelining

More, shorter stages for a faster clock, at the cost of bigger hazard penalties.

Superscalar and VLIW

Issuing several instructions per cycle, chosen by hardware (superscalar) or packed by the compiler (VLIW).

Caches

Cache

A small, fast memory near the processor that holds copies of recently used data.

Locality

Programs reuse recent data (temporal) and use nearby data (spatial), which is why caches work.

Hit rate

The fraction of accesses found in the cache. A high hit rate means most requested data is already there.

AMAT

Average memory access time = hit time + miss rate × miss penalty.

Direct-mapped

Each memory block can go in exactly one cache line.

Fully associative

A memory block can go in any cache line.

Set-associative

A block can go in any of a few lines in one set: a compromise between direct-mapped and fully associative.

Three Cs

Why caches miss: compulsory (first use), capacity (too much data) and conflict (too many blocks in one set).

Write-back vs write-through

Update only the cache and write changes later, or update the next level on every write.

Replacement policy

The rule for choosing which line to evict when the cache is full, such as LRU (least recently used).

Prefetching

Bringing data into the cache before it is requested.

Multilevel caches

L1, L2 and L3 caches that reduce average memory access time: a small, fast L1 backed by larger, slower levels.

Parallel processing

Flynn's taxonomy

Classifies machines by instruction and data streams: SISD, SIMD, MISD and MIMD.

SIMD

One instruction on many data elements at once; best for processing large datasets in parallel.

MIMD

Independent processors each running their own instructions on their own data, as in multicore chips and clusters.

GPU

Thousands of threads running in SIMD-style groups, built for massive data parallelism.

Multicore processor

Several cores on one chip with private caches, a shared last-level cache and an on-chip network.

Cache coherence

Keeps every core's cached copy of a location consistent, typically with a protocol such as MESI.

Gustafson's law

When the problem grows with the machine, speedup can grow almost linearly with processor count.

At a glance: where speed comes from