방법: parallel_invoke를 사용하여 병렬 정렬 루틴 작성

아티클
10/12/2023

이 문서에서는 parallel_invoke 알고리즘을 사용하여 비트음속 정렬 알고리즘의 성능을 향상시키는 방법을 설명합니다. 비트닉 정렬 알고리즘은 입력 시퀀스를 더 작은 정렬된 파티션으로 재귀적으로 나눕니다. 각 파티션 작업은 다른 모든 작업과 독립적이므로 비트닉 정렬 알고리즘을 병렬로 실행할 수 있습니다.

bitonic 정렬은 입력 시퀀스의 모든 조합을 정렬하는 정렬 네트워크의 예이지만 길이가 2인 시퀀스를 정렬하는 예제입니다.

참고 항목

이 예제에서는 이해를 돕기 위해 병렬 정렬 루틴을 사용합니다. PPL에서 제공하는 기본 제공 정렬 알고리즘인 concurrency::p arallel_sort, concurrency::p arallel_buffered_sort 및 concurrency::p arallel_radixsort를 사용할 수도 있습니다. 자세한 내용은 병렬 알고리즘을 참조 하세요.

섹션

이 문서에서는 다음 작업을 설명합니다.

직렬로 비트음 정렬 수행
parallel_invoke 사용하여 병렬로 비트소닉 정렬 수행

직렬로 비트음 정렬 수행

다음 예제에서는 비트닉 정렬 알고리즘의 직렬 버전을 보여 있습니다. 이 함수는 bitonic_sort 시퀀스를 두 파티션으로 나누고 해당 파티션을 반대 방향으로 정렬한 다음 결과를 병합합니다. 이 함수는 자신을 두 번 재귀적으로 호출하여 각 파티션을 정렬합니다.

const bool INCREASING = true;
const bool DECREASING = false;

// Comparator function for the bitonic sort algorithm.
template <class T>
void compare(T* items, int i, int j, bool dir)
{
   if (dir == (items[i] > items[j]))
   {
      swap(items[i], items[j]);
   }
}

// Sorts a bitonic sequence in the specified order.
template <class T>
void bitonic_merge(T* items, int lo, int n, bool dir)
{
   if (n > 1)
   {
      int m = n / 2;
      for (int i = lo; i < lo + m; ++i)
      {
         compare(items, i, i + m, dir);
      }
      bitonic_merge(items, lo, m, dir);
      bitonic_merge(items, lo + m, m, dir);
   }
}

// Sorts the given sequence in the specified order.
template <class T>
void bitonic_sort(T* items, int lo, int n, bool dir)
{
   if (n > 1)
   {
      // Divide the array into two partitions and then sort 
      // the partitions in different directions.
      int m = n / 2;
      bitonic_sort(items, lo, m, INCREASING);
      bitonic_sort(items, lo + m, m, DECREASING);

      // Merge the results.
      bitonic_merge(items,lo, n, dir);
   }
}

// Sorts the given sequence in increasing order.
template <class T>
void bitonic_sort(T* items, int size)
{
    bitonic_sort(items, 0, size, INCREASING);
}

[맨 위로 이동]

parallel_invoke 사용하여 병렬로 비트소닉 정렬 수행

이 섹션에서는 알고리즘을 parallel_invoke 사용하여 비트음속 정렬 알고리즘을 병렬로 수행하는 방법을 설명합니다.

비트음 정렬 알고리즘을 병렬로 수행하려면

#include 헤더 파일 ppl.h에 대한 지시문을 추가합니다.
```
#include <ppl.h>
```
네임스페이 usingconcurrency 스에 대한 지시문을 추가합니다.
```
using namespace concurrency;
```

수행할 작업이 충분한 경우 알고리즘을 사용하여 parallel_invoke 시퀀스를 병렬로 병합하는 새 함수를 parallel_bitonic_mege만듭니다. 그렇지 않으면 시퀀스를 직렬로 병합하도록 호출 bitonic_merge 합니다.

// Sorts a bitonic sequence in the specified order.
template <class T>
void parallel_bitonic_merge(T* items, int lo, int n, bool dir)
{   
   // Merge the sequences concurrently if there is sufficient work to do.
   if (n > 500)
   {
      int m = n / 2;
      for (int i = lo; i < lo + m; ++i)
      {
         compare(items, i, i + m, dir);
      }

      // Use the parallel_invoke algorithm to merge the sequences in parallel.
      parallel_invoke(
         [&items,lo,m,dir] { parallel_bitonic_merge(items, lo, m, dir); },
         [&items,lo,m,dir] { parallel_bitonic_merge(items, lo + m, m, dir); }
      );
   }
   // Otherwise, perform the work serially.
   else if (n > 1)
   {
      bitonic_merge(items, lo, n, dir);
   }   
}

이전 단계의 프로세스와 유사하지만 함수에 대한 프로세스를 수행합니다 bitonic_sort .

// Sorts the given sequence in the specified order.
template <class T>
void parallel_bitonic_sort(T* items, int lo, int n, bool dir)
{   
   if (n > 1)
   {
      // Divide the array into two partitions and then sort 
      // the partitions in different directions.
      int m = n / 2;

      // Sort the partitions in parallel.
      parallel_invoke(
         [&items,lo,m] { parallel_bitonic_sort(items, lo, m, INCREASING); },
         [&items,lo,m] { parallel_bitonic_sort(items, lo + m, m, DECREASING); }
      );
      
      // Merge the results.
      parallel_bitonic_merge(items, lo, n, dir);
   }
}

배열을 순서대로 정렬하는 오버로드된 버전의 parallel_bitonic_sort 함수를 만듭니다.
```
// Sorts the given sequence in increasing order.
template <class T>
void parallel_bitonic_sort(T* items, int size)
{
   parallel_bitonic_sort(items, 0, size, INCREASING);
}
```
이 알고리즘은 parallel_invoke 호출 컨텍스트에서 일련의 마지막 작업을 수행하여 오버헤드를 줄입니다. 예를 들어 함수에서 parallel_bitonic_sort 첫 번째 작업은 별도의 컨텍스트에서 실행되고 두 번째 작업은 호출 컨텍스트에서 실행됩니다.
```
// Sort the partitions in parallel.
parallel_invoke(
   [&items,lo,m] { parallel_bitonic_sort(items, lo, m, INCREASING); },
   [&items,lo,m] { parallel_bitonic_sort(items, lo + m, m, DECREASING); }
);
```

다음 전체 예제에서는 비트소닉 정렬 알고리즘의 직렬 및 병렬 버전을 모두 수행합니다. 또한 이 예제는 각 계산을 수행하는 데 필요한 시간을 콘솔에 출력합니다.

// parallel-bitonic-sort.cpp
// compile with: /EHsc
#include <windows.h>
#include <algorithm>
#include <iostream>
#include <random>
#include <ppl.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 bool INCREASING = true;
const bool DECREASING = false;

// Comparator function for the bitonic sort algorithm.
template <class T>
void compare(T* items, int i, int j, bool dir)
{
   if (dir == (items[i] > items[j]))
   {
      swap(items[i], items[j]);
   }
}

// Sorts a bitonic sequence in the specified order.
template <class T>
void bitonic_merge(T* items, int lo, int n, bool dir)
{
   if (n > 1)
   {
      int m = n / 2;
      for (int i = lo; i < lo + m; ++i)
      {
         compare(items, i, i + m, dir);
      }
      bitonic_merge(items, lo, m, dir);
      bitonic_merge(items, lo + m, m, dir);
   }
}

// Sorts the given sequence in the specified order.
template <class T>
void bitonic_sort(T* items, int lo, int n, bool dir)
{
   if (n > 1)
   {
      // Divide the array into two partitions and then sort 
      // the partitions in different directions.
      int m = n / 2;
      bitonic_sort(items, lo, m, INCREASING);
      bitonic_sort(items, lo + m, m, DECREASING);

      // Merge the results.
      bitonic_merge(items,lo, n, dir);
   }
}

// Sorts the given sequence in increasing order.
template <class T>
void bitonic_sort(T* items, int size)
{
    bitonic_sort(items, 0, size, INCREASING);
}

// Sorts a bitonic sequence in the specified order.
template <class T>
void parallel_bitonic_merge(T* items, int lo, int n, bool dir)
{   
   // Merge the sequences concurrently if there is sufficient work to do.
   if (n > 500)
   {
      int m = n / 2;
      for (int i = lo; i < lo + m; ++i)
      {
         compare(items, i, i + m, dir);
      }

      // Use the parallel_invoke algorithm to merge the sequences in parallel.
      parallel_invoke(
         [&items,lo,m,dir] { parallel_bitonic_merge(items, lo, m, dir); },
         [&items,lo,m,dir] { parallel_bitonic_merge(items, lo + m, m, dir); }
      );
   }
   // Otherwise, perform the work serially.
   else if (n > 1)
   {
      bitonic_merge(items, lo, n, dir);
   }   
}

// Sorts the given sequence in the specified order.
template <class T>
void parallel_bitonic_sort(T* items, int lo, int n, bool dir)
{   
   if (n > 1)
   {
      // Divide the array into two partitions and then sort 
      // the partitions in different directions.
      int m = n / 2;

      // Sort the partitions in parallel.
      parallel_invoke(
         [&items,lo,m] { parallel_bitonic_sort(items, lo, m, INCREASING); },
         [&items,lo,m] { parallel_bitonic_sort(items, lo + m, m, DECREASING); }
      );
      
      // Merge the results.
      parallel_bitonic_merge(items, lo, n, dir);
   }
}

// Sorts the given sequence in increasing order.
template <class T>
void parallel_bitonic_sort(T* items, int size)
{
   parallel_bitonic_sort(items, 0, size, INCREASING);
}

int wmain()
{  
   // For this example, the size must be a power of two.
   const int size = 0x200000;

   // Create two large arrays and fill them with random values.
   int* a1 = new int[size];
   int* a2 = new int[size];

   mt19937 gen(42);
   for(int i = 0; i < size; ++i)
   {
      a1[i] = a2[i] = gen();
   }

   __int64 elapsed;
   
   // Perform the serial version of the sort.
   elapsed = time_call([&] { bitonic_sort(a1, size); });
   wcout << L"serial time: " << elapsed << endl;

   // Now perform the parallel version of the sort.
   elapsed = time_call([&] { parallel_bitonic_sort(a2, size); });
   wcout << L"parallel time: " << elapsed << endl;
 
   delete[] a1;
   delete[] a2;
}

프로세서가 4개인 컴퓨터의 샘플 출력은 다음과 같습니다.

serial time: 4353
parallel time: 1248

[맨 위로 이동]

코드 컴파일

코드를 컴파일하려면 코드를 복사한 다음 Visual Studio 프로젝트에 붙여넣거나 이름이 지정된 parallel-bitonic-sort.cpp 파일에 붙여넣은 다음 Visual Studio 명령 프롬프트 창에서 다음 명령을 실행합니다.

cl.exe /EHsc parallel-bitonic-sort.cpp

강력한 프로그래밍

이 예제에서는 각 작업 그룹의 수명이 함수 이상으로 확장되지 않으므로 동시성::task_group 클래스 대신 알고리즘을 사용합니다parallel_invoke. 개체보다 task group 실행 오버헤드가 적기 때문에 가능한 경우 사용하는 parallel_invoke 것이 좋습니다. 따라서 더 나은 수행 코드를 작성할 수 있습니다.

일부 알고리즘의 병렬 버전은 수행할 작업이 충분한 경우에만 더 나은 성능을 발휘합니다. 예를 들어 parallel_bitonic_merge 시퀀스에 요소가 500개 이하인 경우 함수는 직렬 버전을 bitonic_merge호출합니다. 작업량에 따라 전체 정렬 전략을 계획할 수도 있습니다. 예를 들어 다음 예제와 같이 배열에 500개 미만의 항목이 포함된 경우 빠른 정렬 알고리즘의 직렬 버전을 사용하는 것이 더 효율적일 수 있습니다.

template <class T>
void quick_sort(T* items, int lo, int n)
{
   // TODO: The function body is omitted for brevity.
}

template <class T>
void parallel_bitonic_sort(T* items, int lo, int n, bool dir)
{
   // Use the serial quick sort algorithm if there are relatively few
   // items to sort. The associated overhead for running few tasks in 
   // parallel may not overcome the benefits of parallel processing.
   if (n - lo + 1 <= 500)
   {
      quick_sort(items, lo, n);
   }
   else if (n > 1)
   {
      // Divide the array into two partitions and then sort 
      // the partitions in different directions.
      int m = n / 2;

      // Sort the partitions in parallel.
      parallel_invoke(
         [&items,lo,m] { parallel_bitonic_sort(items, lo, m, INCREASING); },
         [&items,lo,m] { parallel_bitonic_sort(items, lo + m, m, DECREASING); }
      );
      
      // Merge the results.
      parallel_bitonic_merge(items, lo, n, dir);
   }
}

병렬 알고리즘과 마찬가지로 코드를 적절하게 프로파일링하고 조정하는 것이 좋습니다.

참고 항목

작업 병렬 처리
parallel_invoke 함수

방법: parallel_invoke를 사용하여 병렬 정렬 루틴 작성

섹션

직렬로 비트음 정렬 수행

parallel_invoke 사용하여 병렬로 비트소닉 정렬 수행

비트음 정렬 알고리즘을 병렬로 수행하려면

코드 컴파일

강력한 프로그래밍

참고 항목

피드백

피드백

추가 리소스