Algorithmes parallèles
La Bibliothèque de modèles parallèles (PPL) fournit des algorithmes qui exécutent simultanément du travail sur des collections de données. Ces algorithmes ressemblent à ceux fournis par la Bibliothèque de modèles Standard (STL, Standard Template Library).
Les algorithmes parallèles sont composés de fonctionnalités existantes du runtime d'accès concurrentiel. Par exemple, l'algorithme concurrency::parallel_for utilise un objet concurrency::structured_task_group pour effectuer les itérations de boucle parallèles. L'algorithme parallel_for partitionne le travail de façon optimale en fonction de la quantité de ressources de calcul disponible.
Sections
Algorithme parallel_for
Algorithme parallel_for_each
Algorithme parallel_invoke
Algorithmes parallel_transform et parallel_reduce
Algorithme parallel_transform
Algorithme parallel_reduce
Exemple : exécution du mappage et de la réduction en parallèle
Partitionnement du travail
Tri parallèle
- Choisir un algorithme de tri
Algorithme parallel_for
L'algorithme concurrency::parallel_for effectue à plusieurs reprises la même tâche en parallèle. Chacune de ces tâches est peut être paramétrée par une valeur d'itération. Cet algorithme est utile lorsque vous avez un corps de boucle qui ne partage pas de ressources parmi les itérations de cette boucle.
L'algorithme parallel_for partitionne les tâches de façon optimale pour une exécution en parallèle. Il utilise un algorithme de vol de travail et de vol de portée pour équilibrer ces partitions lorsque les charges de travail sont déséquilibrées. Lorsqu'une itération de boucle effectue un blocage coopératif, le runtime redistribue la plage des itérations assignée au thread actuel à d'autres threads ou processeurs. De même, lorsqu'un thread termine une plage d'itérations, le runtime redistribue le travail d'autres threads sur ce thread. L'algorithme parallel_for prend également en charge le parallélisme imbriqué. Lorsqu'une boucle parallèle contient une autre boucle parallèle, le runtime coordonne le traitement efficace des ressources entre les corps des boucles pour une exécution en parallèle.
L'algorithme parallel_for a plusieurs versions surchargées. La première version prend une valeur de départ, une valeur de fin et une fonction de travail (expression lambda, objet de fonction ou pointeur fonction). La deuxième version prend une valeur de départ, une valeur de fin, une valeur d'étape et une fonction de travail. La première version de cette fonction utilise 1 comme valeur d'étape. Les versions restantes prennent les autres objets partitioneurs, qui vous permettent de spécifier comment parallel_for devraient être divisées des plages parmi les threads. Les partitionneurs sont expliqués plus en détail dans la section Partitionner le travail de ce document.
Vous pouvez convertir de nombreuses boucles for de façon à utiliser parallel_for. Cependant, l'algorithme parallel_for diffère de l'instruction for des manières suivantes :
L'algorithme parallel_for parallel_for n'exécute pas les tâches dans un ordre prédéterminé.
L'algorithme parallel_for ne prend pas en charge les conditions d'arrêt arbitraires. L'algorithme parallel_for s'arrête lorsque la valeur actuelle de la variable d'itération est inférieure de 1 à _Last.
Le paramètre de type _Index_type doit être un type entier. Ce type intégral peut être signé ou non signé.
L'itération de boucle doit être vers l'avant. L'algorithme parallel_for lève une exception de type std::invalid_argument si le paramètre _Step est inférieur à 1.
Le mécanisme de gestion des exceptions pour l'algorithme parallel_for diffère de celui utilisé pour une boucle for. Si plusieurs exceptions se produisent simultanément dans un corps de boucle parallèle, le runtime propage une seule des exceptions sur le thread appelé parallel_for. De plus, lorsqu'une itération de boucle lève une exception, le runtime n'arrête pas immédiatement la boucle globale. Au lieu de cela, l'état de la boucle devient « annulé » et le runtime ignore toutes les tâches qui n'ont pas encore commencé. Pour plus d'informations sur la gestion des exceptions et les algorithmes parallèles, consultez Gestion des exceptions dans le runtime d'accès concurrentiel.
Bien que l'algorithme parallel_for ne prenne pas en charge les conditions d'arrêt arbitraires, vous pouvez utiliser l'annulation pour arrêter toutes les tâches. Pour plus d'informations sur l'annulation, consultez Annulation dans la bibliothèque de modèles parallèles.
Notes
Le coût de planification qui résulte de l'équilibrage de la charge et de la prise en charge des fonctionnalités telles que l'annulation ne l'emporte pas sur les avantages qui découlent de l'exécution du corps de la boucle en parallèle, surtout lorsque le corps de la boucle est relativement petit.Vous pouvez minimiser cette surcharge en utilisant un partitionneur dans la boucle parallèle.Pour plus d'informations, consultez Partitionner le travail plus loin dans ce document.
Exemple
L'exemple suivant illustre la structure de base de l'algorithme parallel_for. Cet exemple imprime sur la console chaque valeur de la plage [1, 5] en parallèle.
// parallel-for-structure.cpp
// compile with: /EHsc
#include <ppl.h>
#include <array>
#include <sstream>
#include <iostream>
using namespace concurrency;
using namespace std;
int wmain()
{
// Print each value from 1 to 5 in parallel.
parallel_for(1, 6, [](int value) {
wstringstream ss;
ss << value << L' ';
wcout << ss.str();
});
}
Cet exemple génère l'exemple de sortie suivant :
Étant donné que l'algorithme parallel_for agit sur chaque élément en parallèle, l'ordre dans lequel les valeurs sont imprimées sur la console varie.
Pour obtenir un exemple complet utilisant l'algorithme parallel_for, consultez Comment : écrire une boucle parallel_for.
[Premières]
Algorithme parallel_for_each
L'algorithme concurrency::parallel_for_each effectue les tâches sur un conteneur itératif, comme ceux fournis par la bibliothèque STL, en parallèle. Il utilise la même logique de partitionnement que l'algorithme parallel_for.
L'algorithme parallel_for_each ressemble à l'algorithme std::for_each STL, à l'exception près que l'algorithme parallel_for_each exécute les tâches simultanément. Comme d'autres algorithmes parallèles, parallel_for_each n'exécute pas les tâches dans un ordre spécifique.
Bien que l'algorithme parallel_for_each fonctionne sur les itérateurs avancés et les itérateurs d'accès aléatoire, ses performances sont supérieures avec les itérateurs d'accès aléatoire.
Exemple
L'exemple suivant illustre la structure de base de l'algorithme parallel_for_each. Cet exemple imprime sur la console chaque valeur dans un objet std::array en parallèle.
// parallel-for-each-structure.cpp
// compile with: /EHsc
#include <ppl.h>
#include <array>
#include <sstream>
#include <iostream>
using namespace concurrency;
using namespace std;
int wmain()
{
// Create an array of integer values.
array<int, 5> values = { 1, 2, 3, 4, 5 };
// Print each value in the array in parallel.
parallel_for_each(begin(values), end(values), [](int value) {
wstringstream ss;
ss << value << L' ';
wcout << ss.str();
});
}
/* Sample output:
5 4 3 1 2
*/
Cet exemple génère l'exemple de sortie suivant :
Étant donné que l'algorithme parallel_for_each agit sur chaque élément en parallèle, l'ordre dans lequel les valeurs sont imprimées sur la console varie.
Pour obtenir un exemple complet utilisant l'algorithme parallel_for_each, consultez Comment : écrire une boucle parallel_for_each.
[Premières]
Algorithme parallel_invoke
L'algorithme concurrency::parallel_invoke exécute un ensemble de tâches en parallèle. Il retourne des valeurs une fois que chaque tâche est terminée. Cet algorithme est utile lorsque vous voulez exécuter simultanément plusieurs tâches indépendantes.
L'algorithme parallel_invoke prend comme paramètres une série de fonctions de travail (fonctions lambda, objets de fonction ou pointeurs fonction). L'algorithme parallel_invoke est surchargé pour prendre entre deux et dix paramètres. Chaque fonction que vous passez à parallel_invoke doit prendre les paramètres nuls.
Comme d'autres algorithmes parallèles, parallel_invoke n'exécute pas les tâches dans un ordre spécifique. La rubrique Parallélisme des tâches (runtime d'accès concurrentiel) illustre le rapport entre l'algorithme parallel_invoke et les tâches et groupes de tâches.
Exemple
L'exemple suivant illustre la structure de base de l'algorithme parallel_invoke. Cet exemple appelle simultanément la fonction twice sur trois variables locales et affiche le résultat sur la console.
// parallel-invoke-structure.cpp
// compile with: /EHsc
#include <ppl.h>
#include <string>
#include <iostream>
using namespace concurrency;
using namespace std;
// Returns the result of adding a value to itself.
template <typename T>
T twice(const T& t) {
return t + t;
}
int wmain()
{
// Define several values.
int n = 54;
double d = 5.6;
wstring s = L"Hello";
// Call the twice function on each value concurrently.
parallel_invoke(
[&n] { n = twice(n); },
[&d] { d = twice(d); },
[&s] { s = twice(s); }
);
// Print the values to the console.
wcout << n << L' ' << d << L' ' << s << endl;
}
Cet exemple génère la sortie suivante :
Pour obtenir des exemples complets utilisant l'algorithme parallel_invoke, consultez Comment : utiliser parallel_invoke pour écrire une routine de tri parallèle et Comment : utiliser parallel_invoke pour exécuter des opérations parallèles.
[Premières]
Algorithmes parallel_transform et parallel_reduce
Les algorithmes concurrency::parallel_transform et concurrency::parallel_reduce sont respectivement les versions parallèles des algorithmes STL std::transform et std::accumulate. Les versions de runtime d'accès concurrentiel se comportent comme des versions de STL à ceci près que la commande d'opération n'est pas définie car elles s'exécutent en parallèle. Utilisez ces algorithmes lorsque vous travaillez avec un ensemble qui est assez grand pour obtenir les avantages en performance et en extensibilité d'un traitement en parallèle.
Important
Les algorithmes parallel_transform et parallel_reduce prennent uniquement en charge l'accès aléatoire,bidirectionnelle et transfèrent des itérateurs car les itérateurs produisent les adresses mémoire stables.En outre, les itérateurs doivent produire des l-values non-const.
Algorithme parallel_transform
Utilisez l'algorithme parallel transform pour exécuter un grand nombre d'opérations de mise en parallèle de données. Par exemple, vous pouvez :
Ajustez la luminosité d'une image, et exécutez d'autres opérations de traitement des images.
Ajoutez ou soustrayez le produit scalaire entre plusieurs vecteurs, et effectuez d'autres calculs numériques sur les vecteurs.
Exécutez le lancement de rayon 3D où chaque itération fait référence à un unique pixel qui doit être affiché.
L'exemple suivant illustre la structure de base de l'algorithme, aussi appelée parallel_transform. L'exemple suivant inverse chaque élément d'un objet std::vector de deux manières. La première méthode utilise une expression lambda. La deuxième méthode utilise std::negate, qui dérive de std::unary_function.
// basic-parallel-transform.cpp
// compile with: /EHsc
#include <ppl.h>
#include <random>
using namespace concurrency;
using namespace std;
int wmain()
{
// Create a large vector that contains random integer data.
vector<int> values(1250000);
generate(begin(values), end(values), mt19937(42));
// Create a vector to hold the results.
// Depending on your requirements, you can also transform the
// vector in-place.
vector<int> results(values.size());
// Negate each element in parallel.
parallel_transform(begin(values), end(values), begin(results), [](int n) {
return -n;
});
// Alternatively, use the negate class to perform the operation.
parallel_transform(begin(values), end(values), begin(values), negate<int>());
}
Avertissement
Cet exemple illustre l'utilisation simple de parallel_transform.Dans la mesure où la fonction de travail n'effectue pas une quantité importante de travail, une augmentation significative des performances n'est pas attendue dans cet exemple.
L'algorithme parallel_transform a deux surcharges. La première surcharge accepte une seule plage d'entrée et une fonction unaire. La fonction unaire peut être une expression lambda qui prend un argument, un objet de la fonction, ou un type qui dérive de unary_function. La deuxième surcharge prend deux plages d'entrée et une fonction binaire. La fonction binaire peut être une expression lambda qui accepte deux arguments, un objet de la fonction, ou un type qui dérive de std::binary_function. L'exemple de code suivant illustre ces différences.
//
// Demonstrate use of parallel_transform together with a unary function.
// This example uses a lambda expression.
parallel_transform(begin(values), end(values),
begin(results), [](int n) {
return -n;
});
// Alternatively, use the negate class:
parallel_transform(begin(values), end(values),
begin(results), negate<int>());
//
// Demonstrate use of parallel_transform together with a binary function.
// This example uses a lambda expression.
parallel_transform(begin(values), end(values), begin(results),
begin(results), [](int n, int m) {
return n * m;
});
// Alternatively, use the multiplies class:
parallel_transform(begin(values), end(values), begin(results),
begin(results), multiplies<int>());
Important
L'itérateur que vous donnez à la sortie de parallel_transform doit parfaitement chevaucher l'itérateur d'entrée ou ne pas le chevaucher du tout.Le fonctionnement de cet algorithme n'est pas spécifié si les itérateurs d'entrée et de sortie se chevauchent partiellement.
Algorithme parallel_reduce
L'algorithme parallel_reduce est utile lorsque vous avez une séquence d'événements qui satisfont la propriété associative. (Cet algorithme ne requiert pas la propriété commutative.) Voici certaines opérations que vous pouvez effectuer avec parallel_reduce:
Multiplier les séquences de matrices pour produire une matrice.
Multipliez un vecteur dans une séquence de matrices pour produire un vecteur.
Calculez la taille d'une séquence de chaînes.
Associez une liste d'éléments, tels que des chaînes, dans un élément.
L'exemple suivant montre comment utiliser l'algorithme parallel_reduce pour combiner une séquence de chaînes en une seule chaîne. Comme avec les exemples pour parallel_transform, l'amélioration des performances n'est pas attendue dans l'exemple de base.
// basic-parallel-reduce.cpp
// compile with: /EHsc
#include <ppl.h>
#include <iostream>
#include <string>
#include <vector>
using namespace concurrency;
using namespace std;
int wmain()
{
// Create a vector of strings.
vector<wstring> words;
words.push_back(L"Lorem ");
words.push_back(L"ipsum ");
words.push_back(L"dolor ");
words.push_back(L"sit ");
words.push_back(L"amet, ");
words.push_back(L"consectetur ");
words.push_back(L"adipiscing ");
words.push_back(L"elit.");
// Reduce the vector to one string in parallel.
wcout << parallel_reduce(begin(words), end(words), wstring()) << endl;
}
/* Output:
Lorem ipsum dolor sit amet, consectetur adipiscing elit.
*/
Dans de nombreux cas, vous pouvez considérer parallel_reduce comme rapide pour l'utilisation de l'algorithme parallel_for_each avec la classe concurrency::combinable.
Exemple : exécution du mappage et de la réduction en parallèle
Une opération de mappage s'applique la fonction à chaque valeur dans une séquence. Une opération de réduction combine les éléments d'une séquence dans une valeur. Utilisez les classes de (STL) std::transform std::accumulate de la Standard TEMPLATE Library (STL) pour effectuer le mappage et les opérations de réductions. Toutefois, pour de nombreux problèmes, utilisez l'algorithme parallel_transform pour exécuter l'opération de mappage en parallèle et l'algorithme parallel_reduce pour exécuter l'opération de réduction en parallèle.
L'exemple suivant compare le temps nécessaire pour calculer la somme des premiers numéros à la suite et en parallèle. Les transformations, non primordiales, de phase de mappage se déprécient jusqu'à 0 et la phase réduite additionne les valeurs.
// parallel-map-reduce-sum-of-primes.cpp
// compile with: /EHsc
#include <windows.h>
#include <ppl.h>
#include <array>
#include <numeric>
#include <iostream>
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;
}
// Determines whether the input value is prime.
bool is_prime(int n)
{
if (n < 2)
return false;
for (int i = 2; i < n; ++i)
{
if ((n % i) == 0)
return false;
}
return true;
}
int wmain()
{
// Create an array object that contains 200000 integers.
array<int, 200000> a;
// Initialize the array such that a[i] == i.
iota(begin(a), end(a), 0);
int prime_sum;
__int64 elapsed;
// Compute the sum of the numbers in the array that are prime.
elapsed = time_call([&] {
transform(begin(a), end(a), begin(a), [](int i) {
return is_prime(i) ? i : 0;
});
prime_sum = accumulate(begin(a), end(a), 0);
});
wcout << prime_sum << endl;
wcout << L"serial time: " << elapsed << L" ms" << endl << endl;
// Now perform the same task in parallel.
elapsed = time_call([&] {
parallel_transform(begin(a), end(a), begin(a), [](int i) {
return is_prime(i) ? i : 0;
});
prime_sum = parallel_reduce(begin(a), end(a), 0);
});
wcout << prime_sum << endl;
wcout << L"parallel time: " << elapsed << L" ms" << endl << endl;
}
/* Sample output:
1709600813
serial time: 7406 ms
1709600813
parallel time: 1969 ms
*/
Pour obtenir un autre exemple qui effectue un mappage et réduit l'opération en parallèle, consultez Comment : exécuter des opérations de mappage et de réduction en parallèle.
[Premières]
Partitionnement du travail
Pour mettre en parallèle une opération sur une source de données, une étape essentielle consiste à partitionner la source en plusieurs sections auxquelles il est possible d'accéder de manière simultanée par le biais de plusieurs threads. Un partitionneur spécifie comment un algorithme parallèle doit partitionner des plages parmi des threads. Comme expliqué précédemment dans ce document, le PPL utilise un mécanisme par défaut de partitionnement qui crée la première charge de travail puis utilise un algorithme de vol de travail et une plage de vol pour équilibrer les partitions lorsque les charges de travail sont non équilibrées. Par exemple, lorsqu'une boucle d'itération termine une plage d'itérations, le runtime redistribue le travail d'autres threads sur ce thread. Toutefois, pour certains scénarios, vous pourriez vouloir spécifier un autre mécanisme de partitionnement qui est mieux adapté à votre problème.
Les algorithmes parallel_for, parallel_for_each, et les algorithmes parallel_transform fournissent des versions surchargées qui prennent un paramètre supplémentaire, _Partitioner. Ce paramètre définit le type de partitioneur qui divise le travail. Voici les types de partitionneurs que le PPL définit :
concurrency::affinity_partitioner
Divise le travail en un nombre fixe de plages (généralement le nombre de threads de travail disponibles pour travailler sur la boucle). Ce type de partitionneur ressemble à static_partitioner, mais améliore l'affinité du cache par la manière dont il mappe les plages des threads de travail. Ce type de partitionneur peut améliorer les performances lorsqu'une boucle est exécutée plusieurs fois sur le même set de données (par exemple une boucle dans une boucle) et que les données s'intègrent dans le cache. Ce partitionneur ne participe pas entièrement à l'annulation. Il n'utilise pas la sémantique de blocage coopérative et ne peut donc pas être utilisé avec des boucles parallèles qui ont une dépendance par transfert.concurrency::auto_partitioner
Divise le travail en un nombre initial de plages (généralement le nombre de threads de travail disponibles pour travailler sur la boucle). Le runtime utilise ce type par défaut lorsque vous n'appelez pas un algorithme parallèle surchargé qui accepte un paramètre _Partitioner. Chaque plage peut être divisée en sous-plages, et permet ainsi à l'équilibrage de charges pour produire. Lorsqu'une plage de travail est complète, le runtime redistribue les sous-plages de travail d'autres threads sur ce thread. Utilisez ce partitionneur si votre charge de travail ne correspond pas à l'une des autres catégories ou si vous avez besoin d'une prise en charge complète de l'annulation ou d'un blocage coopératif.concurrency::simple_partitioner
Divise le travail en plages telles que chaque plage comprend au moins le nombre d'itérations spécifiées par la taille de segment donnée. Ce type de partitionneur participe à l'équilibrage de charges; toutefois, le runtime ne divise pas les plages en sous-plages. Pour chaque processus de travail, le runtime vérifie l'annulation et exécute l'équilibrage de charges après que les itérations _Chunk_size soient achevées.concurrency::static_partitioner
Divise le travail en un nombre fixe de plages (généralement le nombre de threads de travail disponibles pour travailler sur la boucle). Ce type de partitionneur peut améliorer les performances car il n'utilise pas le vol de travail et par conséquent moins de charge. Utilisez ce type de partitionneur lorsque chaque itération de la boucle parallèle effectue une quantité fixe et uniforme de travail et vous n'avez pas besoin de prise en charge de l'annulation ou ne transférez pas le blocage coopératif.
Avertissement
Les algorithmes parallel_for_each et parallel_transform ne prennent en charge que les conteneurs qui utilisent les itérateurs d'accès sélectif (par exemple std::vector) pour le type statique, simple, et les partitionneurs d'affinité.L'utilisation des conteneurs qui utilisent les itérateurs bidirectionnels et par transfert produit une erreur de compilation.Le partitionneur par défaut, auto_partitioner, prend en charge l'ensemble de ces trois types d'itération.
En général, ces partitionneurs sont utilisées de la même façon, à l'exception affinity_partitioner. La plupart des types de partitionneurs ne contiennent pas d'état et ne sont pas modifiés par le runtime. Il est par conséquent possible de créer ces objets de partitioneur au site d'appel, comme le montre l'exemple suivant.
// static-partitioner.cpp
// compile with: /EHsc
#include <ppl.h>
using namespace concurrency;
void DoWork(int n)
{
// TODO: Perform a fixed amount of work...
}
int wmain()
{
// Use a static partitioner to perform a fixed amount of parallel work.
parallel_for(0, 100000, [](int n) {
DoWork(n);
}, static_partitioner());
}
Toutefois, vous devez transmettre un objet affinity_partitioner comme un non-const, référence de l-value afin que l'algorithme puisse signaler l'état des futures boucles de réutilisation. L'exemple suivant illustre une application simple qui exécute plusieurs fois la même opération sur un set de données en parallèle . L'utilisation de affinity_partitioner peut améliorer les performances parce que la table est susceptible d'être contenue dans le cache.
// affinity-partitioner.cpp
// compile with: /EHsc
#include <ppl.h>
#include <array>
using namespace concurrency;
using namespace std;
int wmain()
{
// Create an array and fill it with zeroes.
array<unsigned char, 8 * 1024> data;
data.fill(0);
// Use an affinity partitioner to perform parallel work on data
// that is likely to remain in cache.
// We use the same affinitiy partitioner throughout so that the
// runtime can schedule work to occur at the same location for each
// iteration of the outer loop.
affinity_partitioner ap;
for (int i = 0; i < 100000; i++)
{
parallel_for_each(begin(data), end(data), [](unsigned char& c)
{
c++;
}, ap);
}
}
Avertissement
Soyez prudent lorsque vous modifiez le code existant qui repose sur la sémantique du blocage coopérative pour utiliser static_partitioner ou affinity_partitioner.Ces types de partitionneurs n'utilisent pas l'équilibrage de charges ou les plages de vol, et par conséquent peuvent modifier le comportement de votre application.
La meilleure méthode pour déterminer s'il convient d'utiliser un partitionneur dans tout scénario donné consiste à expérimenter et à mesurer le temps que prennent les opérations avec des charges et des configurations d'ordinateurs représentatives. Par exemple, le partitionnement statique peut fournir une accélération significative sur un ordinateur multicœur qui est uniquement doté de quelques cœurs, mais il peut provoquer des ralentissements sur les ordinateurs qui disposent de nombreux cœurs.
[Premières]
Tri parallèle
Le PPL fournit trois algorithmes de tri : concurrency::parallel_sort, concurrency::parallel_buffered_sort, et concurrency::parallel_radixsort. Ces algorithmes de tri sont utiles lorsque vous avez un jeu de données qui peut tirer parti du tri en parallèle. En particulier, trier en parallèle est utile lorsque vous avez un dataset volumineux ou lorsque vous utilisez une opération de comparaison gourmande en ressources informatiques pour trier les données. Chacun de ces éléments de tri d'algorithmes en place.
Les algorithmes parallel_sort et parallel_buffered_sort sont les deux algorithmes basés sur la comparaison. Autrement dit, il compare les éléments par valeur. L'algorithme parallel_sort n'a pas besoin de mémoire supplémentaire, et est approprié pour le tri à caractère général. L'algorithme parallel_buffered_sort peut donner de meilleurs résultats que parallel_sort, mais requiert un espace O(N).
L'algorithme parallel_radixsort est basé sur le code de hachage. Autrement dit, il utilise des clés d'entier pour trier les éléments. En utilisant des clés, l'algorithme peut directement calculer la destination d'un élément au lieu d'utiliser des comparaisons. Comme parallel_buffered_sort, cet algorithme requiert un espace O(N).
Le tableau suivant récapitule les propriétés importantes des trois algorithmes de tri parallèles.
Algorithme |
Description |
Mécanisme de tri |
Stabilité de tri |
Mémoire requise |
Complexité de temps |
Accès d'itérateur |
|---|---|---|---|---|---|---|
parallel_sort |
Tri à caractère général basé sur la comparaison. |
Basé sur la comparaison (croissant) |
Instable |
None |
O((N/P)log(N/P) + 2N((P-1)/P)) |
Aléatoire |
parallel_buffered_sort |
Un tri à caractère général plus rapide basé sur la comparaison qui nécessite un espace O(N). |
Basé sur la comparaison (croissant) |
Instable |
Requiert davantage d'espace O(N) |
O((N/P)log(N)) |
Aléatoire |
parallel_radixsort |
Tri basé sur clé d'entier qui nécessite un espace O(N). |
Basé sur le code de hachage |
Stable |
Requiert davantage d'espace O(N) |
O(N/P) |
Aléatoire |
L'illustration suivante montre plus graphiquement les propriétés importantes des trois algorithmes de tri parallèles.
.png "Comparaison des algorithmes de tri")
Ces algorithmes de tri parallèles respectent les règles de l'annulation et de la gestion des exceptions. Pour plus d'informations sur l'annulation et la gestion des exceptions dans le runtime d'accès concurrentiel, consultez Annuler les algorithmes parallèles et Gestion des exceptions dans le runtime d'accès concurrentiel.
Conseil
Ces algorithmes de tri parallèle s'appuient sur des sémantiques de déplacement.Définissez un opérateur d'assignation de déplacement pour permettre aux opérations de swap de se générer plus efficacement.Pour plus d'informations sur la sémantique de déplacement et l'opérateur d'affectation de déplacement, consultez Déclarateur de référence Rvalue : &&, et le Comment : écrire un constructeur move.Si vous ne fournissez pas de fonction d'opérateur d'assignation de déplacement ou d'échange, les algorithmes de tri utilisent le constructeur de copie.
L'exemple simple suivant montre comment utiliser parallel_sort pour trier vector des valeurs int. Par défaut, parallel_sort utilise std::less pour comparer des valeurs.
// basic-parallel-sort.cpp
// compile with: /EHsc
#include <ppl.h>
#include <random>
#include <iostream>
using namespace concurrency;
using namespace std;
int wmain()
{
// Create and sort a large vector of random values.
vector<int> values(25000000);
generate(begin(values), end(values), mt19937(42));
parallel_sort(begin(values), end(values));
// Print a few values.
wcout << "V(0) = " << values[0] << endl;
wcout << "V(12500000) = " << values[12500000] << endl;
wcout << "V(24999999) = " << values[24999999] << endl;
}
/* Output:
V(0) = -2147483129
V(12500000) = -427327
V(24999999) = 2147483311
*/
Cet exemple montre comment fournir une fonction de comparaison personnalisée. Il utilise la méthode std::complex::real pour trier les valeurs std::complex<double> dans l'ordre croissant.
// For this example, ensure that you add the following #include directive:
// #include <complex>
// Create and sort a large vector of random values.
vector<complex<double>> values(25000000);
generate(begin(values), end(values), mt19937(42));
parallel_sort(begin(values), end(values),
[](const complex<double>& left, const complex<double>& right) {
return left.real() < right.real();
});
// Print a few values.
wcout << "V(0) = " << values[0] << endl;
wcout << "V(12500000) = " << values[12500000] << endl;
wcout << "V(24999999) = " << values[24999999] << endl;
/* Output:
V(0) = (383,0)
V(12500000) = (2.1479e+009,0)
V(24999999) = (4.29497e+009,0)
*/
Cet exemple montre comment fournir une fonction de hachage pour l'algorithme parallel_radixsort. Il trie les points 3D. Les points sont triés en fonction de leur distance à un point de référence.
// parallel-sort-points.cpp
// compile with: /EHsc
#include <ppl.h>
#include <random>
#include <iostream>
using namespace concurrency;
using namespace std;
// Defines a 3-D point.
struct Point
{
int X;
int Y;
int Z;
};
// Computes the Euclidean distance between two points.
size_t euclidean_distance(const Point& p1, const Point& p2)
{
int dx = p1.X - p2.X;
int dy = p1.Y - p2.Y;
int dz = p1.Z - p2.Z;
return static_cast<size_t>(sqrt((dx*dx) + (dy*dy) + (dz*dz)));
}
int wmain()
{
// The central point of reference.
const Point center = { 3, 2, 7 };
// Create a few random Point values.
vector<Point> values(7);
mt19937 random(42);
generate(begin(values), end(values), [&random] {
Point p = { random()%10, random()%10, random()%10 };
return p;
});
// Print the values before sorting them.
wcout << "Before sorting:" << endl;
for_each(begin(values), end(values), [center](const Point& p) {
wcout << L'(' << p.X << L"," << p.Y << L"," << p.Z
<< L") D = " << euclidean_distance(p, center) << endl;
});
wcout << endl;
// Sort the values based on their distances from the reference point.
parallel_radixsort(begin(values), end(values),
[center](const Point& p) -> size_t {
return euclidean_distance(p, center);
});
// Print the values after sorting them.
wcout << "After sorting:" << endl;
for_each(begin(values), end(values), [center](const Point& p) {
wcout << L'(' << p.X << L"," << p.Y << L"," << p.Z
<< L") D = " << euclidean_distance(p, center) << endl;
});
wcout << endl;
}
/* Output:
Before sorting:
(2,7,6) D = 5
(4,6,5) D = 4
(0,4,0) D = 7
(3,8,4) D = 6
(0,4,1) D = 7
(2,5,5) D = 3
(7,6,9) D = 6
After sorting:
(2,5,5) D = 3
(4,6,5) D = 4
(2,7,6) D = 5
(3,8,4) D = 6
(7,6,9) D = 6
(0,4,0) D = 7
(0,4,1) D = 7
*/
À titre d'illustration, cet exemple utilise un jeu de données relativement petit. Augmentez la taille initiale du vecteur pour tester les améliorations des performances sur de plus grands jeux de données.
Cet exemple utilise une expression lambda comme une fonction de hachage. Utilisez également l'une des implémentations intégrées de la classe std::hash ou définissez votre propre spécialisation. Utilisez également un objet personnalisé de fonction de hachage, comme illustré dans l'exemple suivant :
// Functor class for computing the distance between points.
class hash_distance
{
public:
hash_distance(const Point& reference)
: m_reference(reference)
{
}
size_t operator()(const Point& pt) const {
return euclidean_distance(pt, m_reference);
}
private:
Point m_reference;
};
// Use hash_distance to compute the distance between points.
parallel_radixsort(begin(values), end(values), hash_distance(center));
La fonction de hachage doit retourner un type intégral (std::is_integral::value doit être true). Ce type de doit être converti en type size_t.
Choisir un algorithme de tri
Dans de nombreux cas, parallel_sort fournit le meilleur compromis entre la vitesse et la performance de la mémoire. Toutefois, lorsque vous augmentez la taille de votre jeu de données, le nombre de processeurs disponibles, ou la complexité de votre fonction de comparaison, parallel_buffered_sort ou parallel_radixsort peut donner de meilleurs résultats. La meilleure méthode pour déterminer quel algorithme de tri utiliser dans tout scénario donné consiste à expérimenter et à mesurer le temps que prennent le tri de données caractéristiques avec des configurations d'ordinateurs représentatives. Gardez en tête les principes suivants lorsque vous choisissez une stratégie de tri.
La taille de votre jeu de données. Dans ce document, un petit dataset contient moins de 1.000 éléments, un dataset intermédiaire contient entre 10.000 et 100.000 éléments, et un dataset volumineux contient plus de 100.000 éléments.
La quantité de travail que votre fonction de comparaison ou votre fonction de hachage exécute.
La quantité de ressources informatiques disponibles.
Les caractéristiques de votre jeu de données. Par exemple, un algorithme peut bien se comporter pour les données déjà presque triées, mais pas pour des données complètement non triées.
La taille de segment. L'argument facultatif de _Chunk_size spécifie quand l'algorithmes passe d'une implémentation de tri en parallèle à une en série tel qu'il subdivise le tri global en plus petites unités de travail. Par exemple, si vous spécifiez 512, l'algorithme passe à l'implémentation série lorsqu'une unité de travail contient 512 ou moins d'éléments. Une implémentation série peut améliorer les performances globales car elle élimine la surcharge requise pour le traitement des données en parallèle.
Il peut ne pas être intéressant de trier un petit dataset en parallèle, même quand vous avez un grand nombre de ressources informatiques disponible ou que votre fonction de comparaison ou fonction de hachage effectue relativement une grande quantité de travail. Utilisez la fonction std::sort pour trier des petits jeu de données. (parallel_sort et parallel_buffered_sort appellent sort lorsque vous spécifiez une taille de segment qui est plus grande que le jeu de données; toutefois, parallel_buffered_sort doit allouer un espace O(N), qui peut prendre du temps supplémentaire en raison d'un conflit de verrouillage ou de l'allocation de mémoire.)
Si vous devez conserver la mémoire ou que l'allocateur de mémoire est sujet à un conflit de verrouillage, utilisez parallel_sort pour trier un dataset moyen. parallel_sort ne requiert pas d'espace supplémentaire; les autres algorithmes nécessitent un espace O(N).
Utilisez parallel_buffered_sort pour trier les jeux de données moyens et lorsque votre application correspond à un espace nécessaire supplémentaire O(N). parallel_buffered_sort est particulièrement utile lorsque vous avez un grand nombre de ressources informatiques ou un coût de comparer la fonction ou la fonction de hachage.
Utilisez parallel_radixsort pour trier des datasets et lorsque votre application correspond à l'espace nécessaire supplémentaire O(N). parallel_radixsort est particulièrement utile lorsque l'opération de comparaison équivalente est plus coûteuse ou lorsque les deux opérations sont coûteuses.
Avertissement
Implémenter une bonne fonction de hachage requiert que vous connaissiez la plage de dataset et la façon dont chaque élément du dataset est transformé en une valeur non signée correspondante.Étant donné que l'opération de hachage fonctionne sur les valeurs non signées, considérez une stratégie différente de tri si des valeurs de hachage non signées ne peuvent pas être produites.
L'exemple suivant compare les performances de sort, de parallel_sort, de parallel_buffered_sort, et de parallel_radixsort sur le même grand jeu de données arbitraires.
// choosing-parallel-sort.cpp
// compile with: /EHsc
#include <ppl.h>
#include <random>
#include <iostream>
#include <windows.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 size_t DATASET_SIZE = 10000000;
// Create
// Creates the dataset for this example. Each call
// produces the same predefined sequence of random data.
vector<size_t> GetData()
{
vector<size_t> data(DATASET_SIZE);
generate(begin(data), end(data), mt19937(42));
return data;
}
int wmain()
{
// Use std::sort to sort the data.
auto data = GetData();
wcout << L"Testing std::sort...";
auto elapsed = time_call([&data] { sort(begin(data), end(data)); });
wcout << L" took " << elapsed << L" ms." <<endl;
// Use concurrency::parallel_sort to sort the data.
data = GetData();
wcout << L"Testing concurrency::parallel_sort...";
elapsed = time_call([&data] { parallel_sort(begin(data), end(data)); });
wcout << L" took " << elapsed << L" ms." <<endl;
// Use concurrency::parallel_buffered_sort to sort the data.
data = GetData();
wcout << L"Testing concurrency::parallel_buffered_sort...";
elapsed = time_call([&data] { parallel_buffered_sort(begin(data), end(data)); });
wcout << L" took " << elapsed << L" ms." <<endl;
// Use concurrency::parallel_radixsort to sort the data.
data = GetData();
wcout << L"Testing concurrency::parallel_radixsort...";
elapsed = time_call([&data] { parallel_radixsort(begin(data), end(data)); });
wcout << L" took " << elapsed << L" ms." <<endl;
}
/* Sample output (on a computer that has four cores):
Testing std::sort... took 2906 ms.
Testing concurrency::parallel_sort... took 2234 ms.
Testing concurrency::parallel_buffered_sort... took 1782 ms.
Testing concurrency::parallel_radixsort... took 907 ms.
*/
Dans cet exemple, qui suppose qu'il est possible d'allouer un espace O(N) lors du tri, parallel_radixsort offre les meilleures performances sur ce dataset sur la configuration de cet ordinateur.
[Premières]
Rubriques connexes
Titre |
Description |
|---|---|
Indique comment utiliser l'algorithme parallel_for pour effectuer une multiplication matricielle. |
|
Indique comment utiliser l'algorithme parallel_for_each pour calculer la quantité de nombres premiers dans un objet std::array en parallèle. |
|
Comment : utiliser parallel_invoke pour écrire une routine de tri parallèle |
Indique comment utiliser l'algorithme parallel_invoke pour améliorer les performances de l'algorithme de tri bitonique. |
Comment : utiliser parallel_invoke pour exécuter des opérations parallèles |
Indique comment utiliser l'algorithme parallel_invoke pour améliorer les performances d'un programme qui effectue plusieurs opérations sur une source de données partagée. |
Comment : exécuter des opérations de mappage et de réduction en parallèle |
Indique comment utiliser les algorithmes parallel_transform et parallel_reduce pour effectuer une carte et réduire l'opération qui compte les occurrences des mots dans les fichiers. |
Décrit la bibliothèque PPL, qui fournit un modèle de programmation impérative qui encourage l'extensibilité et la facilité d'utilisation pour le développement d'applications simultanées. |
|
Explique le rôle de l'annulation dans la bibliothèque PPL, comment annuler un travail parallèle et comment déterminer quand un groupe de tâches est annulé. |
|
Gestion des exceptions dans le runtime d'accès concurrentiel |
Explique le rôle de la gestion des exceptions dans le runtime d'accès concurrentiel. |