병렬 알고리즘

PPL(병렬 패턴 라이브러리)은 데이터 컬렉션에 대한 작업을 동시에 수행하는 알고리즘을 제공합니다. 이러한 알고리즘은 C++ 표준 라이브러리에서 제공하는 알고리즘과 유사합니다.

병렬 알고리즘은 동시성 런타임의 기존 기능으로 구성됩니다. 예를 들어 concurrency::p arallel_for 알고리즘은 동시성::structured_task_group 개체를 사용하여 병렬 루프 반복을 수행합니다. 알고리즘 파티션은 parallel_for 사용 가능한 컴퓨팅 리소스 수를 고려할 때 최적의 방식으로 작동합니다.

섹션

• parallel_for 알고리즘

• parallel_for_each 알고리즘

• parallel_invoke 알고리즘

• parallel_transform 및 parallel_reduce 알고리즘

  • parallel_transform 알고리즘

  • parallel_reduce 알고리즘

  • 예: 병렬로 맵 및 축소 수행

• 작업 분할

• 병렬 정렬

  • 정렬 알고리즘 선택

parallel_for 알고리즘

concurrency::p arallel_for 알고리즘은 동일한 작업을 병렬로 반복적으로 수행합니다. 이러한 각 작업은 반복 값으로 매개 변수화됩니다. 이 알고리즘은 해당 루프의 반복 간에 리소스를 공유하지 않는 루프 본문이 있는 경우에 유용합니다.

알고리즘은 parallel_for 병렬 실행을 위한 최적의 방법으로 작업을 분할합니다. 작업 부하가 분산되지 않은 경우 작업 가로채기 알고리즘과 범위 도용을 사용하여 이러한 파티션을 분산시킵니다. 한 루프 반복이 협조적으로 차단되면 런타임은 현재 스레드에 할당된 반복 범위를 다른 스레드 또는 프로세서에 재배포합니다. 마찬가지로 스레드가 반복 범위를 완료하면 런타임은 다른 스레드에서 해당 스레드로 작업을 재배포합니다. 이 알고리즘은 parallel_for 중첩된 병렬 처리도 지원합니다. 하나의 병렬 루프에 다른 병렬 루프가 포함된 경우 런타임은 병렬 실행을 위한 효율적인 방법으로 루프 본문 간의 처리 리소스를 조정합니다.

parallel_for 알고리즘에는 여러 개의 오버로드된 버전이 있습니다. 첫 번째 버전은 시작 값, 끝 값 및 작업 함수(람다 식, 함수 개체 또는 함수 포인터)를 사용합니다. 두 번째 버전은 시작 값, 끝 값, 단계별 값 및 작업 함수를 사용합니다. 이 함수의 첫 번째 버전은 1을 단계 값으로 사용합니다. 나머지 버전은 parallel_for가 여러 스레드 간에 범위를 분할하는 방법을 지정하는 파티셔너 개체를 사용합니다. 파티셔너에 대한 자세한 내용은 이 문서의 파티션 작업 섹션에 설명되어 있습니다.

여러 for 루프를 변환하여 사용할 parallel_for수 있습니다. 그러나 알고리즘은 parallel_for 다음과 같은 방법으로 문과 다릅니다 for .

• 알고리즘 parallel_for 은 parallel_for 미리 결정된 순서로 작업을 실행하지 않습니다.

• 알고리즘은 parallel_for 임의 종료 조건을 지원하지 않습니다. parallel_for 반복 변수의 현재 값이 1보다 last작은 경우 알고리즘이 중지됩니다.

• 형식 매개 변수는 _Index_type 정수 형식이어야 합니다. 이 정수 계열 형식은 서명되거나 서명되지 않을 수 있습니다.

• 루프 반복은 전달되어야 합니다. 매개 변수가 1보다 작은 경우 알고리즘은 parallel_for std::invalid_argument 형식의 예외를 _Step throw합니다.

• 알고리즘에 대한 예외 처리 메커니즘은 parallel_for 루프의 메커니즘과 for 다릅니다. 병렬 루프 본문에서 동시에 여러 예외가 발생하는 경우 런타임은 예외 중 하나만 호출 parallel_for된 스레드에 전파합니다. 또한 하나의 루프 반복에서 예외를 throw하는 경우 런타임은 전체 루프를 즉시 중지하지 않습니다. 대신 루프가 취소된 상태로 배치되고 런타임은 아직 시작되지 않은 모든 작업을 삭제합니다. 예외 처리 및 병렬 알고리즘에 대한 자세한 내용은 예외 처리를 참조 하세요.

알고리즘은 임의 parallel_for 종료 조건을 지원하지 않지만 취소를 사용하여 모든 작업을 중지할 수 있습니다. 취소에 대한 자세한 내용은 PPL의 취소를 참조하세요.

참고 항목

부하 분산 및 취소와 같은 기능에 대한 지원으로 인한 예약 비용은 특히 루프 본문이 상대적으로 작은 경우 루프 본문을 병렬로 실행하는 이점을 극복하지 못할 수 있습니다. 병렬 루프에 파티셔너를 사용하여 이러한 오버헤드를 최소화할 수 있습니다. 자세한 내용은 이 문서의 뒷부분에 있는 분할 작업을 참조하세요.

예시

다음 예제에서는 알고리즘의 parallel_for 기본 구조를 보여줍니다. 다음은 [1, 5] 범위의 각 값을 콘솔에 병렬로 출력하는 예제입니다.

