Algoritmos paralelos

La biblioteca de patrones paralelos (PPL) proporciona algoritmos que realizan trabajo simultáneamente en recolección de datos. Estos algoritmos son similares a los proporcionados por la Biblioteca Estándar C++.

Los algoritmos paralelos se componen de la funcionalidad existente en el Runtime de simultaneidad. Por ejemplo, el algoritmoconcurrency::p arallel_for utiliza un objeto concurrency::structured_task_group para realizar las iteraciones del bucle paralelo. Las particiones algoritmosparallel_for funcionan de forma óptima dado el número disponible de recursos informáticos.

Secciones

• Algoritmo de parallel_for

• Algoritmo de parallel_for_each

• Algoritmo de parallel_invoke

• Algoritmos parallel_transform y parallel_reduce

  • Algoritmo de parallel_transform

  • Algoritmo de parallel_reduce

  • Ejemplo: Realizar asignación y reducir en paralelo

• Trabajo de creación de particiones

• Ordenación en paralelo

  • Elección de un algoritmo de ordenación

Algoritmo de parallel_for

El algoritmo concurrency::p arallel_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 cuando tiene un cuerpo de bucle que no comparte recursos entre iteraciones de ese bucle.

Las parallel_for particiones de algoritmos se encarga de forma óptima para la de la ejecución en paralelo. Usa un algoritmo de robo de trabajo y un robo por intervalos para equilibrar estas particiones cuando las cargas de trabajo están desequilibradas. Cuando una iteración de bucle se bloquea de forma cooperativa, el tiempo de ejecución redistribuye el intervalo de iteraciones que se asigna al subproceso actual a otros subprocesos o procesadores. De forma similar, cuando un subproceso completa un intervalo de iteraciones, el tiempo de ejecución redistribuye el trabajo de otros subprocesos a ese subproceso. El algoritmo parallel_for también admite el paralelismo anidado. Cuando un bucle paralelo contiene otro bucle paralelo, el tiempo de ejecución coordina los recursos de procesamiento entre los cuerpos del bucle de una manera eficaz para la ejecución en paralelo.

El algoritmoparallel_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, un objeto de función o un puntero de función). La segunda versión toma un valor inicial, un valor final, un valor en el cual pararse y una función de trabajo. La primera versión de esta función usa 1 como valor para pararse. Las versiones restantes toman objetos de particiones, lo que le permite especificar cómo parallel_for debería ser el alcance de las particiones entre subprocesos. Las particiones se explican con más detalle en la sección Trabajo de particiones en este documento.

Puede convertir muchosfor bucles para usar parallel_for. Sin embargo, el algoritmoparallel_for difiere de la for instrucción de las siguientes maneras:

• El parallel_for algoritmo parallel_for no ejecuta las tareas en un orden determinado previamente.

• El algoritmo parallel_for no admite condiciones de terminación arbitrarias. El algoritmo parallel_for se detiene cuando el valor actual de la variable de iteración es uno menor que last.

• El _Index_type tipo de parámetro debe ser un tipo entero. Este tipo entero puede estar firmado o sin firmar.

• La iteración del bucle debe ser hacia delante. El algoritmo parallel_for genera 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 un cuerpo de bucle paralelo, el tiempo de ejecución propaga solo una de las excepciones al subproceso que llamó a parallel_for. Además, cuando una iteración de bucle produce una excepción, el tiempo de ejecución no detiene inmediatamente el bucle general. En su lugar, el bucle se coloca en el estado cancelado y el tiempo de ejecución descarta las tareas que aún no se han iniciado. Para obtener más información sobre el control de excepciones y los algoritmos paralelos, vea Control de excepciones.

Aunque el algoritmo parallel_for no admite condiciones de terminación arbitrarias, 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:

Es posible que el costo de programación que resulta del equilibrio de carga y la compatibilidad con características como la cancelación no supere las ventajas de ejecutar el cuerpo del bucle en paralelo, especialmente cuando el cuerpo del bucle es relativamente pequeño. Puede minimizar esta sobrecarga mediante quien realiza las particiones en el bucle paralelo. Para obtener más información, vea Trabajo de particiones 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:

