Comment : utiliser parallel_invoke pour écrire une routine de tri parallèle
Ce document explique 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 partitions triées plus petites. 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 les séquences dont les longueurs sont une puissance de deux.
Remarque
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 ::p arallel_sort, concurrency ::p arallel_buffered_sort et concurrency ::p arallel_radixsort. Pour plus d’informations, consultez Algorithmes parallèles.
Sections
Ce document décrit les tâches suivantes :
Exécution d’un tri bitonique en série
L’exemple suivant montre la version série de l’algorithme de tri bitonique. La bitonic_sort fonction divise la séquence en deux partitions, trie ces partitions dans des directions opposées, puis fusionne les résultats. Cette fonction s’appelle deux fois de manière récursive 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);
}
[Haut]
Utilisation de parallel_invoke pour effectuer un tri bitonique en parallèle
Cette section explique comment utiliser l’algorithme parallel_invoke pour effectuer l’algorithme de tri bitonique en parallèle.
Pour effectuer l’algorithme de tri bitonique en parallèle
Ajoutez une
#includedirective pour le fichier d’en-tête ppl.h.#include <ppl.h>Ajoutez une
usingdirective pour l’espaceconcurrencyde noms.using namespace concurrency;Créez une fonction appelée , qui
parallel_bitonic_megeutilise l’algorithmeparallel_invokepour fusionner les séquences en parallèle s’il y a suffisamment de travail à effectuer. Sinon, appelezbitonic_mergepour fusionner les séquences en série.// 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); } }Effectuez un processus semblable à celui de l’étape précédente, mais pour la
bitonic_sortfonction.// 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
parallel_bitonic_sortfonction qui trie le tableau dans l’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_invokeréduit la surcharge en effectuant la dernière série de tâches sur le contexte appelant. Par exemple, dans la fonction, laparallel_bitonic_sortpremière tâche s’exécute sur un contexte distinct et la deuxième 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 la série et les versions parallèles de l’algorithme de tri bitonique. L’exemple imprime également dans la console l’heure nécessaire 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 équipé de quatre processeurs.
serial time: 4353
parallel time: 1248
[Haut]
Compilation du code
Pour compiler le code, copiez-le, 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. Nous vous recommandons d’utiliser parallel_invoke quand vous pouvez le faire, car il a moins de surcharge d’exécution que task group les objets, et vous permet donc d’écrire du code plus performant.
Les versions parallèles de certains algorithmes ne fonctionnent mieux que lorsqu’il y a suffisamment de travail à effectuer. Par exemple, la parallel_bitonic_merge fonction appelle la version série, bitonic_merges’il y a 500 éléments ou moins dans la séquence. Vous pouvez également planifier votre stratégie globale de tri en fonction de la quantité de travail. Par exemple, il peut être plus efficace d’utiliser la version série de l’algorithme de tri rapide si le tableau contient moins de 500 éléments, comme illustré 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);
}
}
Comme avec n’importe quel algorithme parallèle, nous vous recommandons de profiler et de paramétrer votre code selon les besoins.
Voir aussi
Commentaires
Bientôt disponible : pendant toute l’année 2024, nous allons éliminer progressivement Problèmes GitHub comme mécanisme de commentaires pour le contenu et le remplacer par un nouveau système de commentaires. Pour plus d’informations, voir : https://aka.ms/ContentUserFeedback.
Soumettre et afficher des commentaires pour