Thread_10_C++ Cache
1. CPU 용어 정리
Register
CPU 내부에 존재하는 가장 작고 빠른 메모리
해당 메모리에서 값을 가져오고 ALU에서 계산을 실행한다
피연산자 또는 연산의 결과가 저장됨
데이터들은 Cache에서 가져옴
ALU(Arithmetic Logic Unit)
산술 및 논리 연산을 실행(덧셈, 뺄셈, AND, OR, NOT…)
실질적으로 CPU의 연산을 이곳에서 실행
CU(Control Unit)
명령어 해독
레지스터와 ALU의 명령 흐름 제어
BUS Interface
CPU와 RAM을 이어주는 데이터 통로
Cache
CPU와 RAM 사이에 있는 메모리
CPU의 연산속도와 RAM의 처리속도의 차이가 많이 나기 때문에 도입
RAM의 데이터들이 Cache에 옮겨지고 Cache에 있는 데이터들로 연산을 실행
따라서 Cache에 데이터가 있는지 없는지가 성능에 영향을 끼친다
Cache Hit Rate라고 해서 캐시적중률이라고 함
Cache의 3종류
- L1 : 가장 빠른 Cache 메모리, CPU 코어 안에 존재
- L2 : L1 Cache에서 miss가 발생했을 때 사용, 코어 내부 또는 외부에 존재
- L3 : 코어 외부에 존재해서 각 코어가 공유 즉, L1, L2는 코어별로 따로 있지만 L3는 모든 코어가 공유
2. Cache Hit Rate
Cache는 2가지의 특징을 가지고 있다
- 공간 지역성(Spatial Locality) : 한번 참조한 위치 근처에 있는 데이터를 참조할 확률이 높다
- 시간 지역성(Temporal locality) : 한번 참조한 데이터를 가까운 시간안에 또 참조할 확률이 높다
따라서 이 2가지의 지역성을 지켜서 프로그래밍하는 것이 최적화에 많은 도움이 된다
공간지역성 예시
#include <iostream>
#include "windows.h"
using namespace std;
int buffer[10000][10000] = { {0,} , };
int main()
{
//메모리 순차접근 -> cache hit rate가 높다
{
__int64 start = GetTickCount64();
__int64 sum = 0;
for (int i = 0; i < 10000; ++i)
{
for (int j = 0; j < 10000; ++j)
sum += buffer[i][j];
}
__int64 endt = GetTickCount64();
std::cout << endt - start << std::endl;
}
//메모리 무작위 접근 -> cache hit rate가 낮다
{
__int64 start = GetTickCount64();
__int64 sum = 0;
for (int i = 0; i < 10000; ++i)
{
for (int j = 0; j < 10000; ++j)
sum += buffer[j][i];
}
__int64 endt = GetTickCount64();
std::cout << endt - start << std::endl;
}
return 0;
}
2차원 배열을 선언해도 메모리상에는 1차원으로 잡힌다.
개념적으로 생각하기 편하게 2차원으로 생각하는 것
2차원 배열의 메모리 순서
buffer[0][0] buffer[0][1] buffer[0][2] buffer[0][3] buffer[0][4] ...buffer[1][0] buffer[1][1] ...
1번째가 더 빠른 이유?
1번째 방식대로 하면 0번, 1번, 2번… 순으로 index를 참조하지만 2번째 방식대로 하게 되면 0번 index를 참고했다가 10000 번 index를 참조하고 20000번 index를 참조하는 식으로 하게 된다 즉, 공간지역성 측면에서 2번째가 불리하다
시간지역성 예시
#include <iostream>
#include "windows.h"
using namespace std;
int dataArr[100000] = {0,};
int main()
{
//한 공간을 10000번씩 참조
{
__int64 start = GetTickCount64();
__int64 sum = 0;
for (int i = 0; i < 100000; ++i)
{
for (int j = 0; j < 100000; ++j)
sum += dataArr[i];
}
__int64 endt = GetTickCount64();
std::cout << endt - start << std::endl;
}
//10000개의 공간을 순차참조
{
__int64 start = GetTickCount64();
__int64 sum = 0;
for (int i = 0; i < 100000; ++i)
{
for (int j = 0; j < 100000; ++j)
sum += dataArr[j];
}
__int64 endt = GetTickCount64();
std::cout << endt - start << std::endl;
}
return 0;
}
1번째가 더 빠른 이유?
첫번째의 경우 한 공간을 10000번 참조한 다음 다음 공간으로 넘어간다. 즉, cache에 한번 올려놨던 데이터 공간을 계속 사용할 수 있다
따라서 빠르게 계속 참조가 가능하다
두번째의 경우 1KB Cache라고 한다면 256(1KB = 1024Byte = int256개)번을 진행하게 되면 첫번째 참조했던 Cache는 사라지게 된다
따라서 Cache miss가 발생하고 이로인해서 성능이 첫번째보다 덜 나오는 것
참조한지 얼마되지 않은 부분을 다시 참조하는 측면에서 봤을 때 시간지역성으로 볼 수 있다
3. Cache Visibility(가시성)
Thread 는 일반적인 상황에서 Core를 하나씩 점유한다
또한 Cache글을 참고했을 때 CPU Core당 Cache를 하나씩 가지고 있다
이렇게 되면 발생하는 현상이
Thread A와 Thread B가 동시에 구동된다고 가정했을 때
A cache와 B cache가 같은 변수에 접근했지만 그 값이 서로 다를 수도 있다!!!
이러한 현상을 cache 가시성이라고 함
4. 코드 재배치
컴파일러는 코드를 컴파일할 때 코드의 순서를 임의로 재배치 할 수 있다
해당 코드를 컴파일 하면
int a = 0;
int b = 0;
void foo()
{
a = b + 1;
b = 1;
}
다음과 같이 나오는데 같은 색깔라인을 그대로 매칭시켜놓은 것이다
즉, 컴파일러는 코드 최적화를 위해서 코드의 순서를 재배치 할 수 있다
왜 재배치가 일어날까?
CPU의 작업 스케쥴링을 최적화 하기 위해서 여러개의 작업을 동시에 실행하는데 이를 CPU 파이프라이닝(Pipelining)이라고 한다. 이 CPU 파이프라이닝을 효율적으로 진행하기 위해서 컴파일러는 코드 재배치를 수행하는 것이다
5. 문제점
Cache 가시성과 컴파일러 코드 재배치로 인해서 다음과 같은 현상이 발생할 수 있다
#include <iostream>
#include <thread>
#include <mutex>
#include <chrono>
#include <future>
#include "windows.h"
using namespace std;
int x = 0;
int y = 0;
int r1 = 0;
int r2 = 0;
volatile bool ready;
void Thread_1()
{
while (!ready) //딜레이를 위한 더미코드
{
volatile int i = 39;
i += 10;
}
y = 1;
r1 = x;
}
void Thread_2()
{
while (!ready) //딜레이를 위한 더미코드
{
volatile int i = 39;
i += 10;
}
x = 1;
r2 = y;
}
int main()
{
int count = 0;
while (true)
{
ready = false;
count++;
x = y = r1 = r2 = 0; //0으로 초기화
thread t1(Thread_1); //Thread_1 시작
thread t2(Thread_2); //Thread_2 시작
ready = true; //딜레이 해제
t1.join();
t2.join();
if (r1 == 0 && r2 == 0) //해당 부분으로 빠지는 현상이 발생
break;
}
std::cout << count << std::endl;
return 0;
}
main함수의 break 문으로 빠지는 현상이 발생
코드설명
코드재배치와 Cache 가시성 때문에 순서가 꼬이면
r1과 r2가 동시에 0인 상황이 발생할 수 있다
댓글남기기