병렬 알고리즘

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 알고리즘은 반복 변수의 현재 값이 _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 루프 작성을 참조하십시오.

Top

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), begin(values), [](int value) {
      wstringstream ss;
      ss << value << L' ';
      wcout << ss.str();
   });
}

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

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

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

Top

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를 사용하여 병렬 작업 실행을 참조하십시오.

Top

Parallel_transform 및 parallel_reduce 알고리즘

Concurrency::parallel_transform 및 concurrency::parallel_reduce 알고리즘은 STL 알고리즘의 병렬 버전 std::transform 및 std::accumulate, 각각.병렬로 실행 되므로 작업 순서 결정 되지 않습니다 것을 제외 하 고 동시성 런타임 버전 STL 버전 처럼 동작 합니다.병렬로 처리할 성능 및 확장성의 이점을 얻을 수 있는 큰 집합으로 작업할 때 이러한 알고리즘을 사용 합니다.

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

Parallel_transform 알고리즘

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

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

• 합 하거나 두 벡터 간의 내적을 가져와 벡터에서 다른 숫자 계산을 수행 합니다.

• 여기서 렌더링 해야 하는 하나의 픽셀에 각 반복을 참조 하는 3 차원 레이 트레이싱을 수행 합니다.

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

// 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 의 사용에 대 한 축약형으로는 parallel_for_each 함께 알고리즘의 concurrency::combinable 클래스.

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

A 맵 작업 시퀀스에서의 각 값에 함수를 적용 합니다.A 감소 작업이 하나의 값 시퀀스의 요소를 결합 합니다.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
*/

지도 수행 하 고 작업을 동시에 줄일 수는 다른 예제를 보려면 방법: 매핑 수행 및 병렬 작업 줄이기.

Top

파티션 작업

데이터 원본에 대 한 작업을 병렬화 하기 위해 반드시 필요한 단계 하는 것 파티션 소스 다중 스레드에서 동시에 액세스할 수 있습니다 여러 섹션으로.파티 셔 너를 병렬 알고리즘 범위 스레드 간에 분할 해야 방법을 지정 합니다.이전에이 문서에서 설명한 대로 기본 메커니즘은 초기 작업 부하를 만들고는 작업 가로채기 알고리즘 및 절도 작업 부하가 분산 되지 않은 경우 이러한 파티션을 조정 하는 범위를 사용 하 여 분할 PPL을 사용 합니다.예를 들어, 하나의 루프 반복 반복 범위를 완료 하면 런타임은 다른 스레드의 작업을에서 스레드에 재배포 합니다.그러나, 일부 시나리오에 대 한 문제에 적합 한 다른 파티션 메커니즘을 지정 할 수 있습니다.

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

• concurrency::affinity_partitioner
  나눕니다 고정 된 수의 범위 (일반적으로 루프에서 작동 하는 데 사용할 수 있는 작업자 스레드의 개수)로 작동 합니다.이 파티 셔 너 종류와 유사한 static_partitioner, 하지만 캐시 선호도 작업자 스레드에 범위 매핑되는 방식으로 개선 합니다.이 파티 셔 너 종류는 여러 번 (예: 루프) 루프 내에서 같은 데이터 집합을 통해 루프 실행 되 고 캐시에 데이터를 맞추는 경우 성능이 향상 됩니다.이 파티 셔이 너에서 취소 완벽 하 게 참여 하지 않습니다.협조적 차단 기능을 사용 하지 않는 하 고 있으므로 앞으로 의존 관계에 있는 병렬 루프를 사용할 수 없습니다.

• concurrency::auto_partitioner
  나눕니다 범위 (일반적으로 루프에서 작동 하는 데 사용할 수 있는 작업자 스레드의 개수)는 초기 수로 작동 합니다.사용 하는 오버 로드 된 병렬 알고리즘을 호출 하지 않을 때 기본적으로 런타임에서이 형식을 사용 하는 _Partitioner 매개 변수입니다.각 범위는 sub-ranges로 나눌 수 있습니다 하 고 있으므로 활성화 되려면 로드를 균형 조정 합니다.다양 한 작업을 완료 하면 런타임은 sub-ranges 한 스레드가 다른 스레드에서 작업을 재배포 합니다.이 파티 셔이 너 작업 다른 범주 중 하나에 속하지 않는 경우 취소 되거나 협조적 차단에 대 한 완벽 한 지원 해야를 사용 합니다.

• concurrency::simple_partitioner
  각 범위에 적어도 지정 된 청크 크기에 의해 지정 된 반복 횟수 갖도록 나눕니다 범위로 작동 합니다.이 파티 셔 너 형식 로드 균형 조정에 참여 합니다. 그러나 런타임에서 범위 sub-ranges에 나누지 않습니다.각 작업자에 대 한 런타임 확인 취소를 하 고 로드 균형 조정 후 수행 _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());
}

