Walkthrough: Using Task Groups to Improve Performance
[This documentation is for preview only, and is subject to change in later releases. Blank topics are included as placeholders.]
This walkthrough describes how to use task groups to improve the performance of the bitonic sort algorithm.
The bitonic sort algorithm recursively divides the input sequence into smaller sorted partitions.
The bitonic sort algorithm can run in parallel because each partition operation is independent of all other operations.
Although the bitonic sort is an example of a sorting network that sorts all combinations of input sequences, this example sorts sequences whose lengths are a power of two.
Sections
This walkthrough describes the following tasks:
Performing Bitonic Sort Serially
The following example shows the serial version of the bitonic sort algorithm.
The bitonic_sort function divides the sequence into two partitions, sorts those partitions in opposite directions, and then merges the results.
This function calls itself two times recursively to sort each partition.
const
bool INCREASING = true;
constbool 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 hi, bool dir)
{
if (hi > 1)
{
int m = hi / 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 hi, bool dir)
{
if (hi > 1)
{
// Divide the array into two partitions and then sort // the partitions in different directions.int m = hi / 2;
bitonic_sort(items, lo, m, INCREASING);
bitonic_sort(items, lo + m, m, DECREASING);
// Merge the results.
bitonic_merge(items,lo, hi, dir);
}
}
// Sorts the given sequence in increasing order.template <class T>
void bitonic_sort(T* items, int size)
{
bitonic_sort(items, 0, size, INCREASING);
}
[go to top]
Using structured_task_group to Perform Bitonic Sort in Parallel
This section describes how to use a structured_task_group object to perform the bitonic sort algorithm in parallel.
Procedures
To perform the bitonic sort algorithm in parallel
-
Add a #include directive for the header file ppl.h.
-
Add a using directive for the Concurrency namespace.
-
In the bitonic_merge function, remove the recursive function calls to that function.
-
Create a structured_task_group object that will merge the sequences in parallel.
structured_task_group tg;
-
Create a task_handle object that contains a work function that merges the first sequence in the task group.
auto task = make_task([&] {
bitonic_merge(items, lo, m, dir);
});
-
Call the structured_task_group::run method to start execution of the first task.
-
Merge the second partition on the calling context.
bitonic_merge(items, lo + m, m, dir);
-
Call the structured_task_group::wait method to wait for the first task to complete.
-
Perform a process that resembles the one in the earlier steps, but for the bitonic_sort function.
structured_task_group tg;
auto task = make_task([&] {
parallel_bitonic_sort(items, lo, m, INCREASING);
});
tg.run(task);
parallel_bitonic_sort(items, lo + m, m, DECREASING);
tg.wait();
The following complete example performs both the serial and the parallel versions of the bitonic sort algorithm.
The example also prints to the console the time that is required to perform each computation.
// parallel-bitonic-sort.cpp
// compile with: /EHsc
#include <windows.h>
#include <algorithm>
#include <iostream>
#include <ppl.h>
usingnamespace Concurrency;
usingnamespace 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;
}
constbool INCREASING = true;
constbool 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 hi, bool dir)
{
if (hi > 1)
{
int m = hi / 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 hi, bool dir)
{
if (hi > 1)
{
// Divide the array into two partitions and then sort // the partitions in different directions.int m = hi / 2;
bitonic_sort(items, lo, m, INCREASING);
bitonic_sort(items, lo + m, m, DECREASING);
// Merge the results.
bitonic_merge(items,lo, hi, 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 hi, bool dir)
{
// Merge the sequences concurrently if there is sufficient work to do.if (hi > 500)
{
int m = hi / 2;
for (int i = lo; i < lo + m; ++i)
{
compare(items, i, i + m, dir);
}
// Use a structured task group to merge the sequences in parallel.
structured_task_group tg;
// Use the task group to merge the first sequence.
auto task = make_task([&] {
parallel_bitonic_merge(items, lo, m, dir);
});
tg.run(task);
// Merge the second partition on the calling context.
parallel_bitonic_merge(items, lo + m, m, dir);
// Wait for the first task to complete.
tg.wait();
}
// Otherwise, perform the work serially.elseif (hi > 1)
{
bitonic_merge(items, lo, hi, dir);
}
}
// Sorts the given sequence in the specified order.template <class T>
void parallel_bitonic_sort(T* items, int lo, int hi, bool dir)
{
if (hi > 1)
{
// Divide the array into two partitions and then sort // the partitions in different directions.int m = hi / 2;
// Use a structured task group to sort the partitions in parallel.
structured_task_group tg;
// Use the task group to sort the first partition.
auto task = make_task([&] {
parallel_bitonic_sort(items, lo, m, INCREASING);
});
tg.run(task);
// Sort the second partition on the calling context.
parallel_bitonic_sort(items, lo + m, m, DECREASING);
// Wait for the first task to complete.
tg.wait();
// Merge the results.
parallel_bitonic_merge(items, lo, hi, 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.constint size = 0x200000;
// Create two large arrays and initialize them with random values.int* a1 = newint[size];
int* a2 = newint[size];
srand(42);
for(int i = 0; i < size; ++i)
{
a1[i] = a2[i] = rand();
}
__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;
}
The following sample output is for a computer that has four processors.
serial time: 4353
parallel time: 1248
[go to top]
Compiling the Code
To compile the code, copy it and then paste it in a Visual Studio project, or paste it in a file that is named parallel-bitonic-sort.cpp and then run the following command in a Visual Studio Command Prompt window.
cl.exe /EHsc parallel-bitonic-sort.cpp
Robust Programming
This example uses the structured_task_group class instead of the task_group class because the lifetime of each task group does not extend beyond a function.
We recommend that you use structured_task_group objects when you can because they have less execution overhead than task group objects, and therefore let you write better performing code.
When you use the structured_task_group class, you must manually create task_handle objects and make sure that the destructor of each task_handle object runs after the structured_task_group object finishes.
This example uses the make_task helper function to create task_handle objects.
This example reduces overhead by performing the last of a series of tasks on the calling context.
For example, it performs the first call to bitonic_merge in the task group and the second call on the calling context.
The parallel versions of some algorithms perform better only when there is sufficient work to do.
For example, the parallel_bitonic_merge function calls the serial version, bitonic_merge, if there are 500 or fewer elements in the sequence.
See Also
|
Visual Studio 2010 - Visual C++ チュートリアル: タスク グループの使用によるパフォーマンスの向上
[このドキュメントはプレビュー版であり、後のリリースで変更されることがあります。 空白のトピックは、プレースホルダーとして挿入されています。]
このチュートリアルでは、作業グループを使用して、bitonic 並べ替えアルゴリズムのパフォーマンスを向上させる方法について説明します。
bitonic の [並べ替えアルゴリズム再帰的には入力シーケンスを小さい並べ替えられたパーティションに分割します。
bitonic の並べ替えアルゴリズムは各パーティションの操作が他のすべての操作とは無関係で並列実行できます。
並べ替え入力シーケンスのすべての組み合わせを並べ替えますネットワーク の例を bitonic の並べ替えには、次の使用例シーケンスの長さが 2 の累乗を並べ替えます。
セクション
このチュートリアルでは、次のタスクについて説明します。
直列 Bitonic 並べ替えを実行します。
次の使用例は、bitonic の並べ替えアルゴリズムのシリアル バージョンを表示します。
bitonic_sort 関数はシーケンスを 2 つのパーティションに分割し、反対方向は、これらのパーティションを並べ替えますをし、結果を結合します。
この関数は各パーティションの並べ替えに 2 回繰り返し自体呼び出します。
const
bool INCREASING = true;
constbool 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 hi, bool dir)
{
if (hi > 1)
{
int m = hi / 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 hi, bool dir)
{
if (hi > 1)
{
// Divide the array into two partitions and then sort // the partitions in different directions.int m = hi / 2;
bitonic_sort(items, lo, m, INCREASING);
bitonic_sort(items, lo + m, m, DECREASING);
// Merge the results.
bitonic_merge(items,lo, hi, dir);
}
}
// Sorts the given sequence in increasing order.template <class T>
void bitonic_sort(T* items, int size)
{
bitonic_sort(items, 0, size, INCREASING);
}
[go to top]
Bitonic の並べ替えを実行する structured_task_group をパラレルでください。
ここでは、structured_task_group オブジェクトを使用して bitonic 並べ替えアルゴリズムを並列で実行する方法について説明します。
手順
bitonic 並べ替えアルゴリズムを並列で実行するには
-
ヘッダー ファイル ppl.h の #include ディレクティブを追加します。
-
using
名前空間の Concurrency ディレクティブを追加します。
-
bitonic_merge 関数でその関数に、再帰関数呼び出しを削除します。
-
並列で、シーケンスをマージする structured_task_group オブジェクトを作成します。
structured_task_group tg;
-
タスク グループに最初のシーケンスを結合する作業関数を含む、task_handle オブジェクトを作成します。
auto task = make_task([&] {
bitonic_merge(items, lo, m, dir);
});
-
最初のタスクの実行を開始する structured_task_group::run メソッドを呼び出します。
-
呼び出しコンテキストに 2 つ目のパーティションのマージします。
bitonic_merge(items, lo + m, m, dir);
-
最初のタスクを完了するまで待機する structured_task_group::wait メソッドを呼び出します。
-
1 つ前の手順では、bitonic_sort 関数のようなプロセスを実行します。
structured_task_group tg;
auto task = make_task([&] {
parallel_bitonic_sort(items, lo, m, INCREASING);
});
tg.run(task);
parallel_bitonic_sort(items, lo + m, m, DECREASING);
tg.wait();
次の完全な例では、シリアルと bitonic 並べ替えアルゴリズムの並列バージョンの両方を実行します。
使用例もコンソールに出力の各計算を実行する必要な時間。
// parallel-bitonic-sort.cpp
// compile with: /EHsc
#include <windows.h>
#include <algorithm>
#include <iostream>
#include <ppl.h>
usingnamespace Concurrency;
usingnamespace 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;
}
constbool INCREASING = true;
constbool 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 hi, bool dir)
{
if (hi > 1)
{
int m = hi / 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 hi, bool dir)
{
if (hi > 1)
{
// Divide the array into two partitions and then sort // the partitions in different directions.int m = hi / 2;
bitonic_sort(items, lo, m, INCREASING);
bitonic_sort(items, lo + m, m, DECREASING);
// Merge the results.
bitonic_merge(items,lo, hi, 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 hi, bool dir)
{
// Merge the sequences concurrently if there is sufficient work to do.if (hi > 500)
{
int m = hi / 2;
for (int i = lo; i < lo + m; ++i)
{
compare(items, i, i + m, dir);
}
// Use a structured task group to merge the sequences in parallel.
structured_task_group tg;
// Use the task group to merge the first sequence.
auto task = make_task([&] {
parallel_bitonic_merge(items, lo, m, dir);
});
tg.run(task);
// Merge the second partition on the calling context.
parallel_bitonic_merge(items, lo + m, m, dir);
// Wait for the first task to complete.
tg.wait();
}
// Otherwise, perform the work serially.elseif (hi > 1)
{
bitonic_merge(items, lo, hi, dir);
}
}
// Sorts the given sequence in the specified order.template <class T>
void parallel_bitonic_sort(T* items, int lo, int hi, bool dir)
{
if (hi > 1)
{
// Divide the array into two partitions and then sort // the partitions in different directions.int m = hi / 2;
// Use a structured task group to sort the partitions in parallel.
structured_task_group tg;
// Use the task group to sort the first partition.
auto task = make_task([&] {
parallel_bitonic_sort(items, lo, m, INCREASING);
});
tg.run(task);
// Sort the second partition on the calling context.
parallel_bitonic_sort(items, lo + m, m, DECREASING);
// Wait for the first task to complete.
tg.wait();
// Merge the results.
parallel_bitonic_merge(items, lo, hi, 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.constint size = 0x200000;
// Create two large arrays and initialize them with random values.int* a1 = newint[size];
int* a2 = newint[size];
srand(42);
for(int i = 0; i < size; ++i)
{
a1[i] = a2[i] = rand();
}
__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
[go to top]
コードのコンパイル
コードをコンパイルするには、コピー、Visual Studio プロジェクトに貼り付けるしたりという名前の並列-bitonic-sort.cpp の され Visual Studio コマンド プロンプト ウィンドウで、次のコマンドを実行しされるファイルに貼り付けます。
cl.exe /EHsc parallel-bitonic-sort.cpp
信頼性の高いプログラミング
次の使用例は各作業グループの有効期間は、関数を超えて拡張しないため、task_group structured_task_groupクラスの代わりに、 クラスを使用します。
できます、structured_task_group オブジェクトよりもオーバーヘッドが小さい実行があるように適切に実行するコードを記述するためので、ときに task group オブジェクトを使用することを推奨します。
structured_task_group クラスを使用する場合は手動でに オブジェクトの task_handle を作成し、 task_handle オブジェクトの終了後に各 structured_task_group オブジェクトのデストラクターが実行されることを確認する必要があります。
この例では、make_task ヘルパー関数を使用して task_handle オブジェクトを作成します。
次の使用例は、呼び出し元のコンテキストで最後の一連のタスクを実行してオーバーヘッドが減少します。
たとえば、bitonic_merge に最初の呼び出し、作業グループで、2 番目の呼び出し、呼び出し元のコンテキストで実行されます。
一部のアルゴリズムの並列バージョンを行うには十分な処理がある場合にのみより実行します。
たとえば、parallel_bitonic_merge 関数シーケンスに 500 または少ない要素がある場合は、シリアル バージョン bitonic_merge を呼び出します。
参照
|