Cache

Memory Hierarchy Concept

• ideal: infinitely large, infinitely fast
• mimicked imperfectly via hierarchy

Cache Memory

• based on the idea that if you want a piece of data from memory
• you'll want it again soon (temporal locality)
• you'll want other data from nearby(spatial locality)
• operation
• Saves data that has been recently used
• moves data from memory in lines(blocks)
  • higher bandwidth

e.g. ARM Cortex A9

line length = 8 words 4-way set associative critical word first size = 16, 32 or 64 kB

e.g

1. cache starts empty
2. read at $24
3. cache miss
4. all of B1 copied to cache L0
5. word 1 passed to proc
6. read at $28
7. cache hit in L0
8. word 2 passed to proc

Performance

• Average access time:
• t_avg = hC + (1 - h)M
• h = hit rate, (1 - h) = miss rate, C = cache hit time, M = miss penalty to load missing block

e.g.

h = 90%, C = 1 cycle, M = 10 cycles

t_avg = 0.9 x 1 + (1 - 0.9) 10 = 1.9 cycles

• improving t_avg
• Increasing h:
  • keep the right blocks(mapping scheme)
  • prefetch: load lines before requested(h/w prediction or s/w instruction)
  • bigger cache
• Decrease C:
  • small cache size
  • multiple banks
• Decrease M
  • load-through: give data to proc while line still loading
  • critical word first: memory sends block starting with requested data and wrapping

Store Instructions

• if block missing: write miss
• load-block
• modify cache line

Write policy:

• Write through:
  • modify mem at same time(poor performance)
• Write back
  • mark line dirty
  • write line to mem on eviction
  • cache cherncy problem: different caches with different copies of same block

Mapping Schemes

Eviction Policy

• if cache full(fully associative) or set full(set associative), which line should be replaced by new block(read/write miss)?
• Least recently used(LRU)
• better than FIFO or random

Address decomposition

e.g. line size = 32 bytes, #lines = 64, # address bits = 16

addresses 0 - 31 B0 0000 0000 000X XXXX

      32- 63   B0    0000 0000 001X XXXX

      64- 95   B0    0000 0000 010X XXXX

address 0x1234 => 0001 0010 0011 0100

Fully associative: 0001 0010 001 tag, 1 0100 offset

4 way set associative: 0001 001 tag, 0 001 index, 1 0100 offset
#sets = 64 / 4 = 16, index bits = log₂16 = 4

Direct mapped: 0001 0 tag, 010 001 index, 1 0100 offset
index bits = log₂64 = 6

Virtual Memory

• each process sees its own virtual address space 0 - 2ⁿ - 1
• virtual memory pages are mapped to physical (main) memory pages
• overflow(pages that exceed pysical memory capacity) are swapped to hard disk
• handout: v.m. for 2 processes
• (page size ~ 4kB: need large transfers to achieve good b/w due to high latenecy of HDD)

Page Table

• one per process
• list of mappings of virtual pages to physical pages(page frames)
• Memory Management Unit(MMU) translates virtual addresses into physical
• handout: v.m. address translation

Translation Lookaside Buffer

• caches recent v.p-to-p.f.(virtual pages to physical page frame)
• fully associative
• without TLB, every LD, ST or instr. fetch requires 2 mem accesses(1 for translation and 1 for data)
• handout: v.m. associative mapped TLB

Page Faults

• on address translation if no matching page frame, MMU raises exception
• page fault handler
• creates or swaps pages from HDD
• updates page table(s)
• returns and excepting instruction restarted
• page frames chosen for replacement via LRU

Hard Disk Drives

• data stored on magnetized platters spinning at 5000 - 10 000 rpm
• data stored using transitions in polarity
• platter surface
  

• access time = seek time(to move heads) + rotational delay(for sector to spin under head)

See next chapter See previous chapter