1 2 4 3 5

Dado que el algoritmoparallel_for actúa en cada elemento en paralelo, el orden en que los valores se imprimen en la consola variará.

Para obtener un ejemplo completo que usa el algoritmo parallel_for, vea Cómo: escribir un bucle parallel_for.

[Arriba]

Algoritmo de parallel_for_each

El algoritmoconcurrency::p arallel_for_each realiza tareas en un contenedor iterativo, tales como las proporcionadas por la biblioteca estándar C++, 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 de la biblioteca de plantillas estándar, excepto en que el algoritmo parallel_for_each ejecuta las tareas de forma simultánea. Al igual que otros algoritmos paralelos, parallel_for_each no ejecuta las tareas en un orden específico.

Aunque el algoritmo parallel_for_each funciona tanto en iteradores de reenvío como en iteradores de acceso aleatorio, funciona mejor con iteradores de acceso aleatorio.

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 std::array objeto 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:

4 5 1 2 3

Dado que el algoritmoparallel_for_each actúa en cada elemento en paralelo, el orden en que los valores se imprimen en la consola variará.

Para obtener un ejemplo completo que usa el algoritmo parallel_for_each, vea Cómo: Escribir un bucle parallel_for_each.

[Arriba]

Algoritmo de parallel_invoke

El algoritmoconcurrency::p arallel_invoke ejecuta un conjunto de tareas en paralelo. No se devuelve hasta que finaliza cada tarea. Este algoritmo es útil cuando tiene varias tareas independientes que desea ejecutar al mismo tiempo.

El algoritmoparallel_invoke toma como parámetros una serie de funciones de trabajo (funciones lambda, objetos de función o punteros de función). El algoritmoparallel_invoke está sobrecargado para tomar entre dos y diez parámetros. Todas las funciones que pase a parallel_invoke deben tomar parámetros cero.

Al igual que otros algoritmos paralelos, parallel_invoke no ejecuta las tareas en un orden específico. En el tema Task Parallelism explica cómo el algoritmo parallel_invoke se relaciona con tareas y grupos de tareas.

Ejemplo

En el ejemplo siguiente se muestra la estructura básica del algoritmo parallel_invoke. Este ejemplo llama simultáneamente a la funcióntwice en tres variables locales e 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:

108 11.2 HelloHello

Para obtener ejemplos completos que usan el algoritmo parallel_invoke, vea Cómo: usar parallel_invoke para escribir una rutina de ordenación paralela y Cómo: usar parallel_invoke para ejecutar operaciones paralelas.

[Arriba]

Algoritmos parallel_transform y parallel_reduce

Los algoritmos concurrency::p arallel_transform y concurrency::p arallel_reduceson versiones paralelas de los algoritmos de Biblioteca estándar C++std::transform y std::accumulate, respectivamente. Las Runtime de simultaneidad se comportan como las versiones de la Biblioteca Estándar C++, salvo que el orden de la operación no se determina porque se ejecutan en paralelo. Use estos algoritmos cuando trabaje con un conjunto lo suficientemente grande como para obtener ventajas de rendimiento y escalabilidad al procesarse en paralelo.

Importante

Los algoritmos parallel_transform y parallel_reduce solo admiten iteradores de acceso aleatorio, bidireccionales y de reenvío porque estos iteradores generan direcciones de memoria estables. Además, estos iteradores deben generar valores Lconst no válidos.

Algoritmo de parallel_transform

Puede usar el algoritmo parallel transform para realizar muchas operaciones de paralelización de datos. Por ejemplo, puede hacer lo siguiente:

• Ajuste el brillo de una imagen y realice otras operaciones de procesamiento de imágenes.

• Sume o tome el producto de puntos entre dos vectores y realice otros cálculos numéricos en vectores.

• Realice el seguimiento de rayos 3D, donde cada iteración hace referencia a un píxel que se debe representar.

En el ejemplo siguiente se muestra la estructura básica que se usa para llamar al algoritmo parallel_transform. Este ejemplo niega cada elemento de un objeto vector std:: de dos maneras. La primera forma usa una expresión lambda. La segunda forma usa 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

