컴퓨터의 CPU (3) - 캐시 메모리

https://basaeng.tistory.com/27

컴퓨터의 CPU (2) - 레지스터

레지스터에 이어 이번에는 CPU의 캐시 메모리에 대해서 알아보자.

 

개요

캐시 메모리는 CPU에서 메인메모리의 데이터를 가져올 때 드는 비용을 줄이기 위해서 사용하는 하드웨어 캐시이다.

RAM에 비해 CPU 코어에 더 가깝게 위치하며, 용량이 작고 빠르다.

 

보통 아래와 같이 메모리 계층을 표현한다. 

https://ko.wikipedia.org/wiki/%EB%A9%94%EB%AA%A8%EB%A6%AC_%EA%B3%84%EC%B8%B5_%EA%B5%AC%EC%A1%B0

 

상위 계층일 수록, 용량이 작고 속도가 빠르며 비싸다. 하위 계층일 수록 용량이 크고 속도가 느며 저렴하다. 

 

캐시 메모리는 메모리 계층에서 레지스터 바로 다음에 위치한다.

또한 캐시 메모리 안에서도 L1, L2, L3로 레벨이 나뉘어 캐시 내에서 L1이 상위 계층, L3가 하위 계층이라고 간단하게 생각할 수 있다.

 

---

캐시 라인

캐시에 대해 본격적으로 알아보기 전에 캐시 라인 개념에 대해서 알아야 한다.

캐시 라인은 CPU 캐시 메모리가 데이터를 저장하고 가져오는 최소 단위이다. 

RAM에서 캐시로 데이터를 가져올 때는 해당 데이터가 존재하는 캐시 라인 전체를 가져온다.

보통 캐시라인의 크기는 x86-64에서 64바이트 크기이며, 따라서 64로 나눠지는 주소값이 해당 캐시라인의 시작점이라고 볼 수 있다.

 

두 데이터가 같은 캐시라인에 속해있다면, 하나의 데이터를 캐시로 가져올 때 같이 캐시로 가져오게 된다.

---

캐시의 크기, 주소, way

내 PC의 캐시 정보

먼저 캐시의 크기, 주소, way에 대해서 알아보자.

 

캐시의 크기

위 사진은 cpu-z를 통해 확인한 내PC의 캐시 정보이다.

캐시는 L1 Data, L1 Inst, L2, L3로 나누어져있는 것을 볼 수 있다.

 

캐시의 크기를 보고 알 수 있는 것이 있다.

L1, L2는 코어마다 각각 존재하며, L3는 모든 코어에서 공유한다는 것이다.

 

이는 캐시 접근 속도와 캐시 일관성 설계에 큰 영향을 미친다.

• L1과 L2는 코어에 가장 가깝기 때문에 매우 빠르지만, 용량은 작다.
• L3는 여러 코어가 공유하기 때문에 접근은 비교적 느리지만, 용량이 크고 코어 간 데이터 공유에 유리하다.

 

캐시의 주소

캐시는 메인 메모리의 데이터를 저장하고 있지만,
전체 메모리 주소를 저장하는 것이 아니라 특정 방식으로 매핑해서 관리한다.

메모리 주소는 다음과 같이 세 부분으로 나뉜다.

구분설명

Tag	캐시에 저장된 데이터가 어느 메모리 블록을 나타내는지 구분하는 고유 식별자
Index	해당 데이터가 캐시 내의 어떤 "Set"에 위치하는지 결정
Offset	캐시라인 내부에서 데이터의 정확한 위치를 가리킴 (64바이트 캐시라인 기준)

 

즉, CPU가 메모리 주소를 보고 데이터를 찾을 때:

1. Index를 이용해 캐시의 특정 Set으로 이동한다.
2. Set 안에 저장된 여러 블록 중에서 Tag를 비교하여 일치하는 데이터를 찾는다.
3. Offset을 사용해 캐시라인 안에서 필요한 바이트를 읽는다.

순으로 캐시의 히트, 미스를 결정한다.

 

캐시의 Way

