Threads and Memory

References

• Ch5, The Art of Writing Efficient Programs

Contents

• Threads and Memory (Data Sharing)
• Concurrency and Memory Syncrhonization
• Mutex, Atomic Variables
• False Sharing

---

요좀 고성능 컴퓨터는 여러 CPU를 가지거나 여러 CPU 코어를 갖는다. 대부분의 노트북도 최소 2개에서 4개의 코어를 가지고 있다. 성능 측면에서 효율이 높으려면 하드웨어를 유후 상태로 두지 않아야 한다. 많은 CPU 코어 중 하나만 사용하는 것과 같이 전체 하드웨어 성능의 일부만 사용하는 경우에는 프로그램이 효율적이거나 고성능일 수가 없다. 프로그램이 한 번에 둘 이상의 프로세서를 사용하는 방법은 여러 스레드나 프로세스를 실행하는 것 뿐이다.

이번 포스팅에서는 스레드에 대한 기본적인 내용은 생략하고 스레드와 동시 프로그램에서의 성능과 관련된 주제에 대해서 자세히 살펴볼 예정이다.

 

아래에서 사용된 전체 벤치마크 코드는 link에서 확인할 수 있다

Threads and Memory

여러 스레드 간에 CPU를 시분할(time-slice)한다면 성능상의 이점이 전혀 없다. 모든 프로세스 코어에서 하나의 스레드만 실행한다고 가정해보자. 이러한 스레드들은 리소스를 두고 경쟁하지 않는 한 완전히 독립적으로 실행되며, 완벽한 속도 향상을 기대할 수 있다. 두 스레드는 정확히 한 스레드에서 수행할 수 있는 작업의 두 배에 해당하는 작업을 수행한다 (주어진 작업이 두 스레드 사이의 상호 작용을 필요로 하지 않고 완벽하게 분할될 수 있는 경우에).

 

이런 이상적인 상황은 실제로 아예 발생하지 않는 것은 아니지만 흔한 경우는 아니다.

효율적인 동시 프로그램 (concurrency program)을 작성하는데 어려운 부분은 서로 다른 스레드가 수행하는 작업이 완전히 독립적이지 않고 스레드가 리소스를 두고 경쟁하기 시작할 때 발생한다. 각 스레드가 CPU를 최대로 활용한다면, 스레드들이 경쟁하는 것은 모든 스레드 간에 공유되는 공통 리소스인 메모리이다. 따라서, 멀티스레드 프로그램의 성능에 대해 이야기할 때는 일반적으로 메모리를 통한 스레드 간의 상호작용에서 발생하는 문제에 집중한다.

 

고성능의 동시 프로그램을 작성할 때 신경써야 할 또 다른 측면이 있다. 이는 프로그램을 구성하는 스레드와 프로세스 간에 작업을 나누는 것이다. 다만, 이에 대한 내용은 현재 살펴볼 내용을 벗어난다. 이에 대한 내용은 병렬 프로그래밍(parallel programming)에 대해서 공부하면 알 수 있는 것들이다.

 

성능에 큰 제약이 되는 메모리에 동시성을 추가하면 더욱 문제가 된다. 하드웨어로 인한 근본적인 한계는 극복할 수 없지만, 대부분의 프로그램은 이러한 한계까지 성능을 발휘하지 못하기 때문에 프로그래머가 코드 효율성을 향상시킬 수 있는 여지가 많다.

 

먼저 여러 스레드를 사용하는 상황에서 메모리 시스템의 성능을 살펴보자. 메모리를 순차적으로 쓰는 벤치마크를 통해 속도 성능을 측정할 예정이며, 이때, 스레드 갯수를 다양하게 설정하여 여러 스레드가 동시에 쓰도록 구성한다. 이 벤치마크는 각 스레드가 액세스할 자체 메모리 영역을 가진다. 즉, 스레드 간 데이터를 공유하지는 않지만 memory bandwidth와 같은 하드웨어 리소스는 공유하는 상황이다.

 

