병렬 알고리즘

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

병렬 알고리즘은 동시성 런타임의 기존 기능으로 구성됩니다. 예를 들어 concurrency::parallel_for 알고리즘은 concurrency::structured_task_group 개체를 사용하여 병렬 루프 반복을 수행합니다. 또한 parallel_for 알고리즘은 사용 가능한 컴퓨팅 리소스 수가 제공되면 최적의 방법으로 작업을 분할합니다.

단원

• parallel_for 알고리즘

• parallel_for_each 알고리즘

• parallel_invoke 알고리즘

• parallel_transform 및 parallel_reduce 알고리즘

  • parallel_transform 알고리즘

  • parallel_reduce 알고리즘

  • 예: 매핑 및 줄이기 병렬로 수행

• 분할 작업

• 병렬 정렬

  • 정렬 알고리즘 선택

parallel_for 알고리즘

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

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

parallel_for 알고리즘에는 여러 개의 오버로드된 버전이 있습니다. 첫 번째 버전은 시작 값, 끝 값 및 작업 함수(람다 식, 함수 개체 또는 함수 포인터)를 사용하고 두 번째 버전은 시작 값, 끝 값, 단계 기준 값 및 작업 함수를 사용합니다. 이 함수의 첫 번째 버전에서는 1을 단계 값으로 사용합니다. 남은 버전은 어떻게 parallel_for 범위 스레드 간에 분할 해야 하는 지를 지정하는 파티션 프로그램의 개체를 가집니다. 이 문서에서 분할 작업 섹션에서 파티션 프로그램은 더 자세히 설명됩니다.

parallel_for를 사용하기 위해 많은 for 루프를 변환할 수 있습니다. 그러나 다음과 같은 면에서 parallel_for 알고리즘은 for 문과는 다릅니다.

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

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

• _Index_type 형식 매개 변수는 정수 계열 형식이어야 합니다. 이 정수 형식은 부호가 있거나 없을 수 있습니다.

• 루프 반복은 정방향이어야 합니다. _Step 매개 변수가 1보다 작으면 parallel_for 알고리즘에서 std::invalid_argument 형식의 예외를 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();
   });
}

이 예제를 실행하면 다음과 같은 샘플 결과가 출력됩니다.

parallel_for 알고리즘은 각 항목에 대해 병렬로 작동하기 때문에 콘솔에 값이 출력되는 순서가 다릅니다.

parallel_for 알고리즘을 사용하는 전체 예제를 보려면 방법: parallel_for 루프 작성을 참조하십시오.

[맨 위]

parallel_for_each 알고리즘

concurrency::parallel_for_each 알고리즘은 STL에서 제공되는 것과 같은 반복 컨테이너에 대해 병렬로 작업을 수행합니다. 이 알고리즘은 parallel_for 알고리즘에서 사용하는 것과 같은 분할 논리를 사용합니다.

parallel_for_each 알고리즘은 parallel_for_each 알고리즘이 동시에 작업을 실행한다는 점을 제외하고는 STL 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
*/

이 예제를 실행하면 다음과 같은 샘플 결과가 출력됩니다.

parallel_for_each 알고리즘은 각 항목에 대해 병렬로 작동하기 때문에 콘솔에 값이 출력되는 순서가 다릅니다.

parallel_for_each 알고리즘을 사용하는 전체 예제를 보려면 방법: parallel_for_each 루프 작성을 참조하십시오.

[맨 위]

parallel_invoke 알고리즘

concurrency::parallel_invoke 알고리즘은 작업 집합을 병렬로 실행하며, 각 작업이 완료될 때까지 반환하지 않습니다. 이 알고리즘은 서로 관련이 없는 여러 작업을 동시에 실행하려는 경우에 유용합니다.

parallel_invoke 알고리즘은 일련의 작업 함수(람다 함수, 함수 개체 또는 함수 포인터)를 매개 변수로 사용합니다. parallel_invoke 알고리즘은 2개에서 10개 사이의 매개 변수를 사용하도록 오버로드됩니다. 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;
}

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

parallel_invoke 알고리즘을 사용하는 전체 예제를 보려면 방법: parallel_invoke를 사용하여 병렬 정렬 루틴 작성 및 방법: parallel_invoke를 사용하여 병렬 작업 실행을 참조하십시오.

