[Computer Architecture] - Associative Cache

📕Associative Caches

• Fully associative cache
  • 모든 memory에 block이 캐시에 아무 곳이나 위치할 수 있다.
  • block들은 아무 공간에 위치할 수 있기에, 다른 Cache방법보다 search가 어렵습니다.
• Set associative cache는 direct mapped와 fully associative cache의 중간 개념이라고 생각하면 쉽습니다.
  • n-way set associative : 주어진 set안에 n개의 데이터가 존재합니다.
    • 데이터들은 지정된 공간중 아무 곳이나 위치할 수 있습니다.

• set-associative cache에서 memory block 
  • (Block number) modulo (Number of sets in the cache)
• associative의 degree를 증가시킬 때
  •  장점은 miss rate가 줄어든다.
  • 하지만 단점은 hit time이 늘어난다.
    • 왜냐하면 탐색해야 될 장소가 더 늘어나기 때문입니다.
  • degree가 늘어난다는 것은 n-way에서 n이 늘어난다는 뜻이다.
  • 그러면 하나의 set에 여러 개의 data가 들어갈 수 있다는 뜻이고, 원하는 data를 찾기 위해서 탐색해야 될 장소도 늘어난다는 뜻이다.

 

Eight-Block cache를 예로 들면

1️⃣one-way set associative -> direct mapped

2️⃣Two-way set associative 

3️⃣four-way set associative 

4️⃣eight-way set associative

{tag, data}가 8쌍 존재한다.

📕Misses and Associativity in Caches

📗direct-mapped cache

block address / block 수 = cache block의 위치

1. 0은 cache [0]에 위치하게 되고, cache에 0이 없었기에 cache miss가 일어난다.
2. 8은 cache [0]에 위치하게 되는데, cache [0]에는 이미 0이 있기에 0을 밀어내고, cache에 0이 없었기에 cache miss가 일어난다.
3. 0은 cache[0]에 위치하게 되는데, cache[0]에는 이미 8이 있기에 8을 밀어내고, cache에 0이 없었기에 cache miss가 일어난다.
4. 6은 cache [2]에 위치하게 되고, cache에 이미 존재하지 않아서, cache miss가 일어난다.
5. 8은 cache [0]에 위치하게 되는데, cache [0]에는 이미 0이 있기에 0을 밀어내고, cache에 8이 없었기에 cache miss가 일어난다.
6. 총 일어난 miss는 5번이다.

📗2-way associative cache

• 2개의 set이 잇다. 
• 0과 6과 8은 2로 나누면 나머지가 0이기에 set [0]에 위치하게 된다.

1. 0은 cache에 없어서 miss가 일어나고, set[0]에 위치하게 된다.
2. 8은 cache에 없어서 miss가 일어나고, set[0]에 위치하게 된다.
3. 0은 cache에 있어서 hit가 일어난다.
4. 6은 cache에 없어서 miss가 일어나고, set[0]에 있는 6을 밀어내고 그 자리를 찾아낸다.
   • 여기서 밀어내는 기준은 LRU방법을 사용한다.
     
     • LRU is Least recently used라는 뜻인데, 가장 오래전에 사용된 memory를 밀어낸다.
5. 8은 cache에 없어서 miss가 일어나고, LRU 방법에 의해 0을 밀어내고 set[0]에 위치하게 된다.
6. 총 4번의 miss가 일어났다. 

 

📗Fully associative cache

• 4개의 cache block - 여기는 아무 data나 위치할 수 있다.

1. 0은 cache에 없어서 miss가 일어나고 0번에 위치하게 된다.
2. 8은 cache에 없어서 miss가 일어나고 1번에 위치하게 된다.
3. 0은 cache에 있어서 hit가 일어난다.
4. 6은 cache에 없어서, miss가 일어난다.
5. 8은 cache에 있어서, hit가 일어난다. 
6. 총 2번의 hit가 일어난다.

 

📕Locating a Block in the Cache

• 총 캐시 크기를 동일하게 유지할 경우 associativity가 증가하면 set block 수가 증가합니다.
• N-way cache의 구성
  • N comparators : tag와 valid bit를 비교
  • n-to 1 multiplexers : n개의 set 중에서 N comparators에서 하나라도 존재할 경우 data를 반환.

 

📕Replace 될 Block을 선정하는 방법

• direct-mapped cache는 정해진 구역만 갈 수 있기에 , 선택지가 하나밖에 없어서, 단순히 밀어내는 작업만 수행하면 된 됩니다.
• set associative cache는 정해진 구역 내에서 block을 선정해야 합니다.
• fully associative cache는 모든 data가 아무 block에 위치할 수 있기에, 모든 block들은 대체 후보가 됩니다.
  
  • 그래서 우리는 대체될 블록들을 선정하기 위해서 LRU 방법을 사용합니다.
  • LRU는 가장 오랫동안 사용되지 않은 block을 선정합니다.