Partilhar via

Algoritmos paralelos

A Biblioteca de Padrões Paralelos (PPL) fornece algoritmos que executam simultaneamente trabalho em coleções de dados. Esses algoritmos se assemelham aos fornecidos pela Biblioteca Padrão C++.

Os algoritmos paralelos são compostos a partir da funcionalidade existente no Concurrency Runtime. Por exemplo, o algoritmo concurrency::p arallel_for usa um objeto concurrency::structured_task_group para executar as iterações de loop paralelo. As parallel_for partições de algoritmo funcionam de forma ótima, dado o número disponível de recursos de computação.

Secções

O algoritmo parallel_for

O algoritmo concurrency::parallel_for executa repetidamente a mesma tarefa em paralelo. Cada uma dessas tarefas é parametrizada por um valor de iteração. Esse algoritmo é útil quando você tem um corpo de loop que não compartilha recursos entre iterações desse loop.

O parallel_for algoritmo particiona tarefas de uma maneira ideal para execução paralela. Ele usa um algoritmo de roubo de trabalho e roubo de intervalo para equilibrar essas partições quando as cargas de trabalho estão desequilibradas. Quando uma iteração de loop bloqueia cooperativamente, o tempo de execução redistribui o intervalo de iterações atribuído ao thread atual para outros threads ou processadores. Da mesma forma, quando um thread conclui um intervalo de iterações, o tempo de execução redistribui o trabalho de outros threads para esse thread. O parallel_for algoritmo também suporta paralelismo aninhado. Quando um loop paralelo contém outro loop paralelo, o tempo de execução coordena os recursos de processamento entre os corpos do loop de forma eficiente para execução paralela.

O parallel_for algoritmo tem várias versões sobrecarregadas. A primeira versão usa um valor inicial, um valor final e uma função de trabalho (uma expressão lambda, objeto de função ou ponteiro de função). A segunda versão usa um valor inicial, um valor final, um valor de incremento e uma função de trabalho. A primeira versão desta função usa 1 como o valor da etapa. As versões restantes usam objetos de partição, que permitem especificar como parallel_for deve particionar intervalos entre as threads. Os particionadores são explicados com mais detalhes na seção Trabalho de particionamento neste documento.

Você pode converter muitos for loops para utilizar parallel_for. No entanto, o parallel_for algoritmo difere da for instrução das seguintes maneiras:

  • O parallel_for algoritmo parallel_for não executa as tarefas em uma ordem pré-determinada.

  • O parallel_for algoritmo não suporta condições de terminação arbitrárias. O parallel_for algoritmo pára quando o valor atual da variável de iteração é um valor a menos do que last.

  • O _Index_type parâmetro type deve ser um tipo integral. Este tipo de variável integral pode ser do tipo assinado ou não assinado.

  • A iteração do loop deve ser para diante. O parallel_for algoritmo lança uma exceção do tipo std::invalid_argument se o _Step parâmetro for menor que 1.

  • O mecanismo de tratamento de exceções para o parallel_for algoritmo difere do de um for loop. Se várias exceções ocorrerem simultaneamente em um corpo de loop paralelo, o tempo de execução propagará apenas uma das exceções para o thread chamado parallel_for. Além disso, quando uma iteração de loop lança uma exceção, o tempo de execução não interrompe imediatamente o loop geral. Em vez disso, o loop é colocado no estado cancelado e o tempo de execução descarta todas as tarefas que ainda não foram iniciadas. Para obter mais informações sobre manipulação de exceções e algoritmos paralelos, consulte Tratamento de exceções.

Embora o parallel_for algoritmo não ofereça suporte a condições de terminação arbitrárias, você pode usar o cancelamento para interromper todas as tarefas. Para obter mais informações sobre cancelamento, consulte Cancelamento no PPL.

Observação

O custo de agendamento resultante do balanceamento de carga e do suporte para funcionalidades como cancelamento pode não superar os benefícios de executar o corpo do loop em paralelo, particularmente quando o corpo do loop é relativamente pequeno. Você pode minimizar essa sobrecarga usando um particionador em seu loop paralelo. Para obter mais informações, consulte a seção Particionamento de Trabalho mais adiante neste documento.

Exemplo

O exemplo a seguir mostra a estrutura básica do parallel_for algoritmo. Este exemplo imprime no console cada valor no intervalo [1, 5] em 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 exemplo produz a seguinte saída:

