Cómo: Usar parallel.invoke para escribir una rutina de ordenación en paralelo

Artículo
08/10/2011

En este documento se describe cómo usar el algoritmo parallel_invoke para mejorar el rendimiento del algoritmo de ordenación bitónica. Este algoritmo divide de forma recursiva la secuencia de entrada en particiones ordenadas más pequeñas. Se puede ejecutar en paralelo porque cada operación de partición es independiente de las demás operaciones.

Aunque la ordenación bitónica es un ejemplo de una red de ordenación que ordena todas las combinaciones de secuencias de entrada, en este ejemplo se ordenan secuencias cuyas longitudes son potencia de dos.

Secciones

En este documentos se describen las tareas siguientes:

Realizar la ordenación bitónica en serie
Usar parallel_invoke para realizar la ordenación bitónica en paralelo

Realizar la ordenación bitónica en serie

En el siguiente ejemplo se muestra la versión en serie del algoritmo de ordenación bitónica. La función bitonic_sort divide la secuencia en dos particiones, ordena estas particiones en direcciones opuestas y, a continuación, combina los resultados. Esta función se llama a sí misma dos veces de forma recursiva para ordenar cada partición.

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);
}

[Ir al principio]

Usar parallel_invoke para realizar la ordenación bitónica en paralelo

En esta sección se describe cómo usar el algoritmo parallel_invoke para realizar el algoritmo de ordenación bitónica en paralelo.

Procedimientos

Para realizar el algoritmo de ordenación bitónica en paralelo

Agregue una directiva #include para el archivo de encabezado ppl.h.
```
#include <ppl.h>
```
Agregue una directiva using para el espacio de nombres Concurrency.
```
using namespace Concurrency;
```

Cree una nueva función, denominada parallel_bitonic_mege, que use el algoritmo parallel_invoke para combinar las secuencias en paralelo si hay suficiente cantidad de trabajo. De lo contrario, llame a bitonic_merge para combinar las secuencias en serie.

// 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);
   }   
}

Realice un proceso similar al del paso anterior, pero en este caso para la función bitonic_sort.

// 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);
   }
}

Cree una versión sobrecargada de la función parallel_bitonic_sort que ordene la matriz en sentido ascendente.

// 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);
}

El algoritmo parallel_invoke reduce la sobrecarga al realizar la última tarea de la serie en el contexto de llamada. Por ejemplo, en la función parallel_bitonic_sort, la primera tarea se ejecuta en un contexto independiente y la segunda tarea se ejecuta en el contexto de llamada.

// 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); }
);

El siguiente ejemplo completo realiza tanto las versiones en serie como en paralelo del algoritmo de ordenación bitónica. También imprime en la consola el tiempo necesario para realizar cada cálculo.

// 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;
}

La siguiente salida de ejemplo corresponde a un equipo con cuatro procesadores.

serial time: 4353
parallel time: 1248

[Ir al principio]

Compilar el código

Para compilar el código, cópielo y, a continuación, péguelo en un proyecto de Visual Studio, o péguelo en un archivo denominado parallel-bitonic-sort.cpp y, a continuación, ejecute el siguiente comando en una ventana del símbolo del sistema de Visual Studio.

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

Programación sólida

En este ejemplo se usa el algoritmo parallel_invoke en lugar de la clase Concurrency::task_group porque la duración de cada grupo de tareas no se extiende más allá de una función. Se recomienda usar parallel_invoke siempre que se pueda, ya que tiene menos sobrecarga de ejecución que los objetos task group y, por tanto, permite escribir código con mejor rendimiento.

Las versiones en paralelo de algunos algoritmos presentan mejor rendimiento cuando existe suficiente trabajo. Por ejemplo, la función parallel_bitonic_merge llama a la versión en serie, bitonic_merge, si existen 500 elementos o menos en la secuencia. También puede planear la estrategia global de ordenación según la cantidad de trabajo. Por ejemplo, puede ser más eficaz usar la versión en serie del algoritmo de ordenación rápida si la matriz contiene menos de 500 elementos, como se muestra en el ejemplo siguiente:

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);
   }
}

Como con cualquier algoritmo paralelo, se recomienda generar un perfil y optimizar el código según corresponda.

Vea también

Referencia

parallel_invoke (Función)

Conceptos

Paralelismo de tareas (Runtime de simultaneidad)

Historial de cambios

Fecha	Historial	Motivo
Julio de 2010	Ejemplo actualizado para usar parallel_invoke.	Mejora de la información.

Julio de 2010

Ejemplo actualizado para usar parallel_invoke.

Mejora de la información.

Compartir a través de