En este ejemplo se muestra el uso básico de parallel_transform. Dado que la función de trabajo no realiza una cantidad significativa de trabajo, no se espera un aumento significativo del rendimiento en este ejemplo.

El algoritmo parallel_transform tiene dos sobrecargas. La primera sobrecarga toma un intervalo de entrada y una función unaria. La función unaria puede ser una expresión lambda que toma un argumento, un objeto de función o un tipo que deriva de unary_function. La segunda sobrecarga toma dos intervalos 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 deriva de std::binary_function. En el ejemplo siguiente se ilustran 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 que proporciona para la salida de parallel_transform debe superponerse completamente al iterador de entrada o no superponerse en absoluto. El comportamiento de este algoritmo no se especifica si los iteradores de entrada y salida se superponen parcialmente.

Algoritmo de parallel_reduce

El algoritmo parallel_reduce es útil cuando se tiene una secuencia de operaciones que satisfacen la propiedad asociativa. (Este algoritmo no requiere la propiedad conmutativa). Estas son algunas de las operaciones que puede realizar con parallel_reduce:

• Multiplique las secuencias de matrices para generar una matriz.

• Multiplique un vector por una secuencia de matrices para generar un vector.

• Calcule la longitud de una secuencia de cadenas.

• Combine una lista de elementos, como cadenas, en un solo elemento.

