Procedura: utilizzare parallel_invoke per scrivere una routine di ordinamento in parallelo
In questo documento viene descritto come utilizzare l'algoritmo parallel_invoke per migliorare le prestazioni dell'algoritmo di ordinamento bitonico. L'algoritmo di ordinamento bitonico divide in modo ricorsivo la sequenza di input in partizioni ordinate più piccole. L'algoritmo di ordinamento bitonico può essere eseguito in parallelo poiché ogni operazione della partizione è indipendente da tutte le altre operazioni.
Sebbene l'ordinamento bitonico sia un esempio di rete di ordinamento che ordina tutte le combinazioni di sequenze di input, in questo esempio vengono ordinate le sequenze la cui lunghezza è una potenza di due.
Sezioni
In questo documento vengono descritte le attività seguenti:
Esecuzione dell'ordinamento bitonico in serie
Utilizzo di parallel_invoke per eseguire l'ordinamento bitonico in parallelo
Esecuzione dell'ordinamento bitonico in serie
Nell'esempio seguente viene illustrata la versione seriale dell'algoritmo di ordinamento bitonico. La funzione bitonic_sort divide la sequenza in due partizioni, ordina tali partizioni in direzioni opposte, quindi unisce i risultati. Questa funzione chiama se stessa due volte in modo ricorsivo per ordinare ogni partizione.
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);
}
[vai all'inizio]
Utilizzo di parallel_invoke per eseguire l'ordinamento bitonico in parallelo
In questa sezione viene descritto come utilizzare l'algoritmo parallel_invoke per eseguire l'algoritmo di ordinamento bitonico in parallelo.
Procedure
Per eseguire l'algoritmo di ordinamento bitonico in parallelo
Aggiungere una direttiva #include per file di intestazione ppl.h.
#include <ppl.h>Aggiungere una direttiva using per lo spazio dei nomi Concurrency.
using namespace Concurrency;Creare una nuova funzione, denominata parallel_bitonic_mege, che utilizza l'algoritmo parallel_invoke per unire le sequenze in parallelo se esiste una quantità di lavoro sufficiente da eseguire. In caso contrario, chiamare bitonic_merge per unire le sequenze in serie.
// 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); } }Eseguire un processo analogo a quello riportato nel passaggio precedente, ma per la funzione 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); } }Creare una versione di overload della funzione parallel_bitonic_sort che ordina la matrice in ordine crescente.
// 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); }
L'algoritmo parallel_invoke riduce il sovraccarico eseguendo l'ultima di una serie di attività nel contesto di chiamata. Nella funzione parallel_bitonic_sort, ad esempio, la prima attività viene eseguita in un contesto separato, mentre la seconda nel contesto di chiamata.
// 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); }
);
Nell'esempio completo seguente viene eseguita sia la versione seriale che quella parallela dell'algoritmo di ordinamento bitonico. L'esempio inoltre visualizza nella console il tempo necessario per eseguire ciascun calcolo.
// 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;
}
L'output di esempio seguente è relativo a un computer con quattro processori.
serial time: 4353
parallel time: 1248
[vai all'inizio]
Compilazione del codice
Per compilare il codice, copiarlo e quindi incollarlo in un progetto di Visual Studio o incollarlo in un file denominato parallel-bitonic-sort.cpp, quindi eseguire il comando seguente in una finestra del prompt dei comandi di Visual Studio.
cl.exe /EHsc parallel-bitonic-sort.cpp
Programmazione robusta
In questo esempio viene utilizzato l'algoritmo parallel_invoke anziché la classe Concurrency::task_group affinché la durata di ogni gruppo di attività non venga estesa oltre una funzione. È consigliabile utilizzare parallel_invoke quando è possibile poiché ha meno sovraccarico di esecuzione degli oggetti task group e consente pertanto di scrivere un codice dalle prestazioni migliori.
Le prestazioni delle versioni parallele di alcuni algoritmi sono migliori solo in presenza di un discreto numero di operazioni da eseguire. La funzione parallel_bitonic_merge, ad esempio, chiama la versione seriale, bitonic_merge, se nella sequenza sono presenti meno di 500 elementi. È inoltre possibile pianificare la strategia di ordinamento globale in base alla quantità di lavoro. Ad esempio, potrebbe essere più efficiente utilizzare la versione seriale dell'algoritmo QuickSort se la matrice contiene un massimo di 500 elementi, come illustrato nell'esempio seguente:
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);
}
}
Come per qualsiasi algoritmo parallelo, è consigliabile profilare e ottimizzare il codice in base alle proprie esigenze.
Vedere anche
Riferimenti
Concetti
Parallelismo delle attività (runtime di concorrenza)
Cronologia delle modifiche
Data |
Cronologia |
Motivo |
|---|---|---|
|
Luglio 2010 |
Aggiornamento dell'esempio per utilizzare parallel_invoke. |
Miglioramento delle informazioni. |