1 2 4 3 5

Como o parallel_for algoritmo atua em cada item em paralelo, a ordem em que os valores são impressos no console varia.

Para obter um exemplo completo que usa o parallel_for algoritmo, consulte Como escrever um loop de parallel_for.

[Topo]

O algoritmo parallel_for_each

O algoritmo concurrency::parallel_for_each executa tarefas em um contentor iterativo, como os fornecidos pela Biblioteca Padrão do C++, de forma paralela. Ele usa a mesma lógica de particionamento que o parallel_for algoritmo usa.

O parallel_for_each algoritmo se assemelha ao algoritmo std::for_each da Biblioteca Padrão C++, exceto que o parallel_for_each algoritmo executa as tarefas simultaneamente. Como outros algoritmos paralelos, parallel_for_each não executa as tarefas em uma ordem específica.

Embora o parallel_for_each algoritmo funcione com iteradores bidirecionais e iteradores de acesso aleatório, ele funciona melhor com iteradores de acesso aleatório.

Exemplo

O exemplo a seguir mostra a estrutura básica do parallel_for_each algoritmo. Este exemplo imprime no console cada valor em um objeto std::array em 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 exemplo produz a seguinte saída:

4 5 1 2 3

Como o parallel_for_each algoritmo atua em cada item em paralelo, a ordem em que os valores são impressos no console varia.

Para obter um exemplo completo que usa o parallel_for_each algoritmo, consulte Como escrever um loop de parallel_for_each.

[Topo]

O algoritmo parallel_invoke

O algoritmo concurrency::parallel_invoke executa um conjunto de tarefas em paralelo. Ele não retorna até que cada tarefa termine. Esse algoritmo é útil quando você tem várias tarefas independentes que deseja executar ao mesmo tempo.

O parallel_invoke algoritmo toma como parâmetros uma série de funções de trabalho (funções lambda, objetos de função ou ponteiros de função). O parallel_invoke algoritmo é sobrecarregado para tomar entre dois e dez parâmetros. Cada função que você passa para parallel_invoke deve ter zero parâmetros.

Como outros algoritmos paralelos, parallel_invoke não executa as tarefas em uma ordem específica. O tópico Paralelismo de tarefas explica como o parallel_invoke algoritmo se relaciona com tarefas e grupos de tarefas.

Exemplo

O exemplo a seguir mostra a estrutura básica do parallel_invoke algoritmo. Este exemplo chama simultaneamente a twice função em três variáveis locais e imprime o resultado no console.

// 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 exemplo produz a seguinte saída:

108 11.2 HelloHello

Para obter exemplos completos que usam o parallel_invoke algoritmo, consulte Como usar parallel_invoke para escrever uma rotina de classificação paralela e Como usar parallel_invoke para executar operações paralelas.

[Topo]

Os algoritmos parallel_transform e parallel_reduce

Os algoritmos concurrency::parallel_transform e concurrency::parallel_reduce são versões paralelas dos algoritmos da Biblioteca Padrão C++ std::transform e std::accumulate, respectivamente. As versões do Concurrency Runtime se comportam como as versões da biblioteca padrão do C++, exceto que a ordem da operação não é determinada porque são executadas em paralelo. Use esses algoritmos quando trabalhar com um conjunto grande o suficiente para obter benefícios de desempenho e escalabilidade ao ser processado em paralelo.

Importante

Os algoritmos parallel_transform e parallel_reduce suportam apenas iteradores de acesso aleatório, bidireccionais e de avanço porque esses iteradores produzem endereços de memória estáveis. Além disso, esses iteradores devem produzir valores não-lconst .

O algoritmo parallel_transform

Você pode usar o parallel transform algoritmo para executar muitas operações de paralelização de dados. Por exemplo, você pode:

  • Ajuste o brilho de uma imagem e execute outras operações de processamento de imagem.

  • Somar ou pegar o produto ponto entre dois vetores e executar outros cálculos numéricos em vetores.

  • Execute o ray tracing 3D, onde cada iteração se refere a um pixel que deve ser renderizado.

O exemplo a seguir mostra a estrutura básica usada para chamar o parallel_transform algoritmo. Este exemplo nega cada elemento de um objeto std::vetor de duas maneiras. A primeira maneira usa uma expressão lambda. A segunda maneira 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>());
}