En el ejemplo básico siguiente se muestra cómo usar el algoritmo parallel_reduce para combinar una secuencia de cadenas en una cadena. Al igual que con los ejemplos de parallel_transform, no se esperan mejoras de rendimiento 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{
      L"Lorem ",
      L"ipsum ",
      L"dolor ",
      L"sit ",
      L"amet, ",
      L"consectetur ",
      L"adipiscing ",
      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 pensar en parallel_reduce como una abreviatura del uso del algoritmo parallel_for_each junto con la clase concurrency::combinable.

Ejemplo: Realizar asignación y reducir en paralelo

Una operación deasignación aplica una función a cada valor de una secuencia. Una operación dereducción combina los elementos de una secuencia en un valor. Puede usar la Biblioteca estándar C++ std::transform y las funciones std::accumulate para realizar operaciones de asignación y reducción. Sin embargo, para muchos problemas, puede usar el algoritmo parallel_transform para realizar la operación de asignación en paralelo y el algoritmo parallel_reduce realiza la operación de reducción en paralelo.

En el ejemplo siguiente se compara el tiempo que se tarda en calcular la suma de números primos en serie y en paralelo. La fase de asignación transforma los valores no primos en 0 y la fase de reducción 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 una operación de asignación y reducción en paralelo, vea Cómo: realizar operaciones de asignación y reducción en paralelo.

[Arriba]

Trabajo de creación de particiones

Para hacer paralela una operación en un origen de datos, uno de los pasos esenciales es particionar el origen en varias secciones a las que pueden acceder varios subprocesos al mismo tiempo. Quien realiza las particiones especifica cómo un algoritmo paralelo debería dividir los intervalos entre subprocesos. Como se explicó anteriormente en este documento, PPL usa un mecanismo de creación de particiones predeterminado que crea una carga de trabajo inicial y, a continuación, usa un algoritmo de robo de trabajo y un robo de intervalos para equilibrar estas particiones cuando las cargas de trabajo están desequilibradas. Por ejemplo, cuando una iteración de bucle completa un intervalo de iteraciones, el tiempo de ejecución redistribuye el trabajo de otros subprocesos a ese subproceso. Sin embargo, para algunos escenarios, es posible que desee especificar un mecanismo de creación de particiones diferente que sea más adecuado para su problema.

Los algoritmosparallel_for, parallel_for_eachy parallel_transform proporcionan versiones sobrecargadas que toman un parámetro adicional, _Partitioner. Este parámetro define el tipo de particionador que divide el trabajo. Estos son los tipos de quienes realizan las particiones que define PPL:

concurrency::affinity_partitioner
Divide el trabajo en un número fijo de intervalos (normalmente, el número de subprocesos de trabajo que están disponibles para trabajar en el bucle). Este tipo de particionador se parece static_partitioner, pero mejora la afinidad de caché por la forma en que asigna intervalos a subprocesos de trabajo. Este tipo de particionador puede mejorar el rendimiento cuando se ejecuta un bucle en el mismo conjunto de datos varias veces (por ejemplo, un bucle dentro de un bucle) y los datos caben en la memoria caché. Este particionador no participa completamente en la cancelación. Tampoco usa semántica de bloqueo cooperativa y, por tanto, no se puede usar con bucles paralelos que tienen una dependencia de reenvío.

concurrency::auto_partitioner
Divide el trabajo en un número inicial de intervalos (normalmente, el número de subprocesos de trabajo que están disponibles para trabajar en el bucle). El tiempo de ejecución usa este tipo de forma predeterminada cuando no se llama a un algoritmo paralelo sobrecargado que toma un _Partitioner parámetro . Cada intervalo se puede dividir en sub intervalos y, por tanto, permite que se produzca el equilibrio de carga. Cuando se completa un intervalo de trabajo, el tiempo de ejecución redistribuye los subgrupos de trabajo de otros subprocesos a ese subproceso. Use este particionador si la carga de trabajo no se encuentra en ninguna de las otras categorías o necesita soporte técnico completo 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 de fragmento especificado. Este tipo de particionador participa en el equilibrio de carga; sin embargo, el tiempo de ejecución no divide los intervalos en sub intervalos. Para cada trabajo, el tiempo de ejecución comprueba la cancelación y realiza el equilibrio de carga después de _Chunk_size iteraciones completas.

concurrency::static_partitioner
Divide el trabajo en un número fijo de intervalos (normalmente, el número de subprocesos de trabajo que están disponibles para trabajar en el bucle). Este tipo de particionador puede mejorar el rendimiento porque no usa el robo de trabajo y, por tanto, tiene menos sobrecarga. Use este tipo de particionador cuando cada iteración de un bucle paralelo realice una cantidad de trabajo fija y uniforme y no se requiera compatibilidad con la cancelación o el bloqueo cooperativo hacia delante.

Advertencia

Los algoritmos parallel_for_each y parallel_transform solo admiten contenedores que usan iteradores de acceso aleatorio (como std::vector) para los particionadores estáticos, simples y de afinidad. El uso de contenedores que usan iteradores bidireccionales y de reenvío genera un error en tiempo de compilación. El particionador predeterminado, auto_partitioner, admite los tres tipos de iterador.

Normalmente, estos particionadores se usan de la misma manera, excepto affinity_partitioner. La mayoría de los tipos de particionador no mantienen el estado y el tiempo de ejecución no los modifica. Por lo tanto, puede crear estos objetos 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 affinity_partitioner como referencia de valor l que no sea deconstpara que el algoritmo pueda almacenar el estado de los bucles futuros que se reutilizarán. En el ejemplo siguiente se muestra una aplicación básica que realiza la misma operación en un conjunto de datos en paralelo varias veces. El uso de affinity_partitioner puede mejorar el rendimiento porque es probable que la matriz quepa en la memoria 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);
    }
}

Precaución

Tenga cuidado al modificar el código existente que se basa en la semántica de bloqueo cooperativa para usar static_partitioner o affinity_partitioner. Estos tipos de particionador no usan el equilibrio de carga ni el robo de intervalos y, por tanto, pueden modificar el comportamiento de la aplicación.

La mejor manera de determinar si usar un particionador en un escenario determinado es experimentar y medir cuánto tiempo tardan las operaciones en completarse con cargas representativas y configuraciones de equipo. Por ejemplo, el particionamiento estático podría proporcionar un aumento significativo de la velocidad en un equipo de varios núcleos que tenga solo unos pocos núcleos, pero podría dar como resultado una ralentización de los equipos que tienen relativamente muchos núcleos.

[Arriba]

Ordenación en paralelo

PPL proporciona tres algoritmos de ordenación: concurrency::p arallel_sort, concurrency::p arallel_buffered_sort, y concurrency::p arallel_radixsort. Estos algoritmos de ordenación son útiles cuando tiene un conjunto de datos que puede beneficiarse de la ordenación en paralelo. En concreto, la ordenación en paralelo es útil cuando se tiene un conjunto de datos grande o cuando se usa una operación de comparación costosa por cálculo para ordenar los datos. Cada uno de estos algoritmos ordena los elementos en su lugar.