// parallel-for-structure.cpp
// compile with: /EHsc
#include <ppl.h>
#include <array>
#include <sstream>
#include <iostream>

using namespace concurrency;
using namespace std;

int wmain()
{
   // Print each value from 1 to 5 in parallel.
   parallel_for(1, 6, [](int value) {
      wstringstream ss;
      ss << value << L' ';
      wcout << ss.str();
   });
}

이 예제에서는 다음 샘플 출력을 생성합니다.

1 2 4 3 5

알고리즘은 parallel_for 각 항목에서 병렬로 작동하므로 값이 콘솔에 인쇄되는 순서는 달라집니다.

알고리즘을 사용하는 전체 예제는 parallel_for 방법: parallel_for 루프 작성을 참조 하세요.

[맨 위로 이동]

parallel_for_each 알고리즘

concurrency::p arallel_for_each 알고리즘은 C++ 표준 라이브러리에서 제공하는 것과 같은 반복 컨테이너에 대한 작업을 병렬로 수행합니다. 알고리즘에서 사용하는 것과 동일한 분할 논리를 parallel_for 사용합니다.

알고리즘은 parallel_for_each 작업을 동시에 실행한다는 parallel_for_each 점을 제외하고 C++ 표준 라이브러리 std::for_each 알고리즘과 유사합니다. 다른 병렬 알고리즘과 parallel_for_each 마찬가지로 특정 순서로 작업을 실행하지 않습니다.

알고리즘은 전달 반복기와 임의 parallel_for_each 액세스 반복기 모두에서 작동하지만 임의 액세스 반복기를 사용하여 더 잘 수행됩니다.

예시

다음 예제에서는 알고리즘의 parallel_for_each 기본 구조를 보여줍니다. 다음은 std::array 개체의 각 값을 콘솔에 병렬로 출력하는 예제입니다.

// parallel-for-each-structure.cpp
// compile with: /EHsc
#include <ppl.h>
#include <array>
#include <sstream>
#include <iostream>

using namespace concurrency;
using namespace std;

int wmain()
{
   // Create an array of integer values.
   array<int, 5> values = { 1, 2, 3, 4, 5 };

   // Print each value in the array in parallel.
   parallel_for_each(begin(values), end(values), [](int value) {
      wstringstream ss;
      ss << value << L' ';
      wcout << ss.str();
   });
}
/* Sample output:
   5 4 3 1 2
*/

이 예제에서는 다음 샘플 출력을 생성합니다.

4 5 1 2 3

알고리즘은 parallel_for_each 각 항목에서 병렬로 작동하므로 값이 콘솔에 인쇄되는 순서는 달라집니다.

알고리즘을 사용하는 전체 예제는 parallel_for_each 방법: parallel_for_each 루프 작성을 참조 하세요.

[맨 위로 이동]

parallel_invoke 알고리즘

concurrency::p arallel_invoke 알고리즘은 태스크 집합을 병렬로 실행합니다. 각 작업이 완료될 때까지 반환되지 않습니다. 이 알고리즘은 동시에 실행하려는 여러 독립 작업이 있는 경우에 유용합니다.

알고리즘은 parallel_invoke 일련의 작업 함수(람다 함수, 함수 개체 또는 함수 포인터)를 매개 변수로 사용합니다. 알고리즘은 parallel_invoke 2~10개의 매개 변수를 사용하도록 오버로드됩니다. 전달하는 모든 함수는 0 매개 변수를 parallel_invoke 사용해야 합니다.

다른 병렬 알고리즘과 parallel_invoke 마찬가지로 특정 순서로 작업을 실행하지 않습니다. 작업 병렬 처리 항목에서는 알고리즘이 parallel_invoke 작업 및 작업 그룹과 어떻게 관련되어 있는지 설명합니다.

예시

다음 예제에서는 알고리즘의 parallel_invoke 기본 구조를 보여줍니다. 이 예제에서는 세 개의 지역 변수에 대해 함수를 동시에 호출 twice 하고 결과를 콘솔에 출력합니다.

// parallel-invoke-structure.cpp
// compile with: /EHsc
#include <ppl.h>
#include <string>
#include <iostream>

using namespace concurrency;
using namespace std;

// Returns the result of adding a value to itself.
template <typename T>
T twice(const T& t) {
   return t + t;
}

int wmain()
{
   // Define several values.
   int n = 54;
   double d = 5.6;
   wstring s = L"Hello";

   // Call the twice function on each value concurrently.
   parallel_invoke(
      [&n] { n = twice(n); },
      [&d] { d = twice(d); },
      [&s] { s = twice(s); }
   );

   // Print the values to the console.
   wcout << n << L' ' << d << L' ' << s << endl;
}

이 예제는 다음과 같은 출력을 생성합니다.

108 11.2 HelloHello

알고리즘을 사용하는 parallel_invoke 전체 예제는 방법: parallel_invoke 사용하여 병렬 정렬 루틴 작성 및 방법: parallel_invoke 사용하여 병렬 작업 실행

[맨 위로 이동]

parallel_transform 및 parallel_reduce 알고리즘

concurrency::p arallel_transform 및 concurrency::p arallel_reduce 알고리즘은 각각 std::transform 및 std::accumulate C++ 표준 라이브러리 알고리즘의 병렬 버전입니다. 동시성 런타임 버전은 병렬로 실행되기 때문에 작업 순서가 결정되지 않는다는 점을 제외하고 C++ 표준 라이브러리 버전처럼 동작합니다. 병렬 처리에 따른 성능 및 확장성 효과를 볼만큼 큰 집합으로 작업할 때 이 알고리즘을 사용합니다.

