Porady: używanie parallel_invoke do napisania procedury sortowania równoległego
W tym dokumencie opisano, jak używać parallel_invoke algorytm, aby zwiększyć wydajność algorytmu sortowania bitonic.Rekursywnie algorytm sortowania bitonic sekwencji wejściowych jest podzielony na mniejsze posortowane partycji.Algorytm sortowania bitonic można uruchomić równolegle, ponieważ każda operacja partycji jest niezależna od innych operacji.
Chociaż sortowanie bitonic jest przykładem sortowania sieci sortuje wszystkie kombinacje sekwencji wejściowych, w tym przykładzie sortuje sekwencji, w których długości są potęgą liczby 2.
[!UWAGA]
W tym przykładzie użyto rutynowych sortowania równolegle do ilustracji.Można również użyć wbudowanych algorytmów sortowania, które zapewnia PPL: concurrency::parallel_sort, concurrency::parallel_buffered_sort, i concurrency::parallel_radixsort.Aby uzyskać więcej informacji, zobacz Algorytmy równoległe.
Sekcje
W tym dokumencie opisano następujące zadania:
Wykonanie seryjnie bitonicznego sortowania
Korzystając z parallel_invoke, aby wykonać bitoniczne sortowanie równolegle
Wykonanie seryjnie bitonicznego sortowania
Poniższy przykład pokazuje szeregowy wersji algorytm sortowania bitonic.bitonic_sort Funkcja dzieli się na dwie partycje sekwencji, sortuje te partycje w przeciwnych kierunkach i następnie scalenia wyniki.Ta funkcja wymaga dwa razy rekursywnie w stosunku do sortowania każdej partycji.
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);
}
[U góry]
Korzystając z parallel_invoke, aby wykonać bitoniczne sortowanie równolegle
Ta sekcja opisuje sposób używania parallel_invoke algorytm przeprowadzać równolegle algorytm sortowania bitonic.
Procedury
Aby wykonać algorytm bitonicznego sortowania równolegle
Dodaj #include w dyrektywie dla ppl.h pliku nagłówka.
#include <ppl.h>Dodaj using w dyrektywie dla concurrency obszaru nazw.
using namespace concurrency;Utwórz nową funkcję o nazwie parallel_bitonic_mege, który korzysta z parallel_invoke algorytm do scalenia sekwencje równolegle, jeśli istnieje wystarczająca ilość do zrobienia.W przeciwnym razie połączenie bitonic_merge szeregowo połączyć sekwencji.
// 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); } }Wykonanie procesu, zbliżony do w poprzednim kroku, ale dla bitonic_sort funkcji.
// 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); } }Utworzyć przeciążone wersję parallel_bitonic_sort funkcja, która sortuje tablicy w kolejności rosnącej.
// 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 Algorytm zmniejsza obciążenie wykonując ostatniego serię zadań w kontekście wywołującego.Na przykład, w parallel_bitonic_sort funkcji, pierwsze zadanie będzie uruchamiane w oddzielnych kontekstu, a drugie zadanie będzie uruchamiane w kontekście wywołującego.
// 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); }
);
W następującym przykładzie pełną wykonywana równolegle wersji bitonic algorytm sortowania i szeregowy.W przykładzie drukuje do konsoli również czas potrzebny do wykonania każdego obliczeń.
// 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;
}
Następujące przykładowe dane wyjściowe pochodzą z komputera, który ma cztery procesory.
[U góry]
Kompilowanie kodu
Aby skompilować kod, skopiuj go a następnie wkleić go w projekcie programu Visual Studio lub wkleić go w pliku o nazwie równolegle bitonic-sort.cpp , a następnie uruchomić następujące polecenie w oknie wiersza polecenia programu Visual Studio.
cl.exe /EHsc parallel-bitonic-sort.cpp
Niezawodne programowanie
W poniższym przykładzie użyto parallel_invoke algorytm zamiast concurrency::task_group klasy, ponieważ okres istnienia każdej grupy zadań nie wykracza poza funkcją.Firma Microsoft zaleca użycie parallel_invoke kiedy można ponieważ ma mniej wykonanie napowietrznych niż task group obiektów, a zatem pozwala pisać poprawy jego kod.
Równoległe wersje niektóre algorytmy lepiej tylko wtedy, gdy istnieje wystarczający pracy.Na przykład parallel_bitonic_merge funkcja wywołuje wersję szeregowego, bitonic_merge, jeśli istnieją elementy 500 lub mniejszej liczby w sekwencji.Można także zaplanować ogólnej strategii sortowania w oparciu o ilość pracy.Na przykład może to być efektywniejsze szeregowy wersji algorytmu szybkie sortowanie Jeśli tablica zawiera mniej niż 500 elementów, jak pokazano w następującym przykładzie:
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);
}
}
Podobnie jak w przypadku dowolnego algorytmu równoległego, firma Microsoft zaleca profilu i strojenie w razie potrzeby swój kod.
Zobacz też
Informacje
Koncepcje
Równoległość zadania (współbieżność środowiska wykonawczego)