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

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

Embora a classificação bitônica seja um exemplo de uma rede de classificação que classifica todas as combinações de sequências de entrada, este exemplo classifica sequências cujos comprimentos são uma potência de dois.

Observação

Este exemplo usa uma rotina de classificação paralela para ilustração. Você também pode usar os algoritmos de ordenação internos que o PPL fornece: concurrency::parallel_sort, concurrency::parallel_buffered_sort e concurrency::parallel_radixsort. Para obter mais informações, consulte Parallel Algorithms.

Secções

Este documento descreve as seguintes tarefas:

• Executando Bitonic Sort Serially

• Usando parallel_invoke para executar a classificação bitônica em paralelo

Executando a Bitonic Sort de forma sequencial

O exemplo a seguir mostra a versão serial do algoritmo de classificação bitônica. A bitonic_sort função divide a sequência em duas partições, classifica essas partições em direções opostas e, em seguida, mescla os resultados. Esta função chama-se duas vezes recursivamente para ordenar 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);
}

[Topo]

Usando parallel_invoke para executar a classificação bitônica em paralelo

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

Para executar o algoritmo de classificação bitônica em paralelo

1. Adicione uma #include diretiva para o arquivo de cabeçalho ppl.h.

   #include <ppl.h>
   

2. Adicione uma using diretiva para o concurrency namespace.

   using namespace concurrency;
   

3. Crie uma nova função, chamada parallel_bitonic_mege, que usa o parallel_invoke algoritmo para mesclar as sequências em paralelo se houver quantidade suficiente de trabalho a fazer. Caso contrário, 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);
      }   
   }
   

4. Execute um processo semelhante ao da etapa anterior, mas para a 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. Crie uma versão sobrecarregada da parallel_bitonic_sort função 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 parallel_invoke algoritmo reduz a sobrecarga executando a última da série de tarefas no contexto de chamada. Por exemplo, na função parallel_bitonic_sort, a primeira tarefa é executada num contexto separado e a segunda tarefa é executada no contexto do chamador.

   // 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 a seguir executa as versões serial e paralela do algoritmo de classificação bitônica. 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 é para um computador que tem quatro processadores.

serial time: 4353
parallel time: 1248

[Topo]

Compilando o código

Para compilar o código, copie-o e cole-o em um projeto do Visual Studio ou cole-o em um arquivo nomeado parallel-bitonic-sort.cpp e, em seguida, execute o seguinte comando em uma janela do prompt de comando do Visual Studio.

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

Programação robusta

Este exemplo usa o parallel_invoke algoritmo em vez da classe concurrency::task_group porque o tempo de vida de cada grupo de tarefas não se estende além de uma função. Recomendamos que você use parallel_invoke quando puder, pois tem menos sobrecarga de execução do que task group objetos e, portanto, permite que você escreva código com melhor desempenho.

As versões paralelas de alguns algoritmos funcionam melhor apenas quando há trabalho suficiente para fazer. Por exemplo, a parallel_bitonic_merge função chama 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 classificação rápida se a matriz contiver menos de 500 itens, conforme 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);
   }
}

Tal como acontece com qualquer algoritmo paralelo, recomendamos que crie o perfil e ajuste o seu código conforme apropriado.

Ver também

Paralelismo de tarefas
Função parallel_invoke