Important

parallel_transform 및 parallel_reduce 알고리즘은 임의 액세스, 양방향 및 정방향 반복기만 지원합니다. 이들 반복기는 안정적인 메모리 주소를 생성하기 때문입니다. 또한 이들 반복기는 비const l-value를 생성해야 합니다.

parallel_transform 알고리즘

parallel transform 알고리즘을 사용하여 많은 데이터 병렬화 작업을 수행할 수 있습니다. 이렇게 시작할 수 있는 작업의 예는 다음과 같습니다.

• 이미지 밝기를 조정하고 기타 이미지 처리 작업을 수행합니다.

• 두 벡터의 내적을 계산하거나 합을 구하고 벡터에 대한 다른 숫자 계산을 수행합니다.

• 각 반복이 렌더링해야 하는 하나의 픽셀을 참조하는 3차원 레이 추적을 수행합니다.

다음 예제에서는 parallel_transform 알고리즘을 호출하는데 사용되는 기본 구조를 보여줍니다. 이 예제에서는 두 가지 방법으로 std::vector 개체의 각 요소를 부정합니다. 첫 번째 방법은 람다 식을 사용합니다. 두 번째 방법은 std::unary_function 파생되는 std::negate를 사용합니다.

// basic-parallel-transform.cpp
// compile with: /EHsc
#include <ppl.h>
#include <random>

using namespace concurrency;
using namespace std;

int wmain()
{
    // Create a large vector that contains random integer data.
    vector<int> values(1250000);
    generate(begin(values), end(values), mt19937(42));

    // Create a vector to hold the results.
    // Depending on your requirements, you can also transform the 
    // vector in-place.
    vector<int> results(values.size());

    // Negate each element in parallel.
    parallel_transform(begin(values), end(values), begin(results), [](int n) {
        return -n;
    });

    // Alternatively, use the negate class to perform the operation.
    parallel_transform(begin(values), end(values), begin(values), negate<int>());
}

Warning

이 예제에서는 parallel_transform의 기본적인 사용 방법을 설명합니다. 작업 함수가 상당한 양의 작업을 수행하지 않으므로 이 예제에서 큰 성능 향상이 필요하지는 않습니다.

parallel_transform 알고리즘에는 두 개의 오버로드가 있습니다. 첫 번째 오버로드는 하나의 입력 범위와 하나의 단항 함수를 사용합니다. 단항 함수는 하나의 인수, 함수 개체 또는 unary_function에서 파생되는 형식을 사용하는 람다 식일 수 있습니다. 두 번째 오버로드는 두 개의 입력 범위와 하나의 이진 함수를 사용합니다. 이진 함수는 두 인수, 함수 개체 또는 std::binary_function 파생되는 형식을 사용하는 람다 식일 수 있습니다. 다음 예제에서는 이러한 차이를 보여줍니다.

//
// Demonstrate use of parallel_transform together with a unary function.

// This example uses a lambda expression.
parallel_transform(begin(values), end(values), 
    begin(results), [](int n) { 
        return -n;
    });

// Alternatively, use the negate class:
parallel_transform(begin(values), end(values), 
    begin(results), negate<int>());

//
// Demonstrate use of parallel_transform together with a binary function.

// This example uses a lambda expression.
parallel_transform(begin(values), end(values), begin(results), 
    begin(results), [](int n, int m) {
        return n * m;
    });

// Alternatively, use the multiplies class:
parallel_transform(begin(values), end(values), begin(results), 
    begin(results), multiplies<int>());

Important

parallel_transform의 출력에 제공하는 반복기는 입력 반복기와 완전히 겹치거나 아예 겹치지 않아야 합니다. 입력 및 출력 반복기가 부분적으로 겹치는 경우 이 알고리즘의 동작은 지정되지 않습니다.

parallel_reduce 알고리즘

parallel_reduce 알고리즘은 결합형 속성을 만족하는 작업 시퀀스가 있을 경우 유용합니다. (이 알고리즘에는 통근 속성이 필요하지 않습니다.) 다음은 수행할 수 있는 몇 가지 작업입니다.parallel_reduce

• 매트릭스 시퀀스를 곱하여 매트릭스를 구합니다.

• 벡터에 매트릭스 시퀀스를 곱하여 벡터를 구합니다.

• 문자열 시퀀스의 길이를 컴퓨팅합니다.

• 한 요소에 문자열과 같은 요소의 목록을 결합합니다.

다음 기본 예제에서는 parallel_reduce 알고리즘을 사용하여 문자열 시퀀스를 한 문자열로 결합하는 방법을 보여줍니다. parallel_transform에 대한 예제와 같이 이 기본 예제에서는 성능 향상이 필요하지 않습니다.

// basic-parallel-reduce.cpp
// compile with: /EHsc
#include <ppl.h>
#include <iostream>
#include <string>
#include <vector>

using namespace concurrency;
using namespace std;

int wmain()
{
  // Create a vector of strings.
  vector<wstring> words{
      L"Lorem ",
      L"ipsum ",
      L"dolor ",
      L"sit ",
      L"amet, ",
      L"consectetur ",
      L"adipiscing ",
      L"elit."};
      
  // Reduce the vector to one string in parallel.
  wcout << parallel_reduce(begin(words), end(words), wstring()) << endl;
}