Los algoritmos parallel_sort y parallel_buffered_sort son algoritmos basados en la comparación. Es decir, comparan elementos por valor. El algoritmoparallel_sort no tiene requisitos de memoria adicionales y es adecuado para la ordenación de uso general. El algoritmo parallel_buffered_sort puede tener un mejor rendimiento que parallel_sort, pero requiere espacio O(N).

El algoritmo parallel_radixsort está basado en síntesis del mensaje. Es decir, usa claves enteras para ordenar los elementos. Mediante el uso de claves, este algoritmo puede calcular directamente el destino de un elemento en lugar de usar comparaciones. Tal como parallel_buffered_sort, este algoritmo requiere espacio O(N).

En 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 del tiempo	Acceso de iterador
parallel_sort	Ordenación basada en comparación de uso general.	Basado en comparación (ascendente)	Inestable	Ninguno	O((N/P)log(N/P) + 2N((P-1)/P))	Aleatorio
parallel_buffered_sort	Ordenación basada en comparación de uso general más rápida que requiere espacio O(N).	Basado en comparación (ascendente)	Inestable	Requiere espacio O(N) adicional	O((N/P)log(N))	Aleatorio
parallel_radixsort	Ordenación basada en claves enteras que requiere espacio O(N).	Basado en hash	Stable	Requiere espacio O(N) adicional	O(N/P)	Aleatorio

En la ilustración siguiente se muestran las propiedades importantes de los tres algoritmos de ordenación paralelos de forma más gráfica.

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 Runtime de simultaneidad, vea Cancelando algoritmos paralelos yControl de excepciones.

Sugerencia

Estos algoritmos de ordenación en paralelo admiten la semántica de movimiento. Puede definir un operador de asignación de movimiento para permitir que las operaciones de intercambio se produzcan de forma más eficaz. Para obtener más información sobre la semántica de movimiento y el operador de asignación de movimiento, vea Rvalue Reference Declarator: && y Move Constructores y Operadores de asignación de movimiento (C++). Si no proporciona un operador de asignación de movimiento o una función de intercambio, los algoritmos de ordenación usan el constructor de copia.

En el ejemplo básico siguiente se muestra cómo usar parallel_sort para ordenar un vector de int valores. De forma predeterminada, parallel_sort usa 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
*/

En este ejemplo se muestra cómo proporcionar una función de comparación personalizada. Usa el método std::complex::real para ordenar std::complex<valores dobles> 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)
*/

En este ejemplo se muestra cómo proporcionar una función hash al algoritmo parallel_radixsort. En este ejemplo se ordenan los puntos 3D. Los puntos se ordenan en función de su distancia desde 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
*/

A modo de ilustración, en este ejemplo se usa un conjunto de datos relativamente pequeño. Puede aumentar el tamaño inicial del vector para experimentar con mejoras de rendimiento en conjuntos de datos más grandes.

En este ejemplo se usa una expresión lambda como función hash. También puede usar una de las implementaciones integradas de std::clase hash o definir su propia especialización. También puede usar un objeto de función hash personalizado, 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 ser convertible al tipo size_t.

Elección de un algoritmo de ordenación

En muchos casos, parallel_sort proporciona el mejor equilibrio de velocidad y rendimiento de memoria. Sin embargo, a medida que 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 pueden funcionar mejor. La mejor manera de determinar qué algoritmo de ordenación usar en un escenario determinado es experimentar y medir cuánto tiempo se tarda en ordenar los datos típicos en configuraciones de equipo representativas. Tenga en cuenta las siguientes directrices al elegir una estrategia de ordenación.

• El tamaño de su conjunto de datos. En este documento, un conjunto de datospequeño contiene menos de 1000 elementos, un conjunto de datosmedianocontiene entre 10 000 y 100 000 elementos y un conjunto de datos grande contiene más de 100 000 elementos.

• Cantidad de trabajo que realiza la función de comparación o la función hash.

• Cantidad de recursos informáticos disponibles.

