운영체제 - 컴퓨터 구조 원리 : 캐시

📒 캐시

📌 캐시

• CPU는 데이터를 꺼내(전송)와 연산하는데, 데이터 전송 비용이 CPU 연산 비용에 비해 어마어마하게 크다.
• 매번 데이터가 필요할 때마다 RAM에 접근하여 데이터를 꺼내 쓰는 것은 올바른 방법이 아니다.
• 컴퓨터 설계자들은 '캐시'라는 것을 도입하였다. (임시 저장소)
• CPU 내부에는 '코어'가 있고, '코어'는 'ALU(연산)'와 '캐시 장치'가 들어있다.
• 캐시는 단계별로 레지스터, L1 캐시, L2 캐시로 구성되어 있고, 피라미드 형식으로 이루어져 있다.
• 위쪽으로 갈수록 용량이 작은 대신 아주 빠르게 접근할 수 있다. 내려갈수록 용량이 커지고 비용도 커지게 된다.
• 캐시를 모두 탐색한 후 데이터가 없다면 RAM(메인 메모리)에서 데이터를 꺼내오게 된다.
• 꺼내온 데이터는 이후에 사용될 수 있기 때문에 케시에 저장해 놓게 된다.
  
  

요약

• 캐시 메모리에서 해당 주소의 값을 가졌는지 탐색 -> 알고 있다면 캐시에서 데이터 추출, 없다면 RAM에서 추출
• 캐시 용량 자체가 크지 않기 때문에 캐시 용량이 모두 차게 된다면 제일 오래되고 사용 빈도가 떨어지는 데이터는 패기하고 새로운 데이터로 덮어씌워지게 된다.
  
  

📌 캐시 철학

• 1) Temporal Locality
  • 시간상으로 보면 방금 주문한 테이블에서 추가 주문이 나올 확률이 높다.
  • 방금 주문한 걸 메모해 놓으면 편하지 않을까?
• 2) Spatial Locality
  • 공간적으로 보면, 방금 주문한 사람 근처에 있는 사람이 추가 주문을 할 확률이 높다.
  • 방금 주문한 사람과 합석하고 있는 사람들의 주문 목록도 메모해 놓으면 편하지 않을까?
• 가장 최근, 이미 접근했던 데이터 바로 옆에 데이터에 접근할 확률이 높다.
  
  

예제

#include "pch.h"
#include "CorePch.h"
#include <atomic>
#include <iostream>
#include <mutex>
#include <thread>
#include <windows.h>

int32 buffer[10000][10000];

int main()
{
	memset(buffer, 0, sizeof(buffer));

	{
		uint64 start = GetTickCount64(); // windows.h

		int64 sum = 0;

		for (int32 i = 0; i < 10000; i++)
		{
			for (int32 j = 0; j < 10000; j++)
			{
				sum += buffer[i][j];
			}
		}
		uint64 end = GetTickCount64();
		cout << "Elapsed Tick" << (end - start) << endl;
	}

	{
		uint64 start = GetTickCount64();
		int64 sum = 0;
		for (int32 i = 0; i < 10000; i++)
		{
			for (int32 j = 0; j < 10000; j++)
			{
				sum += buffer[j][i];
			}
		}
		uint64 end = GetTickCount64();
		cout << "Elapsed Tick" << (end - start) << endl;
	}
}

Output:
Elapsed Tick266
Elapsed Tick1125

• 메모리 구조 예시 : [][][][][][][][][][][][][][][][][][][][]
• 인접한 데이터가 곧 활용될 가능성이 높다고 판단하여 인접한 블록 단위로 데이터를 가져와 캐시에 저장한다.
• 예제에서 첫 번째 2중 for 문은 j가 하나씩 증가할 때는 순차적으로 메모리를 옮기게 된다.
• 다음 블록을 검색할 때 해당 블록의 데이터가 캐시에 있는지 검사하게 되는데, 위에서 말했듯이 인접한 데이터를 같이 가져왔기 때문에 존재할 확률이 높다. (이미 캐시에 있는 것을 '캐시 히트'라 한다.)
• j가 순차적으로 증가하게 된다면 인접한 데이터를 계속 검색하며 나아가기 때문에 캐시 히트가 연속으로 발생하게 되어 속도 측면에서 이득을 볼 수 있다.
• 그런데 아래 2중 for 문은 열을 i로 올리고 있다.
• 이렇게 되면 메모리 구조상 띄엄띄엄 검색되는 구조이기 때문에 캐시 히트가 발생할 확률이 낮다.
• 캐시 히트가 안 되면 RAM까지 가서 데이터를 가져오기 때문에 캐시 히트가 안 되는 만큼 속도 측면에서 손해가 크다.