☰ Main menu

Foundations

Seven short sections, twenty-two pictures, no assumed background. Read these first and every chapter in the map becomes readable. Each animation shows one mechanism; the line under it says why it matters.

How a computer holds data

Bytes, addresses, and values

Memory is a long row of numbered bytes0816243240485664each box = 1 byte = 8 bits, holding a number 0-255address = the box number0, 8, 16 …value = what is insideraw bytesNothing knows what a byte means. The program decides: today a number, tomorrow a letter.Two bytes can only be understood together if you agree on the order (little vs big endian).

Every variable, string and array is bytes in numbered boxes. Addresses are the box numbers you hand to the CPU or GPU.

Why the cache line matters

The CPU never reads one byte — it reads a whole lineone 64-byte cache lineyou asked for 4 bytesThe memory system moves 64 bytes at a time. Neighbouring data comes for free; scattered data does not.This one fact explains most of the speed difference between two loops that do the same arithmetic.

Hardware fetches a fixed block around your address. Using the whole block is free speed; using one byte per fetch wastes the rest.

The latency ladder

Same clock, wildly different waitsregister / L11 cycleL2 cache~14 cyclesmain memory (RAM)~200 cyclesGPU HBM~400 cyclesNVMe SSD~100 000 cyclesnetwork round trip~1 000 000 cyclesEverything in performance work is an attempt to avoid the bottom two rows.

If you remember one scale, remember this one. Work on registers is free; waiting on the network is the whole problem.

How work is organised

CPU versus GPU

Few fat cores, or thousands of thin onesCPU core 0deep, clever, reordersCPU core 1deep, clever, reordersCPU core 2deep, clever, reordersCPU core 3deep, clever, reordersCPU: 8-64 coresGPU: thousands of small cores, all doing the same thing to different data

A CPU is built to finish one complicated task fast. A GPU is built to run the same simple task on thousands of data points at once.

Processes versus threads

A process owns memory; threads share itprocessits own memoryaddress space, filesthread 0thread 1thread 2second processseparate memory,cannot see the first one's dataThreads see the same variables, so they must agree on who writes what. That is what locks and atomics are for.Processes communicate through the kernel: pipes, sockets, shared memory you set up on purpose.

Separate memory is safe but slow to share. Shared memory is fast to share and easy to corrupt.

What a warp is

One instruction, 32 threads, different data32 threads = 1 warpthey execute the same lineeach with its own dataif (x[i] > 0) … → half the warp waits when the answer differsbx badDivergence is the cost: when threads in a warp take different branches, the other half idles.

The GPU issues work to groups of 32 threads. They run in step, which is fast until their paths differ.

Grid, block, thread

A kernel launch is a shape you choosegridall the blocksblock (CTA)256 threadswarp32 threadsthread 0 of block 0 works on element 0 — that is the mapping you wrotebxGrid too small: the GPU idles. Grid too large: overhead. Grid shaped wrong: memory jumps around.

You describe work as a three-level shape. The hardware turns that description into warps on SMs.

Blocking threads versus async tasks

Waiting for a slow device, two waysThreads: one thread per waitthread 0blockedthread 1blockedthread 2blockedthread 3blockedAsync: one thread, many waits, nothing blockstask 0 polls, returns Pending, parks; the loop polls task 1, task 2, task 3 …

A blocked thread holds a stack and does nothing. An async task gives the thread back while it waits for the device.

The call stack

Every call adds a frame and returns through itmainparsecheckreportthe stack grows downand unwinds in reverseA slow call chain is why an error's traceback reads like a path through your program.

Each call pushes a frame with its locals; the return pops it. Deep recursion runs out of frames.

How a program becomes instructions

From source to something runnable

What a compiler actually doesyour sourceparsechecklowerbinaryhumans read thisstructure, names, typesthe CPU runs thisnumbers, addresses, jumpsEvery compiler in this map is a variation of this shape: understand, simplify, then choose instructions for a target.

A compiler reads text, builds a structure, checks it, simplifies it, and finally picks machine instructions.

Stack and heap

Two places to keep valuesstack — automaticfast, small, freed at scope endx = 7p →frame of fheap — requestedbigger, slower, freed when told[1, 2, 3, 4][9, 8]In Rust the stack value that owns heap data is dropped at scope end, and the heap is freed with it.

