5. Set-Associative Mapping

Address Conflict

Direct mapping에서 cache의 한 위치에는 하나의 block만이 들어갈 수 있다.

자주 사용하는 다수의 block이 하나의 같은 위치로 mapping 된다면 계속 miss가 발생하면서 block이 교체 될 것이다.

이는 miss rate의 증가를 일으키고 성능을 떨어뜨린다.

 

이렇게 2개의 block이 하나의 위치로 mapping 되면서 발생하는 문제를 2-way address conflict라고 한다.

만약, 3개의 block이 하나의 위치로 mapping되면서 문제가 발생한다면 3-way address conflict라고 한다.

 

---

Set-Associative Cache

Direct mapping과 유사하지만 address conflict를 해결한 방식이다.

 

Cache의 몇개의 block을 묶어서 하나의 set으로 구성한다.

Cache는 여러 개의 set으로 구성되어있다.

Main memory의 block들은 들어갈 set은 정해져있지만 set 내에서는 어디로 들어가든 상관 없다.

 

만약 하나의 set이 2개의 block으로 이루어져있다면 2-way set-associative cache라고 한다.

하나의 set이 3개의 block으로 이루어져있다면 3-way set-associative cache라고 한다.

 

즉, n-way set-associative cache는 block들을 n열 종대로 배열한 것이다.

 

자유도

Main memory의 block은 하나의 set에 있는 block의 수 만큼 자유도가 있다.

들어갈 set은 선택되어있지만 어디로 들어가는지는 상관 없기 때문이다.

2-way set-associatvie cache에서는 2개의 자유도가 있다.

 

Set-Associative Cache vs. Direct Cache

Direct mapping cache은 1-way set-associative cache로 볼 수 있다.

Cache에서의 전체 block의 수는 변하지 않는다.

 

Direct cache에서 16:1 mapping이었다면, 2-way set-associative cache 에서는 32:2 mapping이 된다.

Main memory의 32개 block 중 2개의 block이 하나의 set에 들어간다는 의미이다.

 

Main memory의 32개 중 하나를 구분해야 하기 때문에 tag의 bit 수는 증가한다.

Cache에서 8개의 set 을 구분하면 되기 때문에 index의 bit 수는 감소한다.

 

---

Two-Way Set-Associative Cache

Cache에서 하나의 set은 2개의 block으로 이루어져있다.

 

Placement

Main memory의 각 block은 들어갈 set이 정해져있다.

• 32:2 mapping
  • main memory의 32개 block 중 2개의 block이 하나의 set에 올 수 있다.
• tag : 5bit
  • main memory의 32($2^5$)개의 block을 구분해야 하므로 5bit이 필요하다.
• index : 3bit
  • cache에는 8($2^3$)개의 set이 존재하므로 3bit이 필요하다.

 

Identification

자유도가 2개 있으므로 set을 찾은 후 2개의 block을 모두 봐야한다.

두 군데에서 병렬로 찾음으로써 block을 찾는 것으로 인해 hit time이 증가하지는 않는다.

 

그러나 찾은 후 OR gate를 통해서 hit/miss를 판단하게 되고, MUX를 통해서 찾은 것을 선택한다.

OR gate의 추가와 MUX가 더 복잡하짐에 따라서 hit time이 살짝 증가하게 된다.

 

Replacement Policy

자유도가 있기 때문에 replacement issue가 발생한다.

들어갈 set 안의 2개의 block 중 어떤 것을 뺄 것인가를 결정해야 한다.

 

Direct mapping과의 차이점

Direct mapping은 같은 위치로 mapping되는 자주 쓰이는 2개 block이 동시에 cache에 들어올 수 없다.

그러나 2-way set-associative mapping에서는 자주 사용되는 2개 block이 하나의 set에 동시에 들어올 수 있다.

 

---

4, 8, 16-Way Set-Associative Cache

Way가 늘어날 수록 자유도가 증가한다.

 

4-Way Set-Associative Cache

• placement
  • 4-way set-associative cache는 64개의 block 중 4개의 block이 하나의 set에 들어갈 수 있으므로 64:4 mapping이 일어난다.
• identification
  • 4개의 way에서 병렬로 찾는다.
  • miss rate는 감소하지만, MUX와 OR gate가 복잡해짐으로써 hit time이 살짝 증가한다.

 

16-Way Set-Associative Cache

무조건 set0로 들어와야 하지만 set 안에서는 어디든 가도 된다.

이 예제에서 16-way set-associative는 최대 자유도를 가진다.

최대의 자유도를 가지는 ssociative mapping을 fully associative mapping이라 한다.

 

---

Fully-Associative Mapping

= content addressable memory

 

우리가 줄 수 있는 최대한의 자유도를 준 모델이다.

 

 

다음과 같은 특징을 가진다.

• index filed가 사라진다.
  • 무조건 set0로 가야하기 때문에 선택할 set이 없어진다.
  • 따라서 address에서 index의 bit 수가 0이 된다.
• parallel search
  • 내가 원하는 tag를 병렬도 search한다.
  • 이는 하드웨어로 구현되기 때문에 set 내에서 원하는 block을 찾음으로써 발생하는 hit time 증가는 없다.
• content addressable memory(CAM)
  • 원래는 index가 address의 역할을 한다.
  • 그런데 fully associative mapping에서는 address의 개념이 없다.
  • content를 가지고 parallel pattern matching을 해서 원하는 것이 있는지 없는지를 찾는다.
  • 이를 contetn addressable memory(CAM)이라 한다.
  • 메모리의 특별한 형태이다.

 

Performance

Miss rate가 최대로 해결이 가능하다.

즉, 가장 좋은 hit rate를 보인다.

 

어디서든 hit이 날 수 있기 때문에 identification에서 OR gate와 MUX의 구현이 가장 복잡해진다.

때문에 hit time이 살짝 증가하게 된다.

 

Fully-Associative Mapping을 해야 하는 경우

Cache가 작아서 block의 수가 적은 경우에서는 address conflict가 자주 나타난다.

따라서 이러한 경우는 fully-associative mapping을 통해 최대의 자유도를 줘야 한다.

 

---

Performance

• associativity ↑ → miss rate ↓
• miss rate가 가장 많이 감소하는 구간은 one-way → two-way 구간이다.
• cache size ↑ → miss rate ↓ : 더 많은 곳에서 찾기 때문, 단 hit time은 증가한다.
• cache size ↑ → associativity에 둔감하다.