Advertência

Este exemplo demonstra o uso básico do parallel_transform. Como a função de trabalho não executa uma quantidade significativa de trabalho, não se espera um aumento significativo no desempenho neste exemplo.

O parallel_transform algoritmo tem duas sobrecargas. A primeira sobrecarga leva um intervalo de entrada e uma função unária. A função unária pode ser uma expressão lambda que usa um argumento, um objeto de função ou um tipo que deriva de unary_function. A segunda sobrecarga aceita dois intervalos de entrada e uma função binária. A função binária pode ser uma expressão lambda que usa dois argumentos, um objeto de função ou um tipo que deriva de std::binary_function. O exemplo a seguir ilustra essas diferenças.

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

O iterador que você fornece para a saída de parallel_transform deve sobrepor-se completamente ao iterador de entrada ou não se sobrepor de modo algum. O comportamento deste algoritmo não é especificado se os iteradores de entrada e saída se sobrepõem parcialmente.

O algoritmo parallel_reduce

O parallel_reduce algoritmo é útil quando você tem uma sequência de operações que satisfazem a propriedade associativa. (Este algoritmo não requer a propriedade comutativa.) Aqui estão algumas das operações que você pode executar com parallel_reduce:

  • Multiplique sequências de matrizes para produzir uma matriz.

  • Multiplique um vetor por uma sequência de matrizes para produzir um vetor.

  • Calcule o comprimento de uma sequência de cadeias de caracteres.

  • Combine uma lista de elementos, como cadeias de caracteres, em um único elemento.

O exemplo básico a seguir mostra como usar o parallel_reduce algoritmo para combinar uma sequência de cadeias de caracteres em uma cadeia de caracteres. Tal como acontece com os exemplos para parallel_transform, não são esperados ganhos de desempenho neste exemplo 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.
*/

Em muitos casos, você pode pensar parallel_reduce como uma abreviação para o uso do parallel_for_each algoritmo juntamente com a classe concurrency::combinable .

Exemplo: Executando mapeamento e redução em paralelo

Uma operação de mapa aplica uma função a cada valor em uma sequência. Uma operação de redução combina os elementos de uma sequência em um valor. Você pode usar as funções C++ Standard Library std::transform e std::accumulate para executar operações de mapeamento e redução. No entanto, para muitos problemas, você pode usar o parallel_transform algoritmo para executar a operação de mapa em paralelo e o parallel_reduce algoritmo executar a operação de redução em paralelo.

O exemplo a seguir compara o tempo que leva para calcular a soma dos números primos em série e em paralelo. A fase do mapa transforma os valores não primos em 0 e a fase de redução soma os 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 outro exemplo que executa um mapa e reduz a operação em paralelo, consulte Como executar o mapa e reduzir operações em paralelo.

[Topo]

Divisão do Trabalho

Para paralelizar uma operação em uma fonte de dados, uma etapa essencial é particionar a fonte em várias seções que podem ser acessadas simultaneamente por vários threads. Um particionador especifica como um algoritmo paralelo deve particionar intervalos entre threads. Conforme explicado anteriormente neste documento, o PPL usa um mecanismo de particionamento padrão que cria uma carga de trabalho inicial e, em seguida, usa um algoritmo de roubo de trabalho e roubo de intervalo para equilibrar essas partições quando as cargas de trabalho estão desequilibradas. Por exemplo, quando uma iteração de loop completa um intervalo de iterações, o tempo de execução redistribui o trabalho de outros threads para esse thread. No entanto, para alguns cenários, convém especificar um mecanismo de particionamento diferente que seja mais adequado ao seu problema.

Os algoritmos parallel_for, parallel_for_each e parallel_transform fornecem versões sobrecarregadas que utilizam um parâmetro adicional, _Partitioner. Este parâmetro define o tipo de particionador que divide o trabalho. Aqui estão os tipos de particionadores que o PPL define:

concorrência::affinity_partitioner
Divide o trabalho em um número fixo de intervalos (normalmente o número de threads de trabalho disponíveis para trabalhar no loop). Esse tipo de particionador assemelha-se a static_partitioner, mas melhora a afinidade de cache pela maneira como mapeia intervalos para threads de execução. Esse tipo de particionador pode melhorar o desempenho quando um loop é executado no mesmo conjunto de dados várias vezes (como um loop dentro de um loop) e os dados cabem no cache. Este particionador não participa plenamente no processo de cancelamento. Ele também não usa semântica de bloqueio cooperativo e, portanto, não pode ser usado com loops paralelos que têm uma dependência de encaminhamento.

