C++17 표준 라이브러리의 알고리즘 병렬화 소개

"핵심 C++ 표준 라이브러리" 부록 A 중 C++17의 알고리즘 병렬화에 관한 글입니다. "순서 대로"와 "순차적으로"의 차이는 제 능력으로는 간단하게 설명하기가 좀 어렵네요. 언제 좀 더 풀어서 설명하는 글을 한 번 써보겠습니다.

알고리즘의 병렬화

C++17은 표준 라이브러리의 여러 알고리즘에 ‘병렬 실행’을 지원하는 중복적재 버전을 추가하며, 병렬 실행을 지원하는 새 알고리즘도 여럿 추가한다. 예를 들어 기존 알고리즘인 std::transform에는 다음과 같은 중복적재 버전들이 추가되었다.

FwdIt2 transform( ExePolicy&& policy, FwdItIt1 first1, FwdItIt1 last1,
                    FwdIt2 d_first, UnFunc func);
FwdIt3 transform( ExePolicy&& policy, FwdIt1 first1, FwdIt1 last1,
                    FwdIt2 first2, FwdIt3 d_first, BiFunc func );

모든 병렬 버전에서 템플릿 매개변수 ExePolicy는 실행 방침(execution policy)을 뜻하는 어떤 클래스로, 주된 용도는 중복적재 해소 과정에서 알고리즘의 병렬 버전이 선택되게 하는 것이다. C++17 표준 라이브러리의 std::execution 이름공간에는 다음과 같은 세 가지 구체적 실행 방침 클래스가 정의되어 있다(필요한 헤더는 <execution>).

• sequenced_policy 클래스
• parallel_policy 클래스
• parallel_unsequenced_policy 클래스

또한, 편의를 위해 std::execution::seq, std::execution::par, std::execution::par_unseq라는 인스턴스들(각각 sequenced_policy, parallel_policy, paralllel_unsequenced_policy의 인스턴스)이 미리 생성되어 있으므로, 특별한 이유가 없는 한 따로 객체를 생성할 필요 없이 이들을 바로 사용하면 된다(마치 cout을 사용할 때처럼).

병렬 알고리즘을 호출할 때 첫 인수로 seq를 지정하면 병렬 실행이 금지된다. 즉, 구현은 요소들을 반드시 현재 스레드(알고리즘을 호출한 스레드)에서 처리해야 한다. 이 방침에서 요소들이 반드시 원래 순서대로(in order) 처리된다는 보장은 없지만, 요소들이 순차적으로 처리된다(sequenced)는 보장은 있다. 다른 말로 하면, 한 스레드에서 어떤 한 요소의 처리가 끝나기 전에 다른 요소의 처리가 시작되는 일은 없다.

par를 지정하면 병렬 실행이 허용된다. 즉, 병렬 알고리즘 구현은 현재 스레드 이외의 스레드를 따로 생성해서 요소들을 처리할 수 있다. 이 경우에도 각 스레드는 요소들을 반드시 순차적으로 처리한다. 이 방침에서는 다중 스레드 상황이 벌어지므로 경쟁 조건이나 교착 상태가 발생할 수 있는데, 사용자가 지정한 호출 가능 단위로 요소에 접근하는 알고리즘의 경우 적절한 동기화로 그런 문제를 방지하는 것은 프로그래머의 몫이다. 예를 들어 다음은 C++17 표준 명세서 초안에 나오는 예로, 공유 변수 x에 대한 접근을 뮤텍스로 보호한다.

int x = 0;
std::mutex m;
int a[] = {1,2};
std::for_each(std::execution::par, std::begin(a), std::end(a), [&](int) {
  std::lock_guard<mutex> guard(m);
  ++x;
});

마지막으로, par_unseq를 지정한다는 것은 병렬 실행을 허용할 뿐만 아니라 순차 처리도 강제하지 않는다는 뜻이다. 순차 처리가 필수가 아니면 구현이 벡터화(vectorization)를 이용해서 좀 더 빠른 코드를 생성할 여지가 생긴다. 사용자가 지정한 호출 가능 단위로 요소에 접근하는 알고리즘의 경우, 벡터화에 따른 위험(교착 상태 등)은 프로그래머가 방지해야 한다. 다음은 앞의 예에서 par만 par_unseq로 대체한 코드로, 역시 C++17 초안에 나온 것이다.

int x = 0;
std::mutex m;
int a[] = {1,2};
std::for_each(std::execution::par_unseq, std::begin(a), std::end(a),
  [&](int) {
    std::lock_guard<mutex> guard(m); // 올바르지 않음: lock_guard 생성자는
                                     // m.lock()을 호출함.
    ++x;
});

구현이 for_each 루프를 하나의 스레드로 실행하기로 해도(par나 par_unseq는 병렬 실행을 허용하는 것일 뿐 강제하는 것은 아니므로, 필요하다면 구현은 그냥 하나의 스레드에서 알고리즘을 실행할 수 있다), 앞의 par 예제에서는 의해 순차 처리가 요구되므로 루프가 m.lock(); ++x; m.unlock(); m.lock(); ++x; m.unlock(); 형태로 실행된다. 따라서 교착 상태는 벌어지지 않는다. 그러나 이번 예제의 par_unseq 방침 하에서는 순차 처리가 필수가 아니므로 구현이 m.lock(); m.lock(); ++x; ++x; m.unlock(); m.unlock(); 형태의 코드를 생성할 수 있다. 그러면 한 스레드에서 같은 뮤텍스를 연달아 잠그려 해서 교착 상태가 발생한다.

표 A.2는 병렬 버전이 추가된 알고리즘들이다. 알고리즘 자체가 C++17에서 새롭게 추가된 경우는 굵은 글씨로 표시했다.

표 A.2 병렬 실행을 지원하는 표준 알고리즘

adjacent_difference, adjacent_find, all_of, any_of, copy, copy_if, copy_n, count, count_if, equal, exclusive_scan, fill, fill_n, find, find_end, find_first_of, find_if, find_if_not, for_each, for_each_n, generate, generate_n, includes, inclusive_scan, inner_product, inplace_merge, is_heap, is_heap_until, is_partitioned, is_sorted, is_sorted_until, lexicographical_compare, max_element, merge, min_element, minmax_element, mismatch, move, none_of, nth_element, partial_sort, partial_sort_copy, partition, partition_copy, reduce, remove, remove_copy, remove_copy_if, remove_if, replace, replace_copy, replace_copy_if, replace_if, reverse, reverse_copy, rotate, rotate_copy, search, search_n, set_difference, set_intersection, set_symmetric_difference, set_union, sort, stable_partition, stable_sort, swap_ranges, transform, transform_exclusive_scan, transform_inclusive_scan, transform_reduce, uninitialized_copy, uninitialized_copy_n, uninitialized_fill, uninitialized_fill_n, unique, unique_copy

병렬화의 이득을 볼 만한 기존 알고리즘 accumulate, inner_product, partial_sum에 병렬 버전이 추가되지 않은 점을 의아하게 생각하는 독자도 있을 텐데, 이 세 알고리즘의 병렬화는 다음 절^[1]에 나오는 reduce, transform_reduce, inclusive_scan의 병렬 버전으로 대신할 수 있다.