How does a computer get a job done? Processor, memory and cache

Type 7 + 3 + 5 + 2 into a calculator and the answer appears in the blink of an eye. The processor in your phone can do that sum in about a billionth of a second. So if it is that fast, why do computers sometimes seem to “think”? Why does a program take seconds to open? Most of the answer lies not in calculating but in waiting for data. In this post we open up a computer as if it were a workshop: a worker doing the job, a few small drawers in front of it, a small but fast shelf beside it, a large cabinet behind, and an archive store furthest away.

What does a processor do? Fetch, decode, execute

Every program on a computer is a long list of very simple instructions that the processor understands: “fetch this number from memory”, “add two numbers”, “write the result to memory”, “if this condition is true, jump to that line of the list”. The processor works through the list one by one, always with the same three-step cycle:

1. Fetch: the next instruction is taken from memory. A small counter called the program counter keeps track of which instruction comes next.
2. Decode: the processor works out what the instruction asks for: an addition, a read from memory, a jump? Which registers will it use?
3. Execute: the work is done. For an addition the arithmetic logic unit runs; for a memory read the data is requested and the processor waits for it to arrive.

Then the program counter points to the next instruction and the cycle starts again. This idea became clear in the 1940s, when the first electronic computers were being designed: instructions sit in memory just like data, and the processor reads them in order. The phone in your pocket and huge servers alike still work on this same basic plan.

The clock signal: the processor’s metronome

The billions of transistors inside a processor keep in step with a clock signal. The clock is an electrical signal that “ticks” a fixed number of times a second; each tick counts as one cycle. The clock of a processor marked “3 GHz” ticks 3 billion times a second, so one cycle lasts about a third of a nanosecond. In that time even light travels only about 10 centimetres.

In a simple processor each phase of an instruction takes one or a few cycles. Real processors are cleverer: while executing one instruction, they decode the next and fetch the one after that. This arrangement, like an assembly line in a factory, is called a pipeline, and it lets one or even several instructions finish every cycle on average. But they all share one limit: nothing can be done with data before it arrives.

Registers: the drawers in front of the worker

Right inside the processor there are a very small number of very fast memory slots called registers. The adding machine takes its numbers straight from registers and writes the result to a register too. In today’s common processors the general-purpose registers a program can use directly number in the tens, and each holds a 64-bit number. So all the registers together add up to a few hundred bytes. Using a register involves no waiting: the data is where the processor can use it within a cycle.

The problem is that a program’s data can run to gigabytes. Even one photo is millions of numbers. Everything that does not fit in the registers lives further away, in what we call memory, and distance means time.

Why does memory come in layers?

The ideal memory would be huge, very fast, cheap, and would not forget anything when the power goes. No such memory exists. Fast kinds of memory (the SRAM cells inside the processor) are expensive per bit and take up a lot of space; large, cheap kinds (DRAM in RAM, flash memory in an SSD) are slow. The solution engineers found is to stack several kinds in layers: the layer closest to the processor is small and fast, and the layers further away get bigger but slower.

The table below shows rough orders of magnitude for today’s desktop and laptop computers. Exact values vary from processor to processor; what matters here is that the gaps between layers are measured in multiples, not percentages. We have also turned the times into cycles of a 3 GHz processor.

It helps to bring these numbers to a human scale. If taking a number from the cache took one second, taking it from RAM would take almost a minute, reading from an SSD would take a few hours or even a day, and reading from a spinning hard disk would stretch into months. The processor does its best not to sit idle during these waits, but it does not always manage.

A program in the workshop

In the drawing below we have built these layers as a workshop. The bench on the right is the processor: a punched tape carries the program, the reader reads the next instruction (fetch), the lamps show what kind of instruction it is (decode), and the adding machine and the worker arm do the work (execute). The metronome is the clock signal. In front of the arm are two register slots called R1 and R2. The shelf with slots right next to the arm is the cache, the cabinet of drawers behind it is RAM, and the rack furthest away is the disk. Data that is not in the cache is fetched by the wagon on the rail.

The program adds up a list of numbers over three passes. Each pass resets R1, brings the numbers into R2 one by one and adds them to R1, just as a game reprocesses the same data every frame. First step through with the default values using the Step button: you will see the fetch, decode and execute phases of each instruction separately. Then try these:

• Watch how in the first pass the arm comes away from the cache empty-handed for each number, while from the second pass on it takes the numbers straight from the shelf. Look at the clock tick counter: the first pass eats almost all the time.
• Cut the cache to 2 slots and finish the program. How many hits were there? We explain why below.
• Switch the access pattern to Scattered: see how many pages are read from disk when the numbers are spread through memory.
• Type your own numbers (for example 3, 7, 12) or change the delays. For instance, raise the disk delay to that of a hard disk, tens of millions of cycles.

The wagon’s travel time in the drawing is not to scale; at real scale the trip to the disk would take tens of thousands of times longer than a read from the cache. The counters, though, count the cycles correctly from the model.

Cache hits and misses

When the processor needs some data, it looks in the cache first. If the data is there, that is called a hit, and it arrives in a few cycles. If not, it is a miss: the data is fetched from the next layer, in the worst case from RAM or the disk, and a copy is put into the cache. If the cache is full, one of its contents is evicted to make room. One of the most common rules is to evict the one that has gone unused for the longest time (LRU, for “least recently used”).

We can estimate the average access time roughly like this:

average time = hit time + miss rate × miss penalty

With the default numbers in the drawing, the hit time is 4 cycles and the miss penalty (going to RAM) is 200 cycles. If 90% of reads are hits, the average is 4 + 0.1 × 200 = 24 cycles. If the hit rate drops to 50%, the average rises to 4 + 0.5 × 200 = 104 cycles: more than four times slower. In real processors well-behaved programs usually have very high cache hit rates, which is exactly why a small change in that rate makes such a big difference.

Something interesting happens in the drawing when you cut the cache to 2 slots: the program reading the list 7, 3, 5, 2 in order gets no hits at all. The two-slot cache evicts the oldest number each time a new one arrives, and the number it evicts is exactly the one needed two steps later. When the working data does not fit, a cache may not help “a little less”: it may not help at all. That is why programmers try to process data in pieces that fit in the cache.

Locality: why does a small shelf help so much?

A cache is hundreds or even thousands of times smaller than RAM. It can still serve most reads because of a regularity in how programs behave. This is called locality, and it comes in two kinds:

• Temporal locality: data that was just used will be used again soon. A loop counter, a player’s position in a game and a frequently called function all behave like this.
• Spatial locality: if one piece of data was used, the data right next to it in memory will be used soon too. Reading a list from start to finish is an example.

To take advantage of spatial locality, real caches fetch data not one item at a time but in blocks called cache lines (64 bytes in most of today’s processors). The model in the drawing is simpler: each slot holds one number. But you can see the same idea between RAM and the disk: the disk moves data into RAM in pages of 4 numbers. When the numbers sit side by side, a single page read brings them all; when they are scattered, the disk has to be visited separately for each page.

RAM and disk: volatile and permanent

Registers, cache and RAM are volatile memory: their contents disappear when the power goes. The disk (an SSD or a hard disk) is permanent. That is why programs and files are stored on disk and loaded into RAM when they are run. It is also one reason why an application opens slowly the first time and faster the second time: the operating system keeps the files it has just read in RAM for a while.

When a page a program needs is not in RAM, this is called a page fault, and the operating system reads the page from disk. Meanwhile the processor waits on behalf of that program, but it usually switches to another program rather than sitting idle. When there is not enough RAM, the computer slows down visibly because pages keep going back and forth to the disk.

Real processors are cleverer still

The processor in the drawing is deliberately simple: it handles instructions one at a time and stops while it waits for data. Real processors use many techniques to hide the waiting:

• Multi-level caches: most processors have three levels, L1, L2 and L3; L1 is usually split in two, one for instructions and one for data.
• Prefetching: if the processor notices that a list is being read in order, it starts fetching the next data before it is asked for.
• Out-of-order execution: while one instruction waits for data, later instructions that do not depend on it are moved ahead and executed.
• Multiple cores: several processor cores run different jobs at the same time; each core has its own L1 and usually its own L2 cache.

All of these techniques were developed against the same fact: over the past decades processor speed has grown much faster than memory speed. Engineers call this gap the “memory wall”.

Summary

• A processor works through a program as small instructions, with the fetch, decode, execute cycle; its steps are set by the clock signal.
• Registers are a few fast slots inside the processor; the rest of the data lives in memories that are further away, layer after layer.
• The speed gaps between layers are measured in multiples: the cache takes a few cycles, RAM hundreds, the disk tens of thousands or more.
• Data found in the cache is a hit, data not found is a miss; the average access time is very sensitive to the miss rate.
• A cache works despite being small thanks to the locality of programs. If the working data does not fit, the benefit can vanish entirely.