Procedura: Usare parallel_invoke per scrivere una routine di ordinamento in parallelo

  • Articolo

Questo documento descrive come usare l'algoritmo di parallel_invoke per migliorare le prestazioni dell'algoritmo di ordinamento bitonico. L'algoritmo di ordinamento bitonico divide in modo ricorsivo la sequenza di input in partizioni ordinate più piccole. L'algoritmo di ordinamento bitonico può essere eseguito in parallelo perché ogni operazione di partizione è indipendente da tutte le altre operazioni.

Anche se l'ordinamento bitonico è un esempio di rete di ordinamento che ordina tutte le combinazioni di sequenze di input, questo esempio ordina le sequenze le cui lunghezze sono una potenza di due.

Nota

In questo esempio viene utilizzata, a scopo illustrativo, una routine di ordinamento in parallelo. È anche possibile usare gli algoritmi di ordinamento predefiniti forniti da PPL: concurrency::p arallel_sort, concurrency::p arallel_buffered_sort e concurrency::p arallel_radixsort. Per altre informazioni, vedere Algoritmi paralleli.

Sezioni

Questo documento descrive le attività seguenti:

Esecuzione seriale dell'ordinamento bitonico

Nell'esempio seguente viene illustrata la versione seriale dell'algoritmo di ordinamento bitonico. La bitonic_sort funzione divide la sequenza in due partizioni, ordina tali partizioni in direzioni opposte e quindi unisce i risultati. Questa funzione si chiama due volte in modo ricorsivo per ordinare ogni partizione.

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

[Torna all'inizio]

Uso di parallel_invoke per eseguire l'ordinamento bitonico in parallelo

Questa sezione descrive come usare l'algoritmo per eseguire l'algoritmo parallel_invoke di ordinamento bitonico in parallelo.

Per eseguire l'algoritmo di ordinamento bitonico in parallelo

  1. Aggiungere una #include direttiva per il file di intestazione ppl.h.

    #include <ppl.h>

  2. Aggiungere una using direttiva per lo spazio dei concurrency nomi .

    using namespace concurrency;

  3. Creare una nuova funzione, denominata parallel_bitonic_mege, che usa l'algoritmo parallel_invoke per unire le sequenze in parallelo se è disponibile una quantità sufficiente di lavoro da eseguire. In caso contrario, chiamare bitonic_merge per unire le sequenze in modo seriale.

    // 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. Eseguire un processo simile a quello del passaggio precedente, ma per la bitonic_sort funzione .

    // 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. Creare una versione di overload della parallel_bitonic_sort funzione che ordina la matrice in ordine 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);
}

    L'algoritmo parallel_invoke riduce il sovraccarico eseguendo l'ultima delle serie di attività nel contesto chiamante. Nella funzione, ad esempio, parallel_bitonic_sort la prima attività viene eseguita in un contesto separato e la seconda viene eseguita nel contesto chiamante.

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

L'esempio completo seguente esegue sia la versione seriale che quella parallela dell'algoritmo di ordinamento bitonico. L'esempio stampa anche nella console il tempo necessario per eseguire ogni calcolo.

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

L'output di esempio seguente è relativo a un computer con quattro processori.

serial time: 4353
parallel time: 1248

[Torna all'inizio]

Compilazione del codice

Per compilare il codice, copiarlo e incollarlo in un progetto di Visual Studio oppure incollarlo in un file denominato parallel-bitonic-sort.cpp e quindi eseguire il comando seguente in una finestra del prompt dei comandi di Visual Studio.

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

Programmazione efficiente

Questo esempio usa l'algoritmo parallel_invoke anziché la classe concurrency::task_group perché la durata di ogni gruppo di attività non si estende oltre una funzione. È consigliabile usare parallel_invoke quando è possibile perché ha un sovraccarico di esecuzione inferiore rispetto agli task group oggetti e pertanto consente di scrivere codice con prestazioni migliori.

Le versioni parallele di alcuni algoritmi offrono prestazioni migliori solo quando è disponibile un lavoro sufficiente da eseguire. Ad esempio, la parallel_bitonic_merge funzione chiama la versione seriale, , bitonic_mergese nella sequenza sono presenti 500 o meno elementi. È anche possibile pianificare la strategia di ordinamento generale in base alla quantità di lavoro. Ad esempio, potrebbe essere più efficiente usare la versione seriale dell'algoritmo di ordinamento rapido se la matrice contiene meno di 500 elementi, come illustrato nell'esempio seguente:

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

Come per qualsiasi algoritmo parallelo, è consigliabile profilarsi e ottimizzare il codice in base alle esigenze.

Vedi anche

Parallelismo delle attività
Funzione parallel_invoke