Partager via

Algorithmes parallèles

  • Article

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

Les algorithmes parallèles sont composés de fonctionnalités existantes dans le runtime d’accès concurrentiel. Par exemple, l’algorithme concurrency ::p arallel_for utilise un objet concurrency ::structured_task_group pour effectuer les itérations de boucle parallèles. Les parallel_for partitions d’algorithmes fonctionnent de manière optimale en fonction du nombre disponible de ressources informatiques.

Sections

Algorithme de parallel_for

L’algorithme concurrency ::p arallel_for effectue à plusieurs reprises la même tâche en parallèle. 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 boucle qui ne partage pas les ressources entre les itérations de cette boucle.

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 une plage de vol 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 processeurs. De même, lorsqu’un thread termine une plage d’itérations, le runtime redistribue le travail entre d’autres threads et 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 des ressources entre les corps de la boucle de manière efficace pour l’exécution parallèle.

L’algorithme parallel_for a plusieurs versions surchargées. La première version prend une valeur de début, 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ébut, une valeur de fin, une valeur par laquelle effectuer l’étape 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 les plages de partitions doivent être comprises entre les threads. Les partitionneurs sont expliqués plus en détail dans la section Partitionnement du travail dans ce document.

Vous pouvez convertir de nombreuses for boucles à utiliser parallel_for. Toutefois, l’algorithme parallel_for diffère de l’instruction for de la manière suivante :

  • 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 lastinférieure à .

  • Le _Index_type paramètre de 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 _Step paramètre est inférieur à 1.

  • Le mécanisme de gestion des exceptions pour l’algorithme parallel_for diffère de celui d’une for boucle. Si plusieurs exceptions se produisent simultanément dans un corps de boucle parallèle, le runtime ne propage qu’une des exceptions au thread appelé parallel_for. En outre, 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, la boucle est placée dans l’état annulé et le runtime dis carte toutes les tâches qui n’ont pas encore démarré. Pour plus d’informations 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 bibliothèque PPL.

Remarque

Le coût de planification résultant de l’équilibrage de charge et de la prise en charge des fonctionnalités telles que l’annulation peut ne pas surmonter les avantages de l’exécution du corps de la boucle en parallèle, en particulier lorsque le corps de la boucle est relativement petit. Vous pouvez réduire cette surcharge à l’aide d’un partitionneur dans votre boucle parallèle. Pour plus d’informations, consultez Partitionnement du travail plus loin dans ce document.

Exemple

L’exemple suivant montre la structure de base de l’algorithme parallel_for . Cet exemple montre comment imprimer 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 imprimées dans la console varie.

Pour obtenir un exemple complet qui utilise l’algorithme parallel_for , consultez How to : Write a parallel_for Loop.

[Haut]

Algorithme de parallel_for_each

L’accès concurrentiel ::p arallel_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 fonctionne à la parallel_for_each fois sur les itérateurs de transfert et les itérateurs d’accès aléatoire, il fonctionne mieux avec les itérateurs d’accès aléatoire.

Exemple

L’exemple suivant montre la structure de base de l’algorithme parallel_for_each . Cet exemple montre comment imprimer 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 imprimées dans la console varie.

Pour obtenir un exemple complet qui utilise l’algorithme parallel_for_each , consultez Guide pratique pour écrire une boucle parallel_for_each.

[Haut]

Algorithme de parallel_invoke

L’algorithme concurrency ::p arallel_invoke exécute un ensemble de tâches en parallèle. Elle 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 passez 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. Le 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 twice fonction sur trois variables locales et imprime le résultat dans 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 obtenir des exemples complets qui utilisent l’algorithme parallel_invoke , consultez How to : Use parallel_invoke to Write a Parallel Sort Routine and How to : Use parallel_invoke to Execute Parallel Operations.

[Haut]

Algorithmes de parallel_transform et de parallel_reduce

Les algorithmes concurrency ::p arallel_transform et concurrency ::p arallel_reduce sont des versions parallèles des algorithmes std ::transform et std ::accumulate, 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 obtenir des performances et des avantages de scalabilité en parallèle.

Important

Les algorithmes et parallel_reduce les parallel_transform algorithmes prennent uniquement en charge l’accès aléatoire, les itérateurs bidirectionnels et les itérateurs de transfert, car ces itérateurs produisent des adresses mémoire stables. En outre, ces itérateurs doivent produire des valeurs non-lconst .

Algorithme de 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.

  • Sum ou take the dot product between two vectors, and perform other numeric calculations on vectors.

  • Effectuez un suivi de rayons 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 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 de base de parallel_transform. Étant donné que 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 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>());

Important

L’itérateur que vous fournissez pour la sortie doit parallel_transform chevaucher complètement l’itérateur d’entrée ou ne pas se chevaucher du tout. Le comportement de cet algorithme n’est pas spécifié si les itérateurs d’entrée et de sortie se chevauchent partiellement.

