Algorithmes parallèles

La bibliothèque de modèles parallèles (PPL) fournit des algorithmes qui effectuent simultanément des travaux sur des collections de données. Ces algorithmes ressemblent à ceux fournis par la bibliothèque standard C++.

Les algorithmes parallèles se composent de fonctionnalités existantes dans le 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. Les partitions d’algorithmes parallel_for fonctionnent de manière optimale selon le nombre disponible de ressources de calcul.

Rubriques

• 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

  • Choix d’un algorithme de tri

Algorithme parallel_for

L’algorithme concurrency::parallel_for effectue la même tâche en parallèle à plusieurs reprises. Chacune de ces tâches est paramétrée par une valeur d’itération. Cet algorithme est utile lorsque vous disposez d’un corps de la boucle qui ne partage pas les ressources entre les itérations de cette dernière.

L’algorithme parallel_for partitionne les tâches de manière optimale pour l’exécution parallèle. Il utilise un algorithme de vol de travail et un vol de plage pour équilibrer ces partitions lorsque les charges de travail sont déséquilibrés. Lorsqu’une itération de boucle se bloque de manière coopérative, le runtime redistribue la plage d’itérations attribuée au thread actuel à d’autres threads ou à d'autres processeurs. De même, lorsqu’un thread termine une plage d’itérations, le runtime redistribue le travail d’autres threads vers 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 les ressources de traitement entre les corps de boucles de manière efficace pour l’exécution parallèle.

L’algorithme parallel_for présente 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 de fonction). La deuxième version prend une valeur de départ, une valeur de fin, une valeur par laquelle progresser et une fonction de travail. La première version de cette fonction utilise 1 comme valeur d’étape. Les versions restantes prennent des objets partitionneurs, ce qui vous permet de spécifier la façon dont parallel_for doit partitionner les plages entre les threads. Les partitionneurs sont expliqués plus en détail dans la section Partitionnement du travail dans ce document.

Vous pouvez convertir beaucoup de bouches for pour utiliser parallel_for. Toutefois, l’algorithme parallel_for diffère de l’instruction for de plusieurs façons :

• L’algorithme parallel_for parallel_for n’exécute pas les tâches dans un ordre prédéfinit.

• 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 une valeur inférieure à last.

• Le paramètre de type _Index_type doit être un type intégral. Ce type intégral peut être signé ou non signé.

• L’itération de boucle doit être transférée. 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 d’une boucle for. Si plusieurs exceptions se produisent simultanément dans un corps de boucle parallèle, le runtime ne propage qu’une seule des exceptions au thread qui a appelé parallel_for. En outre, lorsqu’une itération de boucle lève une exception, le runtime n’arrête pas immédiatement l'ensemble de la boucle. Au lieu de cela, la boucle est placée dans l’état Annulé et le runtime ignore toutes les tâches qui n’ont pas encore démarré. Pour en savoir plus sur la gestion des exceptions et les algorithmes parallèles, consultez Gestion des exceptions.

Bien que l’algorithme parallel_for ne prend 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 PPL.

Exemple

L’exemple suivant montre la structure de base de l’algorithme parallel_for. Cet exemple affiche dans 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 produit l'exemple de sortie suivant :

1 2 4 3 5

Étant donné que l’algorithme parallel_for agit sur chaque élément en parallèle, l’ordre dans lequel les valeurs sont affichées dans la console varie.

Pour obtenir un exemple complet de l'utilisation de l’algorithme parallel_for, consultez Procédure : Écrire une boucle parallel_for.

[Haut]

Algorithme parallel_for_each

L’algorithme concurrency::parallel_for_each effectue des tâches sur un conteneur itératif, tel que ceux fournis par la bibliothèque standard C++, en parallèle. Il utilise la même logique de partitionnement que celle utilisée par l’algorithme parallel_for.

L’algorithme parallel_for_each ressemble à l’algorithme std::for_each de la bibliothèque standard C++, sauf 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 à la fois sur les itérateurs vers l'avant et les itérateurs à accès aléatoire, il fonctionne mieux avec ces derniers.

Exemple

L’exemple suivant montre la structure de base de l’algorithme parallel_for_each. Cet exemple affiche dans la console chaque valeur d’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 produit l'exemple de sortie suivant :

4 5 1 2 3

Étant donné que l’algorithme parallel_for_each agit sur chaque élément en parallèle, l’ordre dans lequel les valeurs sont affichées dans la console varie.

