캐시(Cache)(feat. Hit Rate, 메모리 계층구조, Locality)

안녕하세요. 

오늘은 컴퓨터의 메모리 중 캐시에 대해서 알아보겠습니다.

앤트맨의 딸 캐시

이 캐시는 아니구요.

 

시작해보겠습니다.

 

---

컴퓨터의 메모리계층구조

컴퓨터에는 다양한 저장장치가 있습니다.

SSD, HDD, RAM(일반적으로 메모리라고 하면 RAM을 뜻합니다.), 캐시, 레지스터 등등

메모리 계층구조

이렇게 저장장치들이 다양하게 나뉘게 된 이유는

이러한 저장장치들의 특징이 각기 다르기 때문입니다.

 

컴퓨터는 기본적으로 CPU가 연산을 수행합니다.

CPU는 연산에 필요한 데이터를 저장장치로부터 가지고 와서 작업을 하는데요.

 

이때 필요한 데이터가 있는 저장장치가 CPU와 가까울수록 효율이 높아집니다.

가깝다는 말은, CPU가 작업에 필요한 데이터를 꺼내오는데에 걸리는 시간이 적다는 뜻입니다.

 

CPU는 컴퓨터에서 가장 빠른 부품입니다.

그에 반해 저장장치들은 CPU보다 느립니다.

 

계층에 따라서 간단히 비교해보자면

• 레지스터 : CPU내부에 존재합니다. 1clock cycle안에 접근 가능합니다.
• Cache 
  • L1 Cache : 1~5clock cycle안에 접근이 가능합니다.
  • L2 Cache : 7~15clock cycle안에 접근이 가능합니다.
  • L3 Cache : 40~50clock cycle안에 접근이 가능합니다.
• RAM : 100clock cycle정도에 접근이 가능합니다.
• SSD : 수~수십 마이크로초
• HDD : 수십 밀리초

이렇게 계층이 낮아질수록, CPU에서 접근하는데에 걸리는 시간이 길어진다는 것을 알 수 있습니다.

이렇게 길어지면 컴퓨터가 너무 느려지기 때문에 접근 빈도는 계층이 낮아질수록 적어집니다.

 

하지만, 단점만 있는 건 아닙니다.

속도가 빠를수록 비싸고 저장공간이 작습니다.

속도가 느리다면, 가격이 싸고, 저장공간이 큽니다.

 

	접근 빈도	속도	가격(단위 용량당 가격)	용량
레지스터	가장 많음	가장 빠름	가장비쌈	가장 작음
캐시	많음	빠름	비쌈	작음
메모리	적음	느림	쌈	큼
HDD, SDD	가장 적음	가장느림	가장 쌈	가장 큼

 

여튼...

핵심은 CPU가 작업에 필요한 데이터를 가져오는데 걸리는 시간은

CPU의 속도를 따라가지 못한다는 것입니다.

 

그래도 최대한 CPU의 효율을 극대화하고, 작업시간을 최소화하기 위해서 만든 것이 

오늘의 주제인 캐시라고 할 수 있습니다.

 

---

캐시 사용의 목적

캐시를 사용하는 목적은

CPU가 데이터를 가지러 RAM이나 HDD로 가는 횟수를 최소화하여,

CPU가 노는 시간을 줄이는 것에 있습니다.

 

데이터를 가지러 RAM이나 HDD에 가면 그 동안 CPU는 놀게되니까요.

 

---

Hit Rate

CPU가 원하는 데이터가 캐시에 존재하는 경우를 Hit라고 합니다.

그리고, CPU가 원하는 데이터를 캐시에서 찾은 확률을 Hit Rate라고 합니다.

 

그러면 Hit Rate를 높이기 위해서는 어떻게 해야할까요?

 

---

캐시 설계의 2가지 고려사항

캐시가 동작하는 구조는 기본적으로 메모리에서 데이터를 블럭단위로 가져오는 것입니다.

 

그러니까 CPU가 요청한 데이터가 캐시에 없었다면, 메모리에 가서 가져와야 하는데

이 때 필요로하는 데이터 딱 하나만 가져오는 것이 아니라

CPU가 또 필요로 하겠구나~ 하는 데이터를 같이 가져오는 것이죠.

 

