캐시(Cache)

 

메모리와 CPU, 컴퓨터 시스템의 두 핵심 구성 요소는 폰 노이만 구조 모델을 기반으로 상호 작용한다.

CPU의 기계 명령어와 데이터가 모두 메모리에 저장되어 있어야 하며, 레지스터가 존재하지만 레지스터의 용량은 극히 제한적이기 때문에 프로그램이 실행되는 동안 CPU는 메모리와 빈번하게 상호 작용을 해야 한다.

폰 노이만 구조

 

폰 노이만 구조를 단순하게 생각해보면, CPU가 직접 메모리를 읽고 쓰는 것처럼 보이지만, 현실의 컴퓨터는 이처럼 단순하게 작동되지는 않는다.

 

Why?

A. CPU와 메모리의 속도 차이!

시스템 성능은 느린 쪽에 맞추어 제한되므로, CPU가 아무리 빨라지더라도 메모리의 속도에 따라 컴퓨터 성능은 항상 제한적일 수 밖에 없다.

일반적으로 메모리의 속도는 CPU의 100분의 1에 불과하며, CPU가 메모리를 직접 읽고 쓴다면 CPU의 고속 처리 능력은 쓸모가 없어지기 때문이다.

 

그래서 현재의 CPU는 캐시(cache) 계층이 추가되었다.

---

캐시(Cache)

캐시란?

• 가격이 비싸다.
• 용량이 제한적이다.
• but, 접근 속도가 빠르다. CPU에 필적함

- CPU가 메모리를 직접 읽고 쓸 경우

 

- CPU와 메모리 사이에 캐시 계층이 추가될 경우

 

캐시 계층이 추가되었을 때, 캐시 안에는 최근에 메모리에서 얻은 데이터가 저장되며, CPU는 메모리에 접근하기 전에 캐시에서 해당 내용을 찾은 후 없을 때만 메모리에 접근한다.

캐시가 적중하면 메모리에 접근할 필요가 없어 CPU가 명령어를 실행하는 속도가 매우 빨라지며, 메모리와의 속도 차이를 보완할 수 있다.

---

실제 캐시 단계

일반적으로 최신 CPU(e.g. x86)와 메모리 사이에는 L1, L2, L3 세 단계의 캐시가 추가되어 있다.

L1 캐시의 접근 속도는 레지스터 접근 속도보다 약간 느리며, 캐시 단계에 따라 접근 속도는 낮아지지만 용량은 증가한다.

L1, L2, L3 캐시와 CPU 코어는 레지스터 칩 내에 묶여 패키징되어 있다.

CPU는 데이터를 찾을 때, 먼저 L1 캐시부터 차례로 살펴보며 캐시가 적중하는지 확인한다. 마지막 L3 캐시까지 적중하지 않으면 그 때, 메모리에 직접 접근한다.

---

캐시 추가의 비용, 대가

1. 캐시 갱신 동기화

캐시와 메모리의 데이터를 동기화해야 한다.

- 연속 기입(write-through) : 캐시를 갱신할 때 메모리도 함께 갱신
- 후기입(write-back) : 메모리 갱신 완료를 기다리지 않고 CPU가 다음 명령어를 실행. 캐시의 최신 데이터는 캐시 데이터가 제거될 때 수정 이력이 있다면 그 때 메모리에 갱신하는 방법으로 반영된다.

 

연속 기입 방식으로 데이터를 동기화시키려고 하면 동기화될 때까지 CPU가 대기해야 하는데, 이렇게 하면 메모리 접근 시간을 줄이는 목적이 사라진다. 이런 상황을 최적화하기 위해서 이 갱신 방식을 비동기 방식으로 처리해야 하며, 이 방식이 후기입 방식이다.

 

 

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

이 때, CPU가 코어 여러 개를 가지고 있다면?

각각의 코어에서는 서로 다른 스레드들이 실행되며, 이 스레드들이 모두 메모리 내 동일한 변수 x에 접근해야 한다고 하자.

변수의 초깃값이 2라고 가정하면

코어C1과 C2는 변수 x를 사용하기 위해 각각 메모리에 있는 변수 x의 값을 읽어 온다. (캐시에 아직 없으니까)

그 후 변수 x의 값은 대응하는 캐시에 갱신되어, C1캐시와 C2캐시는 모두 x=2를 캐시에 저장해 두게 된다.

여기서 코어C1에서 변수 x에 덧셈 연산을 수행하고, 이를 캐시에 반영한다면?

이후 메모리도 동기화되어 C1에서 수행된 연산의 결과값을 가지겠지만, 여전히 C2캐시에는 변수 x에 값 2가 있으므로 코어C2는 x 변수의 값을 2라고 읽어오게 될 것이다.

이렇게 다중 코어의 캐시에서 동일한 변수를 저장할 때, 불일치 문제가 발생할 수 있다.

