Associative Caches

Fully associative

• block이 cache 내의 어느 곳에나 위치할 수 있게 한다
• requires all entries to be searched at once
• 각 entry와 연결된 comparator(비교기)를 이용해서 병렬로 검색한다 (expensive)

n-way set associatice

• each set은 n개의 entry를 갖는다
• 한 블록이 들어갈 수 있는 자리 개수가 고정되어 있다
• 각각 n개의 블록으로 이루어진 다수의 집합들로 구성되어 있다
• search all entries in a given set at once
• n comparators (less expensive)

3 reasons why cache miss

1. conflict miss
   • replace data
2. compulsory miss (cold miss)
   • empty cache
3. capacity miss
   • small cache size

주소가 12인 block의 위치

• Direct mapped
  • cache 내 메모리 블록의 위치
    : (block 번호) modulo (# blocks in cache)

• 2-way set associative
  • block이 들어가야 하는 집합
    : (block 번호) modulo (# sets in cache)
  • 각 set은 2개의 block을 갖는다

• 만약 block 번호가 4, 12, 4, 12일 때
  • direct : Miss(0) Miss(0) Miss(0) Miss(0)
  • 2-way : Miss(0-1) Miss(0-2) Hit Hit
  • reduce the conflict

• fully associative
  • 모든 block이 cache 내 어느 entry에나 map될 수 있다.

일단 block과 entry를 같은 스케일의 개념으로 이해하자

8-block cache

Example (4-block cache)

• block access sequence : 0, 8, 0, 6, 8

Direct mapped

• divide by 4
  

2-way set

• divide by 2
• LRU
  

Fully

• any place
• conflict miss는 최소화하지만, capacity miss가 발생할 수 있다
  

• Increasing associativity decrease miss rate

---

Organization

• 4-way set associative
• 주소는 tag - 22 bits, index - 8 bits, byte offset - 2 bits로 나뉜다
  (direct mapped : tag-20, index-10, byte offset-2)
• index가 8bits이므로, 256개의 set(?) 중 하나를 고른다.
  이 때, tag bits와 함께 matching해서
  only one matching -> HIT
  nothing maching -> MISS
• (교수님 설명) Using the index, read 4 entries in 4 different way in parallel
• cache size = 1024 blocks

---

Replacement Policy

• Direct mapped에서는 선택지가 없다.
  "replace that one block"
• Set associative에서는 일단 non-valid entry를 선호한다
  없으면, 다른 entry 중에서 골라야 한다
• LRU (Least recently used)
  • Choose the one unused for the longest time
• Random
  • LRU와 거의 비슷한 성능을 보이지만 그래도 LRU가 더 낫다

---

Multilevel Cache

• Primary cache(1차 캐시)는 CPU에 붙어있다.
  • 작고, 빠르다.
• Level-2 cache는 1차 캐시에서 miss가 발생할 때 접근된다
  • 크고 느리긴 하지만 main memory보단 빠르다
• Main memory는 2차 캐시에서 miss가 발생할 때 접근된다
• Some high-end systems include L-3 cache