Algorithmes parallèles

Article
03/04/2013

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 d' concurrency::parallel_for utilise un objet d' concurrency::structured_task_group pour exécuter les itérations de boucle parallèle.L'algorithme parallel_for partitionne le travail de façon optimale en fonction de la quantité de ressources de calcul disponible.

Sections

L'algorithme parallel_for
L'algorithme parallel_for_each
L'algorithme parallel_invoke
Les algorithmes de parallel_transform et de parallel_reduce
- L'algorithme de parallel_transform
- L'algorithme de parallel_reduce
- Exemple : Exécuter le mappage et réduisent en parallèle
Partitionner le travail
Tri parallèle
- Choisir un algorithme de tri

L'algorithme parallel_for

L'algorithme d' concurrency::parallel_for exécute à 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 une plage volant pour équilibrer ces partitions lorsque les charges de travail sont pas correctement apparié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 d' 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 acceptent les objets de partitionneur, qui vous permettent de spécifier comment parallel_for doit partitionner des intervalles entre les threads.Les partitionneurs sont présentés en détail dans la section Partitionner le travail dans 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_forparallel_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.

[!REMARQUE]

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 réduire la charge mémoire à l'aide d'un partitionneur dans votre boucle parallèle.Pour plus d'informations, consultez l' 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.

[Supérieur]

L'algorithme parallel_for_each

L'algorithme d' concurrency::parallel_for_each effectue des tâches sur un conteneur itératif, tels que 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), begin(values), [](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_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.

[Supérieur]

L'algorithme parallel_invoke

L'algorithme d' 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 produit 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.

[Supérieur]

Les algorithmes de parallel_transform et de parallel_reduce

Les algorithmes de concurrency::parallel_transform et d' concurrency::parallel_reduce sont des versions parallèles de algorithmes std::transform et std::accumulateSTL, respectivement.Les versions du runtime d'accès concurrentiel se comportent comme les versions STL sauf que l'ordre d'exécution n'est pas déterminé car ils sont exécutés en parallèle.Utilisez ces algorithmes lorsque vous travaillez avec un jeu qui est assez grand pour obtenir des avantages de performance et l'extensibilité d'être traité en parallèle.

Important

Les algorithmes de parallel_transform et d' parallel_reduce prennent uniquement en charge d'accès aléatoire, bidirectionnel, puis effectuez le suivi des itérateurs car ces itérateurs produisent les adresses mémoire stable.En outre, ces itérateurs doivent produire l-value qu'non d'const .

L'algorithme de parallel_transform

Vous pouvez utiliser l'algorithme d' parallel transform pour exécuter de nombreuses opérations de parallélisation de données.Par exemple, vous pouvez :

Ajustez la luminosité d'une image, et exécuter d'autres opérations de traitement d'images.
Ajoutez ou prenez le produit scalaire de deux vecteurs, et effectuez d'autres calculs numériques sur des vecteurs.
Exécutez le lancement de rayon 3D, où chaque itération fait référence à un pixel à afficher.

L'exemple suivant illustre la structure de base qui est utilisée pour appeler l'algorithme d' parallel_transform .Cet exemple réalise négative chaque élément d'un objet d' std::vector de deux façons.La première méthode utilise une expression lambda.La deuxième méthode utilise std::negate, qui dérive d' 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>());
}

Attention
Cet exemple illustre l'utilisation de base d' parallel_transform.Étant donné que la fonction de travail n'effectue pas une quantité de travail, une augmentation considérable de performances n'est pas destinée dans cet exemple.

L'algorithme d' parallel_transform deux surcharges.La première surcharge prend un intervalle d'entrée et une fonction unaire.La fonction unaire peut être une expression lambda qui prend un argument, un objet de fonction, ou un type qui dérive d' 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 prend deux arguments, un objet de fonction, ou un type qui dérive d' std::binary_function.L'exemple 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 fournissez pour la sortie d' parallel_transform doit complètement chevaucher l'itérateur d'entrée ou ne pas se chevaucher du tout.Le comportement de cet algorithme est pas spécifié si les itérateurs d'entrée et de sortie chevauchent partielle.

L'algorithme de parallel_reduce

