4. 캐시 메모리

4. 캐시 메모리 - 2025/08

캐시 메모리

 

연산결과를 메인 메모리에서 읽어오고 메인 메모리에 쓰는 작업은 상당히 부담 되는 작업 입니다.
이 경우의 성능 손해를 피하기 위해서 메인메모리의 사본을 코어 근처에 두는 방식으로 구현된 장치가 캐시 메모리입니다.
현대 멀티코어 CPU는 보통 3개 계층의 캐시메모리를 칩 안에 가집니다.
차례대로 L1, L2, L3 캐시라고 부릅니다.
가장 마지막 계층의 캐시를 (Last Level Cache, LLC) 라고 부르기도 합니다.

LOAD와 STORE 명령이 많고, 부하의 대부분을 차지하는 특성상,
프로세서는 다양한 작업에 하드웨어 캐시를 사용합니다.
대표적으로는 명령어 캐시(Instruction Cache, 줄여서 I$ 라고도 부름),
데이터 캐시(Data Cache, 간단하게 D$ 라고도 부름) 등이 있습니다.
물론 Store Buffer 와 Load Buffer 도 따지고 보면 캐시지만,
이건 따로 다루기 위해 넘어가겠습니다. 
현대의 멀티코어 CPU의 경우에는 L1,L2 는 코어 독립적이고,
L3의 경우에는 모든 코어가 이를 공유 합니다.

 

캐시 라인의 검색

필요한 주소의 데이터를 빠르게 가져올 수 있게 하는 장치가 캐시입니다.
따라서 주어진 주소가 있다면, 이 주소에 해당하는 값이 있는지 캐시에 있는지
검색을 빠르게 할 수 있는 방법이 필요합니다.
방식은 다음과 같습니다. 
주어진 주소가 있을때에 그 주소를 태그, 인덱스, 오프셋 세 파트로 나눕니다.

먼저 오프셋은, 라인내에서의 오프셋을 이야기합니다.
해당 라인 내에서의 N번째 바이트를 이야기 하는 것 입니다.
따라서 캐시라인의 크기와 똑같습니다.
따라서, 대부분의 컴퓨터가 캐시라인이 64바이트인 것을 고려하면,
6비트가 필요할 것 입니다.

다음으로 인덱스는, 캐시 장치 내에서의 위치입니다. 따라서, 장치의 캐시 크기만큼 표현이 가능해야 합니다.
예를 들어, 어떠한 아키텍처의 데이터 캐시 크기가 32KB라고 하면, 2^15/2^6
9비트 만큼의 공간을 인덱스에 할당해야 합니다.

그리고 나머지를 태그 비트로 활용합니다.
위의 예로 적용한다면, 인덱스로 9비트, 오프셋으로 6비트, 나머지 49비트는 태그로 활용이 가능할 것 입니다.

캐시 라인의 배치
앞선 예시에서, 인덱스와 오프셋의 합은 15비트니까, 2^15까지 표현이 가능했습니다.
물론 캐시메모리의 크기가 메인 메모리의 크기보다는 작기 때문에, 당연한 이야기지만
매핑시 캐시 메모리에서의 위치가 겹치는 주소가 발생합니다.
예를 들어, 다음의 두 주소는 캐시 인덱스가 겹칩니다.

0xA6A00 ->  1010 0110 1010 0000 0000 -> 10100 |110101000 | 000000 
0xAEA00 ->  1010 1110 1010 0000 0000 -> 10101 |110101000 | 000000

인덱스가 겹칠때마다 캐시라인을 교체한다면, 캐시 미스가 많이 일어날 것입니다.
따라서, 대부분의 프로세서는 같은 인덱스를 위한 캐시라인을 여러개 두는 방식을 선택하는데,
이를 Set-Assosiative Cache 라고 합니다.
캐시 라인의 배치 - Set-Associative 방식 
이름에서 알 수 있듯, 라인을 여러개 합쳐서 Set 의 방식으로 만든것이 Set-Assosiative 방식 입니다.
예를 들면, 4-Way Set Assosiative 방식은 같은 인덱스를 가지는 캐시라인 4개가 하나의 Set를 이룹니다.
이렇게 되면, 인덱스 비트는 당연히 2비트가 줄어 들고, 태그 비트는 2비트가 늘어납니다.

 

 

위의 예시는 4-Way Set Assosiative 의 예시를 보여줍니다.
캐시메모리의 크기는 4KB이고 하나의 라인크기가 4바이트 이니까, 라인은 1024개가 있습니다.
같은 인덱스에 4개 까지 넣을 수 있으니, 256개의 세트를 만들 수 있습니다 세트를 인덱스로 사용하기 때문에,
인덱스 비트는 2개가 줄어들고, 태그 비트는 2비트가 늘어납니다.

