分享方式:


如何:使用 parallel_invoke 撰寫平行排序常式

本檔說明如何使用 parallel_invoke 演算法來改善 bitonic 排序演算法的效能。 bitonic 排序演算法會以遞迴方式將輸入序列分割成較小的排序資料分割。 bitonic 排序演算法可以平行執行,因為每個資料分割作業與所有其他作業無關。

雖然 bitonic 排序是 排序網路 範例,可排序輸入序列的所有組合,但此範例會排序長度為兩個乘冪的序列。

注意

這個範例會使用平行排序常式做為說明。 您也可以使用 PPL 提供的內建排序演算法: concurrency::p arallel_sort、 concurrency::p arallel_buffered_sort concurrency::p arallel_radixsort 。 如需詳細資訊,請參閱 平行演算法

區段

本檔描述下列工作:

以序列方式執行 Bitonic 排序

下列範例顯示 bitonic 排序演算法的序列版本。 函 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平行執行 Bitonic 排序

本節說明如何使用 parallel_invoke 演算法平行執行位排序演算法。

以平行方式執行 bitonic 排序演算法

  1. #include新增標頭檔 ppl.h 的指示詞。

    #include <ppl.h>
    
  2. using新增 命名空間的 concurrency 指示詞。

    using namespace concurrency;
    
  3. 建立名為 parallel_bitonic_mege 的新函式,此函式會使用 parallel_invoke 演算法在有足夠的工作量時平行定序序列。 否則,呼叫 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);
       }   
    }
    
  4. 執行類似上一個步驟中,但針對 函 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);
       }
    }
    
  5. 建立函式的多 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); }
    );
    

下列完整範例會同時執行 bitonic 排序演算法的序列和平行版本。 此範例也會列印到主控台,以執行每個計算所需的時間。

// 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;
}

下列範例輸出適用於具有四個處理器的電腦。

serial time: 4353
parallel time: 1248

[靠上]

編譯程式碼

若要編譯器代碼,請複製程式碼,然後將它貼到 Visual Studio 專案中,或貼到名為 parallel-bitonic-sort.cpp 的檔案中,然後在 Visual Studio 命令提示字元視窗中執行下列命令。

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

穩固程式設計

此範例會 parallel_invoke 使用 演算法,而不是 並行::task_group 類別,因為每個工作組的存留期不會延伸至函式之外。 建議您在可以的時候使用 parallel_invoke ,因為它的執行額外負荷比 task group 物件少,因此可讓您撰寫效能更佳的程式碼。

只有有足夠的工作要做時,某些演算法的平行版本才會執行得更好。 例如,如果序列中有 500 個或更少的專案, bitonic_merge 則函 parallel_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函式