Memory on the x86-64

I/O Bridge

We can think of the I/O bridge as the system's King's Cross station — where all of the system's buses meet. The disk controller, graphics adapter, network adapter, and USB controller (a chip for managing devices like wired mice and keyboards) all have buses that connect to the I/O bridge. More specifically, these buses connect to the I/O bus, which feeds to the I/O bridge. From the I/O bridge are the two buses seen earlier, the system bus (leading to the CPU) and the memory bus (leading to main memory).

Each chip connected to the I/O bus has a port address. This a specific address in memory dedicated to the particular chip. For example, for some computer system 𝑆, the graphics adapter (for managing image output to a device like a monitor) might have dedicated regions in memory for the adapter.

Whenever we want to read or write to some device managed by the chip, the relevant instruction sent from the CPU will include the port address. When the I/O bridge receives this instruction, it routes the instruction to the relevant port address, where it is then received by the managing chip. That chip then sends the instruction to the connected device, which executes the instruction accordingly.

For example, say we wanted to read some piece of data 𝐷 from our hard disk. The CPU's recieves the instruction, outputting the relevant bits to include the managing chip's port address. In this case, that chip is the disk controller. The I/O bridge receives these bits and the port address, and sends the bits down to the disk controller. The disk controller receives the bits and reads the disk's sector containing 𝐷. Once it retrieves 𝐷, it performs a direct memory access (DMA) to transfer 𝐷 into main memory.

By using DMA, the disk controller doesn't have to bother the CPU with transferring the data to main memory. This allows the CPU to perform other computations while it waits for the data 𝐷 to get to main memory. Once 𝐷 is in memory, an interrupt bit is sent to the CPU, where it's received at a special pin called the interrupt pin. This alerts the CPU that the data is now in memory.

Caches

A cache is a memory device used to temporarily hold a small amount of data. Specifically, it's a staging area for a small part of a large piece of data. The idea: For each level ${L}$ in the memory hierarchy presented earlier, the memory device used in the level serves as a cache for the level directly below it (${L+1}$).

Caches are a direct application of locality. Say a program 𝑃 runs, and it needs 48 bytes of data now, and 12 bytes of data later. This totals 72 bytes of data; far more than the capacity of the fastest memory devices on the system. Caches are a way to get around this problem:

1. First, assume the 48 bytes and the 12 bytes exist at the same level in the memory hiearchy.
2. The 48 bytes are more pertinent than the 12 bytes in terms of need, so a copy of those 48 bytes go up the memory hierarchy.
3. At the next level, perhaps the first 24 bytes are more pertinent than the other 24 bytes. So, 24 bytes bytes are copied to the next memory device up the hierarchy, and 24 bytes remain at the level in cache.
4. At the next level, perhaps only 12 of the 24 bytes are more pertinent than the other. So, 12 bytes remains at the level in cache, and the other 12 bytes are copied.
5. The process continues until we're at the processor's word-size. For the x86-64, this is 64 bits — 8 bytes.

This achieves a key goal in memory systems: Creating a large pool of storage that costs as much as the cheap storage near the hierarchy's bottom, all while serving data to programs at the rate of the fastest storage near the top.

Importantly, the bytes don't necessarily move up the hiearchy in halves. They can move at either a fixed size or a variable size. For example, an HTML file from a webpage can be either 10 kilobytes or 2 megabytes (hopefully not). That webpage is served from a web server. When we visit that page, a copy of it is cached in the next level's memory device — disk memory.

Cache Hits and Misses

Given what we now know about caching, it follows that whenever we execute a program, there are two possible scenarios for the program's data:

1. The data is cached at the current level, or
2. the data is not stored at the current level

If it's scenario (1), then we have a cache hit. The system reads the data directly.

If it's scenario (2), we have a cache miss — the system must fetch the data from the cache at the level below, and place it in the current level. Because caches get smaller as we go up the hierarchy, the system will likely will have to overwrite data in cache. Which data is overwritten? It depends on the memory device's replacement policy. Generally, there are two kinds:

1. Random replacement policies are replacement rules where a random block in cache is selected for overwrite.
2. Lease recently used policies are replacement rules where blocks least recently used (i.e., last used further in time) are selected for overwrite.

Needless to say, we don't want cache misses. They result in additional instructions for fetching, copying, and replacement. That said, some cache misses are unavoidable.

There are three kinds of cache misses:

1. Cold misses. These are unavoidable misses. They occur because the cache starts empty.
2. Capacity misses. These misses occur when the working set's size exceeds the cache's size. For example, we might have a loop that iterates over an array of structs. If those structs are large tree structures, we'll more than likely hit capacity misses — they're far too large for the cache. Some of these misses are avoidable, others are not. Again, these are tradeoffs we have to deal with.
3. Conflict misses. These misses occur because the cache is large enough to hold the data, but the cache is designed to only copy data from a particular area 𝐴 of the memory device in the level below it. Thus, any data not stored in 𝐴 will result in a miss. This is restriction is generally found in the highest rungs of the memory hierarchy — the processor registers, L1 cache, and others close to the CPU.

Cache Organization

Like the diagrams we saw with main memory, caches are divided into blocks:

Each address in main memory maps to exactly one of the cache blocks. For example if our cache is only 4-bytes large, the following addresses in main memory might map as follows:

This is the simplest approach to implementing a cache — direct mapping. The contents of the frequently accessed main memory addresses are stored in their corresponding cache block. When we need that data, we check the cache. If it isn't there, we fetch it from main memory.

Problem: How do we determine which cache block goes to which memory address? Well, we can do so with the modulus operator. If the cache contains ${2^k}$ blocks, then the data at memory address ${i}$ goes to the cache block with the index:

This is one way to compute the mapping. We could also use the addreses least-significant bits. For example, addresses ending in 00 map to the cache block with with the index 00, addresses ending 01 map to the cache block with the index 01, and so on.

But what if we get an instruction to read the contents of a particular address? If each block in the register can map to multiple addresses, how do we know we're going to the right address? To solve this problem, we add tag bits:

Assuming the tag and block indices are properly mapped to the respective memory address, we can determine which address the cache line maps to by reading the tag and block index together:

With this basic understanding, let's add a bit more detail.

A cache consists of memory cells grouped into lines. The lines are then grouped into sets:

How many sets and lines there are varies by processor. Generally, however, cache can be measured in two dimensions:

1. The number of lines per set, given by the equation:

   $$E = 2^n$$

   where ${n \in \nat}$.

2. The number of sets, which is given by the equation:

   $$S = 2^s$$

   where ${s \in \nat.}$

The memory device's placement policy determines which of the sets a particular address goes, and which of the lines within that set the address is stored.

Within each cache line, there are three key components:

1. 𝐵 bytes, where ${B \in \nat.}$ These bytes are where the actual data are stored.
2. A set of tag bits that identify the block's memory address.
3. A valid bit — a single bit to indicate whether the line is valid.

The total cache size ${C}$ is given by the equation:

The values for ${s}$ and ${n}$ will depend on the memory device's manufacturer. Suppose the CPU receives an instruction to read the data at main memory address 𝐴.

Upon receipt, the CPU sends the bits comprising 𝐴 to cache memory. If the cache doesn't have the data inside address 𝐴, it will fetch the contents of 𝐴 from main memory, and store them in the cache. But if the cache does have a copy of 𝐴's contents, it will send 𝐴 back to the CPU.

The memory device can determine whether 𝐴's contents already exist somewhere in its lines because of how addresses are formatted.

Each block has the address format above: 𝑡 bits for the tag, 𝑠 bits for the set's index in the line, and 𝑏 bits for the block's offset (equal to the number of 𝐵 bytes the block can store). To determine if 𝐴 exists in the block, all the cache memory device has to do is:

1. Look at the the 𝐴 address's set index bits. This tells the cache which set the address 𝐴's mapped cell might exist in.
2. Go to the set.
3. Look at the tag bits in the 𝐴 address. This tells the cache which line within the set the address 𝐴 might be mapped to. If the tag bits don't yield the 𝐴 address, then we have a cache miss: the data to be retrieved from address 𝐴 in main memory, brought to the cache, the line's occupants are evicted, and data retrieved from 𝐴 becomes the new occupant. If the tag bits do match, then we go to the next step.
4. Use the 𝑏 bits to determine where in the 𝐵 bytes the data starts.

