Algoritmos paralelos

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

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

Seções

• O algoritmo parallel_for

• O algoritmo parallel_for_each

• O algoritmo parallel_invoke

• Os algoritmos parallel_transform e parallel_reduce

  • O algoritmo parallel_transform

  • O algoritmo parallel_reduce

  • Exemplo: Executando mapear e reduzir em paralelo

• Trabalho de particionamento

• Classificação paralela

  • Escolhendo um algoritmo de classificação

O algoritmo parallel_for

O algoritmo concurrency::p arallel_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 algoritmo parallel_for particiona tarefas de maneira ideal para a execução paralela. Ele usa um algoritmo de roubo de trabalho e um intervalo de roubo para equilibrar essas partições quando as cargas de trabalho estão desequilibrados. Quando uma iteração de loop bloqueia cooperativamente, o runtime redistribui o intervalo de iterações atribuídas ao thread atual para outros threads ou processadores. Da mesma forma, quando um thread conclui um intervalo de iterações, o runtime redistribui o trabalho de outros threads para esse thread. O algoritmo parallel_for também dá suporte ao paralelismo aninhado. Quando um loop paralelo contém outro loop paralelo, o runtime coordena o processamento de recursos entre os corpos de loop de forma eficiente para execução paralela.

O algoritmo parallel_for 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, um objeto de função ou ponteiro de função). A segunda versão usa um valor inicial, um valor final, um valor pelo qual a etapa e uma função de trabalho. A primeira versão dessa função usa 1 como o valor da etapa. As versões restantes levam objetos particionadores, que permitem especificar como parallel_for deve particionar intervalos entre threads. Os particionadores são explicados com mais detalhes na seção Trabalho de Particionamento neste documento.

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

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

• O algoritmo parallel_for não dá suporte a condições arbitrárias de término. O algoritmo parallel_for para quando o valor atual da variável de iteração é um a menos que last.

• O parâmetro _Index_type de tipo deve ser um tipo integral. Esse tipo integral pode ser assinado ou não assinado.

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

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

Embora o algoritmo parallel_for não dê suporte a condições arbitrárias de encerramento, você pode usar o cancelamento para interromper todas as tarefas. Para saber mais sobre cancelamento, confira Cancelamento no PPL.

Observação

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

Exemplo

O exemplo a seguir mostra a estrutura básica do algoritmo parallel_for. 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 gera a seguinte saída de amostra:

1 2 4 3 5

Como o algoritmo parallel_for atua em cada item em paralelo, a ordem na qual os valores são impressos no console variará.

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

[Parte superior]

O algoritmo parallel_for_each

O algoritmo concurrency::p arallel_for_each executa tarefas em um contêiner iterativo, como as fornecidas pela Biblioteca Padrão do C++, em paralelo. Ele usa a mesma lógica de particionamento que o algoritmo parallel_for utiliza.

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

Embora o algoritmo parallel_for_each funcione em iteradores de encaminhamento e iteradores de acesso aleatório, ele tem um desempenho melhor com iteradores de acesso aleatório.

Exemplo

O exemplo a seguir mostra a estrutura básica do algoritmo parallel_for_each. 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 gera a seguinte saída de amostra:

4 5 1 2 3

Como o algoritmo parallel_for_each atua em cada item em paralelo, a ordem na qual os valores são impressos no console variará.

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

[Parte superior]

O algoritmo parallel_invoke

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

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

Assim 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 algoritmo parallel_invoke se relaciona com tarefas e grupos de tarefas.

Exemplo

O exemplo a seguir mostra a estrutura básica do algoritmo parallel_invoke. Esse exemplo chama simultaneamente a função twice 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;
}

Esse exemplo gera a saída a seguir:

108 11.2 HelloHello

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

[Parte superior]

Os algoritmos parallel_transform e parallel_reduce

Os algoritmos concurrency::p arallel_transform e concurrency::p arallel_reduce são versões paralelas dos algoritmos da Biblioteca Padrão C++ std::transform e std::accumulate, respectivamente. As versões do Runtime de simultaneidade se comportam como as versões da Biblioteca Padrão do C++, exceto que a ordem de operação não é determinada porque são executadas em paralelo. Use esses algoritmos quando você trabalha com um conjunto grande o suficiente para obter benefícios de desempenho e escalabilidade de serem processados em paralelo.

Importante

Os algoritmos parallel_transform e parallel_reduce dão suporte apenas a iteradores de acesso aleatório, bidirecional e de encaminhamento porque esses iteradores produzem endereços de memória estáveis. Além disso, esses iteradores devem produzir valores l diferentes de const.

O algoritmo parallel_transform

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

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

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

• Executar o rastreamento de raios 3D, em que 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 algoritmo parallel_transform. Este exemplo nega cada elemento de um objeto std::vector 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>());
}

Aviso

Esse exemplo mostra o uso básico de parallel_transform: Como a função de trabalho não executa uma quantidade significativa de trabalho, um aumento significativo no desempenho não é esperado neste exemplo.

