📕Associative Caches
- Fully associative cache
- 모든 memory에 block이 캐시에 아무 곳이나 위치할 수 있다.
- block들은 아무 공간에 위치할 수 있기에, 다른 Cache방법보다 search가 어렵습니다.
- Set associative cache는 direct mapped와 fully associative cache의 중간 개념이라고 생각하면 쉽습니다.
- n-way set associative : 주어진 set안에 n개의 데이터가 존재합니다.
- 데이터들은 지정된 공간중 아무 곳이나 위치할 수 있습니다.
- 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의 위치
- 0은 cache [0]에 위치하게 되고, cache에 0이 없었기에 cache miss가 일어난다.
- 8은 cache [0]에 위치하게 되는데, cache [0]에는 이미 0이 있기에 0을 밀어내고, cache에 0이 없었기에 cache miss가 일어난다.
- 0은 cache[0]에 위치하게 되는데, cache[0]에는 이미 8이 있기에 8을 밀어내고, cache에 0이 없었기에 cache miss가 일어난다.
- 6은 cache [2]에 위치하게 되고, cache에 이미 존재하지 않아서, cache miss가 일어난다.
- 8은 cache [0]에 위치하게 되는데, cache [0]에는 이미 0이 있기에 0을 밀어내고, cache에 8이 없었기에 cache miss가 일어난다.
- 총 일어난 miss는 5번이다.
📗2-way associative cache
- 2개의 set이 잇다.
- 0과 6과 8은 2로 나누면 나머지가 0이기에 set [0]에 위치하게 된다.
- 0은 cache에 없어서 miss가 일어나고, set[0]에 위치하게 된다.
- 8은 cache에 없어서 miss가 일어나고, set[0]에 위치하게 된다.
- 0은 cache에 있어서 hit가 일어난다.
- 6은 cache에 없어서 miss가 일어나고, set[0]에 있는 6을 밀어내고 그 자리를 찾아낸다.
- 여기서 밀어내는 기준은 LRU방법을 사용한다.
- LRU is Least recently used라는 뜻인데, 가장 오래전에 사용된 memory를 밀어낸다.
- 여기서 밀어내는 기준은 LRU방법을 사용한다.
- 8은 cache에 없어서 miss가 일어나고, LRU 방법에 의해 0을 밀어내고 set[0]에 위치하게 된다.
- 총 4번의 miss가 일어났다.
📗Fully associative cache
- 4개의 cache block - 여기는 아무 data나 위치할 수 있다.
- 0은 cache에 없어서 miss가 일어나고 0번에 위치하게 된다.
- 8은 cache에 없어서 miss가 일어나고 1번에 위치하게 된다.
- 0은 cache에 있어서 hit가 일어난다.
- 6은 cache에 없어서, miss가 일어난다.
- 8은 cache에 있어서, hit가 일어난다.
- 총 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을 선정합니다.
'Computer Science > Computer Architecture' 카테고리의 다른 글
[Computer Architecture] - Virtual Memory (0) | 2022.12.04 |
---|---|
[Computer Architecture]- Cache(1) (2) | 2022.11.26 |
[Computer Architecture] - Exploiting Memory Hiearchy(1) (0) | 2022.11.25 |
[Computer Architecture] - processor(3)-[pipeline, hazard] (0) | 2022.11.19 |
[Computer Architecture] - processor (2) (0) | 2022.11.12 |