/* Output:
   Lorem ipsum dolor sit amet, consectetur adipiscing elit.
*/

대부분의 경우 동시성::결합 가능한 클래스와 함께 알고리즘을 parallel_for_each 사용하기 위한 약식이라고 생각할 parallel_reduce 수 있습니다.

예: 병렬로 맵 및 축소 수행

맵 작업은 시퀀스의 각 값에 함수를 적용합니다. 축소 작업은 시퀀스의 요소를 하나의 값으로 결합합니다. C++ 표준 라이브러리 std::transform 및 std::accumulate 함수를 사용하여 맵 및 축소 작업을 수행할 수 있습니다. 그러나 많은 문제에 대해 parallel_transform 알고리즘을 사용하여 매핑 작업을 병렬로 수행하고, parallel_reduce 알고리즘을 사용하여 줄이기 작업을 병렬로 수행할 수 있습니다.

다음 예제에서는 연속 및 병렬 방식으로 소수의 합을 컴퓨팅하는데 걸리는 시간을 비교합니다. 매핑 단계에서 소수가 아닌 값을 0으로 변환하고, 줄이기 단계에서 값의 합을 구합니다.

// parallel-map-reduce-sum-of-primes.cpp
// compile with: /EHsc
#include <windows.h>
#include <ppl.h>
#include <array>
#include <numeric>
#include <iostream>

using namespace concurrency;
using namespace std;

// Calls the provided work function and returns the number of milliseconds 
// that it takes to call that function.
template <class Function>
__int64 time_call(Function&& f)
{
   __int64 begin = GetTickCount();
   f();
   return GetTickCount() - begin;
}

// Determines whether the input value is prime.
bool is_prime(int n)
{
   if (n < 2)
      return false;
   for (int i = 2; i < n; ++i)
   {
      if ((n % i) == 0)
         return false;
   }
   return true;
}

int wmain()
{   
   // Create an array object that contains 200000 integers.
   array<int, 200000> a;

   // Initialize the array such that a[i] == i.
   iota(begin(a), end(a), 0);

   int prime_sum;
   __int64 elapsed;

   // Compute the sum of the numbers in the array that are prime.
   elapsed = time_call([&] {
       transform(begin(a), end(a), begin(a), [](int i) { 
         return is_prime(i) ? i : 0; 
      });
      prime_sum = accumulate(begin(a), end(a), 0);
   });   
   wcout << prime_sum << endl;   
   wcout << L"serial time: " << elapsed << L" ms" << endl << endl;

   // Now perform the same task in parallel.
   elapsed = time_call([&] {
      parallel_transform(begin(a), end(a), begin(a), [](int i) { 
         return is_prime(i) ? i : 0; 
      });
      prime_sum = parallel_reduce(begin(a), end(a), 0);
   });
   wcout << prime_sum << endl;
   wcout << L"parallel time: " << elapsed << L" ms" << endl << endl;
}
/* Sample output:
   1709600813
   serial time: 7406 ms
   
   1709600813
   parallel time: 1969 ms
*/

맵 및 축소 작업을 병렬로 수행하는 또 다른 예제는 방법: 병렬로 맵 및 축소 작업 수행을 참조하세요.

[맨 위로 이동]

작업 분할

데이터 원본에 대한 작업을 병렬화하려면 원본을 여러 스레드에서 동시에 액세스할 수 있는 여러 섹션으로 분할 하는 것이 중요합니다. 파티셔너는 병렬 알고리즘이 여러 스레드로 범위를 분할하는 방법을 지정합니다. 이 문서의 앞부분에서 설명한 바와 같이 PPL은 초기 작업 부하를 만든 다음 작업 부하가 분산되지 않은 경우 작업 가로채기 알고리즘과 범위 도용을 사용하여 이러한 파티션을 분산시키는 기본 분할 메커니즘을 사용합니다. 예를 들어, 하나의 루프 반복이 반복 범위를 마치면 런타임에서 스레드 간에 작업을 재배포합니다. 그러나 시나리오에 따라 문제에 더 적합한 다른 분할 메커니즘을 지정할 수 있습니다.

parallel_for, parallel_for_each 및 parallel_transform 알고리즘은 추가 매개 변수인 _Partitioner를 사용하는 오버로드된 버전을 제공합니다. 이 매개 변수는 작업을 나누는 파티셔너 형식을 정의합니다. 다음은 PPL이 정의하는 파티셔너 종류입니다.

concurrency::affinity_partitioner
작업을 고정된 범위 수(대개 루프 작업에 사용 가능한 작업자 스레드 수)로 나눕니다. 이 파티셔너 형식은 static_partitioner와 유사하지만 작업자 스레드에 범위를 매핑하는 방식으로 캐시 선호도를 향상시킵니다. 이 파티셔너 형식은 같은 데이터 집합에 대해 루프가 여러 번 실행되고(예: 루프 내 루프) 데이터가 캐시에 맞을 때 성능을 향상시킬 수 있습니다. 이 파티셔너는 취소에 완전히 참여하지 않습니다. 또한 협조적 차단 기능을 사용하지 않으므로 정방향 종속성을 가진 병렬 루프와 함께 사용할 수 없습니다.