캐시는 인덱스의 충돌로 인해 캐시 미스가 발생할 수 있다.

캐시의 충돌을 낮추기 위해 같은 인덱스이더라도 서로 다른 Way에 저장해 충돌률을 낮추도록 만들었다. (Set-Associative)

 

단순히 인덱스를 늘려 Set 수를 증가시키는 방법도 있지만, 이는 캐시 크기와 비용의 급증으로 이어지므로 현실적인 해결책은 아니다. 특히 현대 프로그램은 방대한 주소 공간과 다양한 접근 패턴을 가지므로, 충돌 완화를 위해 Way 수를 늘리는 것이 효과적이다.

 

간단하게는 배열의 안에 또다른 배열이 있다고 생각하면 된다.

---

캐시 히트와 미스

데이터를 요청했을 때 캐시에 해당 데이터가 존재한다면 캐시 히트, 존재하지 않는다면 캐시 미스라고 부른다.

당연히 캐시 히트가 많을 수록 성능이 좋으며 캐시 미스가 많이 일어날 수록 성능이 떨어진다.

 

캐시 미스는 보통 3가지로 나누어 부른다.

1. compulsory miss: 해당 메모리를 처음 로드해서 생기는 미스이다. MESI에서 Exclusive 상태로 로드된다.

2. conflict miss: 두 개의 주소가 같은 인덱스를 가져서 일어나는 미스이다. LRU에 따라 먼저 적재한 쪽은 데이터가 날라간다.

3. capacity miss: 캐시 메모리 자체에 공간이 부족해서 생기는 미스이다. 

 

캐시 히트와 미스 예측

캐시의 기본 개념을 바탕으로, 어떤 메모리 접근이 캐시에 히트할지 또는 미스할지를 어느 정도 예측할 수 있다.
하지만 현실의 시스템은 단일 스레드 환경이 아닌 멀티코어, 멀티프로세스 환경이기 때문에,
다른 코어의 캐시 동기화, 컨텍스트 스위칭, OS 개입 등으로 인해 예측 정확도에 오차가 생긴다.
특히 캐시 히트는 미세한 타이밍 변화나 공유 자원에 의해 예측보다 더 낮게 발생할 수 있으며,
반대로 캐시 미스는 예측보다 더 많이 발생하는 경향이 있다.

---

캐시 사상 구조(캐시 배치 정책)

캐시는 현재 집합 연관 사상(Set-Associative) 방식으로 많이 사용된다. 이전에 사용되던 방법과 함께 보며 차이점을 확인해보자

 

직접 사상(Direct Mapped Cache)

메모리에서 인덱스 부분에 따라 그대로 캐시 메모리에 넣는 방식이다.

간단하지만 충돌이 자주일어날 수 있다.

 

완전 연관 사상(Fully Associative Cache)

메모리가 충돌하면 비어있는 곳을 찾아서 사용하는 방식이다.

비어있는 메모리를 찾아서 사용하기 때문에 캐시 미스율이 떨어지지만, 탐색 과정에서 많은 시간이 소요될 수 있다.

이를 해결하기 위해 CAM이라는 메모리를 사용한다고 한다. 

TLB(Translation Lookaside Buffer) 에서 사용하는 방식이다.

https://en.wikipedia.org/wiki/Content-addressable_memory

Content-addressable memory - Wikipedia

 

집합 연관 사상(Set Associative Cache)

직접, 완전 사상 방식을 적절히 섞은 방식이다.

캐시 index에서 way를 분리하여 만약 index 충돌이 발생한다면 way를 탐색하며 적절하게 저장한다.

현대 PC에서는 이 방식을 사용한다.

---

캐시 쓰기 정책과 MESI 프로토콜

캐시 쓰기 정책

캐시에 데이터를 쓸 때는 아래와 같은 방식들을 사용한다.

1. 캐시에 메모리가 써지면 바로 RAM에 저장한다. (write through)

2. 캐시에만 저장하고 캐시에서 필요없을 때 RAM에 저장한다. (write back)

 

