Algoritmos paralelos

Artigo
02/25/2013

A biblioteca (PPL) dos padrões de paralela fornece os algoritmos executados simultaneamente o trabalho em coleções de dados.Esses algoritmos se parecem com aqueles fornecidos pela biblioteca padrão (STL) do modelo.

Os algoritmos paralelos são compostos de funcionalidade existente em tempo de execução de simultaneidade.Por exemplo, o algoritmo de concurrency::parallel_for usa um objeto de concurrency::structured_task_group para executar as iterações paralelas do loop.O particiona algoritmo de parallel_for funcionam em um meio ideal dado o número disponível de recursos de computação.

Seções

O algoritmo de parallel_for
O algoritmo de parallel_for_each
O algoritmo de parallel_invoke
Os algoritmos de parallel_transform e de parallel_reduce
- O algoritmo de parallel_transform
- O algoritmo de parallel_reduce
- Exemplo: Executando o mapa e reduz paralelamente
Particionando o trabalho
Classificação paralela
- Escolhendo um algoritmo de classificação

O algoritmo de parallel_for

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

O algoritmo de parallel_for dividir tarefas na melhor maneira para execução paralela.Algoritmo usa um e um intervalo de ser roubada que roubar para equilibrar quando esses particiona o carrega de trabalho são desequilibradas.Quando uma iteração do loop bloqueia cooperativa, o tempo de execução redistribui o intervalo de iterações que é atribuído ao segmento atual para outros segmentos ou processadores.Da mesma forma, quando um segmento termina um intervalo de iterações, o tempo de execução redistribui o trabalho de outros segmentos para aquele segmento.O algoritmo de parallel_for também suporta o paralelismo aninhado.Quando um loop paralelo contém outro loop paralelo, o tempo de execução coordena processamento entre os recursos do corpo de loop de uma maneira eficiente para a execução paralela.

O algoritmo de parallel_for tem várias versões sobrecarregadas.A primeira versão tem um valor inicial, um valor final, e uma função de trabalho (uma expressão lambda, um objeto de função, ou um ponteiro de função).A segunda versão tem um valor inicial, um valor final, um valor por que para depuração, e uma função de trabalho.A primeira versão dessa função usa 1 como o valor da etapa.As versões outros usam os objetos de partitioner, que permitem você especificar como parallel_for deve dividir intervalos entre segmentos.Partitioners é explicado em detalhes na seção Particionando o trabalho neste documento.

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

O algoritmo parallel_for de parallel_for não executa as tarefas em uma ordem predeterminado.
O algoritmo de parallel_for não suporta arbitrárias condições de finalização.O algoritmo de parallel_for para quando o valor atual da variável de iteração é um menor que _Last.
O parâmetro do tipo de _Index_type deve ser um tipo integral.Este tipo integral pode ser assinado ou sem sinal.
A iteração do loop deve ser direta.O algoritmo de parallel_for gera uma exceção do tipo std::invalid_argument se o parâmetro de _Step é menor que 1.
O mecanismo de manipulação de exceção para o algoritmo de parallel_for difere do de um loop de for .Se várias exceções ocorrem simultaneamente em um corpo de loop paralelo, o tempo de execução propaga apenas uma das exceções no thread que chamou parallel_for.Além disso, quando uma iteração do loop lança uma exceção, o tempo de execução não imediatamente para o loop total.Em vez disso, o loop é colocado no estado cancelado e o tempo de execução descarta todas as tarefas que ainda não começarem.Para obter mais informações sobre manipulação de exceção e os algoritmos paralelos, consulte Manipulação de exceção em tempo de execução de concorrência.

Embora o algoritmo de parallel_for não oferece suporte condições arbitrárias de fim, você pode usar o botão para parar todas as tarefas.Para obter mais informações sobre o botão, consulte Cancelar o PPL.

Observação
Programação custou que os resultados de balanceamento de carga e suporte para recursos como cancelamento não podem superar os benefícios de executar o corpo de loop paralelamente, especialmente quando o corpo de loop é relativamente pequeno.Você pode minimizar essa sobrecarga usando um partitioner em seu loop paralelo.Para obter mais informações, consulte Particionando o trabalho posteriormente neste documento.

