Partager via

Comment : utiliser parallel_invoke pour écrire une routine de tri parallèle

  • Article

Ce document explique comment utiliser l’algorithme parallel_invoke pour améliorer les performances de l’algorithme de tri bitonique. L’algorithme de tri bitonique divise de manière récursive la séquence d’entrée en partitions triées plus petites. L’algorithme de tri bitonique peut s’exécuter en parallèle, car chaque opération de partition est indépendante de toutes les autres opérations.

Bien que le tri bitonique soit un exemple de réseau de tri qui trie toutes les combinaisons de séquences d’entrée, cet exemple trie les séquences dont les longueurs sont une puissance de deux.

Remarque

Cet exemple utilise une routine de tri parallèle pour l’illustration. Vous pouvez également utiliser les algorithmes de tri intégrés que le PPL fournit : concurrency ::p arallel_sort, concurrency ::p arallel_buffered_sort et concurrency ::p arallel_radixsort. Pour plus d’informations, consultez Algorithmes parallèles.

Sections

Ce document décrit les tâches suivantes :

Exécution d’un tri bitonique en série

L’exemple suivant montre la version série de l’algorithme de tri bitonique. La bitonic_sort fonction divise la séquence en deux partitions, trie ces partitions dans des directions opposées, puis fusionne les résultats. Cette fonction s’appelle deux fois de manière récursive pour trier chaque partition.

const bool INCREASING = true;
const bool DECREASING = false;

// Comparator function for the bitonic sort algorithm.
template <class T>
void compare(T* items, int i, int j, bool dir)
{
   if (dir == (items[i] > items[j]))
   {
      swap(items[i], items[j]);
   }
}

// Sorts a bitonic sequence in the specified order.
template <class T>
void bitonic_merge(T* items, int lo, int n, bool dir)
{
   if (n > 1)
   {
      int m = n / 2;
      for (int i = lo; i < lo + m; ++i)
      {
         compare(items, i, i + m, dir);
      }
      bitonic_merge(items, lo, m, dir);
      bitonic_merge(items, lo + m, m, dir);
   }
}

// Sorts the given sequence in the specified order.
template <class T>
void bitonic_sort(T* items, int lo, int n, bool dir)
{
   if (n > 1)
   {
      // Divide the array into two partitions and then sort 
      // the partitions in different directions.
      int m = n / 2;
      bitonic_sort(items, lo, m, INCREASING);
      bitonic_sort(items, lo + m, m, DECREASING);

      // Merge the results.
      bitonic_merge(items,lo, n, dir);
   }
}

// Sorts the given sequence in increasing order.
template <class T>
void bitonic_sort(T* items, int size)
{
    bitonic_sort(items, 0, size, INCREASING);
}

[Haut]

Utilisation de parallel_invoke pour effectuer un tri bitonique en parallèle

Cette section explique comment utiliser l’algorithme parallel_invoke pour effectuer l’algorithme de tri bitonique en parallèle.

Pour effectuer l’algorithme de tri bitonique en parallèle

  1. Ajoutez une #include directive pour le fichier d’en-tête ppl.h.

    #include <ppl.h>

  2. Ajoutez une using directive pour l’espace concurrency de noms.

    using namespace concurrency;

  3. Créez une fonction appelée , qui parallel_bitonic_megeutilise l’algorithme parallel_invoke pour fusionner les séquences en parallèle s’il y a suffisamment de travail à effectuer. Sinon, appelez bitonic_merge pour fusionner les séquences en série.

    // Sorts a bitonic sequence in the specified order.
template <class T>
void parallel_bitonic_merge(T* items, int lo, int n, bool dir)
{   
   // Merge the sequences concurrently if there is sufficient work to do.
   if (n > 500)
   {
      int m = n / 2;
      for (int i = lo; i < lo + m; ++i)
      {
         compare(items, i, i + m, dir);
      }

      // Use the parallel_invoke algorithm to merge the sequences in parallel.
      parallel_invoke(
         [&items,lo,m,dir] { parallel_bitonic_merge(items, lo, m, dir); },
         [&items,lo,m,dir] { parallel_bitonic_merge(items, lo + m, m, dir); }
      );
   }
   // Otherwise, perform the work serially.
   else if (n > 1)
   {
      bitonic_merge(items, lo, n, dir);
   }   
}

  4. Effectuez un processus semblable à celui de l’étape précédente, mais pour la bitonic_sort fonction.

    // Sorts the given sequence in the specified order.
