[컴퓨터 구조] 24. Cache (2) - Direct-Mapped Cache

기본적인 캐시 동작

 

컴퓨터가 크게 위 그림과 같은 구조로 되어있다고 생각해보자.

 

 

이때 프로세서를 확대하면 위 그림과 같이 확대할 수 있다.

하나의 캐시 블록(캐시 라인)은 한번에 4개 워드를 관리한다.

 

또 메모리는 위와 같이 확대한다고 해보자.

녹색칸마다 4byte씩 주소가 증가하므로, 녹색 1칸은 4byte 크기를 갖는다는 것을 알 수 있다.

 

이때 CPU가 0x0004 위치에 있는 명령어를 읽는다고 해보자.

그러면 CPU는 먼저 캐시를 살펴본다.

현재 캐시에는 아무런 데이터가 없으므로 캐시는 메모리로부터 데이터를 갖고 온다.

이때 캐시는 정말 필요한 데이터 딱 하나만 가져오는게 아니라, 미리 정의한 블록(라인) 크기 단위로 데이터를 갖고 온다.

(위 메모리 그림에서 주황색 영역이 블록 영역이다.)

 

그러면 위 그림과 같이 데이터가 가져와졌다.

그리고 이렇게 블럭단위로 가져온 캐시 블록(라인)에 접근할 수 있는 주소 (tag) 로 0x0000_0 이라는 5bit 값을 부여했다.

지금 당장 필요하지도 않은 데이터까지 가져오는 것이 불필요해보이지만, 만약 미래에 CPU가 0x000C 위치의 데이터를 요구한다면 이때는 메모리까지 가지 않아도 캐시가 직접 44444444라는 값을 바로 보내줄 수 있다.

 

 

이번에는 비슷하게 0x0000_1208 위치에 있는 데이터를 요구한다면, 다시 캐시를 확인해보고 캐시에 데이터가 없다면 마찬가지로 미리 정의한 블록 크기 단위로 데이터를 읽어서 캐시로 가져올 것이다.

 

그러면 위 그림과 같은 모습이 된다.

 

Locality

캐시의 크기는 메인 메모리와 비교하면 아주 작은 크기다.

그런데 CPU가 어떤 값을 요구했을 때 그 값이 높은 확률로 캐시에 들어있도록 하려면 어떻게 해야할까?

이때 사용하는 것이 Locality 의 원리이다.

 

로켈리티는 크게 2가지가 있다.

Temporal Locality (locality in time) 과 Spatial Locality (locality in space) 이다.

 

템포럴 로켈리티는 말그대로 시간적 로켈리티이다.

템포럴 로켈리티는 한번 접근했던 위치는 나중에 또 접근하게 될 것이라는 내용을 의미한다.

마치 도서관에서 한번 빌렸던 책을 읽다가 말았다면 같은 위치에서 책을 찾게 될 것이라는 것과 같다.

 

스페셜 로켈리티는 특정 위치에 접근했다면 그 인접 주소에도 접근할 확률이 높다는 의미이다.

해리포터 시리즈 1권을 다 읽었다면 2권을 읽기 위해 인접한 곳에서 책을 찾을 것이라는 것으로 비유를 생각해볼 수 있다.

 

캐시에서의 템포럴 로켈리티를 활용하면 한번 접근한 데이터를 나중에 또 접근해서 사용할 가능성이 크므로, 가장 최근에 접근한 데이터를 계속해서 캐시에 남겨두려고 하는 노력한다.

만약 캐시 공간이 모자라서 어떤 데이터를 추가로 캐싱하려고 할 때 기존 데이터를 빼야한다면, 가장 최근에 읽었던 데이터는 남겨두고 나머지에서 빼는 것을 말한다.

 

스페셜 로켈리티를 활용하는 것은 방금 본 것처럼 한번 캐시에 데이터를 가져올 때, 그 데이터 하나만 가져오는 것이 아니라, 인접한 데이터까지 블록단위로 캐시에 저장하는 것을 스페셜 로켈리티를 활용한다고 볼 수 있다.

 

한번 코드 예시를 보자.

100개 원소를 갖는 배열 3개와 변수 하나를 선언했고, 반복문을 돌면서 배열의 원소에 접근해서 값을 계산하고 있다.

첫번째 반복에서는 0번 인덱스에 접근해서 덧셈을 하는데, 이때 이 데이터들이 처음에는 캐시에 없을 것이다.

따라서 메모리에서 데이터를 캐시로 가져올 텐데, 만약 이전에 본 캐시처럼 동작한다면 A[0] 만 가져오는 게 아니라 A[1], A[2], A[3]도 모두 가져올 것이다.