동시성::auto_partitioner
작업을 초기 범위 수(대개 루프 작업에 사용 가능한 작업자 스레드 수)로 나눕니다. _Partitioner 매개 변수를 사용하는 오버로드된 병렬 알고리즘을 호출하지 않는 경우 런타임에서 기본적으로 이 형식을 사용합니다. 각 범위를 하위 범위로 나눌 수 있어 부하 분산이 가능합니다. 작업 범위가 완료되면 런타임에서 스레드 간에 작업의 하위 범위를 재배포합니다. 작업 부하가 다른 범주 중 하나에 속하지 않거나 취소 또는 협조적 차단을 위한 모든 지원이 필요할 경우 이 파티셔너를 사용하십시오.

동시성::simple_partitioner
각 반복에 주어진 청크 크기로 지정되는 반복 수 이상이 있도록 작업을 여러 범위로 나눕니다. 이 파티셔너 형식은 부하 분산에 참여하지만 런타임에서 범위를 하위 범위로 나누지 않습니다. 각 작업자에 대해 런타임에서 취소를 확인하고 _Chunk_size 반복 완료 후 부하 분산을 수행합니다.

concurrency::static_partitioner
작업을 고정된 범위 수(대개 루프 작업에 사용 가능한 작업자 스레드 수)로 나눕니다. 이 파티셔너 형식은 작업 가로채기를 사용하지 않아 오버헤드가 적기 때문에 성능을 향상시킬 수 있습니다. 병렬 루프의 각 반복이 고정되고 균일한 양의 작업을 수행하며, 취소 또는 정방향 협조적 차단에 대한 지원이 필요 없는 경우 이 파티셔너 형식을 사용합니다.

Warning

및 parallel_transform 알고리즘은 parallel_for_each 정적, 단순 및 선호도 파티셔너에 대해 임의 액세스 반복기(예: std::vector)를 사용하는 컨테이너만 지원합니다. 양방향 및 정방향 반복기를 사용하는 컨테이너는 컴파일 시간 오류를 발생시킵니다. 기본 파티셔너인 auto_partitioner는 이러한 세 가지 반복기 형식을 모두 지원합니다.

일반적으로 이러한 파티셔너는 affinity_partitioner를 제외하고 동일한 방식으로 사용됩니다. 대부분의 파티셔너 형식은 상태를 유지하지 않고 런타임에 의해 수정되지 않습니다. 따라서 다음 예제와 같이 호출 지점에 이러한 파티셔너 개체를 만들 수 있습니다.

// static-partitioner.cpp
// compile with: /EHsc
#include <ppl.h>

using namespace concurrency;

void DoWork(int n)
{
    // TODO: Perform a fixed amount of work...
}

int wmain()
{
    // Use a static partitioner to perform a fixed amount of parallel work.
    parallel_for(0, 100000, [](int n) {
        DoWork(n);
    }, static_partitioner());
}

하지만 알고리즘에서 이후 루프에 다시 사용할 상태를 저장할 수 있게 l-value 참조인 비affinity_partitioner로 const 개체를 전달해야 합니다. 다음 예제에서는 데이터 세트에 대해 동일한 작업을 여러 번 병렬로 수행하는 기본 애플리케이션을 보여줍니다. affinity_partitioner를 사용하면 배열이 캐시에 맞을 가능성이 높기 때문에 성능이 향상될 수 있습니다.

// affinity-partitioner.cpp
// compile with: /EHsc
#include <ppl.h>
#include <array>

using namespace concurrency;
using namespace std;

int wmain()
{
    // Create an array and fill it with zeroes.
    array<unsigned char, 8 * 1024> data;
    data.fill(0);

    // Use an affinity partitioner to perform parallel work on data
    // that is likely to remain in cache.
    // We use the same affinitiy partitioner throughout so that the 
    // runtime can schedule work to occur at the same location for each 
    // iteration of the outer loop.

    affinity_partitioner ap;
    for (int i = 0; i < 100000; i++)
    {
        parallel_for_each(begin(data), end(data), [](unsigned char& c)
        {
            c++;
        }, ap);
    }
}

주의

협조적 차단 기능으로 static_partitioner 또는 affinity_partitioner를 사용하는 기존 코드를 수정할 때 주의하십시오. 이러한 파티셔너 형식은 부하 분산이나 범위 도용을 사용하지 않으므로 애플리케이션 동작을 변경할 수 있습니다.

해당 시나리오에서 파티셔너를 사용할지 여부를 결정하려면 대표적인 부하 및 컴퓨터 구성에서 작업 완료에 걸리는 시간을 실제로 측정하는 것이 가장 좋습니다. 예를 들어 정적 분할은 몇 개의 코어만 있는 멀티 코어 컴퓨터에서 상당한 속도 향상을 제공할 수 있지만, 비교적 많은 코어가 있는 컴퓨터에서는 속도 저하가 발생할 수 있습니다.

[맨 위로 이동]

병렬 정렬

PPL은 concurrency::p arallel_sort, concurrency::p arallel_buffered_sort 및 concurrency::p arallel_radixsort의 세 가지 정렬 알고리즘을 제공합니다. 이러한 정렬 알고리즘은 병렬로 정렬의 효과를 볼 수 있는 데이터 집합이 있는 경우 유용합니다. 특히 병렬로 정렬은 큰 데이터 세트이 있거나 많은 계산이 필요한 비교 작업을 사용하여 데이터를 정렬할 때 유용합니다. 각 알고리즘은 요소를 정렬합니다.