Small values live on the stack with the function. Big or variable-size values live on the heap behind a pointer.

Pointers and references

A pointer is just a number that means 'over there'p0x7ffc20the value42follow the addressa reference is the same idea with a promise: it always points at a live value of the right typebxUnsafe code lets you hold a number and hope. Safe code makes the compiler check the promise for you.

Both say where a value lives. A reference carries a guarantee the compiler enforces; a raw pointer does not.

How threads share data safely

What a lock does

A lock is a door with one keythread Aholds the keythe dataone writer at a timethread Bwaitsacquire → read, write, read → release. Everyone else blocks until the key comes back.Two rules follow: hold it for a short time, and never take two locks in different orders.A lock held too long turns a parallel program back into a serial one.

One writer, everyone else waits. Simple, correct, and the usual source of both deadlocks and slowdowns.

Why atomics exist

Read, change, write is three steps — that is the racethread A: read 5thread B: read 5writes 6writes 6Expected 7. Got 6. The change counts as one indivisible step only if the hardware is told to make it one.atomic_add(&x, 1) does exactly that, and memory ordering says when other threads may see the new value.

Two threads doing read-modify-write on one variable lose an update. Atomics make the whole step indivisible.

How machines talk

Client and server

One request, one response, over a networkclientasksserveranswersrequestresponsein between: a name lookup, a TCP connection, TLS, then bytes both waysbxEvery distributed problem starts with this round trip being slower and less reliable than a function call.

Two programs on different machines talk in messages. Nothing is shared, so anything can be late, lost, or duplicated.

Where a network call lives

Layers you name when you debug a connectionapplicationgRPC, HTTPtransportTCP — ordered bytes, or UDP — datagramsnetworkIP — addresses and routinglinkEthernet, InfiniBandEach layer adds a header. A stall at the bottom looks like a slow application at the top.

You send a message; four layers wrap it. Knowing which layer failed decides whether you fix code or fix the network.

How machines agree

Replication, and the problem it creates

Copies of the data on more than one machineprimarytakes writescopy 1copy 2copy 3More copies = more durability and more read capacity, but the copies must be kept in step.That single requirement is where consensus, quorums and anti-entropy all come from.If a client reads a stale copy, it sees history that never happened in that order.

Copying data is easy. Keeping copies agreeing while machines fail is the hard part.

What consensus means

Agreement: everyone picks the same value, oncenode 0proposesnode 1proposesnode 2proposesvalue Xvalue Xvalue XThe hard case is not agreement — it is agreement when messages are lost and the leader dies mid-decision.Safety means two nodes never decide differently. Liveness means a decision eventually happens.

A group decides one value, and all of them agree on it, even when some crash or the network loses messages.

The append-only log

An append-only log: the simplest way to agree#1#2#3#4#5#6#7#8entries are appended, never edited, and each has an indexreplay = rebuild the statethe log is the truthnew replica = copy the logthen follow itDatabases, queues and consensus protocols all store their history this way, because the order is the meaning.

A list you only add to. Given the same log, every machine builds the same state.

Quorums

Majority: 2 of 3, or 3 of 5node 0node 1node 2node 3node 4a write is accepted once a majority stores it — 3 of 5 herebx okTwo majorities always overlap on at least one node, and that overlap is what makes the rule safe.

Any two majorities share a member. That single fact lets a system survive a minority of failures without losing writes.

The maths that decides speed

Shapes in one matrix multiply

A tensor is just numbers with a shapeAM x KxBK x N=CM x NC[i][j] = sum over k of A[i][k] * B[k][j]K is the shared dimension: every output element reads K values from each input. Bigger K = more reuse per byte.The shapes are the first thing to check when a model fails: a wrong K gives a wrong answer with no error.

Three letters carry the whole data flow. Most ML systems bugs are a shape mismatch, and most speed comes from reusing K.

Arithmetic intensity

How much work per byte you movearithmetic2*M*N*K FLOPstrafficbytes read and written/intensity = FLOPs / byte → what the roofline plots on the x axisbxLow intensity means the memory system is the limit. High intensity means the arithmetic units are the limit.

One number tells you what a kernel is waiting on: the ratio of maths done to bytes moved.

Every diagram here was drawn for this site. None of it is from the books.