template <class T>
void parallel_bitonic_sort(T* items, int lo, int n, bool dir)
{   
   if (n > 1)
   {
      // Divide the array into two partitions and then sort 
      // the partitions in different directions.
      int m = n / 2;

      // Sort the partitions in parallel.
      parallel_invoke(
         [&items,lo,m] { parallel_bitonic_sort(items, lo, m, INCREASING); },
         [&items,lo,m] { parallel_bitonic_sort(items, lo + m, m, DECREASING); }
      );
      
      // Merge the results.
      parallel_bitonic_merge(items, lo, n, dir);
   }
}

  5. Créez une version surchargée de la parallel_bitonic_sort fonction qui trie le tableau dans l’ordre croissant.

    // Sorts the given sequence in increasing order.
template <class T>
void parallel_bitonic_sort(T* items, int size)
{
   parallel_bitonic_sort(items, 0, size, INCREASING);
}

    L’algorithme parallel_invoke réduit la surcharge en effectuant la dernière série de tâches sur le contexte appelant. Par exemple, dans la fonction, la parallel_bitonic_sort première tâche s’exécute sur un contexte distinct et la deuxième tâche s’exécute sur le contexte appelant.

    // Sort the partitions in parallel.
parallel_invoke(
   [&items,lo,m] { parallel_bitonic_sort(items, lo, m, INCREASING); },
   [&items,lo,m] { parallel_bitonic_sort(items, lo + m, m, DECREASING); }
);

L’exemple complet suivant exécute à la fois la série et les versions parallèles de l’algorithme de tri bitonique. L’exemple imprime également dans la console l’heure nécessaire pour effectuer chaque calcul.

// parallel-bitonic-sort.cpp
// compile with: /EHsc
#include <windows.h>
#include <algorithm>
#include <iostream>
#include <random>
#include <ppl.h>

using namespace concurrency;
using namespace std;

// Calls the provided work function and returns the number of milliseconds 
// that it takes to call that function.
template <class Function>
__int64 time_call(Function&& f)
{
   __int64 begin = GetTickCount();
   f();
   return GetTickCount() - begin;
}

const bool INCREASING = true;
const bool DECREASING = false;

// Comparator function for the bitonic sort algorithm.
template <class T>
void compare(T* items, int i, int j, bool dir)
{
   if (dir == (items[i] > items[j]))
   {
      swap(items[i], items[j]);
   }
}

// Sorts a bitonic sequence in the specified order.
template <class T>
void bitonic_merge(T* items, int lo, int n, bool dir)
{
   if (n > 1)
   {
      int m = n / 2;
      for (int i = lo; i < lo + m; ++i)
      {
         compare(items, i, i + m, dir);
      }
      bitonic_merge(items, lo, m, dir);
      bitonic_merge(items, lo + m, m, dir);
   }
}

// Sorts the given sequence in the specified order.
template <class T>
void bitonic_sort(T* items, int lo, int n, bool dir)
{
   if (n > 1)
   {
      // Divide the array into two partitions and then sort 
      // the partitions in different directions.
      int m = n / 2;
      bitonic_sort(items, lo, m, INCREASING);
      bitonic_sort(items, lo + m, m, DECREASING);

      // Merge the results.
      bitonic_merge(items,lo, n, dir);
   }
}

// Sorts the given sequence in increasing order.
template <class T>
void bitonic_sort(T* items, int size)
{
    bitonic_sort(items, 0, size, INCREASING);
}

// Sorts a bitonic sequence in the specified order.
template <class T>
void parallel_bitonic_merge(T* items, int lo, int n, bool dir)
{   
   // Merge the sequences concurrently if there is sufficient work to do.
   if (n > 500)
   {
      int m = n / 2;
      for (int i = lo; i < lo + m; ++i)
      {
         compare(items, i, i + m, dir);
      }

      // Use the parallel_invoke algorithm to merge the sequences in parallel.
      parallel_invoke(
         [&items,lo,m,dir] { parallel_bitonic_merge(items, lo, m, dir); },
         [&items,lo,m,dir] { parallel_bitonic_merge(items, lo + m, m, dir); }
      );
   }
   // Otherwise, perform the work serially.
   else if (n > 1)
   {
      bitonic_merge(items, lo, n, dir);
   }   
}