parallel_sort 및 parallel_buffered_sort 알고리즘은 모두 비교 기반 알고리즘입니다. 즉, 값으로 요소를 비교합니다. parallel_sort 알고리즘은 추가 메모리 요구 사항이 없으며 범용 정렬에 적합합니다. 알고리즘은 parallel_buffered_sort 보다 parallel_sort더 나은 성능을 발휘할 수 있지만 O(N) 공간이 필요합니다.

parallel_radixsort 알고리즘은 해시 기반입니다. 즉, 정수 키를 사용하여 요소를 정렬합니다. 이 알고리즘은 비교를 사용하지 않고 키를 사용하여 요소의 대상을 직접 컴퓨팅합니다. 마찬가지로 parallel_buffered_sort이 알고리즘에는 O(N) 공간이 필요합니다.

다음 표에는 세 가지 병렬 정렬 알고리즘의 중요 속성이 요약되어 있습니다.

알고리즘	설명	정렬 메커니즘	정렬 안정성	메모리 요구 사항	시간 복잡도	반복기 액세스
parallel_sort	범용 비교 기반 정렬입니다.	비교 기반(오름차순)	불안정	None	O((N/P)log(N/P) + 2N((P-1)/P))	임의
parallel_buffered_sort	O(N) 공간이 필요한 보다 빠른 범용 비교 기반 정렬입니다.	비교 기반(오름차순)	불안정	추가 O(N) 공간이 필요합니다.	O((N/P)log(N))	임의
parallel_radixsort	O(N) 공간이 필요한 정수 키 기반 정렬입니다.	해시 기반	안정	추가 O(N) 공간이 필요합니다.	O(N/P)	임의

다음 그림은 세 가지 병렬 정렬 알고리즘의 중요 속성을 그래픽으로 보여줍니다.

이러한 병렬 정렬 알고리즘은 취소 및 예외 처리의 규칙을 따릅니다. 동시성 런타임의 취소 및 예외 처리에 대한 자세한 내용은 병렬 알고리즘 및 예외 처리 취소를 참조하세요.

팁

병렬 정렬 알고리즘은 이동 의미 체계를 지원합니다. 보다 효율적인 스왑 작업을 위해 이동 할당 연산자를 정의할 수 있습니다. 이동 의미 체계 및 이동 할당 연산 자에 대한 자세한 내용은 Rvalue 참조 선언자: && 이동 생성자 및 이동 할당 연산자(C++)를 참조하세요. 이동 할당 연산자나 스왑 함수를 제공하지 않으면 정렬 알고리즘에서 복사 생성자를 사용합니다.

다음 기본 예제에서는 parallel_sort를 사용하여 vector 값의 int를 정렬하는 방법을 보여줍니다. 기본적으로 parallel_sort std::less를 사용하여 값을 비교합니다.

// basic-parallel-sort.cpp
// compile with: /EHsc
#include <ppl.h>
#include <random>
#include <iostream>

using namespace concurrency;
using namespace std;

int wmain()
{
    // Create and sort a large vector of random values.
    vector<int> values(25000000);
    generate(begin(values), end(values), mt19937(42));
    parallel_sort(begin(values), end(values));

    // Print a few values.
    wcout << "V(0)        = " << values[0] << endl;
    wcout << "V(12500000) = " << values[12500000] << endl;
    wcout << "V(24999999) = " << values[24999999] << endl;
} 
/* Output:
   V(0)        = -2147483129
   V(12500000) = -427327
   V(24999999) = 2147483311
*/

이 예제에서는 사용자 지정 비교 함수를 제공하는 방법을 보여줍니다. std::complex::real 메서드를 사용하여 std::complex<double> 값을 오름차순으로 정렬합니다.

// For this example, ensure that you add the following #include directive:
// #include <complex>

// Create and sort a large vector of random values.
vector<complex<double>> values(25000000);
generate(begin(values), end(values), mt19937(42));
parallel_sort(begin(values), end(values),
    [](const complex<double>& left, const complex<double>& right) {
        return left.real() < right.real();
    });

// Print a few values.
wcout << "V(0)        = " << values[0] << endl;
wcout << "V(12500000) = " << values[12500000] << endl;
wcout << "V(24999999) = " << values[24999999] << endl;
/* Output:
   V(0)        = (383,0)
   V(12500000) = (2.1479e+009,0)
   V(24999999) = (4.29497e+009,0)
*/

이 예제에서는 parallel_radixsort 알고리즘에 해시 함수를 제공하는 방법을 보여줍니다. 이 예제는 3차원 점을 정렬합니다. 점은 참조 위치와의 거리를 기준으로 정렬됩니다.

// parallel-sort-points.cpp
// compile with: /EHsc
#include <ppl.h>
#include <random>
#include <iostream>

using namespace concurrency;
using namespace std;

// Defines a 3-D point.
struct Point
{
    int X;
    int Y;
    int Z;
};

// Computes the Euclidean distance between two points.
size_t euclidean_distance(const Point& p1, const Point& p2)
{
    int dx = p1.X - p2.X;
    int dy = p1.Y - p2.Y;
    int dz = p1.Z - p2.Z;
    return static_cast<size_t>(sqrt((dx*dx) + (dy*dy) + (dz*dz)));
}