벤치마크 자체는 이전 포스팅에서 사용한 것과 완전히 동일하다. 다만 이 벤치마크를 실행할 때, 구글 benchmark 라이브러리의 멀티스레드 벤치마크 기능을 활용한다. 아래 벤치마크는 스레드 갯수가 1, 2, 3, 4, 6, 8, 16개일 때 각 메모리 크기에 대한 쓰기 성능을 측정한다.

template <class Word>
void BM_write_seq(benchmark::State& state) {
    void* memory;
    const size_t size = state.range(0);
    if (::posix_memalign(&memory, 64, size) != 0) abort();
    void* const end = static_cast<char*>(memory) + size;
    volatile Word* const p0 = static_cast<Word*>(memory);
    Word* const p1 = static_cast<Word*>(end);
    Word fill1; ::memset(&fill1, 0xab, sizeof(fill1));
    Word fill = fill1;

    for (auto _ : state) {
        for (volatile Word* p = p0; p != p1; ) {
            REPEAT(*p++ = fill;)
        }
        benchmark::ClobberMemory();
    }
    benchmark::DoNotOptimize(fill);
    ::free(memory);
    state.SetBytesProcessed(size*state.iterations());
    state.SetItemsProcessed((p1 - p0)*state.iterations());
    char buf[1024];
    snprintf(buf, sizeof(buf), "%lu", size);
    state.SetLabel(buf);
}


#define ARGS \
    ->RangeMultiplier(2)->Range(1<<10, 1<<30) \
    ->Threads(1)->Threads(2)->Threads(3)->Threads(4)->Threads(6)->Threads(8)->Threads(16)

 

 

위 벤치마크의 일반적인 결과는 아래와 같다. 디테일한 부분은 하드웨어마다 약간씩 다를 수 있다.

전체적인 주세는 예상이 가능하다. 그래프 왼쪽 부분부터 살펴보면, 왼쪽 부분은 L1 캐시(일반적으로 ~32KB)와 L2 캐시(일반적으로 256KB)에 의해서 제한된다는 것을 확인할 수 있다. 각 코어마다 별도의 L1 및 L2 캐시가 있으므로 데이터 크기가 L2 캐시에 맞다면 스레드들은 리소스를 공유하지 않으므로 스레드 간 상호작용이 없다. 실제로는 스레드 간 공유되는 다른 CPU 구성 요소가 있긴 하지만, 메모리 측면에서 봤을 때는 스레드 간 상호작용은 없다고 할 수 있다. 2개의 스레드의 처리량은 한 개의 스레드의 처리량보다 두 배 크다. 16개의 스레드의 처리량은 4개의 스레드보다 거의 4배 크다.

 

L2 캐시 크기를 초과한 뒤, L3 캐시와 메인 메모리로 넘어가게 되면 성능은 급격하게 떨어진다. 위 그래프 결과의 시스템에서 L3 캐시는 모든 CPU 코어 간에 공유된다. 또한, 메인 메모리도 공유된다. 이 그래프를 봤을 때, 스레드가 1, 2, 3, 4개일 때는 처리량이 각각 스레드 갯수에 비례한다. 즉, 메인 메모리는 4개의 프로세서가 쓰기 작업을 최고 속도로 할 수 있을만큼의 bandwidth를 가진다고 말할 수 있다. 그 이상으로 증가하면 성능은 떨어진다. 스레드가 6개에서 16개로 증가하더라도 처리량이 증가하지 않는다. 이때, 메모리 버스가 포화되었으며 이 상황에서는 메모리를 더 빨리 쓸 수 없게 된다.

Memory-Bound Programs and Concurrency

동일한 결과를 아래와 같이 다른 방식으로 표현할 수도 있다. 메모리 쓰기 속도를 각 스레드 갯수에 대해 상대적으로 표현하고 있고, 메모리 속도에 대한 동시성에 대해 집중하고 있다.

단일 스레드의 속도가 1라고 했을 때, L1 또는 L2 캐시에 데이터 크기가 맞는 경우에는 메모리 속도가 모든 스레드에서 거의 동일하게 유지된다는 것을 알 수 있다. 그러나 L3 캐시 또는 그 크기를 초과하면 4개의 스레드부터 속도가 느려지기 시작한다. 즉, 시스템에는 많은 스레드들이 데이터를 메모리에 빠르게 쓸 만큼 bandwidth가 충분하지 않다. 다양한 메모리 액세스 패턴에 대한 결과도 아마 비슷하지만, memory read bandwidth가 memory write bandwidth보다 성능이 좋은 경우가 많다.

 