concorrência::auto_partitioner
Divide o trabalho em um número inicial de intervalos (normalmente o número de threads de trabalho que estão disponíveis para trabalhar no loop). O tempo de execução usa esse tipo por padrão quando você não chama um algoritmo paralelo sobrecarregado que usa um _Partitioner parâmetro. Cada intervalo pode ser dividido em subintervalos e, assim, permite que o balanceamento de carga ocorra. Quando uma gama de tarefas é concluída, o sistema de execução redistribui subgamas de tarefas de outros threads para esse thread. Use este particionador se sua carga de trabalho não se enquadrar em uma das outras categorias ou se você precisar de suporte total para cancelamento ou bloqueio cooperativo.

concorrência::simple_partitioner
Divide o trabalho em intervalos de forma que cada intervalo tenha pelo menos o número de iterações especificadas pelo tamanho de bloco determinado. Este tipo de particionador participa no balanceamento de carga; no entanto, o tempo de execução não divide intervalos em subintervalos. Para cada trabalhador, o tempo de execução verifica se há cancelamento e executa o balanceamento de carga após _Chunk_size a conclusão das iterações.

concorrência::static_partitioner
Divide o trabalho em um número fixo de intervalos (normalmente o número de threads de trabalho disponíveis para trabalhar no loop). Este tipo de particionador pode melhorar o desempenho porque não usa roubo de trabalho e, portanto, tem menos sobrecarga. Use este tipo de particionador quando cada iteração de um loop paralelo executa uma quantidade fixa e uniforme de trabalho e não necessita de suporte para cancelamento ou bloqueio cooperativo progressivo.

Advertência

Os parallel_for_each algoritmos e parallel_transform suportam apenas contêineres que usam iteradores de acesso aleatório (como std::vetor) para os particionadores estáticos, simples e de afinidade. O uso de contentores que usam iteradores bidirecionais e em avanço produz um erro de compilação. O particionador padrão, auto_partitioner, suporta todos esses três tipos de iterador.

Normalmente, esses particionadores são usados da mesma maneira, exceto para affinity_partitioner. A maioria dos tipos de particionador não mantém o estado e não são modificados pelo tempo de execução. Portanto, você pode criar esses objetos particionadores no site de chamada, conforme mostrado no exemplo a seguir.

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

No entanto, você deve passar um affinity_partitioner objeto como uma referência l-value, não const para que o algoritmo possa armazenar o estado e reutilizá-lo em loops futuros. O exemplo a seguir mostra um aplicativo básico que executa a mesma operação em um conjunto de dados em paralelo várias vezes. O uso de affinity_partitioner pode melhorar o desempenho porque é provável que o array caiba no cache.

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

Atenção

Tenha cuidado ao modificar o código existente que depende da semântica de bloqueio cooperativo para usar static_partitioner ou affinity_partitioner. Esses tipos de particionador não usam balanceamento de carga ou roubo de intervalo e, portanto, podem alterar o comportamento do seu aplicativo.

A melhor maneira de determinar se um particionador deve ser usado em qualquer cenário é experimentar e medir quanto tempo as operações levam para serem concluídas sob cargas representativas e configurações de computador. Por exemplo, o particionamento estático pode fornecer uma aceleração significativa em um computador multi-core que tem apenas alguns núcleos, mas pode resultar em lentidão em computadores que têm relativamente muitos núcleos.

[Topo]

Classificação paralela

O PPL fornece três algoritmos de classificação: concurrency::parallel_sort, concurrency::parallel_buffered_sort e concurrency::parallel_radixsort. Esses algoritmos de classificação são úteis quando você tem um conjunto de dados que pode se beneficiar de ser classificado em paralelo. Em particular, a classificação em paralelo é útil quando você tem um grande conjunto de dados ou quando usa uma operação de comparação computacionalmente cara para classificar seus dados. Cada um desses algoritmos ordena os elementos localmente.

Os algoritmos parallel_sort e parallel_buffered_sort são ambos algoritmos baseados em comparação. Ou seja, comparam elementos por valor. O parallel_sort algoritmo não tem requisitos de memória adicionais e é adequado para classificação de uso geral. O parallel_buffered_sort algoritmo pode ter um desempenho melhor do que parallel_sort, mas requer espaço O(N).