인덱스 비트 길이를 유지하고, 인덱스 내에서 별도 2비트를 둬서 검색을 하면 안되냐? 사실 그거랑 똑같습니다.
검색을 위한 2비트는 그대로 씁니다.
히트 감지와 멀틱플렉서를 이용한 데이터 획득의 예시를 잘 보여주고 있습니다. 

캐시 라인의 교체 정책 - LRU
캐시는 메인메모리보다 훨씬 크기가 작은 메모리 입니다.
앞선 4-Way Assosiative 방식이 Conflict를 줄일 수 있지만,
메인 메모리는 크고, 캐시 메모리는 작습니다.
따라서 어찌 되었건 충돌은 일어날 수 밖에 없습니다.

캐시세트에 빈공간이 있다면, 값을 채우면 되지만, 충돌이 계속 일어난다면 기존의 라인을 
내쫓고 새로운 라인을 구성해야 합니다.

이러한 교체 정책에는 많은 방법이 있지만,
가장 널리 사용되는 방법인 Least Recently Used, LRU 방식을 소개하겠습니다.

이 방식은 가장 사용된 빈도수가 작은 라인을 밀어내는 방식입니다.
이 방식은 N-way assosiative 방식에서 카운터를 이용하면 간단한 방식으로 구현할 수 있습니다.
캐시 히트가 일어났을때 해당 라인의 카운터보다 큰 카운터 값을 가지는 라인이 있다면,
그런 라인들의 카운터값을 모두 1씩 감소 시킨 다음, 히트가 일어난 라인의 카운터를 N-1 로 바꿉니다.
즉, 먼저 히트되었던 라인들이 자리를 하나씩 비켜주고, 방금 히트된 라인이 가장 최근에 접근된 라인이 되는 것 입니다.

 

캐시 쓰기 시 정책

캐시 메모리에 변경(쓰기)이 발생하면, 하위계층의 캐시메모리 혹은 메인메모리에 동기화 되어야 합니다.
이미 가진 라인에 대한 쓰기 발생시, 캐시를 언제 동기화 하느냐에 따라서 Write-through 와 Write-back 두가지로 나눕니다.
또한 가지고 있지 않은 라인,
즉 미스 발생시 또한 규칙이 적용되어야 합니다 이 규칙에는 Write-Allocate / No-Write-Allocate 방식으로 나뉩니다.

Write-through 방식
캐시라인에 변경점이 발생했을 때에 그 즉시 이를 하위 계층의 캐시메모리 또는 메인 메모리에 반영하는 방식 입니다.

Write-back 방식
더티비트를 이용해서 변경점이 발생한 사실을 기록합니다.
그리고 캐시라인에서 제거될때 이를 하위 계층의 캐시메모리 또는 메인 메모리에 반영하는 방식입니다.

대부분의 캐시 메모리는 write-back 방식을 사용합니다.
허나 , L1 I$(L1 명령어 캐시) 의 경우에는 write-through 방식을 사용합니다.
프로그램의 명령어 코드는 보통 거의 수정이 일어나지 않기 때문입니다.

Write-allocate 방식
캐시 메모리에 새로 만들고, 기존것이 있다면 대체 합니다.

No-write-allocate
캐시 메모리에 쓰지 않고, 메인 메모리에 씁니다.

보통 이런 방식으로 조합을 합니다.
Write-back + Write-allocate (가장 많이 사용됨)
캐시 미스시 만들고, 캐시 메모리 내에서 지속적 업데이트 , 캐시 라인 교체시 메인 메모리에 쓴다.

Write-through + No-write-allocate
캐시 히트시에 메인메모리에 계속 지속적 업데이트, 캐시 미스시에도 메인메모리에 업데이트

 

멀티 레벨 캐시

 

거의 모든 프로세서는 캐시메모리를 L1,L2,L3 와 같이 계층을 두어서 사용합니다.
캐시 메모리의 크기가 증가하면 하드웨어의 복잡도 또한 올라가서,
캐시 히트시 데이터를 가져올때 레이턴시가 더 커지고,
교체 정책시에도 더 큰 비용이 발생합니다.

간단하게 생각해봐도, 캐시메모리의 크기가 커지면, 인덱스 비트의 크기 혹은 태그 비트의 크기가 커질 것 입니다.
태그 비트가 늘어나면, 당연히 비교 회로 또한 복잡해집니다.

또한 앞서 소개한 N-way Assosiative 방식을 예로 들면, 
N이 늘어나면 캐시 라인 교체시에도 카운터 값들을 더 비교해야하고
비교 연산에 있어서도 성능에서의 손해가 더 생길 수 밖에 없습니다. 