단일 스레드의 경우, 프로그램이 memory-bound라면 메인메모리로 또는 메인메모리로부터 데이터가 이동하는 속도에 의해 성능이 제한됨을 알 수 있으며, 동시성으로 얻을 것이라고 기대하는 성능 향상에도 제한이 있다.

 

멀티 스레드 프로그램에서는 memory-bound를 피하는 것이 훨씬 중요하다. 여기에 유용한 기법은 L1 또는 L2 캐시에 맞는 더 작은 데이터셋에서 더 많은 작업을 수행할 수 있도록 하는 것이다. 또한, 메모리가 무작위가 아닌 순차적으로 액세스되도록 메모리 액세스 패턴도 최적화해야 한다. 구현 기법만으로 원하는 성능 향상을 얻을 수 없는 경우, 다음 단계는 알고리즘을 동시 프로그램에 맞게 수정하는 것이다. 동일한 문제를 해결하는 알고리즘에도 서로 다른 메모리 요구 사항이 필요한 경우가 많다. 단일 스레드 프로그램을 위한 가장 빠른 알고리즘보다 종종 동시성에 더 적합한 다른 알고리즘이 성능이 더 좋을 수 있다.

 

지금까지 살펴본 내용은 각 스레드가 서로 다른 스레드들과 완전히 독립적으로 자체 작업을 수행한다고 가정했다: 각 스레드는 각자 독립적인 메모리 공간을 가지고 있고, 이 메모리에 연산을 수행했다. 따라서, 스레드 간의 유일한 상호작용은 서로 공유하는 memory bandwidth와 같은 제한된 리소스에 대한 간접적인 경쟁이었다. 하지만 대부분의 프로그램에서 이와 같은 제한만 있는 것이 아니다.

 

Understanding the Cost of Memory Syncrhonization

다시 말하지만, 이전까지 살펴본 내용은 스레드 간의 상호작용 없이 동일한 시스템에서 여러 스레드를 실행하는 것에 관한 것이었다. 프로그램이 수행하는 작업을 각 스레드에 분할하여 독립적으로 수행하는 것이 가능하다면 그렇게 하는 것이 가장 좋다.

 

하지만 일반적으로 스레드들의 작업은 공통의 결과에 기여하기 때문에 서로 상호작용할 수 밖에 없다. 이러한 상호작용은 공유하는 리소스인 메모리로 통신하는 스레드에 의해 발생하게 된다. 이것으로 인해 미치는 성능 영향을 이해하는 것이 중요하다.

 

배열의 모든 요소의 합을 구하는 예제 코드를 생각해보자. 배열이 아주 크다고 가정했을 때, 더해야 할 값은 많지만 최종 결과는 하나이다. 배열의 요소를 더하는 작업을 여러 스레드에 분할하지만, 결과는 하나이므로 스레드들은 배열의 요소 값을 더할 때 서로 상호작용 해야 한다.

 

벤치마크로 이를 설명 그대로 구현하면 다음과 같다. 간단하게 표현하기 위해서 벤치마크에서는 덧셈은 값을 1씩 증가하는 연산으로 대체했다. 스레드 수가 증가하면, 증가한만큼 더하는 횟수가 배가 된다.

unsigned long x{0};
void BM_incr(benchmark::State& state) {
    for (auto _ : state) {
        REPEAT(benchmark::DoNotOptimize(++x);)
    }
    state.SetItemsProcessed(32*state.iterations());
}

static const long numcpu = sysconf(_SC_NPROCESSORS_CONF);
#define ARG \
    ->ThreadRange(1, numcpu) \
    ->UseRealTime()

