Postupy: Použití algoritmu parallel_invoke k zápisu rutiny paralelního třídění

Tento dokument popisuje, jak použít algoritmus parallel_invoke ke zlepšení výkonu algoritmu řazení bitových hodnot. Algoritmus řazení bitonic rekurzivně rozdělí vstupní sekvenci na menší seřazené oddíly. Algoritmus řazení bitonic může běžet paralelně, protože každá operace oddílu je nezávislá na všech ostatních operacích.

I když je bitonic sorting příkladem sítě řazení, která seřadí všechny kombinace vstupních sekvencí, tento příklad seřadí sekvence, jejichž délky jsou mocninami dvou.

Poznámka:

Tento příklad používá pro ilustraci rutinu paralelního řazení. Můžete také použít integrované algoritmy řazení, které PPL poskytuje: concurrency::p arallel_sort, concurrency::p arallel_buffered_sort a souběžnost::p arallel_radixsort. Další informace naleznete v tématu Paralelní algoritmy.

Oddíly

Tento dokument popisuje následující úlohy:

• Sériové řazení bitových funkcí

• Paralelní provádění řazení bitonic pomocí parallel_invoke

Sériové řazení bitových funkcí

Následující příklad ukazuje sériovou verzi algoritmu řazení bitonic. Funkce bitonic_sort rozdělí sekvenci do dvou oddílů, seřadí tyto oddíly v opačných směrech a pak sloučí výsledky. Tato funkce se volá dvakrát rekurzivně, aby se seřadily jednotlivé oddíly.

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

[Nahoře]

Paralelní provádění řazení bitonic pomocí parallel_invoke

Tato část popisuje, jak pomocí parallel_invoke algoritmu paralelně provádět algoritmus řazení bitových hodnot.

Paralelní provádění algoritmu bitonického řazení

1. Přidejte direktivu pro hlavičkový #include soubor ppl.h.

   #include <ppl.h>
   

2. Přidejte direktivu using concurrency pro obor názvů.

   using namespace concurrency;
   

3. Vytvořte novou funkci s názvem parallel_bitonic_mege, která používá parallel_invoke algoritmus ke sloučení sekvencí paralelně, pokud je k dispozici dostatek práce. Jinak volání bitonic_merge pro sloučení sekvencí sériově.

   // 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. Proveďte proces, který se podobá procesu v předchozím kroku, ale pro bitonic_sort funkci.

   // 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. Vytvořte přetíženou verzi parallel_bitonic_sort funkce, která seřadí pole v rostoucím pořadí.

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

   Algoritmus parallel_invoke snižuje režii provedením poslední řady úloh na volajícím kontextu. Například ve parallel_bitonic_sort funkci se první úloha spustí v samostatném kontextu a druhá úloha se spustí v kontextu volání.

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

Následující úplný příklad provádí serial i paralelní verze bitonic sort algoritmu. Příklad také vytiskne do konzoly čas potřebný k provedení jednotlivých výpočtů.

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

Následující ukázkový výstup je pro počítač se čtyřmi procesory.

serial time: 4353
parallel time: 1248

[Nahoře]

Probíhá kompilace kódu

Pokud chcete kód zkompilovat, zkopírujte ho a vložte ho do projektu sady Visual Studio nebo ho vložte do pojmenovaného parallel-bitonic-sort.cpp souboru a potom v okně příkazového řádku sady Visual Studio spusťte následující příkaz.

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

Robustní programování

Tento příklad používá parallel_invoke algoritmus místo concurrency::task_group třídy, protože životnost každé skupiny úloh se nevztahuje nad rámec funkce. Doporučujeme použít parallel_invoke , když můžete, protože má menší režii při provádění než task group objekty, a proto vám umožní psát lépe fungující kód.

Paralelní verze některých algoritmů fungují lépe jenom v případech, kdy je k dispozici dostatek práce. parallel_bitonic_merge Například funkce volá sériovou verzi , bitonic_mergepokud v sekvenci existuje 500 nebo méně prvků. Můžete také naplánovat celkovou strategii řazení na základě množství práce. Například může být efektivnější použít sériovou verzi algoritmu rychlého řazení, pokud pole obsahuje méně než 500 položek, jak je znázorněno v následujícím příkladu:

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

Stejně jako u jakéhokoli paralelního algoritmu doporučujeme profilovat a ladit kód podle potřeby.

Viz také

Paralelismus úkolu
parallel_invoke – funkce