Programação custou que os resultados de balanceamento de carga e suporte para recursos como cancelamento não podem superar os benefícios de executar o corpo de loop paralelamente, especialmente quando o corpo de loop é relativamente pequeno.Você pode minimizar essa sobrecarga usando um partitioner em seu loop paralelo.Para obter mais informações, consulte Particionando o trabalho posteriormente neste documento.

Exemplo

O exemplo a seguir mostra a estrutura básica do algoritmo de parallel_for .Este exemplo imprime no console cada valor no intervalo 1, 5 [] paralelamente.

// 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 de exemplo:

Porque o algoritmo de parallel_for atua em cada item paralelamente, a ordem em que os valores são variações impresso no console.

Para um exemplo completo que usa o algoritmo de parallel_for , consulte Como: Escreva um loop de parallel_for.

Superior[]

O algoritmo de parallel_for_each

O algoritmo de concurrency::parallel_for_each executa tarefas em um contêiner iterativo, como aqueles fornecidos pelo STL, paralelamente.Usa a mesma lógica do particionamento que o algoritmo de parallel_for usa.

O algoritmo de parallel_for_each lembra o algoritmo de STL std::for_each , exceto que o algoritmo de parallel_for_each executa as tarefas simultaneamente.Como outros algoritmos paralelos, parallel_for_each não executa as tarefas em uma ordem específica.

Embora o algoritmo de parallel_for_each funciona em ambos encaminhar iteradores de acesso aleatório e iteradores, executa melhor com iteradores de acesso aleatório.

Exemplo

O exemplo a seguir mostra a estrutura básica do algoritmo de parallel_for_each .Este exemplo imprime no console cada valor em um objeto de std::array paralelamente.

// 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), begin(values), [](int value) {
      wstringstream ss;
      ss << value << L' ';
      wcout << ss.str();
   });
}

Este exemplo produz a seguinte saída de exemplo:

Porque o algoritmo de parallel_for_each atua em cada item paralelamente, a ordem em que os valores são variações impresso no console.

Para um exemplo completo que usa o algoritmo de parallel_for_each , consulte Como: Escreva um loop de parallel_for_each.

Superior[]

O algoritmo de parallel_invoke

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

O algoritmo de parallel_invoke utiliza como seus parâmetros um fx-series de funções de trabalho (funções lambda, objetos de função, ou ponteiros de função).O algoritmo de parallel_invoke está sobrecarregado para receber e dez entre dois parâmetros.Cada função que você passa a parallel_invoke deve tomar os parâmetros zero.

Como outros algoritmos paralelos, parallel_invoke não executa as tarefas em uma ordem específica.O tópico Paralelismo de tarefa (tempo de execução de simultaneidade) explica como o algoritmo de parallel_invoke se relaciona as tarefas e grupos de trabalho.

Exemplo

O exemplo a seguir mostra a estrutura básica do algoritmo de parallel_invoke .Este exemplo chama simultaneamente a função de 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 produz a seguinte saída.

Para os exemplos completos que usam o algoritmo de parallel_invoke , consulte Como: Use o parallel_invoke para gravar uma rotina paralela de tipo e Como: use o parallel_invoke para executar operações paralelas.

Superior[]

Os algoritmos de parallel_transform e de parallel_reduce

Os algoritmos de concurrency::parallel_transform e de concurrency::parallel_reduce são versões paralelas de algoritmos std::transform e std::accumulatede STL, respectivamente.As versões de tempo de execução de simultaneidade se comportam como as versões de STL exceto que a ordem de operação não é determinado porque executam paralelamente.Use os algoritmos quando você trabalha com um conjunto que é grande o suficiente para atingir o desempenho e escalabilidade tire proveito de ser processado paralelamente.

Importante
Os algoritmos de parallel_transform e de parallel_reduce suportam apenas de acesso aleatório, bidirecional, e encaminham iteradores porque esses iteradores geram endereços de memória estável.Além disso, esses iteradores devem gerar l- não valores deconst .

O algoritmo de parallel_transform

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