이 문제를 해결하기 위해서는 캐시 하나에서 갱신되면 다른 코어의 캐시에도 있는지 확인하고, 있다면 해당 캐시도 갱신해야 한다. 최신 CPU에는 고전적인 MESI protocol과 같은 다중 코어 캐시의 일관성을 유지하는 규칙이 존재하지만,

이 일관성 유지가 빈번하게 발생하면 그로 인해 성능에 영향이 있을 수밖에 없다.

💬 MESI 프로토콜은 캐시 메모리의 일관성을 유지하기 위해서 별도의 플래그(flag)를 할당한 후 플래그의 상태를 통해 데이터의 유효성 여부를 판단하는 프로토콜이다. 멀티프로세서 시스템에서 캐시 메모리의 일관성을 유지하기 위해 메모리가 가질 수 있는 4가지 상태를 정의한다.

Modified(수정) 상태 : 데이터가 수정된 상태
Exclusive(배타) 상태 : 유일한 복사본이며, 주기억장치의 내용과 동일한 상태
Shared(공유) 상태 : 데이터가 두 개 이상의 프로세서 캐시에 적재되어 있는 상태
Invalid(무효) 상태 : 데이터가 다른 프로세스에 의해 수정되어 무효화된 상태

---

캐시의 마지막 단계, 디스크

마지막으로, 메모리 뒤에는 디스크가 있다.

우리는 파일 입출력을 할 때 디스크에서 파일을 읽어오는데, 메모리의 접근 속도가 CPU와 비교해서 느리다고 했지만 디스크와 비교하면 메모리는 디스크 탐색 속도보다 10만 배 가량 빠르다.

최신 운영 체제는 메모리를 디스크의 캐시로 사용한다.

(서버에서는 최근 메모리가 디스크를 대체하는 것이 대세😉 메모리가 대용량 대비 저렴해지고 있기 때문이다.)

 

 

가상 메모리와 디스크

모든 프로세스는 표준 크기의 자체적인 주소 공간을 가지고 있으며, 이 주소 공간의 크기는 물리 메모리와는 관련이 없어 물리 메모리의 크기를 초과할 수 있다.

시스템의 프로세스 N개가 실제 물리 메모리를 모두 사용하고 있을 때, 새로운 N+1번째 프로세스가 메모리를 요청한다면?

메모리는 디스크의 캐시로 쓸 수 있으며 이 때 디스크는 메모리의 '창고' 역할을 할 수 있다.

일부 프로세스에서 자주 사용하지 않은 메모리 데이터를 디스크에 기록하고, 여유 물리 메모리 공간을 확보한다.

(메모리 사용률이 매우 높을 경우, CPU가 프로그램을 실행할 때 디스크에도 접근해야 할 수 있다.)

 

CPU가 메모리를 사용할 때, 모두 가상 메모리 주소를 본다. 이 주소가 실제 물리 메모리 주소로 변환되면 캐시를 검색하기 시작하는 것.

 

 

분산 파일 시스템(distributed file system)

대용량 데이터의 저장이 장치 한 대로 부족하다면? 여러 대를 사용하면 된다.

사용자 장치는 분산 파일 시스템을 직접 장착할 수 있고, 로컬 디스크는 원격 분산 파일 시스템에서 전송된 파일을 저장한다. 이 때, 로컬 디스크를 원격 분산 파일 시스템의 캐시로 간주할 수 있다.

응답 속도를 더 높이기 위해 원격 분산 파일 시스템의 데이터를 데이터 흐름(data stream) 형태로 직접 로컬 시스템의 메모리로 끌어온다면, 이 경우에는 메모리를 원격 분산 파일 시스템의 캐시로 간주할 수 있다.

---

 

이제 우리의 저장 시스템은 다음과 같이 표현할 수 있다.

 

컴퓨터 저장 체계의 각 계층은 다음 계층에 대한 캐시 역할을 하며, 각 계층의 저장 용량은 반드시 다음 계층보다 작아야 한다. 또한, 전체 저장 체계가 최대 성능을 발휘하려면 프로그램이 캐시 친화적이어야 한다.

 

 

---

캐시 친화적인 프로그램을 작성하려면?

캐시 친화적 = 높은 캐시 적중률

 

프로그램 지역성의 원칙(locality of reference or principle of locality)

: 프로그램은 매우 규칙적으로 메모리에 접근한다.

 

- 시간적 지역성(temporal locality)

: 한 메모리 조각을 여러 번 반복하여 참조하는 것

: 참조 후 해당 메모리 조각이 캐시에 저장되므로 캐시 친화적

 

- 공간적 지역성(spatial locality)

: 한 메모리 조각을 참조한 후, 인접한 메모리도 참조하는 것

: 일반적으로 요청한 메모리의 인접 데이터도 함께 캐시에 저장되므로(캐시 라인) 캐시 친화적