L'algorithme d' parallel_reduce est utile lorsque vous avez une séquence d'opérations qui satisfont la propriété associative.(Cet algorithme ne requiert pas la propriété commutative.) Voici quelques-unes des opérations que vous pouvez exécuter avec parallel_reduce:

Multipliez les séquences de tableaux pour produire un tableau.
Multipliez un vecteur par une séquence de tableaux pour produire un vecteur.
Calculez la longueur d'une séquence de chaînes.
Combinez une liste d'éléments, tels que les chaînes, dans un élément.

L'exemple de base suivant montre comment utiliser l'algorithme d' parallel_reduce pour associer une séquence de chaînes dans une chaîne.Comme avec les exemples de parallel_transform, les gains de performance ne sont pas prévus dans cet 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 sténographie pour l'utilisation de l'algorithme d' parallel_for_each avec la classe d' concurrency::combinable .

Exemple : Exécuter le mappage et réduisent en parallèle

Une opération de mappage applique une fonction à chaque valeur d'une séquence.Une opération de réduire combine les éléments d'une séquence en une valeur.Vous pouvez utiliser les classes de (STL) std::transform std::accumulate de modèles Standard pour exécuter le mappage et réduire des opérations.Toutefois, pour de nombreux problèmes, vous pouvez utiliser l'algorithme d' parallel_transform pour exécuter l'opération de mappage en parallèle et l'algorithme d' parallel_reduce exécutent l'opération de réduire en parallèle.

L'exemple suivant compare le temps nécessaire pour calculer la somme des nombres premiers séquentielle et en parallèle.Les valeurs de deuxième tableau de transformations de phase de carte à 0 et la phase de réduire ajoute 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 exécute une carte et réduit l'exécution en parallèle, consultez Comment : exécuter des opérations de mappage et de réduction en parallèle.

[Supérieur]

Partitionner le travail

Pour paralléliser une opération sur une source de données, une étape essentielle est de partitionner la source en plusieurs sections qui peuvent être accessibles simultanément par plusieurs threads.Un partitionneur spécifie comment un algorithme parallèle doit partitionner des intervalles entre les threads.Comme expliqué précédemment dans ce document, la bibliothèque PPL utilise un mécanisme par défaut de partitionnement qui crée une première charge de travail puis utilise un algorithme de vol de travail et une plage volant pour équilibrer ces partitions lorsque les charges de travail sont pas correctement appariées.Par exemple, lorsqu'une itération de boucle se termine une plage d'itérations, le runtime redistribue le travail d'autres threads de ce thread.Toutefois, pour certains cas, vous pouvez spécifier un mécanisme différent de partitionnement qui est mieux adapté à votre problème.

parallel_for, parallel_for_each, et les algorithmes de parallel_transform fournissent des versions surchargées qui acceptent un paramètre supplémentaire, _Partitioner.Ce paramètre définit le type de partitionneur qui divise le travail.Voici les types de partitionneurs que la bibliothèque PPL définit :

