Cache Memory (캐시 메모리) #1 Direct mapping (직접 사상)

Cache?

CPU 와 Memory 사이의 속도 차이를 줄이기 위한 고속 메모리입니다.
비용이 높기 때문에 작은 용량으로 구성됩니다. (메인 메모리보다 작음)
개발자는 캐시 메모리를 조작할 수 있는 명령어가 없습니다.

Cache hit : 원하는 데이터가 캐시 메모리에 있음
Cache miss : 원하는 데이터가 캐시 메모리에 없음
캐시 적중률 : Cache hit 횟수 / 전체 메모리 참조 횟수

캐시는 블록 단위로 데이터를 저장합니다. 블록은 여러개의 워드의 집합입니다.
워드는 CPU가 한 번에 처리할 수 있는 데이터의 크기를 가집니다. 즉, 레지스터에 옮겨 놓을 수 있는 데이터 단위이며 ALU을 통해 데이터를 조작하거나 할 때, 하나의 명령어로 실행될 수 있는 데이터 처리 단위입니다. ( 32 비트 운영체제 -> 32 bit word )

캐시는 메모리보다 작으므로 각 캐시 블록은 메모리의 여러 블록들에 매핑 될 수 있습니다. 해시와 유사합니다. 예를 들어 메인 메모리 512MB 인데 캐시가 128 MB 이라면, 캐시가 512MB 를 커버하기 위해서는 캐시의 한 블록은 메모리의 여러 블록에 대응되야 하겠죠.

캐시 : 음.. 내 데이터 메모리 1번 블록에 메인 메모리 8번, 16번, 32번이 매핑 될 수 있겠구나.. 그러면 8, 16, 32 를 구분할 무언가가 추가로 필요하겠다..

그래서 태그라는 것이 필요하고 태그는 CPU가 요청한 블록을 탐색하는 데 사용하는 주소 정보의 일부입니다. ( 주로 캐시 메모리의 용량은 데이터 메모리의 용량을 의미합니다. )

태그 이외에도 다른 구성요소가 있습니다.
유효 비트 : 캐시 블록이 valid 한 데이터인지. ( 컴퓨터 부팅시 무효로 초기화 )
갱신 비트 : 블록이 수정되었는지.
비교기 : CPU 주소와 태그를 비교.

자세한 건 아래에서 다뤄보겠습니다.

캐시의 기본 동작

1. CPU가 원하는 데이터 주소를 캐시로 보낸다.
2. 캐시 메모리의 비교기에서 태그를 탐색하고 비교한다.
3. 태그 일치(Hit)시 캐시의 해당 블록에 접근하여 원하는 워드를 CPU로 전송한다.
   이때 수정의 경우, 블록 갱신방식에 따라 갱신 비트를 사용하여 블록 수정 여부를 표시한다.
4. 태그 불일치(miss)의 경우, 캐시는 실패 신호를 CPU에게 보내고 CPU는 메모리에서 블록을 가져와 캐시의 데이터 메모리에 복사한다.
   이때 대응하는 태그를 갱신하고, 원하는 워드를 사용하게 된다.
5. 만약 메모리에도 없다면? 페이지 폴트! (여기서는 다루지 않습니다.)

캐시 설계 논점들

1. 캐시 메모리의 용량과 블록 크기
   캐시 메모리가 크면 무조건 이득인가? 블록의 크기는 캐시와 관련해서 어떤 영향을 미칠까?
2. 블록 사상 (mapping)
   캐시 블록과 메모리 블록을 어떻게 대응시킬까?
   직접 사상(여기서 다룹니다.), 완전 연관 사상, 집합 연관 사상
3. 블록 교체
   새 블록을 메모리에서 가져왔는데 캐시가 가득 차 있을 때, 캐시 블록 중 어떤 것과 교체해야 할까?
   무작위, FIFO, LRU ..
4. 블록 갱신
   캐시 내 데이터가 수정되면 대응되는 메모리 데이터는 언제 갱신시켜야 할까?
   즉시 쓰기, 나중에 쓰기 ..

블록 사상 (block mapping)

이게 왜 필요할까요? 위에서 잠깐 언급했지만. 캐시는 메모리보다 용량이 작으므로 다수의 메모리 블록이 동일한 캐시 블록에 매핑되기 때문입니다.

직접 사상 : 메모리 블록을 정해진 하나의 캐시 블록에만 사상 ( 메모리 0, 10, 100 번 블록은 무조건 캐시의 0 번 블록에 매핑! )
완전 연관 사상 : 메모리 블록을 어떤 캐시 블록에도 매핑할 수 있게 하는 것
집합 연관 사상 : 직접 사상과 완전 연관 사상을 절충. 메모리 블록을 캐시 블록의 정해진 집합내에서 사상

