[Computer Arch.] Cache 종류

Cache란 processing unit과 memory 사이에 존재하는 data를 저장하는 logic으로 memory access의 긴 latency로 인한 performance overhead를 줄여줄 수 있는 logic이다.
Cache Wikipedia

여기엔 다양한 configuration으로 cache를 구성할 수 있는데 대표적으로 크게 3 가지가 존재한다.

1. Direct mapped cache
2. N-way set associative cache
3. Fully associative cache

우선 cache에서 사용하는 각 field들은 다음과 같다.

• Offset: 각 word (최소의 data size)를 선택할 수 있는 field
• Index: cache의 각 line을 선택할 수 있는 field
• Tag: 해당 cache line의 data가 맞는지 확인하기 위한 field로 보통 offset, index를 제외한 나머지 address 값을 저장한다.
• Valid: 해당 cache line에 data가 존재하는지를 나타낸다.
• Dirty: 해당 cache line이 memory의 최신 값과 다른 경우 assertion 됨

1. Direct Mapped Cache

Direct mapped cache의 경우 단순하게 input address를 가지고 빠르게 cache line에 접근하는 방식이다. 만약 이미 valid entry가 존재하는 address에 data가 존재하는 경우 기존 data를 덮어 쓰면서 tag field 또한 업데이트한다.

위 cache 구조의 경우 index + offset bit을 합치면 총 13-bit이기 때문에 2^13 8KB address range에 대해서 cover 가능하다. 동일한 cache size를 가져가더라도 direct mapped cache 구조가 더 많이 cover 가능하다.

위 그림의 cache configuration은 다음과 같다.

Configuration	Value
Cache size	8 KB
Cache line size	16 Bytes
# of cache entries (cache lines)	8 KB / 16 = 512
Offset bits	4 (16 = 2^4)
Index bits	9 (512 = 2^9)
Tag bits	19 (32 – 9 – 4)

1.1 Access Scenario

1. Address에서 index에 해당하는 tag를 읽는다
2. Address의 tag와 cache의 tag를 비교한다
3. 일치하면 해당하는 cache line의 data를 내보낸다 (Hit)
4. 일치하지 않는다면 memory로부터 data를 불러오고, 해당 address의 tag로 새롭게 업데이트한다 (miss)

2. Set Associative Cache

Direct mapped cache 구조와 다르게 동일한 index를 가지는 주소에 대해 추가적으로 data를 더 저장 할 수 있는 특징을 가진다.

위 cache 구조도 direct mapped cache example과 마찬가지로 8 KB 용량을 가지지만, 4-way로 구성되기 때문에 cover하는 address range는 1/4로 적어진다. 그러나 해당 영역 내에서만 memory access pattern이 존재한다면 성능 측면에서 더 좋을 것이다.

Configuration	Value
Cache size	8 KB
Cache line size	16 Bytes
Set way	4
# of cache entries (cache lines)	8 KB / 16 / 4 = 128
Offset bits	4 (16 = 2^4)
Index bits	7 (128 = 2^7)
Tag bits	21 (32 – 7 – 4)

2.1 Access Scenario

1. Address에서 index에 해당하는 tag를 읽는다
2. Address의 tag와 cache의 tag를 모든 way에 대해 모두 비교한다
3. 일치하는 way가 존재한다면, 해당하는 cache line의 data를 내보낸다 (Hit)
4. 일치하는 way가 존재하지 않는다면 memory로부터 data를 불러오고, 해당 address의 tag로 새롭게 업데이트한다 (miss). 여기서 어떤 way를 내보낼지는 replacement policy에 따라 달라진다. LRU, random, FIFO 등

3. Fully Associative Cache

Configuration	Value
Cache size	8 KB
Cache line size	16 Bytes
Set way	Fully
# of cache entries (cache lines)	8 KB / 16 = 512
Offset bits	4 (16 = 2^4)
Index bits	0
Tag bits	28 (32 – 4)

Fully associative cache의 경우는 모든 cache entry의 data를 way로 가져가는 구조로, 모든 cache line의 tag를 비교하기 때문에 power가 많이 소비된다. 그리고 address의 대부분의 영역을 차지하는 tag로 모든 cache entry를 lookup하는 CAM 구조를 포함한다.

3.1 Access Scenario

1. Address의 tag와 cache의 tag를 모든 cache line tag에 대해 모두 비교한다
2. 일치하는 way가 존재한다면, 해당하는 cache line의 offset에 해당하는 data를 내보낸다 (Hit)
3. 일치하는 cache line이 존재하지 않는다면 memory로부터 data를 불러오고, 해당 address의 tag로 새롭게 업데이트한다 (miss). 여기서 어떤 cache line을 내보낼지는 replacement policy에 따라 달라진다. LRU, random, FIFO 등

참고로 (Content-Addressable Memory) CAM 구조와 혼동이 될 수 있는데 해당 내용은 아래 post를 참고 바란다.

Difference between CAM and Fully-associative Cache?

Reference