멀티코어와 캐시 일관성

캐시가 둘이면 생기는 문제

코어 0과 코어 1이 공유 변수 X를 함께 쓴다. 각 코어의 캐시는 5장에서 본 나중 쓰기(write-back) 캐시다. 쓰기는 일단 자기 캐시에만 반영되고, 줄이 쫓겨날 때에야 메모리에 내려간다. 아래에서 버튼을 눌러 두 코어가 X를 읽고 1씩 올리게 해 보자. 먼저 "일관성 없음"으로 놓고 코어 0 쓰기 → 코어 1 읽기를 해 보자.

문제를 정확히 말하면 이렇다. 여러 사본이 있을 때 어떤 주소 하나에 대해 모든 코어가 같은 쓰기 순서를 보고, 읽기는 그 순서에서 가장 최근에 쓴 값을 돌려받아야 한다. 이 성질이 캐시 일관성이다. 흔히 두 가지 불변식으로 정리한다.

• 단일 쓰기자, 다중 읽기자(SWMR): 어느 순간이든 한 줄에 대해 쓸 수 있는 사본 하나만 있거나, 읽기만 하는 사본 여러 개만 있다.
• 데이터 값 불변식: 한 시기가 시작될 때 줄의 값은 직전 시기에 마지막으로 쓴 값과 같다.

쓰기 전에 다른 사본을 모두 없애는 방식을 쓰기 무효화(Write-invalidate), 쓸 때마다 새 값을 다른 사본에 뿌리는 방식을 쓰기 갱신(Write-update)이라 한다. 같은 줄에 연달아 쓰는 일이 많아서 거의 모든 현대 CPU는 무효화 방식을 쓴다.

줄마다 붙는 상태표: MESI

무효화 프로토콜을 구현하려면 캐시의 줄마다 몇 비트짜리 상태를 붙인다. 가장 널리 알려진 것이 네 상태의 MESI다.

• M (Modified): 이 캐시만 가졌고, 메모리보다 새 값이다(더티). 마음대로 읽고 쓸 수 있다.
• E (Exclusive): 이 캐시만 가졌고, 메모리와 같은 값이다. 쓰려면 아무에게도 묻지 않고 조용히 M이 된다.
• S (Shared): 다른 캐시에도 사본이 있을 수 있다. 읽기만 가능. 쓰려면 다른 사본을 무효화해야 한다.
• I (Invalid): 사본이 없다(혹은 쓸모없다).

각 캐시 제어기는 자기 코어의 요청(PrRd, PrWr)과, 공유 버스에서 엿들은 다른 캐시의 요청(BusRd: 읽으려 함, BusRdX: 쓰려고 독점 사본을 원함)에 반응해 상태를 바꾼다. 이렇게 버스를 엿듣는 것을 스누핑(Snooping)이라 한다. 아래 상태 기계에 사건을 하나씩 넣어 보자.

멀티코어 일관성 시뮬레이터

이제 코어를 2~4개로 늘리고 줄도 A~D 네 개로 늘려 보자. 각 캐시 상자 안의 줄을 누르면 그 코어가 그 줄을 읽거나 쓴다. 아래 시나리오를 고르면 정해진 순서로 접근을 재생하고, 같은 시나리오를 세 프로토콜로 돌렸을 때의 트래픽을 표로 비교한다.

표를 보면 프로토콜마다 잘하는 일이 다르다. 각자 자기 데이터를 고치는 경우 MESI는 MSI보다 버스 트랜잭션이 절반이다. 읽은 직후 쓰는 일이 프로그램에 아주 흔하기 때문에 E 상태는 거의 모든 프로세서가 채택했다. 이동하는 데이터처럼 더티 줄이 코어 사이를 옮겨 다니면 MOESI가 메모리 쓰기를 아낀다. Arm의 AMBA ACE·CHI 버스가 정의한 다섯 상태(UniqueDirty, SharedDirty, UniqueClean, SharedClean, Invalid)는 사실상 MOESI다. 반면 두 코어가 번갈아 쓰기는 어떤 프로토콜로도 줄이지 못한다. 쓰기 하나마다 줄이 통째로 건너가야 한다. 이것이 뒤에서 볼 거짓 공유와 락 경합의 뿌리다.

스누핑은 얼마나 커질 수 있나: 디렉터리와 SoC의 일관성