그래서.. 어떻게 메모리 블록을 캐시 블록에 매핑하는 걸까요?
이를 알아보기 위해 몇가지 가정이 필요합니다.

메모리 : 512 Byte
캐시 : 128 Byte
블록 : 16 Byte
워드 : 4 Byte
바이트 당 하나의 주소를 부여한다고 가정.

512 = 2⁹ 이므로 바이트 당 하나의 주소를 부여하기 위해 총 9 bit가 필요합니다.
즉 메모리 주소는 000000000 ~ 111111111 로 표현될 수 있습니다.
그런데 블록이라는 것이 있죠. 블록은 16 Byte 이고 16 = 2⁴ 이므로
512/16 = 2⁹ / 2⁴ = 2⁵ . 즉 블록 번호로 5 bit 가 필요합니다.

다시 말해서, 512 byte 메모리에 블록이 32개 필요하고, 이 32개에 주소를 부여한다면, 5비트가 필요합니다.
자 그러면, 블록은 워드의 집합으로 구성된다고 했으니, 블록도 워드로 나눌 수 있겠죠
블록 16 byte, 워드 4 byte 이므로
16/4 = 2⁴ / 2² = 2² . 즉 한 블록에 워드는 총 4개 들어가므로 워드 번호에 2bit가 필요합니다.
앞서, 메모리에 9 bit 가 필요하다고 했으니, 우리는 그 9 bit를 다음과 같이 나눌 수 있습니다.

앞의 5 bit : 블록 번호
뒤의 4 bit : 블록 오프셋
00000/00/00 : 00000번 블록의 0 번 워드의 첫 번째 바이트
00000/00/01 : 00000번 블록의 0 붠 워드의 두 번째 바이트
00001/01/01 : 00001번 블록의 1 번 워드의 두 번째 바이트

같은 방법으로, 캐시 메모리도 나눠 보면,
128 = 2⁷ 이므로 캐시 메모리 바이트 주소는 7 bit 필요 합니다.
128 / 16 = 2⁷ / 2⁴ = 2³ 이므로 블록이 총 8개 들어가고 블록 번호에 3 bit 가 필요하네요.
메모리와 동일하게 하나의 블록은 16 byte 에 워드 크기도 4 byte 로 동일하므로, 워드 번호에 2bit 필요 합니다.

앞의 3 bit : 블록 번호
뒤의 4 bit : 블록 오프셋
000/00/00 : 캐시 메모리의 000번 블록의 0번 워드의 첫 번째 바이트
001/01/01 : 캐시 메모리의 001번 블록의 1번 워드의 두 번째 바이트

즉, 메모리 블록 5 bit -> 캐시 3 bit 로 매핑됩니다.

직접 사상 ( Direct Mapping )

modulo 연산을 통해 메모리 블록을 캐시 블록에 사상.

5bit를 3bit 로 나누면 앞의 2bit 는 몫에 해당하고 뒤의 3bit는 나머지 bit에 해당합니다. 이 나머지 3bit 에 해당하는 캐시 블록에 매핑하게 됩니다.

메모리 블록 번호 00100, 01100, 10100, 11100 은 모두 하위 3bit 가 100 입니다. 이 블록들은 모두 캐시 메모리 블록 100 에 매핑됩니다.
앞의 2bit 가 바로 태그가 됩니다. 캐시 메모리 블록 100 에 블록이 채워져있는데, 이게 메모리 블록의 어떤 것을 가리키는지, 00100 인지, 01100 인지.. 판단할 수 있어야 겠죠? 그 역할을 태그가 하게 되는 것입니다.

결국, 직접 사상에서는 메모리 주소를 다음과 같이 최종적으로 나누게 됩니다.

직접 사상 방식에서 캐시 동작

캐시 메모리는 아래와 같이 비어 있다고 가정하겠습니다.

이 상태에서 CPU가 001000000 의 데이터를 참조했다고 해볼게요. ( 워드 a 요청 )

1. CPU 가 주소 001000000 의 데이터를 캐시 메모리에 요청
2. 캐시는 주소를 태그, 인덱스, 블록 오프셋으로 분할
   태그 : 00, 인덱스 : 100, 블록 오프셋 : 0000