B, C도 마찬가지로 가져오고, D도 가져올 것이다.

 

이때는 캐시에서 데이터를 바로 가져오지 못했으니 그 효과를 누리지 못했다.

 

다음 반복이 되면 A[1], B[1], D 값을 이용해서 연산을 한다.

이때는 모든 데이터가 캐시에 들어있으므로 캐시에서 가져온 데이터로 연산을 할 수 있어서 더 빠르게 연산할 수 있다.

스페셜 로켈리티 원칙에 따라 인접 데이터도 같이 캐싱한 덕분에 효과를 본 것이다.

또한 D라는 데이터는 한번 접근했던 데이터에 또 접근해서 가져온 것이므로, 템퍼럴 로켈리티의 원칙에 따라 효과를 보았다고 볼 수 있다.

 

기본적인 캐시 용어

1. Block (Cache Line) 

캐시와 메모리 사이에 주고받는 데이터 크기 단위

만약 하나의 캐시 블록이 64byte 라면, 항상 캐시와 메인 메모리는 64바이트 단위 (16개 워드) 로만 주고 받는다.

이 크기는 상황에 맞게 CPU마다 다르게 정의할 수 있다.

보통은 64byte를 사용하고 있고, 지금 생각할 예시도 64바이트 단위를 사용한다.

 

2. Hit

코어가 요청한 데이터가 캐쉬 안에 있어서 바로 서비스할 수 있는 경우를 캐시 히트라고 한다.

캐시 히트는 많을 수록 좋다.

 

Hit Rate는 캐시 히트가 발생할 확률을 말한다.

만약 Hit Rate가 90%라면, 코어가 요청한 100개 명령어 중 90개는 캐시에 데이터가 있어서 캐시에서 바로 서비스할 수 있었다는 의미이다.

 

Hit Time 은 Hit 가 발생했을 때 걸리는 서비스 타임을 말한다.

Hit Time 은 메모리에서 서비스하는 시간보다 상대적으로 짧을 것이다.

 

3. Miss

코어가 요청한 데이터가 캐쉬 안에 없어서 바로 서비스할 수 없는 경우를 캐시 미스라고 한다.

Miss Rate는 히트가 일어나지 않을 확률이다. 따라서 Hit Rate + Miss Rate = 100 이 된다.

따라서 Miss Rate 는 1 - Hit Rate로 구할 수도 있다.

 

마지막으로 Miss Penalty 는 Miss가 발생했을 때 생기는 시간적 손해를 말한다.

 

Direct-Mapped Cache

캐시에는 몇가지 구조가 있는데, 제일 단순한 Direct-Mapped Cache 부터 한번 살펴보자.

 

우선 캐시와 메모리가 데이터를 주고받는 단위는 블록이다.

그래서 메모리와 캐시를 모두 블록 단위로 구획을 나눠 표시한 것이 위와 같다.

회색 한칸도, 주황색 1칸도 모두 블록을 나타낸다. (워드가 아니다!)

그러면 캐시 블록의 개수가 8개라고 가정할 때, 위와 같이 8개 블록으로 구성된 캐시로 나타낼 수 있다.

 

8개 캐시의 블록을 구분하려면 000부터 111까지 3개 bit를 사용해서 구분할 수 있다.

메모리의 경우 캐시보다 용량이 큰 것이 당연하다.

위 예시에서는 메모리가 블록 수로는 32개 블록으루 구성되어 있었다고 해보자.

(캐시보다 4배 크다)

그러면 이 경우, 메모리에서 각 블록을 구분하는 주소값은 5bit만 있으면 충분하다. (32개 블록이니까)

 

만약 CPU에서 00101 블록에 들어있는 어떤 워드를 읽으려고 했다고 해보자.

이때 캐시에 이 블록 데이터가 캐싱되어 있지 않다면, 메모리에서 00101 블록의 데이터를 모두 캐시에 저장한 뒤, 캐시에 저장한 데이터를 CPU에게 보내줄 것이다.

 

그런데 이때 메모리에서 읽은 00101 블록을 캐시에 있는 8개 블록 중 어떤 블록에 저장해야할까?

메모리의 블록과 캐시의 블록 사이의 관계를 매핑하는 규칙은 다양하게 있을 수 있다.

아무데나 빈 공간으로 가라고 할 수도 있고, 정해진 위치로 가라고 할 수도 있다.

이때 Direct Mapped Cache는 각 메모리의 블록마다 정확하게 한 군데로 정해진 캐시 블록 위치가 있다.

