方法: 並列呼び出しを使用して並列並べ替えルーチンを記述する

[アーティクル]
06/09/2015

ここでは、parallel_invoke アルゴリズムを使用して、バイトニックソートアルゴリズムのパフォーマンスを向上させる方法について説明します。バイトニックソートアルゴリズムでは、入力シーケンスを、より小さな並べ替え済みのパーティションへと再帰的に分割します。各パーティションの操作は他のすべての操作から独立しているため、バイトニックソートアルゴリズムは並列的に実行することができます。

バイトニックソートは、入力シーケンスのあらゆる組み合わせを並べ替えるソーティングネットワークの 1 つではありますが、この例で並べ替えるのは、長さが 2 の累乗であるシーケンスです。

注意

この例では、例を示す目的で、並列並べ替えルーチンを使用します。また、concurrency::parallel_sort、concurrency::parallel_buffered_sort、および concurrency::parallel_radixsort という、PPL に用意されている組み込みの並べ替えアルゴリズムを使用することもできます。詳細については、「並列アルゴリズム」を参照してください。

セクション

ここでは、次のタスクについて説明します。

バイトニックソートを逐次的に実行する
parallel_invoke を使用してバイトニックソートを並列に実行する

バイトニックソートを逐次的に実行する

次の例は、逐次的なバイトニックソートアルゴリズムを示しています。 bitonic_sort 関数は、シーケンスを 2 つのパーティションに分割し、一方のパーティションは昇順に、もう一方のパーティションは降順に並べ替えた後、その結果をマージします。この関数は、自分自身を 2 回再帰的に呼び出して、それぞれのパーティションを並べ替えます。

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 アルゴリズムを使用して、バイトニックソートアルゴリズムを並列に実行する方法について説明します。

手順

バイトニックソートアルゴリズムを並列実行するには

ヘッダーファイル ppl.h の #include ディレクティブを追加します。
```
#include <ppl.h>
```
concurrency 名前空間の using ディレクティブを追加します。
```
using namespace concurrency;
```

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

前の手順と似たプロセスを実行します (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 関数では、1 つ目のタスクは別のコンテキストで実行され、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); }
);

以下に示したのは完成したコード例です。逐次実行版と並列実行版の両方のバイトニックソートアルゴリズムが実行されます。この例では、それぞれの計算に要する時間もコンソールに出力します。

// 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 つのプロセッサを備えたコンピューターを使用したときのサンプル出力を次に示します。

[トップ]

コードのコンパイル

このコードをコンパイルするには、コードをコピーし、Visual Studio プロジェクトに貼り付けるか、parallel-bitonic-sort.cpp という名前のファイルに貼り付けてから、Visual Studio のコマンドプロンプトウィンドウで次のコマンドを実行します。

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

信頼性の高いプログラミング

それぞれのタスクグループの有効期間が関数を超えることはないため、この例では、concurrency::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 を使用してバイトニックソートを並列に実行する

バイトニックソートアルゴリズムを並列実行するには