공유 메모리·NUMA·일관성

여러 코어가 같은 합계 변수를 읽고 각자 1씩 더할 때, 메모리가 하나이니 당연히 안전하다고 생각하기 쉽습니다. 하지만 데이터가 메모리의 어디에 있는지, 각 코어의 캐시에 복사본이 어떻게 남는지, 여러 읽기와 쓰기가 어떤 순서로 보이는지는 서로 다른 문제이고, 각각 다른 규칙이 필요합니다. 이 글에서는 병렬처리와 Flynn 분류의 멀티코어가 메모리를 함께 쓸 때 생기는 이 문제들을 하나씩 나누어 봅니다.

공유 메모리와 접근 거리

공유 메모리(shared memory)는 여러 처리 장치가 같은 주소 공간을 써서, 같은 주소로 같은 데이터에 접근할 수 있는 구조입니다. 어느 메모리에 접근하든 비용이 같다고 보는 모델을 UMA(uniform memory access)라고 합니다. 그런데 코어가 많아지면 모든 코어를 모든 메모리에 같은 거리로 잇기 어려워서, 코어와 메모리를 여러 묶음, 곧 노드로 나누고 노드끼리를 연결합니다. 그러면 자기 노드의 메모리에는 빨리, 다른 노드의 메모리에는 느리게 접근하게 되는데, 이것을 NUMA(non-uniform memory access)라고 합니다.

그림처럼 코어 A는 메모리 A와 메모리 B를 모두 같은 주소 공간에서 쓰지만, 메모리 A는 로컬로, 메모리 B는 원격으로 접근합니다. 예를 들어 로컬 접근이 80 ns, 원격 접근이 140 ns이고 접근의 30%가 원격이라면 평균은 0.7 × 80 + 0.3 × 140 = 98 ns입니다. 그래서 NUMA 시스템에서는 작업을 실행하는 코어 가까이에 그 작업의 데이터를 두는 것이 성능에 중요합니다.

노드마다 자기 메모리를 따로 두고, 다른 노드의 데이터가 필요하면 메시지를 보내 주고받는 구조는 분산 메모리(distributed memory)라고 합니다. 여러 컴퓨터를 네트워크로 묶은 클러스터가 그 예이며, 같은 주소로 다른 노드의 메모리를 읽을 수 없으므로 멀티코어 칩 하나의 공유 메모리와 같은 규칙으로 다루면 안 됩니다.

캐시 복사본의 값을 맞춘다

코어마다 캐시가 있으면 같은 메모리 위치의 복사본이 여러 캐시에 생깁니다. 한 코어가 자기 캐시의 복사본을 고쳤는데 다른 코어가 자기 캐시의 옛 복사본을 계속 읽는다면 문제가 됩니다. 같은 위치의 복사본들이 쓰기 뒤에 어떤 값을 보여야 하는지를 정한 것이 캐시 일관성(cache coherence)입니다. 흔히 쓰는 방법은 한 코어가 쓰기 전에 다른 캐시의 복사본을 무효로 만드는 무효화(invalidation) 방식입니다.

무효화 방식의 가장 단순한 예가 MSI 프로토콜입니다. 캐시 라인은 세 상태 가운데 하나에 있습니다. M(modified)은 이 캐시만 복사본을 가지고 있고 그것을 고친 상태, S(shared)는 여러 캐시가 고치지 않은 같은 복사본을 함께 가진 상태, I(invalid)는 복사본이 없거나 쓸 수 없는 상태입니다. 쓰려는 코어는 다른 캐시의 복사본을 I로 만든 뒤 자기 라인을 M으로 바꾸고, M인 라인을 다른 코어가 읽으려 하면 고친 값을 내보내고 둘 다 S가 됩니다.