그런데 문제는 메인 메모리에 있는 블록 개수가 캐시의 블록 개수보다 많아서 당연히 여러 메모리 블록이 하나의 캐시 블록을 공유할 수 밖에 없다. 따라서 가급적 공평하게 분배해야 좋다.

 

이제 공평하게 분배하기 위해, 캐시블록의 크기인 8개를 기준으로, 메모리를 똑같이 8개씩 끊어서 나눠보자.

그러면 아래 그림과 같이 메모리가 나눠진다.

 

이때 하나의 색칠된 구역 속 블록들은 8개 블록으로 구성되어 있으므로 캐시의 블록과 왼쪽부터 차례대로 1대1 매핑을 시킬 수 있다. 이렇게 1대1로 매핑하는 것이 디렉트 맵드 캐시의 방식이다.

그리고 이렇게 매핑하면 메모리 전체적으로 봤을 땐 4개 블록이 하나의 캐시 블록을 두고 경쟁하는 관계가 된다.

 

그러면 각 메모리의 블록 주소와 캐시 블록 번호 사이의 규칙이 생기게 된다.

이 규칙은 메모리 블록주소의 하위 3개 비트를 보면 알 수 있다.

(3개 비트인 이유는 캐시 블록의 크기가 8개이기 때문이다.)

 

우선 메모리의 블록 번호 5bit 중에서 하위 3비트는 캐시 라인의 블록 번호와 1대1로 매핑시킬 수 있다.

4가지 색상 구역에서 항상 000 ~ 111 사이가 공통적으로 반복되기 때문이다.

그리고 4가지 색상 구역에서 어떤 색상구역을 나타내는지는 상위 2bit로 나타낼 수 있다.

이때 이 색상 구역을 나타내는 상위 2bit를 Tag 라고 부른다.

각각의 블록에 대해 너는 어떤 색상 출신인지 태그를 붙인 것과 같다.

 

캐시 블록을 기준으로는 하나의 블록에 들어갈 수 있는 메모리 블록의 종류가 4가지이다.

위 그림으로 보면 녹색, 노란색, 주황색, 보라색 중 하나이다.

이때 현재 들어가 있는 종류가 4가지중 어떤 것인지는 태그를 보고 알 수 있다.

 

 

이를 표로 나타내면 위와 같이 나타낼 수 있다.

Tag 왼쪽에 Valid 라는 필드는 뒤에서 정리한다.

 

이 표는 캐시의 블록들을 나타낸다.

하나의 line은 캐시의 블록 (캐시 라인) 을 나타내며 표에는 없지만 각각 자신의 인덱스를 갖고 있다.

이 인덱스는 000 부터 111까지 8개로 구분될 것이며, 메모리의 블록 어드레스의 하위 3bit와 매핑될 수 있을 것이다.

그리고 이곳에 저장된 데이터가 메모리의 실제 어떤 구역(색상)으로 매팽되는지는 Tag를 통해 알 수 있다.

 

---

 

지금까지 블록으로 이야기를 했는데, 실제 메모리 주소는 어쨌든 Byte Address로 표기되어 있다.

따라서 이번에는 Byte Address에서부터 따라가보자.

 

메모리는 본래 이렇게 Byte마다 주소가 1씩 증가하도록 매겨져있다.

여기에서 만약 1 word를 4byte 라고 정의한다면, 각각의 byte를 4개씩 묶어서 하나의 워드로 보고 워드마다 번호를 매길수도 있다.

 

그러면 위 그림과 같이 기존 byte address 에서 하위 2bit를 제외한 나머지 bit 로 묶어서 생각할 수 있다.

이때 하위 2bit를 제외했을 때 주소가 4개씩 겹치게 되는데, 이 겹치는 주소를 묶으면 오른쪽에 보이는 것처럼 0x0000부터 0x0003까지로 다시 1씩 증가하는 형태로 구분지을 수 있다.

 

이제 워드 단위로 번호를 매겼으니, 블록단위로 번호를 매기는 것을 생각할 수 있다.

 

32bit를 하나의 byte address로 사용하는 경우를 생각해보자.

이 32bit 숫자는 개념적으로 byte address를 나타낸다. (녹색 화살표 범위)

그러면 서로 구분할 수 있는 주소의 범위가 총 2^32 이다.

이때 하나의 주소는 1byte를 의미하므로, 32bit 메모리 주소 체계가 사용할 수 있는 최대 메모리 공간은 2^32 byte = 4G byte 이다.

 

만약 하나의 명령어, 또는 데이터를 구분하기 위해 word 단위로 번호를 매기고 싶다면, 이 byte address 에서 하위 2byte를 떼어낸 숫자를 사용하면 된다.

이를 word address 라고 부를 수 있다.

 