int wmain()
{
    // The central point of reference.
    const Point center = { 3, 2, 7 };

    // Create a few random Point values.
    vector<Point> values(7);
    mt19937 random(42);
    generate(begin(values), end(values), [&random] {
        Point p = { random()%10, random()%10, random()%10 };
        return p;
    });

    // Print the values before sorting them.
    wcout << "Before sorting:" << endl;
    for_each(begin(values), end(values), [center](const Point& p) {
        wcout << L'(' << p.X << L"," << p.Y << L"," << p.Z 
              << L") D = " << euclidean_distance(p, center) << endl;
    });
    wcout << endl;

    // Sort the values based on their distances from the reference point.
    parallel_radixsort(begin(values), end(values), 
        [center](const Point& p) -> size_t {
            return euclidean_distance(p, center);
        });

    // Print the values after sorting them.
    wcout << "After sorting:" << endl;
    for_each(begin(values), end(values), [center](const Point& p) {
        wcout << L'(' << p.X << L"," << p.Y << L"," << p.Z 
              << L") D = " << euclidean_distance(p, center) << endl;
    });
    wcout << endl;
} 
/* Output:
    Before sorting:
    (2,7,6) D = 5
    (4,6,5) D = 4
    (0,4,0) D = 7
    (3,8,4) D = 6
    (0,4,1) D = 7
    (2,5,5) D = 3
    (7,6,9) D = 6

    After sorting:
    (2,5,5) D = 3
    (4,6,5) D = 4
    (2,7,6) D = 5
    (3,8,4) D = 6
    (7,6,9) D = 6
    (0,4,0) D = 7
    (0,4,1) D = 7
*/

설명을 위해 이 예제에서는 비교적 작은 데이터 집합을 사용합니다. 벡터의 초기 크기를 늘려 큰 데이터 집합에 대한 성능 향상을 실험해 볼 수 있습니다.

이 예제에서는 해시 함수로 람다 식을 사용합니다. std::hash 클래스 의 기본 제공 구현 중 하나를 사용하거나 고유한 특수화를 정의할 수도 있습니다. 이 예제에서와 같이 사용자 지정 해시 함수 개체를 사용할 수도 있습니다.

// Functor class for computing the distance between points.
class hash_distance
{
public:
    hash_distance(const Point& reference)
        : m_reference(reference)
    {
    }

    size_t operator()(const Point& pt) const {
        return euclidean_distance(pt, m_reference);
    }

private:
    Point m_reference;
};

 

// Use hash_distance to compute the distance between points.
parallel_radixsort(begin(values), end(values), hash_distance(center));

해시 함수는 정수 계열 형식을 반환해야 합니다(std::is_integral::value 여야 true합니다). 이 정수 계열 형식을 size_t 형식으로 변환할 수 있어야 합니다.

정렬 알고리즘 선택

대부분의 경우 parallel_sort는 적절한 속도와 메모리 성능을 제공합니다. 그러나 데이터 집합 크기, 사용 가능한 프로세서 수 또는 비교 함수의 복잡성을 늘리면 parallel_buffered_sort 또는 parallel_radixsort 성능이 향상될 수 있습니다. 주어진 시나리오에서 정렬 알고리즘을 사용할지 여부를 결정하려면 대표적인 컴퓨터 구성에서 일반적인 데이터를 정렬하는데 걸리는 시간을 실제로 측정하는 것이 가장 좋습니다. 정렬 전략을 선택할 때 다음 지침을 염두에 두십시오.

• 데이터 집합의 크기 이 문서에서 작은 데이터 세트는 1,000개 미만의 요소를 포함하고, 중간 데이터 세트는 10,000개에서 100,000개 사이의 요소를 포함하며 , 큰 데이터 세트에는 100,000개 이상의 요소가 포함됩니다.

• 비교 함수 또는 해시 함수가 수행하는 작업의 양

• 사용 가능한 컴퓨팅 리소스의 양

• 데이터 집합의 특징입니다. 예를 들어, 한 알고리즘이 이미 거의 정렬된 데이터에는 잘 작동하지만, 완전히 정렬되지 않은 데이터에는 잘 작동하지 않을 수 있습니다.

• 청크 크기 선택적 _Chunk_size 인수는 전체 정렬을 보다 작은 작업 단위로 나눌 때 병렬에서 연속 정렬로 알고리즘이 전환되는 시기를 지정합니다. 예를 들어, 512를 제공하는 경우 작업 단위가 512개 이하의 요소를 포함하는 경우 알고리즘이 연속 구현으로 전환됩니다. 연속 구현은 데이터를 병렬로 처리하는 데 필요한 오버헤드를 제거하기 때문에 전체 성능을 향상시킬 수 있습니다.

사용 가능한 컴퓨팅 리소스가 많거나 비교 함수나 해시 함수가 비교적 많은 양의 작업을 수행할 때도 작은 데이터 세트을 병렬로 정렬하는 것은 가치가 없습니다. std::sort 함수를 사용하여 작은 데이터 세트를 정렬할 수 있습니다. (parallel_sort 데이터 parallel_buffered_sort 세트보다 큰 청크 크기를 지정할 때 호출 sort 합니다. 그러나 parallel_buffered_sort 잠금 경합 또는 메모리 할당으로 인해 추가 시간이 걸릴 수 있는 O(N) 공간을 할당해야 합니다.)

메모리를 보존해야 하거나 메모리 할당자가 잠금 경합을 따르는 경우 parallel_sort를 사용하여 중간 크기의 데이터 세트을 정렬하십시오. parallel_sort 에는 추가 공간이 필요하지 않습니다. 다른 알고리즘에는 O(N) 공간이 필요합니다.

