Electronics Guide

Memory Hierarchy

The memory hierarchy is a fundamental concept in computer architecture that organizes different types of storage based on their speed, capacity, and cost characteristics. At the top of the hierarchy sits the processor's registers, which offer the fastest access but extremely limited capacity. Moving down the hierarchy, each level typically provides greater capacity at lower cost, but with increased access latency.

Levels of the Memory Hierarchy

A typical modern memory hierarchy includes the following levels:

• Registers: The fastest storage, located within the processor core itself. Access time is typically less than one clock cycle, but capacity is limited to a few hundred bytes at most. Registers hold the data currently being operated upon.
• L1 Cache: First-level cache, usually split into separate instruction and data caches. Access time is typically 1-4 clock cycles with capacities ranging from 16KB to 128KB per core. Located on the processor die itself.
• L2 Cache: Second-level cache, often unified for instructions and data. Access time is typically 10-20 clock cycles with capacities from 256KB to several megabytes. May be private to each core or shared among cores.
• L3 Cache: Third-level cache, typically shared among all processor cores. Access time is 30-50 clock cycles with capacities from several megabytes to over 100MB in high-end processors.
• Main Memory (RAM): Dynamic RAM provides the primary working memory for the system. Access time is typically 50-100 nanoseconds (hundreds of clock cycles), with capacities ranging from gigabytes to terabytes.
• Secondary Storage: Solid-state drives and hard disk drives provide persistent storage. Access times range from microseconds (SSDs) to milliseconds (HDDs), with capacities in terabytes.

Principles of Locality

The memory hierarchy exploits two fundamental principles of program behavior:

Temporal locality refers to the tendency of programs to access the same memory locations repeatedly over short periods. When data is accessed, it is likely to be accessed again soon. This principle justifies keeping recently accessed data in fast cache memory.

Spatial locality refers to the tendency of programs to access memory locations that are near each other. When one memory location is accessed, nearby locations are likely to be accessed soon. This principle motivates fetching entire cache lines rather than individual bytes.

By exploiting these locality principles, a well-designed memory hierarchy can achieve an average memory access time close to that of the fastest level while providing the capacity of the largest level.

Cache Memory Organization

Cache memory serves as a high-speed buffer between the processor and main memory, storing copies of frequently accessed data and instructions. The organization of a cache determines how data is mapped from main memory addresses to cache locations, and significantly impacts cache performance.

Direct-Mapped Cache

In a direct-mapped cache, each memory block can only be stored in exactly one cache location, determined by the memory address. The cache location is typically computed as:

Cache Index = (Memory Address / Block Size) mod (Number of Cache Lines)

Direct-mapped caches are simple to implement and have fast lookup times since only one location needs to be checked. However, they suffer from conflict misses when multiple frequently accessed memory locations map to the same cache line, forcing repeated evictions even when other cache lines are empty.

Fully Associative Cache

A fully associative cache allows any memory block to be stored in any cache line. When searching for data, all cache lines must be checked simultaneously using parallel comparators. This organization eliminates conflict misses but requires expensive hardware for parallel tag comparison. Fully associative caches are typically used only for small, specialized caches such as translation lookaside buffers.

Set-Associative Cache

Set-associative caches represent a compromise between direct-mapped and fully associative designs. The cache is divided into sets, each containing multiple lines (ways). A memory block maps to a specific set but can be placed in any line within that set.

Common configurations include:

• 2-way set associative: Each set contains 2 lines, offering good conflict miss reduction with modest hardware cost
• 4-way set associative: Each set contains 4 lines, commonly used in L1 caches
• 8-way to 16-way set associative: Higher associativity used in L2 and L3 caches where the larger size justifies additional comparison hardware

Cache Replacement Policies

When a cache set is full and a new block must be loaded, a replacement policy determines which existing block to evict:

• Least Recently Used (LRU): Evicts the block that has not been accessed for the longest time. Provides good performance but requires tracking access history.
• Pseudo-LRU: Approximates LRU behavior with less hardware overhead, commonly used in practice.
• Random: Selects a victim block randomly. Simple to implement and performs surprisingly well in many workloads.
• First-In First-Out (FIFO): Evicts the oldest block regardless of access pattern. Simple but can perform poorly with certain access patterns.

