SHPC 10 - Caches

Principle of Locality

• Temporal locality
  • 최근에 접근한 데이터는 가까운 미래에 다시 접근할 가능성이 높다
• Spatial locality
  • 접근한 데이터 근처의 데이터를 접근할 가능성이 높다
• Predictable behavior가 많아지는 것이므로 좋다
• 예시
  • 데이터의 경우,
    • A를 차례대로 access한다 - spatial locality
    • sum을 반복 access한다 - temporal locality
  • Instruction의 경우,
    • 루프문을 반복 접근 - temporal locality
    • 명령어를 차례대로 접근 - spatial locality

Memory Hierarhies

• 스토리지의 계층적 구조
• 빠르고 비싼 스토리지는 작게, 느리고 싼 스토리지는 크게
• 빠른 스토리지를 느린 스토리지의 캐시로 사용

Caching

• 캐시 라인을 통해 여러 word를 저장
• cache line은 8~512bytes라고 되어 있는데
  • 이 크기에 따라 성능이 달라진다
  • 어플리케이션에 맞춰 하드웨어를 디자인한다
  • 한번 정해지면 하드웨어적이므로 바뀔 수가 없다

Cache Organizations in General

• Valid: 캐시 라인의 유효성
• Tag: 비교하여 찾는 데이터가 맞는지 확인
  • 메모리보다 캐시가 작아서 메모리가 여러 캐시라인에 대응될 수 있기 때문
• Set: 여러 캐시라인의 집합
  • 위와 마찬가지 이유로 존재
  • 대응되는 여러 캐시라인을 올려둔 것
• Cache size: L*S*B bytes

접근 방법

1. Set index로 index를 찾아감
2. Tag로 비교
3. Offset으로 찾아감

Direct Mapped Cache

• Associativity가 1인 것
• 가장 간단
• Replacement도 간단하다
  • Collision이 발생하면 해당 위치를 replace하면 됨
• MUX를 이용해 offset을 찾는다

Associative Cache

• 장점
  • Collision이 일어날 확률이 줄어든다
• 단점
  • Set 내의 Tag들을 비교하기 위해 트랜지스터가 더 많이 필요하다는 단점이 존재
  • Replacement policy가 조금 복잡해짐
• 세모는 control bit가 1이면 연결, 0이면 끊어짐
• 매치가 되는 캐시라인만 볼 수 있도록

Fully Associative Caches

• 하나의 set만 존재
• Tag 비교 하드웨어가 더 복잡, 충돌 확률이 없음

Type of Cache Misses

Cold(Compulsory) miss

• Cache가 비어있어서 나는 미스

Conflict miss

• Cache가 충분히 큰데, 같은 캐시라인을 여러 item이 매핑되어서 발생

Capacity miss

• Cache size때문에 나는 미스
• 구체적으로 active cache line (== working set)이 캐시보다 큰 경우
  • Working set: 특정 시간(e.g. 프로그램 실행) 동안 레퍼런스되는 블록들

Replacement Policies

• 가장 덜 사용되는 캐시 데이터를 replace하는 것이 가장 좋음
• LRU(Least Recently Used)
  • 하드웨어가 복잡함
• Pseudo LRU
  • 통계적으로 LRU와 비슷
  • 대부분이 이를 구현
• FIFO
  • 먼저 들어온 블록을 쫒아내기
• Random
  • LRU보다 조금 떨어지는게 신기

Least Recently Used (LRU)

• 구현하려면 많은 비트가 필요
  • n-way라고 하면 n!개의 순서가 존재. 이 모든 순서를 나타내기 위해서는 logn 개의 bit가 필요
  • 2-way set associative cache: 1 bit to encode 2 states in a set
  • 4-way set associative cache: 5 bits to encode 4! = 24 states in a set
  • 8-way set associative cache: 16 bits to encode 8! = 40320 states in a set → Pseudo LRU

Pseudo LRU

• Binary decison tree를 이용해 구현
• 각 분기를 1 bit로 관리
  • N-way set associative cache의 경우 $(2^{lo{g}_{2}N+1}-1)-N$
    • N개의 리프노드가 있으면 중간 노드의 갯수는 $N-1$ 개
    • 마찬가지로 그냥 $N-1$ 비트임
    • 괜히 어렵게 써놓네 뭐지
  • 해당 분기가 최근에 왼쪽으로 갔으면 1, 오른쪽으로 갔으면 0
• Replace를 하는 경우 bit를 봤을 때 접근을 안한것같은놈을 삭제
  • 아래는 테이블이 있지만 간단함
  • A의 경우는 1, 1, - 을 쓰는 접근이니 0, 0, - 인 경우 A를 접근하지 않았을 것
  • B의 경우는 1, 0, - 을 쓰는 접근이니 0, 1, - 인 경우 B를 접근하지 않았을 것
  • …
  • 이런식으로 테이블을 만들어서 가장 적합한게 뭔지 보면 된다

Write Policies

• Write through : 캐시에도 쓰고, 메모리에 바로 씀
  • 성능이 느리지만 write buffer를 이용해 극복 가능
• Write back : 캐시에만 쓰고 메모리에는 evict될 때 씀
  • 불필요한 쓰기를 막기 위해 dirty bit 관리
• Write allocate : 캐시를 가져와서 캐시에 write
• No write allocate : 메모리에 가서 메모리에 write, 캐시에는 가져오지 않음

Write through vs Write back

Read miss가 재미있음. speed 부분도

Write allocate vs No write allocate

• Write allocate : Write miss가 났을 때 캐시에 allocation을 하는 것
  • 가까운 미래에 접근할 데이터에 유용
  • e.g. 함수호출을 위해 stack에 인자를 push하는 경우, 컨트롤이 넘어가면 바로 볼 것
• No write allocate : Write miss가 났을 때 캐시에 allocation을 하지 않는 것
  • 주로 write through와 사용
  • 다시 접근하지 않을 데이터에 유용
  • e.g. I/O 버퍼를 채우는 경우

사실상 write back and no write allocate는 모순되는 정책을 가지고 있기 때문에(캐시에 쓰려고 함 vs 캐시를 가져오지 않으려 함) 사용될 수 없는 정책이다.

Non-Blocking/Lockup-Free Caches

• 대부분의 캐시가 한번에 하나의 요청만 처리할 수 있음
  • 미스가 나면 뒤의 요청들도 모두 기다려야 함
• Non-blocking cache는 cache miss 동안 뒤의 cache hit를 처리해줌
  • Miss penalty를 줄여주는 역할
  • 여러 개의 미스를 동시에 지원할 수도 있음
    • 각 미스마다 Miss status/Information Holding Registers(MSHRs)를 둬서 미스 상태를 관리하면 됨