[컴퓨터 밑바닥의 비밀] 5장. 캐시(Cache)

5. 작은 것으로 큰 성과 이루기, 캐시

 

5.1 캐시, 어디에나 존재하는 것.

 

[캐시의 탄생 배경]

 

시스템의 성능은 상대적으로 느린 쪽에 맞추어 제한된다.

CPU의 속도 >>>>> 메모리의 속도. 메모리는 CPU의 1/100 수준에 해당한다.

 

CPU와 메모리의 속도차로 인해 CPU가 메모리를 직접 읽고 쓰지 않도록 ‘캐시’가 개발되었다.

캐시에 최근에 메모리에서 얻은 데이터가 저장되며 CPU가 메모리에서 명령어와 데이터를 꺼내야 할 때 무조건 먼저 캐시에서 해당 내용을 찾는다.

[캐시의 물리적 형태]

 

 

x86과 같은 최신 CPU와 메모리 사이에는 실제로 3단계의 캐시가 추가되어 있다. L1 캐시, L2 캐시, L3 캐시.

 

L1 > L2 >> L3 순으로 속도가 빠르다.

각 계층의 크기는 다음 계층의 크기보다 작다.

[캐시의 문제]

 

1. 캐시 갱신

 

* 문제의 원인

캐시로 인해 CPU가 더이상 메모리와 직접 일하지 않게 되며 CPU는 캐시에 직접 기록을 할 수 있게 되었다. 이로 인해 캐시의 데이터는 갱신되었지만 메모리의 데이터는 아직 갱신되지 않는 ‘불일치 문제’가 발생할 수 있다.

 

* 해결방법

1) 캐시를 갱신할 때 메모리도 함께 갱신하는 ‘연속 기입’ 방법을 사용한다. (동기)

2) 캐시의 용량도 제한되어 있기에 용량이 부족하면 자주 사용하지 않는 데이터를 삭제하고 이를 메모리에도 갱신한다. ‘후기입 방식’ (비동기) 

2. 다중 코어 캐시의 일관성

 

* 문제의 원인

단일 CPU의 성능은 쉽게 향상되진 않지만 다중 코어로 숫자를 늘릴 수 있다.

각  CPU에는 캐시가 서로 존재한다. 즉, 이때도 갱신 문제가 발생한다.

 

* 해결방법

캐시 한 개에서 갱신된 변수가 다른 CPU 코어의 캐시에도 존재한다면 이 캐시도 함께 갱신한다. MESI 규칙.

[디스크의 캐시로 활용되는 메모리]

 

메모리 하단에는 ‘디스크’가 존재한다. 즉, 디스크에서 메모리로 데이터를 옮겨야 CPU가 메모리에서 데이터를 읽을 수 있다.

 

메모리와 디스크 사이에 캐시를 추가할 수도 있지만, 최신 운영 체제는 메모리의 일부를 디스크의 캐시로 사용한다.

[가상 메모리와 디스크]

 

1) 프로세스가 요청하는 메모리의 크기가 넘어도 괜찮다.

why? 메모리가 부족할 때, 메모리는 자주 사용하지 않는 메모리 데이터를 디스크에 기록하고 이 데이터가 차지하던 물리 메모리 공간을 해제한다. 그럼 다시 프로세스가 메모리를 요청할 수 있다.

 

2) 로컬 디스크는 원격의 분산 파일 시스템의 캐시로 사용된다.

대용량의 데이터를 저장할 때, 하나의 로컬 디스크로 부족하면 ‘분산 파일 시스템’을 사용한다. 로컬 디스크가 원격의 분산 파일 시스템에서 전송된 파일을 저장하면 네트워크를 통하지 않고 로컬 디스크에 직접 접근할 수 있다.

5.2 어떻게 캐시 친화적인 프로그램을 작성할까?

 

1. 프로그램 지역성의 원칙

1) 시간적 지역성: 프로그램이 메모리 조각에 접근한 후 이 조각을 여러번 자주 참조한다.

2) 공간적 지역성: 프로그램이 메모리 조각을 참조할 때 인접한 메모리도 참조한다.

 

2. 메모리 풀 사용

메모리를 동적으로 할당받으면 메모리 조각이 힙 영역 이곳저곳에 흩어져 있을 가능성이 높다. => ‘메모리 풀 기술’로 큰 메모리 조각을 미리 할당받으면 연속된 메모리 공간 안에서 공간적 지역성을 높일 수 있다.

 

3. 핫 데이터와 콜드 데이터의 분리

자주 사용되지 않는 변수는 cold data, 자주 사용되는 변수는 hot data라고 부른다. 콜드 데이터와 핫 데이터를 분리하면 더 높은 지역성을 얻을 수 있다.

 

4. 지역적 원칙 관점에서 보면 배열이 연결 리스트보다 좋다.

배열은 하나의 연속된 메모리 공간에 할당된다.

연결 리스트는 일반적으로 이곳저곳에 흩어져 있을 수 있다.

 

다만, 노드가 빈번하게 추가/삭제되는 경우라면 ‘연결 리스트’가 배열보다 우수할 수 있다. 노드의 추가/삭제에 드는 시간 복잡도는 O(1)이기 때문이다.

 

연결 리스트에서도 캐시 친화적임을 반영하고 싶다면 연결 리스트 생성시 ‘메모리 풀’에서 메모리를 요청하면 된다.