만약 캐시가 사용하는 블록의 크기가 4word 라면, byte로는 16byte 가 하나의 블록으로 사용된다는 것을 알 수 있다.

따라서 block address는 이 경우, 4개 bit를 떼어내고 남은 숫자로 구분하게 된다.

 

만약 캐시가 사용하는 블록의 크기가 8word 라면 byte로는 32byte가 하나의 블록으로 사용되므로 5개 비트를 떼어내고 남은 숫자로 구분하면 되고,

 

만약 캐시가 사용하는 블록의 크기가 16word 라면, byte로는 64byte가 하나의 블록으로 사용되므로 6개 비트를 떼어내고 남은 숫자로 블록을 구분하면 된다.

 

Direct-Mapped Cache의 기본 구조

 

기본적으로 Direct-Mapped Cache 는 위와 같은 구조를 가진다.

캐시가 가지는 하나의 블록 크기 (즉, 위 그림에서는 Data 영역의 한 칸의 크기) 는 CPU 설계 시점이 임의로 정해두며, 그 값은 보통 64byte (= 16word) 를 사용한다.

캐싱할 때는 메모리에서 블록단위로 읽은 데이터를 위 표에서 Data 한 칸에 쓴다.

 

만약 32bit 길이의 메모리 주소 체계를 쓴다면, word 주소는 30bit로 구분한다.

그리고 블록 하나의 크기가 16 word 라면 블록 주소는 여기에 6bit (2^6 = 64) 를 추가적으로 뺀 24bit 로 블록을 구분한다.

이렇게 블록을 구분할 때 사용하는 값이 Tag 가 된다.

 

Valid 는 1bit 데이터로, 이 cache block (line) 에 저장된 값이 유효한지 무효한지를 나타내는 bit 이다.

처음에 캐시에는 아무 값이 저장되어 있지 않으므로, 모든 값이 다 무효해야 한다. 따라서 모든 Valid bit 는 0으로 초기화 되어있다. 이후에 캐시에 올바른 캐시 데이터가 들어갈 때마다 valid 비트가 1이 될 것이다.

 

예시

4KB 의 direct-mapped cache 가 존재하고, 하나의 캐시 블록 크기가 1word (32bit) 라고 하자.

용량이 4KB 인 캐시라면, 모든 엔트리에 들어갈 수 있는 데이터 합이 4KB 라는 것과 같다.

그러면 얼마나 많은 block (cache line) 들이 캐시에 들어갈 수 있을까?

4KB = 4 * 2^10 byte 의 캐시 안에는 1word = 4byte 데이터가 2^10 = 1024개 들어갈 수 있다.

 

이 캐시의 구조를 그림으로 나타내면 위와 같이 나타낼 수 있다.

 

CPU는 그림과 같이 32bit 주소체계를 사용한다.

이때 어떤 메모리 주소에 접근해서 데이터를 캐시에서 읽어온다고 하면 우선 Byte Address 를 Word Address로 바꾼다.

 

 

근데 이 주소는 cache line 을 구분할 수 있는 단위이기도 하다.

왜냐하면 cache line 하나에 들어가는 데이터의 단위 크기가 1word 이기 때문이다.

따라서 이 주소는 Block Address 로서도 기능한다.

 

그렇다면 32bit 주소를 쓰는 CPU는 최대 4GB의 메모리 공간을 구분할 수 있을 때,

하위 2bit 를 제외한 나머지 30bit 로 메모리 공간의 워드를 구분하는 동시에, 이를 block 으로 구분할 수 있다.

 

그런데 cache 는 1024개의 엔트리를 가질 수 밖에 없기 때문에, 메모리의 block address 에서 하위 10bit 를 엔트리를 구분하는 용도로 사용한다.

 

 

이를 그림으로 나타내면 위와 같다.

direct-mapped cache 는 이 10bit index로 바로 몇번째 인덱스에 있는 캐시를 읽을지 1:1로 결정할 수 있다.

 

이때 메모리 입장에서는 같은 인덱스를 가리킬 수 있는 서로 다른 블록이 2^20 개 있다.

이를 구분해주기 위해 Tag 에는 20bit 데이터가 들어가서 메모리의 블록을 구분해준다.

 

 

따라서 메모리 주소값으로부터 캐시에서 값을 읽을 때는 위와 같이 byte offset 2bit 를 제외하여 word address 를 구하고,

다시 이로부터 block address 를 구한 뒤 (위 상황에서는 word address == block address ) 메모리에서 캐시 라인을 구분하는 그 다음 하위 10bit 를 이용해 엔트리 번호에 접근해서 그곳에 기록된 tag 와 현재 주소가 가리키는 남은 20bit 의 tag 를 비교해서 같은지 확인한다.

 

 