Pour obtenir un exemple complet de l'utilisation de l’algorithme parallel_for_each, consultez Procédure : Écrire une boucle parallel_for_each.

[Haut]

Algorithme parallel_invoke

L’algorithme concurrency::parallel_invoke exécute un ensemble de tâches en parallèle. Il ne retourne pas tant que chaque tâche n’est pas terminée. Cet algorithme est utile lorsque vous avez plusieurs tâches indépendantes que vous souhaitez exécuter en même temps.

L’algorithme parallel_invoke prend comme paramètres une série de fonctions de travail (fonctions lambda, objets de fonction ou pointeurs de fonction). L’algorithme parallel_invoke est surchargé pour prendre entre deux et dix paramètres. Chaque fonction que vous transférez à parallel_invoke doit prendre zéro paramètre.

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 explique comment l’algorithme parallel_invoke se rapporte aux tâches et aux groupes de tâches.

Exemple

L’exemple suivant montre 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 :

108 11.2 HelloHello

Pour des exemples complets de l’utilisation de l’algorithme parallel_invoke, consultez Procédure : Utiliser parallel_invoke pour écrire une routine de tri parallèle et Procédure : Utiliser parallel_invoke pour exécuter des opérations parallèles.

[Haut]

Algorithmes parallel_transform et parallel_reduce

Les algorithmes concurrency::parallel_transform et concurrency::parallel_reduce sont des versions parallèles des algorithmes std::transform et std::accumulate de la bibliothèque standard C++, respectivement. Les versions du runtime d’accès concurrentiel se comportent comme les versions de la bibliothèque standard C++, sauf que l’ordre d’opération n’est pas déterminé, car ils s’exécutent en parallèle. Utilisez ces algorithmes lorsque vous travaillez avec un ensemble suffisamment grand pour que le traitement en parallèle présente des avantages en termes de performances et d'extensibilité.

Algorithme parallel_transform

Vous pouvez utiliser l’algorithme parallel transform pour effectuer de nombreuses opérations de parallélisation des données. Par exemple, vous pouvez :

• Ajustez la luminosité d’une image et effectuez d’autres opérations de traitement d’images.

• Additionner ou faire le produit scalaire entre deux vecteurs, et effectuer d'autres calculs numériques sur des vecteurs

• Effectuez un traçage de rayon 3D, où chaque itération fait référence à un pixel qui doit être rendu.

L’exemple suivant montre la structure de base utilisée pour appeler l’algorithme parallel_transform. Cet exemple annule chaque élément d’un objet std ::vector de deux façons. La première utilise une expression lambda. La deuxième 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>());
}

L’algorithme parallel_transform a deux surcharges. La première surcharge prend une plage d’entrée et une fonction unaire. La fonction unaire peut être une expression lambda qui accepte un argument, un objet de 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 fonction ou un type qui dérive de 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>());

Algorithme parallel_reduce

L’algorithme parallel_reduce est utile lorsque vous disposez d’une séquence d’opérations qui satisfont la propriété associative. (Cet algorithme ne nécessite pas la propriété commutative.) Voici quelques-unes des opérations que vous pouvez effectuer avec parallel_reduce :

• Multipliez les séquences de matrices pour produire une matrice.

• Multipliez un vecteur par une séquence de matrices pour produire un vecteur.

• Calculez la longueur d’une séquence de chaînes.

• Combinez une liste d’éléments, tels que des chaînes, en un seul.

L’exemple de base suivant montre comment utiliser l’algorithme parallel_reduce pour combiner une séquence de chaînes en une seule. Comme avec les exemples pour parallel_transform, il ne faut pas s'attendre à des gains de performances 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{
      L"Lorem ",
      L"ipsum ",
      L"dolor ",
      L"sit ",
      L"amet, ",
      L"consectetur ",
      L"adipiscing ",
      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 raccourci 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 applique une fonction à chaque valeur d’une séquence. Une opération de réduction combine les éléments d’une séquence en une seule valeur. Vous pouvez utiliser les fonctions de la bibliothèque standard C++ std::transform et std::accumulate pour effectuer des opérations de mappage et de réduction. Toutefois, en réponse à de nombreux problèmes, vous pouvez utiliser l'algorithme parallel_transform pour effectuer l'opération de mappage en parallèle et l'algorithme parallel_reduce pour effectuer l'opération de réduction en parallèle.

