Fast memory and slow memory

Stacking the components fastest first is the memory hierarchy. Higher is faster and smaller; lower is slower and larger.

• Registers … the workbench inside the CPU. Fastest, but only tens of bytes
• Cache memory … right beside the CPU. A few megabytes
• Main memory … the memory as usually meant. A few gigabytes
• Auxiliary storage (SSD, magnetic disk) … a place that survives the power going off. A few terabytes

Speed differs by several orders of magnitude top to bottom. Comparing registers with auxiliary storage feels like the difference between paper on your desk and a trip to the warehouse.

Data basically passes between neighbours. The CPU does not read auxiliary storage directly; things are carried up from below, level by level.

Putting a small fast component on top still means fetching from below whatever does not fit. So what is the point? What makes it work is the property of locality.

The way a program reads data is not at all scattered. In practice there are two biases.

• Temporal locality … what was just used is likely to be used again soon
• Spatial locality … what sits next to what was used is likely to be used next

Picture a loop. The same instructions run over and over, and the elements of an array are walked through in order. That is, a very narrow range gets used intensively.

So keeping "just the small part used often" in the upper level lets almost all reads and writes finish up there. Being small yet effective is thanks to that bias.

Cache memory is a small fast memory inserted between the CPU and main memory. It does one job only: keep data read from main memory close by, and return it without going to main memory when the same place is read again.

Having it and being able to return it is a hit; not having it and going to main memory is a miss.

Remember what happens on a miss: the surroundings are read into the cache from main memory in whole blocks. Not one byte, because spatial locality makes the neighbours likely to be used too.

This swapping is done by the hardware on its own. The program does not direct it, and no interrupt occurs for software to do the carrying. That is a favourite exam target.

"A cache makes it faster" is too crude. You want a number for what the average comes to, and that is the effective access time.

The thinking is not hard. Every read or write has only two cases, a hit or a miss. And

• the time on a hit is the cache access time
• the time on a miss is the main memory access time

With a hit rate of h, a fraction h of the whole hits and the remaining 1 - h misses. Multiply each time by how often it happens and add, and you have the average. That is why it is a weighted average. There is no formula to memorise; just think "add each in proportion to how often it happens".

Put numbers in. With a cache at 10 nanoseconds, main memory at 60 nanoseconds and a hit rate of 0.9: 10 x 0.9 = 9 and 60 x 0.1 = 6, together 15 nanoseconds. Far nearer the 10 than the 60.

The exam more often asks it backwards, giving only the effective access time and having you produce the hit rate.

All you do is solve the same formula for h. With the same numbers, suppose the effective access time was 15 nanoseconds.

Start from 15 = 10h + 60(1 - h), open the brackets for 15 = 10h + 60 - 60h. Gather the h terms for 15 = 60 - 50h, rearrange for 50h = 45, and divide for h = 0.9.

When you have an answer, always check the direction. An effective 15 nanoseconds is near the cache 10, so the hit rate should be high. Getting 0.1 or 0.17 here is a sign that you multiplied the wrong things together.

So far this has been about reading. Writing brings one more worry, because changing only the cache leaves the contents of main memory stale.

There are two ways to go.

• Write through … change the cache and main memory at the same time. The contents always agree, but every write reaches main memory, so it is slow
• Write back … change only the cache for now and write back to main memory when that data is evicted. Fewer trips to main memory, so it is fast, but they disagree for a while

The aim of write back is clearly reducing the number of writes to main memory. It is not that writing back becomes unnecessary — it does write, properly, on eviction. Choices mixing that up come up often.

Main memory and cache actually use memories of different construction.

DRAM expresses one bit by whether a capacitor holds a charge. Being simple to build, a great many fit in and it is cheap. But the stored charge leaks away naturally, so without continual refresh (periodic rewriting) the contents vanish. Cheap and large, it is used for main memory.

SRAM holds one bit in a circuit called a flip-flop. It holds as long as power flows, so it needs no refresh and is fast. But one bit takes several circuits, so it is expensive and cannot be made large. Fast and small, it is used for cache memory.

Remember it as D needs refresh (dynamic) and S does not (static). Both are volatile and vanish when the power goes off.

Both DRAM and SRAM vanish when the power goes off. What you want kept goes in ROM (read-only memory), which is non-volatile.

The kinds divide on whether they can be rewritten.

• Mask ROM … the contents are burned in during manufacture and cannot be rewritten afterwards
• PROM … can be written once after shipping
• EPROM … erased with ultraviolet light and rewritten
• EEPROM … erased electrically and rewritten

The worth of mask ROM lies in that very inability to be rewritten. The contents cannot be tampered with after shipping, which suits it to holding the program embedded in a device.

Flash memory is a relative of EEPROM, erased electrically in blocks and rewritten. It is what is inside USB sticks and SSDs. It needs no refresh and no ultraviolet.

There are devices for speeding up main memory itself, and memory interleaving is one.

Main memory is divided into several independent groups called banks, with consecutive addresses scattered across different banks. Then reading a consecutive region can access several banks in parallel: while one bank is taking its time to answer, the read on the next can begin.

Learn it alongside similar-sounding mechanisms, sorted by what is being divided.

• Memory interleaving … divides main memory and reads in parallel
• Cache memory … inserts a small fast memory to bridge the difference
• DMA … exchanges directly without going through the CPU

All three speed things up, so they are set out side by side as choices. Where it says "divides main memory into several groups and accesses them in parallel", it is interleaving.

Look at the bottom of the hierarchy, auxiliary storage. A magnetic disk (hard disk) is a machine that spins platters and reads with a head, so reading takes time to physically move.

The access time is a sum of three.

• Seek time (positioning time) … moving the head to the target track
• Rotational latency … waiting for the target place to come round
• Transfer time … actually reading the data out

The crux of the arithmetic is the rotational latency. You may wait a whole revolution or none at all, so the average is half a revolution. At 6,000 revolutions a minute, one revolution is 60 / 6000 seconds = 10 milliseconds, so the average wait is 5 milliseconds.

The transfer time is amount of data / transfer rate. Reading 1,000 bytes at 10 megabytes a second takes 0.1 milliseconds.

An SSD is flash memory, with no spinning parts and hence no seek and no rotational latency. So it is fast, quiet and robust to knocks.

Finally, the sockets that connect devices. They split into two by how the signal lines are used.

• Serial … one line sending one bit at a time in order
• Parallel … many lines sending at once

Parallel looks faster at first glance, but more lines mean arrival times stop lining up, so it becomes unusable at high speed. Today interfaces are almost all serial. USB and Bluetooth are serial, and USB connects devices in a tree using hubs. USB 3.0 has a 5 gigabit per second transfer called SuperSpeed.

One more to remember is DMA. Normally the CPU mediates the exchange between a device and main memory, which ties the CPU up as a porter. DMA lets a device and main memory exchange data directly without going through the CPU, leaving the CPU free for other work meanwhile.