Graph computing에서의 atomic operation에 대한 개념 정리

1. Atomic Operation이란

 

원자적 연산(atomic operation)이란 동시성 제어와 데이터 무결성을 보장하기 위해, 다른 프로세스 또는 스레드가 해당 데이터를 변경할 수 없는 상태로 보호하는 연산이다. 여러 CPU가 메모리 등 공유자원에 접근할 때, 여러 프로세스 또는 스레드가 동시에 액세스하지 않도록 하기 위해 다른 프로세스 또는 스레드가 해당 데이터를 변경할 수 없는 상태로 만들어준다. 원자적 연산에는 여러 가지가 있다.

 

# atomic
i = None
a.extend([x, y, z])
x = a.pop()
v = dict[k]

# not atomic
i = i + 1
if not dict.has_key(k) : dict[k] = 0

 

(1) Compare-and-Swap (CAS): 이 연산은 메모리 위치의 값을 비교한 다음, 값이 예상되는 값과 일치하는 경우 새로운 값으로 업데이트다. 이 연산은 원자적으로 수행되어야 하며, 동시에 여러 스레드가 해당 메모리 위치를 변경하는 것을 방지한다.

 

(2) Fetch-and-Add (F&A): 이 연산은 메모리 위치의 값을 읽어온 다음, 주어진 값을 더하고 결과를 원래의 메모리 위치에 저장한다. 이 연산은 원자적으로 수행되어야 하며, 동시에 여러 스레드가 카운터를 증가시키거나 누적 합을 계산하는 것을 방지한다.

 

(3) Test-and-Set (T&S): 이 연산은 메모리 위치의 값을 검사한 후, 새로운 값으로 설정한다. 이 연산은 원자적으로 수행되어야 하며, 동시에 여러 스레드가 공유 자원에 액세스하려고 시도하는 것을 방지한다.

 

(4) Load-Link / Store-Conditional (LL/SC): 이 연산은 값을 로드하고(로드 링크), 변경된 경우에만 조건부로 저장(스토어 컨디셔널)하는 원자적 연산이다. 이 연산은 동시에 여러 스레드가 같은 메모리 위치를 변경하려고 시도하는 것을 방지한다.

 

2. Graph computing에서 atomic operations의 문제점

 

이렇게 동시성 제어와 데이터 무결성을 보장하는 데 필요한 atomic operation에는 분명 trade-off가 있다. Atomic execution이 여러 연산을 포함하고 있는 데다가 성능 오버헤드가 발생한다는 점이다. Modern graph computing에서는 복잡한 그래프 탐색 알고리즘이나 vertices/edges에 수많은 정보를 포함하고 있다는 특징, 또는 그래프 구조가 동적으로 변경되기도 한다는 특징이 있다. 다음은 atomic operation의 성능 오버헤드가 발생하는 이유다.

 

(1) 동기화: 원자적 연산은 데이터에 대한 동시 액세스를 제어하고 동기화를 유지하기 위해 사용되지만, 이로 인해 성능이 저하될 수 있다. 동기화를 위해 여러 스레드가 원자적 연산을 기다리는 동안, 이러한 스레드는 다른 작업을 수행할 수 없으므로 시스템의 처리량이 감소할 수 있다.

 

(2) 비용이 많이 드는 하드웨어 지원: 원자적 연산을 제공하는 하드웨어 명령은 일반적인 명령보다 더 복잡하고 비용이 많이 들 수 있다. 이로 인해 원자적 연산의 수행 시간이 늘어나고, 성능이 저하될 수 있다.

 

(3) 캐시 일관성: 원자적 연산을 사용하면 여러 프로세서 간의 캐시 일관성을 유지하기 위해 추가적인 동기화 작업이 필요할 수 있다. 이로 인해 원자적 연산의 성능이 저하될 수 있다.

 

위와 같은 문제는 메모리에 접근하는 데 bottleneck이 발생하여 생기는 문제점이다. 따라서 메모리 접근을 최소화한다던지 불필요하게 동기화가 일어나는 부분은 없는지 살펴보고 최적화를 해야 한다.

 

3. Atomic operations를 최적화하여 사용하는 방벙

 

다음은 애플리케이션의 병렬성 수준과 동시성 요구 사항에 따라 적절한 원자적 연산을 선택하고, 불필요한 동기화를 최소화하는 방법이다.

(1) 동시성 요구 사항 분석: 애플리케이션의 병렬성 및 동시성 요구 사항을 정확하게 이해하려면, 애플리케이션에서 중요한 자원, 데이터 구조, 그리고 공유 변수를 식별해야 한다. 이를 통해 동시성 문제가 발생할 수 있는 영역을 파악하고, 적절한 원자적 연산을 결정할 수 있다.

(2) 최소한의 동기화: 동시성 문제를 해결하기 위해 필요한 최소한의 동기화만 수행해야 한다. 동기화 영역을 작게 유지하고, 공유 자원에 대한 액세스를 최소화하여 성능 저하를 줄일 수 있다.

(3) 고수준 원자적 연산 사용: 고수준 원자적 연산(예: atomic_add, atomic_fetch_add 등)을 사용하여 성능을 최적화할 수 있다. 이러한 연산은 일반적으로 하드웨어에서 직접 지원되며, 낮은 수준의 원자적 연산보다 효율적이다.

(4) 락 경합 최소화: 락을 사용하여 동시성을 제어할 때, 락 경합을 최소화하는 것이 중요하다. 락 경합은 여러 스레드가 동시에 락을 획득하려고 할 때 발생하며, 이로 인해 성능 저하가 발생할 수 있다. 락 경합을 줄이는 방법으로는 락의 범위를 줄이거나, 락을 세분화하여 더 세밀한 동시성 제어를 수행하는 것이 있다.

(5) 락-프리(lock-free) 및 웨이트-프리(wait-free) 알고리즘 사용: 락-프리 및 웨이트-프리 알고리즘은 원자적 연산을 사용하여 동기화를 수행하면서 락을 사용하지 않는다. 이러한 알고리즘은 높은 병렬성을 제공하며, 락 기반 동기화에 관련된 오버헤드를 줄일 수 있다.

 

(6) 스레드 로컬 데이터 사용: 공유 데이터를 최소화하기 위해 스레드 로컬 데이터를 사용하는 것을 고려해 볼 수 있다. 스레드 로컬 데이터는 각 스레드가 자체 데이터를 가지고 작업할 수 있게 해주며, 이로 인해 불필요한 동기화를 줄일 수 있다. 단, 이 방법은 적절한 데이터 분할이 가능한 경우에만 적합하다.

(7) 연산 순서에 관대하게 설계하기: 애플리케이션의 동작이 연산의 순서에 크게 의존하지 않도록 설계함으로써, 동시성 제어를 더 간단하게 만들 수 있다. 이러한 설계는 연산 간의 동시성을 높이고, 동기화를 최소화하는 데 도움이 된다.