Algoritmos paralelos
A biblioteca (PPL) de padrões de paralelo fornece algoritmos que são executados simultaneamente o trabalho em coleções de dados. Esses algoritmos lembram a aqueles fornecidos pela biblioteca padrão (STL) do modelo.
Os algoritmos paralelos são compostos da 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. As partições do algoritmo de parallel_for funcionam em uma ótima maneira disponível para o número de recursos de computação.
Seções
O Algoritmo parallel_for
O Algoritmo parallel_for_each
O Algoritmo parallel_for_each
Os Algoritmos parallel_transform e parallel_reduce
O Algoritmo parallel_transform
O Algoritmo parallel_reduce
Exemplo: Realizando Mapeamento e Redução em Paralelo
Particionando Trabalho
Classificação Paralela
- Escolhendo um Algoritmo de Classificação
O Algoritmo parallel_for
O algoritmo de concurrency::parallel_for executa repetidamente a mesma tarefa em paralelo. Cada uma dessas tarefas é parametrizada por um valor da iteração. Esse algoritmo é útil quando você tem um corpo de loop que não compartilha recursos entre iterações do loop.
O algoritmo de parallel_for divide tarefas de forma a melhor para a execução paralela. Usa um algoritmo e um intervalo de rob que roubam para balancear essas partições quando as cargas de trabalho são desbalanceadas. Quando uma iteração do loop bloqueia cooperativa, o tempo de execução redistribui o intervalo das iterações que é atribuído ao thread atual para outros threads ou processadores. Da mesma forma, quando um thread termina um intervalo das iterações, o tempo de execução são roteadas novamente o trabalho de outros threads a esse thread. 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 os recursos de processamento entre os corpos de loop de maneira efetiva para execução paralela.
O algoritmo de parallel_for tem várias versões sobrecarregadas. A primeira versão usa um valor de início, um valor final, e uma função de trabalho (uma expressão de lambda, um objeto de função, ou um ponteiro de função). A segunda versão usa um valor de início, um valor final, um valor pelo qual passar por exemplo, uma função de trabalho. A primeira versão desta função usará 1 como o valor da etapa. As outras versões têm os objetos de partitioner, o que permite especificar como parallel_for deve particionar intervalos entre threads. Partitioners é explicado em mais detalhes na seção Dividindo o trabalho neste documento.
Você pode converter muitos loop de for para usar parallel_for. Entretanto, o algoritmo de parallel_for difere da instrução de for das seguintes maneiras:
O algoritmo parallel_for de parallel_for não executa as tarefas em uma ordem índice.
O algoritmo de parallel_for não da suporte a condições arbitrárias de término. O algoritmo de parallel_for para quando o valor atual da variável de iteração é um menor que _Last.
O tipo de parâmetro _Index_type deve ser um tipo integral. Esse tipo integral pode ser assinado ou não assinado.
A iteração do loop deve ser encaminhada. O algoritmo de parallel_for gerará uma exceção do tipo std::invalid_argument se o parâmetro de _Step for menor que 1.
O mecanismo manipulação de exceções gerais para o algoritmo de parallel_for difere 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 ao thread que chamou parallel_for. Além disso, quando uma iteração do loop gerou uma exceção, o tempo de execução não interrompe imediatamente o loop total. Em vez disso, o loop será colocado no estado cancelado e o tempo de execução descarta todas as tarefas que ainda não sejam iniciados. Para obter mais informações sobre manipulação de exceções gerais e algoritmos paralelos, consulte Tratamento de exceções no tempo de execução de simultaneidade.
Embora o algoritmo de parallel_for não têm suporte em condições arbitrárias de término, você pode usar em cancelar para parar todas as tarefas. Para obter mais informações sobre cancelamento, consulte Cancelamento no PPL.
Dica
Programação custou que os resultados de balanceamento de carga e suporte para recursos como cancelamentos não podem ultrapassar os benefícios da execução do corpo de loop em paralelo, especialmente quando o corpo de loop for relativamente pequeno.Você pode minimizar a sobrecarga usando um partitioner no loop paralelo.Para obter mais informações, consulte Dividindo o trabalho mais adiante neste documento.
Exemplo
O exemplo a seguir mostra a estrutura básica do algoritmo de parallel_for . Este exemplo grava no console cada valor no intervalo de [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 gerencia a seguinte saída de exemplo:
Como o algoritmo de parallel_for atua em cada item em paralelo, a ordem em que os valores são impressos no console variará.
Para obter um exemplo completo que usa o algoritmo de parallel_for , consulte Como gravar um loop parallel_for.
[Superior]
O Algoritmo parallel_for_each
O algoritmo de concurrency::parallel_for_each executa tarefas em um contêiner iterativo, como a fornecida por STL, em paralelo. Usa a mesma lógica de particionamento que o algoritmo de parallel_for usa.
O algoritmo de parallel_for_each se assemelha ao algoritmo 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 funcione em ambos encaminhar iteradores e iteradores de acesso aleatório, 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 grava no console cada valor em um objeto de 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 gerencia a seguinte saída de exemplo:
Como o algoritmo de parallel_for_each atua em cada item em paralelo, a ordem em que os valores são impressos no console variará.
Para obter um exemplo completo que usa o algoritmo de parallel_for_each , consulte Como gravar um loop parallel_for_each.
[Superior]
O Algoritmo parallel_for_each
O algoritmo de concurrency::parallel_invoke executa um conjunto de tarefas em paralelo. 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 de parallel_invoke usa como seus parâmetros uma série de funções de trabalho (funções de lambda, objetos de função, ou ponteiros de função). O algoritmo de parallel_invoke é sobrecarregado para colocar entre dois parâmetros e dez. Cada função que você passa a parallel_invoke deve ter os parâmetros zero.
Como outros algoritmos paralelos, parallel_invoke não executa as tarefas em uma ordem específica. O Paralelismo de tarefa (tempo de execução de simultaneidade) tópico explica como o algoritmo de parallel_invoke se relaciona com as tarefas e os 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;
}
Este exemplo gera a seguinte saída:
Para os exemplos completo que usam o algoritmo de parallel_invoke , consulte Como usar parallel_invoke para escrever uma rotina de classificação em paralelo e Como usar parallel_invoke para executar operações em paralelo.
[Superior]
Os Algoritmos parallel_transform e parallel_reduce
Os algoritmos de concurrency::parallel_transform e de concurrency::parallel_reduce são versões paralelas dos algoritmos std::transform e std::accumulateSTL, respectivamente. As versões de tempo de execução de simultaneidade se comportam como as versões STL exceto que a ordem de operação não é determinado porque podem ser executados em paralelo. Use esses algoritmos quando você trabalha com um conjunto que seja grande o suficiente para obter o desempenho e a escalabilidade tire beneficiar de ser processado em paralelo.
Importante
Os algoritmos de parallel_transform e de parallel_reduce só dão suporte de acesso aleatório, bidirecional, e encaminham iteradores como esses iteradores gerenciem endereços de memória estáveis.Além disso, os iteradores devem gerar l- valores não deconst .
O Algoritmo 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 executar outras operações de processamento da imagem.
Some ou consulte o produto de ponto entre dois vetores, e executar outros cálculos numéricos em vetores.
Execute o rastreamento do raio 3d, onde cada iteração se refere a um pixels que deve ser renderizado.
O exemplo a seguir mostra a estrutura básica que é usada para chamar o algoritmo de parallel_transform . Esse exemplo nega cada elemento de um objeto de std::vector de duas formas. O primeiro modo usa uma expressão de lambda. O segundo modo usa std::negate, que se 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
Este exemplo demonstra 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 de parallel_transform tem duas sobrecargas. A primeira sobrecarga usa um intervalo entrada e uma função unário. A função unário pode ser uma expressão de 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ário. A função binária pode ser uma expressão de 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 fornecido para a saída de parallel_transform deve completamente sobreposição do iterador de entrada ou não se sobrepõem de todos eles.O comportamento desse algoritmo não é especificado se os iteradores de entrada e saída sobreposição parcialmente.
O Algoritmo parallel_reduce
O algoritmo de parallel_reduce é útil quando você tem uma sequência de operações que satisfazem a propriedade associativa. (Esse algoritmo não requer que a propriedade comutativa.) Aqui estão algumas das operações que você pode executar com parallel_reduce:
Multiplique sequências das matrizes para gerar uma matriz.
Multiplica um vetor por uma sequência das matrizes para gerar um vetor.
Computar o comprimento de uma sequência de cadeias de caracteres.
Combina uma lista de elementos, como cadeias de caracteres, em um elemento.
O exemplo básico mostra como usar o algoritmo de 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;
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 algoritmo de parallel_for_each junto com a classe de concurrency::combinable .
Exemplo: Realizando 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 classes padrão de std::transform (STL) std::accumulate da biblioteca do modelo para executar o mapa e reduzir as operações. No entanto, para muitos problemas, você pode usar o algoritmo de parallel_transform para ser executados em paralelo a operação de mapa e o algoritmo de parallel_reduce executa a operação de redução em paralelo.
O exemplo a seguir compara o tempo necessário para computar em série e em paralelo a soma de números à esquerda. A fase de mapa transforma valores de escolha a segunda fase 0 e a diminuiçã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 obter outro exemplo que executa um mapa e reduzir a operação em paralelo, consulte Como realizar operações de mapa e redução em paralelo.
[Superior]
Particionando 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 acessadas simultaneamente por vários threads. Um partitioner especifica como um algoritmo paralelo deve particionar intervalos entre threads. Como explicado anteriormente neste documento, o PPL usa um mecanismo padrão de particionamento que crie uma carga de trabalho inicial e então use um algoritmo e um intervalo de rob que roubam para balancear essas partições quando as cargas de trabalho são desbalanceadas. Por exemplo, quando uma iteração do loop concluir um intervalo das iterações, o tempo de execução são roteadas novamente o trabalho de outros threads a esse thread. Porém, para alguns cenários, você pode querer especificar um mecanismo diferente de particionamento que é mais adequado ao seu problema.
parallel_for, parallel_for_each, e os algoritmos de parallel_transform fornecem as versões sobrecarregadas que possuem um parâmetro adicional, _Partitioner. Esse parâmetro define o tipo de partitioner que divide o trabalho. Aqui estão os tipos de partitioners que o PPL define:
concurrency::affinity_partitioner
Trabalho de divide em um número fixo de intervalos (normalmente o número de threads de trabalho que estão disponíveis para trabalhar no loop). Esse tipo de partitioner se assemelha a static_partitioner, mas melhora-se a afinidade de cache a relação que mapeia intervalos a threads 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 não participa totalmente no cancelamento. Também não usa semântica cooperativa de bloqueio e em virtude disso não pode ser usado com loop paralelos que têm uma dependência futuras.concurrency::auto_partitioner
Divide funcionam 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 sobrecarregado paralelo que usa um parâmetro de _Partitioner . Cada intervalo pode ser dividido em subintervalos, e habilita assim o balanceamento de carga para ocorrer. Quando um intervalo de trabalho é concluído, o tempo de execução redistribui subintervalos de trabalho de outros threads a esse thread. Use este partitioner se sua carga de trabalho não estiver sob as outras categorias ou você precisar suporte completo ao cancelamento ou o bloqueio cooperativo.concurrency::simple_partitioner
Divide funcionam em intervalos de modo que cada intervalo tenha pelo menos o número de iterações que são especificadas determinado pelo tamanho da parte. Esse tipo de partitioner entra no balanceamento de carga; no entanto, o tempo de execução não particiona intervalos em subintervalos. Para cada trabalhador, o tempo de execução verifica o cancelamento e executa o balanceamento de carga depois que as iterações de _Chunk_size terminar.concurrency::static_partitioner
Trabalho de divide em um número fixo de intervalos (normalmente o número de threads de trabalho que estão disponíveis para trabalhar no loop). Esse tipo de partitioner pode melhorar o desempenho porque não usa o início rob e tem menos sobrecarga em virtude disso. Use esse tipo de partitioner quando cada iteração do loop paralelo executa uma quantidade fixa de trabalho e uniforme e não requer suporte para o cancelamento nem encaminha o bloqueio cooperativo.
Aviso
Os algoritmos de parallel_for_each e de parallel_transform oferecem suporte apenas aos contêineres que usam iteradores de acesso aleatório (como std::vector) para o estático, simples, e os partitioners de afinidade.O uso de contêiner que usam iteradores bidirecionais e dianteiros gerencie um erro de tempo de compilação.O partitioner padrão, auto_partitioner, o oferece suporte a todos os três desses tipos de iterador.
Normalmente, esses partitioners são usados da mesma forma, com exceção de affinity_partitioner. A maioria dos tipos de partitioner não flexível mantêm o estado e não são modificados em tempo de execução. Em virtude disso você pode criar esses objetos de partitioner no site da 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());
}
Porém, você deve passar um objeto comoconstnão, referência de affinity_partitioner de l- valor de forma que o algoritmo possa armazenar o estado para que o loop futuros reutilizem. 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 é provável que se ajustar 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);
}
}
Aviso
Tome cuidado quando você altera o código existente que confia na semântica cooperativa de bloqueio para usar static_partitioner ou affinity_partitioner.Esses tipos de partitioner não usam o balanceamento de carga nem variam roubando e, consequentemente podem alterar o comportamento de seu aplicativo.
A melhor maneira de determinar se usar um partitioner em qualquer determinado cenário é testar e medir o tempo necessário para concluir operações sob cargas e configurações do computador representativas. Por exemplo, o particionamento estático pode fornecer a aceleração significativa em um computador de vários núcleos que tem apenas alguns núcleos, mas pode resultar para reduzir 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 podem se beneficiar de ser classificado em paralelo. Em particular, classificar em paralelo é útil quando você tem um grande conjunto de dados ou quando você usa um computacional- caro compara a operação para classificar seus dados. Cada um desses elementos os tipos de algoritmos no lugar.
Os algoritmos de parallel_sort e de parallel_buffered_sort são ambos os algoritmos comparar-baseados. Ou seja, comparar os elementos pelo valor. O algoritmo de parallel_sort não tem nenhum requisito de memória adicional, e é apropriado para a classificação de uso geral. O algoritmo de parallel_buffered_sort talvez seja melhor do que parallel_sort, mas requer espaço de O(N) .
O algoritmo de parallel_radixsort hash-é baseado. Isto é, o usa chaves de inteiro para classificar os elementos. Usando chaves, esse algoritmo diretamente pode calcular o destino de um elemento em vez de usar comparações. Como parallel_buffered_sort, esse algoritmo requer espaço de O(N) .
A tabela a seguir resume as propriedades importantes dos três algoritmos de classificação paralelos.
Algoritmo |
Descrição |
O mecanismo de classificação |
Estabilidade do tipo |
Requisitos de memória |
Complexidade de tempo |
Acesso de iterador |
|---|---|---|---|---|---|---|
parallel_sort |
Tipo comparar- base de uso geral. |
Comparar- baseado em ordem crescente () |
Instável |
Nenhum |
O((N/P)log(N/P) + 2N((P-1)/P)) |
Aleatória |
parallel_buffered_sort |
Tipo comparar- base de uso geral mais rápido que requer O (s) (N) o espaço. |
Comparar- baseado em ordem crescente () |
Instável |
Requer espaço adicional de O(N) |
O((N/P)log(N)) |
Aleatória |
parallel_radixsort |
Tipo de chave baseada inteiro que requer O (s) (N) o espaço. |
Com base Hash- |
Stable |
Requer espaço adicional de O(N) |
O(N/P) |
Aleatória |
A ilustração a seguir mostra as propriedades importantes dos três algoritmos de classificação paralelos mais graficamente.
.png "Comparação dos algoritmos de classificação")
Esses algoritmos de classificação paralelos seguem as regras de manipulação de cancelamento e exceção. Para obter mais informações sobre a manipulação de cancelamento e de exceção em tempo de execução de simultaneidade, consulte Cancelando algoritmos paralelos e Tratamento de exceções no tempo de execução de simultaneidade.
Dica
Semântica paralela o suporte desses algoritmos de classificação.Você pode definir um operador de atribuição de movimentação para habilitar operações de troca para ocorrer mais eficiente.Para obter mais informações sobre a semântica de movimentação e o operador de atribuição de movimentação, consulte Declarador de referência Rvalue: &&, e Como escrever um construtor move.Se você não fornecer uma função do operador de atribuição ou de troca de movimentação, os algoritmos de classificação usam o construtor de cópia.
O exemplo básico mostra como usar parallel_sort 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 conjunto personalizado compara a função. Usa o método de std::complex::real para classificar valores de 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 algoritmo de parallel_radixsort . Este exemplo classifica pontos 3d. Os pares 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 ilustrar, este exemplo usa um conjunto de dados relativamente pequeno. Você pode aumentar o tamanho inicial de vetor para testar as melhorias de desempenho em conjuntos de dados maiores.
Este exemplo usa uma expressão de lambda como a função de hash. Você também pode usar uma das implementações internos da classe de std::hash ou definir sua própria conhecimento. Você também pode usar um objeto personalizado da 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 completo (std::is_integral::value deve ser true). Esse tipo integral deve ser convertida digite size_t.
Escolhendo um Algoritmo de Classificação
Em muitos casos, parallel_sort fornece o melhor equilíbrio da velocidade de desempenho e memória. Porém, à medida que você aumenta o tamanho do conjunto de dados, do número de processadores disponíveis, ou da complexidade do comparar a função, o parallel_buffered_sort ou o parallel_radixsort talvez seja melhor. A melhor maneira de determinar qual algoritmo de classificação usar em qualquer cenário é determinado novamente e medir o tempo necessário para classificar dados típicos em configurações do computador representativas. Lembre-se das seguintes diretrizes em consideração ao escolher uma estratégia de classificação.
O tamanho do conjunto de dados. Neste documento, um conjunto de dados pequeno contiver menos de 1.000 elementos, um conjunto de dados intermediário contém entre 10.000 e 100.000 elementos, e um grande conjunto de dados contiver mais de 100.000 elementos.
A quantidade de trabalho que o comparar a função ou a função de hash é executado.
A quantidade de recursos de computação disponíveis.
As características do conjunto de dados. Por exemplo, um algoritmo poderia executar bem para os dados que já estão classificados quase, mas não tão bem para os dados que são completamente não escolhido.
O tamanho da parte. O argumento opcional de _Chunk_size especifica quando o algoritmo de um paralelo a uma implementação do tipo como serial subdivide o tipo total em unidades menores de trabalho. Por exemplo, se você fornecer 512, o algoritmo à implementação serial quando uma unidade de trabalho contenha 512 ou menos para elementos. Uma implementação serial pode melhorar o desempenho global porque elimina sobrecarga que é necessária para processar em paralelo dados.
Não pode ser valor de classificação em paralelo um conjunto de dados pequeno, mesmo quando você tem muitos recursos de computação disponíveis ou sua para comparar a função ou a função de hash executa uma quantia relativamente grande de trabalho. Você pode usar a função de std::sort para classificar conjunto de dados pequenos. (parallel_sort e parallel_buffered_sort chamam sort quando você especificar um tamanho da parte que seja maior que o conjunto de dados; no entanto, parallel_buffered_sort precisar alocar espaço de O(N) , que pode levar mais tempo devido a contenção ou na alocação de memória de bloqueio.)
Se você precisar conservar a memória ou o alocador de memória está sujeito a contenção de bloqueio, use parallel_sort para classificar um conjunto de dados de tamanho médio. parallel_sort não requer nenhum espaço adicional; os outros algoritmos requerem espaço de O(N) .
Use parallel_buffered_sort para classificar conjunto de dados de tamanho médio e quando seu aplicativo atender aos requisitos de espaço adicional de O(N) . parallel_buffered_sort poderá ser especialmente útil quando você tem muitos recursos de computação ou um caro comparar a função ou a função de hash.
Use parallel_radixsort para classificar grandes conjuntos de dados e quando seu aplicativo atender aos requisitos de espaço adicional de O(N) . parallel_radixsort poderá ser especialmente útil quando o equivalente compara a operação é mais caro ou quando as duas operações são caras.
Aviso
Implementar uma boa função de hash requer que você souber o intervalo de conjunto de dados e como cada elemento no conjunto de dados é transformado em um valor sem assinatura correspondente.Por que a operação de hash funciona em valores não assinados, considere uma estratégia de classificação diferente se os valores de hash sem assinatura 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 no 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.
*/
Neste exemplo, que assume que é aceitável alocar espaço de O(N) durante o tipo, parallel_radixsort o melhor desempenho neste conjunto de dados nesta configuração do computador.
[Superior]
Tópicos relacionados
Nome |
Descrição |
|---|---|
Mostra como usar o algoritmo de parallel_for para executar a multiplicação da matriz. |
|
Mostra como usar o algoritmo de parallel_for_each para computar em paralelo a contagem de números à esquerda em um objeto de std::array . |
|
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 bitonic. |
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. |
Mostra como usar os algoritmos de parallel_transform e de parallel_reduce para executar um mapa e reduzir a operação que conta as ocorrências das palavras nos arquivos. |
|
Descreve o PPL, que fornece um modelo de programação obrigatório que promova a escalabilidade e a facilidade de uso para desenvolver aplicativos simultâneos. |
|
Explica a função de cancelamento em PPL, como cancelar o trabalho paralelo, e como determinar quando um grupo de trabalho for cancelado. |
|
Tratamento de exceções no tempo de execução de simultaneidade |
Explica a função de manipulação de exceção em tempo de execução de simultaneidade. |