concurrency::affinity_partitioner
Travail de divise en un nombre fixe d'intervalles (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 sorte qu'il mappe les plages aux threads de travail.Ce type de partitionneur peut améliorer les performances lorsqu'une boucle est exécutée sur le même groupe de données plusieurs fois (comme une boucle dans une boucle) et les mieux de données dans le cache.Ce partitionneur ne participe pas complètement à l'annulation.Il n'utilise pas la sémantique de blocage coopérative et ne peut donc pas être utilisé avec les boucles parallèles qui ont une dépendance en avant.
concurrency::auto_partitioner
Divise s'exécutent dans un premier nombre d'intervalles (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ée qui accepte un paramètre d' _Partitioner .Chaque intervalle peut être divisé en Sub- intervalles, et permet ainsi à l'équilibrage de charge de se produire.Lorsqu'un intervalle de travail se termine, le runtime redistribue des Sub- intervalles de travail d'autres threads de ce thread.Utilisez ce partitionneur si votre charge de travail ne se situe pas sous l'une des autres catégories ou vous avez besoin de la prise en charge complète pour l'annulation ou le blocage coopératif.
concurrency::simple_partitioner
Divise s'exécutent dans des plages de sorte que chaque plage a au moins le nombre d'itérations spécifiées par la taille du segment donnée.Ce type de partitionneur participe à l'équilibrage de charge ; toutefois, le runtime ne divise pas les intervalles en Sub- plages.Pour chaque ouvrier, le runtime vérifie l'annulation et exécute équilibrer la charge de après les itérations de _Chunk_size complètes.
concurrency::static_partitioner
Travail de divise en un nombre fixe d'intervalles (généralement le nombre de threads de travail disponibles pour travailler sur la boucle).Ce type de partitionneur peut améliorer les performances parce qu'il n'utilise pas le vol et est par conséquent moins de charge mémoire.Utilisez ce type de partitionneur lorsque chaque itération d'une boucle parallèle effectue une quantité fixe et uniforme de travail et vous n'avez pas besoin de la prise en charge de l'annulation ou ne faites pas suivre le blocage coopératif.

Attention
Les algorithmes de parallel_for_each et d' parallel_transform prennent uniquement en charge des conteneurs qui utilisent des itérateurs d'accès aléatoire (par exemple std::vector) pour le type statique, simple, et les partitionneurs d'affinité.L'utilisation des conteneurs qui utilisent des itérateurs bidirectionnelles et en arrière produit une erreur de compilation.Le partitionneur par défaut, auto_partitioner, prend en charge les trois de ces types d'itérateur.

Les algorithmes de parallel_for_each et d' parallel_transform prennent uniquement en charge des conteneurs qui utilisent des itérateurs d'accès aléatoire (par exemple std::vector) pour le type statique, simple, et les partitionneurs d'affinité.L'utilisation des conteneurs qui utilisent des itérateurs bidirectionnelles et en arrière produit une erreur de compilation.Le partitionneur par défaut, auto_partitioner, prend en charge les trois de ces types d'itérateur.

En général, ces partitionneurs sont utilisés de la même manière, à l'exception affinity_partitioner.La plupart des types de partitionneur ne conservent pas l'état et ne sont pas modifiés par le runtime.Par conséquent vous pouvez créer ces objets de partitionneur au site d'appel, comme indiqué dans 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 passer un objet d' affinity_partitioner commeconstnon, référence lvalue afin que l'algorithme peut stocker l'état pour les futures les boucles réutilisent.L'exemple suivant montre une application de base qui exécute la même opération sur un groupe de données en parallèle plusieurs fois.L'utilisation d' affinity_partitioner peut améliorer les performances parce que le tableau est susceptible de tenir dans le cache.

// affinity-partitioner.cpp
// compile with: /EHsc
#include <ppl.h>
#include <array>

using namespace concurrency;

int wmain()
{    
    // Create an arry 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);
    }
}

Attention
Être prudent lorsque vous modifiez le code existant qui repose sur la sémantique de blocage coopérative pour utiliser static_partitioner ou affinity_partitioner.Ces types de partitionneur n'utilisent pas l'équilibrage de charge ou ne s'étendent pas volant, et peuvent donc modifier le comportement de votre application.

La meilleure méthode pour déterminer si utiliser un partitionneur dans tout scénario donné consiste à tester et de mesurer la durée pendant laquelle elle accepte des opérations pour s'exécuter sous charge et les paramètres de l'ordinateur 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.

[Supérieur]

Tri parallèle

La bibliothèque 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 groupe de données qui peut tirer parti d'être triées en parallèle.En particulier, trier en parallèle est utile lorsque vous avez un grand groupe de données ou lorsque vous utilisez un gourmand en ressources informatiques comparez l'exécution pour trier les données.Chacun de ces éléments de tris d'algorithmes en place.

Les algorithmes de parallel_sort et d' parallel_buffered_sort sont les deux algorithmes comparer- basés sur.Autrement dit, elles comparent les éléments par valeur.L'algorithme d' parallel_sort n'avez pas besoin en mémoire supplémentaire, et convient pour le tri à caractère général.L'algorithme d' parallel_buffered_sort peut offrir de meilleures performances qu' parallel_sort, mais il requiert l'espace d' O(N) .

L'algorithme d' parallel_radixsort information-est basé.Autrement dit, il utilise les clés entières pour trier les éléments.En utilisant des clés, cet algorithme peut directement calculer la destination d'un élément au lieu d'utiliser des comparaisons.Comme parallel_buffered_sort, cet algorithme requiert l'espace d' O(N) .