벤치마크 함수는 각 스레드에서 호출되므로 이 함수 내부에 선언된 모든 변수는 각 스레드의 스택에 독립적으로 존재한다. 이와 같은 변수들은 공유되지 않는다. 모든 스레드들이 기여하는 공통의 결과를 얻으려면 벤치마크 함수 외부, 파일 범위에서 변수를 선언해야 한다.

 

물론 위 벤치마크는 전역 변수의 위치보다 더 큰 문제가 있다. 프로그램 자체가 잘못되었으며 최종 결과는 정의되지 않는다. 그 문제는 동일한 값을 증가시키는 스레드들에게 있다. 값을 증가시키는 작업은 단순히 한 단계로 이루어지는 것이 아니라 3단계로 진행되는 프로세스이다. 메모리에서 값을 레지스터로 읽고, 레지스터에서 값을 하나 증가시키고, 새 값을 다시 메모리에 쓴다. 모든 스레드들이 동시에 동일한 값을 얻고, 각 프로세서에서 별도로 증가시킨 후, 다시 메모리에 쓰는 것이 충분히 가능할 수 있다. 이 경우, 여러 스레드들이 결과에 기여했지만 최종 결과는 1이 된다. 이렇게 동일한 메모리 위치에 여러 스레드들이 쓰기 작업하는 것과 같은 경쟁을 데이터 레이스(data race)라고 한다.

 

동기화(syncrhonization)없이 여러 스레드에서 동일한 메모리 위치에 액세스하고, 이러한 액세스 중 적어도 하나가 write 작업인 경우에는 모든 프로그램이 undefined 결과를 생성한다. 어떤 순서로 작업이 수행되는지 파악할 필요도 없다. 동일한 메모리 위치에 액세스하는 두 개 이상의 스레드가 있을 때, 모든 액세스가 읽기 전용이거나 모든 액세스가 적절한 메모리 동기화를 사용하지 않는다면 데이터 경쟁이 발생하고 결과를 보장할 수 없다.

 

방금 위에서 살펴본 벤치마크 BM_incr에서는 결과 변수에 값을 쓰므로 read-only가 아니다. 기본적으로 메모리 동기화는 뮤텍스에 의해서 제공될 수 있는데, 스레드 간에 공유되는 변수에 대한 모든 액세스를 뮤텍스로 보호할 수 있다.

unsigned long x{0};
std::mutex m;
void BM_mutex_incr(benchmark::State& state) {
    for (auto _ : state) {
        REPEAT(
            {
                std::lock_guard<std::mutex> g(m);
                benchmark::DoNotOptimize(++x);
            }
        );
    }
    state.SetItemsProcessed(32*state.iterations());
}

뮤텍스를 이용한 락(lock)은 멀티스레드 프로그램의 정확성을 보장하는 가장 간단한 방법이지만, 성능 측면에서 파악하기가 어렵다. 뮤텍스는 상당히 복잡한 객체이며 일부 시스템콜을 포함한다.

 

메모리 동기화를 수행할 수 있는 조금 더 간단한 옵션인 원자성 변수(atomic variable)에 대해서 먼저 살펴보자. C++에는 변수를 atomic으로 선언할 수 있는 옵션을 제공한다. 이를 통해 제공되는 모든 작업은 중단되지 않는 단일 트랜잭션으로 수행된다. 이 변수를 관측하는 다른 모든 스레드들은 atomic 연산 이전 또는 이후에만 해당 변수의 상태를 볼 수 있으며 연산 도중은 관측할 수 없다.

 

지금 살펴보는 예제에서는 atomic increment 연산만 있으면 충분하다. Atomic 변수를 사용하도록 다음과 같이 벤치마크를 작성할 수 있다.

std::atomic<unsigned long> x1{0};
void BM_shared_incr(benchmark::State& state) {
    std::atomic<unsigned long>& x = x1;
    for (auto _ : state) {
        REPEAT(benchmark::DoNotOptimize(++x);)
    }
    state.SetItemsProcessed(32*state.iterations());
}

이 벤치마크에서는 더 이상 데이터 경쟁은 없다. 또한, 스레드 간 상호작용도 없으므로 우리는 스레드의 수가 두 배 증가하면 

 

위 벤치마크의 결과는 다음과 같다.