L’exemple suivant compare le temps nécessaire pour calculer la somme des nombres premiers en série et en parallèle. La phase de mappage transforme les valeurs qui ne sont pas des nombres premiers en 0 et la phase de réduction 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 une opération de mappage et de réduction en parallèle, consultez Procédure : Effectuer des opérations de mappage et de réduction en parallèle.

[Haut]

Partitionnement du travail

Pour paralléliser une opération sur une source de données, l’une des étapes essentielles consiste à partitionner la source en plusieurs sections accessibles simultanément par plusieurs threads. Un partitionneur spécifie la façon dont un algorithme parallèle doit partitionner des plages entre threads. Comme nous l'avons vu précédemment, la PPL utilise un mécanisme de partitionnement par défaut qui crée une charge de travail initiale, puis utilise un algorithme de vol de travail et un vol de plage pour équilibrer ces partitions lorsque les charges de travail sont déséquilibrées. Par exemple, lorsqu’une itération de boucle termine une plage d’itérations, le runtime redistribue le travail d’autres threads vers ce thread. Toutefois, pour certains scénarios, vous pouvez spécifier un mécanisme de partitionnement différent qui est mieux adapté à votre problème.

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

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 grâce à la façon dont il mappe les plages aux 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 jeu 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 non plus la sémantique de blocage coopératif et ne peut donc pas être utilisée avec des boucles parallèles qui ont une dépendance vers l’avant.

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 quand vous n’appelez pas d’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 charge. Lorsqu’une plage de travail est terminée, le runtime redistribue des sous-plages de travail entre d’autres threads et ce thread. Utilisez ce partitionneur si votre charge de travail ne relève pas de l’une des autres catégories ou si vous avez besoin d’une prise en charge complète de l’annulation ou du blocage coopératif.

concurrency::simple_partitioner
Divise le travail en plages de sorte que chacune d'elles possède au moins le nombre d’itérations spécifiées par la taille de bloc donnée. Ce type de partitionneur participe à l’équilibrage de charge ; toutefois, le runtime ne divise pas les plages en sous-plages. Pour chaque worker, le runtime vérifie l’annulation et effectue l’équilibrage de charge une fois les itérations _Chunk_size terminé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 a donc moins de surcharge. Utilisez ce type de partitionneur lorsque chaque itération d’une boucle parallèle effectue une quantité fixe et uniforme de travail, et que vous n’avez pas besoin de prise en charge de l’annulation ou du blocage coopératif.

En règle générale, ces partitionneurs sont utilisés de la même façon, à l’exception de affinity_partitioner. La plupart des types de partitionneurs ne conservent pas l’état et ne sont pas modifiés par le runtime. Par conséquent, vous pouvez créer ces objets partitionneurs sur le site d’appel, comme illustré 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 transférer un objet affinity_partitioner en tant que référence non-const de valeur I, afin que l’algorithme puisse stocker l’état en vue de sa réutilisation par les boucles ultérieures. L’exemple suivant montre une application de base qui effectue plusieurs fois la même opération sur un jeu de données en parallèle. L’utilisation de affinity_partitioner peut améliorer les performances, parce que le tableau est susceptible de s’adapter au 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);
    }
}

La meilleure méthode pour déterminer si vous devez utiliser un partitionneur dans un scénario donné consiste à faire des essais et à mesurer la durée des opérations avec des charges et des configurations d’ordinateur représentatives. Par exemple, le partitionnement statique peut accélérer considérablement les opérations sur un ordinateur multicœur doté de quelques cœurs, mais il peut entraîner des ralentissements sur les ordinateurs qui disposent de nombreux cœurs.

[Haut]

Tri parallèle

La 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 disposez d'un ensemble de données pouvant bénéficier d'un tri en parallèle. En particulier, le tri en parallèle est utile lorsque vous disposez d’un jeu de données volumineux ou lorsque vous utilisez une opération de comparaison coûteuse en calcul pour trier vos données. Chacun de ces algorithmes trie les éléments sur place.

Les algorithmes parallel_sort et parallel_buffered_sort sont des algorithmes basés sur la comparaison. Autrement dit, ils comparent les éléments par valeur. L’algorithme parallel_sort n’a pas de configuration de mémoire supplémentaire et convient au tri à usage général. L’algorithme parallel_buffered_sort peut s'avérer plus performant que parallel_sort, mais il nécessite de l’espace O(N).

L’algorithme parallel_radixsort est basé sur le hachage. Autrement dit, il utilise des clés de type entier pour trier les éléments. Grâce aux clés, cet algorithme peut calculer directement la destination d’un élément au lieu d’utiliser des comparaisons. Comme parallel_buffered_sort, cet algorithme nécessite de l’espace O(N).

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