Algorithme de parallel_reduce

L’algorithme parallel_reduce est utile lorsque vous disposez d’une séquence d’opérations qui répondent à la propriété associatif. (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ément.

L’exemple de base suivant montre comment utiliser l’algorithme parallel_reduce pour combiner une séquence de chaînes en une seule chaîne. Comme pour les exemples pour parallel_transform, les gains de performances ne sont pas attendus 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 comme parallel_reduce abrégé pour l’utilisation de l’algorithme parallel_for_each avec la classe concurrency ::combinable .

Exemple : Exécution d’une carte et d’une 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 la bibliothèque C++ Standard std ::transform et std ::accumulate pour effectuer des opérations de mappage et de réduction. Toutefois, pour 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 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 non prime 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 How to : Perform Map and Reduce Operations in Parallel.

[Haut]

Partitionnement du travail

Pour paralléliser une opération sur une source de données, une étape essentielle consiste à partitionner la source en plusieurs sections accessibles simultanément par plusieurs threads. Un partitionneur spécifie comment un algorithme parallèle doit partitionner des plages entre threads. Comme expliqué précédemment dans ce document, le 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 parallel_foralgorithmes parallel_for_each, et parallel_transform les algorithmes 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 le 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 de 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 sur le même jeu de données plusieurs fois (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. Elle n’utilise pas non plus la sémantique de blocage coopérative 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 prend un _Partitioner paramètre. 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 chaque plage 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 case activée pour l’annulation et effectue l’équilibrage de charge une fois _Chunk_size les itérations 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.

Avertissement

Les algorithmes et parallel_transform les parallel_for_each conteneurs prennent uniquement en charge les conteneurs qui utilisent des itérateurs d’accès aléatoire (tels que std ::vector) pour les partitionneurs statiques, simples et d’affinités. L’utilisation de conteneurs qui utilisent des itérateurs bidirectionnels et transférés génère une erreur au moment de la compilation. Le partitionneur par défaut, prend auto_partitioneren charge les trois de ces types d’itérateurs.

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 passer un affinity_partitioner objet en tant que référence non-l-valueconst afin que l’algorithme puisse stocker l’état des boucles futures à réutiliser. L’exemple suivant montre une application de base qui effectue la même opération sur un jeu de données en parallèle plusieurs fois. L’utilisation de affinity_partitioner peut améliorer les performances, car 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);
    }
}

Attention

Soyez prudent lorsque vous modifiez du code existant qui s’appuie sur la sémantique de blocage coopérative à utiliser static_partitioner ou affinity_partitioner. Ces types de partitionneurs n’utilisent pas l’équilibrage de charge ou le vol de plage, et peuvent donc modifier le comportement de votre application.

La meilleure façon de déterminer s’il faut utiliser un partitionneur dans un scénario donné consiste à expérimenter et à mesurer le temps nécessaire aux opérations pour effectuer des opérations sous des charges représentatives et des configurations d’ordinateur. 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

Le PPL fournit trois algorithmes de tri : concurrency ::p arallel_sort, concurrency ::p arallel_buffered_sort et concurrency ::p arallel_radixsort. Ces algorithmes de tri sont utiles lorsque vous disposez d’un jeu de données qui peut bénéficier d’être 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 en place.

Les parallel_sort algorithmes et parallel_buffered_sort les algorithmes sont des algorithmes basés sur des comparaisons. 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 fonctionner mieux 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 entières pour trier les éléments. En utilisant des 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.

Algorithm Description Mécanisme de tri Stabilité du tri Besoins en mémoire Complexité temporelle Accès itérateur
parallel_sort Tri basé sur la comparaison à usage général. Basé sur la comparaison (croissant) Instable Aucun O((N/P)log(N/P) + 2N((P-1)/P)) Random
parallel_buffered_sort Tri basé sur la comparaison à usage général plus rapide qui nécessite de l’espace O(N). Basé sur la comparaison (croissant) Instable Nécessite un espace O(N) supplémentaire O((N/P)log(N)) Random
parallel_radixsort Tri basé sur une clé entière qui nécessite un espace O(N). Basé sur un hachage Stable Nécessite un espace O(N) supplémentaire O(N/P) Random

L’illustration suivante montre les propriétés importantes des trois algorithmes de tri parallèles plus graphiquement.

Comparison of the sorting algorithms.

Ces algorithmes de tri parallèles suivent les règles de gestion des annulations et des exceptions. Pour plus d’informations 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.

Conseil

Ces algorithmes de tri parallèle prennent en charge la sémantique de déplacement. Vous pouvez définir un opérateur d’affectation de déplacement pour permettre aux opérations d’échange de se produire plus efficacement. Pour plus d’informations sur la sémantique de déplacement et l’opérateur d’affectation de déplacement, consultez Rvalue Reference Declarator : &&, and Move Constructors and Move Assignment Operators (C++). Si vous ne fournissez pas d’opérateur d’affectation de déplacement ou de fonction d’échange, les algorithmes de tri utilisent le constructeur de copie.

