Background
현재 CPU의 발전 흐름은, CPU의 clock의 속도를 늘리는 방향이 아니라 코어의 개수를 늘려 throughput 늘리는
방향으로 진행되고 있다.
core의 수가 늘어나면서 memory에 대한 높은 bandwith이 요구된다. 하지만 아래와 같이 North bridge에 단일 memory controller로 구성된 시스템이라면 North bridge가 병목 구간이 될 수 있다.
이와 같은 문제를 해결하기 위해, CPU마다 memory controller 통합하고 local Ram을 연결하여 전체적인 bandwidth을 증가시킬 수 있다. 서로 다른 다이 또는 코어와의 커뮤니케이션은 데이터 버스로 이루어진다.
위의 예시에서 서로 다른 다이들은 inter connection controller로 연결되어 있다. 만약 1번 die에서 2번 die에 위치한 메모리에 접근하려면 interconnection controller을 통해 1번의 hop이 필요로 한다. 이러한 구조로 CPU는 접근하려하는 메모리의 위치에 따라 접근 시간이 달라지는 구조를 가지며 이를 Non-Uniform Memory Access(NUMA)라고 한다.
Cache-coherent 아키텍처
multicore 아키텍처에서, 각 코어는 개별적인 캐시를 보유한다. 따라서 어떠한 규칙이 없다면 동일한 메모리에 대한 복사본이 여러 버전이 존재할 수 있다. 이러한 현상을 방지하기 위해 CPU는 cache coherent 프로토콜을 사용한다.
많은 multicore 아키텍처에서 사용하는 cache coherent 프로토콜은 MESI 프로토콜에 기반하고 있다. MESI는 4가지 state들의 이름을 딴 것으로, cache line들은 4가지 속성(Modified, Exclusive, Shared, Invalid) 중 1개를 가진다. 버스에 요청된는 transaction들은 snooper에 의해 모니터링되며, 각 요청에 대해 cache에 대한 state를 갱신한다
Modified: The data in the cache line has been modified locally (i.e., it is dirty), and only resides in this cache. The copy in the main memory is is not up to date, therefore, if the cache line is evicted or changes its state, its data must be flushed to the main memory.
Exclusive: The data in the cache line is unmodified (i.e., it is clean), and it does not reside in any other cache.
Shared: The data in the cache line is clean but other copies may reside in other caches.
Invalid: The cache line does not contain valid data. This typically happens when a shared cache line was modified in one of the caches: other copies of the data got invalidated by the cache-coherence protocol
Cache access performance
NUMA architecture에서 remote CPU의 cache에 접근하는 것은 local CPU의 cache에 접근하는 것보다 많은 시간이 걸린다. 아래의 그림과 같이 4개의 AMD Opteron 6172 CPUs로 구성된 시스템에서, L1 캐시에 미리 데이터를 로드한 다음 각각의 코어(Local, Remote)들이 cache에 접근하는 시간을 구해보도록 한다.
Local CPU가 L1 cache에 접근하는 데에 3 cycle이 걸렸고, 그래프에서는 초록색으로 표시된다. 같은 다이의 다른 코어의 L1 cache에 접근하는데 38 cycle이 소요되었고 그래프에서는 보라색으로 표시된다. Remote cache에 접근할 때는 2가지의 케이스가 존재한다. 만약 local 다이에 직접적으로 연결된 경로가 있다면 220 cycle이 소요되고, 그래프에서는 빨간색으로 표시된다. 직접적으로 연결된 경로가 없다면 추가적인 hop이 요구되므로 300 cycle이 소요되며, 이는 노랑색으로 그려진다.
Contention overhead
store instruction과 atomic instruction의 contention overhead를 측정하기 위해, custom benchmark를 이용한다. 해당 벤치 마크는 1개의 monitoring thread와 N개의 Non-monitoring thread로 구성되어 있다.
monitoring thread:shared variable에 대해 반복해서 store/atomic instruction을 실행하며 1000번의 실행할 때마다 소요된 시간을 측정한다.
non-monitoring thread: shared variable에 대해 반복해서 store/atomic instruction을 실행한다.
1 thread: 한 개의 thread(monitoring thread)만 실행될 때, store instruction은 73 cycle이 소요되었고 cas instruction은 98 cycle이 소요되었다. 이 경우, shared variable은 항상 monitoring thread의 L1 cache에 위치해 있다.
N thread: 한 개의 monitoring thread와 여러 개의 Non-monitoring thread가 개별적인 코어에서 실행된다. 따라서 cache coherence 프로토콜에 따라 다른 코어의 cache line을 invalid 하고 본인의 L1 cache로 fetch하는 과정이 수행된다. Thread가 늘어나면 늘어날 수록 요구되는 cache coherence traffic은 늘어나며, 48개 thread일 경우 소요되는 시간은 수 천 cycle에 이르게 된다.
Monitoring thread가 접근하는 shared variable가 local NUMA 메모리에 위치한 경우, Remote NUMA에 위치한 경우보다 더 좋은 성능을 보인다. 이미 L1 cache line에 로드하였기 때문에, RAM에 접근하지도 않지만 더 좋은 성능을 보인다. 이것은 AMD의 HT Assist technology 때문이다.
결론적으로, atomic operation은 scalable 하지 않으며, 만약 spinlock이 단순히 atomic operation으로 구현되었다면, 이 역시 scalable 하지 않을 것이다.
Spinlock
basic spinlock
spinlock은 조건 변수에 대해 busy-waiting을 사용하는 lock 알고리즘이다. x86에서 제공하는 cmpxchg와 같은 instruction을 이용하여 간단하게 구현할 수 있다.
앞에서 보았듯이, 위와 같은 lock은 core 개수가 늘어나면 늘어날 수록 성능이 저하될 것이다. 문제는 lock이라는 shared variable에 대해 여러 thread가 반복해서 cmpxchg하는 것이다. 이러한 문제를 해결하는 알고리즘으로 MCS lock이 있다.
MCS lock
mcs lock은 queued lock의 일종이며, lock은 queue에 insert하는 것과 동일하고, unlock은 delete하는 것과 동일하다. 이때, lock을 획득하지 못하여 queue에 insert된 thread들은, Node에 위치한 thread 별 조건 변수에 대해 busy waiting한다. 따라서 thread 별로 개별적인 cacheline에 대해 접근하기 때문에 scalable하다.
해당 알고리즘은 high contention일 때 더 높은 성능을 보이고, low contention일 때는 CAS 기반 알고리즘보다는 느리다(CAS 기반 lock은 워낙 적은 instruction으로 구현 가능하기 때문이다.)
좀 더 자세한 내용은 해당 알고리즘이 제안된 "Algorithms for scalable synchronization on shared-memory multiprocessor"을 참고하면 된다.
기본적인 자료 구조 lock과 node를 C 코드로 구현하면 아래와 같다. (L1 cache의 cachline size는 64바이트로 가정한다.)
주요 함수인 lock과 unlock의 함수를 C로 구현하면 아래와 같다. mcs lock은 기존의 spinlock의 인터페이스와는 다르게 새로운 인자 node를 필요로 한다.
아래는 queue에 여러 thread가 대기할 때, lock을 획득한 thread(Node0)가 다음 thread(Node2)의 조건 변수를 unlock하는 그림이다.
MCS lock in Linux Kernel
Linux kernel에서도 mcs lock을 구현하고 있으며, queued lock으로 불린다. 커널에서 spinlock은 contention의 상황에 따라 2가지로 구분되어 사용된다.
Low contention일 경우 일반적인 CAS 기반 spin lock을 사용한다.
high contention일 때 mcs lock이 사용된다.
커널에서 MCS lock은 다음과 같은 2가지 이유로 변형된 구조로 구현되었다.
기존의 lock 변수에 64bit pointer을 저장할 수 없다.
MCS lock은 lock, unlock 함수에 새로운 인자 Node를 요구하는데 이는 기존의 spinlock 인터페이스와 맞지 않다.
MCS lock을 사용하기 위해서는 CONFIG_QUEUED_SPINLOCKS 옵션이 활성화 되어야 한다(아직, x86, arm64와 같은 특정 아키텍처만 지원한다.).
해당 옵션이 활성화 되면, arch_spin_x 들의 정의는 queue_spinlock에서 구현된 함수들로 매핑이 진행된다.
앞서 말한 대로, queue spin lock은 contention 상황에 따라 CAS 기반 또는 MCS로 사용될 지 결정된다고 하였다. 그것을 결정하는 로직은 아래와 같이 lock을 획득하지 못하면, slow path로 진입하고 MCS로 용도가 변경된다.
커널의 구현된 MCS lock의 아이디어는,
생길 수 있는 context(task, softirq, hardirq, nmi)에 대해 PerCPU 변수로 미리 node들을 선언한다.(Line 7)
node들은 cpu id와 context에 따라 결정되므로, 이 값들을 인코딩하여 32bit 내에 저장할 수 있도록 한다.(encode_tail, decode_tail)
이 밖의 slow_path를 처리하는 로직은 MCS lock의 알고리즘과 거의 동일하므로, 코드를 첨부하진 않는다.
문제점
완전한 MCS lock이 아니기 때문에, 드물게 fairness가 보장되지 않는 케이스가 발생할 수 있다.
한 번 cmpxchg를 시도하고 실패하기 때문에 cache miss가 발생한다.
Combining lock
Flat combining은 lock 알고리즘일 뿐만 아니라 새로운 동기화 패러다임이기도 하다. 공유 자원에 대한 operation을 결합(combine)함으로써 알고리즘의 복잡성을 낮추고 data locality를 증진시킨다.
즉, 공유 자원에 대해 한 쓰레드가 효율적인 sequential 알고리즘을 n번 실행하는 하는 것이, n개의 스레드가 하나의 operation을 각각 실행하는 것보다 빠를 수 있다.
주요 구현 포인트로,
Flat combining에서 한 쓰레드가 공유 자원에 대해 operation을 실행하고 싶을 때, 해당 operation을 queue에 넣는다. 그리고 combiner 쓰레드가 그 operation을 실행할 때까지 대기한다.
만약 combiner 쓰레드가 존재하지 않는다면, 스스로 combiner 쓰레드가 되고 queueing되어 있는 모든 operation을 실행한다.
해당 lock의 주요 자료 구조 node를 C로 표현하면 아래의 코드와 같다.
노드의 각각의 멤버의 역할은 다음과 같다.
req: 실행할 operation의 함수 포인터가 저장된다. thread들은 req에 busy-waiting을 한다.
ret: operation을 실행하고 반환된 값을 저장할 때 사용된다.
params:는 operation 실행 시 parameter로 사용된다.
active: 해당 노드가 활성화되어 있는지 상태를 표현
age: 해당 노드가 완료된 시점을 저장하여 회수할 시점을 결정
next: 다음 node를 가리키는 포인터
flat_combining의 api는 일반적인 interface(lock, unlock)이 아니라, 하나의 함수 execute_cs로 구성된다.
해당 코드는 2개의 파트로 구성되어 있다. 하나는 일반 thread로 처리되는 부분과, combiner thread로 일을 수행하는 부분이 있다.
<normal thread>
Line 9~24는 combiner thread가 request를 실행할 때까지 busy-waiting하는 부분이다.
Line 22에서 combiner_lock을 획득하면, 해당 thread는 combiner thread의 역할을 수행하기 시작한다.
<combiner thread>
Line 36~44는 combiner thread가 pending 되어있는 요청을 전부 수행하는 부분이다.
Line 46~58는 실행이 완료된 노드들을 queue에서 제거하는 로직이다.
문제점
구현에서 살펴볼 수 있듯이, combiner_lock에 대해 high contention이 발생할 수 있다.
CLEANUP_FREQUENCY와 CLEANUP_OLD_THRESHOLD와 같은 파라미터에 따라 성능이 결정되며 어떤 값을 사용해야 할 지 결정하기 쉽지 않다.
CC-Sync
cc-sync 알고리즘은 앞에서 본 flat-combining 알고리즘의 개선된 버전이다. 그렇기에 cc-sync도 global queue를 사용하며 request들을 combine할 수 있다. 또한 flat combining과는 다르게 global lock을 사용하지 않아 high contention시 발생할 수 있는 성능 저하를 피할 수 있다.
주요 아이디어로는,
lock을 획득한 쓰레드가, combiner thread가 된다. 이는 queue의 순서에 따라 지정되므로 contention을 피할 수 있다.
combiner thread는 최대 MAX_COMBINER_CS 개수 만큼의 요청을 처리한다. 즉, combiner thread가 request를 처리한 사용하는 시간에 상한을 둔다.
cc의 node 구성은 flat-combining의 node와 유사하며, completed, wait라는 새로운 멤버 변수를 사용한다.
cc도 execute_cs 함수를 통해 critical section을 실행한다.
문제, critical section에 작업을 완료해도 node 데이터는 유지해야 한다. 그렇다면, 다시 critical section에 진입할 때는 다른 node를 사용해야 하지 않나? node에 대한 free를 하는 시점이 모호하다.
Comments