프로그램의 공간적 지역성 원리에 따라, 프로그램이 어떤 데이터에 접근 시 다음에는 인접한 데이터에도 접근할 가능성이 높다.
따라서 캐시에는 접근한 데이터의 '묶음' 데이터를 저장하게 된다.
일반적으로 이 묶음 데이터는 64byte이며,
이 묶음 데이터를 캐시 라인(cache line)이라고 한다.

 

시간적 지역성과 공간적 지역성은 캐시 친화적이며, 이 프로그램 지역성 원칙에 따라 캐시 친화적인 프로그래밍 원칙이 몇 가지 있다.

---

캐시 친화적인 프로그래밍 원칙

• 메모리 풀 사용
• struct 구조체 재배치
• 핫 데이터와 콜드 데이터 분리
• 캐시 친화적인 데이터 구조 사용
• 다차원 배열 순회

 

---

캐시로 인한 다중 스레드 성능 문제

 

1. 캐시 튕김 문제

캐시 튕김 문제는 다중 스레드의 공유 리소스로 발생한다.

다음 두 가지 상황이 있다고 가정해보자.

A. 두 개의 스레드가 있고, 각각의 스레드는 전역 변수 a 값을 1씩 5억 번 증가시킨다.
B. 단일 스레드에서 전역 변수 a 값을 1씩 10억 번 증가시킨다.

 

이 두 프로그램의 실행 결과는, 예상 외로 단일 스레드인 B가 다중 스레드인 A보다 훨씬 빠르게 나온다.

이는 캐시 일관성 보장 방식 때문인데, 각각의 스레드가 하나의 전역 변수에 접근하면서 캐시의 일관성을 위해 다른 스레드의 캐시를 무효화해야 하기 때문이다.

첫번째 캐시 튕김 현상, 이제 번갈아가며 계속 캐시 튕김 현상이 일어날 것이다...

 

상대 스레드는 캐시가 무효화되어 있기 때문에, 메모리에서 직접 변수 a 값을 읽어와야 하며 이를 연산할 때 또다시 상대 스레드의 캐시를 무효화하고... (반복)

이렇게 캐시 튕김(cache line bouncing) 또는 캐시 핑퐁(cache ping-pong)이라는 문제가 발생하게 된다.

이 때문에 여러 스레드 사이에 데이터 공유를 피할 수 있다면 가능한 한 피해야 한다.

 

 

2. 거짓 공유 문제(false sharing)

그렇다면 다음 두 상황은 어떨까?

A.

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();
}

 

B.

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

 

A를 실행할 때, 두 스레드는 변수를 공유하지 않으므로 앞의 캐시 튕김 문제가 없을 것이라고 유추할 수 있지만, 실제로는 그렇지 않다.

캐시와 메모리는 캐시 라인 단위로 상호 작용하므로, a 변수에 접근할 때 캐시가 적중하지 않으면 인접한 b 변수도 동일한 캐시 라인에 위치하여 이 두 변수 a, b는 동일한 캐시 라인에 있을 가능성이 매우 높다.

이를 개선하는 방법은 간단한 예로, 동일한 캐시 라인에 위치하지 않도록 두 변수 사이에 사용되지 않을 데이터를 크기에 맞게 채울 수도 있고, 변수 순서를 조정할 수도 있다.

 

 

이를 토대로 알 수 있듯이, 다중 스레드 프로그램에서 성능 병목 현상이 일어나고 다른 원인을 찾을 수 없다면, 캐시 튕김 문제가 있는지 고려해볼 수 있다. 보기에는 간단해 보이는 캐시가 적지 않은 영향을 미칠 수 있기 때문이다.

 

---

메모리 장벽(memory barrier)

건너뛰고 싶다...

 

명령어의 비순차적 실행: 컴파일러와 OoOE

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

 

성능 향상의 이유 때문인데, 명령어의 비순차적 실행은 다음과 같은 단계를 거친다.

1. 기계 명령어 생성 - 컴파일 중에 명령어를 재정렬
2. CPU가 명령어를 실행 - 실행 중에 명령어가 비순차적으로 실행됨

실제 CPU의 작업 과정에서는,

가져온 기계 명령어 실행에 필요한 피연산자가 아직 준비되지 않은 경우 다른 준비 완료된 명령어가 먼저 실행 단계에 들어간다. 이 실행 결과는 대기열에 넣고 이전 명령어의 실행 결과가 기록될 때까지 기다렸다가 기록된다.(원래 실행 순서를 유효하게 만들기 위해)

 

이 과정에서 명령어 실행은 엄격한 순서대로 진행되지 않음을 알 수 있으며, 파이프라인 내부에서 피연산자를 기다리는 동안 생기는 빈 공간(slot)을 준비 완료된 다른 명령어로 채우며 명령어의 실행 속도를 끌어올린다.