[맨 위]

parallel_transform 및 parallel_reduce 알고리즘

concurrency::parallel_transform 및 concurrency::parallel_reduce 알고리즘은 std::transform 및 std::accumulate 각각의 STL 알고리즘의 병렬 버전입니다. 동시성 런타임 버전들은 병렬로 실행하기 때문에 동작의 순서가 결정되지 않은 것을 제외하고 STL 버전처럼 작동합니다. 병렬로 처리되는 성능과 확장성 혜택을받을 수있을만큼 큰 세트로 작업 할 때 이러한 알고리즘을 사용합니다.

중요

parallel_transform 및 parallel_reduce 알고리즘은 이러한 반복기 안정 된 메모리 주소를 생성 하기 때문에 임의 액세스 양 지향성 및 정방향 반복기를 지원합니다.또한 이러한 반복기는 비 const l 값을 생성합니다.

parallel_transform 알고리즘

parallel transform 알고리즘은 많은 데이터 병렬 처리 작업을 수행하는 알고리즘입니다. 예를 들어, 다음을 수행할 수 있습니다.

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

• 두 벡터 사이의 내적 합 또는 걸리고 벡터에서 다른 숫자 계산을 수행합니다.

• 1 픽셀 렌더링 해야 하는 각 반복 참조를 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>());
}

경고

이 예제에서는 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>());

중요

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;
    words.push_back(L"Lorem ");
    words.push_back(L"ipsum ");
    words.push_back(L"dolor ");
    words.push_back(L"sit ");
    words.push_back(L"amet, ");
    words.push_back(L"consectetur ");
    words.push_back(L"adipiscing ");
    words.push_back(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_reduce 을 concurrency::combinable 클래스와 parallel_for_each 알고리즘의 사용에 대한 약어로 생각할 수 있습니다.

예: 매핑 및 줄이기 병렬로 수행

맵 작업은 시퀀스의 각 값에 함수를 적용합니다. 감소는 작업 시퀀스를 하나의 값의 요소를 결합합니다. 표준 템플릿 라이브러리 (STL)std::transformstd::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 와 유사합니다, 하지만 작업자 스레드 범위 매핑되는 방식으로 캐시 선호도를 향상시킵니다. 이 파티션 형식은 루프를 여러 번 (예: 루프에서 루프) 같은 데이터 집합에 대해 실행되고 데이터 캐시에 사용할 때 성능을 향상시킬 수 있습니다. 이 파티션은 취소에 관여하지 않습니다. 또한 협조적 차단 기능을 사용하지 않으며, 따라서 순방향 종속성이 병렬 루프와 함께 사용될 수 없다.

• concurrency::auto_partitioner
  나누기 작업에 초기화 된 수의 범위 (일반적으로 루프에서 작동하는 데 사용할 수 있는 작업자 스레드 수). _Partitioner의 매개 변수를 오버로드 된 병렬 알고리즘을 호출하지 않는 경우 런타임은 기본적으로이 유형을 사용합니다. 각 범위는 하위 범위로 분할함으로써 발생하는 로드 균형을 가능하게 할 수 있습니다. 마찬가지로 작업을 완료하면 런타임은 다른 스레드의 작업을 서브 스레드에 재배포합니다. 워크로드가 다른 범주 중 하나에 해당하지 않거나 취소 또는 협조적 차단을 완벽하게 지원이 필요한 경우 이 파티션 프로그램을 사용합니다.

• concurrency::simple_partitioner
  나누기는 각 범위에 대 한 최소한의 특정된 청크 크기에 의해 지정 된 반복 횟수 범위에 작동합니다. 이 파티션 프로그램 유형은 로드 균형 조정에 참여합니다; 그러나, 런타임은 하위 범위로 범위를 구분하지 않습니다. 각 작업자에 대해 _Chunk_size 반복을 완료한 후 런타임 취소 여부를 확인하고 로드 균형 조정을 수행합니다.

• concurrency::static_partitioner
  나누기 작업에 고정된 된 수의 범위 (일반적으로 루프에서 작동하는 데 사용할 수 있는 작업자 스레드 수). 이 파티션 형식은 작업 가로채기를 사용하지 않고 적은 오버 헤드를 포함 하기 때문에 성능이 향상됩니다. 병렬 루프의 각 반복 작업의 일정하고 균일 한 양을 수행하고 취소 또는 앞으로 협력 차단에 대한 지원을 필요로하지 않는 경우이 파티션 프로그램 형식을 사용합니다.

경고

parallel_for_each 및 parallel_transform 알고리즘은 정적인, 간단하고 선호하는 파티션에대한 임의의 액세스 반복기를 사용하는 컨테이너(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());
}

