캐시메모리와 Cache Friendly Code

1. 캐시메모리는 무엇인가?

 

캐시메모리의 핵심 개념은 locality이다.

레지스터에 가까운 지역에 전진기지를 만들어

그 안에 자주 사용하고(temporal locality), 인접한(spartial locality) 데이터를 보관하기 위해 고안되었다.

 

잘 알려져 있듯이 메인메모리보다 크기가 작다.

이 작은 꾸러미를 최대한 활용하기 위한 하드웨어 알고리즘은 지금도 개발되고 있다.

허나 이것은 어디까지나 한계가 있는 이야기이다.

전 지구상에서 지금도 개발되고 있는 모든 어플리케이션의 분기를 예측하는 것은 불가능에 가깝기 때문이다.

따라서 개발자 또한 어느정도는 캐시메모리를 이해하고 코드를 짜는 것이 최적화에 매우 유리하다고 할 수 있다.

 

찾는 데이터가 캐시메모리에 보관되어 있다면, 

캐시 히트 라고 한다.

찾는 데이터가 캐시메모리에 없다면 캐시 미스 이다.

이 경우 하위단의 캐시메모리로 건너가서 데이터를 찾는다.

L1,L2,L3 모두 가지고 있지 않다면 메인메모리로 가야한다.

 

캐시 미스의 종류에는 세가지가 있다.

 

Cold Miss

원하는 번지수의 데이터가 아예 없는 경우.

그니까 단 한번도 그 어드레스에 대한 액세스가 없었던 거다. 

 

Conflict Miss

캐시메모리는 메인메모리보다 크기가 작다.

그래서 당연히 모든 주소에 대한 데이터를 가지고 있을 수 없다.

필연적으로 캐시메모리의 같은 공간에 위치해야 하는 어드레스가 생긴다.

하나를 밀어내고 지금 원하는 값을 찾아와야 한다.

이게 Conflict Miss 이다.

 

Capacity Miss

Conflict Miss와 기존의 것을 밀어내야 하는 상황은 똑같다.

순차적으로 어드레스에 대해 접근한다고 하더라도 캐시 크기가 한정되어 있기 때문에

발생하는 상황이 Capacity Miss이다.

 

학술적으로 서술할때는 구분하기도 하지만 보통은

Cold Miss, Conflict Miss, Capacity Miss 모두 그냥 Cache Miss라고 부른다.

 

2. 캐시메모리의 설계 방식 - 태그,집합,라인

 

캐시메모리의 크기를 C(Cache의 C) 라고 하고,

캐시라인이 모인 일종의 집합의 개수를 S(Set의 S),

한 집합안에 캐시라인이 몇개가 있는가를 E(Line의 E),

그리고 마지막으로 각 캐시라인에 저장될 데이터 블럭(캐시데이터)의 크기를 B(Block의 B)라고 부른다.

이때에 C = S * E * B 가 성립하도록 S,E,B를 설정 한다. 

 

캐시메모리는 메인메모리보다 크기가 작다.

따라서 메인메모리로의 큰 어드레스가 들어오면, 각 비트를 쪼개서 이를 탐색한다.

태그 비트로 라인을 특정하고, 집합 비트로 집합을 특정한다

그리고 해당 블럭에서의 오프셋으로 라인내의블럭에서 데이터를 꺼내온다.

valid 비트는 해당 캐시라인이 빈 상태인지 아닌지를 나타내는 플래그 비트 이다.

 

3. Direct Mapped Cache vs E way Set Associative Cache

 

C = S * E * B에서, E의 크기를 어떻게 설정하느냐에 따라 갈린다.

 

E 를 1로 설정하면 Direct Mapped Cache이다.

E 가 2 이상이면 E way이다.

 

Direct Mapped Cache 방식부터 보도록하자.

 

(0과 7에서의 미스는 맨처음에 캐시에 올라가있지 않은 경우에 생긴 miss이다. 즉, cold miss)

S(집합의 개수)는 4, E(집합당 라인의 수)는 1,  B(라인당 바이트수)는 2이다.

집합의 수를 늘리는 대신 라인의 수가 줄어들어 라인 특정에 유리함을 보인다.

때문에 보폭이 작은 데이터 접근에 대해 매우 유리하다.

예를 들어 어드레스 0,1,2,3,4,5,6,7 을 순차적으로 접근한다면(보폭이 작은 경우) cold miss를 제외하고는

cache hit이다.

 

허나 set index만 합동이고, 태그가 다른경우를 반복적으로 접근하는 경우,

(예를 들어 0번지와 8번지, 1번지 9번지 같은 경우) 계속 해서 캐시미스가 나므로 이때는 불리하다.

 

E - way를 보도록 하자.

위 예시는 E 를 2로 설정했다.

집합의 숫자를 줄이고 라인의 숫자를 늘렸다.

이 경우 같은 집합내의 다른 태그를 가진 라인의 개수가 늘어났기 때문에,

보폭이 큰 데이터에 대한 캐시미스 확률이 낮아진다.

예를 들어 0번지와 8번지에 반복적으로 접근 하더라도, 태그특정이 가능하고,

캐시 미스는 일어나지 않는다.

허나 같은 집합이 나오는 빈도가 늘었으므로 매번 태그 값을 비교해야 하는 빈도수 또한 동시에 올라간다.

보폭이 작은 데이터에 대해서도 같은 집합내에서 검색을 한번 더 해야하기 때문에 다소 불리하다.

 

현대의 컴퓨터는 거의 대부분 Set Assoicative를 사용한다고 한다.

 

4. 캐시로부터의 write 정책

캐시메모리에 있는 값은 어디까지나 사본이다.

특정 어드레스에 대해 write 동작을 수행하려 할때,

캐시메모리에 해당 어드레스의 데이터가 있는 경우와 없는 경우에 각각 두가지의 선택지가 존재한다.

 

Cache Hit 시

 * Write-through - 캐시메모리에 변경된 내용을 메인 메모리에 곧바로 쓴다.

 * Write-back - 캐시 라인을 교체해야 할때에 메인메모리에 쓴다.

Cache Miss 시

* Write-allocate - 캐시 메모리에 쓴다. 기존것이 있다면 그건 밀려난다.

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

 

보통의 정책은 다음의 두가지 중 하나를 고려한다.

Write-back + Write-allocate

(캐시 미스시 만들고, 캐시 메모리 내에서 지속적 업데이트 , 캐시 라인 교체시 메인 메모리에 쓴다.) 

 

Write-through + No-write-allocate

(캐시 히트시에 메인메모리에 계속 지속적 업데이트, 캐시 미스시에도 메인메모리에 업데이트)  

 

전자의 경우를 더 많이 사용한다.

 

4.  Cache Friendly Code Example

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 < Xsize; ++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);

}

같은 라인 내의 연속된 메모리 영역에 순차적으로 접근하는 것이 훨씬 이득임을 확인 할 수 있다.

 

이번에는 temporal 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바이트이기 때문이다.

블럭을 나누고, 해당 라인에 대한 캐시 히트를 얻음으로 속도를 향상 시킬 수 있었다.