Postup: zápis paralelní rutinní řazení pomocí parallel_invoke

Článek
05/01/2013

Tento dokument popisuje, jak použít parallel_invoke algoritmus pro zlepšení výkonu algoritmus řazení bitonic.Rekurzivně algoritmus řazení bitonic rozdělí na menší oddíly seřazené vstupní posloupnosti.Řadicí algoritmus bitonic mohou spouštět současně, protože každé operace oddílu je nezávislý na jiných operací.

Ačkoli je příkladem bitonic řazení řazení sítě , seřadí všechny kombinace vstupní sekvence, jehož délky se napájení dvou řad seřadí tento příklad.

[!POZNÁMKA]

Tento příklad používá paralelní řazení rutina pro ilustraci.Můžete také použít předdefinované třídění algoritmy, které poskytuje PPL: concurrency::parallel_sort, concurrency::parallel_buffered_sort, a concurrency::parallel_radixsort.Další informace naleznete v tématu Paralelní algoritmy.

Oddíly

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

Sériově provedením řazení Bitonic
Pomocí paralelně k provedení řazení Bitonic parallel_invoke

Sériově provedením řazení Bitonic

Následující příklad ukazuje sériové verze algoritmus řazení bitonic.bitonic_sort Funkce Posloupnost rozdělí na dva oddíly, řadí tyto oddíly ve směru a potom sloučí výsledky.Tato funkce volá sám sebe dvakrát rekurzivně řazení jednotlivých oddílů.

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

Top

Pomocí paralelně k provedení řazení Bitonic parallel_invoke

Tato část popisuje použití parallel_invoke algoritmus, algoritmus řazení bitonic provést souběžně.

Procedury

Paralelně provádět bitonic řadicí algoritmus

Přidat #include směrnice pro ppl.h hlavičky souboru.
```
#include <ppl.h>
```
Přidat using směrnice pro concurrency oboru názvů.
```
using namespace concurrency;
```

Vytvoření nové funkce, nazývané parallel_bitonic_mege, která používá parallel_invoke algoritmus ke sloučení sekvence paralelně, pokud je dostatečné množství práce do.Jinak volání bitonic_merge na sekvence sériově sloučit.

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

Proces, který se podobá v předchozím kroku, ale pro provést bitonic_sort funkce.

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

Vytvořit přetížené verzi parallel_bitonic_sort funkce, která se řadí pole vzestupně.

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

parallel_invoke Algoritmus snižuje režii provedením poslední řady úkolů na kontext volání.Například v parallel_bitonic_sort funkce spuštěna první úkol na samostatný kontext a druhý úloha spuštěna v kontextu volajícího.

// 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í příklad úplné provádí sériový a paralelní verze algoritmus řazení bitonic.Příklad vytiskne také v konzole doba potřebná k provedení výpočtu každý.

// 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č, který má čtyři procesory.

serial time: 4353
parallel time: 1248

Top

Probíhá kompilace kódu

Kompilace kódu, zkopírujte a vložte do projektu Visual Studio nebo vložit do souboru s názvem paralelní bitonic sort.cpp a spusťte následující příkaz v okně příkazového řádku Visual Studio.

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

Robustní programování

V tomto příkladu parallel_invoke algoritmus místo concurrency::task_group třídy, protože životnost každé skupiny úloh nepřesahuje funkci.Doporučujeme použít parallel_invoke při můžete protože jeho spuštění, menší nároky než task group objekty a proto umožňuje lepší provést kód.

Paralelní verze některé algoritmy pracovat lépe, pouze pokud není dostatečné pracovní postup.Například parallel_bitonic_merge sériové verze volá funkci bitonic_merge, pokud jsou v pořadí prvků 500 nebo méně.Můžete také naplánovat celkové strategii řazení na základě množství práce.Například může být efektivnější použít sériové verze algoritmus rychlé ř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 všechny paralelní algoritmus doporučujeme, profilu a ladění kódu podle potřeby.

Sdílet prostřednictvím

Postup: zápis paralelní rutinní řazení pomocí parallel_invoke

Oddíly

Sériově provedením řazení Bitonic

Pomocí paralelně k provedení řazení Bitonic parallel_invoke

Procedury

Paralelně provádět bitonic řadicí algoritmus

Probíhá kompilace kódu

Robustní programování

Viz také

Referenční dokumentace

Koncepty

Další materiály