[컴퓨터구조] Cache Memory - Set Associative Cache

 저번의 Direct Mapped Cache에 이어서

 

 

1-2. n-way Set Associative Cache

 

 Direct Mapped Cache의 경우 block의 개수가 1개였다. 여러개의 Word를 하나의 index에 저장하는 n-word block방식으로 여러개의 word를 한꺼번에 저장하여 hit rate를 높일 수 있다는 장점이 존재하기는 했지만 index단위로 갱신되는 특성상 같은 index에는 하나의 block만 저장할 수 있었다.

 

 이러한 단점을 해결하기 위해 n-way Set Associative Cache라는 방법이 존재한다. block의 크기를 단순히 늘리는 것이 아니라, 하나의 index에 여러개의 set을 두는 것이다. n-word block 방식과 비슷해 보일수도 있지만 여기서는 해당 index의 tag값이 틀리다고 해서 해당 block 전체를 갱신하지 않는다. n개의 별도 block이 존재하여 index에 따라 n개중에 tag값이 동일한 block이 한개도 없다면 miss를 내고 갱신하게 된다.

 이러한 방법을 위해 n-way Set Associative Cache에서는 각 index에 존재하는 여러개의 block마다 valid, tag가 별도로 존재해야 한다. 또한 index마다 n개의 별개의 block들이 존재하는데, 이것들을 하나의 set이라고 한다 (set size = n)

 

set마다 별도의 tag가 존재한다.

 따라서 Directed mapped cache는 1-way set associative cache라는 사실을 알 수 있다.

 

 

 1-way와 2-way의 차이를 명확하게 보여주는 예시이다. Direct Mapping에서는 0(0000, tag:00, index:00)과

4(0100, tag:01, index:00)을 연속으로 조회하자 index:00인 캐시메모리에 tag가 00과 01이 반복해서 들어가며 miss가 발생한다. 하지만 2-way cache에서는 index:00인 인덱스에 tag값이 2개까지 저장될 수 있기 때문에 valid bit이 갱신되는 (처음 데이터를 가져오는 경우) 처음 두번의 시도 말고는 모두 hit이 발생한다.

2-way Set-associative Cache. Direct mapped cache를 잘 이해했다면 이것도 어렵지 않다.

 

 그런데 만약 index의 모든 block에 데이터가 들어가 있는 상황에서는 어떻게 작동할까? direct mapping에서는 단순히 tag를 바꾸고 data를 갱신해주면 되는데, 여기서는 여러개의 데이터가 들어가있기 때문에 어떤 것을 갱신해야 할지에 대한 규칙이 필요하다.

 

이러한 규칙을 Replacement policy라고 하는데

i) Optimal - 미래에 가장 사용되지 않을 가능성이 낮은 것을 내보낸다.

ii) FIFO - First in, First out. queue의 그것 맞다.

iii) Random

iv) LRU - Least Recently Used. 사용한지 가장 오래된 것을 내보낸다.

와 같은 방법이 있다. 

 

 

- n-way에서 n에 따른 특징

 캐시의 크기는 동일하기 때문에 n을 2배 늘리면 index가 1비트 감소, tag는 1비트 증가한다.

index가 1비트 감소한다는 뜻은 index의 개수가 반으로 준다는 것을 의미한다.

(cache size = number of blocks*block size를 생각하면 된다. block의 개수가 index잖아?)

 그러면 n이 늘면 적은 index를 가지고 hit rate를 높일 수 있다는 장점이 있지만 comparator가 많이 필요하고 block에서 tag를 찾는 시간이 많이 필요하므로(hit time의 증가) 적당히 조절하여 사용하는 것이 좋을 것이다.

 

 

 

1-3. Fully Associative Cache

 

 n-way에서 n을 최대치로 늘리면 된다. index의 개수는 1개(비트수:0), tag로만 구별한다.

hit rate는 증가하겠지만 n개의 tag를 모두 확인해봐야 할 것이므로 hit time이 엄청 늘어날것이다. 그만큼 비효율적이겠지?