[45] - Multithreading Execution Policy

Cppreference를 통해 C++의 다양한 기능들을 살펴보면서 자주 마주쳤던 단어인 Execution policy입니다. 예를 들면 다음과 같은 곳에서 자주 등장했습니다. Template Parameter list를 보면 나옵니다.

사족을 다 떼고 Execution Policy의 핵심만 정리하면 어떤 알고리즘에 대해서 다중코어를 사용하여 병렬처리를 할 수 있도록 만든다는 것입니다. 여태, 이 부분을 무시하고 알고리즘을 작성했기 때문에 Defualt 값으로 모든 알고리즘은 Single Threaded이며 단일 코어에서 동작했습니다. 그러나 Execution Policy를 통해서 다른 알고리즘을 선택한다면 다중 코어로 알고리즘을 처리하게 됩니다. 

이 전에 실험적 코드를 작성하며 한 번 사용한 적이 있는 par_unseq도 확인할 수 있습니다. 이 Execution Policy는 Class로 정의가 되어 있으며 해당 object를 만들어서 알고리즘에 넘겨주는 식으로 사용합니다. suffix에 _policy가 달려있는 것들이 class type들입니다. 하지만 구태여 object를 만들지 않아도 됩니다. 왜냐하면 Execution Policy 자체는 아무런 정보도 없고 Dynamic 하지도 않은 일종의 'Tag'의 기능만 하기 때문입니다. 그렇게 제공된 object들이 global execution policy objects입니다.

이 policy를 명시하는 행위는 Standard Library에게 어떤 알고리즘을 다중 코어를 사용하든 말든 안전하다는 사실을 알려주는 것과 같은 효과를 줍니다.

Execution Policy Types

가장 먼저 sequenced_policy를 살펴보면 결국 single thread에서 순차적으로 알고리즘을 수행하겠다는 뜻을 갖고 있습니다. 즉, 이 class는 Execution Policy를 명시하지 않았을 때 선택되는 Default 값입니다.

parallel_policy는 알고리즘을 다중 코어를 사용해서 진행하지만 vectorize는 허용하지 않겠다는 뜻입니다.

parallel_unsequenced_policy는 이 알고리즘을 다중 코어에서 동시에 돌려도 상관이 없으며 vectorize도 가능하다는뜻입니다. 마지막 unsequenced_policy는 단일 코어에서 동작해야 하고 vectorize도 할 수 없음을 명시합니다.

Muti-threaded Concurrency와 Vectorize에 대한 내용은 따로 공부하는게 나을 것 같습니다.

Execution Policy에 대한 실험 코드를 작성해보는 것이 좋겠습니다. 실제로 다중 코어를 사용하며 문제를 풀면 더 빠르게 풀리는지 알아봅니다. <execution> header file을 include해야 하며 가장 확실하게 실험을 해볼 수 있는 알고리즘은 정렬일 것입니다.

그러면 먼저 정렬을 위해서 Setup하는 함수를 만들어 보도록 하겠습니다.

기계에 따라 다르게 나올 것입니다.

이건 아무런 Execution Policy가 적용되지 않은 상태입니다. std::execution::par을 한 번 적용을 해보겠습니다.

? 더 느려졌읍니다

코드에 문제가 있을 수도 있습니다. 이론적으로는 더 빨라져야 합니다. 가령, 4개의 CPU를 갖고 있다면 아무튼 빨라지는 효과를 기대해 볼만할 것입니다.

?

다른 모든 정책을 실험해 보았으나 그냥 정책이 끼어들면 더 느려집니다. 다른 알고리즘에서도 시도를 해봐도 결과는 같습니다. 다중 코어 정책을 채택하면 더 성능이 떨어집니다. 다른 기계에서 시도를 해보는 것이 좋겠습니다.

이 코드도 똑같이 정책을 채택하면 느려집니다