전달 해야는 affinity_partitioner 개체로 비-const, l 값 참조 알고리즘 다시 앞으로 루프에 대 한 상태를 저장할 수 있도록 합니다.다음 예제에서는 데이터 집합에서 동일한 작업을 동시에 여러 번 수행 하는 기본 응용 프로그램을 보여 줍니다.사용 하는 affinity_partitioner 캐시에 맞게 배열 높기 때문에 성능을 향상 시킬 수 있습니다.

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

using namespace concurrency;

int wmain()
{    
    // Create an arry 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.이러한 파티 셔 너 종류 로드 균형 조정 또는 범위를 가로채기를 사용 하지 않는 및 따라서 응용 프로그램의 동작을 변경할 수 있습니다.

해당된 시나리오에서 사용 하는 파티 셔 너를 여부를 결정 하는 가장 좋은 방법은 실험 하 고 작업이 완료 대표적인 부하 및 컴퓨터 구성에서 걸리는 측정입니다.예를 들어, 정적 분할은 코어가 많지 않은 다중 코어 컴퓨터에서 속도를 상당히 높일 수 있지만 코어가 비교적 많은 컴퓨터에서는 속도 저하를 유발할 수 있습니다.

Top

병렬 정렬

세 가지 정렬 알고리즘을 제공 하는 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) 공간.

다음 표에서 세 개의 병렬 정렬 알고리즘의 중요 한 속성 요약 되어 있습니다.

알고리즘	설명	정렬 메커니즘	정렬 안정성	메모리 요구 사항	시간 복잡도	반복기 액세스
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 참조 선언 자: & &, 및 방법: 이동 생성자 작성.이동 대입 연산자 스왑 함수를 제공 하는 경우 복사 생성자를 사용 하는 정렬 알고리즘.

다음 기본 예제를 사용 하는 방법을 보여 줍니다. 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 보다 효율적으로 수행할 수 있습니다.해당된 시나리오에서 사용 하는 정렬 알고리즘을 결정 하는 가장 좋은 방법은 실험 하 고 대표적인 컴퓨터 구성에서 일반적인 데이터를 정렬 하려면 걸리는 측정입니다.정렬 하는 전략을 선택할 때 다음 지침을 유의 하십시오.

• 데이터 집합의 크기입니다.이 문서에는 작은 1000 개 이상의 요소를 데이터 집합에 들어는 보통 10000-100000 요소 사이 데이터 집합에 들어와 큰 dataset에 100000 이상의 요소가 포함 되어 있습니다.

• 크기를 비교 또는 해시 함수를 수행 하는 작업입니다.

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

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

• 청크 크기입니다.선택적인 _Chunk_size 이 전체 정렬 작업을 더 작은 단위로 세분으로 알고리즘에서 병렬 직렬 정렬 구현에 전환한 경우 인수를 지정 합니다.예를 들어, 512를 제공 하는 경우 512 이하의 요소 작업의 단위를 포함 하는 경우 알고리즘 구현을 직렬 전환 합니다.데이터를 병렬로 처리 하는 데 필요한 오버 헤드를 제거 하므로 순차적 구현의 전반적인 성능이 향상 됩니다.

작은 데이터 집합에 동시에도 사용 가능한 컴퓨팅 리소스 수가 많은 경우에 나를 비교 또는 해시 함수는 비교적 많은 양의 작업을 수행 하면 정렬 하는 것이 좋을 수 있습니다.사용 하면 std::sort 작은 데이터 집합을 정렬 하는 함수입니다.(parallel_sort 및 parallel_buffered_sort 호출 sort ; 데이터 집합 보다 더 큰 청크 크기를 지정 하는 경우 그러나 parallel_buffered_sort 를 할당 하는 것 O(N) 공간을 잠금 경합 또는 메모리 할당 때문에 시간이 더 걸릴 수 있습니다.)

사용 메모리를 절약 해야 하거나 메모리 할당자를 사용 하 여 잠금 경합이 경우 parallel_sort 중간 규모 데이터 집합을 정렬 합니다.parallel_sort추가 공간이 필요합니다. 다른 알고리즘에 필요한 O(N) 공간.

사용 parallel_buffered_sort 중간 규모 데이터 집합 및 응용 프로그램의 추가 충족 하면 정렬 하려면 O(N) 공간 요구 사항이 있습니다.parallel_buffered_sort많은 수의 컴퓨팅 리소스는 비싼 비교 함수 또는 해시 함수에 있을 때 특히 유용할 수 있습니다.

사용 parallel_radixsort 큰 데이터 집합 및 응용 프로그램의 추가 충족 하면 정렬 하려면 O(N) 공간 요구 사항이 있습니다.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 가장이 컴퓨터 구성에서이 데이터 집합을 수행 합니다.

Top

관련 항목

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