Memory Hierarchy

1Learning Outcomes¶

• Define key components of the memory hierarchy: processor, caches, memory, disk.

2Memory Wall¶

While hardware performance has continued to improve, there is a persistent and increasing gap between the improvements in processor hardware and memory/device interconnects (the Processor-DRAM gap, or simply memory gap).^[1] The “memory wall”^[2] places a significant limit on performance for many modern workloads, especially in AI.^[3]

By designing a memory hierarchy, we can leverage smaller amounts of high-speed hardware without ballooning the cost of our architecture nor sacrificing data and storage capacity.

3The Memory Hierarchy, Revisited¶

Earlier, we assumed there were only two layers of our memory hierarchy: registers (on the CPU) and memory (DRAM is close, but on a separate chip). We now continue our earlier discussion of memory hierarchy.

The mismatch between processor and memory speeds (the “careful tango” described earlier leads us to add a new level: The memory cache, or cache for short. Caches are usually on the same chip as the CPU and fit into the memory hierarchy as follows:

• Size: Smaller than memory, but certainly larger than the 32 registers on our RISC-V processor.

• Speed: Use hardware that is much faster than DRAM (used for main memory), but slower than registers.

• Cost: Use hardware that is more expensive than DRAM.

There are additional levels lower than main memory: disk is a huge one (literally).

Data moves differently between different levels of the memory hierarchy:

• Registers and memory: Managed by the compiler. Loads and stores move data in and out.

• Cache and memory: Managed by cache controller hardware. We will describe the high-level operation, but leave the implementation to a later course.

• Memory and disk: Managed by the operating system and special hardware via virtual memory, a concept that we will discuss later.^[4] Additionally managed by the programer/user via files and file streams.

To summarize, we aim for the illusion of a “very large and fast memory”:

• We make memory fast by using a hierarchy, where higher levels use faster, smaller, and more expensive hardware and are located physically closer to the processor.

• We make memory large by leveraging the principle of locality by “caching” the “right” data in higher levels, and delegating lower levels to store more data. The lowest level contains all available data (though nowadays we don’t go to magnetic disk and stop at SSD).

If useful, we revisit Jim Gray’s analogy of data access time on registers, on the cache, in main memory, and on disk.

3.1Multi-Level Caches¶

You may have noticed that the memory hierarchy diagram contains multiple caches labeled Level 1, Level 2, and Level 3. A computer can have multiple caches, where each cache is a copy of data from lower in the memory hierarchy.

Consider Apple’s A14 bionic chip, which we introduced earlier:

The L2 cache is located on the integrated circuit, often adjacent to the CPU. The System Level Cache labeled in the diagram is likely a Level 3 cache, shared across multiple CPU cores.^[5]

1. L1 cache (L1$^[6]): Usually directly embedded on the CPU, hence why it is not labeled in the above diagram.

   • Size: Tens or hundreds of KiB.

   • Hit Time (see cache terminology): Complete in one clock cycle or less.

   • Miss rate (see cache terminology): 1-5%

2. L2 cache (L2$): Located on the integrated circuit, often adjacent to the CPU.

   • Size: Tens or hundreds of MiB.

   • Hit Time: Few clock cycles

   • Miss rate: 10-20%

3.2Demo¶

To find out the sizes of different components of the memory hierarchy on a Linux-based machine, we can use df and sysctl. The following commands were run on a Mac OS X machine.

To determine disk size, use df. The default display is in blocks (e.g., lines); use the -h option for IEC prefixes (base-two), and the -H option for base-10 prefixes.

$ df -h
Filesystem        Size    Used   Avail Capacity iused ifree %iused  Mounted on
/dev/disk3s1s1   460Gi    17Gi    38Gi    31%    427k  395M    0%   /
devfs            215Ki   215Ki     0Bi   100%     744     0  100%   /dev
...
$ df -H 
Filesystem        Size    Used   Avail Capacity iused ifree %iused  Mounted on
/dev/disk3s1s1    494G     18G     40G    31%    427k  395M    0%   /
devfs             220k    220k      0B   100%     744     0  100%   /dev
...

To determine cache size and memory size, use sysctl. Because this command lists all attributes of the system kernel, we pipe the output through grep to get what we want. The default unit is bytes for memory and caches.

$ sysctl -a | grep hw.memsize
hw.memsize: 25769803776
hw.memsize_usable: 25143640064
$ sysctl -a | grep "hw.l.*size"
hw.l1icachesize: 131072
hw.l1dcachesize: 65536
hw.l2cachesize: 4194304

4Storage¶

5Visuals: Memory Hierarchy¶

Written version coming soon, but not too soon.

For now, know that DRAM (the technology used for )