5.3 다중 스레드 성능 방해자

 

메모리 데이터가 캐시에 저장될 때 ‘캐시 라인’이라는 묶음 데이터가 저장된다.

캐시 라인은 보통 64Byte 크기 이고 캐시가 적중하지 못할 때 이 묶음 데이터가 캐시에 저장된다.

 

캐시의 묶음 데이터로 저장되며 다중 코어 캐시에서 ‘캐시 튕김’ or ‘캐시 핑퐁’ 문제가 발생한다.

 

1. 캐시 튕김 문제

CPU1의 캐시1에 a 변수를 쓸 때 CPU2의 캐시2에 a변수가 있다면 CPU2의 a변수를 무효화 시킨다.(캐시 튕김1)

반대로 CPU2의 캐시2에 a 변수를 사용할 때 CPU1의 캐시1의 a변수를 무효화한다.(캐시 튕김2)

 

즉, 빈번하게 캐시 일관성을 유지하면 캐시가 자신의 역할을 하지 못할 뿐 아니라 프로그램의 성능까지 저하시킬 수 있다.

 

 

2. 거짓 공유 문제

 

아래 두 프로그램을 통해 캐시 데이터 거짓 공유 문제를 알아보자.

 

1) 스레드 2개로 a변수와 b변수를 각각 5억 번 증가시킨다.

void add_a(){      for(int i = 0; i < 500000000; i++){           ++global_data.a;     } } void add_b(){      for(int i = 0; i < 500000000; i++){           ++global_data.b;     } } void run(){     thread t1 = thread(add_a);     thread t2 = thread(add_b);     t1.join();     t2.join(); }

 

2) 단일 스레드로 a변수와 b변수를 1씩 5억 번 증가시킨다.

void run(){      for(int i = 0; i < 500000000; i++){           ++global_data.a;     }      for(int i = 0; i < 500000000; i++){           ++global_data.b;     } }

 

1) 2) 프로그램의 실행시간을 비교해보자.

다중 스레드를 사용한 프로그램: 3초.

단일 스레드를 사용한 프로그램: 2초.

 

다중 스레드는 어떤 변수도 공유하지 않지만 이 두 변수가 동일한 캐시 라인(cache line)에 있기 때문이다. 즉, 계속 캐시 튕김이 발생하며 속도를 지연시키는 것이다.

 

해결방법은 아래와 같이 두 변수 사이에 캐시 라인크기만큼의 사용되지 않는 데이터를 채우는 것이다. 4*16 = 64 Byte.

struct data {      int a;      int arr[16];      int b; }

 

5.4 봉화희제후와 메모리 장벽

 

[비순차적 명령어 처리(OUt of Order Execution, OoOE)]

 

CPU는 반드시 엄격하게 프로그래머가 작성한 코드의 순서대로 기계 명령어를 실행하지 않는다. 

 

why? CPU와 메모리 사이의 속도 차이 때문.

CPU가 기계 명령어를 엄격한 순서대로 실행하면 명령어가 의존하는 피연산자를 기다리는 동안 파이프라인 내부에 ‘빈 공간’인 슬롯이 생긴다. 이걸 이미 준비 완료된 다른 명령어로 채우면 명령어의 실행 속도를 높일 수 있기 때문이다.

(***전후 관계의 두 명령어가 서로 어떤 의존 관계가 없을 때만. ***자기 자신 이외의 또 다른 코어가 해당 코어를 바라볼 때만)

 

1) 기계 명령어를 생성하는 단계: 컴파일 중에 명령어를 재정렬함.

2) CPU가 명령어를 실행하는 단계: 실행 중에 명령어가 비순차적으로 실행됨.

 

비순차적 명령어 처리 시, 캐시도 고려해야 한다.

 

캐시의 일관성을 유지하는 작업은 비교적 시간이 많이 걸린다. 캐시의 일관성 작업 전에 CPU는 반드시 대기상태를 중지해야 한다. 비순차적 명령어 처리를 수행하며 캐시의 일관성 작업을 최적화하기 위해 일부 시스템은 ‘저장 버퍼(store buffer)’ 등을 대기열에 추가한다.

즉, 저장버퍼에 기록함으로써 캐시가 갱신되기를 기다리지 않고 다음 명령어를 계속 실행할 수 있다.

[비순차적 실행 문제 해결 방법]

 

메모리 장벽(Memory Barrier) 기계 명령어를 통해 스레드의 CPU에 순차적으로 실행하라고 강제 명령을 내리자.

 

1) LoadLoad: CPU가 Load 명령어 실행 시, 다음에 오는 Load 명령어가 먼저 실행되지 않도록 방지.

2) StoreStore: CPU가 Store 명령어 실행 시 다음에 오는 Store 명령어가 먼저 실행되지 않도록 방지.

3) LoadStore:Load 명령어가 캐시에 적중하지 못할 때, 일부 CPU에서는 다음에 오는 Store 명령어를 먼저 실행할 수 있다. Load 명령어 다음의 Store 가 먼저 실행되지 않도록 방지.

4) StoreLaod: Store 중에 Load 작업을 먼저 수행할 수 없다. 동기 작업.

 

[마무으리]

잠금 없는 프로그래밍을 해야할 때만 명령어 재정렬에 신경쓰자.