O parallel_radixsort algoritmo é baseado em hash. Ou seja, ele usa chaves inteiras para classificar elementos. Usando chaves, esse algoritmo pode calcular diretamente o destino de um elemento em vez de usar comparações. Como parallel_buffered_sort, este algoritmo requer espaço O(N).

A tabela a seguir resume as propriedades importantes dos três algoritmos de classificação paralela.

Algoritmo Descrição Mecanismo de classificação Estabilidade de classificação Requisitos de memória Complexidade de tempo Acesso ao iterador
parallel_sort Classificação de uso geral baseada em comparação. Baseado em comparação (ascendente) Instável Nenhum O((N/P)log(N/P) + 2N((P-1)/P)) Aleatório
parallel_buffered_sort Classificação baseada em comparação de uso geral mais rápida que requer espaço O(N). Baseado em comparação (ascendente) Instável Requer espaço O(N) adicional O((N/P)log(N)) Aleatório
parallel_radixsort Classificação baseada em chave inteira que requer espaço O(N). Baseado em hash Estável Requer espaço O(N) adicional O(N/P) Aleatório

A ilustração a seguir mostra as propriedades importantes dos três algoritmos de classificação paralela mais graficamente.

Comparação dos algoritmos de classificação.

Esses algoritmos de classificação paralela seguem as regras de cancelamento e tratamento de exceções. Para obter mais informações sobre cancelamento e tratamento de exceções no Concurrency Runtime, consulte Cancelando algoritmos paralelos e tratamento de exceções.

Sugestão

Esses algoritmos de classificação paralela suportam semântica de movimento. Você pode definir um operador de atribuição de movimentação para permitir que as operações de permuta ocorram com mais eficiência. Para obter mais informações sobre semântica de movimentação e o operador de atribuição de movimento, consulte Rvalue Reference Declarator: &&, e Move Constructors and Move Assignment Operators (C++). Se não fornecer um operador de atribuição de movimento ou uma função de troca, os algoritmos de ordenação usarão o construtor de cópia.

O exemplo básico a seguir mostra como usar parallel_sort para classificar um vector dos int valores. Por padrão, 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
*/

Este exemplo mostra como fornecer uma função de comparação personalizada. Ele usa o método std::complex::real para classificar valores std::complex<double> em ordem crescente.

// 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 exemplo mostra como fornecer uma função de hash para o parallel_radixsort algoritmo. Este exemplo classifica pontos 3D. Os pontos são ordenados com base na sua distância de um ponto de referência.

// 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
*/

Para ilustração, este exemplo usa um conjunto de dados relativamente pequeno. Você pode aumentar o tamanho inicial do vetor para experimentar melhorias de desempenho em conjuntos maiores de dados.

Este exemplo usa uma expressão lambda como a função hash. Você também pode usar uma das implementações internas da classe std::hash ou definir sua própria especialização. Você também pode usar um objeto de função hash personalizado, conforme mostrado neste exemplo:

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

A função hash deve retornar um tipo integral (std::is_integral::value deve ser true). Este tipo integral deve ser convertível em tipo size_t.

Escolhendo um algoritmo de classificação

Em muitos casos, parallel_sort fornece o melhor equilíbrio de velocidade e desempenho de memória. No entanto, à medida que você aumenta o tamanho do conjunto de dados, o número de processadores disponíveis ou a complexidade da função de comparação parallel_buffered_sort ou parallel_radixsort pode ter um desempenho melhor. A melhor maneira de determinar qual algoritmo de classificação usar em qualquer cenário é experimentar e medir quanto tempo leva para classificar dados típicos em configurações representativas do computador. Tenha em mente as seguintes diretrizes ao escolher uma estratégia de classificação.

  • O tamanho do seu conjunto de dados. Neste documento, um conjunto de dados pequeno contém menos de 1.000 elementos, um conjunto de dados médio contém entre 10.000 e 100.000 elementos e um conjunto de dados grande contém mais de 100.000 elementos.

  • A quantidade de trabalho que a sua função de comparação ou de hash executa.

  • A quantidade de recursos computacionais disponíveis.

  • As características do seu conjunto de dados. Por exemplo, um algoritmo pode ter um bom desempenho para dados que já estão quase classificados, mas não tão bem para dados que não estão completamente classificados.

  • O tamanho do pedaço. O argumento opcional _Chunk_size especifica quando o algoritmo muda de uma implementação de classificação paralela para uma implementação de classificação serial, pois subdivide a classificação geral em unidades menores de trabalho. Por exemplo, se você fornecer 512, o algoritmo alternará para implementação serial quando uma unidade de trabalho contiver 512 ou menos elementos. Uma implementação serial pode melhorar o desempenho geral porque elimina a sobrecarga necessária para processar dados em paralelo.

