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:
En este ejemplo se utiliza una rutina de ordenación paralela para la ilustración. También puede utilizar los algoritmos de ordenación integrados que proporciona PPL: concurrency::parallel_sort, concurrency::parallel_buffered_sort y concurrency::parallel_radixsort. Para obtener más información, consulte Algoritmos paralelos.
Secciones
En este documentos se describen las tareas siguientes:
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);
}
[Arriba]
Uso de 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.
Para realizar el algoritmo de ordenación bitónica en paralelo
Agregue una directiva
#includepara el archivo de encabezado ppl.h.#include <ppl.h>Agregue una directiva
usingpara el espacio de nombresconcurrency.using namespace concurrency;Cree una nueva función, denominada
parallel_bitonic_mege, que use el algoritmoparallel_invokepara fusionar mediante combinación las secuencias en paralelo si hay suficiente cantidad de trabajo. De lo contrario, llame abitonic_mergepara 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_sortque 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_invokereduce la sobrecarga al realizar la última tarea de la serie en el contexto de llamada. Por ejemplo, en la funciónparallel_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
[Arriba]
Compilar el código
Para compilar el código, cópielo y péguelo en un proyecto de Visual Studio, o en un archivo denominado parallel-bitonic-sort.cpp. Después, ejecute el comando siguiente 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.
Consulte también
Comentarios
Próximamente: A lo largo de 2024 iremos eliminando gradualmente GitHub Issues como mecanismo de comentarios sobre el contenido y lo sustituiremos por un nuevo sistema de comentarios. Para más información, vea: https://aka.ms/ContentUserFeedback.
Enviar y ver comentarios de