Ajuste o brilho de uma imagem, e realizar outras operações de processamento de imagem.
Some ou recebe o produto de ponto entre dois vetores, e executar outros cálculos numéricos em vetores.
Execute o rastreamento de raio 3d, onde cada iteração se refere a um pixel que deve ser renderizado.

O exemplo a seguir mostra a estrutura básica que é usada para chamar o algoritmo de parallel_transform .Este exemplo nega cada elemento de um objeto de 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>());
}

Cuidado
Este exemplo demonstra o uso mais 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 de parallel_transform tem duas sobrecargas.A primeira sobrecarga toma um intervalo conectado e uma função unário.A função unário pode ser uma expressão lambda que recebe um argumento, um objeto de função, ou um tipo que deriva de unary_function.A segunda sobrecarga aceita dois intervalos conectados e uma função binário.A função binário pode ser uma expressão lambda que leva 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 sobrepostos de todo.O comportamento desse algoritmo é especificado não se iteradores de entrada e saída sobrepostos parcialmente.

O algoritmo de parallel_reduce

O algoritmo de parallel_reduce é útil quando você tiver uma sequência das operações que satisfazem 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:

Multiplica sequências de matrizes para produzir uma matriz.
Multiplica um vetor por uma sequência de matrizes para gerar um vetor.
Calcular o comprimento de uma sequência de cadeias de caracteres.
Combinar uma lista de elementos, como cadeias de caracteres, em um elemento.

O seguinte exemplo básicas mostra como usar o algoritmo de parallel_reduce para combinar uma sequência de cadeias de caracteres em uma cadeia de caracteres.Como com exemplos para parallel_transform, os ganhos de desempenho não deverão nesse 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;
    words.push_back(L"Lorem ");
    words.push_back(L"ipsum ");
    words.push_back(L"dolor ");
    words.push_back(L"sit ");
    words.push_back(L"amet, ");
    words.push_back(L"consectetur ");
    words.push_back(L"adipiscing ");
    words.push_back(L"elit.");

    // Reduce the vector to one string in parallel.
    wcout << parallel_reduce(begin(words), end(words), wstring()) << endl;
}

/* Output:
   Lorem ipsum dolor sit amet, consectetur adipiscing elit.
*/

Em muitos casos, você pode pensar em parallel_reduce como taquigrafia para o uso do algoritmo de parallel_for_each juntamente com a classe de concurrency::combinable .

Exemplo: Executando o mapa e reduz paralelamente

Uma operação de mapa aplica uma função para 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 classes de padrão (STL) std::transform std::accumulate de biblioteca de modelo para executar o mapa e reduzir operações.No entanto, para muitos problemas, você pode usar o algoritmo de parallel_transform para executar paralelamente a operação de mapa e o algoritmo de parallel_reduce executar a operação de redução paralelamente.

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

Superior[]

Particionando o trabalho

Para parallelize uma operação em uma fonte de dados, uma etapa é essencial dividir a origem em várias seções que podem ser acessados simultaneamente por vários segmentos.Um partitioner especifica como um algoritmo paralelo deve dividir intervalos entre segmentos.Conforme explicado anteriormente neste documento, o PPL usa um mecanismo padrão do particionamento que cria uma carga de trabalho inicial e use um algoritmo e um intervalo de ser roubada que roubar para equilibrar quando esses particiona o carrega de trabalho são desequilibradas.Por exemplo, quando uma iteração do loop concluir um intervalo de iterações, o tempo de execução redistribui o trabalho de outros segmentos para aquele segmento.No entanto, para alguns cenários, você pode desejar especificar um mecanismo diferente do particionamento que é a melhor opção para seu problema.

parallel_for, parallel_for_each, e os algoritmos de parallel_transform fornecem as versões sobrecarregadas que têm um parâmetro adicional, _Partitioner.Este parâmetro define o tipo de partitioner que divide o trabalho.Aqui estão os tipos de partitioners que o define PPL:

concurrency::affinity_partitioner
Divide de trabalho em um número fixo de intervalos (normalmente o número de segmentos de trabalho que estão disponíveis para trabalhar no loop).Esse tipo de partitioner é semelhante a static_partitioner, mas melhora-se afinidade do cache a relação que mapeia a extensão para segmentos de trabalho.Esse tipo de partitioner 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 ajustes de dados no cache.Este partitioner totalmente não participa no botão.Também não usa a semântica cooperativa de bloqueio e não pode ser usado como uma conseqüência com loops paralelos que têm uma dependência de avanço.
concurrency::auto_partitioner
Divide trabalham em um número inicial de intervalos (normalmente o número de segmentos 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 recebe um parâmetro de _Partitioner .Cada intervalo pode ser dividido em intervalos subelemento, e permite assim o balanceamento de carga para ocorrer.Quando um intervalo de trabalho for concluída, o tempo de execução redistribui subelemento intervalos de trabalho de outros segmentos para aquele segmento.Use este partitioner se sua carga de trabalho não se encaixa em uma das outras categorias ou precisar de suporte completo para o cancelamento ou o bloqueio cooperativo.
concurrency::simple_partitioner
Divide trabalham em intervalos de modo que cada intervalo tem pelo menos o número de iterações que são especificadas por determinado tamanho da parte.Esse tipo de partitioner participa no balanceamento de carga; no entanto, o tempo de execução não divide em intervalos subelemento intervalos.Para cada trabalhador, o runtime verifica o botão e executa o balanceamento de carga depois que as iterações de _Chunk_size concluírem.
concurrency::static_partitioner
Divide de trabalho em um número fixo de intervalos (normalmente o número de segmentos de trabalho que estão disponíveis para trabalhar no loop).Esse tipo de partitioner pode melhorar o desempenho porque o não usa apenas ser roubada e tem como consequência menos sobrecarga.Use esse tipo de partitioner quando cada iteração de um loop paralelo executa uma quantidade de trabalho fixa e uniforme e não requer o suporte de para o cancelamento ou não encaminha o bloqueio cooperativo.

Cuidado
Os algoritmos de parallel_for_each e de parallel_transform suportam somente contêiners que usam iteradores de acesso aleatório (como std::vector) para o estático simples, e os partitioners afinidade de.O uso de contêiners que usam iteradores bidirecionais e dianteiros gera um erro de tempo de compilação.O partitioner padrão, auto_partitioner, suporta todos os três tipos de iterador.

Os algoritmos de parallel_for_each e de parallel_transform suportam somente contêiners que usam iteradores de acesso aleatório (como std::vector) para o estático simples, e os partitioners afinidade de.O uso de contêiners que usam iteradores bidirecionais e dianteiros gera um erro de tempo de compilação.O partitioner padrão, auto_partitioner, suporta todos os três tipos de iterador.

Normalmente, esses partitioners são utilizados da mesma forma, exceto para affinity_partitioner.A maioria dos tipos de partitioner não mantém o estado e não são modificados em tempo de execução.Como consequência você pode criar esses objetos de partitioner no site de chamada, conforme mostrado no exemplo o 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 comoconst, não referência de affinity_partitioner de l- valor de modo que o algoritmo pode armazenar o estado para que os loops futuros reutilizem.O exemplo a seguir mostra um aplicativo básico que executa a mesma operação em um dataset paralelamente várias vezes.O uso de affinity_partitioner pode melhorar o desempenho porque a matriz é provável caber no cache.

// affinity-partitioner.cpp
// compile with: /EHsc
#include <ppl.h>
#include <array>

using namespace concurrency;

int wmain()
{    
    // Create an arry 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
Use cuidados quando você altera o código existente que depende da semântica cooperativa de bloqueio para usar static_partitioner ou affinity_partitioner.Esses tipos de partitioner não usam o balanceamento de carga ou não variem roubar como consequência, e podem alterar o comportamento do aplicativo.

A melhor maneira de determinar se usar um partitioner em qualquer situação é determinado testar e medir quanto demora para concluir operações em e carrega configurações do computador representativas.Por exemplo, o particionamento estático pode fornecer a aceleração significativa em um computador de vários principal que tem apenas alguns núcleos, mas pode resultar diminuições em computadores que têm relativamente muitos núcleos.

Superior[]

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 paralelamente.Em particular, classificar paralelamente é útil quando você tiver um grande conjunto de dados ou quando você usa um computacional- caro compara a operação para classificar os dados.Cada um desses elementos do tipo dos algoritmos no lugar.

Os algoritmos de parallel_sort e de parallel_buffered_sort são ambos os algoritmos comparar- base.Isto é, comparam os elementos por valor.O algoritmo de parallel_sort não tem requisitos de memória adicional, e é apropriado para classificação de uso geral.O algoritmo de parallel_buffered_sort pode executar melhor do que parallel_sort, mas requer o espaço de O(N) .

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

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

Algoritmo	Descrição	Mecanismo de classificação	Estabilidade de tipo	Requisitos de memória	Complexidade de tempo	Acesso de iterador
parallel_sort	Comparar- tipo base de uso geral.	Comparar- base () ascensão	Instável	Nenhum	O((N/P)log(N/P) + 2N((P-1)/P))	Aleatório
parallel_buffered_sort	Comparar- tipo base de uso geral mais rápido que requer O () No espaço.	Comparar- base () ascensão	Instável	Requer o espaço extra de O(N)	O((N/P)log(N))	Aleatório
parallel_radixsort	Tipo chave com base inteiro que requer O () No espaço.	Baseado em hash	Estável	Requer o espaço extra de O(N)	O(N/P)	Aleatório

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

Comparação dos algoritmos de classificação

Esses algoritmos de classificação paralelos seguem as regras de manipulação de exceção e cancelar.Para obter mais informações sobre manipulação de cancelamento e de exceção em tempo de execução de concorrência, consulte Cancelando algoritmos paralelos e Manipulação de exceção em tempo de execução de concorrência.

Dica
Paralela semântica de movimentação de suporte desses algoritmos de classificação.Você pode definir um operador de atribuição de animação para ativar operações de troca para ocorrer com mais eficiência.Para obter mais informações sobre a semântica de animação e de operador de atribuição de animação, consulte Declarador de referência Rvalue: & &, e Como: gravar um construtor de movimentação.Se você não fornecer uma função de operador de atribuição ou de troca de animação, os algoritmos de classificação usam o construtor de impressão.

Paralela semântica de movimentação de suporte desses algoritmos de classificação.Você pode definir um operador de atribuição de animação para ativar operações de troca para ocorrer com mais eficiência.Para obter mais informações sobre a semântica de animação e de operador de atribuição de animação, consulte Declarador de referência Rvalue: & &, e Como: gravar um construtor de movimentação.Se você não fornecer uma função de operador de atribuição ou de troca de animação, os algoritmos de classificação usam o construtor de impressão.

O seguinte exemplo mostra como usar parallel_sort básico para classificar vector de valores de int .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 um personalizado compara a função.Usa o método de std::complex::real valores de std::complex<double> para classificar 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 um função de hash para o algoritmo de parallel_radixsort .Este exemplo classe pontos 3d.Os pontos são classificados com base na 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 a ilustração, este exemplo usa um dataset relativamente pequeno.Você pode aumentar o tamanho inicial do vetor para experimentar as melhorias de desempenho sobre conjuntos de dados maiores.

Este exemplo usa uma expressão lambda como a função de hash.Você também pode usar uma das implementações internas da classe de std::hash ou definir sua própria especialização.Você também pode usar um objeto personalizado de função de hash, 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 de hash deve retornar um tipo integral (std::is_integral::value deve ser true).Este tipo integral deve ser conversível digite size_t.

Escolhendo um algoritmo de classificação

Em muitos casos, parallel_sort fornece melhor saldo de desempenho da velocidade e de memória.No entanto, como o aumentar o tamanho do seu dataset, o número de processadores disponíveis, ou a complexidade do seu compare a função, o parallel_buffered_sort ou o parallel_radixsort pode executar melhor.A melhor maneira de determinar que algoritmo de classificação usar em qualquer situação é determinado testar e medir quanto demora para classificar dados típicos em configurações do computador representativas.Manter as seguintes diretrizes em mente quando você escolhe uma estratégia de classificação.

O tamanho do dataset.Neste documento, um dataset pequeno contém menos de 1.000 elementos, um dataset contém médio entre 10.000 e 100.000 elementos, e um grande conjunto de dados contém mais de 100.000 elementos.
A quantidade de trabalho que seu compare a função ou a função de hash é executado.
A quantidade de recursos de computação disponíveis.
As características do dataset.Por exemplo, um algoritmo pode executar bem para os dados que já são classificados quase além disso, mas não para dados que não são completamente escolhidos.
O tamanho da parte.O argumento opcional de _Chunk_size especifica quando as opções do algoritmo de uma paralela a uma implementação serial do tipo como o tipo subdivide total em unidades secundárias de trabalho.Por exemplo, se você fornecer 512, as opções do algoritmo da implementação serial quando uma unidade de trabalho contém 512 ou menos aos elementos.Uma implementação serial pode melhorar o desempenho geral como elimina a sobrecarga que é necessária para processar paralelamente dados.

Não pode ser valor de classificação paralelamente um dataset pequeno, mesmo quando você tiver um grande número de recursos de computação disponíveis ou sua para comparar a função ou a função de hash executa relativamente uma grande quantidade de trabalho.Você pode usar a função de std::sort para classificar datasets pequenos.(parallel_sort e parallel_buffered_sort chamam sort quando você especificar um tamanho da parte que é maior do que o conjunto de dados; no entanto, parallel_buffered_sort precisará atribuir o espaço de O(N) , que poderia levar tempo adicionais devido à conflito ou a alocação de memória de bloqueio.)

Se você deve conservar memória ou o distribuidor de memória é sujeita a conflito de bloqueio, use parallel_sort para classificar um conjunto de dados de tamanho médio.parallel_sort não requer nenhum espaço extra; os algoritmos outros requerem o espaço de O(N) .

Use parallel_buffered_sort para classificar dataset de tamanho médio e quando seu aplicativo cumprir o requisito de espaço extra de O(N) .parallel_buffered_sort pode ser especialmente útil quando você tiver um grande número de recursos de computação ou um grande comparar a função ou a função de hash.

Use parallel_radixsort para classificar grandes datasets e quando seu aplicativo cumprir o requisito de espaço extra de O(N) .parallel_radixsort pode ser especialmente útil quando o equivalente compara a operação é mais grande ou quando ambas as operações são custosas.

Cuidado
Implementar uma boa função de hash requer que você souber o intervalo de datasets e como cada elemento no conjunto de dados é convertido para um valor sem sinal correspondente.Porque a operação de hash funciona em valores sem sinal, considere uma estratégia diferente de classificação se os valores de hash não assinados não podem ser gerados.

O exemplo a seguir compara o desempenho de sort, de parallel_sort, de parallel_buffered_sort, e de parallel_radixsort contra o 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 assume que é aceitável atribuir o espaço de O(N) durante o tipo, parallel_radixsort executa melhor neste conjunto de dados nesta configuração do computador.

Superior[]

Tópicos relacionados

Nome	Descrição
Como: Escreva um loop de parallel_for	Mostra como usar o algoritmo de parallel_for para executar multiplicação da matriz.
Como: Escreva um loop de parallel_for_each	Mostra como usar o algoritmo de parallel_for_each para calcular paralelamente a contagem de números primos em um objeto de std::array .
Como: Use o parallel_invoke para gravar uma rotina paralela de tipo	Mostra como usar o algoritmo de parallel_invoke para melhorar o desempenho do algoritmo de tipo bitonic.
Como: use o parallel_invoke para executar operações paralelas	Mostra como usar o algoritmo de parallel_invoke para melhorar o desempenho de um programa que executa várias operações em uma fonte de dados compartilhado.
Como: executar o mapa e reduzir as operações em paralelo	Mostra como usar os algoritmos de parallel_transform e de parallel_reduce para executar um mapa e para reduzir a operação que conta as ocorrências da palavra em arquivos.
A modelos paralela a biblioteca (PPL)	Descreve o PPL, que fornece um modelo imperativo de programação que promova a escalabilidade e acessibilidade para desenvolver aplicativos simultâneas.
Cancelar o PPL	Explica a função cancelar o PPL, como cancelar o trabalho paralelo, e como determinar quando um grupo de trabalho é cancelado.
Manipulação de exceção em tempo de execução de concorrência	Explica a função de manipulação de exceção em tempo de execução de simultaneidade.