(https://devblogs.microsoft.com/cppblog/using-c17-parallel-algorithms-for-better-performance/)GCC가 아니긴 하지만 참고할 만한 것 같습니다.

이번에는 조금 다른 실험을 진행했습니다. 벡터를 만드는 과정을 parallel하게 만들어 그렇지 않은 경우와 비교를 했습니다.

?

더 느려진 것은 둘째치고 크게 차이가 나지 않습니다. C++17 표준부터 지원이 되는 execution이라는 글을 읽어서 compiler을 할 때 옵션에 -std=gnu++17을 줘도 결과는 같았습니다. 그런데 MSVC Compiler를 쓰면 정상적으로 정책을 사용했을 때 더 빠르게 계산이 됐습니다. 뭐가 문제인지 고민을 해봐야 할 것 같습니다. 아래는 MSVC Compiler를 사용한 코드와 결과입니다. 

압도적으로 빠르게 나옵니다

이번에는 다음과 같은 코드를 짜봅니다. 같은 벡터 v에 대해서 한쪽에서는 single core정책을 채택하고 다른 쪽에서는 multi core 정책을 채택합니다.

컴파일 에러라든가 그런 요소는 없이 결과도 만족스럽습니다. 이번에는 이렇게 생각해봅니다. 두 개의 벡터를 같은 랜덤 변수 생성기[Random Number Engine]를 통해서 만든다고 가정해봅시다. 이걸 같은 Seed를 이용하여 두 개의 Sequences를 만들었다고 표현합니다. ( 문장 자체를 영어로 풀어보면 : Generate two sequences with the same seed in the same random number engine.과 같습니다. 이게 더 자연스러울 가능성도 있습니다.) 

이 코드의 예상되는 결과는 true입니다. 같은 Seed에서 만들어낸 벡터이기 때문이며 True를 반환할 것입니다.

하지만 False를 반환합니다. 이유는 굉장히 다양한데 몇 가지를 생각해 볼 수 있습니다. 먼저, 같은 Radom Number Generate Engine(이하, RNE)이라도 서로 다른 Thread에 리소스를 할당합니다. 같은 Seed에서 나온 값이라도 해당 값이 여기저기 흩어져 저장될 가능성이 있다는 말이기도 합니다. 

또 생각해 볼 수 있는 다른 가능성은 RNE Object에 대해서 여러 개의 Threads가 아무런 Mutex 정책 없이 마구 접근하기 때문에 실행 도중에 잘못된 혹은 정의되지 않은 행동을 하여 서로 같지 않은 값을 반환했을 가능성입니다. 이 케이스의 경우는 검증하기가 쉬운데 생성을 한 이후에 정렬을 해보면 답이 나옵니다. 

위와 완전히 같은 코드에 정렬만 추가합니다.

그럼에도 불구하고 false가 나옵니다. 그러면 예상했던 대로 아예 엔진이 Corrupt했을 가능성이 있습니다. 같은 시드를 통해 컨테이너의 요소를 'Parallel'의 정책을 채택했을 때 요소들이 뒤섞이는 것은 어쩔 수 없습니다. 하지만 이런 식으로 RNE가 망가지는 것은 막을 수 있습니다.

이 두 가지는 시스템 프로그래밍이나 운영체제 강의 시간에 자주 보았던 요소입니다. 문제를 다시 파악해보면, 같은 시드의 RNE이 muti thread 정책을 채택하면 망가진다는 것입니다. 그리고 Muti-threading의 문제를 해결하는 방법 중 하나는 mutex입니다.

다음과 같이 std::mutex의 인스턴스 mtx를 선언하고 해당 scope에서 lock을 하도록 하면 다른 thread에서도 똑같은 시도를 하겠으나 먼저 lock을 건 thread가 RNE을 사용할 때까지 다른 thread는 lock도 못하고 접근도 못할 것입니다. 즉, 순차적으로 처리가 될 것이란 의미입니다. 그럼 성능 자체는 현저히 느려지겠으나 RNE이 엉망이 되지 않고 위의 코드대로 만들어 정렬하여 비교하면 True가 나올 것입니다.

확실히 느려진 것이 보이지만 true를 반환하여 성공적으로 실험을 마쳤습니다. 그런데 다중 코어를 사용해도 단일 코어를 사용하는 것보다 느려지면 대체 무슨 의미가 있을까요? 그래서 반드시 공유하는 메모리에 대해서 접근할 때는 극도로 주의를 기울여 디자인을 해야합니다. 다중 코어 작업으로 만드는 것이 나은지, 단일 코어 작업으로 만드는 것이 나은지 정확하게 판단할 수 있어야 합니다.