그러면 같이 가져오는 데이터를 선정하는 기준에 대해서 알아보겠습니다.

 

1. Temporal Locality

'시간적'으로 최근에 사용한 주소값은 또 사용할 가능성이 높다고 생각하는 것입니다.

예를 들면 for문으로 loop를 돌 때 index로 사용하는 i, j는 for문을 도는 동안 계속 사용하는 것처럼요.

 

2. Spatial Locality

'공간적'으로 최근에 사용한 주소값 부근의 데이터는 사용할 가능성이 높다고 생각하는 것입니다.

대표적으로 배열이 있겠습니다. 

 

2차원 배열의 경우에는 개념적으로는 2차원이지만, 실제로는 1차원 배열처럼 구성됩니다.

1행의 마지막 원소의 주소값 뒤에 바로 2행의 첫 원소의 주소가 나옵니다.

 

---

L1, L2, L3 Cache

앞서 본 메모리 계층 구조처럼 캐시도 계층이 있습니다.

L1 캐시는 CPU Core와 가장 가까이 위치합니다. 그래서 속도도 가장 빠르지만, 크기는 작습니다.

L2 캐시는 L1캐시보다 조금 멀리 위치합니다. 크기는 조금 더 크구요.

L3 캐시는 L2캐시보다 멀리 위치합니다. 그리고 L1, L2캐시는 CPU의 각 코어마다 하나씩 존재했다면, 

L3 캐시는 모든 코어가 공유하며 사용하는 공간입니다.

 

아래의 사진을 보면 이해가 빠를 것 같습니다.

CPU L1, L2, L3 Cache

 

---

간단한 실습

캐시와 관련된 간단한 실습을 해보겠습니다.

 

앞서 2차원 배열의 경우, 행우선저장 방식으로 저장된다고 말씀 드렸습니다.

 

CPU가 2차원 배열을 이용해서 연산을 하려고 한다고 가정해보겠습니다.

처음에는 당연히 Cache Hit가 일어나지 않습니다.

메모리에 가서 데이터를 가져와야합니다.

 

2차원배열의 경우 행우선 저장방식으로 저장되어있기에

메모리에서 캐시로 데이터를 가져올 때 같은 행에 있는 데이터는 같이 가져올 가능성이 큽니다.

 

따라서,

CPU가 행우선 방식으로 2차원 배열에 대해서 작업을 한다면 그 때 걸리는 시간은

CPU가 열우선 방식으로 2차원 배열에 대해 작업하는 시간보다 짧을 것으로 예상됩니다.

 

이것을 코드로 구현해보겠습니다.

 

int buffer[10000][10000];

int main()
{
	//행우선 접근
	{
		unsigned int start = GetTickCount64();
		__int64 sum = 0;

		for (int i = 0; i < 10000; i++)
			for (int j = 0; j < 10000; j++)
				sum += buffer[i][j];

		__int64 end = GetTickCount64();
		cout << "(행우선 접근) 소요 Tick : " << (end - start) << endl;
	}

	//열우선 접근
	{
		unsigned int start = GetTickCount64();
		__int64 sum = 0;

		for (int j = 0; j < 10000; j++)
			for (int i = 0; i < 10000; i++)
				sum += buffer[i][j];

		__int64 end = GetTickCount64();
		cout << "(열우선접근) 소요 Tick : " << (end - start) << endl;
	}
}

 

• 참고 : GetTickCount64()는 윈도우가 부팅되는 순간부터 틱을 카운트 한다. 1ms마다 1이 카운트된다 1초에 1000이 카운트 된다. 따라서 시작할 때 TickCount에서 끝났을 때 TickCount를 빼면 작업하는데에 걸리는 시간이 나온다.

 

실행을 해보면, 열우선접근시에 소요되는 TickCount가 더 크다는 것을 알 수 있다.

이를 통해서

1. 열우선접근 방법이 행우선 접근 방법보다 느리구나
2. 캐시 Hit Rate가 더 낮아서 그럴 것 같구나.
3. 캐시는 행단위로 데이터를 메모리에서 가져오는구나
4. 그래서 열우선접근으로 하면 캐시 Hit Rate가 낮아지는구나

하고 추측해볼 수 있다.