L’illustration suivante montre les propriétés importantes des trois algorithmes de tri parallèles d'une façon plus graphique.

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

L’exemple de base suivant montre comment utiliser parallel_sort pour trier un vector de valeurs int. Par défaut, parallel_sort utilise std::less pour comparer les 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 à l’algorithme parallel_radixsort. Cet exemple trie les points 3D. Les points sont triés en fonction de leur distance par rapport à 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
*/

Cet exemple utilise un ensemble de données relativement restreint à des fins d'illustration. Vous pouvez augmenter la taille initiale du vecteur pour expérimenter l'améliorations des performances sur des jeux de données plus volumineux.

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 std ::hash ou définir votre propre spécialisation. Vous pouvez également utiliser un objet de fonction de hachage personnalisé, comme 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.

Choix d’un algorithme de tri

Dans de nombreux cas, parallel_sort offre le meilleur équilibre entre la vitesse et les performances de la mémoire. Toutefois, à mesure que 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 peuvent être plus performants.. La meilleure façon de déterminer l’algorithme de tri à utiliser dans un scénario donné consiste à expérimenter et à mesurer le temps nécessaire pour trier des données typiques dans des configurations informatiques représentatives. Gardez à l’esprit les instructions suivantes lors du choix d'une stratégie de tri.

• La taille du jeu de données. Dans ce document, un petit jeu de données contient moins de 1 000 éléments, un jeu de données moyen contient entre 10 000 et 100 000 éléments, et un jeu de données volumineux contient plus de 100 000 éléments.

• La quantité de travail effectuée par votre fonction de comparaison ou fonction de hachage.

• La quantité de ressources de calcul disponibles.

• Les caractéristiques de votre jeu de données. Par exemple, un algorithme peut bien fonctionner pour des données qui sont déjà presque triées, mais moins bien pour des données qui ne sont pas du tout triées.

• La taille du segment. L’argument facultatif _Chunk_size spécifie quand l’algorithme passe d’un implémentation de tri parallèle à une implémentation de tri en série, lorsqu'il subdivise le tri global en unités de travail plus petites. Par exemple, si vous indiquez 512, l’algorithme bascule vers l’implémentation en série lorsqu’une unité de travail contient 512 éléments ou moins. Une implémentation en série peut améliorer les performances globales, car elle élimine la surcharge requise pour traiter les données en parallèle.

Il peut ne pas s'avérer utile de trier un petit ensemble de données en parallèle, même si vous disposez d'un grand nombre de ressources informatiques ou si votre fonction de comparaison ou votre fonction de hachage effectue une quantité de travail relativement importante. Vous pouvez utiliser la fonction std::sort pour trier les petits jeux de données. (parallel_sort et parallel_buffered_sort appellent sort lorsque vous spécifiez une taille de bloc plus grande que le jeu de données ; toutefois, parallel_buffered_sort devrait allouer de l’espace O(N), ce qui peut prendre du temps supplémentaire en raison de la contention de verrouillage ou de l’allocation de mémoire.)

Si vous devez conserver la mémoire ou que votre allocateur de mémoire est soumis à une contention de verrouillage, utilisez parallel_sort pour trier un jeu de données de taille moyenne. parallel_sort ne nécessite 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 de taille moyenne et lorsque votre application répond à l'exigence d’espace O(N) supplémentaire. parallel_buffered_sort peut être particulièrement utile lorsque vous disposez d’un grand nombre de ressources de calcul ou d’une fonction de comparaison ou de hachage coûteuse.

Utilisez parallel_radixsort pour trier les jeux de données volumineux et lorsque votre application répond à l'exigence d’espace O(N) supplémentaire. parallel_radixsort peut s'avérer particulièrement utile lorsque l’opération de comparaison équivalente est plus coûteuse ou lorsque les deux opérations le sont.

L’exemple suivant compare les performances de sort, parallel_sort, parallel_buffered_sort et parallel_radixsort par rapport au même grand jeu 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 O(N) pendant le tri, parallel_radixsort est le plus performant sur ce jeu de données dans cette configuration informatique.

[Haut]

Rubriques connexes

Référence

Fonction parallel_for

Fonction parallel_for_each

Fonction parallel_invoke

Classe affinity_partitioner

Classe auto_partitioner

Classe simple_partitioner

Classe static_partitioner

Fonction parallel_sort

Fonction parallel_buffered_sort

Fonction parallel_radixsort