스누핑은 모든 미스를 모든 캐시에 방송한다. 코어가 4개일 때는 문제가 없지만, 64개가 되면 미스 하나마다 63개 캐시가 태그를 뒤져야 하고 버스의 대역폭도 금세 바닥난다. 대안은 줄마다 "지금 누가 사본을 가졌는지"를 기록하는 디렉터리(Directory)다. 미스는 그 줄의 담당(홈) 노드로 가고, 디렉터리를 보고 사본을 가진 캐시에만 메시지를 보낸다. 메시지 수는 코어 수가 아니라 공유자 수에 비례한다.

스마트폰 SoC는 두 방식을 섞는다. 한 CPU 클러스터 안(예: Arm DynamIQ의 DSU)에서는 공유 L3 옆에 스누프 필터(Snoop filter)를 두어, 각 코어의 L1·L2에 어떤 줄이 있는지 추적한다. 필터에 없는 코어에는 스누프를 보내지 않으니 사실상 작은 디렉터리다. 클러스터 바깥, 즉 GPU·NPU·DMA까지 아우르는 일관성은 NoC(8장)의 일관성 노드가 맡는다.

CPU 밖의 블록들: I/O 일관성

GPU나 카메라 ISP, DMA 엔진은 CPU가 준비한 버퍼를 읽고 결과를 써서 돌려준다. 그런데 CPU가 막 쓴 데이터는 CPU 캐시에 더티로 남아 있을 수 있다. 이들이 메모리를 직접 읽으면 낡은 데이터를 본다. 해결법은 두 가지다. 소프트웨어가 넘기기 전에 캐시를 청소(clean, 더티 줄을 메모리로 내림)하고 받기 전에 무효화(invalidate)하거나, 하드웨어가 그 블록의 메모리 접근을 CPU 캐시에 스누프해 주는 I/O 일관성(I/O coherency)을 쓰는 것이다. Arm은 이런 블록용으로 스누프는 받지 않고 보내기만 하는 ACE-Lite 인터페이스를 정의했다.

같은 줄에 사는 남남: 거짓 공유

일관성은 캐시 줄 단위로 관리된다. 두 스레드가 서로 다른 변수를 쓰더라도 그 변수들이 같은 64 B 줄에 들어 있으면, 하드웨어 눈에는 같은 줄을 번갈아 쓰는 것과 똑같다. 쓸 때마다 줄을 상대에게서 빼앗아 와야 한다. 이것이 거짓 공유(False sharing)다. 아래에서 코어 0은 a++, 코어 1은 b++만 계속한다. 둘은 아무것도 공유하지 않는다.

해결법은 간단하다. 스레드마다 자주 쓰는 변수를 다른 캐시 줄에 두면 된다. C/C++에서는 alignas(64)나 std::hardware_destructive_interference_size로, 자바에서는 @Contended로 패딩을 넣는다. 스레드별 카운터를 따로 모았다가 마지막에 합치는 것도 같은 생각이다. 거짓 공유는 정답은 맞게 나오고 속도만 느려서, 프로파일러로 캐시 간 전송(HITM) 이벤트를 세어 보기 전에는 알아채기 어렵다.

일관성만으로는 부족하다: 메모리 순서 모델

일관성은 주소 하나에 대한 약속이다. 그런데 프로그램은 여러 주소를 함께 쓴다. 코어 0이 data = 1을 쓰고 이어서 flag = 1을 썼을 때, 코어 1이 flag == 1을 봤다면 data도 반드시 1로 보일까? 이것은 일관성이 아니라 메모리 일관성 모델(Memory consistency model), 줄여서 메모리 모델이 정한다.

가장 직관적인 모델은 순차 일관성(SC, Sequential consistency)이다. 모든 코어의 명령을 하나의 순서로 섞되 각 코어의 프로그램 순서는 지키는 실행만 허용한다. 하지만 SC는 비싸다. 5장에서 본 쓰기 버퍼에 쓰기를 넣어 두고 다음 읽기를 먼저 하는 것조차 금지하기 때문이다. 그래서 x86은 쓰기 → 읽기 순서 바꾸기만 허용하는 TSO(Total store order)를, Arm은 서로 다른 주소라면 거의 모든 순서 바꾸기를 허용하는 약한 모델을 택했다. 순서가 중요한 곳에서는 프로그래머가 펜스(Fence, Arm의 DMB)나 acquire·release 명령으로 순서를 강제한다.

모델의 차이는 짧은 리트머스 테스트(Litmus test)로 드러난다. 아래에서 테스트와 모델을 고르고, 실행할 명령을 직접 눌러 실행 순서를 만들어 보자. 밝은 테두리가 그 모델에서 지금 실행할 수 있는 명령이다. 처음에 모든 메모리 값은 0이다.

