Large and Fast: Exploiting Memory Hierarchy
5.1 Introduction
Memory Hierarchy: An organization of storage levels that provides the illusion of memory that is both large and fast.
Principle of Locality: Programs tend to access a relatively small portion of their address space during a particular period.
Temporal Locality: Recently accessed information is likely to be accessed again soon.
Spatial Locality: Information near a recently accessed address is likely to be accessed soon.
Block: The minimum unit of information transferred between adjacent levels of a memory hierarchy.
Hit: An access in which the requested block is found in the upper level.
Miss: An access in which the requested block is absent from the upper level and must be obtained from a lower level.
Hit Rate: The fraction of memory accesses found in a particular level.
Miss Rate: The fraction of memory accesses not found in a particular level.
Hit Time: The time required to access an upper level and determine whether the access is a hit.
Miss Penalty: The additional time required to obtain a block from a lower level and deliver it to the requester.
5.2 Memory Technologies
1) Semiconductor Memory
Static Random Access Memory (SRAM): Fast volatile memory that stores each bit using a stable circuit and normally does not require refresh.
Dynamic Random Access Memory (DRAM): Dense volatile memory that stores bits as electrical charge and requires periodic refresh.
Synchronous DRAM (SDRAM): DRAM whose operations are coordinated with a clock.
Double Data Rate SDRAM (DDR SDRAM): SDRAM that transfers data on both edges of the clock signal.
Memory Bank: An independently accessible subdivision of a memory device that enables overlapping memory operations.
Row Buffer: Storage holding the currently activated DRAM row and enabling faster accesses to other locations in that row.
2) Nonvolatile Storage
Flash Memory: Nonvolatile semiconductor memory that can be electrically erased and rewritten.
Solid-State Drive (SSD): A storage device that uses flash memory and a controller to provide persistent block storage.
Magnetic Disk: A nonvolatile storage device that records data magnetically on rotating platters.
Seek Time: The time required to move a disk head to the required track.
Rotational Latency: The time spent waiting for the desired disk sector to rotate beneath the read/write head.
Transfer Time: The time required to transfer data after the storage location has been reached.
5.3 The Basics of Caches
1) Cache Organization
Cache: A small, fast memory that stores copies of blocks from a larger, slower memory.
Cache Line: A cache entry containing one memory block and its associated metadata.
Direct-Mapped Cache: A cache in which each memory block can be placed in exactly one cache location.
Tag: The address field stored in a cache line to identify which memory block occupies that line.
Index: The address field used to select a cache set or line.
Block Offset: The low-order address field used to select a byte or word within a cache block.
Valid Bit: A metadata bit indicating whether a cache line contains a meaningful block.
For a byte-addressed cache:
2) Cache Access
Cache Hit: An access whose valid indexed line has a matching tag.
Cache Miss: An access requiring a block to be fetched from the next memory level.
Block Replacement: Removing an existing cache block to make room for a requested block.
Instruction Cache: A cache that stores instructions.
Data Cache: A cache that stores program data.
Split Cache: Separate instruction and data caches at the same hierarchy level.
3) Cache Writes
Write-Through: A write policy that updates both the cache and the next lower memory level on every write hit.
Write Buffer: A queue that allows the processor to continue while pending writes are sent to a lower memory level.
Write-Back: A write policy that updates only the cache on a hit and writes the block to the lower level when it is replaced.
Dirty Bit: A metadata bit indicating that a write-back cache block has been modified since it was loaded.
Write Allocate: A write-miss policy that first loads the missed block into the cache and then performs the write.
No-Write Allocate: A write-miss policy that writes directly to a lower level without loading the block into the cache.
5.4 Measuring and Improving Cache Performance
1) Cache Performance
Average Memory Access Time (AMAT): The average time required for a memory access, including misses.
Memory Stall Cycles: Processor cycles spent waiting for memory hierarchy operations.
Misses Per Instruction: The average number of cache misses caused by each executed instruction.
2) Cache Associativity
Fully Associative Cache: A cache in which a memory block can be placed in any cache line.
Set-Associative Cache: A cache divided into sets in which a memory block can occupy any line within one indexed set.
Way: One possible cache-line position within a set.
Least Recently Used (LRU): A replacement policy that chooses the block not accessed for the longest time.
Random Replacement: A policy that selects a block randomly from the target set.
3) Sources of Cache Misses
Compulsory Miss: The first access to a block that has never been loaded into the cache.
Capacity Miss: A miss caused because the cache cannot contain the program's active blocks simultaneously.
Conflict Miss: A miss caused when multiple blocks compete for the same set despite unused space elsewhere in the cache.
4) Cache Optimizations
Larger Block Size: An optimization that can reduce compulsory misses by exploiting spatial locality but may increase miss penalty and cache pollution.
Higher Associativity: An optimization that reduces conflict misses at the cost of more comparison hardware and potentially longer hit time.
Multilevel Cache: A hierarchy containing multiple cache levels with different size and latency goals.
First-Level Cache (L1): A small cache optimized for minimum hit time.
Lower-Level Cache: A larger cache designed primarily to reduce the miss penalty seen by an upper cache.
For two cache levels:
Prefetching: Fetching a block before the processor explicitly requests it.
Victim Cache: A small fully associative cache that stores recently evicted blocks to reduce conflict misses.
5.5 Dependable Memory Hierarchy
1) Dependability
Dependability: The ability of a system to deliver service that can justifiably be trusted.
Fault: The underlying cause of an incorrect hardware or software state.
Error: An incorrect internal system state produced by a fault.
Failure: A deviation of delivered service from its specified behavior.
Mean Time to Failure (MTTF): The average operating time before a system or component fails.
Mean Time to Repair (MTTR): The average time required to restore service after a failure.
Mean Time Between Failures (MTBF): The average time from one failure to the next.
Availability: The fraction of time a system is operational.
2) Error Detection and Correction
Parity Bit: A redundant bit used to detect an odd number of bit errors in a protected group.
Error-Correcting Code (ECC): Redundant information that allows memory errors to be detected and, in some cases, corrected.
Single-Error Correcting, Double-Error Detecting (SEC-DED): An ECC capability that corrects any single-bit error and detects any double-bit error in a protected word.
Soft Error: A transient error that changes stored data without permanently damaging hardware.
Hard Error: A persistent error caused by a physical hardware defect.
5.6 Virtual Machines
Virtual Machine (VM): An isolated software environment that behaves like a complete computer.
Virtual Machine Monitor (VMM): Software that creates and manages virtual machines and controls their access to physical hardware.
Hypervisor: Another name for a virtual machine monitor.
Host: The physical system and management environment providing resources to virtual machines.
Guest Operating System: An operating system running inside a virtual machine.
System Virtual Machine: A virtual machine that provides a complete hardware abstraction capable of running an operating system.
Privileged Instruction: An instruction that may execute only in a privileged processor mode.
Trap-and-Emulate: A virtualization technique in which privileged guest operations trap to the VMM and are emulated safely.
Paravirtualization: A technique that modifies a guest operating system to interact efficiently with a virtualization interface.
5.7 Virtual Memory
1) Address Translation
Virtual Memory: A technique that gives each process a protected virtual address space and uses secondary storage as a backing store for memory.
Virtual Address: An address generated by a running program.
Physical Address: The actual address used to access main memory.
Page: A fixed-size block of virtual memory.
Page Frame: A fixed-size block of physical memory that can hold one virtual page.
Address Translation: Mapping a virtual address to a physical address.
2) Page Tables
Page Table: A per-process data structure that records mappings from virtual pages to physical page frames.
Page Table Entry (PTE): An entry containing a physical page number and metadata such as valid, protection, reference, and dirty bits.
Page Table Register: A processor register that identifies the current process's page table.
Multilevel Page Table: A hierarchical page-table structure that allocates lower-level tables only for used portions of the virtual address space.
Inverted Page Table: A table with one entry per physical page frame rather than one entry per virtual page.
3) Translation Lookaside Buffer
Translation Lookaside Buffer (TLB): A small associative cache containing recently used virtual-to-physical address translations.
TLB Hit: An address translation found in the TLB.
TLB Miss: An address translation not found in the TLB and therefore obtained from the page table.
Address Space Identifier (ASID): A process identifier stored with a TLB entry so translations from multiple address spaces can coexist.
4) Page Faults
Page Fault: An exception that occurs when a referenced virtual page is not currently in physical memory or violates access permissions.
Demand Paging: Loading a virtual page into physical memory only when it is first referenced.
Page Replacement: Selecting a physical page to evict when no free page frame is available.
Reference Bit: A bit indicating that a page has been accessed recently.
Dirty Bit: A bit indicating that a page has been modified and must be written back before replacement.
Least Recently Used Approximation: A practical replacement method that uses reference information to estimate which page has not been used recently.
5) Protection
Memory Protection: Restrictions controlling whether a process may read, write, or execute a virtual page.
Process Isolation: Prevention of one process from directly accessing another process's private memory.
Shared Page: A physical page intentionally mapped into more than one virtual address space.
5.8 A Common Framework for Memory Hierarchy
Every memory-hierarchy level must answer four questions:
1) Block Placement
Block Placement: The rule determining where a block may be stored in the upper level.
| Organization | Possible locations |
|---|---|
| Direct mapped | One location |
| Set associative | Any line in one set |
| Fully associative | Any line |
2) Block Identification
Block Identification: The mechanism used to determine whether the requested block is present, normally using tag and valid metadata.
3) Block Replacement
Block Replacement: The policy used to choose a block for eviction, such as LRU or random replacement.
4) Write Strategy
Write Strategy: The combination of write-through or write-back with write-allocate or no-write-allocate behavior.
5.9 Using a Finite-State Machine to Control a Simple Cache
Finite-State Machine (FSM): A control model consisting of states, transitions, inputs, and outputs.
Cache Controller: Hardware that sequences cache lookup, memory access, refill, eviction, and processor response operations.
Idle State: The state in which the cache waits for a processor memory request.
Tag Check: The state or operation that compares the requested tag and determines whether the access is a hit.
Write-Back State: A state that writes a dirty victim block to lower memory before replacement.
Refill State: A state that obtains a missed block from lower memory and installs it in the cache.
Cache Ready Signal: A signal indicating that a requested memory operation has completed.
5.10 Parallelism and Memory Hierarchies: Cache Coherence
Cache Coherence: The property that processors observe a consistent value for each shared memory location despite private caches.
Coherence Problem: A condition in which multiple cached copies of one memory block contain inconsistent values.
Coherence Invariant: A rule ensuring that a read returns the most recent write to that location according to the coherence order.
Snooping Protocol: A coherence protocol in which caches monitor transactions on a shared communication medium.
Directory Protocol: A coherence protocol that records which caches hold each block and sends targeted coherence messages.
Write Invalidate Protocol: A protocol that invalidates other cached copies before granting a processor permission to write.
Write Update Protocol: A protocol that broadcasts a new value to other cached copies when a write occurs.
False Sharing: Coherence traffic caused when processors modify different variables located in the same cache block.
5.11 Parallelism and Memory Hierarchy: RAID
Redundant Array of Inexpensive Disks (RAID): A storage organization that combines multiple drives to improve performance, capacity, or dependability.
Striping: Distributing consecutive data blocks across multiple drives for parallel access.
Mirroring: Storing duplicate copies of data on separate drives.
Parity: Redundant information that can reconstruct lost data after a drive failure.
| RAID level | Organization | Main goal |
|---|---|---|
| RAID 0 | Block striping without redundancy | Performance and capacity |
| RAID 1 | Mirroring | Dependability and fast reads |
| RAID 5 | Distributed block-level parity | Capacity-efficient single-drive fault tolerance |
| RAID 6 | Distributed dual parity | Tolerance of two drive failures |
RAID Rebuild: Reconstruction of lost data onto a replacement drive using redundant information.
5.12 Implementing Cache Controllers
Blocking Cache: A cache that handles only one miss at a time and stalls later requests until the miss completes.
Nonblocking Cache: A cache that permits hits and potentially additional misses while an earlier miss is outstanding.
Miss Status Holding Register (MSHR): A structure that records information about an outstanding cache miss.
Critical-Word First: A refill policy that returns the requested word before the rest of the cache block.
Early Restart: Resuming processor execution as soon as the requested word arrives, before the full block refill completes.
5.13 Real Stuff: Modern Memory Hierarchies
Inclusive Cache: A cache organization in which blocks in an upper cache are also guaranteed to exist in a lower cache.
Exclusive Cache: A cache organization designed to minimize duplication of blocks across cache levels.
Unified Cache: A cache that stores both instructions and data.
Private Cache: A cache dedicated to one processor core.
Shared Cache: A cache accessible by multiple processor cores.
Cache Hierarchy Trade-off: L1 caches emphasize low latency, while lower-level caches emphasize capacity and reduced main-memory traffic.
5.14 Going Faster: Cache Blocking and Matrix Multiply
Cache Blocking (Tiling): Reorganizing computation to operate on small data blocks that fit in cache and can be reused before eviction.
Working Set: The collection of memory blocks actively used during a period of execution.
Data Reuse: Repeated use of values already present in cache or registers.
Blocked Matrix Multiplication: Matrix multiplication divided into submatrices so that each submatrix is reused from cache.
Loop Interchange: Reordering nested loops to improve the memory-access pattern and locality.
Memory Traffic Reduction: Decreasing transfers between cache and main memory by increasing temporal locality.
5.15 Fallacies and Pitfalls
Memory-Ignorance Pitfall: Algorithms and compiler transformations that ignore locality can perform poorly even when their arithmetic work is unchanged.
Byte-Addressing Pitfall: Cache mapping calculations must distinguish byte addresses, block addresses, and word addresses.
Associativity Pitfall: Insufficient associativity in a shared cache can produce severe conflict misses as cores or threads compete for the same sets.
AMAT Pitfall: AMAT alone may not predict performance for an out-of-order processor that overlaps multiple memory accesses and cache misses.
Specified-Reliability Fallacy: Storage failure rates observed in real systems may differ significantly from manufacturer specifications.
Virtualization Pitfall: An ISA that does not trap all sensitive operations requires additional hardware support, binary translation, or paravirtualization.
5.16 Concluding Concepts
Locality Foundation: Temporal and spatial locality make cache and virtual-memory hierarchies effective.
Memory Performance: Hit time, miss rate, and miss penalty jointly determine memory-access performance.
Cache Design Trade-off: Capacity, block size, associativity, write policy, latency, bandwidth, and energy must be balanced together.
Virtual-Memory Role: Virtual memory provides address translation, protection, process isolation, controlled sharing, and demand paging.
Reliability Role: Parity, ECC, redundancy, and repair mechanisms improve memory and storage dependability.
Software-Hardware Cooperation: Cache-aware algorithms, prefetching, virtual-memory management, and coherence protocols coordinate software and hardware behavior.