Compact NUMA-aware Locks

Compact NUMA-aware Locks

notion에서 보기 

---

1. Introduction

Lock

• 멀티 프로세스 시스템에서 공유 데이터에 대한 exclusive 접근을 위해 사용된다.

Modern architecture

• 노드(소켓)의 수가 증가
• 각 노드에 로컬 메모리 + 로컬 캐시 + 멀티 프로세싱 units(cores)
• 로컬메모리, 로컬캐시에 대한 접근 속도 > 다른 노드에 있는 리모트메모리, 리모트캐시

NUMA-aware locks

• 같은 소켓 내에 락 소유권을 유지하려는 기법
• 리모트 캐시 miss와 miss로 인한 노드간 이동을 감소시킨다.
• 공유 데이터가 lock holder가 실행 중인 소켓으로 캐시된다.
• NUMA-oblivious locks는 single memory word 만으로 구현되는 반면에 모든 NUMA-aware lock은 계층적인다. - local lock & global lockii) global lock : local lock을 가진 스레드를 동기화한다.
• i) local lock : 노드마다 같은 노드에서 실행중인 스레드를 중재한다.
• problems of hierarchical structure of NUMA-aware locksii) 이식성을 보장하기 위해선 런타임까지 기본 시스템의 소켓 수를 알 수 없기 때문에 NUMA-aware locks을 동적으로 초기화해야 한다. 하지만 이를 보장하는 표준 API가 없기 때문에 이식성을 방해한다.워크로드가 복잡할때 lock에 대한 경쟁이 발생한다.
• iii) NUMA-aware lock의 local, global lock 계층구조는 소켓수만큼의 공간을 필요로 한다. Linux kernel과 같이 수많은 lock을 가진 시스템은 spin lock의 사이즈를 엄격하게 제한한다.
• i) lock에 대한 경쟁이 없을 때에도 스레드는여러 개의 critical section에 진입하기 전에 low-level lock (local)를 얻기 위해 multiple atomic opertation을 수행해야 한다.

compact NUMA-aware lock (CNA)

• 소켓의 개수와 상관없이 one word 만 필요하다
• lock 획득을 위해 한 번의 atomic instruction만 필요하다.
• MCS lock의 개선 버전이다
• ** MCS lock : 스레드는 lock을 기다리는 동안 큐에 들어가고 local cache line에서 spin을 한다.
• 같은 소켓에서 실행 중인 다음 스레드에 lock을 넘긴다.
• 다음 스레드를 찾는 동안 락 소유자는 다른 소켓에서 실행 중인 대기 스레드를 별도의 보조 스레드로 이동시킨다.
• 보조 큐에 있는 스레드는 다음 두 조건 하에 다시 원래의 큐로 돌아간다.ii) local handover이 특정 획수를 넘은 경우
• → long-term fairness를 보장하고 보조 큐에 있는 스레드에 대한 starvation을 방지한다.
• i) 메인 큐에 현재 락 소유자와 동일한 소켓에서 실행 중인 대기 스레드가 없는 경우
• Linux kernel spin lock (qspinlock)을 수정하여 구현한다.

2. Related Work

test-and-set lock

• spin lock의 일종
• 스레드는 unlock에서 lock으로 변경된 lock의 상태를 표시하는 값을 반환할때까지 atomic test-and-set instruction을 반복적으로 실행시킨다.
• one word로 구현할 수 있다.
• 동일한 메모리 위치에 대한 lock spin을 얻으려고 하는 모든 스레드인 global spinning을 사용한다.
• lock handover 동안 coherence traffic이 초과한다.
• 공평성을 보장하지 않는다.

Queue locks (MCS)

• FIFO 큐에서 락을 기다리는 스레드를 정렬하여 test-and-set 락의 문제를 해소한다.
• 락의 공유 상태가 큐의 tail에 대한 포인터로 구성된다.
• 각 스레드는 자동적으로 tail에 swap되어 큐에 삽입되어 큐 노드를 갖는다. 그리고 해당 큐 노드 내부에 flag에 spin을 하다가 락이 unlock되면 flag를 set한다.
• lock handover 마다 소켓간 이동이 발생하면 coherence traffic이 증가하기 때문에 NUMA 시스템에는 적합하지 않다.

Hierarchical backoff lock (HBO)

• lock을 같은 소켓에 유지하기 위해 제안된 락 기법
• lock holder의 소켓 넘버를 저장하기 위한 one word 메모리만 필요로 한다.
• 스레드가 lock이 이용가능한 상태임을 발견하면
• 만약 lock holder가 같은 노드에서 실행된다면 small value로, 다른 노드에서 실행된다면 larger value로 back-off를 설정한다.
• spin lock의 global spinning 문제와 같은 문제가 발생한다.— 락 상태를 덜 자주 확인함에도 불구하고 lock에 대한 경쟁
• — 다른 소켓에서 spin하는 스레드의 starvation 문제
• backoff timeout 개선이 필요하다.

Hierarchical MCS (HMCS)

• queue locks 으로 계층적 동기화 구조를 사용한다.
• 소켓 내부의 동기화를 위한 per-socket 동기화 구조 + 소켓 외부의 스레드간 동기화를 위한 계층적 동기화 구조
• 소캣 네부와 외부 계층이 MCS lock으로 보호된다.
• 소켓의 수와 비례하여 메모리 사용량이 결정된다.
• per-socket - 서로 다른 cache line에 위치해야 해서 lock의 크기를 늘린다.
• 계층적 락은l lock operation이 mutiple atomic instruction을 포함하고 있기 때문에 경쟁 상태에서 성능이 저하된다.