• SB(Store buffering): 두 스레드가 각자 자기 변수에 쓰고 상대 변수를 읽는다. 둘 다 0을 읽는 결과는 SC에서 불가능하지만, 쓰기가 아직 쓰기 버퍼에 있으면 TSO에서도 가능하다. 피터슨 알고리즘 같은 상호 배제가 x86에서 펜스 없이는 깨지는 이유다.
• MP(Message passing): 데이터를 쓰고 깃발을 세운다. 깃발은 보였는데 데이터가 0인 결과는 TSO에서는 불가능하지만 Arm에서는 가능하다. Arm에서는 쓰는 쪽에 STLR(release), 읽는 쪽에 LDAR(acquire)를 쓰거나 양쪽에 DMB를 넣어야 한다.
• LB(Load buffering): 각자 상대 변수를 먼저 읽고 자기 변수에 쓴다. 둘 다 1을 읽는 결과는 미래의 쓰기를 읽은 것처럼 보이지만 Arm 모델은 이를 허용한다.

원자 연산과 락: 일관성 위에 지은 집

여러 코어가 공유 자료를 고치려면 한 번에 한 코어만 들어가게 하는 락(Lock)이 필요하다. 락은 읽고-고치고-쓰기를 쪼갤 수 없게 하는 원자 연산(Atomic operation) 위에 만든다. Arm v8.1부터는 SWP, LDADD, CAS 같은 원자 명령(LSE)이 있고, 그 전에는 LDXR/STXR(배타적 읽기·쓰기) 쌍으로 같은 일을 했다. 원자 연산은 그 줄을 M 상태로 독점해야 실행할 수 있다. 그래서 락을 기다리는 코어가 많으면 락이 든 줄이 코어 사이를 미친 듯이 오간다.

• TAS 스핀락: 될 때까지 swap(lock, 1)을 반복한다. 기다리는 동안에도 매번 줄을 독점하려 해서 버스가 포화되고, 락을 풀려는 주인조차 줄을 받으려고 줄을 서야 한다.
• TTAS(test-and-test-and-set): 먼저 평범한 읽기로 락이 풀릴 때까지 자기 캐시의 S 사본을 보며 기다리다가, 풀린 것을 보면 그때 swap한다. 기다리는 동안 버스가 조용하다. 하지만 풀리는 순간 모든 대기자가 한꺼번에 몰려든다.
• 티켓 락: 은행 번호표처럼 my = fetch_add(next, 1)로 번호를 받고 serving == my가 될 때까지 읽기로 기다린다. 도착 순서대로 공정하게 들어가고, 풀 때 원자 연산 경쟁이 없다.

결과는 생각보다 단순하지 않다. 임계 구역 길이를 400클럭, 코어를 4개로 놓아 보자. TAS는 기다리는 코어들이 서로 줄을 빼앗느라 버스를 90% 가까이 점유하지만, TTAS와 티켓 락은 기다리는 동안 조용해서 점유율이 그 1/3 수준이다. 버스가 비어 있으면 락과 무관한 다른 코어의 메모리 접근도 빨라진다. 그런데 코어를 16개로 늘리고 경합을 심하게 하면 TTAS는 오히려 TAS보다 트래픽이 많아진다. 락이 풀리는 순간 모든 대기자의 사본이 한꺼번에 무효화되고, 15개의 다시 읽기와 여러 swap 시도가 버스로 몰리기 때문이다. 1990년 T. Anderson이 버스 기반 멀티프로세서에서 측정해 보인 바로 그 현상이다. 티켓 락도 해제 때마다 대기자 전원이 다시 읽으므로 트래픽은 코어 수에 비례하지만, 공정성(최소/최대 획득)이 거의 완벽하다. TAS·TTAS에서는 운 나쁜 코어가 거의 굶는다.

근본 해법은 대기자들이 서로 다른 줄을 보며 기다리게 하는 것이다. 리눅스 커널의 qspinlock이 쓰는 MCS 큐 락은 대기자마다 자기 줄을 따로 두고 그 줄만 보며 기다리게 해서, 해제가 다음 대기자 한 명의 줄만 건드린다. 획득당 트래픽이 코어 수와 무관해진다. 실패할 때마다 기다리는 시간을 늘리는 지수 백오프도 TAS·TTAS의 폭주를 크게 줄인다.