O algoritmo parallel_transform tem duas sobrecargas. A primeira sobrecarga usa 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 usa 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 completamente o iterador de entrada ou não se sobrepor completamente. O comportamento desse algoritmo não será especificado se os iteradores de entrada e saída se sobrepõem parcialmente.

O algoritmo parallel_reduce

O algoritmo parallel_reduce é útil quando você tem uma sequência de operações que satisfaz a propriedade associativa. (Esse 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.

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

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

O exemplo básico a seguir mostra como usar o algoritmo parallel_reduce para combinar uma sequência de cadeias de caracteres em uma cadeia de caracteres. Assim como nos exemplos de parallel_transform, os ganhos de desempenho não são esperados 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 em parallel_reduce como abreviação para o uso do algoritmo parallel_for_each junto com a classe concurrency::combinable.

Exemplo: Executando mapear e reduzir 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 std::transform e std::accumulate da Biblioteca Padrão do C++ para executar operações de mapa e redução. No entanto, para muitos problemas, você pode usar o algoritmo parallel_transform para executar a operação de mapa em paralelo e o algoritmo parallel_reduce para executar a operação de redução em paralelo.

O exemplo a seguir compara o tempo necessário para calcular a soma de números primos em série e em paralelo. A fase do mapa transforma 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 consultar outro exemplo que executa uma operação de mapa e de redução em paralelo, confira Como executar operações de mapa e redução em paralelo.

[Parte superior]

Trabalho de particionamento

Para paralelizar a uma operação em uma fonte de dados, uma etapa essencial é particionar a fonte em várias seções que possam 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 desbalanceadas. Por exemplo, quando uma interação de loop conclui um intervalo de iterações, o runtime redistribui o trabalho de outros threads para esse thread. No entanto, para alguns cenários, talvez você queira especificar um mecanismo de particionamento diferente mais adequado ao seu problema.

Os algoritmos parallel_for, parallel_for_each e parallel_transformfornecem versões sobrecarregadas que levam um parâmetro adicional, _Partitioner Esse parâmetro define o tipo de partição que divide o trabalho. Aqui estão os tipos de particionadores que o PPL define:

concurrency::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 partição é semelhante a static_partitioner, mas melhora a afinidade de cache pela maneira como mapeia intervalos para threads de trabalho. 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 se ajustam no cache. Esse particionador não participa totalmente do 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.

concurrency::auto_partitioner
Divide o trabalho em um número inicial de intervalos (normalmente o número de threads de trabalho disponíveis para trabalhar no loop). O runtime usa esse tipo por padrão quando você não chama um algoritmo paralelo sobrecarregado que usa um parâmetro _Partitioner. Cada intervalo pode ser dividido em sub-intervalos e, portanto, permite que o balanceamento de carga ocorra. Quando um intervalo de trabalho é concluído, o runtime redistribui sub intervalos de trabalho de outros threads para esse thread. Use esse particionador se sua carga de trabalho não se enquadrar em uma das outras categorias ou você precisar de suporte total para cancelamento ou bloqueio cooperativo.

concurrency::simple_partitioner
Divide o trabalho em intervalos de modo que cada intervalo tenha pelo menos o número de iterações especificadas pelo tamanho da parte fornecida. Esse tipo de partição participa do balanceamento de carga; no entanto, o runtime não divide intervalos em subintervalos. Para cada trabalho, o runtime verifica o cancelamento e executa o balanceamento de carga depois que as iterações de _Chunk_size são concluídas.

concurrency::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). Esse tipo de particionador pode melhorar o desempenho porque ele não usa roubo de trabalho e, portanto, tem menos sobrecarga. Use esse tipo de particionador quando cada iteração de um loop paralelo executar uma quantidade fixa e uniforme de trabalho e você não precisar de suporte para cancelamento ou bloqueio cooperativo de encaminhamento.

Aviso

Os algoritmos parallel_for_each e parallel_transform dão suporte somente a contêineres que usam iteradores de acesso aleatório (como std::vector) para os particionadores estáticos, simples e de afinidade. O uso de contêineres que usam iteradores bidirecionais e de encaminhamento produz um erro em tempo de compilação. O particionador padrão auto_partitioner dá suporte a todos os três tipos de iterador.

Normalmente, esses particionadores são usados da mesma maneira, exceto affinity_partitioner. A maioria dos tipos de partição não mantém o estado e não são modificados pelo runtime. 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 objeto affinity_partitioner como uma referência de valor l diferente de const para que o algoritmo possa armazenar o estado para loops futuros serem reutilizados. 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 a matriz provavelmente se ajustará ao 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);
    }
}

Cuidado

Tenha cuidado ao modificar o código existente que depende da semântica de bloqueio cooperativa 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 aplicativo.

