SystemSoftware - Cache Memory #1

cache memory에 대해서 알아보자

 

 

Locality

 

Temporal locality(시간 지역성) : 최근에 접근했던 data나 명령이 가까운 미래에 다시 사용될 가능성이 높다. (마지막으로 사용된 시간이 오래될수록 다시 사용될 가능성이 낮아짐)

 

Spatial locality(공간 지역성) : 최근에 접근했던 주소와 가까운 data가 미래에 다시 사용될 가능성이 높다.

 

 

 

아래로 갈수록 느리면서 용량이 크고 가격이 싼 저장공간이 위치한다.

위로 갈 수록 용량은 적지만 속도가 빠르고 비싼 저장공간이 위치한다.

 

---

cache의 메모리 공간은 일정한 크기의 blocks으로 나뉘어진다.

cache에서 읽어 들일 수 있는 크기를 일정한 단위로 지정하는 것이다.

 

 

 

위 그림을 보면 CPU가 14번 블럭을 요청했고 cache에 14번 블럭이 있어서 cache hit가 발생한 상황이다.

 

 

 

 

지금 상황은 CPU가 12번 블럭을 요청했는데 cache의 공간이 모두 사용되고 있어서 기존의 9를 빼고 12를 cache에 넣은 모습이다. cache miss발생.

 

새로운 블럭으로 교체할 때 규칙이 필요한데 이를 Replacement policy라고 한다.

비어있는 공간에 cache블럭을 입력하는 규칙은 Placement policy라고 한다.

 

 

cache miss의 3가지 Type

1. Cold miss : cache가 처음에 비어있는 상태에서 cache miss가 발생하는 경우
2. Capacity miss : cache의 용량이 부족해서 발생하는 miss
3. Conflict miss : cache의 용량은 충분하지만 placement policy에 의해 현재 입력될 cache의 공간이 이미 사용 중인 경우

---

cache의 일반적인 구조

 

line : cache block이라고 생각하면 된다. (2의 제곱수) (E)

set : line이 여러 개 모여서 하나의 set을 형성한다. (2의 제곱수) (S)

그리고 여러 개의 set이 모여서 하나의 cache공간을 이루게 된다.

 

하나의 line은 block공간을 가지게 되는데 data를 저장할 수 있는 공간이 존재한다. (2의 제곱수 byte)

가장 왼쪽 1bit는 line에 유효한 cache block이 올라와 있는지를 검사하는 bit이다.

 

 

block에 대해서 알아보자.

 

하나의 block이 2^b byte의 크기를 가지므로 필요한 데이터의 위치를 block 내에서 찾기 위한 block offset은 b개의 bits가 필요하다.

set의 개수는 2^s 이므로 set의 위치를 알기 위해서 s개의 bit가 필요하다.

나머지 bit는 tag bits라고 한다.

 

cache 데이터를 찾는 과정★

1. 주소를 통해 set_index를 구한다.(몇 번째 set에 원하는 정보가 있는지 알아낸다.)
2. 해당 set의 모든 line을 탐색하며, 찾고자 하는 tag와 일치하는 tag를 가진 line이 있는지 알아낸다.
3. tag와 일치하는 line이 있고 해당 valid bit가 유효하면 cache hit가 발생한다.
4. 해당 line에서 block_offset을 이용해 찾고자 하는 정보를 얻는다.

---

Direct Mapped Cache (E = 1)

 

각 set당 line이 하나만 있다는 말이다.

-> set_index = s bit

 

cache block의 size를 8 bytes라고 가정하자.

-> block offset : 3bit

 

set_index를 통해서 set의 위치를 확인한다.

 

 

 

valid bit를 확인하고, line의 개수가 1개 이므로 바로 address의 tag와 일치하는지 확인한다.

block offset을 이용해서 원하는 정보를 가져온다.

block offset이 4이므로 4번 위치에서부터 int(4 bytes)만큼 데이터를 읽는다.

 

만약 tag가 일치하지 않는다면, 오래된 line을 방출하고 새로운 data로 교체한다.

 

 

시뮬레이션을 통해서 조금 더 자세히 알아보자

 

 

address정보가 4-bits라고 하자.

S = 4, E = 1, b = 1이라고 가정한다. (4개의 set, 1개의 line, 2^1 byte/block)

 

 

 

 

 

먼저 address로 0이 들어왔다.

cache의 처음엔 아무것도 없으므로 cold miss가 발생하고

00번 set에 data가 입력된다.

tag는 0이 입력된다.

블럭의 크기가 2byte 이므로 0-1모두 사용된다

 

 

 

두 번째로 1이 들어왔다.

00번 set에는 tag가 0인 정보가 들어있다.

hit가 발생한다.

block의 offset 1번에 접근한다.

 

 

세 번째로 7이 들어왔다.

11번 set에는 비어있으므로 miss가 발생하고 tag = 0, block에 2byte가 입력된다.

 

 

네 번째로 8이 들어왔다.

00번 set은 data을 가지고 있지만 tag가 일치하지 않는다.

그리고 다른 공간은 비어있기 때문에 conflict miss가 발생한다. 

기존에 있던 M[0-1] 정보를 방출하고 M[8-9]로 교체한다.

 

 

마지막으로 0이 들어왔다.

00번 set은 tag = 1이므로 conflict miss가 발생하고

기존의 M[8-9]를 방출하고 M[0-1]로 교체한다.

 

 

 

set당 line이 하나밖에 없으므로 00번 set의 정보가 방출과 교체를 반복하게 된다. (비효율적)

---

E-way Set Associative Cache (E = 2)

Direct Mapped Cache의 비효율성을 개선

way : set당 line의 개수

 

set에 있는 line들의 tag bit를 모두 비교한다는 점 외에는 Direct 방식과 모두 동일하다.

 

miss가 발생한 경우

Replacement policies

 

1. Random : 무작위로 방출한다
2. Least Recently Used(LRU) : 사용된 시간이 가장 오래된 data를 방출한다.

 

 

address정보가 4-bits라고 하자.

S = 4, E = 1, b = 1이라고 가정한다. (4개의 set, 1개의 line, 2^1 byte/block)

 

위 과정을 수행하면 아래와 같은 결과를 얻을 수 있다.

 

Direct 방식과는 다르게 cache 공간을 더 효율적으로 사용함을 알 수 있다.

 

---

 

궁금한 점이나 잘못된 점 댓글로 알려주심 감사하겠습니다!