한 번의 증분에 걸리는 시간을 계산해보면 스레드가 증가할수록 오히려 증가하는 것을 확인할 수 있고, 스레드 갯수가 8개일 때부터는 스레드 하나일 때와 성능이 비슷한 것을 볼 수 있다. 스레드 갯수가 16개가 되면 한 번의 증분에 걸리는 시간이 스레드 한 개일 때의 절반이 걸린다.

 

뮤텍스를 사용한 벤치마크 결과에서는 스레드가 아무리 증가해도 스레드 한 개일 때보다 단일 증분 시간은 오히려 더 느려진다는 것을 확인할 수 있다.

우선 예상할 수 있듯이, 뮤텍스 락은 하나의 스레드를 사용할 때에서 상당한 비용이 드는 연산이다. 이는 아토믹 변수나 뮤텍스를 사용하지 않고 잘못된 결과를 생성하는 BM_incr 벤치마크 결과와 비교해보면 확실히 알 수 있다.

하나의 스레드에서 6.61ns가 걸리던 작업이 아토믹 변수와 뮤텍스 락을 사용하게 되면 각각 51.6ns, 126ns로 속도가 느려지게 된다. 전체적인 경향성을 봤을 때, 스레드 수가 증가하면 오히려 성능이 저하된다는 것을 보여준다. 프로그램에서 공유 데이터에 액세스하는 부분은 절대 확장되지 않는다는 것이다. 공유 데이터에 액세스할 때 얻을 수 있는 최고의 성능은 단일 스레드일 때이다. 동일한 데이터에 동시에 액세스하는 두 개 이상의 스레드가 있으면 성능이 저하될 수 있다. 물론 서로 다른 스레드가 서로 다른 시간에 동일한 데이터에 액세스하는 것은 서로 상호작용하지 않으므로 단일 스레드의 성능을 얻을 수 있다. 멀티스레드 프로그램에서의 성능상 이점은 동기화없이 스레드가 독립적으로 수행하는 연산으로부터 비롯되며, 정의에 따라 이러한 연산은 공유되지 않은 데이터에 대해 수행된다.

 

Why Data Sharing is Expensive

방금 살펴봤듯, 공유 데이터에 대한 동시 액세스는 성능을 저하시키는 요소이다. 직관적으로 이는 당연하다. 데이터 레이스를 피하려면 오직 하나의 스레드만 주어진 시간에 공유 데이터에 대해 작업해야 한다. 이러한 제한은 뮤텍스나 아토믹 연산을 사용하여 가능하다. 어느 것을 사용하든, 하나의 스레드가 연산을 수행 중이면 다른 모든 스레드는 기다려야 한다.

 

위의 실험에서 관측된 결과는 동시에 여러 스레드에서 공유 변수를 증가시키는 것은 확장되지 않으며, 실제로 하나의 스레드를 사용하는 것보다 느리다라는 것이다. 이는 아토믹 변수와 뮤텍스로 보호되는 일반 변수 모두에 해당된다. BM_incr 벤치마크에서 보호되지 않는 공유 데이터에 대한 액세스 성능 또한 측정했는데, 사실 이는 정의되지 않은 동작을 유발하므로 올바르지는 않다. 다만, 이 벤치마크의 성능을 통해 이러한 보호되지 않는 액세스가 적어도 총 메모리 bandwidth가 포화될 때까지 스레드 수에 따라 확장된다는 사실은 중요하다. 지금까지 살펴본 내용으로 아래의 두 가지 확실한 사실이 있다는 것을 알 수 있다.

• 공유 데이터에 대한 보호된 액세스는 느리다.
• 비공유 데이터에 대한 보호되지 않은 액세스는 빠르다.

이 사실로부터 데이터 공유가 프로그램의 성능을 느리게 만든다는 결론을 내리기에는 부족하다. 한 가지 놓친 성능 측정은 보호되는 데이터에 대한 비공유 액세스에 대한 측정이다. 하나의 스레드에서만 액세스하는 데이터에 대한 액세스는 사실 보호할 필요는 없지만, 공유 데이터에 대한 액세스 비용이 크다는 사실을 정확히 이해하기 위해 사용한다. 이를 위해 아래 두 벤치마크를 통해 성능을 측정해보자.

