Transistors

A transistor is a switch that a wire controls

Gate voltage lowGateSourceDrainblockedno current: this is a 0Gate voltage highGateSourceDraincurrent flows: this is a 1A switch with no moving parts: one wire decides whether another conducts.20 nmgate length: about 4,000 fitacross a human hair1 picosecondto switch: a trilliontimes a second100 – 200 billionon one chip the sizeof a thumbnail

Everything in a computer is built from one part: the transistor. Voltage on its gate decides whether current may pass.

Transistors · Going deeper

A MOSFET as a controlled switch source drain gate channel n-channel MOSFET gate channel 0 V (low) open · no current VDD (high) closed · conducts ≈20 nm gate length · ≈1 ps switching · ≈1011 per modern die two stable states · noise margin · cheap to copy — the substrate of everything above

Inside the switch

This is a MOSFET. It has only two stable outputs, so a noise margin separates them and a bit can pass through millions of stages without degrading. The build has changed (planar, FinFET, gate-all-around) but the contract has not: voltage in, current allowed or denied.

Logic gates and adders

Wire switches together and they do logic, then arithmetic

ANDtwo switches in a rowABoutA B out0 0 → 00 1 → 01 0 → 01 1 → 1both must be onORtwo switches side by sideABoutA B out0 0 → 00 1 → 11 0 → 11 1 → 1either one is enoughTwo gates add one columnthe first circuit that does arithmeticA = 1B = 1ANDXORcarry1sum01 + 1 = 10binary for two: write 0, carry 1XOR means: exactly one is onChain 64 of these adders and the chip adds 64-bit numbers. Multiplying is shifted adding.One NAND gate (AND, then flip the answer) is 4 transistors, and NAND alone can build every other gate.Here the machine stops being electrical and starts being mathematical.

A logic gate is a handful of transistors with a fixed rule. Combine gates and the rule becomes addition.

Logic gates and adders · Going deeper · 1 of 2

The four primitive logic gates and their truth tables AND A B · Y 0 0 0 0 1 0 1 0 0 1 1 1 OR A B · Y 0 0 0 0 1 1 1 0 1 1 1 1 NOT A · Y 0 1 1 0 XOR A B · Y 0 0 0 0 1 1 1 0 1 1 1 0 NAND alone (or NOR alone) is enough — every Boolean function reduces to one repeated gate "functional completeness" is what makes the leap from physics to math possible

The four common gates

AND, OR, NOT and XOR are shorthand for the patterns that appear most. NAND alone, or NOR alone, is functionally complete: any Boolean expression can be built from one repeated gate. A truth table is the contract a gate keeps.

Logic gates and adders · Going deeper · 2 of 2

Half-adder: XOR for sum, AND for carry A B Sum Carry XOR AND A B Sum Carry 0 0 0 0 0 1 1 0 1 0 1 0 1 1 0 1 Sum is "exactly one input high"; Carry is "both inputs high"

From half-adder to 64-bit adder

Two half-adders and an OR make a full adder, which also takes a carry in. Chained naively, the carry ripples through all 64 columns. Real designs use carry-lookahead to finish in about log₂(64) = 6 gate delays.

Clocked memory

Memory is a circuit that only listens when the clock ticks

clockinput Dstored Qtickticktickchanged between ticks: ignoredcopies Dcopies Dcopies D64 flip-flops on one clock = a 64-bit register: the processor’s working memory.At 3 GHz the clock ticks 3 billion times a second. One tick lasts 333 picoseconds:the time light takes to travel about 10 cm. The slowest path between two flip-flops sets the top speed.

A flip-flop copies its input at each clock tick and holds it until the next. That is how a chip remembers, and why it has a clock.

Clocked memory · Going deeper

D flip-flop: Q samples D on the rising edge of the clock D clk Q Q' D-FF edge-triggered · one bit of state clk D Q ↑ ↑ ↑ rising edges sample D into Q

Why edges make design possible

A D flip-flop has one data input, one clock input and one output. Because changes between rising edges are ignored, a designer only has to make each stage finish within one cycle. Flip-flops plus logic make a state machine: every counter and controller in a chip.