일반적으로 우리가 코딩할 때 사용하는 데이터 캐시는 2번 write back 방식을 사용한다.

다만 현대 컴퓨터에서는 멀티코어 시스템을 사용하고, 코어는 개별적으로 L1, L2캐시를 가지고 있기 때문에 코어 간 메모리 일관성을 위해 별도의 프로토콜이 필요하다.

 

 

MESI 프로토콜

위에서 언급한 코어 간 캐시 일관성을 위해서 MESI 프로토콜을 사용한다.

 

MESI 프로토콜은

M: Modified

E: Exclusive

S: Shared

I: Invalid

라는 캐시의 상태를 기반으로 작동하는 프로토콜이다.

 

M,E,S,I 각 상태가 되는 상황 

처음 CPU를 통해 코어에 다른 코어에는 존재하지 않는  데이터(캐시라인 단위로)가 들어오면 해당 코어에서만 사용하고 있다는 의미에서 Exclusive 상태가 된다.

 

Exclusive 상태에서 가져온 데이터를 수정했다면 Modified로 상태가 변한다.

 

그리고 데이터를 가져오는데 다른 코어에 존재하는 데이터라면, L3캐시는 공유하기 때문에 데이터를 찾을 수 있을 것이다. 이 때 이제 해당 데이터는 Shared 상태가 된다.

 

Shared 상태에서 데이터가 변경된다면, 다른 코어들은 해당 데이터를 지운다. 이 때 데이터를 바꾼 코어는 Shared -> Modified상태로 변경하고, 데이터를 가지고 있던 다른 코어들은 Invalid 상태로 만든다. 

 

Exclusive -> Shared 는 단순히 상태를 Shared로 바꾸기만 하지만, Modified -> Shared는 바뀐 데이터를 RAM에 flush하기 때문에 비교적 속도가 차이날 수 있다.

 

현재는 MESI 프로토콜을 확장시켜 MOESI(Owned), MESIF(Forward) 등을 사용한다.

---

False Sharing

변수 a와 b가 동일한 캐시 라인에 존재한다고 가정하자.
이때 코어 A는 a를, 코어 B는 b를 각각 접근하면, 두 변수는 서로 다른 데이터임에도 불구하고 같은 캐시 라인에 포함되어 있기 때문에 MESI 프로토콜상 같은 데이터 블록으로 간주된다.
따라서 한 코어에서 a 또는 b를 수정하면, 해당 캐시 라인은 Shared 상태에서 Modified로 전이되며, 다른 코어의 동일 캐시 라인은 Invalid 상태로 전환된다.
이로 인해 불필요한 캐시 미스가 발생하게 되고, 결과적으로 성능 저하로 이어질 수 있다.

 

이러한 상황을 False Sharing이라고 한다. 실제로는 데이터를 공유하지 않지만 공유하고 있는 것처럼 불필요한 트래픽이 발생하기 때문이다.

 

결과적으로 Context Switching, Multi Thread 상황에서는 더욱 손해를 보게된다.

 

이를 해결하기 위해 alignas와 같은 함수를 사용한다.

alignas(64)를 변수 앞에 붙이면 해당 변수의 시작 주소는 64byte로 나눠지는 경계부터 시작한다.

int a;
alignas(64) int b;

위와 같이 선언하면 a다음에는 패딩이 붙고 b는 a와 다른 캐시라인에 존재하게 된다.

 

지역 변수의 경우 alignas를 사용하면 자동으로 해당 변수를 64 정렬로 스택 포인터 ebp를 조정시켜 주지만,

동적할당 malloc의 경우 32비트 아키텍처에서는 8바이트, 64비트 아키텍처에서는 16바이트의 정렬로 메모리를 할당하기 때문에 의도와는 다르게 메모리가 할당된다. 따라서 이 경우를 위해 _aligned_malloc이 제공된다.

https://learn.microsoft.com/ko-kr/cpp/c-runtime-library/reference/aligned-malloc?view=msvc-170

_aligned_malloc

 

---

간단한듯 복잡한듯 어렵다 다음은 뭐해볼까