def msi(events):
    state = {"A": "I", "B": "I"}
    invalidations = 0
    for core, op in events:
        other = "B" if core == "A" else "A"
        if op == "read" and state[core] == "I":
            if state[other] == "M":
                state[other] = "S"
            state[core] = "S"
        elif op == "write" and state[core] != "M":
            if state[other] != "I":
                state[other] = "I"
                invalidations += 1
            state[core] = "M"
        print(f"{core} {op:5} -> A={state['A']} B={state['B']}")
    return invalidations


print(msi([("A", "read"), ("B", "read"), ("A", "write"), ("B", "read"), ("B", "write")]))
print(0.7 * 80 + 0.3 * 140)

A read  -> A=S B=I
B read  -> A=S B=S
A write -> A=M B=I
B read  -> A=S B=S
B write -> A=I B=M
2
98.0

msi는 코어 A와 B의 캐시에 있는 같은 라인 하나의 상태를 따라갑니다. 두 코어가 읽으면 둘 다 S가 되고, A가 쓰면 B의 복사본이 무효가 되어 A만 M이 됩니다. 다시 B가 읽으면 A가 고친 값을 내주고 둘 다 S가 되며, B가 쓰면 이번에는 A의 복사본이 무효가 됩니다. 그사이 무효화는 두 번 일어났습니다. 실제 CPU는 E(exclusive) 상태를 더한 MESI 같은 더 정교한 프로토콜을 쓰며, 한 코어가 쓰는 순간 다른 모든 캐시가 곧바로 같은 값을 갖는 것은 아니고, 프로토콜의 메시지가 오가는 시간이 걸립니다. 마지막 줄은 앞에서 계산한 NUMA의 평균 접근 시간입니다.

일관성이 있어도 갱신을 잃는다

캐시 일관성이 지켜져도 갱신 손실은 막을 수 없습니다. 처음 X = 0이고 두 코어가 각자 X를 읽어 1을 더한 뒤 쓰는데, 두 코어가 모두 쓰기 전에 읽기를 마쳤다면 어떻게 될까요.

캐시 일관성은 마지막에 모든 캐시가 X = 1이라는 같은 값에 합의하게 해 줄 뿐, 두 번 더해 2가 되어야 한다는 프로그램의 뜻까지 지켜 주지는 않습니다. 각 코어의 읽기와 쓰기 사이에 다른 코어의 접근이 끼어들었기 때문입니다. 이것을 막으려면 읽기, 더하기, 쓰기를 쪼갤 수 없는 하나의 동작으로 하는 원자적 연산이나, 한 번에 한 코어만 들어가게 하는 잠금 같은 동기화(synchronization)가 필요합니다.

여러 위치에 대한 읽기와 쓰기가 다른 코어에게 어떤 순서로 보일 수 있는지를 정한 규칙은 메모리 일관성 모델(memory consistency model)이라고 합니다. 캐시 일관성이 위치 하나의 값을 다룬다면, 메모리 일관성 모델은 여러 위치 사이의 순서를 다룹니다. ISA가 어떤 순서를 허용하는지는 RISC-V의 메모리 모델 규격처럼 공식 규격에 정해져 있고, 이 차이는 다음 글에서 두 변수로 직접 계산해 봅니다.

거짓 공유

서로 다른 변수라도 같은 캐시 라인에 들어 있으면, 한 코어가 자기 변수를 쓸 때마다 다른 코어의 라인 전체가 무효가 됩니다. 두 코어가 각자 자기 변수만 고치는데도 라인이 두 캐시 사이를 계속 오가며 무효화가 일어나는 이 현상을 거짓 공유(false sharing)라고 합니다. 데이터 경쟁은 없어서 결과는 맞지만, 무효화와 전송 때문에 느려집니다. 자주 쓰는 변수들을 서로 다른 캐시 라인에 떨어뜨려 두면 줄일 수 있으며, 라인의 크기와 변수의 배치는 실제 시스템에서 확인해야 합니다.

더 깊이: 떨어뜨려 둘 거리를 알려 주는 C++ 표준 상수