The instruction cycle

A processor is one loop: fetch, decode, execute, write back

Program in memory100load r1 ← 5101load r2 ← 7102add r3 ← r1 + r2103store r3Program counter: 102the address to run next1 Fetchread the instructionat address 1022 Decodeoperation: addregisters: r1, r2 → r33 Executethe adder computes5 + 7 = 124 Write backr3 ← 12counter ← 103repeatRegistersr1 = 5r2 = 7r3 = 1216 – 32 of them,64 bits each: thefastest storage there isEvery program, from a game to a database, becomes this loop.The list of instructions a chip understands is its instruction set: x86-64 (most PCs and servers), Arm (phones, newer laptops), RISC-V (open).

A CPU core reads one instruction, does the tiny thing it names, stores the result and moves to the next. Billions of times a second.

The instruction cycle · Going deeper · 1 of 2

Inside a CPU core: control unit, register file, ALU Instruction memory Data memory Control unit Register file ALU addresses → bytes load · store aligned access decode · sequence x0 … x31 named scratch space add · sub · and · or shift · cmp · mul fetch control signals load / store operands result control · datapath · register file · ALU — the four pieces every ISA exposes in some form

The four pieces of a core

Registers: 16 to 32 named slots, the fastest memory there is. The ALU does the maths. The control unit decodes and pulls the right wires. Buses move the bits. Every microcontroller still looks like this.

The instruction cycle · Going deeper · 2 of 2

The same operation in three ISAs: x86-64, ARM A64, RISC-V Operation: r1 = r2 + r3, then store r1 to memory x86-64 (CISC) ARM A64 (RISC) RISC-V (RISC) add rax, rbx mov [rcx], rax add x0, x1, x2 str x0, [x3] add x10, x11, x12 sw x10, 0(x13) encoding: 1–15 bytes variable length ≈ 1500 base instructions memory operands allowed Intel · AMD encoding: fixed 4 bytes 31 GP regs (x0–x30) ≈ 400 base instructions load/store only to mem Apple · Qualcomm · etc. encoding: 4 bytes (RV32I) 32 GP regs (x0–x31) ≈ 50 base instructions load/store only to mem SiFive · academic · IoT variable-length CISC: dense binaries, hard to decode · fixed-length RISC: simpler decode, more instructions all three are translated to similar internal micro-ops once inside the core

The contract with software

An instruction set architecture says which instructions exist and how they are encoded. x86-64 has variable-length instructions of 1 to 15 bytes; Arm and RISC-V use fixed 32-bit ones. Everything above the ISA is portable; everything below is not.

Pipelining

A pipeline overlaps instructions, like an assembly line

123456789101112131415clock tickOne at a timeinstruction 1FDEMWinstruction 2FDEMWinstruction 3FDEMW3 instructions in 15 ticksOverlapped (a pipeline)instruction 1FDEMWinstruction 2FDEMWinstruction 3FDEMWinstruction 4FDEMWinstruction 5FDEMWtick 5: five in flight5 instructions in 9 ticks.From tick 5 on, one finishesevery tick: 5× the work fromthe same gates and clock.F fetch · D decode · E execute · M memory · W write back. Each instruction still takes 5 ticks; it is the throughput that grows.

Pipelining starts the next instruction before the last one finishes. Each still takes five ticks, but one completes every tick.

Pipelining · Going deeper · 1 of 2

A 5-stage pipeline: five instructions overlap to retire one per cycle cycle 1 2 3 4 5 6 7 8 9 i1 i2 i3 i4 i5 IF ID EX MEM WB IF ID EX MEM WB IF ID EX MEM WB IF ID EX MEM WB IF ID EX MEM WB steady state · one instruction retires per cycle 5 instructions in flight · 5× throughput at the same clock individual latency unchanged · throughput is what scales

The classic five stages

IF fetch, ID decode, EX execute, MEM memory access, WB write back. Latency per instruction is unchanged; throughput is what scales. Modern cores go further and fetch and retire 4 to 8 instructions per cycle.