마지막으로 valid 비트가 1인지 확인했을 때 모든 조건이 해당한다면 cache hit 로 볼 수 있으며, 캐시에 저장된 데이터를 가져와 읽는다.

 

그러면 지금 이 캐시는 temporal locality, spatial locality 중에 어떤 것을 사용하고 있을까? 또는 둘 다 사용하고 있을까?

지금 이 캐시는 temporal locality만 사용하고 있다.

우선 최근에 요청받은 값을 캐시에 남겨두고 쓰고 있기 때문에 temporal locality는 맞다.

하지만 spatial locality는 해당하지 않는데, 블록의 크기가 1word 이기 때문에 하나의 명령어만 캐싱할 수 있기 때문이다.

spatial locality 까지 사용하려면 인접 워드들도 같이 캐싱해야 한다.

 

---

예시 2

이번에는 다른 예시를 보면서 direct-mapped cache 의 데이터 쓰기 동작에 대해서도 생각해보자.

캐시의 엔트리가 8개이고, block의 크기는 4byte = 1word 라고 해보자.

그러면 이 캐시는 총 32byte의 데이터를 캐싱할 수 있다.

그리고 아까와 다르게 CPU를 단순화해서 메모리 주소값의 길이가 8bit 라고 해보자.

 

 

이 상황에서 위와 같은 명령어들을 실행한다고 해보자.

만약 캐시가 없었다면 메모리 월 현상때문에 4개 메모리에 접근하는 총 시간은 굉장히 오래 걸릴 것이다.

이제 캐시를 사용했을 때 어떻게 되는지 그 동작을 살펴보자.

 

먼저 캐시에는 아직 아무런 값이 들어있지 않고, 따라서 valid 값도 모두 0으로 세팅되어 있을 것이다.

더미 데이터 값을 읽으면 안되기 때문이다.

 

1. lw $1, 24($0)

메모리 주소는 24가 된다. (0번 레지스터의 값은 항상 0이기 때문에)

24는 2진수로 나타낼 때 8bit 주소 체계로 보면 0001_1000 으로 나타낼 수 있다.

 

이 주소를 word address로 환산하면, 하위 2bit 를 버리면 되므로, 0001_10 으로 나타낼 수 있다.

동시에 이 주소는 block address 이기도 하다. 이 예제에서도 하나의 캐시 block 크기가 1word 이기 때문이다.

 

지금 캐시에는 8개 엔트리가 있으므로, 엔트리를 구분하는데 3bit 가 필요하다.

따라서 0001_10 중에서, 1_10 이 엔트리를 구분하는 3bit로 사용된다.

 

 

이를 그림으로 나타내면 위와 같다.

그런데 지금은 6번 엔트리의 valid 가 0이기 때문에 cache miss가 발생한다.

(이런 miss 를 아직 캐시에 데이터가 없기 때문에, 뜨겁게 달궈지기 전이기 때문에 발생하는 miss 라고 해서 cold miss 라고 한다.)

 

캐시 미스가 발생했기 때문에, 이제는 메인 메모리의 0001_1000 주소에 접근해서 데이터를 읽어와야 한다.

이때 데이터를 읽을 때는 정의된 블록 크기인 1word 만큼 데이터를 읽어올 것이다.

 

 

만약 메인 메모리의 24 주소에 a 라는 1word 값이 있었다면 이를 데이터로 가져온다.

 

그리고 캐시 블록의 인덱스를 구분하고 남은 상위 3bit를 tag로 하여 같이 저장하고, valid 비트를 1로 세팅한다.

a 라는 값은 이제 CPU에게 전달되어 $1 레지스터에 저장된다.

 

2. lw $2, 28($0)

 

두 번째 명령어도 같은 과정으로 처리하면 된다.

28은 111 이라는 인덱스를 가지고, tag 는 000 이다.

 

3. sw $3, 60($0)

이제 세번째 명령어를 살펴보자.

60 이라는 주소는 8비트로 나타매녀 0011_1100 으로 나타난다.

이 주소를 word address로 바꾸면 0011_11 이 된다.

여기에서 하위 3비트가 캐시의 index를 가리키므로 7번 인덱스를 살펴보게 된다.

 

그런데 지금은 직전에 7번 인덱스에 값을 썼기 때문에 valid 도 1이고, 데이터도 들어있다.

하지만 나머지 상위 3bit 인 tag를 비교했을 때 이 명령어는 001 이라는 tag를 가지므로 캐시에 들어있는 태그값과 다르다.

따라서 캐시 miss가 발생하게 된다.

 