캐시가 여러 계층이 되면 캐시 메모리간 데이터의 중복 여부 또한 고려해 볼 문제입니다.
세가지 정책이 있습니다.

inclusive 캐시 정책의 경우에, 상위 계층 캐시에 데이터가 있다면
하위계층에도 반드시 있다는 것을 보장합니다.

exclusive 캐시 정책의 경우에는 상위 계층 캐시에 데이터가 있다면,
하위계층에는 반드시 없다는 것을 보장합니다.

non-inclusive 또는 non-exclusive 정책의 경우에는
상/하위 계층간의 데이터가 중복 될 수도, 중복 되지 않을 수도 있습니다.

 

캐시 미스

캐시미스의 종류에는 네가지가 있습니다.

콜드 미스(Cold Miss)
데이터를 최초로 읽을때 발생하는 캐시 미스입니다.
이름 그대로 캐시 워밍(cache warming) 되지 않았기 때문에 발생합니다.

충돌 미스(Conflict Miss)  
캐시의 연관도가 부족해 발생하는 캐시 미스입니다.
연관도를 높이면 어느 정도 까지는 회피가 가능하지만
결국 캐시메모리가 메인메모리보다 작기때문에, 완전히 피할 수는 없습니다.
또한, 앞서 서술했듯 레이턴시가 증가할 가능성이 있습니다.

용량 미스(Capacity Miss)
캐시의 용량이 부족해 발생하는 캐시 미스입니다.
간단히 생각하면 용량을 키우면 될 일이지만, 역시나 히트 레이턴시가 악화될 수 있습니다. 

코히런스 미스(Coherence Miss)
다른 프로세서에 의해서 캐시라인이 무효화 된 경우에 발생하는 캐시 미스입니다.

충돌 미스를 줄이기 위한 방법중 하나는 L1 희생자 캐시(victim cache) 입니다.
이 희생자 캐시는 아주 작은 연관 캐시로 쫓겨난 캐시를 잠시 보관하는 역할을 합니다.
완전 연관(Fully Associative) 방식 으로 구현되기 때문에, 비교 레이턴시가 비교적 낮아서
L2 검색전에 레이턴시를 줄여주는 효과가 있습니다.

멀티코어에서의 캐시메모리

 

 

 

 

L1 의 경우 명령어 캐시와 데이터 캐시가 나뉘어져 있고, L2는 Unified, L3도 Unified 입니다.
L1과 L2는 코어 독립적이고, L3 는 모든 코어가 이를 공유 합니다.

이 처럼 멀티코어 CPU에는 코어가 여러개 있고, 캐시메모리도 여러군데 있습니다.
여기서 여러가지의 문제가 발생하는데, 그 중 하나가 바로 메모리 일관성 문제 입니다.

대부분 L1 명령어 캐시를 제외하고는 Write-back 정책을 사용하는데,
생각해보면 최신값을 갱신하지 않으면 같은 주소에 접근하는 여러개의 코어가 다른 값을 보게 됩니다.
이에 대한 일관성을 보장할때 캐시 코히런스(coherence) 를 지원한다고 합니다.

이에 대한 해법중 하나가 무효화 프로토콜 입니다.
무효화 프로토콜은, 코어들 끼리 통신을 통해서 캐시라인을 동기화 하는 방식입니다.
MESI 프로토콜은, 대표적인 무효화 프로토콜 중 하나입니다.

한 코어가 그 데이터를 수정(write) 하면,
다른 코어들이 가진 캐시 라인은 무효화(invalidate) 되어야 합니다.
이를 위해 코어들은 버스(Bus)나 인터커넥트를 통해 서로 프로토콜 메시지를 주고받고, 
각 캐시 라인에 상태 플래그(MESI: Modified, Exclusive, Shared, Invalid)를 설정합니다.

Exclusive
이 코어만 값을 가진 상태입니다.
즉, 메인 메모리와 이 값은 동기화 된 상태입니다.

Shared
이 코어와 다른 어떤 코어가 값을 아는 상태입니다.

Invalid
값이 다른 코어로부터 수정된 상태입니다.
다른 코어가 값을 수정했고, Invalidate를 버스로 보내면,
받은 코어는 자신이 해당 라인을 가지고 있다면, (Shared) 이를 Invalid 상태로 바꾸게 됩니다

Modified
이 코어에서 이 값을 바꿨습니다.
따라서, 이 값은 메모리에 동기화 되어있지 않을 수 있습니다.

