Memory hierarchy, cache and virtual memory notes — Unit 4

Ideally, programmers want memory that is infinitely large, infinitely fast, and completely free. In reality, memory technology forces a trade-off: Fast memory is expensive (and small), cheap memory is slow (and large).

To create the illusion of a fast and large memory, computer architects arrange different memory technologies in a Hierarchy.

⇒1.1 The Pyramid

• 1. CPU Registers: Fastest, smallest, most expensive. (Inside the CPU).
• 2. Cache Memory (SRAM): Very fast, small capacity. Buffers the CPU from main memory.
• 3. Main Memory (DRAM): Moderate speed, large capacity (GBs).
• 4. Magnetic Disk / SSD: Very slow, massive capacity (TBs). Non-volatile.
• 5. Magnetic Tape: Archival storage. Slowest, highest capacity.

As you go down the pyramid, cost per bit decreases, capacity increases, and access time increases.

Why does the memory hierarchy work? Why can a small Cache speed up a massive hard drive? Because programs do not access memory randomly. They exhibit Locality of Reference.

⇒2.1 Spatial Locality

If a memory location is accessed, memory locations physically near it are likely to be accessed soon.
Reason: Sequential instruction execution, array processing.
Hardware implementation: When the CPU requests a byte, the memory system fetches an entire block (e.g., 64 bytes) into the cache.

⇒2.2 Temporal Locality

If a memory location is accessed, it is likely to be accessed again in the near future.
Reason: Loop counters, frequently used variables.
Hardware implementation: Recently accessed data is kept in the Cache, displacing older data.

The Cache is a small, high-speed SRAM memory placed between the CPU and Main Memory (DRAM). It operates at near-CPU speeds.

⇒3.1 Hit and Miss

When the CPU needs to read a word:

• 1. It checks the Cache first.
• 2. Cache Hit: The word is found in the cache. It is read immediately. Fast.
• 3. Cache Miss: The word is not in the cache. The CPU must halt. A block of data containing the word is read from Main Memory, placed into the Cache, and then given to the CPU. Slow.

⇒3.2 Performance Metrics

Hit Ratio ($H$): $\frac{\text{Number of Hits}}{\text{Total Accesses}}$.
A good cache achieves a hit ratio of >95%.
Average Access Time ($T_a$): $T_a = H \times T_{cache} + (1-H) \times T_{main\_memory}$.

Because the Cache is much smaller than Main Memory, many Main Memory blocks will have to map to the same Cache block over time. We need a rigorous mathematical rule to determine exactly where a Main Memory block is allowed to be placed in the Cache.

There are three mapping techniques:

• Direct Mapping
• Associative Mapping
• Set-Associative Mapping

The CPU generates a Main Memory Address. To search the cache, this address is split into fields (Tag, Line/Block, Word).

The simplest technique. Each Main Memory block can map to exactly one specific line in the cache.

Formula: `Cache Line = (Main Memory Block Number) MOD (Number of Cache Lines)`

⇒5.1 Address Format

The CPU address is divided into three fields: `TAG | LINE | WORD`.

• Word: Identifies the exact byte within the block.
• Line: The hardware uses this field to index directly into the Cache. (If the line field is 0110, it looks ONLY at cache line 0110).
• Tag: Because multiple memory blocks map to the same line, the Tag acts as a nametag. The cache compares the Tag from the CPU address with the Tag stored in the cache line. If they match, it's a Hit.

⇒5.2 Pros and Cons

• Pros: Very fast search (only one tag comparison needed). Cheap hardware.
• Cons: Conflict Misses. If a program repeatedly accesses two variables that happen to map to the exact same cache line, they will constantly evict each other, even if the rest of the cache is completely empty. (Thrashing).

Solves the conflict problem of Direct Mapping. A Main Memory block can be placed in any available line in the cache.

⇒6.1 Address Format

The CPU address is divided into two fields: `TAG | WORD`. (There is no Line field because there is no restricted placement).

⇒6.2 Searching the Cache

When the CPU requests an address, the cache must compare the requested Tag against the Tag of every single line in the cache simultaneously. This requires the cache to be built using Content Addressable Memory (CAM).

⇒6.3 Pros and Cons

• Pros: Maximum flexibility. No conflict misses. A block is only evicted if the entire cache is full.
• Cons: Hardware is extremely complex and expensive. Comparing 1000 tags simultaneously requires massive circuitry, which slows down the cache hit time and consumes high power.

The industry-standard compromise between Direct and Associative. It offers the speed of Direct mapping with the flexibility of Associative mapping.

⇒7.1 The Mechanism

The cache is divided into "Sets", where each set contains $K$ lines (e.g., 2-way, 4-way, 8-way set associative).

A Main Memory block maps to a specific Set, but can be placed in any of the $K$ lines within that set.

Formula: `Cache Set = (Main Memory Block Number) MOD (Number of Sets)`

⇒7.2 Address Format

Divided into: `TAG | SET | WORD`.

The hardware uses the Set field to jump to the correct set. Then, it only performs $K$ simultaneous tag comparisons. For a 4-way cache, it only checks 4 tags instead of the whole cache.

