Cache Architecture

Temporal Locality : Locality in Time
Spatial Locality : Locality in space

3C misses

Compulsory miss

처음 들어올 때 miss

Capacity miss

cache 사이즈가 적어서..

Conflict miss

hashing conflict

Direct Mapped Cache

• Cache의 특정한 위치에만 들어갈 수 있음
• 주소를 기준으로 cache에 저장
• (block address) % (cache 내 block 수)
• Valid bit, Tag bit
  

Replacement Policy

그런거 없음. 자동으로 ..

Associative Caches

• 2 ^ index bit * way 수 = cache에 들어가는 block 수

Fully Associative

cache의 아무대나 위치할 수 있음

• entry마다 comparator -> expensive
• 찾는데 시간 오래걸림

n-way set associative

각 set마다 n개의 entry

• Block Number(page address)가 which set에 들어가야 하는지를 결정 (Block number) modulo (# sets in cache)
• associativity 늘어나면
  -> miss rate 감소
  -> complexity, cost, access time 증가

Replacement Policy

LRU, Random..

Direct Mapped vs Associative Cache

• direct mapped: 한번에 찾을 수 있음
• n-way set associative : set까지는 한번에 찾을 수 있음. 그 안에서 # of blocks in set만큼 비교
• Fully associative : 그냥 싹다 비교
  

Multi-level Cache

example

single cache만 있는 경우

cycle 단위로 miss penalty 잘 구해서 miss rate랑 잘 곱해주면 됨

• 0.25ns : 1사이클에 걸리는 시간

L-2 Cache 추가

L1에서 miss penalty -> L2 access time으로 대체
global miss rate 구하고, 원래 miss penalty와 곱해준다

Cache hit

Write-Through

cache도 update하고 memory도 update

• write 때마다 stall이 생기니, 성능이 느려진다!
  ->write buffer쓰면, 꽉 찼을 때만 update하니까 ㄱㅊ
• consistency 보장

Write-Back

cache에만 update

• 수정된 block을 추적하다가(dirty bit), replace될 때 memory update
• cache <-> memory inconsistency 발생 가능

Cache Miss

No Allocate

don't fetch the block (Write around) and 메인메모리만 update

-> bios코드같은건 한번만 쓰고 뭐 더 쓰지 않으니까

Allocate

fetch the block

• cache에 가져와서 쓰기

Cache Performance example

• Instruction Cache : 모든 cycle에 access
• Data Cache : Load / Store cycle에 access
• miss rate * miss penalty 곱해서 Miss cycle 알아낼 수 있음
• base CPI + miss cycle해서 전체 CPI 구할 수 있음

Cache design trade-offs

Cache size가 커지면

장점 : capacity miss 감소
단점 : access time 증가

associativity가 커지면

장점 : conflict miss (hash conflict) 감소
단점 : access time 증가(여러번 비교해야함)

block size가 커지면

장점 : compulsory miss 감소
단점 : miss penalty 증가 (pollution에 의한 Miss rate도 증가할 수 있음)

miss penalty 줄이기

• requested word first
• non-blocking miss processing
• hardware prefetch

Main Memory

DDR

• Double Data rate
• rising,falling edge 모두에서 data transfer

AMAT (Average Memory Access Time)

• hit time + miss rate * miss penalty
  

Memory Bandwidth example

문제 :

• 1 bus cycle for addres transfer
• 15 bus cycle per DRAM access
• 1 bus cycle per data transfer

4-word block, 1-word wide DRAM

• Miss penalty : 1 + 4 * 15 + 4 * 1 = 65 bus cycles
  -> 4번에 걸쳐서 access and transfer
• Bandwidth : (16 bytes) / (65 cycle) = 0.25B / cycle

4-word block, 4-word wide DRAM

• Miss penalty : 1 + 15 + 1 = 17 bus cycles
  -> block 단위로 한번에 access
• Bandwidth : (16 bytes) / (17 cycle) = 0.94B / cycle

4-word block, 4-bank interleaved DRAM

• Miss penalty : 1 + 15 + 4 * 1 = 20 bus cycles
  -> access를 parallel하게 할 수 있음
• Bandwidth : (16 bytes) / (20 cycles) = 0.8B / cycle

Virtual Memory

main memory 공유하는데, protection하기 위해

Page Table (Address Translation)

• page 크기는 동일하므로 offset 비트 동일
• 실제 메모리 용량에 따라 PFN 비트 수도 결정
• (Valid bit = 1) == 현재 이 페이지가 메모리에 있다.
• (Valid bit = 0) -> Page Fault!
  

page fault penalty

• 크다.
• LRU 등 사용(reference bit보고 제일 예전에 쓴 애 결정)
• write back 사용

TLB (Translation Lookaside Buffer)

Page Table의 문제점

• cache를 access하려면 page table이 있는 main memory를 access해야 하는 문제!
  -> page table을 caching하면 어떨까?

TLB miss

1. page는 memory에 있는데, TLB에 없는 경우

memory에서 TLB로 PTE 가져오기 + 한번 더

• HW / SW 두 방식으로 처리 가능

2. page가 Disk에 있는 경우

OS가 page를 memory로 가져오고 Page Table update
instruction 재실행

• page 메모리로 가져오기
• replace할 page 찾기 - memory <-> disk (dirty)
• page memory로 가져오고, page table 내용 update
• faulting instruction 재실행

TLB와 Cache

• TLB를 통해 VA -> PA로
• PA를 다시 Cache의 주소체계로 (Tag + index)
• block offset : cache 1 block당 몇 word인지
• cache index : 한 way당 block의 수 (여기서는 cache 내의 block의 총 갯수)
• tag : 나머지

• 만약, page offset과 cache index의 boundary 같게 하면 -> cache index는 address translation 기다릴 필요 없이 먼저 access 가능!

Conclusion