Como: Use o parallel_invoke para escrever uma rotina de classificação paralela

Este documento descreve como usar o parallel_invoke o algoritmo para melhorar o desempenho do algoritmo de classificação bitonic. O recursivamente de algoritmo de classificação bitonic divide a seqüência de entrada menores classificadas partições. O algoritmo de classificação de bitonic pode ser executado em paralelo porque cada operação de partição é independente de todas as outras operações.

Embora a classificação de bitonic é um exemplo de um a classificação de rede que classifica todas as combinações de seqüências de entrada, este exemplo classifica seqüências cujos comprimentos são uma potência de dois.

Seções

Este documento descreve as seguintes tarefas:

• Executar a classificação de Bitonic em série

• Usando o parallel_invoke para executar o Bitonic classificar em paralelo

Executar a classificação de Bitonic em série

O exemplo a seguir mostra a versão serial do algoritmo de classificação bitonic. O bitonic_sort função divide a seqüência em duas partições, classifica essas partições em direções opostas e em seguida, mescla os resultados. Essa função chama recursivamente duas vezes para classificar 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);
}

go to top

Usando o parallel_invoke para executar o Bitonic classificar em paralelo

Esta seção descreve como usar o parallel_invoke o algoritmo para executar o algoritmo de classificação de bitonic em paralelo.

Procedimentos

Para executar o algoritmo de classificação de bitonic em paralelo

1. Adicionar um #include a diretiva para o ppl.h de arquivo de cabeçalho.

   #include <ppl.h>
   

2. Adicionar um using diretiva para o Concurrency namespace.

   using namespace Concurrency;
   

3. Crie uma nova função chamada parallel_bitonic_mege, que usa a parallel_invoke o algoritmo para mesclar as seqüências em paralelo, se houver uma quantidade suficiente de trabalho a fazer. Caso contrário, chamar bitonic_merge para mesclar as seqüências serialmente.

   // 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);
      }   
   }
   

4. Executar um processo semelhante na etapa anterior, mas para o bitonic_sort função.

   // 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);
      }
   }
   

5. Criar uma versão sobrecarregada da parallel_bitonic_sort função que classifica o array no aumento da ordem.

   // 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 parallel_invoke algoritmo reduz a sobrecarga, realizando a última da série de tarefas no contexto de chamada. Por exemplo, o parallel_bitonic_sort função, a primeira tarefa é executada 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 exemplo a seguir completo executa as versões paralelas do algoritmo de classificação bitonic e a série. O exemplo também imprime no 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 saída de exemplo a seguir é de um computador que possui quatro processadores.

serial time: 4353
parallel time: 1248

go to top

Compilando o código

Para compilar o código, copiá-lo e colá-lo em um Visual Studio do projeto, ou colá-lo em um arquivo que é chamado paralelo-bitonic-sort.cpp e, em seguida, execute o seguinte comando um Visual Studio janela do Prompt de comando.

cl.exe /EHsc parallel-bitonic-sort.cpp

Programação robusta

Este exemplo usa a parallel_invoke o algoritmo em vez da Concurrency::task_group porque o tempo de vida de cada grupo de tarefas não vai além de uma função de classe. Recomendamos que você use parallel_invoke quando possível, porque possui menos sobrecarga de execução do que task group objetos e, portanto, permite que você escreva código melhor desempenho.

As versões paralelas de alguns algoritmos melhor executam somente quando há trabalho suficiente para fazer. Por exemplo, o parallel_bitonic_merge função chama a versão serial, bitonic_merge, se há elementos de 500 ou menos na seqüê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 classificação rápida se a matriz contém menos de 500 itens, como mostrado no exemplo a 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 ocorre com qualquer algoritmo paralelo, recomendamos que você criar o perfil e ajustar seu código conforme apropriado.

Consulte também

Referência

Função de parallel_invoke

Conceitos

Paralelismo de tarefas (Runtime de simultaneidade)

Histórico de alterações

Date	History	Motivo
Julho de 2010	Exemplo atualizado para usar parallel_invoke.	Aprimoramento de informações.