하지만 비const로 affinity_partitioner 개체를 전달해야합니다. l 값은 알고리즘이 다시 미래의 루프 상태를 저장할 수 있도록 참조합니다. 다음 예제에서는 여러 번 동시에 데이터 집합에서 동일한 작업을 수행하는 기본 응용 프로그램을 보여줍니다. 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::parallel_sort, concurrency::parallel_buffered_sort, 및 concurrency::parallel_radixsort. 이 정렬 알고리즘은 동시에 정렬하고 활용할 수 있는 데이터 집합을 사용하는 경우에 유용합니다. 특히 정렬을 병렬로 유용 데이터 집합이 있는 경우 데이터를 정렬 하는 계산 과정이 비교 연산을 사용하거나 합니다. 이러한 알고리즘의 각 위치에 있는 요소를 정렬합니다.

parallel_sort 및 parallel_buffered_sort 알고리즘은 비교 기반 알고리즘 모두 있습니다. 즉, 요소 값으로 비교합니다. parallel_sort 알고리즘은 추가 메모리 요구 사항이 없고 범용 정렬을 하는데 적합합니다. parallel_buffered_sort 알고리즘은 parallel_sort 보다 나은 퍼포먼스를 수행할 수 있습니다, 하지만 O(N) 공간이 필요합니다.

알고리즘이 parallel_radixsort인 해시 기반인 경우 즉, 정수 키 요소를 정렬 하는 데 사용합니다. 키를 사용하여 이 알고리즘은 대상 비교를 사용하는 대신 요소를 직접 계산할 수 있습니다. parallel_buffered_sort 와 마찬가지로,이 알고리즘에서는 O(N) 공간이 필요합니다.

다음 표에서 세 개의 병렬 정렬 알고리즘의 중요한 속성을 요약합니다.

알고리즘(Algorithm)	설명	정렬 메커니즘	정렬 안정성	메모리 요구 사항	시간 복잡도	반복기 액세스
parallel_sort	범용 비교 기준으로 정렬 합니다.	비교 기반 (오름차순)	불안정 한	없음	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 참조 선언자: &&, 및 방법: 이동 생성자 작성을 참조하십시오.Move 대입 연산자 또는 스왑 함수를 제공하지 않을 경우 정렬 알고리즘은 복사 생성자를 사용합니다.

다음 기본 예제에서는 parallel_sort 을 사용하여 int 값의 vector 를 정렬 하는 방법을 보여줍니다. 기본적으로 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<이중> 값을 오름차순으로 정렬합니다.

// 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 가 더 잘 수행할 수 있습니다. 해당 시나리오에서 정렬 알고리즘을 사용할지 여부를 결정하려면 대표적인 컴퓨터 구성에서 일반적인 데이터를 정렬하는데 걸리는 시간을 실제로 측정하는 것이 가장 좋습니다. 정렬 방법을 선택하는 경우 다음 지침을 염두에 두십시오.

• 데이터 집합의 크기입니다. 이 문서에는 작은데이터 집합은 1000 개 이상의 요소를 포함합니다. 보통 데이터 집합은 요소를 10, 000와 100000 사이 , 큰 데이터 집합은 100000 이상의 요소를 포함합니다.

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

• 사용 가능한 컴퓨팅 리소스의 양입니다.

• 데이터 집합의 특징입니다. 예를 들어, 하나의 알고리즘 거의 이미 정렬 된 데이터에 있지만 뿐만 아니라 완전히 정렬 되지 않은 데이터에 대해 수행할 수 있습니다.

• 청크 크기입니다. 선택적인 _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.
*/

이 예제는 정렬하는 동안 O(N) 공간 할당에 적용할 수 있는지 가정합니다. parallel_radixsort 는 이 컴퓨터 구성에서 이 데이터 집합에 최상의 효율을 수행합니다.

[맨 위]

관련 항목

제목	설명
방법: 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 함수