Algoritmos paralelos
La Biblioteca de modelos de procesamiento paralelo (PPL) proporciona algoritmos que se aplican a colecciones de datos de manera simultánea. Estos algoritmos se parecen a los que proporciona la Biblioteca de plantillas estándar (STL).
Los algoritmos paralelos se crean a partir de funcionalidad existente en el Runtime de simultaneidad. Por ejemplo, el algoritmo de concurrency::parallel_for usa un objeto de concurrency::structured_task_group para realizar iteraciones del bucle paralelo. El algoritmo parallel_for particiona el trabajo de una manera óptima en función del número de recursos de computación disponibles.
Secciones
El algoritmo parallel_for
El algoritmo parallel_for_each
El algoritmo parallel_invoke
Los algoritmos parallel_transform y parallel_reduce
El algoritmo parallel_transform
El algoritmo parallel_reduce
Ejemplo: realizar una asignación y una reducción en paralelo
Repartir el trabajo
Ordenación paralela
- Elegir un algoritmo de ordenación
El algoritmo parallel_for
El algoritmo de concurrency::parallel_for realiza repetidamente la misma tarea en paralelo. Cada una de estas tareas se parametriza mediante un valor de iteración. Este algoritmo es útil si hay un cuerpo de bucle que no comparte los recursos entre las iteraciones de ese bucle.
El algoritmo parallel_for particiona las tareas de una manera óptima para la ejecución en paralelo. Utiliza un algoritmo y un intervalo de trabajo- robo que roban para equilibrar estas particiones cuando las cargas de trabajo están desequilibradas. Cuando una iteración del bucle bloquea de forma cooperativa, el runtime redistribuye a otros subprocesos o procesadores el intervalo de iteraciones asignado al subproceso actual. Del mismo modo, cuando un subproceso completa un intervalo de iteraciones, el runtime redistribuye el trabajo de otros subprocesos a ese subproceso. El algoritmo parallel_for también admite paralelismo anidado. Cuando un bucle paralelo contiene otro bucle paralelo, el runtime coordina los recursos de procesamiento entre los cuerpos de bucle de manera eficaz para la ejecución en paralelo.
El algoritmo de parallel_for tiene varias versiones sobrecargadas. La primera versión toma un valor inicial, un valor final y una función de trabajo (una expresión lambda, objeto de función o puntero a función). La segunda versión toma un valor inicial, un valor final, un valor de incremento y una función de trabajo. La primera versión de esta función usa 1 como valor de incremento. Las versiones restantes tienen objetos de particionador, que permiten especificar cómo parallel_for debe crear particiones intervalos entre subprocesos. Particionadores se explica con más detalle en la sección Dividir el trabajo en este documento.
Puede convertir muchos bucles for para usar parallel_for. Sin embargo, el algoritmo parallel_for se diferencia de la instrucción for en los aspectos siguientes:
El algoritmo parallel_for de parallel_for no ejecuta las tareas en un orden predeterminado.
El algoritmo parallel_for no admite las condiciones de finalización arbitrarias. El algoritmo parallel_for se detiene cuando el valor actual de la variable de iteración es uno menos que _Last.
El parámetro de tipo _Index_type debe ser de tipo entero. Este tipo entero puede ser con signo o sin signo.
La iteración del bucle debe ser hacia delante. El algoritmo parallel_for produce una excepción de tipo std::invalid_argument si el parámetro _Step es menor que 1.
El mecanismo de control de excepciones para el algoritmo parallel_for difiere del de un bucle for. Si se producen varias excepciones simultáneamente en el cuerpo de un bucle paralelo, el runtime propaga solo una de las excepciones al subproceso que llamó a parallel_for. Además, cuando una iteración del bucle produce una excepción, el runtime no detiene inmediatamente el bucle completo. En su lugar, el bucle se coloca en el estado cancelado y el runtime descarta cualquier tarea que no se haya iniciado. Para obtener más información sobre el control de excepciones y los algoritmos paralelos, vea Control de excepciones en el runtime de simultaneidad.
Aunque el algoritmo parallel_for no admite condiciones de finalización arbitrarias, se puede usar la cancelación para detener todas las tareas. Para obtener más información sobre la cancelación, vea Cancelación en la biblioteca PPL.
Nota
El costo de programación resultante del equilibrio de carga y la compatibilidad con características como la cancelación podría no superar las ventajas que supone ejecutar el cuerpo del bucle en paralelo, sobre todo cuando el cuerpo del bucle es relativamente pequeño.Puede minimizar esta sobrecarga mediante un particionador en el bucle paralelo.Para obtener más información, vea Dividir el trabajo más adelante en este documento.
Ejemplo
En el ejemplo siguiente se muestra la estructura básica del algoritmo parallel_for. En este ejemplo se imprime en la consola cada valor del intervalo [1, 5] en paralelo.
// 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();
});
}
Este ejemplo genera la siguiente salida de ejemplo:
Puesto que el algoritmo parallel_for actúa sobre cada elemento en paralelo, el orden en el que los valores se imprimen en la consola varía.
Para obtener un ejemplo completo que usa el algoritmo parallel_for, vea Cómo: Escribir un bucle parallel_for.
[Arriba]
El algoritmo parallel_for_each
El algoritmo de concurrency::parallel_for_each realiza tareas en un contenedor iterativo, como los proporcionados por STL, en paralelo. Usa la misma lógica de creación de particiones que el algoritmo parallel_for.
El algoritmo parallel_for_each se parece al algoritmo std::for_each, con la salvedad de que el algoritmo parallel_for_each ejecuta las tareas de forma simultánea. Como sucede con otros algoritmos paralelos, parallel_for_each no ejecuta las tareas en un orden concreto.
Aunque el algoritmo parallel_for_each funciona con iteradores hacia delante e iteradores del acceso aleatorio, funciona mejor con estos últimos.
Ejemplo
En el ejemplo siguiente se muestra la estructura básica del algoritmo parallel_for_each. En este ejemplo se imprime en la consola cada valor de un objeto std::array en paralelo.
// 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
*/
Este ejemplo genera la siguiente salida de ejemplo:
Puesto que el algoritmo parallel_for_each actúa sobre cada elemento en paralelo, el orden en el que los valores se imprimen en la consola varía.
Para obtener un ejemplo completo que usa el algoritmo parallel_for_each, vea Cómo: Escribir un bucle parallel_for_each.
[Arriba]
El algoritmo parallel_invoke
El algoritmo de concurrency::parallel_invoke ejecuta un conjunto de tareas en paralelo. No vuelve hasta que finaliza cada tarea. Este algoritmo es útil cuando hay varias tareas independientes que se desea ejecutar al mismo tiempo.
El algoritmo parallel_invoke toma como parámetros una serie de funciones de trabajo (funciones lambda, objetos de función o punteros a función). El algoritmo parallel_invoke se sobrecarga para tomar entre dos y diez parámetros. Cada función que se pase a parallel_invoke no debe tomar ningún parámetro.
Como sucede con otros algoritmos paralelos, parallel_invoke no ejecuta las tareas en un orden concreto. En el tema Paralelismo de tareas (Runtime de simultaneidad) se explica cómo se relaciona el algoritmo parallel_invoke con tareas y grupos de tareas.
Ejemplo
En el ejemplo siguiente se muestra la estructura básica del algoritmo parallel_invoke. En este ejemplo se llama simultáneamente a la función twice en tres variables locales y se imprime el resultado en la consola.
// 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;
}
Este ejemplo produce el siguiente resultado:
Para obtener ejemplos completos que usan el algoritmo parallel_invoke, vea Cómo: Usar parallel.invoke para escribir una rutina de ordenación en paralelo y Cómo: Usar parallel.invoke para ejecutar operaciones paralelas.
[Arriba]
Los algoritmos parallel_transform y parallel_reduce
Los algoritmos de concurrency::parallel_transform y de concurrency::parallel_reduce son versiones en paralelo de los algoritmos std::transform y std::accumulateSTL, respectivamente. Las versiones del runtime de simultaneidad se comportan como las versiones de STL salvo que el orden de operación no se determina como se ejecutan en paralelo. Utilice estos algoritmos cuando se ejecuta un conjunto que sea suficientemente grande obtener ventajas de rendimiento y la escalabilidad de ser procesado en paralelo.
Importante
Los algoritmos de parallel_transform y de parallel_reduce sólo admiten de acceso aleatorio, bidireccional, e iteradores hacia delante porque estos iteradores generan a direcciones de memoria estables.Además, estos iteradores deben generar los l- valores no deconst .
El algoritmo parallel_transform
Puede usar el algoritmo de parallel transform para realizar muchas operaciones de la paralelización de los datos. Por ejemplo, puede:
Ajuste el ajuste de una imagen, y realizar otras operaciones de procesamiento de imágenes.
La suma o toma el producto de puntos de dos vectores, y realizar otros cálculos numéricos sobre vectores.
Realice el trazado de rayos 3D, donde cada iteración hace referencia a un píxel que debe ser generado.
El ejemplo siguiente se muestra la estructura básica que se utiliza para llamar al algoritmo de parallel_transform . Este ejemplo niega cada elemento de un objeto de std::vector de dos maneras. La primera forma utiliza una expresión lambda. La segunda manera utiliza std::negate, que deriva 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>());
}
Advertencia
Este ejemplo muestra el uso básico de parallel_transform.Dado que la función de trabajo no realiza una cantidad de trabajo significativa, un aumento significativo en el rendimiento no se espera en este ejemplo.
El algoritmo de parallel_transform tiene dos sobrecargas. La primera sobrecarga toma un rango de entrada y una función singular. La función unaria puede ser una expresión lambda que toma un argumento, un objeto de función, o un tipo que se deriva de unary_function. La segunda sobrecarga toma dos rangos de entrada y una función binaria. La función binaria puede ser una expresión lambda que toma dos argumentos, un objeto de función, o un tipo que se deriva de std::binary_function. El ejemplo siguiente muestra estas diferencias.
//
// 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>());
Importante
El iterador suministrada para la salida de parallel_transform debe superponer completamente el iterador de entrada o no superponer en absoluto.El comportamiento de este algoritmo está sin especificar si los iteradores de entrada y salida se superponen parcialmente.
El algoritmo parallel_reduce
El algoritmo de parallel_reduce es útil cuando tiene una secuencia de operaciones que satisfacen la propiedad asociativa. (Este algoritmo no requiere la propiedad conmutativa.) Algunas de las operaciones que puede realizar con parallel_reduce:
Multiplique secuencias de matrices para generar una matriz.
Multiplicar un vector con una secuencia de matrices para generar un vector.
Calcula la longitud de una secuencia de cadenas.
Combina una lista de elementos, como cadenas, en un elemento.
El siguiente ejemplo básico se muestra cómo usar el algoritmo de parallel_reduce para combinar una secuencia de cadenas en una cadena. Como con los ejemplos para parallel_transform, las mejoras de rendimiento no se esperan en este ejemplo básico.
// 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;
words.push_back(L"Lorem ");
words.push_back(L"ipsum ");
words.push_back(L"dolor ");
words.push_back(L"sit ");
words.push_back(L"amet, ");
words.push_back(L"consectetur ");
words.push_back(L"adipiscing ");
words.push_back(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.
*/
En muchos casos, puede considerar parallel_reduce como abreviada para el uso del algoritmo de parallel_for_each así como la clase de concurrency::combinable .
Ejemplo: realizar una asignación y una reducción en paralelo
Una operación de asignación aplica una función a cada valor en una secuencia. Una operación de reducir combina los elementos de una secuencia de un valor. Puede utilizar las clases estándar de (STL) std::transformstd::accumulate de la biblioteca de plantillas para realizar la asignación y reducir operaciones. Sin embargo, para muchos problemas, puede utilizar el algoritmo de parallel_transform para realizar la operación de asignación en paralelo y el algoritmo de parallel_reduce realiza la operación de reducir en paralelo.
El ejemplo siguiente se compara el tiempo necesario para calcular la suma de números primos en serie y en paralelo. La fase de mapa transforma valores no primos en 0 y la fase de reducir suma los valores.
// 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
*/
Para obtener otro ejemplo que realiza un mapa y reduzca la operación en paralelo, vea Cómo: Realizar operaciones de asignación y reducción en paralelo.
[Arriba]
Repartir el trabajo
Para ejecutar una operación en un origen de datos, un paso esencial es crear particiones del origen en varias secciones a las que se puede tener acceso simultáneamente a varios subprocesos. Un particionador especifica cómo un algoritmo paralelo debe crear particiones intervalos entre subprocesos. Como se explica anteriormente en este documento, PPL usa un mecanismo predeterminado de partición que cree una carga de trabajo inicial y utilice un algoritmo y un intervalo de trabajo- robo que roban para equilibrar estas particiones cuando las cargas de trabajo están desequilibradas. Por ejemplo, cuando una iteración del bucle se un intervalo de iteraciones, el runtime redistribuye el trabajo de otros subprocesos a ese subproceso. Sin embargo, en algunos escenarios, puede especificar otro mecanismo de partición que se adapta mejor al problema.
parallel_for, parallel_for_each, y algoritmos de parallel_transform proporcionan las versiones sobrecargadas que toman un parámetro adicional, _Partitioner. Este parámetro define el particionador tipo que divide el trabajo. Éstas son las clases de particionadores que PPL define:
concurrency::affinity_partitioner
Divide el trabajo en un número fijo de intervalos (normalmente el número de subprocesos de trabajo disponibles para trabajar en el bucle). Este tipo de particionadores se parece a static_partitioner, pero mejora afinidad de caché en que asigna intervalos a subprocesos de trabajo. Este tipo de particionador puede mejorar el rendimiento cuando un bucle se ejecuta durante los mismos varias veces de conjunto de datos (como un bucle dentro de un bucle) y los datos se ajusta en caché. Este particionador no participa totalmente en la cancelación. Tampoco utiliza la semántica de bloqueo cooperativo y por consiguiente no se puede utilizar con los bucles paralelos que dependen directa.concurrency::auto_partitioner
Divide el trabajo en un número inicial de intervalos (normalmente el número de subprocesos de trabajo disponibles para trabajar en el bucle). El tiempo de ejecución utiliza este tipo de forma predeterminada cuando no llama a un algoritmo paralelo sobrecargado que toma un parámetro de _Partitioner . Cada intervalo se puede dividir en sub- intervalos y, de esta manera el equilibrio de carga que aparezca. Cuando un intervalo de trabajo completa, el runtime redistribuye sub- intervalos de trabajo de otros subprocesos a ese subproceso. Utilice este particionador si la carga de trabajo no baja con una de las otras categorías o si necesita compatibilidad completa para la cancelación o el bloqueo cooperativo.concurrency::simple_partitioner
Divide el trabajo en intervalos de modo que cada intervalo tenga al menos el número de iteraciones especificadas por el tamaño especificado del fragmento. Este tipo de particionador participa en equilibrio equilibrio de carga; sin embargo, el runtime no divide intervalos en sub- intervalos. Para cada trabajo, el tiempo de ejecución la cancelación y realizan el equilibrio de carga después de las iteraciones de _Chunk_size completado.concurrency::static_partitioner
Divide el trabajo en un número fijo de intervalos (normalmente el número de subprocesos de trabajo disponibles para trabajar en el bucle). Este tipo de particionador puede mejorar el rendimiento porque no utiliza el trabajo- robo y por consiguiente tiene menos sobrecarga. Utilice este particionador tipo cuando cada iteración de un bucle paralelo realiza una cantidad de trabajo fija y uniforme y no necesita la compatibilidad con la cancelación ni reenvía el bloqueo cooperativo.
Advertencia
Los algoritmos de parallel_for_each y de parallel_transform solo admiten los contenedores que utilizan iteradores de acceso aleatorio (como std::vector) para el estático, simple, y los particionadores de afinidad.El uso de contenedores que utilizan bidireccional y los iteradores hacia delante genera un error en tiempo de compilación.El particionador predeterminado, auto_partitioner, admite los tres de estos tipos de iterador.
Normalmente, estos particionadores se utilizan de la misma manera, a excepción de affinity_partitioner. La mayoría de los tipos del particionador no mantienen el estado y no se modifican el motor en tiempo de ejecución. Por consiguiente puede crear estos objetos de particionador en el sitio de llamada, como se muestra en el ejemplo siguiente.
// 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());
}
Sin embargo, debe pasar un objeto comoconstno-, referencia de affinity_partitioner de l- valor de modo que el algoritmo puede almacenar el estado para que los bucles futuros reusen. El ejemplo siguiente se muestra una aplicación básica que realiza la misma operación en varias veces un conjunto de datos en paralelo. El uso de affinity_partitioner puede mejorar el rendimiento porque la matriz es probable caber en caché.
// 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);
}
}
Advertencia
Tenga cuidado al modificar el código existente que utiliza la semántica de bloqueo cooperativo para utilizar static_partitioner o affinity_partitioner.Estos tipos de particionador no utilizan el equilibrio de carga ni se extienden robando y, por consiguiente pueden modificar el comportamiento de la aplicación.
La mejor manera de determinar si utilizar un particionador en un escenario determinado es experimentar y medir cuánto tiempo tardan las operaciones en completarse con cargas y configuraciones de equipo representativas. Por ejemplo, la creación de particiones estáticas podría proporcionar un aumento de velocidad significativo en un equipo multiproceso con pocos núcleos, pero podría ralentizar los equipos que tienen relativamente más núcleos.
[Arriba]
Ordenación paralela
PPL proporciona tres algoritmos de ordenación: concurrency::parallel_sort, concurrency::parallel_buffered_sort, y concurrency::parallel_radixsort. Estos algoritmos de ordenación son útiles cuando tiene un conjunto de datos que se puede beneficiar de ajustar su tamaño en paralelo. En particular, el cambio en paralelo es útil cuando hay un conjunto de datos grande o cuando se usa una operación de comparación de cómputo- costosa para ordenar los datos. Cada uno de estos elementos de las ordenaciones de algoritmos en contexto.
Los algoritmos de parallel_sort y de parallel_buffered_sort son ambos algoritmos comparar- basados en. Es decir, comparan elementos por valor. El algoritmo de parallel_sort no tiene ningún requerimiento de memoria adicional, y es adecuado para la ordenación de uso general. El algoritmo de parallel_buffered_sort puede ser mejor que parallel_sort, pero requiere espacio de O(N) .
Hash- está basado en el algoritmo de parallel_radixsort . Es decir, utiliza las teclas completas para ordenar elementos. Utilizando las teclas, este algoritmo puede calcular directamente el destino de un elemento en lugar de usar comparaciones. Como parallel_buffered_sort, este algoritmo requiere espacio de O(N) .
La tabla siguiente se resumen las propiedades importantes de los tres algoritmos de ordenación paralelos.
Algoritmo |
Descripción |
Mecanismo de ordenación |
Estabilidad de ordenación |
Requisitos de memoria |
Complejidad de tiempo |
Acceso de iterador |
|---|---|---|---|---|---|---|
parallel_sort |
Ordenación comparar- basada de uso general. |
Comparar-basado (ascendiendo) |
Inestable |
None |
O((N/P)log(N/P) + 2N((P-1)/P)) |
Random |
parallel_buffered_sort |
Una ordenación comparar- basada de uso general más rápida que requiere O (N) espacio. |
Comparar-basado (ascendiendo) |
Inestable |
Requiere espacio adicional de O(N) |
O((N/P)log(N)) |
Random |
parallel_radixsort |
Ordenación tecla-basada entero que requiere O (N) espacio. |
Hash-basado |
Estable |
Requiere espacio adicional de O(N) |
O(N/P) |
Random |
La ilustración siguiente se muestran las propiedades importantes de los tres algoritmos de ordenación paralelos más gráficamente.
.png "Comparación de los algoritmos de ordenación")
Estos algoritmos de ordenación paralelos siguen las reglas de cancelación y control de excepciones. Para obtener más información sobre la cancelación y el control de excepciones en el runtime de simultaneidad, vea Cancelar algoritmos paralelos y Control de excepciones en el runtime de simultaneidad.
Sugerencia
Semántica paralela de movimiento de soporte de estos algoritmos de ordenación.Puede definir un operador de asignación de movimiento para permitir a operaciones de intercambio para producirse más eficazmente.Para obtener más información sobre la semántica de transferencia de recursos y el operador de asignación de movimiento, vea Declarador de referencia a un valor R: &&, y Cómo: Escribir un constructor Move.Si no proporciona una función de operador de asignación o de intercambio de movimiento, los algoritmos de ordenación utilizan el constructor de copia.
El siguiente ejemplo básico se muestra cómo utilizar parallel_sort para ordenar vector de los valores de int . De forma predeterminada, parallel_sort utiliza std::less para comparar valores.
// 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
*/
Este ejemplo muestra cómo proporcionar una personalizada compara la función. Utiliza el método de std::complex::real para ordenar los valores de std::complex<doble> en orden ascendente.
// 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)
*/
Este ejemplo muestra cómo proporcionar una función hash para el algoritmo de parallel_radixsort . Este ejemplo ordena los puntos 3D. Se ordenan los puntos según la distancia de un punto de referencia.
// 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
*/
En la ilustración, este ejemplo utiliza un conjunto de datos relativamente pequeño. Puede aumentar el tamaño inicial del vector para experimentar con mejoras de rendimiento sobre los conjuntos de datos.
Este ejemplo utiliza una expresión lambda como función hash. También puede utilizar una de las implementaciones integradas de la clase de std::hash o definirla dispone de especialización. También puede utilizar un objeto personalizado de la función hash, como se muestra en este ejemplo:
// 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 función hash debe devolver un tipo entero (std::is_integral::value debe ser true). Este tipo entero debe poder convertirse escribir size_t.
Elegir un algoritmo de ordenación
En muchos casos, parallel_sort proporciona el mejor equilibrio de rendimiento de progreso y de memoria. Sin embargo, como aumenta el tamaño del conjunto de datos, el número de procesadores disponibles, o la complejidad de la función de comparación, parallel_buffered_sort o parallel_radixsort puede ser mejor. La mejor manera de determinar que el algoritmo de ordenación a utilizar en un escenario determinado es experimentar y medir cuánto tiempo tarda ordenar datos típicos en configuraciones de equipo representativas. Mantenga las instrucciones siguientes al elegir una estrategia de ordenación.
El tamaño del conjunto de datos. En este documento, un pequeño conjunto de datos contiene menos de 1.000 elementos, un medio de conjunto de datos contiene entre 10.000 y 100.000 elementos, y un conjunto de datos grande contiene más de 100.000 elementos.
La cantidad de trabajo que la función o la función hash de comparar realiza.
La cantidad de recursos disponibles.
Las características del conjunto de datos. Por ejemplo, un algoritmo puede funcionar bien para los datos que ya se ordena casi, pero no también para datos completamente sin ordenar.
El tamaño del fragmento. El argumento opcional de _Chunk_size especifica cuando el algoritmo de un paralelo un serie ordenan la implementación mientras divide la ordenación total en unidades más pequeñas de trabajo. Por ejemplo, si proporciona 512, el algoritmo a la implementación en serie a una unidad de trabajo contiene 512 o a menos elementos. La implementación en serie puede mejorar el rendimiento total porque elimina la sobrecarga necesaria procesar datos en paralelo.
Puede no ser pena ordenar un pequeño conjunto de datos en paralelo, aunque tiene un gran número de recursos de computación disponibles o la función o la función hash de comparar realiza relativamente grandes cantidades de. Puede utilizar la función de std::sort para ordenar conjuntos de datos pequeños. (parallel_sort y parallel_buffered_sort llama sort cuando se especifica un tamaño de fragmento que sea mayor que el conjunto de datos; sin embargo, parallel_buffered_sort tendría que asignar espacio de O(N) , que puede tardar tiempo adicional por la contención o la asignación de memoria de bloqueo).
Si debe conservar la memoria o el asignador de memoria está bajo la contención de bloqueo, utilice parallel_sort de ordenar un conjunto de datos intermedio. parallel_sort no requiere espacio adicional; los otros algoritmos requieren el espacio de O(N) .
Utilice parallel_buffered_sort para ordenar los conjuntos de datos medianos y cuando la aplicación cumple el requisito adicional de espacio de O(N) . parallel_buffered_sort puede ser especialmente útil cuando tiene un gran número de recursos de computación o un costoso para comparar la función o la función hash.
Utilice parallel_radixsort para ordenar los conjuntos de datos grandes y cuando la aplicación cumple el requisito adicional de espacio de O(N) . parallel_radixsort puede ser especialmente útil cuando la operación de comparación equivalente es más costosa o cuando ambas operaciones son costosas.
Advertencia
Implementar una buena función hash requiere que conozca el intervalo del conjunto de datos y cómo cada elemento del conjunto de datos se transforma en un valor sin signo correspondiente.Porque la operación hash funciona en valores sin signo, considere otra estrategia de ordenación si los valores hash sin signo no pueden ser generados.
El ejemplo siguiente se compara el rendimiento de sort, de parallel_sort, de parallel_buffered_sort, y de parallel_radixsort con el mismo conjunto grande de datos aleatorios.
// 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.
*/
En este ejemplo, que supone que puede asignar espacio de O(N) durante la ordenación, parallel_radixsort realiza el mejor en este conjunto de datos en esta configuración de equipo.
[Arriba]
Temas relacionados
Título |
Descripción |
|---|---|
Muestra cómo usar el algoritmo parallel_for para realizar una multiplicación de matrices. |
|
Muestra cómo usar el algoritmo parallel_for_each para calcular el recuento de números primos de un objeto std::array en paralelo. |
|
Cómo: Usar parallel.invoke para escribir una rutina de ordenación en paralelo |
Muestra cómo usar el algoritmo parallel_invoke para mejorar el rendimiento del algoritmo de ordenación bitónica. |
Cómo: Usar parallel.invoke para ejecutar operaciones paralelas |
Muestra cómo usar el algoritmo parallel_invoke para mejorar el rendimiento de un programa que realiza varias operaciones en un origen de datos compartido. |
Cómo: Realizar operaciones de asignación y reducción en paralelo |
Muestra cómo utilizar los algoritmos de parallel_transform y de parallel_reduce para realizar un mapa y reducir la operación que cuenta las apariciones de palabras en archivos. |
Se describe la biblioteca PPL, que proporciona un modelo de programación imperativo que promueve la escalabilidad y facilidad de uso para desarrollar aplicaciones simultáneas. |
|
Explica el rol de cancelación en PPL, cómo cancelar trabajos paralelos y cómo determinar cuándo se ha cancelado un grupo de tareas. |
|
Explica el rol de control de excepciones en el Runtime de simultaneidad. |