변수들을 서로 다른 캐시 라인에 떨어뜨리려면 라인의 크기를 알아야 하는데, 이 값은 CPU마다 다릅니다. C++ 표준 라이브러리는 이를 위해 <new>에 상수 두 개를 둡니다. C++ 표준 초안에 따르면 hardware_destructive_interference_size는 동시에 접근하는 두 객체 사이에 두기를 권하는 최소 거리로, 구현이 만드는 경쟁 때문에 성능이 더 떨어지는 것을 피하려는 값입니다. 표준의 예처럼 두 원자 변수에 각각 alignas(hardware_destructive_interference_size)를 붙이면 두 변수가 그 거리 이상 떨어져 배치되므로, 서로 다른 코어가 따로 고칠 때의 거짓 공유를 피할 수 있습니다.

반대 방향의 상수도 있습니다. hardware_constructive_interference_size는 여러 스레드가 시간 지역성을 가지고 함께 쓰는 두 객체가 차지하기를 권하는 연속 메모리의 최대 크기이므로, 함께 쓰는 데이터는 이 크기 안에 모아 두라는 뜻입니다. 두 값은 모두 구현이 정하는 값이라, 프로그램을 실제로 실행할 CPU의 라인 크기와 늘 같다고 단정할 수는 없습니다.

정리

• 공유 메모리는 여러 코어가 같은 주소 공간을 쓰는 구조이고, NUMA에서는 메모리가 로컬인지 원격인지에 따라 접근 비용이 다르며, 분산 메모리는 메시지로 값을 주고받습니다.
• 캐시 일관성은 같은 위치의 캐시 복사본들이 쓰기 뒤에 보여야 할 값을 정하며, MSI는 쓰기 전에 다른 복사본을 무효로 만드는 방식입니다.
• 캐시 일관성은 갱신 손실을 막지 못하므로, 함께 고치는 데이터에는 원자적 연산이나 잠금 같은 동기화가 필요합니다.
• 메모리 일관성 모델은 여러 위치에 대한 접근이 다른 코어에게 보이는 순서를 정하며, 위치 하나의 값을 다루는 캐시 일관성과 다른 문제입니다.
• 거짓 공유는 서로 다른 변수가 같은 캐시 라인에 있어 생기는 성능 문제이고, 결과가 틀리는 데이터 경쟁과는 다릅니다.

연습 문제

1. 거짓 공유와 데이터 경쟁

코어 A는 X를, 코어 B는 Y를 고치는데, X와 Y는 서로 다른 변수지만 같은 캐시 라인에 있습니다. 이것만으로 결과가 틀리나요? 거짓 공유와 데이터 경쟁을 구분하고, 모든 데이터를 원격으로 읽는 NUMA 배치를 개선할 방향도 제안하세요.

2. NUMA의 평균 접근 시간

로컬 접근이 100 ns, 원격 접근이 250 ns입니다. 접근의 40%가 원격일 때 평균 접근 시간을 구하세요. 데이터 배치를 바꾸어 원격 접근을 10%로 줄이면 평균은 얼마가 되나요?

3. 번갈아 쓰는 두 코어

같은 라인을 코어 A와 B가 번갈아 네 번 씁니다. 처음에 두 캐시 모두 I일 때, 본문의 msi로 계산하면 무효화는 몇 번 일어나나요? 이것이 두 코어가 같은 변수를 쓰는 경우와 다른 변수를 쓰는 거짓 공유에서 각각 무엇을 뜻하나요?

여러 코어가 메모리를 함께 쓰는 문제를 만나면, 데이터의 위치, 캐시 복사본의 값, 여러 접근의 순서, 프로그램이 요구하는 동기화를 따로 적어 어느 문제인지 먼저 나누어 보세요. 다음 글 두 변수로 메모리 순서 비교하기에서는 메모리 일관성 모델에 따라 같은 프로그램이 다른 결과를 낼 수 있음을 직접 계산합니다.