Memory Hierarchy Notes

Principle of Locality

• Programs tend to access a small proportion of their address space at any given time.
• Temporal locality: Recently accessed items are likely to be accessed again soon.
  • Examples: Instructions in a loop, induction variables.
• Spatial locality: Items near recently accessed items are likely to be accessed soon.
  • Examples: Sequential instruction access, array data.

Memory Hierarchy

• Store everything on disk.
• Copy recently accessed (and nearby) items from disk to smaller DRAM (main memory).
• Copy more recently accessed (and nearby) items from DRAM to smaller SRAM (cache memory) attached to the CPU.

Memory Hierarchy Levels

• Block (aka line): Unit of copying between levels in the memory hierarchy.
  • May consist of multiple words.
• Hit: Access is satisfied by the upper level.
  • Hit ratio: $hits / accesses$
• Miss: Accessed data is absent and the block is copied from the lower level.
  • Miss penalty: Time taken to copy the block from lower level to upper level.
  • Miss ratio: $misses / accesses = 1 - hit ratio$
• After a miss, the accessed data is supplied from the upper level.

Memory Technology

• Static RAM (SRAM):
  • Access time: $0.5ns – 2.5ns$
  • Cost: 2000 – $5000 per GB
• Dynamic RAM (DRAM):
  • Access time: $50ns – 70ns$
  • Cost: 20 – $75 per GB
• Magnetic disk:
  • Access time: $5ms – 20ms$
  • Cost: 0.20 – $2 per GB
• Ideal memory: Access time of SRAM with the capacity and cost/GB of disk.

DRAM Technology

• Data is stored as a charge in a capacitor.
• A single transistor is used to access the charge.
• The charge must be periodically refreshed (read contents and write back).
• Refresh is performed on a DRAM "row".

Advanced DRAM Organization

• Bits in a DRAM are organized as a rectangular array.
• DRAM accesses an entire row.
• Burst mode: Successive words from a row are supplied with reduced latency.
• Double data rate (DDR) DRAM: Transfer on rising and falling clock edges.
• Quad data rate (QDR) DRAM: Separate DDR inputs and outputs.

DRAM Generations

The capacity and cost per GB of DRAM has improved significantly over the years. For example, in 1980, 64Kbit costed $1500000 per GB but by 2007, 1Gbit costed only $50 per GB.

DRAM Performance Factors

• Row buffer: Allows several words to be read and refreshed in parallel.
• Synchronous DRAM: Allows for consecutive accesses in bursts without needing to send each address, improving bandwidth.
• DRAM banking: Allows simultaneous access to multiple DRAMs, improving bandwidth.

Increasing Memory Bandwidth

• Example:
  • 4-word wide memory: Miss penalty = $1 + 15 + 1 = 17$ bus cycles, Bandwidth = $16 bytes / 17 cycles = 0.94 B/cycle$
  • 4-bank interleaved memory: Miss penalty = $1 + 15 + 4 × 1 = 20$ bus cycles, Bandwidth = $16 bytes / 20 cycles = 0.8 B/cycle$

Flash Storage

• Nonvolatile semiconductor storage.
• $100\times$ – $1000\times$ faster than disk.
• Smaller, lower power, more robust.
• More expensive per GB than disk but cheaper than DRAM.

Flash Types

• NOR flash: Bit cell like a NOR gate.
  • Random read/write access.
  • Used for instruction memory in embedded systems.
• NAND flash: Bit cell like a NAND gate.
  • Denser (bits/area), but block-at-a-time access.
  • Cheaper per GB.
  • Used for USB keys, media storage.
• Flash bits wear out after 1000’s of accesses, making them unsuitable for direct RAM or disk replacement.
• Wear leveling: Remap data to less used blocks.

Disk Storage

• Nonvolatile, rotating magnetic storage.

Disk Sectors and Access

• Each sector records:
  • Sector ID.
  • Data (512 bytes, 4096 bytes proposed).
  • Error correcting code (ECC) to hide defects and recording errors.
  • Synchronization fields and gaps.
