Comment : utiliser parallel_invoke pour écrire une routine de tri parallèle
Ce document décrit comment utiliser l'algorithme parallel_invoke pour améliorer les performances de l'algorithme de tri bitonique. L'algorithme de tri bitonique divise de manière récursive la séquence d'entrée en plus petites partitions triées. L'algorithme de tri bitonique peut s'exécuter en parallèle car chaque opération de partition est indépendante de toutes les autres opérations.
Bien que le tri bitonique soit un exemple de réseau de tri qui trie toutes les combinaisons de séquences d'entrée, cet exemple trie des séquences dont les longueurs sont une puissance de deux.
Notes
Cet exemple utilise une routine de tri parallèle pour l'illustration.Vous pouvez également utiliser les algorithmes de tri intégrés que le PPL fournit : concurrency::parallel_sort, concurrency::parallel_buffered_sort, et concurrency::parallel_radixsort.Pour plus d'informations, consultez Algorithmes parallèles.
Sections
Ce document décrit les tâches suivantes :
Exécution de tri bitonique de façon séquentielle
Utilisation de parallel_invoke pour exécuter un tri bitonique en parallèle
Exécution de tri bitonique de façon séquentielle
L'exemple suivant illustre la version sérialisée de l'algorithme de tri bitonique. La fonction bitonic_sort divise la séquence en deux partitions, trie ces partitions dans des directions opposées, puis fusionne les résultats. Cette fonction s'appelle de manière récursive à deux reprises pour trier chaque partition.
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);
}
[Premières]
Utilisation de parallel_invoke pour exécuter un tri bitonique en parallèle
Cette section décrit comment utiliser l'algorithme parallel_invoke pour exécuter l'algorithme de tri bitonique en parallèle.
Procédures
Pour exécuter l'algorithme de tri bitonique en parallèle
Ajoutez une directive #include pour le fichier d'en-tête ppl.h.
#include <ppl.h>Ajoutez une directive using pour l'espace de noms concurrency.
using namespace concurrency;Créez une fonction, appelée parallel_bitonic_mege, qui utilise l'algorithme parallel_invoke pour fusionner les séquences en parallèle si la quantité de travail à effectuer est suffisante. Sinon, appelez bitonic_merge pour fusionner les séquences de façon séquentielle.
// 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); } }Exécutez un processus qui ressemble à celui de l'étape précédente, mais pour la fonction 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); } }Créez une version surchargée de la fonction parallel_bitonic_sort, qui trie le tableau en ordre croissant.
// 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'algorithme parallel_invoke réduit la charge en exécutant la dernière des séries de tâches sur le contexte appelant. Par exemple, dans la fonction parallel_bitonic_sort, la première tâche s'exécute sur un contexte distinct et la seconde tâche s'exécute sur le contexte appelant.
// 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); }
);
L'exemple complet suivant exécute à la fois les versions séquentielles et parallèles de l'algorithme de tri bitonique. L'exemple imprime également sur la console le temps requis pour effectuer chaque calcul.
// 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'exemple de sortie suivant concerne un ordinateur avec quatre processeurs.
[Premières]
Compilation du code
Pour compiler le code, copiez-le puis collez-le dans un projet Visual Studio, ou collez-le dans un fichier nommé parallel-bitonic-sort.cpp puis exécutez la commande suivante dans une fenêtre d'invite de commandes Visual Studio.
cl.exe /EHsc parallel-bitonic-sort.cpp
Programmation fiable
Cet exemple utilise l'algorithme parallel_invoke au lieu de la classe concurrency::task_group, car la durée de vie de chaque groupe de tâches ne s'étend pas au-delà d'une fonction. Dans la mesure du possible, nous vous conseillons d'utiliser parallel_invoke, car il a une charge d'exécution inférieure aux objets task group. Par conséquent, il permet d'écrire du code plus performant.
Les versions parallèles de certains algorithmes offrent de meilleures performances uniquement lorsqu'il y a une quantité de travail suffisante à effectuer. Par exemple, la fonction parallel_bitonic_merge appelle la version sérialisée, bitonic_merge, s'il y a 500 éléments ou moins dans la séquence. Vous pouvez également organiser votre stratégie de tri globale en fonction de la quantité de travail. Par exemple, il peut s'avérer plus efficace d'utiliser la version sérialisée de l'algorithme de tri rapide si le tableau comporte moins de 500 éléments, comme indiqué dans l'exemple suivant :
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);
}
}
À l'instar de n'importe quel algorithme parallèle, nous vous conseillons de profiler et d'adapter votre code en fonction de vos besoins.