Pipelining · Going deeper · 2 of 2

Data hazard: the stall (top) and the forwarding fix (bottom) Stall: bubble inserted Forwarding: result routed EX → EX cyc 1 2 3 4 5 6 7 i1: add r3,r1,r2 i2: sub r5,r3,r4 IF ID EX MEM WB IF ID stall stall EX MEM i2 reads r3 — must wait for i1 WB · 2 cycles lost i1: add r3,r1,r2 i2: sub r5,r3,r4 IF ID EX MEM WB IF ID EX MEM WB forward a wire from EX-out to EX-in turns a 2-cycle stall into a 0-cycle hazard

When one instruction needs the last one’s result

If instruction 2 reads a register instruction 1 is still computing, the naive fix is to stall. The real fix is forwarding: route the result straight from one execute stage to the next. Out-of-order cores go further, keeping 200 or more instructions in flight and committing them in program order.

Check yourself

FDEMWFDEMWFDEMWFDEMW12345678

With a five-stage pipeline, how long does a single instruction take from start to finish?

Branch prediction

The chip guesses at every fork, and is right 95% of the time

At a fork (“if x > 0 …”) the pipeline must fetch something before it knows which way the program goes.So the chip guesses, and starts work on the guessed path.Guess rightifA1A2A3A4A5A6A7A8no time lostGuess wrongifA1A2A3A4throw away, refill: 15 – 20 ticksB1B2B3B4work on path A was wasted: 50 – 100 small operations on a wide coreIt pays because the guesses are good:of 100 forks95 or more guessed right, by remembering what each fork did last time5 wrongDiscarded work still leaves traces in the cache. Reading those traces is the Spectre attack.

Branch prediction keeps the pipeline full by betting on which way an “if” will go. A wrong bet costs 15 to 20 ticks of discarded work.

Branch prediction · Going deeper

Branch prediction: a 2-bit saturating counter as a state machine 00 01 10 11 strong not taken weak not taken weak taken strong taken taken not taken taken not taken taken not taken not taken taken predict not taken predict taken two consecutive surprises to flip the prediction · ≥ 95% accuracy on real branchy code

How the guess is made

The simplest predictor is a 2-bit counter per branch with four states, from strongly not taken to strongly taken. One surprise does not flip it; two in a row do. Real predictors add history tables. A loop that runs ten times mispredicts once, at the exit.

Memory hierarchy

Memory is a pyramid because fast memory has to be small

how long the processor waits for one read (bar length = clock ticks, to scale)Registersabout 256 bytesno waitL1 cache32 – 64 KB4 ticksL2 cache256 KB – 2 MB12 ticksL3 cache8 – 64 MB40 ticksMain memory (RAM)8 – 512 GB150 tickswhile it waits, the processor could have run hundreds of instructionsSSD0.5 – 8 TB→150,000 ticks: this bar would be 1,000 pages wideSmall is fast, big is slow, so chips keep copies of what was used lately close by: a cache.Asking for 1 byte brings its 64-byte neighbourhood. Code that walks memory in order stays in the fast levels and can run 10× faster.

Main memory is about 150 ticks away, so a cache keeps recent data close. Programs that reuse nearby data run far faster.

Memory hierarchy · Going deeper · 1 of 4

The memory hierarchy with sizes and latencies Registers L1 cache L2 cache L3 cache Main memory (DRAM) SSD HDD / network storage ≈0 cyc ≈4 cyc ≈12 cyc ≈40 cyc ≈150 cyc ≈150,000 cyc ≈15,000,000 cyc ≈256 B 32–64 KB 256 KB – 2 MB 8 – 64 MB 8 – 512 GB 0.5 – 8 TB multi-TB latency · per access capacity · per level a register access is >1,000,000× faster than a disk seek numbers approximate · vary by chip generation · 1 cycle ≈ 0.3 ns at 3 GHz

Sizes and waits at each level

Each level is roughly 5 to 30 times larger and 3 to 10 times slower than the one above. One cycle is about 0.3 ns at 3 GHz. A register access is more than a million times faster than a disk seek.

