Cómo: Usar parallel.invoke para escribir una rutina de ordenación en paralelo
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.
[!NOTA]
Este ejemplo utiliza una rutina paralela de ordenación a la ilustración.También puede utilizar los algoritmos de ordenación integrados que PPL proporciona: concurrency::parallel_sort, concurrency::parallel_buffered_sort, y concurrency::parallel_radixsort.Para obtener más información, vea Algoritmos paralelos.
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);
}
[parte superior]
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.
.gif "Dd728066.collapse_all(es-es,VS.110).gif")
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
[parte superior]
Compilar el código
Para compilar el código, copiarlo y pegarlo en un proyecto de Visual Studio, o péguelo en un archivo denominado parallel-bitonic-sort.cpp y se ejecuta el siguiente comando en una ventana de símbolo del sistema de Visual Studio.
cl.exe /EHsc parallel-bitonic-sort.cpp
Programación sólida
Este ejemplo utiliza el algoritmo de parallel_invoke en lugar de la clase de 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.