3. Background

Linux Kernel Spin Lock

• multi-path approachii) MCS lock으로 구현된 slow path
• i) test-and-set lock으로 구현된 fast path
• 4-bytes lock word = lock value + pending bit + queue tail
• lock 을 얻는 방법
  1. spin lock을 얻으려는 스레드는 일단 자동적으로 lock value를 0에서 1로 바꾸려 한다. 이것이 성공하면 lock을 얻게 된다.
  2. 실패하면 lock에 대한 경쟁이 있는지 확인한다. 경쟁은 pending bit과 queue tail bit을 통해 나타난다.
  3. 경쟁이 없다면 스레드는 자동적으로 pending bit을 0에서 1로 바꾼다. 이것이 성공하면 현재 락 소유자가 lock을 반납할때까지 spin을 하면서 기다린다.
  4. 경쟁이 있다면 스레드는 slow path로 전환되어 자동으로 queue tail bit를 swap하여 MCS 큐로 삽입된다.
  5. MCS 큐에 삽입된 스레드 t는 큐의 head에 도달할 때까지 기다린다.
  6. t가 빈 큐에 진입하거나 큐 내부에 t의 앞에 있는 스레드가 t의 큐 노드에 있는 flag에 write를 하면 발생한다.
  7. 이때, t는 lock holder와 pending bit에서 spin하고 있는 스레드가 사라지기를 기다린다.
  8. lock value, pending bit가 모두 0이 된 것을 확인하면 t는 lock value를 1로 set하여 lock을 요청하고 MCS 큐에서 t 다음에 있는 스레드 tt 의 flag에 write를 하여 tt가 MCS 큐의 head에 있다는 것을 알려준다.
  9. spin lock을 해제하는 스레드는 lock value를 0 으로 바꾼다.

CNA lock

• CNA lock은 kernel spin lock의 slow path (MCS lock)을 대체한다.

4. Design Overview

CNA - main, secondary Queue

• MCS는 하나의 큐로 lock을 기다리는 스레드를 정렬하지만 CNA는 두개의 큐를 사용한다.— 보조 큐 : lock holder와 다른 소켓에서 실행되는 스레드
• — 메인 큐 : lock holder와 같은 소켓에서 실행되는 스레드
• 스레드가 CNA lock을 얻으려고 할때 항상 메인큐에 먼저 합류하고 다른 소켓에서 실행중인 lock holder에 의해 보조 큐로 옮겨진다.

CNA lock pointer

• CNA lock의 공유 상태는 메인 큐를 가리키는 포인터인 1 single word = tail로 구성된다.
• 스레드 t는 자동적으로 tail 포인터가 가리키는 위치에 swapping되며 메인큐에 삽입된다. (=atomic instruction)
• 보조 노드는 다음 스레드를 담은 큐 노드를 가리키는 포인터인 next를 가지고 있다.
• 스레드 t는 spin 필드가 0에서 1로 바뀔때까지 기다리면서 spin한다. spin 필드는 큐에서 t의 앞에 있는 스레드가 critical section을 나갈가면서 unlock function을 실행시키면서 lock 소유권을 t에게 넘길때 바뀐다.

CNA unlock function

• CNA의 lock function은 MCS와 거의 동일하고 unlock function은 다르다.
• *** MCS - 단순히 다음 스레드에 lock을 넘긴다.
• 현재 lock holder 스레드 h는 메인 큐를 순회하면서 같은 소켓에서 실행 중인 스레드를 찾는다.
• 다음 스레드로 h'를 찾으면 메인 큐에서 h와 h' 사이에 있는 모든 스레드 (큐 노드) 를 보조 큐로 옮기고 h가 h'으로 소유권을 넘긴다.
• h는 포인터를 보조 큐의 head, h'로 옮긴다. 이렇게 하면 h'는 그 다음에 lock을 보조 큐의 스레드로 넘길 수 있게 된다.
• 다음 스레드를 가리키는 포인터를 저장하기 위해 spin 필드를 재사용 한다.
• h는 h'의 spin으로 보조 큐의 head를 가리키는 포인터를 쓴다.

when threads in the secondary queue can return to the main queue and acquire the lock

• 현재 락 홀더인 h가 메인 큐에서 다음 스레드를 찾지 못하면 메인 큐에서 h 바로 다음 스레드 전에 보조큐의 tail에 위치한다. 그리고 보조 큐의 head node에 lock을 넘긴다.
• 보조큐의 tail을 찾기 위해서 보조 큐의 head에서부터 순회를 시작하는데 이때 큐가 너무 길어지면 비효율적이다. 따라서 포인터를 보조 큐의 head에 속하는 노드에 보조큐의 tail을 가리키는 포인터를 저장한다.
• 보조 큐의 head node에 저장한 보조 큐의 tail을 가리키는 포인터는 unlock function 시에 메인 큐에서 보조 큐로 노드를 이동시킬때 사용한다.
• 같은 소켓에 실행 중인 스레드가 반복적으로 lock에 획득하고 메인 큐에 진입하려고 하면 CNA는 다른 소켓에서 실행 중인 다른 모든 스레드에 starvation을 발생시킨다.
• fairness를 보장하기 위해 CNA 는 주기적으로 스레드를 보조큐에서 메인큐로 옮긴다.

5. Implementation Details

 

• Example