Shared 상태에서 Write를 할때는 Invalidate를 브로드캐스트 합니다.
Shared를 가진 모든 코어가 응답을 보내면, 나의 코어에서 Modified로 바꿉니다.
만약, 바꾸려는 값이 Shared가 아니라 Exclusive라면, 바로 Modified로 바꿔도 됩니다.

어떠한 값 100번지의 값을 코어 0가 메모리에서 읽어왔다고 하겠습니다.
이 상태에서 코어 0의 100번지에 대한 캐시라인은 Exclusive 상태입니다.

코어 0이 가지고 있는 100번지 값을 코어 1이 요청해서 이를 보내줬습니다.
코어 1은 받은 다음 Shared로 설정합니다.

코어 0은 자신이 준 다음 Shared로 설정합니다.
코어 0이 100번지 값을 수정하려고 합니다.

Invalidate 를 버스로 보냅니다.
이를 받은 코어 1은 자신의 100번지 를 Invalid로 바꿉니다.
이에 대한 응답을 받은 코어 0은 Modified로 바꿉니다.

코어 1은 다시 100번지의 값에 대해서 Read 요청을 보냅니다.
이를 받은 코어 0은 수정된 100번지의 값을 보내줍니다.
코어 0과 1의 100번지는 모두 Shared 상태로 바뀝니다.

 

캐시 친화적 코드 (Cache Friendly Code)

 

Spartial Locality를 이용한 예제입니다.

#include <Windows.h>
#include <iostream>
#pragma comment(lib,"winmm.lib")
 
constexpr int Ysize = 4096;
constexpr int Xsize = 4096;
 
 
int main()
{
	timeBeginPeriod(0);
 
	int Sum = 0;
 
	int* Arr = (int*)malloc(sizeof(int) * Xsize * Ysize);
 
	unsigned long S = timeGetTime();
 
	for (int i = 0; i < Ysize; ++i)
	for (int j = 0; j < Xsize; ++j)
	Sum += Arr[i * Xsize + j];
 
	unsigned long E = timeGetTime();
 
	std::cout << "X By Y Access : " << E - S << std::endl;
 
	S = timeGetTime();
 
	for (int j = 0; j < Xsize; ++j)
		for (int i = 0; i < Ysize; ++i)
			Sum += Arr[i * Xsize + j];
 
	E = timeGetTime();
 
	std::cout << "Y By X Access : " << E - S << std::endl;
 
 
 
	timeEndPeriod(0);
 
}

같은 라인내에 연속적으로 접근 할때에 더 이득을 볼 수 있습니다.

 

Temoral Locality를 이용하는 예제의 대표적인 것이 바로 행렬곱입니다.

 

#include <Windows.h>
#include <iostream>
#pragma comment(lib,"winmm.lib")
 
constexpr int Ysize = 1024;
constexpr int Xsize = 1024;
 
int main()
{
	timeBeginPeriod(0);
 
	int* ArrayA = (int*)malloc(sizeof(int) * Ysize * Xsize);
	int* ArrayB = (int*)malloc(sizeof(int) * Ysize * Xsize);
	int* ArrayC = (int*)malloc(sizeof(int) * Ysize * Xsize);
 
	memset(ArrayC, 0, sizeof(int) * Ysize * Xsize);
 
	unsigned long S = timeGetTime();
 
	for (int i = 0; i < Ysize; ++i)
	for (int j = 0; j < Xsize; ++j)
	for (int iter = 0; iter < Xsize; ++iter)
	ArrayC[i * Xsize + j] += ArrayA[i * Xsize + iter] * ArrayB[iter * Ysize + j];
		
	unsigned long E = timeGetTime();
	std::cout << "No Block Partition : " << E - S << std::endl;
 
	S = timeGetTime();
 
 
	//캐시라인의 크기가 64. 따라서 16의 크기로 행렬을 나눈다.
	//라인 단위로 나뉜 메모리에 접근해서 캐시히트를 유도한다.
	for (int i = 0; i < Ysize; i += 16)
	for (int j = 0; j < Xsize; j += 16)
	for (int InnerOffset = 0; InnerOffset < Xsize; InnerOffset += 16)
	for (int InnerY = i; InnerY < i + 16; ++InnerY)
	for (int InnerX = j; InnerX < j + 16; ++InnerX)
	for (int InnerIter = InnerOffset; InnerIter < InnerOffset + 16; ++InnerIter)
	ArrayC[InnerY * Xsize + InnerX] += ArrayA[InnerY * Xsize + InnerIter] * ArrayB[InnerIter * Xsize + InnerX];
 
	E = timeGetTime();
	
	std::cout << "Block Partition : " << E - S << std::endl;
 
	timeEndPeriod(0);
}

 

16으로 나눈 이유는 캐시라인의 크기가 64바이트이기 때문입니다.