3. 인덱스 필드 100 이 가리키는 캐시의 태그를 추출 하고 CPU 태그 00 과 비교
4. 유효 비트가 0 이므로 (캐시 초기화시 모두 0 ) 캐시 miss 신호를 CPU 에게 알림.
5. CPU 는 메모리에 주소 001000000 을 보내 데이터를 요청
6. 메모리는 워드 a가 있는 메모리 블록을 복사하여 캐시 메모리로 전송
7. 메모리 블록을 인덱스 필드 100 이 가리키는 캐시 블록으로 매핑하고 캐시 태그를 00 으로 갱신. 유효 비트를 1로 세팅 .
8. 블록 오프셋을 사용하여 캐시 블록에서 워드 a를 추출하고 CPU에게 전송

이 과정을 거친 뒤 캐시 메모리 상태는 다음과 같습니다.

자, 이번에는 CPU 가 001000100 (워드 b ) 을 요청했다고 해보겠습니다.

1. 위의 1~3 과정을 동일하게 수행
2. 유효 비트가 1 이고 두 태그가 일치하므로 캐시 hit.
3. 블록 오프셋이 0100 이므로 두번째 워드 b 를 추출하여 CPU에 전송

캐시 메모리 상태는 변하지 않고, 그대로 유지됩니다.

마지막으로 CPU가 111000000 (워드 e ) 을 요청한 상황을 보겠습니다.

1. 마찬가지로 1~3 과정을 동일하게 수행
2. 두 태그가 일치하지 않으므로 캐시 miss 신호를 CPU에게 보냄
3. CPU 는 111000000 을 메모리에 요청
4. 워드 e가 있는 메모리의 블록을 복사하여 캐시 메모리로 전송
5. 캐시 메모리 100 에 매핑해야 하는데 다른 블록 00100 이 이미 존재함. 이 블록의 갱신 여부를 파악하고 쓰기 정책에 맞게 처리.
6. 캐시 메모리 100 에 매핑하고 태그를 11 로 갱신.
7. 블록 오프셋 0000 이므로 첫 번째 워드 e 를 추출하여 CPU에게 전송

이 과정을 거친 뒤 캐시 메모리 상태는 다음과 같습니다.

직접 사상의 pros and cons

장점
- 태그 길이가 짧다.
- CPU 태그를 하나의 캐시 태그와 비교하므로 하나의 비교기만 있으면 된다. ( 구현이 간단)
- 메모리 블록이 사상될 캐시 위치가 정해져 있다. ( 교체 정책이 필요 없음. 그냥 모듈로 연산만 하면 됨)

단점
- 적중률이 낮은 편. ( 대용량 캐시 메모리일 경우에만 이 방식을 주로 쓴다고 함 )

캐시 메모리와 성능

️️ ⭐️ 지역성 원리

• 시간적 지역성
  특정 데이터에 한번 접근하면, 가까운 미래에 또 한번 그 데이터에 접근할 가능성이 높은 것
  -> 캐시 hit 가 계속 발생!
• 공간적 지역성
  특정 데이터와 한번 접근하면, 그 데이터와 가까운 주소의 데이터에 다시 접근할 가능성이 높은 것.
  -> 블록 단위로 캐시에 가져오므로 근처의 데이터를 계속 요청하면 캐시 hit 가 계속 발생!

성능 개선

• 실패율을 줄이자
  블록의 크기를 늘리자!
  연관도를 높이자! ( 메모리 블록이 매핑할 수 있는 곳이 한 군데가 아니라 여러 군데라면? )
  캐시 용량을 크게 하자!
  컴파일러를 똑똑하게 만들어서 메모리 사용 최적화 시키자!
• 실패시 패널티를 줄이자
  메모리 접근 타임을 줄이자! ( 메모리 대역폭 향상, 블록 크기 줄이기, 요청한 워드 우선 전송방식 등 )
• 적중 시간 줄이자
  캐시 접근 시간을 줄이자! ( 캐시 소용량화, 직접 사상 등 )
• 블록 크기와 성능
  블록을 크게하면, 공간적 지역성 상승으로 적중률이 상승한다. 블록 개수의 감소로 태그 메모리 양이 감소한다.
  하지만 메모리 엑세스 시간이 증가하여 캐시 미스시 패널티가 커진다.
  블록을 작게하면, 메모리 엑세스 시간이 감소하여 캐시 미스시 패널티가 감소한다.
  하지만 공간적 지역성 감소로 적중률이 감소한다. 태그 메모리 양이 커진다
• 캐시 용량과 성능
  캐시 용량을 늘리면, 공간/시간 지역성 상승으로 적중률이 증가하지만 하드웨어 부담이 커진다.
  캐시 용량이 작으면, 캐시 적중률이 감소하고 사상 방식 선택에 제약이 생길 수 있다.
• 그 외
  다단계 캐시