std::atomic<unsigned long> x2(0);
unsigned long x2a[1024];
void BM_false_shared_incr(benchmark::State& state) {
    unsigned long& x = x2a[state.thread_index()];
    size_t const N = state.range(0);
    for (auto _ : state) {
        for (size_t i = 0; i < N; i += 32) {
            REPEAT(benchmark::DoNotOptimize(++x);)
        }
        x2 += x;
    }
    state.SetItemsProcessed(N*state.iterations());
}

std::atomic<unsigned long> x3(0);
void BM_not_shared_incr(benchmark::State& state) {
    std::atomic<unsigned long> x;
    size_t const N = state.range(0);
    for (auto _ : state) {
        for (size_t i = 0; i < N; i += 32) {
            REPEAT(benchmark::DoNotOptimize(++x);)
        }
        x3 += x;
    }
    state.SetItemsProcessed(N*state.iterations());
}

첫 번째 벤치마크는 아토믹 변수에 대한 전역 배열을 만들고, 각 스레드가 자신의 아토믹 변수 요소에 액세스하도록 한다. 그리고 마지막에 그 결과를 전역 아토믹 변수에 취합한다. 두 번째 벤치마크는 벤치마크 함수 자체에 로컬 아토믹 변수를 선언하여 각 스레드가 이를 사용한다.

 

두 벤치마크의 성능 측정 결과는 다음과 같다. N의 크기는 1024로 설정하였다.

두 벤치마크 함수는 모두 증가시키는 변수가 스레드 간에 공유되지 않는다. 따라서, 두 스레드에서 실행하면 하나의 스레드보다 두 배 빠르게 실행될 것으로 예상할 수 있다. BM_not_shared_incr 벤치마크의 결과는 정확히 우리가 예상한 것과 같다.

 

하지만, BM_false_shared_incr 벤치마크의 결과는 이상하다. 전역 아토믹 변수 배열을 사용하지만, 각 스레드가 자체 배열 요소를 사용하므로 각 스레드 간에 공유되는 데이터는 없다. 하지만, 그 결과는 스레드 간 데이터가 공유되는 것과 같은 성능을 보여준다. 이와 같은 현상을 False Sharing(거짓 공유)라고 부른다. 실제로 공유되는 것은 없지만 프로그램은 데이터를 공유하는 것처럼 동작한다.

 

False Sharing

위 결과는 데이터를 공유하는 비용이 높은 이유가 이전에 가정했던 것보다 더 복잡하다는 것을 암시한다. False Sharing을 보여주는 벤치마크에서 각 배열 요소가 하나의 스레드에서만 액세스되므로 다른 스레드가 증분을 완료할 때까지 기다릴 필요가 없다. 그럼에도 성능 측정 결과는 각 스레드가 서로를 기다리는 것처럼 보인다. 이러한 현상을 이해하려면 캐시가 동작하는 방식에 대해서 이해해야 한다.

 

멀티코어 또는 멀티프로세서 시스템에서 프로세서와 메모리 사이에서 데이터가 이동하는 방식을 그림으로 표현하면 다음과 같다.

CPU는 L1 캐시에만 직접 액세스할 수 있고 L1 캐시로부터 데이터를 가지고 온다. 데이터가 메인메모리(RAM)에서 캐시로 이동하는 것은 훨씬 더 넓은 메모리 버스를 통해 복사된다. 메인메모리로부터 캐시로 복사할 수 있는 최소 데이터 크기를 캐시 라인(cache line)이라고 부른다. 모든 x86 CPU에서는 하나의 캐시 라인은 64바이트이다. CPU가 atomic increment와 같은 하나의 아토믹 트랜잭션을 위해 메모리 위치를 잠궈야(lock)하는 경우, 단지 하나의 단일 word에만 메모리를 쓰지만 캐시 라인 전체를 잠궈야 한다. 만약, 두 CPU가 동시에 동일한 캐시 라인에 쓸 수 있으면, 그 중 하나가 다른 CPU 결과를 덮어쓰게 된다. 위 그림은 단순하게 표현하기 위해서 캐시 계층 중 하나만 표시하고 있지만, 계층이 있더라도 달라지는 것은 없으며 데이터는 여전히 캐시 라인 단위로 이동하게 된다.

 