이때 할 수 있는 행동으로 2가지 선택지가 생긴다.

첫번째는 기존 캐시값을 버리고 내가 쓰려고 하는 값을 캐시에다가 쓰는 것이다.

두번째는 기존 캐시값은 놔두고 내가 쓰려고 하는 값을 메모리에다가 쓰는 것이다.

 

첫번째 방법은 캐시를 비워서 공간을 할당하고 거기에 값을 쓴다고 해서 write-allocation 방식이라고 부른다.

두번째 방법은 캐시를 비우지 않고 직접 메모리에 쓴다고 해서 no-allocation 방식이라고 부른다.

 

우선 지금은 write-allocation 방식을 사용한다고 해보자.

그러면 아래와 같이 캐시가 바뀐다.

 

우선 메모리의 c 번지에서 데이터를 가져와 캐시에 쓰면서 tag도 업데이트 한다. (메인 메모리 블록 복사)

이때 기조에 쓰여진 b 라는 값은 방출된다.

valid는 여전히 1이다.

 

메인 메모리의 블록을 복사해서 가져오는 이유는 지금은 이게 1word 지만 만약 4word 라면 일단 복사할 때 4개 word를 모두 복사해두고 쓰려고 하는 word만 수정하기 위함이다.

 

 

이제 캐시의 데이터를 sw 명령어로 쓰려고 했던 값으로 업데이트 한다.

 

이때도 선택지가 2가지 존재하는데,

첫번째는 지금 시점에서 메모리에도 $3 레지스터의 값을 쓰는 것이고

두번째는 나중에 필요할 때 메모리에 $3 레지스터의 값을 쓰는 것이다.

 

이때 나중에 쓰는 것을 write-back cache 방식이라고 부른다.

그런데 이렇게 나중에 쓰게 되면, 메모리의 값과 캐시의 값이 현재 일치하지 않다는, 동기화되어 있지 않다는 것을 의미하게 된다.

이 상태를 나타내기 위해서 캐시에 새롭게 dirty 라는 비트 정보를 추가로 둔다.

 

그러면 위와 같이 구성할 수 있게 된다.

 

4. sw $4, 188($0)

이 상태에서 4번째 명령어를 실행한다고 해보자.

 

188 이라는 주소는 같은 방식으로 계산하면 인덱스 7을 가리키게 된다.

이 위치에 새롭게 값을 쓰려고 하는데, tag를 비교해보니 달라서 cache miss가 발생했다.

 

그러면 write-allocation 방식을 채택한 지금, 캐시에 188 위치가 속한 블록의 데이터를 모두 복사해온뒤, 

write-back cache 방식에 따라 캐시에만 업데이트하고 메모리에는 나중에 업데이트 해야할 것이다.

 

그런데 지금 시점에서는 캐시의 값을 당장 비울 수 없다.

왜냐하면 캐시에는 $3의 값이 새롭게 들어있고, 아직 메모리에는 이 값이 동기화되어 있지 않기 때문이다.

따라서 dirty bit 를 보고 동기화 여부를 확인하고, 값이 동기화 되어있지 않은 것을 확인한 지금, 메모리 값을 새롭게 업데이트 한다.

 

그리고 dirty bit 값은 0으로 바뀐다.

 

이제 188 주소가 속한 메모리 블록 데이터를 복사해올 수 있게 되었다.

 

기존 값을 복사해온 뒤, 

 

 

새로운 값으로 캐시를 업데이트하고, dirty bit를 세팅해준다.

 

---

Handling Writes

앞서 살펴본 예제로부터 read 상황에서 miss 가 발생했을 때와, write 상황에서 miss가 발생했을 때 동작을 살펴볼 수 있었다.

 

먼저 read 상황에서 cache miss 가 발생했을 때는 선택의 여지 없이 메모리에서 블록단위로 데이터를 가져와서 캐시에 새로 쓰고, 캐시는 그 안에서 필요한 데이터를 찾아 CPU에 전달해주어야 한다.

 

하지만 write 상황에서 cache miss 가 발생했을 때는 선택지가 존재했다.

첫번째는 캐시에 먼저 메모리 블록 값을 가져온 뒤, 캐시를 업데이트할 것인지 (Write-allocate)

두번째는 캐시에 쓰지 않고 바로 메모리에 접근해서 쓸 것인지 이다. (Write-no-allocate)

 

그리고 값을 쓸 때 역시 2가지 선택지가 존재했다.

첫번째는 캐시에 들어있는 block 내부 데이터만 업데이트하고, 메모리는 아직 업데이트 하지 않을 것인지 (Write-back)