Write Policies

Cache write policies determine how modifications to cached data are propagated to lower levels of the hierarchy:

Write-through: Every write to the cache is simultaneously written to main memory. This keeps memory consistent but generates significant memory traffic. Often combined with write buffers to reduce processor stalls.

Write-back: Writes modify only the cache, and modified (dirty) blocks are written to memory only when evicted. This reduces memory traffic but requires tracking which blocks have been modified and complicates cache coherence in multiprocessor systems.

Write allocation policies determine behavior on write misses:

• Write-allocate: On a write miss, the block is first loaded into cache, then modified. Works well with write-back caches.
• No-write-allocate: On a write miss, the write goes directly to memory without loading the block into cache. Often used with write-through caches.

Cache Coherence Protocols

In multiprocessor systems where each processor has its own cache, maintaining a consistent view of memory across all caches presents a significant challenge. Cache coherence protocols ensure that all processors observe a consistent ordering of memory operations and that modifications made by one processor are visible to others.

The Cache Coherence Problem

Consider a scenario where two processors each cache a copy of the same memory location. If one processor modifies its cached copy, the other processor's cache contains stale data. Without coherence mechanisms, this leads to incorrect program behavior when processors communicate through shared memory.

Snooping Protocols

Snooping protocols rely on all caches monitoring (snooping) a shared bus for memory transactions. When a cache observes a transaction relevant to a block it holds, it takes appropriate action to maintain coherence.

MSI Protocol: The basic snooping protocol where each cache line can be in one of three states:

• Modified (M): The cache has the only valid copy, which has been modified. The cache is responsible for writing the block back to memory.
• Shared (S): The cache has a valid, unmodified copy. Other caches may also have copies.
• Invalid (I): The cache line does not contain valid data.

MESI Protocol: Extends MSI by adding an Exclusive state:

• Exclusive (E): The cache has the only valid copy, which has not been modified. This allows silent transitions to Modified state without bus traffic, improving performance.

MOESI Protocol: Further extends MESI by adding an Owned state:

• Owned (O): The cache has a modified copy that may be shared with other caches. The owning cache is responsible for supplying data on requests and eventually writing back to memory.

Directory-Based Protocols

For systems with many processors, snooping becomes impractical as bus bandwidth becomes a bottleneck. Directory-based protocols maintain a centralized or distributed directory that tracks which caches hold copies of each memory block.

When a processor needs to read or write a block, it consults the directory to determine which other caches might have copies. This allows point-to-point communication between only the relevant caches, scaling better to large processor counts.

Memory Consistency Models

Beyond cache coherence, memory consistency models define the order in which memory operations appear to execute across processors:

• Sequential consistency: The strongest model, where operations appear to execute in a total order consistent with each processor's program order. Simple to understand but limits performance optimizations.
• Total store ordering (TSO): Allows reads to bypass earlier writes to different addresses. Used by x86 processors.
• Relaxed consistency models: Allow more reordering, requiring explicit memory barriers for synchronization but enabling greater performance.

Virtual Memory Systems

Virtual memory is a memory management technique that provides programs with the illusion of a large, contiguous address space while the actual physical memory may be smaller and fragmented. This abstraction simplifies programming, enables memory protection between processes, and allows efficient sharing of physical memory among multiple programs.

Address Translation

Virtual memory systems divide both virtual and physical address spaces into fixed-size units. The memory management hardware translates virtual addresses generated by programs into physical addresses used to access actual memory.

Paging divides memory into fixed-size pages (commonly 4KB, though larger page sizes like 2MB or 1GB are also used). Each virtual page maps to a physical page frame. Page tables store the mappings from virtual to physical page numbers.

Segmentation divides memory into variable-size segments based on logical program structure (code, data, stack). While less common in modern systems, segmentation can be combined with paging in some architectures.

Page Tables

Page tables are data structures that store virtual-to-physical address mappings. For a 64-bit address space with 4KB pages, a simple flat page table would be impractically large. Modern systems use hierarchical page tables:

Multi-level page tables divide the virtual address into multiple fields, each indexing into a separate table level. A 4-level hierarchy is common in 64-bit systems, with each level covering a portion of the address. This approach allocates page table memory only for address ranges actually in use.

Each page table entry typically contains:

• Physical page frame number
• Present/valid bit indicating if the page is in physical memory
• Read/write permission bits
• User/supervisor mode access bits
• Accessed and dirty bits for replacement and write-back decisions
• Cache control bits

Page Faults

When a program accesses a virtual address whose page is not currently in physical memory, a page fault occurs. The operating system's page fault handler must:

1. Determine if the access is valid (within allocated address space)
2. Find a free physical page frame, potentially evicting another page
3. Read the required page from secondary storage if necessary
4. Update the page table to reflect the new mapping
5. Restart the faulting instruction

Page Replacement Algorithms

When physical memory is full, the operating system must choose which page to evict. Common algorithms include:

• LRU (Least Recently Used): Evicts the page not accessed for the longest time. Optimal in theory but expensive to implement exactly.
• Clock (Second Chance): Approximates LRU using a circular list and reference bits. Pages get a second chance before eviction.
• Working Set: Maintains pages accessed within a recent time window, evicting pages outside the working set.

Memory Management Units

The Memory Management Unit (MMU) is a hardware component that handles address translation and memory protection. Located between the processor and the memory system, the MMU intercepts all memory accesses and translates virtual addresses to physical addresses.

MMU Functions

The MMU performs several critical functions:

• Address translation: Converts virtual addresses to physical addresses using page tables
• Memory protection: Enforces access permissions, preventing unauthorized reads, writes, or execution
• Cache control: Determines caching behavior for different memory regions
• TLB management: Maintains the translation lookaside buffer for fast translations

Protection Mechanisms

The MMU enforces memory protection at multiple levels:

Page-level protection assigns permissions to each page, controlling read, write, and execute access. The processor's privilege level (user vs. supervisor mode) determines which pages can be accessed.

Supervisor/user mode separation prevents user programs from accessing kernel memory or modifying page tables. Attempts to violate these protections trigger exceptions handled by the operating system.

Execute disable (NX/XD bit) marks pages as non-executable, preventing code injection attacks by ensuring data pages cannot be executed as code.

Translation Lookaside Buffers

The Translation Lookaside Buffer (TLB) is a specialized cache that stores recent virtual-to-physical address translations. Since every memory access requires address translation, and page table lookups require multiple memory accesses, the TLB is critical for system performance.

TLB Organization

TLBs are typically small, fully associative or highly set-associative caches. A typical system might have:

• L1 ITLB: Instruction TLB with 32-128 entries for code translations
• L1 DTLB: Data TLB with 32-64 entries for data translations
• L2 TLB: Unified second-level TLB with 512-2048 entries

Each TLB entry contains:

• Virtual page number (tag)
• Physical page frame number
• Permission and attribute bits
• Address Space Identifier (ASID) for multi-process support

TLB Misses

When a translation is not found in the TLB, a TLB miss occurs. The miss can be handled by:

Hardware page table walker: Dedicated hardware automatically traverses the page table hierarchy to find the translation. Common in x86 and ARM processors.

Software TLB miss handler: The processor traps to operating system code that performs the translation. Used in some MIPS and older architectures.

TLB Management

Operating systems must manage TLB contents carefully:

TLB flushing invalidates entries when page table mappings change. Global flushes invalidate all entries, while targeted flushes invalidate specific addresses.

Address Space Identifiers (ASIDs) tag TLB entries with process identifiers, allowing entries from multiple processes to coexist. This reduces TLB flushes on context switches.

Process Context Identifiers (PCIDs) in x86 processors serve a similar purpose, preserving TLB entries across context switches for recently-used processes.

Memory Interleaving

Memory interleaving is a technique that distributes consecutive memory addresses across multiple memory banks or channels, enabling parallel access and higher memory bandwidth.

Interleaving Schemes

Low-order interleaving uses the low-order address bits to select the memory bank. Consecutive addresses map to different banks, maximizing parallelism for sequential access patterns:

• Address 0 goes to Bank 0
• Address 1 goes to Bank 1
• Address 2 goes to Bank 2
• Address 3 goes to Bank 3
• Address 4 goes to Bank 0 (wraps around)

High-order interleaving uses high-order address bits for bank selection. Consecutive addresses stay in the same bank, grouping related data together. This can be useful for certain access patterns but provides less parallelism for sequential access.

Multi-Channel Memory

Modern systems use multiple memory channels to increase bandwidth:

• Dual-channel: Two independent memory channels double theoretical bandwidth
• Quad-channel: Four channels for high-performance desktop and server systems
• Six and eight-channel: Used in high-end servers and workstations

Memory controllers interleave accesses across channels at cache line granularity, typically 64 bytes, to maximize bandwidth utilization.

Bank Conflicts

Within each memory module, DRAM chips are organized into banks that can be accessed independently. However, accessing the same bank consecutively incurs additional latency. Memory controllers attempt to schedule accesses to minimize bank conflicts while maintaining access order constraints.

Error Correction Codes

Error Correction Codes (ECC) protect memory contents against corruption caused by electrical noise, cosmic rays, and other transient faults. In mission-critical systems, ECC memory is essential for reliable operation.

Types of Memory Errors

Hard errors are permanent failures in memory cells, typically caused by manufacturing defects or wear. These require replacing the faulty memory module.

Soft errors are transient bit flips caused by external factors like cosmic rays or alpha particles. These are temporary and can be corrected if detected.

Single Error Correction, Double Error Detection (SECDED)

The most common ECC scheme for computer memory is SECDED, which uses Hamming codes to:

• Detect and correct any single-bit error in a data word
• Detect (but not correct) any double-bit error

For 64-bit data words, SECDED requires 8 additional check bits, resulting in 72-bit wide memory modules. The check bits are computed when writing to memory and verified when reading.

Chipkill and Advanced ECC

Server systems often employ more sophisticated ECC schemes:

Chipkill (also called Advanced ECC or SDDC) can correct the failure of an entire memory chip within a module. This protects against chip failures, not just single-bit errors.

Memory mirroring maintains duplicate copies of data on separate memory modules. If one module fails, the mirror provides continued operation.

Memory sparing reserves spare memory that can replace failing DIMMs without system shutdown.

ECC in Cache Memory

Modern processors also protect cache memory with ECC or parity:

• L1 caches often use parity (single-error detection) since they can be refilled from L2
• L2 and L3 caches typically use full ECC to protect larger data stores

When a cache error is detected, the cache line is invalidated and refetched from the next level of the hierarchy or main memory.

Performance Considerations

Effective memory system design requires balancing multiple performance factors:

Key Performance Metrics

• Hit rate: The fraction of memory accesses satisfied by the cache. Even small improvements in hit rate can significantly impact performance.
• Miss penalty: The time required to fetch data from the next level of hierarchy on a cache miss.
• Average memory access time: Hit time + (Miss rate x Miss penalty)
• Memory bandwidth: The rate at which data can be transferred between memory and processor.
• Memory latency: The time from request to data delivery.

Optimization Techniques

Hardware and software techniques can improve memory system performance:

• Prefetching: Anticipating future memory accesses and fetching data before it is needed
• Cache-conscious algorithms: Structuring data access patterns to maximize cache utilization
• Memory allocation strategies: Placing related data together to exploit spatial locality
• NUMA awareness: In multi-socket systems, accessing local memory rather than remote memory

Summary

Memory architecture and management form a critical foundation of modern computing systems. The memory hierarchy exploits locality principles to provide the illusion of large, fast memory using a combination of expensive fast caches and economical slower storage. Cache organizations balance implementation complexity against miss reduction, while coherence protocols ensure correct behavior in multiprocessor systems.

Virtual memory systems provide process isolation, simplified programming models, and efficient memory sharing through hardware-software cooperation between MMUs and operating systems. Translation lookaside buffers cache address translations to make virtual memory practical. Memory interleaving and multi-channel architectures increase bandwidth, while error correction codes ensure data integrity.

Understanding these concepts is essential for system architects designing new hardware, software developers optimizing performance-critical code, and engineers working with any computing system where memory performance matters.

Related Topics