이러한 이유로 false sharing이 발생하게 된다. 인접한 배열 요소들이 스레드 간에 실제로 공유되지 않더라도 동일한 캐시 라인을 차지하고 있으면 데이터를 서로 공유하는 효과가 발생하게 된다. CPU가 아토믹 증분 연산을 위해 한 배열 요소에 대한 단독 액세스를 요청하면 이 배열 요소를 포함하는 전체 캐시 라인을 잠궈버리며, 다른 CPU는 동시에 그 안에 있는 데이터 요소에 액세스하지 못한다. 이는 스레드 갯수를 훨씬 더 많이 사용하여 벤치마크 성능을 측정해보면 알 수 있다. 128개의 스레드까지 사용하도록 하여 BM_false_shared_incr 벤치마크를 측정한 결과는 다음과 같다.

벤치마크 함수는 8바이트 크기의 요소에 대해 쓰기 작업을 수행하므로, 총 64바이트인 8개의 요소가 동일한 캐시 라인에 속하게 된다. 스레드가 8개만 있다면 실제 데이터를 공유하는 것과 같이 한 번에 하나의 CPU만 값을 증가시킬 수 있지만, 그 이상의 스레드에서는 배열 요소가 최소 2개의 캐시 라인에 걸쳐 위치하고 있으므로 두 개 이상의 CPU에서 독립적으로 값을 증가시킬 수 있게 된다.

 

반면, BM_not_shared_incr 벤치마크는 각 스레드의 스택 영역에 아토믹 변수를 할당한다. 따라서, 로컬 영역에 위치한 아토믹 변수는 서로 다른 캐시 라인에 위치하게 되고, 스레드들은 완전히 독립적으로 실행될 수 있다.

 

위 결과를 통해 공유 데이터에 액세스하는 데 비용이 높은 진짜 이유는 캐시 라인에 대한 독점적인 액세스 유지하고 모든 CPU가 캐시에 대해 일관적인 데이터를 갖도록 하기 때문이라는 것을 알 수 있다. 캐시 라인에서 단 하나의 비트라도 업데이트했다면 다른 모든 CPU의 모든 캐시에 있는 해당 캐시 라인의 복사본은 더이상 최신이 아니다. 다른 CPU가 동일한 캐시 라인의 데이터에 액세스하려면 먼저 메인메모리에서 업데이트된 것을 가져와야하는데, 앞서 살펴본 것처럼 이는 상당한 시간이 걸린다.

 

다시 말하지만, 두 스레드가 동일한 메모리 위치에 액세스하려고 시도하는지 여부는 중요하지 않다. 중요한 것은 독점적인 캐시 라인에 대한 액세스이며, 이는 공유 변수의 높은 비용의 근본 원인이다.

 

Mutex Lock

뮤텍스 락의 비용이 큰 이유를 이들이 포함하는 공유 데이터에서 찾을 수 있을지 궁금할 수 있다 (모든 락에는 일정 크기의 공유 데이터가 있어야 하며, 이것이 한 스레드에서 다른 스레드로 잠금이 수행되었다는 것을 알릴 수 있는 유일한 방법이다). 이전 벤치마크 결과에서 볼 수 있듯이 뮤텍스 락은 단일 스레드에서 아토믹 액세스보다 훨씬 더 비용이 크다. 즉, 뮤텍스 락에는 하나의 아토믹 변수에 대해 연산하는 것보다 더 많은 작업이 필요하다고 가정할 수 있다. 하지만 두 개 이상의 스레드에서 이 작업의 시간이 더 걸리는 이유는 어떻게 알 수 있을까? 이를 측정하기 위한 실험의 핵심은 락에 대해 false sharing을 설정하는 것이다. 즉, 스레드가 자체 뮤텍스 락에서 동작하지만 동일한 캐시 라인을 두고 경쟁하는 뮤텍스 배열을 사용하도록 한다. 실제 실험은 생각보다 더 복잡한데, 표준 C++ 뮤텍스인 std::mutex는 일반적으로 OS에 따라 40바이트에서 80바이트 사이 크기로 상당히 크다. 즉, 동일한 캐시 라인에 두 개도 넣지 못한다는 뜻이다. 따라서, spinlock이나 futex와 같은 더 작은 락을 사용하여 실험을 수행해야 한다.

 



 