두번째는 캐시와 그 밑에 있는 메모리들 (레벨2, 레벨3, 메인메모리) 모두에 데이터를 바로 업데이트 할 것인지 (Write-through)

 

write-back 방식은 dirty bit를 추가로 필요로 했었고, write-through 방식은 dirty-bit를 필요로 하지 않는다.

캐시에 값을 업데이트하는 것에 대해 선택지가 존재하는 것이기 때문에, write 단계의 선택지는 write-allocate 를 선택했을 때만 추가적으로 선택하면 될 것이다?

 

보통은 Write-allocate 와 wirte-back policy 가 함께 쓰이고, Write no-allocate 와 write-through policy가 함께 쓰인다.

(write through 는 캐시와 그 밑에 있는 모든 메모리에 값을 쓰겠다는 것인데, 엄밀하게는 write no-allocate는 캐시에 데이터를 불러오지 않으니까 적용할 수 없는 것 아닌가?)

그럼 level 1 캐시에서 캐시 미스가 발생했을 때 level 1 캐시는 쓰지 않고, level 2, level 3, main memory 는 쓴다는 것인가?

write-allocate, wirte-back 과 같은 policy는 모든 캐시가 동일한 방식을 공통적으로 사용하는가 아니면, 각 캐시마다 다른 정책을 사용할 수 있는가

 

예제

이와 관련하여 예제를 살펴보자.

 

Wrtie-Allocate & Write-back

write-back 방식을 사용할 때는 dirty bit 가 필요하므로 아래와 같이 캐시와 메모리를 구성할 수 있다.

 

이번 예제에서는 캐시블록의 크기가 4word 라고 해보자.

 

첫번째 쓰기 상황이다.

지금 상황에서는 캐시 Hit 가 발생했다.

TAG가 동일하고, valid 비트도 1이기 때문이다.

 

 

이때는 Write-back 정책에 따라 캐시에만 데이터를 업데이트하고, dirty bit를 1로 설정한다.

 

 

이번 쓰기 상황에서는 cache miss 가 발생했다.

Tag 가 가리키는 곳에 데이터가 없기 때문이다. (valid = 0) 

 

이때는 wrtie-allocate 정책에 따라 먼저 기존의 캐시 블록 데이터 (4word) 를 모두 불러온 뒤 캐시에만 값을 쓴다.

 

그러면 그림과 같이 4개 word 데이터가 모두 캐시에 allocate 된다.

 

그리고나서 이후에 쓰려고 하는 값을 쓴 뒤 dirty bit를 세팅한다.

 

---

write no-allocate & write-through

이번엔 두번째 조합, write no-allocate & write-through 방식을 살펴보자.

 

이번에는 dirty bit 필드가 필요없다.

 

이 상황에서 cache hit 가 발생했다면, wrtie-through 정책에 의해 캐시와 메모리 모두를 업데이트한다.

 

그러면 그림과 같은 상황이 된다.

 

 

만약 캐시 miss 가 발생했다면, write no-allocate 정책에 따라 캐시에 데이터를 allocate 하지 않고 곧바로 메모리에 데이터를 쓴다.

---

정리

이제 지금까지 정리한 내용을 요약해보면 캐시에서는 다음과 같이 4가지 상황이 발생할 수 있다.

 

1. Read Hits

우리가 원하는 상황이다.

 

2. Read miss

CPU를 잠깐 멈추고 (stall) 메인 메모리에서 캐시로 데이터를 가져온 뒤, 캐시에서 CPU로 데이터를 가져온다.

(만약 계층이 더 세분화 되어있다면, 그 세분화 된 계층 모두를 거친다)

 

3. Write Hits

wrtie-through cache 방식으로 캐시와 메모리 모두에 데이터를 쓰거나

write-back cache 방식으로 캐시에만 데이터를 쓴 뒤 dirty 비트를 세팅해서 표시해두고 나중에 메모리와 동기화 할 수도 있다.

실제로 메모리와 동기화되는 것은 write miss 가 발생해서 메모리의 block 데이터로 캐시가 교체될 때 동기화 된다.

 

4. Write Miss

write-allocate & write-back 방식으로 메모리에서 block 데이터를 캐시에 할당한 뒤, 캐시에만 업데이트 하고 dirty bit 를 세팅하거나,

write no-allocate & write-through 방식으로 캐시에 데이터를 불러오지 않은채로 직접 메모리에 데이터를 업데이트 한다.

 

4-word Block 의 direct mapped cache

캐시 사이즈가 4KB 이고, 1블록의 크기가 4word 라고 해보자.

그러면 4 * 1024 byte 에 들어갈 수 있는 block 의 개수는 4 * 4 byte = 16byte 로 나눈 256 개의 block (cache line) 을 갖는다.

 