이를 비순차적 명령어 처리(Out of Order Execution, OoOE)라고 한다.

 

 

캐시 계층을 포함하고 있는 시스템은 모두 어떻게 캐시를 갱신하고, 어떻게 캐시의 일관성을 유지시키느냐 하는 문제에 마주치게 된다.

일부 시스템은 저장 버퍼(store buffer) 대기열을 추가하여 기록 작업을 하고, 캐시를 즉시 갱신시키지 않고 CPU가 다음 명령어를 계속 실행할 수 있도록 한다.

 

기록 작업은 비동기 과정이며, CPU는 기록 작업이 실제로 캐시와 메모리를 갱신하는 것을 기다리지 않고 다음 명령어를 실행할 수 있다.

코어 A의 명령어 1의 기록 작업이 저장 버퍼에만 있고 캐시에 갱신되지 않았을 때, 다음 명령어 2를 실행하고 해당 명령어 2의 실행의 결과를 다른 코어 B가 인지하는 시점에 명령어 1의 작업은 이루어지지 않은 것처럼 보일 수 있다는 것이다.

(코어 A는 1,2,3 순서로 실행했지만, 다른 코어 B에서 볼 때는 1,3,2 순서로 실행된 것처럼 보일 수 있다.)

 

단일 스레드 내에서는 이런 비순차적 실행을 볼 수 없으며, 다른 스레드도 해당 공유 데이터에 접근해야만 볼 수 있다.

일부 시스템은 이 동작을 저장 버퍼를 통해서 하지만, CPU 유형에 따라 각기의 최적화 방법이 있을 수 있으며 비순차적 실행이 불가능한 CPU도 있다. 

 

대부분의 프로그래밍 언어에서 이런 차이를 메꿔 주므로 보통은 신경 쓸 필요가 없지만, 만일 잠금 없는 프로그래밍(lock-free programming)을 하고 있다면 이 문제를 신경써야만 한다.

 

---

메모리 장벽(memory barrier)

메모리 장벽은 특정 코어가 비순차적 실행을 해도, 다른 코어가 보았을 때 순차적으로 보이도록 하는 것이다.

메모리 작업은 읽기(Load)와 쓰기(Store) 단 두 가지 유형의 작업만 있으며, 이에 따라 메모리 장벽에는 네 가지 유형이 있다.

• LoadLoad
  • CPU가 Load 명령어를 실행할 때 다음에 오는 Load 명령어가 먼저 실행되는 것을 방지
  • 변수에 저장되어 있던 '예전 값'을 읽지 않도록 보장
• StoreStore
  • CPU가 Store 명령어를 실행할 때 다음에 오는 Store 명령어가 먼저 실행되는 것을 방지
  • 다른 코어에서 볼 때 변수의 갱신 순서가 보장됨
  • 순서만 보장되지, 읽어온 값이 최신 값이라는 보장은 없음
• LoadStore
  • CPU가 Load 명령어를 실행할 때 다음에 오는 Store 명령어가 먼저 실행되는 것을 방지
  • 특정 쓰기 동작이 읽기 신호에 따라 실행되어야 할 경우, 이 장벽으로 실행 순서를 보장함
• StoreLoad
  • CPU가 Store 명령어를 실행할 때 다음에 오는 Load 명령어가 먼저 실행되는 것을 방지
  • 네 가지 메모리 장벽 중 가장 무겁다.
  • 쓰기 작업이 얼마나 걸리든 유휴 시간 동안 다음의 읽기 작업을 미리 실행할 수 없다.
  • 읽은 값이 최신 값이라는 것을 보장
  • 동기 작업

---

획득-해제 의미론

 

획득 의미론: LoadLoad + LoadStore

 

해제 의미론: StoreStore + LoadStore

 

 

모든 유형의 CPU에 명령어 재정렬이 있는 것은 아니며,

명령어 재정렬 유형의 포함 갯수에 따라 약한 메모리 모델, 강한 메모리 모델로 나눌 수 있다.

(강한 메모리 모델 중 x86 플랫폼은 StoreLoad 재정렬 하나만 있는데, 이것은 자체적인 획득-해제 의미론이 있다는 이야기)

 

---

잠금 프로그래밍과 잠금 없는 프로그래밍

잠금 없는 프로그래밍은 운영 체제의 순서 스케줄링에 상관없이 무조건 앞으로 나아갈 수 있는 스레드 하나가 확보된다.

잠금 없는 프로그래밍을 해야 할 때만 명령어 재정렬에 신경 쓰면 되며, 공유 변수가 잠금 보호 없이 여러 스레드에서 사용될 경우 문제가 발생한다.

 

(시스템의 다중 스레드 프로그래밍에서는 일반적으로 상호 배제, 스핀 잠금 등으로 잠금이 사용된다.)