// Sorts the given sequence in the specified order.
template <class T>
void parallel_bitonic_sort(T* items, int lo, int n, bool dir)
{   
   if (n > 1)
   {
      // Divide the array into two partitions and then sort 
      // the partitions in different directions.
      int m = n / 2;

      // Sort the partitions in parallel.
      parallel_invoke(
         [&items,lo,m] { parallel_bitonic_sort(items, lo, m, INCREASING); },
         [&items,lo,m] { parallel_bitonic_sort(items, lo + m, m, DECREASING); }
      );
      
      // Merge the results.
      parallel_bitonic_merge(items, lo, n, dir);
   }
}

// Sorts the given sequence in increasing order.
template <class T>
void parallel_bitonic_sort(T* items, int size)
{
   parallel_bitonic_sort(items, 0, size, INCREASING);
}

int wmain()
{  
   // For this example, the size must be a power of two.
   const int size = 0x200000;

   // Create two large arrays and fill them with random values.
   int* a1 = new int[size];
   int* a2 = new int[size];

   mt19937 gen(42);
   for(int i = 0; i < size; ++i)
   {
      a1[i] = a2[i] = gen();
   }

   __int64 elapsed;
   
   // Perform the serial version of the sort.
   elapsed = time_call([&] { bitonic_sort(a1, size); });
   wcout << L"serial time: " << elapsed << endl;

   // Now perform the parallel version of the sort.
   elapsed = time_call([&] { parallel_bitonic_sort(a2, size); });
   wcout << L"parallel time: " << elapsed << endl;
 
   delete[] a1;
   delete[] a2;
}

L'exemple de sortie suivant concerne un ordinateur équipé de quatre processeurs.

serial time: 4353
parallel time: 1248

[Haut]

Compilation du code

Pour compiler le code, copiez-le, collez-le dans un projet Visual Studio ou collez-le dans un fichier nommé parallel-bitonic-sort.cpp , puis exécutez la commande suivante dans une fenêtre d’invite de commandes Visual Studio.

cl.exe /EHsc parallel-bitonic-sort.cpp

Programmation fiable

Cet exemple utilise l’algorithme parallel_invoke au lieu de la classe concurrency ::task_group , car la durée de vie de chaque groupe de tâches ne s’étend pas au-delà d’une fonction. Nous vous recommandons d’utiliser parallel_invoke quand vous pouvez le faire, car il a moins de surcharge d’exécution que task group les objets, et vous permet donc d’écrire du code plus performant.

Les versions parallèles de certains algorithmes ne fonctionnent mieux que lorsqu’il y a suffisamment de travail à effectuer. Par exemple, la parallel_bitonic_merge fonction appelle la version série, bitonic_merges’il y a 500 éléments ou moins dans la séquence. Vous pouvez également planifier votre stratégie globale de tri en fonction de la quantité de travail. Par exemple, il peut être plus efficace d’utiliser la version série de l’algorithme de tri rapide si le tableau contient moins de 500 éléments, comme illustré dans l’exemple suivant :

template <class T>
void quick_sort(T* items, int lo, int n)
{
   // TODO: The function body is omitted for brevity.
}

template <class T>
void parallel_bitonic_sort(T* items, int lo, int n, bool dir)
{
   // Use the serial quick sort algorithm if there are relatively few
   // items to sort. The associated overhead for running few tasks in 
   // parallel may not overcome the benefits of parallel processing.
   if (n - lo + 1 <= 500)
   {
      quick_sort(items, lo, n);
   }
   else if (n > 1)
   {
      // Divide the array into two partitions and then sort 
      // the partitions in different directions.
      int m = n / 2;

      // Sort the partitions in parallel.
      parallel_invoke(
         [&items,lo,m] { parallel_bitonic_sort(items, lo, m, INCREASING); },
         [&items,lo,m] { parallel_bitonic_sort(items, lo + m, m, DECREASING); }
      );
      
      // Merge the results.
      parallel_bitonic_merge(items, lo, n, dir);
   }
}

Comme avec n’importe quel algorithme parallèle, nous vous recommandons de profiler et de paramétrer votre code selon les besoins.

Voir aussi

Parallélisme des tâches
fonction parallel_invoke