따라서 byte offset 으로 2bit를 빼고, 4개 word 가 1block 이므로 block offset 으로 2bit 를 빼고, 남은 나머지 block address에서 캐시에 들어있는 256개의 block 을 구분할 인덱스를 위해 하위 8개 bit를 빼면 남은 20bit 가 tag가 된다.

 

이를 그림으로 나타내면 위와 같다.

이제 하나의 entry 에서 4개 word를 구분할 때는 block offset 을 이용해서 구분한다.

 

그러면 캐시에서 데이터를 가져올 때는 이렇게 valid, tag를 이용해서 hit를 판단하고, hit 일경우 데이터는 4개 word 중 하나를 선택해서 (선택은 block off 을 셀렉트 신호로 이용) 32bit 데이터를 가져온다.

 

이 예시에서는 1word 예시와 달리 temporal locality와 spatial locality를 모두 사용하고 있다.

최근 읽은 데이터를 캐싱하고 잇으므로 temporal locality는 해당되고, 이제 인접한 word를 4개씩 캐싱하므로 spatial locality 도 적용되었다.

따라서 만약 spatial locality를 적극 활용하고 싶다면 (높이고 싶다면) block 의 크기를 증가시키면 된다고 생각해볼 수 있다.

Cache 사이즈, Block 사이즈와 Miss Rate 사이의 관계

그렇다면 과연 block 크기를 키우면 무조건 캐시의 성능 (Hit Rate) 이 증가할까?

이에 대한 실험이 있다.

 

우선 오른쪽 legend에서 보이는 것처럼 캐시의 용량을 키우면 키울 수록, Miss Rate는 감소한다.

이건 어렵지 않게 예상할 수 있다.

 

이번엔 같은 캐시 사이즈일 때, block 크기에 따른 Miss Rate 의 변화를 보자.

처음에는 Miss rate가 줄어들다가 block size가 너무 커지면 오히려 miss rate도 같이 증가하는 것을 볼 수 있다.

x축이 오른쪽으로 가면 갈수록 spatial locality를 너무 기대한 나머지 너무 block size를 크게  구성하면 block의 개수가 줄어들어서 캐시의 역효과가 나타날 수 있다.

 

그래서 결론은 정해져있는 블록 사이즈는 원래 없다. (어떤 블록사이즈가 항상 최고의 결과를 낸다는 것이 정해져있지 않다.)

심지어 요즘에는 인공지능을 다루면서 큰 데이터를 다루다보니 로켈리티가 약해지는 측면이 있어서 다루기가 어려워졌다.

그럼에도 불구하고 지금까지는 CPU 회사가 자체적으로 책정하고 있는 값은 64byte 정도의 크기이다.

그래서 4바이트만 읽는 명령어를 실행해도 CPU는 64byte 를 가져와서 캐싱해서 CPU에 서비스한다.

 

캐시를 디자인하는 하드웨어 비용

이번에는 캐시에 들어가는 bit 수를 캐시를 디자인할 때 들어가는 비용의 관점에서 생각해보자.

bit 숫자로 볼 때 캐시에는 data 말고도 valid, tag 와 같은 부가적인 정보(오버헤드)가 함께 저장된다.

이 오버헤드 비용을 생각해보자.

 

16kb direct mapped cache 에서 한 블록의 크기가 4-word 라면, 32bit 주소 체계하에서 캐싱할 때 얼마나 많은 bit가 필요할까?

 

우선 한 블록의 크기를 byte로 나타내면 16byte 라는 것을 알 수 있다.

16 kb = 16 * 1024 byte 이므로, 이 캐시에는 1024개의 block이 있다.

따라서 블록을 구분할 인덱스는 10bit가 필요하다.

 

32bit 주소 체계에서 2bit를 빼면 word address가 되고, 여기에서 4 word 이므로 2bit를 추가적으로 빼면 28bit가 남는다.

남은 28bit 라는 block address 에서 하위 10bit를 인덱스 구분을 위해 빼면, 18bit가 남고 이게 tag가 된다.

 

따라서 캐시의 하나의 entry에는 dirty bit, valid bit, tag 18bits, data 16byte = 64bits 를 더하면, 하나의 block을 캐싱하는데 84bit가 필요하다.

 

이 entry가 총 1024개 있으므로, 실제로 캐시에는 84 * 1024 bit 가 필요하다.

 

이를 계산하면 대략 18.5 KB 가 나온다.

16KB를 캐싱하기 위해서 실제로 필요한 공간은 18.5KB 인 것이다.

%비율로 따지면 대략 15.6%의 공간이 더 필요한 셈이다.