Memory hierarchy · Going deeper · 2 of 4

Temporal vs spatial locality Temporal Spatial same address re-accessed in time nearby addresses accessed together addr A · addr B · addr A · addr B · addr A loop counter · cached lookup · hot lock time → arr[0] arr[1] arr[2] arr[3] arr[4] … array scan · packed struct · instruction stream address →

Locality: why the bet pays

Temporal locality: what was used is used again soon. Spatial locality: its neighbours are next. Both are properties of programs, not hardware. An L3 miss rate above a few percent is usually fixable.

Memory hierarchy · Going deeper · 3 of 4

MESI cache-coherence states for one cache line, per core M E S I Modified Exclusive Shared Invalid local write remote read remote write local read local write remote write / evict M: dirty, only-copy — must write back on eviction E: clean, only-copy — silently upgradeable to M S: clean, may exist in other caches — read-only I: invalid — must refetch on next access MESI: four states per cache line, per core

Two cores, one cache line

When cores share a 64-byte line, the MESI protocol keeps their copies consistent. If two threads write different bytes of the same line, it ping-pongs between caches: false sharing, which can make a loop 10 times slower. Pad hot per-thread fields onto separate lines.

Memory hierarchy · Going deeper · 4 of 4

Virtual-to-physical address translation through the TLB VPN (virtual page number) offset virtual address (issued by core) TLB VPN → PFN cache ≈ 64–2048 entries hit · ≈ 1 cycle page-table walk miss · ≥ 100 cycles · DRAM install in TLB PFN (physical frame) offset physical address PFN from TLB · offset unchanged DRAM access ≈ 100 ns to fetch a line TLB hit ≈ 1 cycle · TLB miss + walk ≈ 100+ cycles · context switch may flush the whole table

Translating addresses: the TLB

Programs see virtual addresses; RAM is indexed by physical ones. The TLB caches recent translations. A hit costs one cycle; a miss walks a four-level page table, four more RAM reads. Huge pages of 2 MB cover 512 ordinary 4 KB pages with one entry.

Check yourself

Loop ALoop B memory stores the grid row after row

Two loops add up the same grid of numbers. Which is faster on a real machine?

Multicore

Clocks stopped getting faster in 2005, so chips grew more cores

growth since 1985 (each line up = 10× more)1×10×100×1,000×10,000×100,000×1,000,000×19851995200520152025transistors per chipclock speed: flat at 3 – 5 GHz2005: the power wallpower ∝ voltage² × clock speedvoltage could not drop further,so a faster clock meant heatno cooler could removeSo chips grew sidewaysdesktop: 8 – 32 coresserver: 64 – 192 coresplus graphics and AI blocksOne thread on one core got little faster.Speed now comes from using many cores,and that work moved to programmers.Approximate values for leading chips. Transistor counts kept doubling; the clock did not.

Transistors kept shrinking, but heat capped the clock: the power wall. Since then, more speed means more cores, not faster ones.

Multicore · Going deeper · 1 of 2

The power wall — frequency plateaus while transistor count keeps climbing 1011 109 107 105 103 1985 1995 2005 2015 2025 Transistors / die Clock frequency Single-thread perf ≈2005: power wall log scale Moore's law continues; Dennard scaling does not

Why the wall is where it is

Dynamic power in CMOS is roughly C · V² · f. While voltage fell with each generation, power per transistor fell too. Leakage put a floor under voltage around 2005, and raising f at fixed V meant power no 1 cm² of silicon could shed.

Multicore · Going deeper · 2 of 2

A multi-core die — cores share L3 and a memory bus Core 0 Core 1 Core 2 Core 3 L1 + L2 private L1 + L2 private L1 + L2 private L1 + L2 private Shared L3 cache Memory controller · interconnect more transistors → more cores, not faster cores

Many cores, and memory that is not uniform

Cores share the L3 cache and coordinate through atomic operations. With more than one socket, memory is NUMA: local RAM is about 80 ns away, the other socket’s 120 to 150 ns. Where a thread runs and where its pages were first touched can change throughput by 1.5 to 2 times.

Check yourself

