C++17 표준 라이브러리의 알고리즘 병렬화 소개
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
의 병렬 버전으로 대신할 수 있다.
-
'다음 절'은 핵심 C++ 표준 라이브러리 부록 A의 '새로 추가된 알고리즘' 단원을 말하는데, 조만간 이 블로그에도 올리겠습니다. ↩