yeolyi.comSeongyeol's CS

Locality

So far we’ve said that reading and writing memory also finishes in a single clock. In reality it doesn’t. While fetching one value from memory, the CPU just waits for hundreds of clocks. Memory is slow because it’s large. Making it fast makes it small, and making it large makes it slow.

Can we use a large, slow memory and still wait less?

Desk, drawer, storage room

Think about studying. You keep the textbook you read often open on the desk, a workbook you read now and then in a drawer, and books you won’t use this semester in a storage room. Keeping every book in the storage room costs time each time you fetch one, and the desk is too small for all of them. So you keep what you use more often closer.

A computer can likewise keep just the frequently used data close to the CPU. But do programs really have data they use more often?

Locality

Let’s look at a program that adds up eight numbers lined up in memory, one by one, keeping the sum in the first slot. Each time it reads a number, it also reads the first slot and writes back the sum.

The demo below shades a slot darker the more recently it was read, fading as time passes.

0
3
1
4
1
5
9
2
6

Reads cluster in two ways.

Instructions work the same way. The body of a loop reads the same slots over and over, and as long as there’s no jump, the PC points to the very next slot.

Wrapping up

Programs don’t read all of memory evenly; they read clustered in narrow regions. So if we move just those regions into a small, fast store like the desk, most reads won’t have to go all the way to memory. In the next post, let’s build this store.

Challenge

When fetching values from memory, we fetch a block of k slots (slots 0 to k−1, k to 2k−1, …) instead of one slot at a time, and keep only the most recently fetched block. Addresses inside the block we're holding aren't fetched again. A program reads slots 0 to 15 skipping 4 at a time, in four rounds (0, 4, 8, 12, 1, 5, 9, 13, …, 15). With k being one of 1, 2, 4, 8, or 16, what is the smallest k that makes the number of fetches fewer than 16? Answer with a number.

Loading…