이제 공유 데이터에 액세스하는 데 드는 비용이 큰 이유를 이해할 수 있다. 여기서 두 가지 중요한 내용을 알 수 있다.

 

첫 번째는 비공유 데이터를 생성할 때, false sharing을 방지해야 한다는 것이다. 의도하지 않은 false sharing은 성능에 큰 영향을 미친다. 물론 공유 데이터에 액세스하지 않는 것이 가장 좋으며, 적어도 자주 액세스하지 않도록 해야 한다. 위의 예제 코드를 통해 살펴본 것과 같은 배열의 합을 구하는 문제는 사실 더할 때마다 공유 메모리에 액세스할 필요는 없다. 스레드 내에서 로컬로 합을 계산한 이후, 마지막에 단 한 번만 공유 변수에 더해주면 된다.

 

이에 대한 성능 측정을 위한 벤치마크 함수는 다음과 같다.

std::atomic<unsigned long> x1{0};
void BM_local_incr(benchmark::State& state) {
    unsigned long x = 0;
    size_t const N = state.range(0);
    for (auto _ : state) {
        for (size_t i = 0; i < N; i += 32) {
            REPEAT(benchmark::DoNotOptimize(++x);)
        }
        x1 += x;
    }
    state.SetItemsProcessed(N*state.iterations());
}

std::atomic<unsigned long> x1a{0};
unsigned long local_sum[1024];
void BM_local_false_shared_incr(benchmark::State& state) {
    unsigned long& x = local_sum[state.thread_index()];
    size_t const N = state.range(0);
    for (auto _ : state) {
        for (size_t i = 0; i < N; i += 32) {
            REPEAT(benchmark::DoNotOptimize(++x);)
        }
        x1a += x;
    }
    state.SetItemsProcessed(N*state.iterations());
}

위 벤치마크에서 각 스레드는 모든 작업을 로컬에서 수행한 뒤, 정확히 단 한 번만 아토믹 변수에 액세스한다. 스레드 별로 부분합을 저장할 큰 배열을 전역에 만들고, 각 스레드에 작업할 고유한 배열 요소를 할당하여 사용할 수도 있다. 각 메모리에 대해 동시에 수행되는 액세스는 없지만 이 과정에서 false sharing의 함정에 빠질 수 있다. 배열의 인접한 요소는 보통 동일한 캐시 라인에 있으므로 성능에 영향을 미치게 된다. 따라서, 위와 같이 그냥 로컬 변수를 사용하여 부분합을 저장하는것이 좋다. 두 벤치마크의 성능 측정 결과를 통해서 결과를 확인해볼 수 있다.

결과를 통해 알 수 있듯이 false sharing이 있을 때 성능이 매우 좋지 않다. false sharing을 제거하면 속도가 상당히 증가한다.

 

두 번째는 공유 변수에 동시에 액세스하는 것은 비교적 비용이 크기 때문에 일반적으로 더 적은 수의 공유 변수를 사용하는 알고리즘이나 구현이 더 빠르게 수행될 수 있다는 것이다. 문제의 특성상 공유해야 할 데이터 양은 어느 정도 있을 수 있다. 로컬 변수로 부분합을 구하는 최적화를 적용하여 데이터에 대한 불필요한 액세스를 제거할 수 있지만, 부분합들을 모두 합하여 원하는 결과를 생성하기 위해서 액세스해야 하는 데이터가 있다. 따라서, 공유 변수를 제거하는 것에는 한계가 있을 수 있으며, 더 최적화하기 위해서는 공유 데이터에 대한 액세스뿐만 아니라 동시 프로그램을 작성하는 것 자체에 대해서도 이해를 해야 한다.