Pode não valer a pena classificar um pequeno conjunto de dados em paralelo, mesmo quando você tem um grande número de recursos de computação disponíveis ou sua função de comparação ou função hash executa uma quantidade relativamente grande de trabalho. Você pode usar a função std::sort para classificar pequenos conjuntos de dados. parallel_sort e parallel_buffered_sort chamam sort quando especificares um tamanho de pedaço maior do que o conjunto de dados; no entanto, parallel_buffered_sort teria que alocar espaço proporcional a O(N), o que poderia consumir tempo adicional devido à contenção de bloqueio ou à alocação de memória.

Se precisar conservar memória ou se o alocador de memória estiver sujeito a contenção de bloqueios, use parallel_sort para classificar um conjunto de dados de tamanho médio. parallel_sort não requer espaço adicional; os outros algoritmos requerem espaço O(N).

Use parallel_buffered_sort para classificar conjuntos de dados de tamanho médio e quando seu aplicativo atende ao requisito de espaço O(N) adicional. parallel_buffered_sort pode ser especialmente útil quando se tem um grande número de recursos de computação ou funções de comparação ou de hash caras.

Use parallel_radixsort para classificar grandes conjuntos de dados e quando seu aplicativo atende ao requisito de espaço O(N) adicional. parallel_radixsort pode ser especialmente útil quando a operação de comparação equivalente é mais cara ou quando ambas as operações são caras.

Atenção

A implementação de uma boa função de hash requer que você conheça o intervalo do conjunto de dados e como cada elemento no conjunto de dados é transformado em um valor não assinado correspondente. Como a operação de hash funciona em valores não assinados, considere uma estratégia de classificação diferente se os valores de hash não assinados não puderem ser produzidos.

O exemplo a seguir compara o desempenho de sort, parallel_sort, parallel_buffered_sorte parallel_radixsort com o mesmo grande conjunto de dados aleatórios.

// 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.
*/

Neste exemplo, que pressupõe que é aceitável alocar espaço O(N) durante a classificação, parallel_radixsort apresenta o melhor desempenho neste conjunto de dados nesta configuração desta máquina.

[Topo]

Título Descrição
Como Escrever um Loop parallel_for Mostra como usar o algoritmo para executar a parallel_for multiplicação de matrizes.
Como escrever um loop parallel_for_each Mostra como usar o parallel_for_each algoritmo para calcular a contagem de números primos em um objeto std::array em paralelo.
Como: Usar parallel_invoke para escrever uma rotina de classificação paralela Mostra como usar o parallel_invoke algoritmo para melhorar o desempenho do algoritmo de classificação bitônica.
Como: Usar parallel_invoke para executar operações paralelas Mostra como usar o parallel_invoke algoritmo para melhorar o desempenho de um programa que executa várias operações em uma fonte de dados compartilhada.
Como realizar operações de Map e Reduce em paralelo Mostra como usar os parallel_transform algoritmos e parallel_reduce para executar um mapa e reduzir a operação que conta as ocorrências de palavras em arquivos.
Biblioteca de Padrões Paralelos (PPL) Descreve o PPL, que fornece um modelo de programação imperativo que promove escalabilidade e facilidade de uso para o desenvolvimento de aplicativos simultâneos.
Cancelamento no PPL Explica a função do cancelamento no PPL, como cancelar o trabalho paralelo e como determinar quando um grupo de tarefas é cancelado.
Tratamento de exceções Explica a função do tratamento de exceções no Concurrency Runtime.

Referência

Função parallel_for

Função parallel_for_each

Função parallel_invoke

affinity_partitioner Classe

auto_partitioner Classe

simple_partitioner Classe

static_partitioner Classe

Função parallel_sort

Função parallel_buffered_sort

Função parallel_radixsort

  • Last updated on