4 cores 64 coresthe program uses one core on each chip

A program runs as a single thread. You move it from a 4-core chip to a 64-core chip with the same clock speed. What happens?

CPUs and GPUs

A CPU has a few clever lanes; a GPU has thousands of simple ones

CPU: a few clever laneseach guesses, reorders and caches to finish one job fast8 – 32 cores, each doing something differentGPU: thousands of simple lanesall doing the same step on different numbersabout 10,000 lanes, in groups of 32Which chip for which workCPUone thing after another,full of forks: most programsGPUthe same sum on millions of pixelsor numbers: 5 – 20× the work per wattAcceleratorone job only, e.g. AI maths:16,384 multiply-adds per tick

No single shape of silicon wins. A GPU gives up cleverness per lane to run the same maths on thousands of numbers at once.

CPUs and GPUs · Going deeper · 1 of 2

CPU vs GPU — latency cores vs throughput cores CPU core (SISD) GPU (SIMT) one instruction → one data → one result one instruction → many lanes → many results Fetch / decode ALU Result Fetch / decode (one) ALU ALU ALU ALU ALU ALU ALU ALU 8 results / cycle CPU: low latency on the critical path · GPU: high throughput on regular work illustrative — a real GPU has thousands of lanes grouped into warps of 32

Latency cores and throughput cores

SIMD is this idea inside a CPU: 4 to 16 lanes in a vector unit. SIMT is the GPU at scale, with warps of 32 lanes sharing one fetch unit. Branchy, irregular code belongs on the CPU; regular tensor and pixel maths on the GPU.

CPUs and GPUs · Going deeper · 2 of 2

Systolic array — matrix data streams through a grid of MAC cells ×+ ×+ ×+ ×+ ×+ ×+ ×+ ×+ ×+ ×+ ×+ ×+ ×+ ×+ ×+ ×+ ×+ ×+ ×+ ×+ ×+ ×+ ×+ ×+ ×+ Matrix A rows → Matrix B columns ↓ → partial sums accumulate no instruction fetch · every cell does one MAC per cycle

A chip that never fetches an instruction

A systolic array is a grid of multiply-add cells that data flows through, one element per tick. Google’s TPU v4 has a 128 × 128 grid: 16,384 multiply-adds per cycle. It does matrix multiplication superbly and almost nothing else.

Summary

A computer is one trick repeated at six scales

one trick, repeated at six scalesthe number to rememberTransistora switch worked by voltage100 – 200 billion per chipGatea few switches that do logic4 transistors make a NANDAdder and registergates that calculate and remember64 flip-flops hold one numberCorefetch, decode, execute, write back3 billion ticks a secondCache pyramidkeeps the core fedRAM is 150 ticks awayMany cores, GPU, acceleratorssideways growth after 20058 – 192 cores, 10,000 GPU lanesbuilt on

Each layer hides the one below it. Next: orchestration, the software that shares this one machine among many programs.

Summary · Going deeper

Cache mapping: direct-mapped vs N-way set-associative vs fully-associative Direct-mapped 2-way set-assoc Fully associative one slot per address choose 1 of 2 slots any slot anywhere slot 0 slot 1 slot 2 slot 3 way 0 way 1 way 0 way 1 set 0 set 1 any · any · any · any any · any · any · any addr A → slot 1 addr B → slot 1 conflict: A evicts B addr A → set 0, way 0 addr B → set 0, way 1 both fit · no conflict addr A → free slot addr B → free slot no conflict misses cheap · 1 tag compare 2 tag compares · cheap N tag compares · expensive real L1 caches are 8-way · L3 is often 16-way · fully-associative is reserved for very small, very precious caches (TLB)

Where a cached line may live

A direct-mapped cache gives each address one slot: fast, but two hot addresses can evict each other forever. Real L1 caches are 8-way set-associative and L3 is often 16-way. The interfaces on this page are fixed by standards: the x86, Arm and RISC-V manuals, JEDEC for memory, PCI Express for the buses.

Lesson complete

You finished “Machines”

Answer the questions along the way to see your score here.

Open in a new tab