중간 크기의 데이터 세트를 정렬하고 애플리케이션이 추가 O(N) 공간 요구 사항을 충족하는 경우를 사용합니다 parallel_buffered_sort . parallel_buffered_sort는 많은 계산이 필요한 비교 함수 또는 해시 함수나 많은 컴퓨팅 리소스가 있을 경우 특히 유용합니다.

큰 데이터 세트를 정렬하고 애플리케이션이 추가 O(N) 공간 요구 사항을 충족하는 경우에 사용합니다 parallel_radixsort . parallel_radixsort는 해당하는 비교 작업에 더 많은 계산이 필요하거나 두 작업 모두에 많은 계산이 필요할 경우 특히 유용합니다.

주의

좋은 해시 함수를 구현하려면 데이터 세트 범위와 데이터 세트의 각 요소가 해당하는 부호 없는 값으로 변형되는 방법을 알아야 합니다. 해시 연산은 부호 없는 값에 대해 작동하기 때문에 부호 없는 해시 값을 생성할 수 없는 경우 다른 정렬 전략을 고려해야 합니다.

다음 예제에서는 같은 큰 임의의 데이터 집합에 대한 sort, parallel_sort, parallel_buffered_sort 및 parallel_radixsort의 성능을 비교합니다.

// choosing-parallel-sort.cpp
// compile with: /EHsc
#include <ppl.h>
#include <random>
#include <iostream>
#include <windows.h>

using namespace concurrency;
using namespace std;

// Calls the provided work function and returns the number of milliseconds 
// that it takes to call that function.
template <class Function>
__int64 time_call(Function&& f)
{
   __int64 begin = GetTickCount();
   f();
   return GetTickCount() - begin;
}

const size_t DATASET_SIZE = 10000000;

// Create
// Creates the dataset for this example. Each call
// produces the same predefined sequence of random data.
vector<size_t> GetData()
{
    vector<size_t> data(DATASET_SIZE);
    generate(begin(data), end(data), mt19937(42));
    return data;
}

int wmain()
{
    // Use std::sort to sort the data.
    auto data = GetData();
    wcout << L"Testing std::sort...";
    auto elapsed = time_call([&data] { sort(begin(data), end(data)); });
    wcout << L" took " << elapsed << L" ms." <<endl;

    // Use concurrency::parallel_sort to sort the data.
    data = GetData();
    wcout << L"Testing concurrency::parallel_sort...";
    elapsed = time_call([&data] { parallel_sort(begin(data), end(data)); });
    wcout << L" took " << elapsed << L" ms." <<endl;

    // Use concurrency::parallel_buffered_sort to sort the data.
    data = GetData();
    wcout << L"Testing concurrency::parallel_buffered_sort...";
    elapsed = time_call([&data] { parallel_buffered_sort(begin(data), end(data)); });
    wcout << L" took " << elapsed << L" ms." <<endl;

    // Use concurrency::parallel_radixsort to sort the data.
    data = GetData();
    wcout << L"Testing concurrency::parallel_radixsort...";
    elapsed = time_call([&data] { parallel_radixsort(begin(data), end(data)); });
    wcout << L" took " << elapsed << L" ms." <<endl;
} 
/* Sample output (on a computer that has four cores):
    Testing std::sort... took 2906 ms.
    Testing concurrency::parallel_sort... took 2234 ms.
    Testing concurrency::parallel_buffered_sort... took 1782 ms.
    Testing concurrency::parallel_radixsort... took 907 ms.
*/

정렬 parallel_radixsort 중에 O(N) 공간을 할당하는 것이 허용된다고 가정하는 이 예제에서는 이 컴퓨터 구성에서 이 데이터 세트에서 최상의 성능을 발휘합니다.

[맨 위로 이동]

관련 항목

제목	설명
방법: parallel_for 루프 작성	알고리즘을 parallel_for 사용하여 행렬 곱셈을 수행하는 방법을 보여줍니다.
방법: parallel_for_each 루프 작성	알고리즘을 parallel_for_each 사용하여 std::array 개체의 소수 수를 병렬로 계산하는 방법을 보여 줍니다.
방법: parallel_invoke를 사용하여 병렬 정렬 루틴 작성	parallel_invoke 알고리즘을 사용하여 바이토닉 정렬 알고리즘의 성능을 향상시키는 방법을 보여 줍니다.
방법: parallel_invoke를 사용하여 병렬 작업 실행	parallel_invoke 알고리즘을 사용하여 공유 데이터 소스에서 여러 작업을 수행하는 프로그램의 성능을 향상시키는 방법을 보여 줍니다.
방법: 매핑 수행 및 병렬 작업 줄이기	parallel_transform 및 parallel_reduce 알고리즘을 사용하여 파일의 단어 수를 세는 매핑 및 줄이기 작업을 수행하는 방법을 보여줍니다.
PPL(병렬 패턴 라이브러리)	동시 애플리케이션 개발을 위해 확장성과 사용 편의성을 높이는 명령적 프로그래밍 모델을 제공하는 PPL에 대해 설명합니다.
PPL에서의 취소	PPL에서 취소의 역할, 병렬 작업을 취소하는 방법 및 작업 그룹이 취소되는 시기를 확인하는 방법을 설명합니다.
예외 처리	동시성 런타임에서 예외 처리의 역할을 설명합니다.

참조

parallel_for 함수

parallel_for_each 함수

parallel_invoke 함수

affinity_partitioner 클래스

auto_partitioner 클래스

simple_partitioner 클래스

static_partitioner 클래스

parallel_sort 함수

parallel_buffered_sort 함수

parallel_radixsort 함수