Le tableau suivant résume les propriétés importantes des trois algorithmes de tri parallèle.

Algorithme	Description	Mécanisme de tri	Stabilité de tri	Les besoins en mémoire	Complexité du temps	Accès aux itérateurs
parallel_sort	Tri comparer-basé à caractère général.	Comparer- sur (quantité)	Instable	Aucun	O((N/P)log(N/P) + 2N((P-1)/P))	Aléatoire
parallel_buffered_sort	Un tri comparer- basé à caractère général plus rapide qui requiert O (N) l'espace.	Comparer- sur (quantité)	Instable	Requiert l'espace supplémentaire d' O(N)	O((N/P)log(N))	Aléatoire
parallel_radixsort	Tri de clé basé sur entier qui requiert O (N) l'espace.	Information-basé	Stable	Requiert l'espace supplémentaire d' O(N)	O(N/P)	Aléatoire

L'illustration suivante montre les propriétés importantes des trois algorithmes de tri parallèle plus graphique.

Comparaison des algorithmes de tri

Ces algorithmes de tri parallèle suivent les règles de l'annulation et la gestion des exceptions.Pour plus d'informations sur l'annulation et la gestion des exceptions dans le runtime d'accès concurrentiel, consultez Annulation d'algorithmes parallèles et l' Gestion des exceptions dans le runtime d'accès concurrentiel.

Conseil
Sémantique parallèle de mouvements en charge de ces algorithmes de tri.Vous pouvez définir un opérateur d'assignation de déplacement pour permettre aux opérations de swap de se produire plus efficacement.Pour plus d'informations sur la sémantique de déplacement et l'opérateur d'assignation de déplacement, consultez Déclarateur de référence Rvalue : &&, et le Comment : Entrez un constructeur de mouvements.Si vous ne fournissez pas une fonction d'opérateur d'assignation ou d'échange de déplacement, les algorithmes de tri utilisent le constructeur de copie.

Sémantique parallèle de mouvements en charge de ces algorithmes de tri.Vous pouvez définir un opérateur d'assignation de déplacement pour permettre aux opérations de swap de se produire plus efficacement.Pour plus d'informations sur la sémantique de déplacement et l'opérateur d'assignation de déplacement, consultez Déclarateur de référence Rvalue : &&, et le Comment : Entrez un constructeur de mouvements.Si vous ne fournissez pas une fonction d'opérateur d'assignation ou d'échange de déplacement, les algorithmes de tri utilisent le constructeur de copie.

L'exemple de base suivant montre comment utiliser parallel_sort pour trier vector des valeurs d' 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 indique comment fournir un personnalisé comparent la fonction.Il utilise la méthode de std::complex::real pour trier les valeurs d' 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 indique comment fournir une fonction de hachage à l'algorithme d' parallel_radixsort .Cet exemple trie les points 3D.Les points sont triés selon leur distance du 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 de illustration, cet exemple utilise un groupe de données relativement petit.Vous pouvez augmenter la taille du vecteur pour essayer d'amélioration des performances sur les grands groupes de données.

Cet exemple utilise une expression lambda comme fonction de hachage.Vous pouvez également utiliser l'une des implémentations intégrées de la classe d' std::hash ou définir votre propre spécialisation.Vous pouvez également utiliser un objet personnalisé de fonction de hachage, comme illustré dans cet exemple :

// 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 intégral doit être convertible en type size_t.

Choisir un algorithme de tri

Dans de nombreux cas, parallel_sort fournit le meilleur équilibre de la vitesse et la performance de la mémoire.Toutefois, à mesure que vous augmentez la taille du groupe de données, le nombre de processeurs disponibles, ou de la complexité du votre comparez la fonction, l' parallel_buffered_sort ou l' parallel_radixsort peut offrir de meilleures performances.La meilleure façon de déterminer l'algorithme de tri à utiliser dans tout scénario donné consiste à tester et pour mesurer la durée il le faut pour trier les données classiques sous les paramètres de l'ordinateur représentatives.Conservez les indications suivantes à l'esprit lorsque vous choisissez une stratégie de tri.