L’exemple de base suivant montre comment utiliser parallel_sort pour trier une int vector valeur. 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. Elle utilise la méthode std ::complex ::real pour trier les valeurs doubles> std ::complex<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 à partir d’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
*/

Pour illustration, cet exemple utilise un jeu de données relativement petit. Vous pouvez augmenter la taille initiale du vecteur pour expérimenter des 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 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.

Choix d’un algorithme de tri

Dans de nombreux cas, parallel_sort fournit 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 que vous pouvez mieux effectuer. 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 les données classiques sous des configurations d’ordinateur représentatives. Gardez à l’esprit les instructions suivantes lorsque vous choisissez une stratégie de tri.

  • Taille de votre 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.

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

  • Quantité de ressources informatiques disponibles.

  • Caractéristiques de votre jeu de données. Par exemple, un algorithme peut fonctionner correctement pour les données déjà triées, mais pas aussi pour les données complètement non triées.

  • Taille du bloc. L’argument facultatif _Chunk_size spécifie quand l’algorithme passe d’un parallèle à une implémentation de tri série, car il subdivise le tri global en unités de travail plus petites. Par exemple, si vous fournissez 512, l’algorithme bascule vers l’implémentation série lorsqu’une unité de travail contient 512 éléments ou moins. Une implémentation 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 être utile de trier un petit jeu de données en parallèle, même si vous disposez d’un grand nombre de ressources informatiques disponibles ou que votre fonction de comparaison ou fonction de hachage effectue une quantité relativement importante de travail. Vous pouvez utiliser la fonction std ::sort pour trier les petits jeux de données. (parallel_sort et parallel_buffered_sort appelez sort lorsque vous spécifiez une taille de bloc supérieure au jeu de données ; toutefois, parallel_buffered_sort il faudrait 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 votre allocateur de mémoire est soumis à une contention de verrou, utilisez cette option 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).

Permet parallel_buffered_sort de trier les jeux de données de taille moyenne et lorsque votre application répond aux exigences d’espace O(N) supplémentaires. parallel_buffered_sort peut être particulièrement utile lorsque vous disposez d’un grand nombre de ressources informatiques ou d’une fonction de comparaison coûteuse ou de hachage.

Permet parallel_radixsort de trier les jeux de données volumineux et lorsque votre application répond aux exigences supplémentaires d’espace O(N). parallel_radixsort peut être particulièrement utile lorsque l’opération de comparaison équivalente est plus coûteuse ou lorsque les deux opérations sont coûteuses.

Attention

L’implémentation d’une bonne fonction de hachage nécessite que vous connaissiez la plage de jeux de données et la façon dont chaque élément du jeu de données est transformé en valeur non signée correspondante. Étant donné que l’opération de hachage fonctionne sur des valeurs non signées, envisagez une stratégie de tri différente si les valeurs de hachage non signées ne peuvent pas être générées.

L’exemple suivant compare les performances des sortdonnées aléatoiresparallel_sortparallel_buffered_sort, et parallel_radixsort les mêmes grands ensembles 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 effectue le meilleur sur ce jeu de données sur cette configuration d’ordinateur.

[Haut]

Intitulé Description
Guide pratique pour écrire une boucle parallel_for Montre comment utiliser l’algorithme pour effectuer la parallel_for multiplication de matrices.
Guide pratique pour écrire une boucle parallel_for_each Montre comment utiliser l’algorithme parallel_for_each pour calculer le nombre de nombres premiers dans un objet std ::array en parallèle.
Guide pratique pour utiliser parallel_invoke pour écrire une routine de tri parallèle Montre comment utiliser l'algorithme parallel_invoke pour améliorer les performances de l'algorithme de tri bitonique.
Guide pratique pour utiliser parallel_invoke pour exécuter des opérations parallèles Montre 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.
Guide pratique pour exécuter des opérations de mappage et de réduction en parallèle Montre comment utiliser et parallel_transform parallel_reduce algorithmes pour effectuer une opération de mappage et de réduction qui compte les occurrences de mots dans les fichiers.
Bibliothèque de modèles parallèles Décrit le PPL, qui fournit un modèle de programmation impératif qui favorise 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 le PPL, comment annuler le travail parallèle et comment déterminer quand un groupe de tâches est annulé.
Gestion des exceptions Explique le rôle de gestion des exceptions dans le runtime d’accès concurrentiel.

Référence

fonction parallel_for

fonction parallel_for_each

fonction parallel_invoke

affinity_partitioner, classe

auto_partitioner, classe

simple_partitioner, classe

static_partitioner, classe

fonction parallel_sort

fonction parallel_buffered_sort

fonction parallel_radixsort