HPX parallel partition 알고리즘
안녕하세요. 오늘은 제가 예전에 HPX 라는 오픈소스에 구현했던 parallel partition 알고리즘에 대해 간단히 소개하고 설명하는 시간을 가져보도록 하겠습니다. 출처 먼저 이 포스팅에서 다루는 알고리즘/코드의 출처는 다음과 같습니다. HPX : https://github.com/STEllAR-GROUP/hpx 관련 MR : https://github.com/STEllAR-GROUP/hpx/pull/2778 소스코드 : https://github.com/STEllAR-GROUP/hpx/blob/master/hpx/parallel/algorithms/partition.hpp 소개 parallel partition 알고리즘은 여러 개의 연산 유닛 (쉽게 말하면 cpu) 들을 이용해서 partition 알고리즘을 수행하는 것을 말합니다. 이 포스팅에서는 독자가 partition 알고리즘에 대해서 이미 알고있다고 가정합니다. partition 알고리즘에 대한 설명은 cppreference 를 참고하시기 바랍니다. 알고리즘 설명 partition 알고리즘은 주어진 영역을 정해진 규칙을 만족하는지 아닌지에 따라 두 영역으로 분류하는 알고리즘입니다. 예를 들어, 짝수인지 여부에 대해 partition 알고리즘을 수행한다고 하면 결과는 다음과 같습니다. 적용 전 : 3 5 7 4 2 1 9 8 6 적용 후 : 6 8 2 4 * 7 1 9 5 3 즉, partition 알고리즘의 핵심은 다음과 같습니다. 두 영역을 구분할 수 있는 boundary 를 찾는다. 그 boundary 의 왼쪽에는 조건을 만족하는 원소들이, 오른쪽에는 조건을 만족하지 않는 원소들이 위치하게 된다. 자, 위의 핵심을 기억하면서 parallel partition 알고리즘을 살펴보도록 합시다. 결론적으로 parallel partition 알고리즘은 크게 4단계로 이루어집니다. 주어진 영역을 여러 개의 block 으로 쪼개서 병렬로 sub-pa