When the CPU executes a `STORE` instruction, it writes data to the Cache. But now the Cache and Main Memory contain different values for the same address. How is this inconsistency resolved?

⇒8.1 Write-Through

Every time the CPU writes to the Cache, the data is immediately sent down the bus to update Main Memory as well.

• Pros: Main memory is always perfectly up to date. Easy to implement.
• Cons: Extremely slow. Every write operation incurs the penalty of main memory access speed, bottlenecking the CPU.

⇒8.2 Write-Back

The CPU writes ONLY to the Cache. A special bit (the Dirty Bit) is set to 1 for that cache line, indicating it has been modified.

Main Memory is updated only when that dirty cache block is about to be evicted to make room for new data.

• Pros: Extremely fast. CPU doesn't wait for main memory.
• Cons: Complex hardware logic. If power is lost, modified data in the cache is lost forever before reaching main memory.

In Associative and Set-Associative mapping, when a new block must be loaded into a full set, which existing block is chosen for eviction? The hardware must decide.

⇒9.1 LRU (Least Recently Used)

Evicts the block that has gone unaccessed for the longest time. Based on temporal locality, it's the least likely to be needed again.

Implementation: Requires counters or hardware age bits updated on every single cache hit. The most effective, but complex to implement in silicon.

⇒9.2 FIFO (First In, First Out)

Evicts the block that was loaded into the cache first, regardless of how often it's being used. Easy to implement (just a circular pointer), but poor performance because it might evict heavily used variables.

⇒9.3 LFU (Least Frequently Used)

Evicts the block with the fewest number of hits. Seldom used because a newly loaded block has 0 hits and gets unfairly evicted immediately.

What happens if you try to run a 10 GB video game on a computer with only 4 GB of RAM? Without Virtual Memory, the game crashes instantly.

Virtual Memory is a technique that gives the programmer the illusion that they have a massive, continuous main memory, even if physical RAM is tiny. It uses the Hard Drive as an extension of RAM.

⇒10.1 The Core Concept

The Operating System breaks the program into chunks. It keeps the currently active chunks in physical RAM, and leaves the dormant chunks on the Hard Drive.

When the CPU requests a chunk that is on the Hard Drive, a Page Fault occurs. The OS pauses the program, moves a dormant chunk from RAM to the Hard Drive, brings the requested chunk from the Hard Drive into RAM, and resumes the program.

To implement Virtual Memory efficiently, memory is divided into fixed-size blocks.

• Pages: The chunks of the Virtual (Logical) address space generated by the CPU. (e.g., 4 KB chunks).
• Frames: The identically sized chunks of physical RAM. (e.g., 4 KB chunks).

Any Page can be placed into any empty Frame in physical RAM.

⇒11.1 Address Translation

The CPU generates a Virtual Address (Page Number + Offset).
Physical RAM requires a Physical Address (Frame Number + Offset).
The offset remains the same. The hardware must translate the Page Number into a Frame Number.

Address translation is performed using a Page Table stored in main memory. It acts as an index/map.

The Page Table has an entry for every virtual page.

• Valid Bit: 1 if the page is currently in RAM, 0 if it is on the Hard Drive.
• Frame Number: If the Valid Bit is 1, this tells the hardware exactly which frame in RAM holds the page.

⇒12.1 The Speed Penalty

To read a variable, the CPU must first access the Page Table in memory to translate the address, and then access memory again to read the actual variable. Paging halves memory performance!

To fix this, we introduce the TLB.

The TLB is a special, ultra-fast associative Cache placed inside the CPU's Memory Management Unit (MMU).

⇒13.1 Purpose

The TLB caches recent Page Table translations. Instead of holding data, it holds pairs of `[Page Number : Frame Number]`.

⇒13.2 Resolution Flow

• CPU generates Virtual Address.
• Hardware checks the TLB.
• TLB Hit: Translation found instantly. CPU accesses physical RAM. (1 memory access).
• TLB Miss: Translation not found. Hardware must walk the Page Table in memory, find the translation, update the TLB, and then access RAM. (2 memory accesses).

Because of spatial locality, TLB hit rates exceed 99%, entirely solving the paging speed penalty.

Unit 4 covers the crucial illusions that make modern computing possible: Caching (making slow memory seem fast) and Virtual Memory (making small memory seem large).

⇒14.1 University Exam Checklist

• Explain Spatial and Temporal Locality.
• Given a main memory of 64KB, cache of 2KB, and block size of 16 bytes, calculate the number of bits in the Tag, Line, and Word fields for Direct Mapping.
• Contrast Direct Mapping and Associative Mapping. Why is Set-Associative considered the best of both?
• Explain the difference between Write-Through and Write-Back policies. What is the role of the Dirty bit?
• Define Virtual Memory, Page Fault, and Thrashing.
• What is the function of the Translation Lookaside Buffer (TLB)? Draw a block diagram showing address translation with a TLB.

⇒14.2 Operating Systems crossover

• Virtual memory is a hardware-OS co-design. The hardware (MMU) does the fast translation, but the OS handles the slow Page Faults (fetching data from disk).