A melhor maneira de determinar se é preciso usar um particionador em qualquer cenário específico é testar e medir o tempo necessário para concluir operações em cargas representativas e configurações de computador. Por exemplo, o particionamento estático pode fornecer um aumento de velocidade significativo em um computador com vários núcleos que tenha apenas alguns núcleos, mas pode resultar em lentidão em computadores que têm relativamente muitos núcleos.

[Parte superior]

Classificação paralela

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

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

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

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

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

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

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

Dica

Esses algoritmos de classificação paralela dão suporte à semântica de movimentação. Você pode definir um operador de atribuição de movimentação para permitir que as operações de troca ocorram com mais eficiência. Para obter mais informações sobre a semântica de movimentação e o operador de atribuição de movimentação, consulte Rvalue Reference Declarator: &&, e Mover construtores e mover operadores de atribuição (C++). Se você não fornecer um operador de atribuição de movimentação ou uma função de troca, os algoritmos de classificação usarão o construtor de cópia.

O exemplo básico a seguir mostra como usar parallel_sort para classificar um vector de valores 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
*/

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

Esse exemplo mostra como fornecer uma função de hash para o algoritmo parallel_radixsort. Esse exemplo classifica pontos 3D. Os pontos são classificados com base em 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, esse 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.

Esse exemplo usa uma expressão lambda como a função de 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 nesse 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). Esse tipo integral deve ser conversível para o tipo size_t.

Escolhendo um algoritmo de classificação

Em muitos casos, parallel_sort fornece o melhor equilíbrio entre 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 sua função de comparação, parallel_buffered_sort ou parallel_radixsort pode ter um desempenho melhor. A melhor forma de determinar qual algoritmo de classificação usar em qualquer cenário é experimentar e medir o tempo necessário para classificar dados típicos em configurações computacionais representativas. Tenha em mente as diretrizes a seguir 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 sua função de comparação ou função de hash executa.

• A quantidade de recursos de computação disponíveis.

• As características do 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 completamente não classificados.

• O tamanho da parte. O argumento _Chunk_size opcional especifica quando o algoritmo alterna de um paralelo para uma implementação de classificação serial, pois ele subdivide a classificação geral em unidades menores de trabalho. Por exemplo, se você fornecer 512, o algoritmo mudará para a implementação serial quando uma unidade de trabalho contiver 512 elementos ou menos. Uma implementação serial pode melhorar o desempenho geral, pois 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 uma grande quantidade de recursos de computação disponíveis ou sua função de comparação ou função de hash executa uma quantidade relativamente grande de trabalho. Você pode usar a função std::sort para classificar conjuntos de dados pequenos. (parallel_sort e parallel_buffered_sort chamam sort quando você especifica um tamanho de bloco maior que o conjunto de dados; no entanto, parallel_buffered_sort precisa alocar espaço O(N), o que poderia levar mais tempo devido à contenção de bloqueio ou alocação de memória.)

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

Use parallel_buffered_sort para classificar conjuntos de dados de médio porte e quando seu aplicativo atender ao requisito de espaço O(N) adicional. parallel_buffered_sort pode ser especialmente útil quando você tem um grande número de recursos de computação ou uma função de comparação cara ou função de hash.

Use parallel_radixsort para classificar conjuntos de dados grandes e quando seu aplicativo atender 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.

Cuidado

Implementar 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 valores de hash não assinados não puderem ser produzidos.

O exemplo a seguir compara o desempenho de sort, parallel_sort, parallel_buffered_sort e parallel_radixsort em relação ao mesmo conjunto grande 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.
*/

Nesse exemplo, que pressupõe que é aceitável alocar espaço O(N) durante a classificação, parallel_radixsort executa o melhor nesse conjunto de dados nessa configuração do computador.

[Parte superior]

Tópicos Relacionados

Título	Descrição
Como escrever um loop parallel_for	Mostra como usar o algoritmo parallel_for para executar multiplicação de matriz.
Como gravar um loop parallel_for_each	Mostra como usar o algoritmo parallel_for_each 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 em paralelo	Mostra como usar o algoritmo parallel_invoke para melhorar o desempenho do algoritmo de classificação bitônica.
Como usar Parallel.Invoke para executar operações em paralelo	Mostra como usar o algoritmo parallel_invoke para melhorar o desempenho de um programa que executa várias operações em uma fonte de dados compartilhada.
Como realizar operações de mapa e redução em paralelo	Mostra como usar algoritmos parallel_transform 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 a escalabilidade e a facilidade de uso para o desenvolvimento de aplicativos simultâneos.
Cancelamento no PPL	Explica a função de cancelamento no PPL, como cancelar o trabalho paralelo e como determinar quando um grupo de tarefas é cancelado.
Tratamento de exceção	Explica a função de tratamento de exceção no Runtime de simultaneidade.

Referência

Função parallel_for

Função parallel_for_each

Função parallel_invoke

Classe affinity_partitioner

Classe auto_partitioner

Classe simple_partitioner

Classe static_partitioner

Função parallel_sort

Função parallel_buffered_sort

Função parallel_radixsort