Como usar parallel_invoke para escrever uma rotina de classificação em paralelo
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 partições menores classificados. O algoritmo de tipo bitonic pode ser executados em paralelo porque cada operação de partição é independente de todas as 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 desse exemplo com comprimento é uma potência de dois.
Dica
Este exemplo usa uma rotina o tipo parallel para ilustração.Você também pode usar algoritmos de classificação internas que o fornece PPL: 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:
Realizando Classificação Bitonic em Série
Usando parallel_invoke para Realizar Classificação Bitonic em Paralelo
Realizando Classificação 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 duas partições, classifica essas partições em direções opostas, e então 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 parallel_invoke para Realizar Classificação Bitonic em Paralelo
Esta seção descreve como usar o algoritmo de parallel_invoke para ser executados em paralelo o algoritmo de tipo bitonic.
Procedimentos
Para realizar o algoritmo de classificação bitonic em paralelo
Adicionar uma política de #include para o arquivo de cabeçalho ppl.h.
#include <ppl.h>Adicionar uma política 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 em paralelo as sequências se houver uma quantidade suficiente de trabalho para executar. Se não, chame bitonic_merge para mesclar as sequências em série.
// 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 semelhante ao da 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); } }Crie uma versão sobrecarregada da função de parallel_bitonic_sort que classifica a matriz em 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 último da série de tarefas no contexto de chamada. Por exemplo, na função de parallel_bitonic_sort , a primeira tarefa é executada em um contexto separado, e a segunda tarefa é executado 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 exemplo completo executa as versões e seriais paralelas do algoritmo de tipo bitonic. O exemplo também imprime ao console o tempo necessário para executar cada cálculo.
// 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 é para um computador que tem quatro processadores.
[Superior]
Compilando o código
Para compilar o código, copie-a e cole-o em um projeto do Visual Studio, ou cole-o em um arquivo chamado parallel-bitonic-sort.cpp e execute o comando a seguir 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 exceda de uma função. Recomendamos que você use parallel_invoke quando é possível porque tem menos sobrecarga de execução que objetos de task group , e em virtude disso permite escrever um código mais de desempenho.
As versões paralelas de alguns algoritmos executam melhor apenas quando há um trabalho suficiente para executar. Por exemplo, as chamadas de função de parallel_bitonic_merge a versão de série, 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 quando a matriz tiver menos de 500 itens, como mostrado no seguinte exemplo:
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.