• Access to a sector involves:
  • Queuing delay if other accesses are pending.
  • Seek: move the heads.
  • Rotational latency.
  • Data transfer.
  • Controller overhead.

Disk Access Example

• Given:
  • 512B sector, 15,000rpm, 4ms average seek time, 100MB/s transfer rate, 0.2ms controller overhead, idle disk.
• Average read time:
  • $4ms seek time + (1/2) / (15000/60) = 2ms$ rotational latency + $512 / 100MB/s = 0.005ms$ transfer time + 0.2ms controller delay = 6.2ms
• If actual average seek time is 1ms, average read time = 3.2ms.

Disk Performance Issues

• Manufacturers quote average seek time based on all possible seeks.
• Locality and OS scheduling lead to smaller actual average seek times.
• Smart disk controller allocate physical sectors on disk and present logical sector interface to host (SCSI, ATA, SATA).
• Disk drives include caches to prefetch sectors in anticipation of access and avoid seek and rotational delay.

Cache Memory

• Cache memory: The level of the memory hierarchy closest to the CPU.
• Relevant questions:
  • How do we know if the data is present?
  • Where do we look?

Direct Mapped Cache

• Location is determined by address.
• Direct mapped: only one choice.
  • (Block address) modulo (#Blocks in cache)
  • #Blocks is a power of 2, so use low-order address bits.

Tags and Valid Bits

• To know which block is stored in a cache location:
  • Store block address as well as the data (only need the high-order bits, called the tag).
• If there is no data in a location:
  • Valid bit: 1 = present, 0 = not present (initially 0).

Address Subdivision

• Address (showing bit positions) breakdown into Tag, Index, and Byte offset for cache addressing.

Larger Block Size

• Example: 64 blocks, 16 bytes/block. To what block number does address 1200 map to?
  • Block address = $\lfloor 1200/16 \rfloor = 75$
  • Block number = $75 modulo 64 = 11$
• Address breakdown into Tag, Index, Offset.

Block Size Considerations

• Larger blocks:
  • Should reduce miss rate due to spatial locality.
  • But in a fixed-sized cache, larger blocks means fewer blocks, leading to more competition and increased miss rate.
  • Also leads to pollution and larger miss penalty.
  • Early restart and critical-word-first can help.

Cache Misses

• On cache hit, the CPU proceeds normally.
• On cache miss:
  • Stall the CPU pipeline.
  • Fetch block from the next level of hierarchy.
    • Instruction cache miss: Restart instruction fetch.
    • Data cache miss: Complete data access.

Write-Through

• On a data-write hit, update the block in both the cache and memory to maintain consistency.
• Makes writes take longer. For example, if base CPI = 1, 10% of instructions are stores, and write to memory takes 100 cycles, the effective CPI = $1 + 0.1 \times 100 = 11$
• Solution: Write buffer to hold data waiting to be written to memory, allowing the CPU to continue immediately (only stalls if the write buffer is already full).

Write-Back

• On a data-write hit, just update the block in the cache.
• Track whether each block is dirty.
• When a dirty block is replaced, write it back to memory.
• Can use a write buffer to allow replacing block to be read first.

Write Allocation

• What should happen on a write miss?
• Alternatives for write-through:
  • Allocate on miss: Fetch the block.
  • Write around: Don’t fetch the block (since programs often write a whole block before reading it, e.g., initialization).
• For write-back, usually fetch the block.

Example: Intrinsity FastMATH

• Embedded MIPS processor with 12-stage pipeline and instruction and data access on each cycle.
• Split cache: separate I-cache and D-cache.
  • Each 16KB: 256 blocks × 16 words/block.
  • D-cache: write-through or write-back.
• SPEC2000 miss rates:
  • I-cache: 0.4%.
  • D-cache: 11.4%.
  • Weighted average: 3.2%.

Main Memory Supporting Caches

• Use DRAMs for main memory.
  • Fixed width (e.g., 1 word).
• Connected by a fixed-width clocked bus.
  • Bus clock is typically slower than CPU clock.
• Example cache block read (4-word block, 1-word-wide DRAM):
  • 1 bus cycle for address transfer.
  • 15 bus cycles per DRAM access.
  • 1 bus cycle per data transfer.
  • Miss penalty = $1 + 4 \times 15 + 4 \times 1 = 65$ bus cycles.
  • Bandwidth = $16 bytes / 65 cycles = 0.25 B/cycle$

Measuring Cache Performance

• Components of CPU time:
  • Program execution cycles (includes cache hit time).
  • Memory stall cycles (mainly from cache misses).

Cache Performance Example

• Given:
  • I-cache miss rate = 2%.
  • D-cache miss rate = 4%.
  • Miss penalty = 100 cycles.
  • Base CPI (ideal cache) = 2.
  • Load & stores are 36% of instructions.
• Miss cycles per instruction:
  • I-cache: $0.02 \times 100 = 2$
  • D-cache: $0.36 \times 0.04 \times 100 = 1.44$
• Actual CPI = $2 + 2 + 1.44 = 5.44$
• Ideal CPU is $5.44/2 = 2.72$ times faster.

Average Access Time

• Hit time is important for performance. Average memory access time (AMAT):
  • $AMAT = Hit time + Miss rate \times Miss penalty$
• Example:
  • CPU with 1ns clock, hit time = 1 cycle, miss penalty = 20 cycles, I-cache miss rate = 5%.
  • $AMAT = 1 + 0.05 \times 20 = 2ns$
  • 2 cycles per instruction.

Performance Summary

• When CPU performance increased:
  • Miss penalty becomes more significant.
  • Decreasing base CPI leads to a greater proportion of time spent on memory stalls.
  • Increasing clock rate means memory stalls account for more CPU cycles.
• Need to consider/ include cache behavior when evaluating system performance.

Associative Caches

• Fully associative: A given block can go in any cache entry.
  • Requires all entries to be searched at once, comparator per entry (expensive).
• n-way set associative:
  • Each set contains n entries.
  • Block number determines which set: (Block number) modulo (#Sets in cache)
  • Search all entries in a given set at once, n comparators (less expensive).

Spectrum of Associativity

• Explanation using Direct mapped, Set associative, and Fully associative caches.

Associativity Example

• Compare 4-block caches: Direct mapped, 2-way set associative, fully associative.
• Block access sequence: 0, 8, 0, 6, 8.

How Much Associativity

• Increased associativity decreases miss rate, but with diminishing returns.
• Simulation of a system with 64KB D-cache, 16-word blocks, SPEC2000:
  • 1-way: 10.3%
  • 2-way: 8.6%
  • 4-way: 8.3%
  • 8-way: 8.1%

Replacement Policy

• Direct mapped: no choice.
• Set associative:
  • Prefer non-valid entry, if there is one.
  • Otherwise, choose among entries in the set:
    • Least-recently used (LRU): Choose the one unused for the longest time (simple for 2-way, manageable for 4-way, too hard beyond that).
    • Random: Gives approximately the same performance as LRU for high associativity.

Multilevel Caches

• Primary cache (L1) attached to CPU (small, but fast).
• Level-2 cache (L2) services misses from primary cache (larger, slower, but still faster than main memory).
• Main memory services L-2 cache misses.
• Some high-end systems include L-3 cache.

Multilevel Cache Example

• Given:
  • CPU base CPI = 1, clock rate = 4GHz.
  • Miss rate/instruction = 2%.
  • Main memory access time = 100ns.
• With just primary cache:
  • Miss penalty = $100ns/0.25ns = 400$ cycles.
  • Effective CPI = $1 + 0.02 \times 400 = 9$
• Now add L-2 cache:
  • Access time = 5ns.
  • Global miss rate to main memory = 0.5%.
  • Primary miss with L-2 hit: Penalty = $5ns/0.25ns = 20$ cycles.
  • Primary miss with L-2 miss: Extra penalty = 400 cycles.
  • CPI = $1 + 0.02 \times 20 + 0.005 \times 400 = 3.4$
  • Performance ratio = 9/3.4 = 2.6.

Multilevel Cache Considerations

• Primary cache:
  • Focus on minimal hit time.
  • Is usually smaller than a single cache, with a smaller block size than L-2.
• L-2 cache:
  • Focus on low miss rate to avoid main memory access.
  • Hit time has less overall impact.

Interactions with Advanced CPUs

• Out-of-order CPUs can execute instructions during cache miss.
  • Pending store stays in load/store unit.
  • Dependent instructions wait in reservation stations.
  • Independent instructions continue.
• Effect of miss depends on program data flow.
• Much harder to analyze, use system simulation.

Interactions with Software

• Misses depend on memory access patterns.
• Algorithm behavior.
• Compiler optimization for memory access.

Software Optimization via Blocking

• Goal: maximize accesses to data before it is replaced.

Dependability

• Fault: failure of a component.
  • May or may not lead to system failure.
• Illustrates the relationship between service accomplishment, service interruption and failure.

Dependability Measures

• Reliability: Mean time to failure (MTTF).
• Service interruption: Mean time to repair (MTTR).
• Mean time between failures: $MTBF = MTTF + MTTR$
• Availability = $MTTF / (MTTF + MTTR)$
• Improving Availability:
  • Increase MTTF: fault avoidance, fault tolerance, fault forecasting.
  • Reduce MTTR: improved tools and processes for diagnosis and repair.

The Hamming SEC Code

• Hamming distance: Number of bits that are different between two bit patterns.
• Minimum distance = 2 provides single bit error detection (e.g., parity code).
• Minimum distance = 3 provides single error correction, 2 bit error detection.

Encoding SEC

• Hamming code calculation:
  • Number bits from 1 on the left.
  • All bit positions that are a power of 2 are parity bits.
  • Each parity bit checks certain data bits.

Decoding SEC

• Value of parity bits indicates which bits are in error.
• Use numbering from encoding procedure.
• Example:
  • Parity bits = 0000 indicates no error.
  • Parity bits = 1010 indicates bit 10 was flipped.

SEC/DEC Code

• Add an additional parity bit for the whole word ($p_n$) to make Hamming distance = 4.
• Decoding:
  • H even, $p_n$ even, no error.
  • H odd, $p_n$ odd, correctable single bit error.
  • H even, $p<em>n$ odd, error in $p</em>n$ bit.
  • H odd, $p_n$ even, double error occurred.
• Note: ECC DRAM uses SEC/DEC with 8 bits protecting each 64 bits.

Virtual Machines

• Host computer emulates guest operating system and machine resources.
  • Improved isolation of multiple guests to avoid security and reliability problems.
  • Aids sharing of resources.
• Virtualization has some performance impact, but is feasible with modern high-performance computers.
• Examples:
  • IBM VM/370 (1970s technology!).
  • VMWare.
  • Microsoft Virtual PC.

Virtual Machine Monitor

• Maps virtual resources to physical resources (Memory, I/O devices, CPUs).
• Guest code runs on native machine in user mode.
• Traps to VMM on privileged instructions and access to protected resources.
• Guest OS may be different from host OS.
• VMM handles real I/O devices and emulates generic virtual I/O devices for guest.

Example: Timer Virtualization

• In native machine, on timer interrupt:
  • OS suspends current process, handles interrupt, selects and resumes next process.
• With Virtual Machine Monitor:
  • VMM suspends current VM, handles interrupt, selects and resumes next VM.
• If a VM requires timer interrupts:
  • VMM emulates a virtual timer.
  • Emulates interrupt for VM when physical timer interrupt occurs.

Instruction Set Support

• User and System modes.
• Privileged instructions only available in system mode.
  • Trap to system if executed in user mode.
• All physical resources only accessible using privileged instructions.
  • Including page tables, interrupt controls, I/O registers.
• Renaissance of virtualization support as current ISAs (e.g., x86) adapt.

Virtual Memory

• Use main memory as a “cache” for secondary (disk) storage.
• Managed jointly by CPU hardware and the operating system (OS).
• Programs share main memory, each gets a private virtual address space holding its frequently used code and data, protected from other programs.
• CPU and OS translate virtual addresses to physical addresses.
• VM “block” is called a page and a VM translation “miss” is called a page fault.

Address Translation

• Fixed-size pages (e.g., 4K).
• Virtual address components include Virtual page number and Page offset used to produce a Physical address.

Page Fault Penalty

• On page fault, the page must be fetched from disk, which takes millions of clock cycles and is handled by OS code.
• Try to minimize page fault rate with fully associative placement and smart replacement algorithms.

Page Tables

• Stores placement information.
• Array of page table entries, indexed by virtual page number.
• Page table register in CPU points to page table in physical memory.
• If page is present in memory:
  • PTE stores the physical page number plus other status bits (referenced, dirty, …).
• If page is not present:
  • PTE can refer to location in swap space on disk.

Translation Using a Page Table

• Virtual Address translation into a Physical address with memory Valid bit.

Mapping Pages to Storage

• Virtual page number mapped to Physical page or Disk address using Page Table.

Replacement and Writes

• To reduce page fault rate, prefer least-recently used (LRU) replacement.
• Reference bit (aka use bit) in PTE set to 1 on access to page, periodically cleared to 0 by OS.
• A page with reference bit = 0 has not been used recently.
• Disk writes take millions of cycles, so block at once, not individual locations.
• Write through is impractical, so use write-back with a dirty bit in PTE set when page is written.

Fast Translation Using a TLB

• Address translation would appear to require extra memory references:
  • One to access the PTE, then the actual memory access.
• But access to page tables has good locality, so use a fast cache of PTEs within the CPU, called a Translation Look-aside Buffer (TLB).
• Typical: 16–512 PTEs, 0.5–1 cycle for hit, 10–100 cycles for miss, 0.01%–1% miss rate.
• Misses could be handled by hardware or software.

TLB Misses

• If page is in memory, load the PTE from memory and retry (could be handled in hardware, or in software by raising a special exception with optimized handler).
• If page is not in memory (page fault), the OS handles fetching the page and updating the page table, then restarts the faulting instruction.

TLB Miss Handler

• TLB miss indicates:
  • Page present, but PTE not in TLB.
  • Page not present.
• Must recognize TLB miss before destination register overwritten.
• Raise exception.
• Handler copies PTE from memory to TLB, then restarts instruction.
• If page not present, a page fault will occur.

Page Fault Handler

• Use faulting virtual address to find PTE.
• Locate page on disk.
• Choose page to replace (if dirty, write to disk first).
• Read page into memory and update page table.
• Make process runnable again and restart from faulting instruction.

TLB and Cache Interaction

• If cache tag uses physical address:
  • Need to translate before cache lookup.
• Alternative: use virtual address tag with complications due to aliasing (different virtual addresses for shared physical address).

Memory Protection

• Different tasks can share parts of their virtual address spaces but need to protect against errant access.
• Requires OS assistance and hardware support for OS protection:
  • Privileged supervisor mode (aka kernel mode).
  • Privileged instructions.
  • Page tables and other state information only accessible in supervisor mode.
  • System call exception (e.g., syscall in MIPS).

The Memory Hierarchy

• Common principles apply at all levels of the memory hierarchy, based on notions of caching.
• At each level: Block placement, finding a block, replacement on a miss, and write policy.

Block Placement

• Determined by associativity:
  • Direct mapped (1-way associative): One choice for placement.
  • n-way set associative: n choices within a set.
  • Fully associative: Any location.
• Higher associativity reduces miss rate but increases complexity, cost, and access time.

Finding a Block

• Hardware caches: Reduce comparisons to reduce cost.
• Virtual memory: Full table lookup makes full associativity feasible, with benefit in reduced miss rate.

Replacement

• Choice of entry to replace on a miss:
  • Least recently used (LRU): Complex and costly hardware for high associativity.
  • Random: Close to LRU, easier to implement.
• Virtual memory uses LRU approximation with hardware support.

Write Policy

• Write-through: Update both upper and lower levels, simplifies replacement, but may require write buffer.
• Write-back: Update upper level only, update lower level when block is replaced, need to keep more state.
• Virtual memory: Only write-back is feasible, given disk write latency.

Sources of Misses

• Compulsory misses (aka cold start misses): First access to a block.
• Capacity misses: Due to finite cache size, a replaced block is later accessed again.
• Conflict misses (aka collision misses): In a non-fully associative cache, due to competition for entries in a set, would not occur in a fully associative cache of the same total size.

Cache Design Trade-offs

• Increase cache size: Decreases capacity misses, but may increase access time.
• Increase associativity: Decreases conflict misses, but may increase access time.
• Increase block size: Decreases compulsory misses, but increases miss penalty and for very large block size, may increase miss rate due to pollution.

Interface Signals

• Signals between CPU, Cache, and Memory for Read/Write operations, Address, Data, Valid and Ready signals.

Finite State Machines

• Use an FSM to sequence control steps with a set of states, transition on each clock edge.
• State values are binary encoded and the current state is stored in a register.
• Next state = fn (current state, current inputs) and control output signals = fo (current state).

Cache Coherence Problem

• In multiprocessor systems where two CPU cores share a physical address space, write-through caches can lead to incoherence.

Coherence Defined

• Informally: Reads return most recently written value.
• Formally:
  • P writes X; P reads X (no intervening writes) => read returns written value.
  • P1 writes X; P2 reads X (sufficiently later) => read returns written value.
  • P1 writes X, P2 writes X => all processors see writes in the same order and end up with the same final value for X.

Cache Coherence Protocols

• Operations performed by caches in multiprocessors to ensure coherence include: Migration of data to local caches and Replication of read-shared data.
• Snooping protocols: Each cache monitors bus reads/writes.
• Directory-based protocols: Caches and memory record sharing status of blocks in a directory.

Invalidating Snooping Protocols

• Cache gets exclusive access to a block when it is to be written.
• Broadcasts an invalidate message on the bus, and a subsequent read in another cache misses, and Owning cache supplies updated value

Memory Consistency

• When are writes seen by other processors, where “Seen” means a read returns the written value, which can’t be instantaneously.
• Assumptions:
  • A write completes only when all processors have seen it.
  • A processor does not reorder writes with other accesses.
• Consequence:
  • P writes X then writes Y => all processors that see new Y also see new X.
  • Processors can reorder reads, but not writes.

Byte vs. Word Addressing

• Example: 32-byte direct-mapped cache, 4-byte blocks.
  • Byte 36 maps to block 1.
  • Word 36 maps to block 4.

Ignoring Memory System Effects

• Iterating over rows vs. columns of arrays causes Large strides result in poor locality.

In Multiprocessor with Shared L2 or L3 Cache

• Less associativity than cores results in conflict misses, so more cores => need to increase associativity.

Using AMAT to Evaluate Performance of Out-of-Order Processors

• Ignores the effect of non-blocked accesses; evaluate performance by simulation instead.

Extending Address Range Using Segments

• A segment is not always big enough and makes address arithmetic complicated.

Implementing a VMM on an ISA Not Designed for Virtualization

• Non-privileged instructions accessing hardware resources requires to either extend ISA, or require guest OS not to use problematic instructions.

Concluding Remarks

• Fast memories are small, large memories are slow, so caching gives the illusion of fast, large memories.
• Principle of locality: Programs use a small part of their memory space frequently.
• Memory hierarchy: L1 cache « L2 cache « … « DRAM memory « disk.
• Memory system design is critical for multiprocessors.