La taille de votre groupe de données.Dans ce document, un petit groupe de données contient moins de 1.000 éléments, un groupe de données méthode contient entre 10.000 et 100.000 éléments, et un grand groupe de données contient plus de 100.000 éléments.
La quantité de travail que votre comparez la fonction ou la fonction de hachage exécute.
La quantité de ressources de calcul disponibles.
Les caractéristiques de votre groupe de données.Par exemple, un algorithme peut se comporter bien pour les données qui sont déjà presque triées, mais pas pour les données qui sont complètement non triées.
La taille du segment.L'argument facultatif d' _Chunk_size spécifie si les opérations d'algorithme d'un parallèle à une implémentation séquentielle de tri à mesure qu'il subdivise le tri global en plus petites unités de travail.Par exemple, si vous fournissez 512, les commutateurs d'algorithme à l'implémentation séquentiel lorsqu'une unité de travail contient 512 ou sauf éléments.Une implémentation séquentielle peut améliorer les performances globales parce qu'il élimine la charge mémoire requise pour gérer des données en parallèle.

Il ne peut pas être intéressant de trier un petit groupe de données en parallèle, même si vous avez un grand nombre de ressources de calcul disponibles ou votre comparer la fonction ou la fonction de hachage exécute relativement un grand nombre de travail.Vous pouvez utiliser la fonction d' std::sort pour trier de petits groupes de données.(parallel_sort et parallel_buffered_sort appellent sort lorsque vous spécifiez une taille du segment qui est plus grande que le groupe de données ; toutefois, parallel_buffered_sort doit allouer de l'espace d' O(N), qui peut prendre du temps supplémentaire en raison de conflits de verrouillage ou de l'allocation de mémoire.)

Si vous devez économiser de la mémoire ou l'allocateur de mémoire est soumis au conflit de verrouillage, utilisez parallel_sort pour trier un groupe de données central.parallel_sort ne requiert pas d'espace supplémentaire ; les autres algorithmes requièrent l'espace d' O(N) .

Utilisez parallel_buffered_sort pour trier des groupes de données moyen et lorsque votre application répond à l'espace requis supplémentaire d' O(N) .parallel_buffered_sort peut être particulièrement utile lorsque vous avez un grand nombre de ressources de calcul ou un coûteux de comparer la fonction ou la fonction de hachage.

Utilisez parallel_radixsort pour trier de grands groupes de données et lorsque votre application répond à l'espace requis supplémentaire d' O(N) .parallel_radixsort peut être particulièrement utile lorsque l'équivalent comparent l'exécution est plus coûteuses ou lorsque les deux opérations sont coûteuses.

Attention
Implémenter une bonne fonction de hachage requiert que vous connaissez l'intervalle de groupe de données et comment chaque élément dans le groupe de données est transformé en une valeur non signée correspondante.Étant donné que l'exécution de hachage travaille sur des valeurs non signés, considérez une stratégie différente de tri si les valeurs de hachage non signés ne peuvent pas être rencontrées.

Implémenter une bonne fonction de hachage requiert que vous connaissez l'intervalle de groupe de données et comment chaque élément dans le groupe de données est transformé en une valeur non signée correspondante.Étant donné que l'exécution de hachage travaille sur des valeurs non signés, considérez une stratégie différente de tri si les valeurs de hachage non signés ne peuvent pas être rencontrées.

L'exemple suivant compare les performances d' sort, d' parallel_sort, d' parallel_buffered_sort, et d' parallel_radixsort sur le même grand groupe de données aléatoires.

// 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 acceptable d'allouer de l'espace d' O(N) pendant le tri, parallel_radixsort exécute le mieux dans ce groupe de données sur cette configuration de l'ordinateur.

[Supérieur]

Rubriques connexes

Titre	Description
Comment : écrire une boucle parallel_for	Indique comment utiliser l'algorithme parallel_for pour effectuer une multiplication matricielle.
Comment : écrire une boucle parallel_for_each	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	Montre comment utiliser les algorithmes de parallel_transform et d' parallel_reduce pour effectuer une carte et réduire l'exécution qui compte les occurrences des mots dans les fichiers.
Bibliothèque de modèles parallèles	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.
Annulation dans la bibliothèque de modèles parallèles	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.