• Características del conjunto de datos. Por ejemplo, un algoritmo podría tener un buen rendimiento para los datos que ya están casi ordenados, pero no para los datos que están completamente ordenados.

• Tamaño del fragmento. El argumento _Chunk_size especifica cuándo el algoritmo cambia de una implementación paralela a una implementación de ordenación en serie, ya que subdivide la ordenación general en unidades de trabajo más pequeñas. Por ejemplo, si proporciona 512, el algoritmo cambia a implementación en serie cuando una unidad de trabajo contiene 512 o menos elementos. Una implementación en serie puede mejorar el rendimiento general porque elimina la sobrecarga necesaria para procesar los datos en paralelo.

Puede que no valga la pena ordenar un pequeño conjunto de datos en paralelo, incluso cuando tiene un gran número de recursos informáticos disponibles o la función de comparación o la función hash realizan una cantidad de trabajo relativamente grande. Puede usar la funciónstd::sort para ordenar conjuntos de datos pequeños. (parallel_sort y parallel_buffered_sort llamar a sort cuando se especifica un tamaño de fragmento mayor que el conjunto de datos; sin embargo, parallel_buffered_sort tendría que asignar espacio O(N), lo que podría tardar más tiempo debido a la contención de bloqueos o la asignación de memoria).

Si debe conservar memoria o el asignador de memoria está sujeto a contención de bloqueo, use parallel_sort para ordenar un conjunto de datos de tamaño medio. parallel_sort no requiere espacio adicional; los demás algoritmos requieren espacio O(N).

Use parallel_buffered_sort para ordenar conjuntos de datos de tamaño medio y cuando la aplicación cumpla el requisito de espacio O(N) adicional. parallel_buffered_sort puede ser especialmente útil cuando tiene un gran número de recursos informáticos o una función de comparación o función hash costosa.

Use parallel_radixsort para ordenar grandes conjuntos de datos y cuando la aplicación cumpla el requisito de espacio O(N) adicional. parallel_radixsort puede ser especialmente útil cuando la operación de comparación equivalente es más costosa o cuando ambas operaciones son costosas.

Precaución

La implementación de una buena función hash requiere que conozca el intervalo del conjunto de datos y cómo se transforma cada elemento del conjunto de datos en un valor sin signo correspondiente. Dado que la operación hash funciona en valores sin signo, considere una estrategia de ordenación diferente si no se pueden generar valores hash sin signo.

En el ejemplo siguiente se compara el rendimiento de sort, parallel_sort, parallel_buffered_sorty 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 es aceptable asignar espacio O(N) durante la ordenación, parallel_radixsort funciona mejor en este conjunto de datos en esta configuración del equipo.

[Arriba]

Temas relacionados

Title	Descripción
Procedimiento para escribir un bucle parallel_for	Muestra cómo usar el algoritmo parallel_for para realizar la multiplicación de matrices.
Procedimiento para escribir un bucle parallel_for_each	Muestra cómo usar el algoritmo parallel_for_each para calcular el recuento de números primos en un objeto std::array en paralelo.
Procedimiento para 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.
Procedimiento para 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.
Procedimiento para realizar operaciones de asignación y reducción en paralelo	Muestra cómo usar los algoritmos parallel_transform y parallel_reduce para realizar una operación de asignación y reducción que cuenta las repeticiones de palabras en los archivos.
Biblioteca de modelos de procesamiento paralelo (PPL)	Describe la biblioteca de patrones de procesamiento paralelo (PPL) la cual proporciona un modelo de programación imperativo que favorece la escalabilidad y facilidad de uso para desarrollar aplicaciones simultáneas.
Cancelación en la biblioteca PPL	Explica el rol de cancelación en PPL, cómo cancelar el trabajo paralelo y cómo determinar cuándo se cancela un grupo de tareas.
Control de excepciones	Explica el rol del control de excepciones en el Runtime de simultaneidad.

Referencia

función parallel_for

función parallel_for_each

función parallel_invoke

affinity_partitioner (clase)

auto_partitioner (clase)

simple_partitioner (clase)

static_partitioner (clase)

Función parallel_sort

función parallel_buffered_sort

función parallel_radixsort