[컴퓨터 구조] Mapping 방식의 비교

---

앞의 글을 읽으시면 이해에 도움이 됩니다.

 

2022.11.22 - [Computer Science/컴퓨터 구조] - [컴퓨터 구조] The Basic of Cache

[컴퓨터 구조] The Basic of Cache

2022.11.23 - [Computer Science/컴퓨터 구조] - [컴퓨터 구조] Direct Mapping

[컴퓨터 구조] Direct Mapping

2022.12.04 - [Computer Science/컴퓨터 구조] - [컴퓨터 구조] Associative Mapping, Cache

[컴퓨터 구조] Associative Mapping, Cache

---

1. Eight-block cache example

 

 

8개의 block을 가지는 Cache가 있다고 가정해봅시다.

n-way에서 n은 degree라고 하며, degree가 증가함에 따라 보이는 장단점을 살펴봅시다.

 

첫 번째는 One-way set associative입니다.

해당 방식은 set에 하나의 block이 존재하며, 이는 Direct mapping 방식과 같습니다.

One-way set associative

두 번째는 Two-way set associative입니다.

4개의 set로 나뉘며, 각각의 set는 2개의 block을 가지고 있습니다.

Two-way set associative

세 번째는 Four-way set associative입니다.

2개의 set로 나뉘어지며, 각각의 set는 4개의 block을 가지고 있습니다.

Four-way set associative

마지막은 Eight-way set associative입니다.

이는 Fully Associative와 같은 방식입니다. 하나의 set에 8개의 block이 존재합니다.

Eight-way set associative

 

그렇다면 degree가 증가함에 따라 보이는 장점은 무엇이 있을까요?

degree를 증가함에 따라 생기는 장점은 바로 miss rate가 감소한다.입니다.

 

그렇다면 단점은 hit time이 증가한다, 그리고 하드웨어가 복잡해지고, comparator를 추가로 달아야 한다.입니다.

그림으로 한 번 봅시다.

---

2. Example

 

 

4개의 block을 가지고 있는 cache가 있습니다.

입력되는 memory block address는 0, 8, 0, 6, 8입니다.

이제 direct, 2-way set associative, fully associative를 비교해봅시다.

---

2.1 Direct-mapped cache

 

 

 

 

block address에 따른 cache block의 위치는 앞의 글을 참고하시면 됩니다.

miss가 5번이나 발생하네요.

상당히 안 좋아 보입니다.

 

0번과 8번 같은 경우에는 서로 번갈아가면서 참조되기 때문에 계속해서 miss가 발생합니다.

6번은 한 번만 참조되지만, cache의 2번 block에는 6번이 없기 때문에 miss가 발생합니다.

---

2.2 2-way set associative cache

 

 

 

이번에는 miss가 4번 발생하네요.

특이한 점이 모든 block이 0번 set에 mapping 된다는 점입니다.

들어가야 하는 block은 3개인데, 0번 set에는 entry가 2개밖에 없습니다.

따라서 한 개는 교체되어야 합니다.

교체 정책에 대해서는 나중에 알아봅시다.

(운영체제 카테고리에서 더 자세히 쓸 예정입니다.)

---

2.3 Fully associativie in cache

 

 

miss가 3번 발생했습니다.

아무 위치에 매핑될 수 있기 때문에, 한 번 cache에 들어가면 자리가 꽉 차서 교체되기 전까지는 hit가 발생합니다.

 

16-word block을 가지고 있는 64KB data cache를 대상으로 시뮬레이션 돌린 결과입니다.

degree of Associativity가 증가할 수록 miss rate가 감소하네요.

하지만 그와 동시에 참조 시간도 증가했을 거예요.

---

3. Locating a Block in the Cache

 

 

n-way cache는 n개의 comparator와 n-to-1 multiplexer를 가지고 있습니다.

n은 miss rate와 time, extra hw 사이의 trade-off를 생각하여 결정해야 합니다.

 

4-way set cache의 구조를 봅시다.

4-way set associative cache

address의 index field를 통하여 4개의 block을 참조합니다.

그와 동시에 tag field를 비교하여 어느 set이 참조 값을 가지고 있는지 비교합니다.

(아래에 있는 =이 comparator)

 

따라서 특정 set에 참조 값이 있다는 것을 알게 되고,

이를 multiplexor를 통하여 해당 set의 값을 추출합니다.

 

 

이번 글은 여기서 끝내도록 하겠습니다.

 

다음 글이 마지막이 되겠네요.

다음 글에서는 Replacement Policy와 multilevel cache에 대해 설명하도록 하겠습니다.

 

2022.12.04 - [Computer Science/컴퓨터 구조] - [컴퓨터 구조] Replacement Policy, Multi level Caches

[컴퓨터 구조] Replacement Policy, Multi level Caches

 

감사합니다.