How do we know that the data inside those bytes is correct? Through the valid bit we mentioned earlier. If the line contains some garbage value, that bit will be set to 0. Otherwise, it's 1.

Contiguous over Connected

Given an equal choice between a connected data structure (e.g., a linked list) and a contiguous data structure (e.g., an array), use the contiguous data structure. Arrays are much more cache friendly than linked lists because of spatial locality — the data are all close together.

Exploit Order

When working with matrices or jagged arrays, always be cognizant of whether the language uses row- or column-major ordering. If the language uses row-major ordering (the vast majority of languages), increment the column index first, then increment the rows. If the language uses column-major ordering, increment the row index first, then increment the columns. This is a common point of neglect for those unaware of the language's indexing system.

For example, say we had a 2-dimensional matrix in some language:

int M = [
	[1, 2],
	[3, 4]
]

Now suppose we're asked to perform some operation on each element in the matrix:

for (int i = 0; i < 2; i++) {
	for (int j = 0; j < 2; j++) {
		M[i][j];
	}
}

This is cache friendly code. The cache unfriendly version is swapping the i and the j:

for (int i = 0; i < 2; i++) {
	for (int j = 0; j < 2; j++) {
		M[j][i];
	}
}

There are few reasons to write something like the above, but it does happen.

Pass-by-reference over Pass-by-value

When we pass by value, the callee gets a copy of the value, and then once the callee is done, that copy is destroyed. This can often be a needless use of memory, processing time, and cache resources.

Minimize Branches

The more branches we have, the more the system must read data from memory. And the more often the system must read data from memory, the more likely we are to encounter cache misses.

Sorted over Unsorted

If our data can be given some sort of order, we minimize the amount of unpredictable branches. The more unpredictable branches we have, the more likely we are to experience cache misses.

Alignment

Suppose we defined a struct as follows:

struct rec {
   int a[4];
   int i;
   struct rect *next;
}

This struct consumes:

bytes of memory. Wait. Why is that i consuming 8 bytes of memory? Shouldn't it be 4? The answer is because of alignment. The rule is as follows:

Rule. If a primitive data type requires 𝑘 bytes, then the address of an instance of that data type must be a multiple of 𝑘.

For example, suppose we defined a struct as:

struct S {
   char c;
   int i[2];
   double v;
} *p

Without alignment, we would get something that looks like:

Here, the char c causes the pointer indices to go off. With alignment, we get a different picture:

In the diagram above, the cells containing 𝑝 are called padding bytes. By inserting these bytes, we see that the bytes are allocated in such a way that the offsets from the struct's pointer p is a multiple of their primitive type. char is allocated 1 byte (offsetting from the pointer by 1), the ints within the array are allocated in multiples of 4 (offsetting from the pointer as a multiple of 4), and the double is allocated as a multiple of 8 (offsetting from the pointer as a multiple of 8).

Why go through this trouble? Because it's far more expensive — efficiency wise — to offset pointers with values that are not multiples of the primitive datatype's size. This is because memory is accessed in chunks of 4 bytes (for a 32-bit system) or 8 bytes (for a 64-bit system).

The general rule: For each primitive data type in the struct, the largest data type determines the largest alignment 𝑘. If the struct, without padding, ends on an address that is not a multiple of 𝑘, then the compiler will insert padding to ensure the struct ends on an address that is a multiple of 𝑘. Thus, in the diagram above, we see that the struct ends at p+24, which is a multiple of 8. This corresponds to ${𝑘 = 8,}$ the size of the largest primitive data type in the struct, a double.

Note that because of this rule, the way we arrange our declarations can result in more or less padding. In our example struct S, it just so happens that the arrangement of the declarations doesn't change much. We would still need 7 bytes of padding. For example, if we had instead made the declarations as:

struct S {
   double V;
   int i[2];
   char c;
} *p;

we still see 7 bytes of padding: