Postupy: Použití algoritmu parallel_invoke k zápisu rutiny paralelního třídění
Tento dokument popisuje, jak použít parallel_invoke algoritmus pro zlepšení výkonu řadicí algoritmus bitonic.Rekurzivní algoritmus řazení bitonic rozdělí na menší oddíly seřazené vstupní sekvence.Řadicí algoritmus bitonic lze spustit paralelně, protože operace každého oddílu je nezávislý na jiných operací.
Přestože bitonic řadit je příklad řazení síť , seřadí všechny kombinace vstupní sekvence, jejichž délky se napájení ze dvou řad seřadí v tomto příkladu.
[!POZNÁMKA]
Tento příklad používá paralelní řadění pro ilustraci.Můžete také použít předdefinované algoritmy třídění poskytuje PPL: concurrency::parallel_sort, concurrency::parallel_buffered_sort, a concurrency::parallel_radixsort.Další informace naleznete v tématu Paralelní algoritmy.
Oddíly
Tento dokument popisuje následující úlohy:
Sériové provádění bitonického řazení
Paralelní provádění bitonického řazení s použitím algoritmu parallel_invoke
Sériové provádění bitonického řazení
Následující příklad ukazuje sériové verze algoritmu řazení bitonic.bitonic_sort Funkce pořadí dělí na dva oddíly, řadí tyto oddíly ve směru a potom sloučí výsledky.Tato funkce volá dvakrát rekurzivně sama řazení jednotlivých oddílů.
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);
}
[Nahoře]
Paralelní provádění bitonického řazení s použitím algoritmu parallel_invoke
Tato část popisuje způsob použití parallel_invoke algoritmus, algoritmus řazení bitonic provést současně.
Procedury
Paralelní provádění algoritmu bitonického řazení
Přidat #include pro ppl.h soubor záhlaví.
#include <ppl.h>Přidat using pro concurrency obor názvů.
using namespace concurrency;Vytvořit zcela novou funkci, nazvanou parallel_bitonic_mege, který používá parallel_invoke algoritmus ke sloučení sekvence paralelně, pokud je dostatečné množství práce do.Jinak volání bitonic_merge z pořadí sloučení sériově.
// 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); } }Proces, který se podobá v předchozím kroku, ale pro provedení bitonic_sort funkce.
// 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); } }Vytvoření přetížené verze parallel_bitonic_sort funkce, která se řadí pole ve vzestupném pořadí.
// 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 Algoritmus snižuje režii provedením poslední řadu úkolů v kontextu volajícího.Například v parallel_bitonic_sort první úloha bude spuštěna v kontextu samostatné funkce, a druhá úloha bude spuštěna v kontextu volajícího.
// 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); }
);
Kompletní příklad provádí sériový a paralelní verze algoritmu řazení bitonic.Příklad vytiskne také konzolu pro čas, který je vyžadován k provedení každého výpočtu.
// 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;
}
Následující ukázkový výpis je pro počítač se čtyřmi procesory.
[Nahoře]
Probíhá kompilace kódu
Kompilovat kód, zkopírujte jej a vložte do projektu sady Visual Studio nebo vložit do souboru s názvem paralelní bitonic sort.cpp a potom spusťte následující příkaz v okně Příkazový řádek Visual Studio.
cl.exe /EHsc parallel-bitonic-sort.cpp
Robustní programování
V tomto příkladu parallel_invoke algoritmus místo concurrency::task_group třídy, protože životnost jednotlivých skupin úloh nepřesahuje funkci.Doporučujeme používat parallel_invoke když může protože má méně spuštění režii než task group objekty a umožňuje tedy napsat lepší provádění kódu.
Paralelní verze některé algoritmy poskytují lepší výkon pouze v případě, že není dostatek práce provádět.Například parallel_bitonic_merge sériové verzi volá funkce bitonic_merge, jsou-li 500 nebo méně prvků v posloupnosti.Můžete také naplánovat strategii celkového řazení založené na množství práce.Například může být efektivnější použití sériové verze algoritmu rychlé řazení, pokud pole obsahuje méně než 500 položek, jak je znázorněno v následujícím příkladu:
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);
}
}
Stejně jako u paralelního algoritmu, doporučujeme profilu a optimalizaci kódu podle potřeby.