[CS:APP-ch6] The Memory Hierarchy

CS:APP ch-6 The Memory Hierarchy

6.1 Storage Technologies

SRAM

  • cache, transistor, stable, fast, expensive

DRAM

  • main memory, capacitor, sensitive( periodically refresh every bit )
  • d * w cells --> d supercells == r rows * c columns ( two dimension array )
  • data pins ( w bits ) & addr pins ( row addr i, column addr j )
  • Memory modules: Each supercell stores 11 byte. Each address represent by 8 supercells
  • Enhanced DRAM


Nonvolatile Memory ( ROM )

  • retain information even when they’re powered off

  • Flash memory ( erasable programmable ROM )

  • firmware: programs stored in ROM


Accessing Main Memory

  • I/O bridge: translate signals

Disk

  • platter --> surface --> track --> sectors

  • Logical Disk Blocks: hide complexity from OS

  • disk controller: maintains mapping between logical block number and physical disk sectors

  • I/O devices: USB, graphics card, host bus adapter

  • I/O bus: connect disks to CPU and main memory, independent under CPU

Accessing Disk

  • Memory mapped I/O: a block of addresses in the address space is reserved for communicating with I/O devices. Each of these address is known as an I/O port. Each device associated with one or more ports.
  • CPU read disk
    1. initiate a read
    2. indicate logical block number that should be read
    3. indicate main memory address to store disk sector
    4. do other work
  • Disk controller receives the read command
    1. translates logical block number to sector address
    2. read content
    3. transfer content directly to main memory ( DMA )
    4. send a interrupt signal to CPU
  • CPU returns control to the point where interrupted

Solid State Disk

  • A page can be written only after the entire block it belongs to has erased
  • A block wears out after roughly 100, 000 repeated writes
  • Advantage: semiconductor, faster, use less power, more rugged
  • Disadvantage: potential to wear out, expensive

6.2 Locality

Temporal Locality: reference again multiple times

Spatial Locality: reference nearby locations

stride-k reference pattern: visiting every kth element of a contiguous vector

k increase, spatial decrease


6.3 The Memory Hierarchy

Caching in memory hierarchy

Cache hits

Cache misses

  • replacing / evicting the block, victim block, replacement policy

Kind of Cache misses

  • cold miss: cache is empty
  • conflict miss: map to the same block
  • capacity miss: size of working set exceed

Cache management

  • partition storage into blocks, transfer blocks between levels, deal with hits and misses
  • compiler – register file
  • hardware logic – L1, L2, L3 caches
  • OS + Address Translation hardware – main memory
  • AFS client process – disk

6.4 Cache Memories

Main memory: $ M = 2^m $

cache: $ C = S * E * B $

  • $ S = 2^s $ cache sets, $ E $ = cache lines, $ B = 2^b $ = bytes per block

Address:

  • set index = $ log_2S $ – Sets
  • tag = $ m - ( s + b ) $ – Lines
  • block offset = $ log_2B $ – blocks

Process that cache determine hit or miss

  1. Set Selection
  2. Line matching: search each line, find tag bits in cache match tag bits in address
  3. Word Extraction: block offset provide first byte of desired word
  4. Line Replacement: random / least frequently used / least recently used

Direct-Mapped Caches

one line per set ( E = 1 )

Set Associative Caches

a E-way set

$ 1 < E < C/B $

Fully Associative Caches

S = 1

$ E = C/B $


Issues with writes

  • write-through ( immediately write to next lower level when hit )
  • no-write-allocate ( write directly to next lower level when miss )
  • write-back ( defers the update until it is evicted when hit )
  • write-allocate ( load the block into cache and update it when miss )

Anatomy of real cache hierarchy

  • Instruction cache ( i-cache )
  • Data cache ( d-cache )
  • both ( unified cache )

6.5 Writing Cache-Friendly Code

6.6 Putting It Together: The Impact of Caches on Program Performance

smaller size – better temporal locality

smaller stride – better spatial locality

The memory mountain