Como: Use o parallel_invoke para gravar uma rotina paralela de tipo
Este documento descreve como usar o algoritmo de parallel_invoke para melhorar o desempenho do algoritmo de tipo bitonic.O algoritmo de tipo bitonic divide recursivamente a sequência de entrada em particiona menores classificados.O algoritmo de tipo bitonic pode executar paralelamente porque cada operação de partição é independente de quaisquer outras operações.
Embora o tipo bitonic é um exemplo de uma rede de classificação que classifica todas as combinações de sequências de entrada, as sequências de tipos deste exemplo cujos comprimentos são uma potência de dois.
.gif "Observação") Observação |
|---|
Este exemplo usa uma rotina paralela do tipo para a ilustração.Você também pode usar os algoritmos de classificação internos que o PPL fornece: concurrency::parallel_sort, concurrency::parallel_buffered_sort, e concurrency::parallel_radixsort.Para obter mais informações, consulte Algoritmos paralelos. |
Seções
Este documento descreve as seguintes tarefas:
Executando o tipo de Bitonic em série
Usando o parallel_invoke para executar paralelamente o tipo de Bitonic
Executando o tipo de Bitonic em série
O exemplo a seguir mostra a versão serial do algoritmo de tipo bitonic.A função de bitonic_sort divide a sequência em dois particiona esses particiona, classe em instruções opostas, e mescla os resultados.Este chamadas de função próprias duas vezes classificar recursivamente cada partição.
const bool INCREASING = true;
const bool DECREASING = false;
// Comparator function for the bitonic sort algorithm.
template <class T>
void compare(T* items, int i, int j, bool dir)
{
if (dir == (items[i] > items[j]))
{
swap(items[i], items[j]);
}
}
// Sorts a bitonic sequence in the specified order.
template <class T>
void bitonic_merge(T* items, int lo, int n, bool dir)
{
if (n > 1)
{
int m = n / 2;
for (int i = lo; i < lo + m; ++i)
{
compare(items, i, i + m, dir);
}
bitonic_merge(items, lo, m, dir);
bitonic_merge(items, lo + m, m, dir);
}
}
// Sorts the given sequence in the specified order.
template <class T>
void bitonic_sort(T* items, int lo, int n, bool dir)
{
if (n > 1)
{
// Divide the array into two partitions and then sort
// the partitions in different directions.
int m = n / 2;
bitonic_sort(items, lo, m, INCREASING);
bitonic_sort(items, lo + m, m, DECREASING);
// Merge the results.
bitonic_merge(items,lo, n, dir);
}
}
// Sorts the given sequence in increasing order.
template <class T>
void bitonic_sort(T* items, int size)
{
bitonic_sort(items, 0, size, INCREASING);
}
Superior[]
Usando o parallel_invoke para executar paralelamente o tipo de Bitonic
Esta seção descreve como usar o algoritmo de parallel_invoke para executar paralelamente o algoritmo de tipo bitonic.
.gif "Dd728066.collapse_all(pt-br,VS.110).gif")
Procedimentos
Para executar paralelamente o algoritmo de tipo bitonic
Adicione uma diretiva de #include para o arquivo de cabeçalho ppl.h.
#include <ppl.h>Adicione uma diretiva de using para o namespace de concurrency .
using namespace concurrency;Crie uma nova função, parallel_bitonic_megechamado, que usa o algoritmo de parallel_invoke para mesclar as paralelamente sequências se houver uma quantidade de trabalho suficiente para fazer.Caso contrário, chame bitonic_merge para mesclar na série sequências.
// Sorts a bitonic sequence in the specified order. template <class T> void parallel_bitonic_merge(T* items, int lo, int n, bool dir) { // Merge the sequences concurrently if there is sufficient work to do. if (n > 500) { int m = n / 2; for (int i = lo; i < lo + m; ++i) { compare(items, i, i + m, dir); } // Use the parallel_invoke algorithm to merge the sequences in parallel. parallel_invoke( [&items,lo,m,dir] { parallel_bitonic_merge(items, lo, m, dir); }, [&items,lo,m,dir] { parallel_bitonic_merge(items, lo + m, m, dir); } ); } // Otherwise, perform the work serially. else if (n > 1) { bitonic_merge(items, lo, n, dir); } }Executar um processo que lembra o na etapa anterior, mas para a função de bitonic_sort .
// Sorts the given sequence in the specified order. template <class T> void parallel_bitonic_sort(T* items, int lo, int n, bool dir) { if (n > 1) { // Divide the array into two partitions and then sort // the partitions in different directions. int m = n / 2; // Sort the partitions in parallel. parallel_invoke( [&items,lo,m] { parallel_bitonic_sort(items, lo, m, INCREASING); }, [&items,lo,m] { parallel_bitonic_sort(items, lo + m, m, DECREASING); } ); // Merge the results. parallel_bitonic_merge(items, lo, n, dir); } }Criar uma versão sobrecarregada de função de parallel_bitonic_sort que classifica a matriz na ordem crescente.
// Sorts the given sequence in increasing order. template <class T> void parallel_bitonic_sort(T* items, int size) { parallel_bitonic_sort(items, 0, size, INCREASING); }
O algoritmo de parallel_invoke reduz a sobrecarga executando o final da série de tarefas no contexto de chamada.Por exemplo, na função de parallel_bitonic_sort , a primeira tarefa é executado em um contexto separado, e a segunda tarefa é executada no contexto de chamada.
// Sort the partitions in parallel.
parallel_invoke(
[&items,lo,m] { parallel_bitonic_sort(items, lo, m, INCREASING); },
[&items,lo,m] { parallel_bitonic_sort(items, lo + m, m, DECREASING); }
);
O seguinte exemplo completo executa as versões seriais e paralelas do algoritmo de tipo bitonic.O exemplo também imprime no console a hora que são necessários para executar cada computação.
// parallel-bitonic-sort.cpp
// compile with: /EHsc
#include <windows.h>
#include <algorithm>
#include <iostream>
#include <random>
#include <ppl.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 bool INCREASING = true;
const bool DECREASING = false;
// Comparator function for the bitonic sort algorithm.
template <class T>
void compare(T* items, int i, int j, bool dir)
{
if (dir == (items[i] > items[j]))
{
swap(items[i], items[j]);
}
}
// Sorts a bitonic sequence in the specified order.
template <class T>
void bitonic_merge(T* items, int lo, int n, bool dir)
{
if (n > 1)
{
int m = n / 2;
for (int i = lo; i < lo + m; ++i)
{
compare(items, i, i + m, dir);
}
bitonic_merge(items, lo, m, dir);
bitonic_merge(items, lo + m, m, dir);
}
}
// Sorts the given sequence in the specified order.
template <class T>
void bitonic_sort(T* items, int lo, int n, bool dir)
{
if (n > 1)
{
// Divide the array into two partitions and then sort
// the partitions in different directions.
int m = n / 2;
bitonic_sort(items, lo, m, INCREASING);
bitonic_sort(items, lo + m, m, DECREASING);
// Merge the results.
bitonic_merge(items,lo, n, dir);
}
}
// Sorts the given sequence in increasing order.
template <class T>
void bitonic_sort(T* items, int size)
{
bitonic_sort(items, 0, size, INCREASING);
}
// Sorts a bitonic sequence in the specified order.
template <class T>
void parallel_bitonic_merge(T* items, int lo, int n, bool dir)
{
// Merge the sequences concurrently if there is sufficient work to do.
if (n > 500)
{
int m = n / 2;
for (int i = lo; i < lo + m; ++i)
{
compare(items, i, i + m, dir);
}
// Use the parallel_invoke algorithm to merge the sequences in parallel.
parallel_invoke(
[&items,lo,m,dir] { parallel_bitonic_merge(items, lo, m, dir); },
[&items,lo,m,dir] { parallel_bitonic_merge(items, lo + m, m, dir); }
);
}
// Otherwise, perform the work serially.
else if (n > 1)
{
bitonic_merge(items, lo, n, dir);
}
}
// Sorts the given sequence in the specified order.
template <class T>
void parallel_bitonic_sort(T* items, int lo, int n, bool dir)
{
if (n > 1)
{
// Divide the array into two partitions and then sort
// the partitions in different directions.
int m = n / 2;
// Sort the partitions in parallel.
parallel_invoke(
[&items,lo,m] { parallel_bitonic_sort(items, lo, m, INCREASING); },
[&items,lo,m] { parallel_bitonic_sort(items, lo + m, m, DECREASING); }
);
// Merge the results.
parallel_bitonic_merge(items, lo, n, dir);
}
}
// Sorts the given sequence in increasing order.
template <class T>
void parallel_bitonic_sort(T* items, int size)
{
parallel_bitonic_sort(items, 0, size, INCREASING);
}
int wmain()
{
// For this example, the size must be a power of two.
const int size = 0x200000;
// Create two large arrays and fill them with random values.
int* a1 = new int[size];
int* a2 = new int[size];
mt19937 gen(42);
for(int i = 0; i < size; ++i)
{
a1[i] = a2[i] = gen();
}
__int64 elapsed;
// Perform the serial version of the sort.
elapsed = time_call([&] { bitonic_sort(a1, size); });
wcout << L"serial time: " << elapsed << endl;
// Now perform the parallel version of the sort.
elapsed = time_call([&] { parallel_bitonic_sort(a2, size); });
wcout << L"parallel time: " << elapsed << endl;
delete[] a1;
delete[] a2;
}
A seguinte saída de exemplo são para um computador que tem quatro processadores.
Superior[]
Compilando o código
Para compilar o código, copie e cole em um projeto Visual Studio, ou cole em um arquivo denominado parallel-bitonic-sort.cpp e execute o seguinte comando em uma janela de prompt de comando do Visual Studio.
cl.exe /EHsc parallel-bitonic-sort.cpp
Programação robusta
Este exemplo usa o algoritmo de parallel_invoke em vez da classe de concurrency::task_group porque o tempo de vida de cada grupo de trabalho não ultrapassa de uma função.Recomendamos que você usa quando parallel_invoke você pode porque tem menos sobrecarga de execução para objetos de task group , e permite como consequência escrever um código mais de trabalho satisfatório.
As versões paralelas de alguns algoritmos executam melhor somente quando há um trabalho suficiente para fazer.Por exemplo, as chamadas de função de parallel_bitonic_merge a versão serial, bitonic_merge, se houver 500 ou menos elementos na sequência.Você também pode planejar sua estratégia geral de classificação com base na quantidade de trabalho.Por exemplo, pode ser mais eficiente usar a versão serial do algoritmo de tipo rápido se a matriz contém menos de 500 itens, conforme mostrado no exemplo o seguir:
template <class T>
void quick_sort(T* items, int lo, int n)
{
// TODO: The function body is omitted for brevity.
}
template <class T>
void parallel_bitonic_sort(T* items, int lo, int n, bool dir)
{
// Use the serial quick sort algorithm if there are relatively few
// items to sort. The associated overhead for running few tasks in
// parallel may not overcome the benefits of parallel processing.
if (n - lo + 1 <= 500)
{
quick_sort(items, lo, n);
}
else if (n > 1)
{
// Divide the array into two partitions and then sort
// the partitions in different directions.
int m = n / 2;
// Sort the partitions in parallel.
parallel_invoke(
[&items,lo,m] { parallel_bitonic_sort(items, lo, m, INCREASING); },
[&items,lo,m] { parallel_bitonic_sort(items, lo + m, m, DECREASING); }
);
// Merge the results.
parallel_bitonic_merge(items, lo, n, dir);
}
}
Como com qualquer algoritmo paralelo, recomendamos que você analisa e ajustamos seu código conforme apropriado.