Udostępnij za pośrednictwem

Jak: za pomocą parallel_invoke zapisu równoległych rutynowych sortowania

  • Artykuł

W tym dokumencie opisano, jak używać parallel_invoke algorytm, aby zwiększyć wydajność bitonic algorytm sortowania.Rekursywnie algorytm sortowania bitonic dzieli sekwencji wejściowych na mniejszych partycji sortowane.Bitonic algorytm sortowania można równolegle, ponieważ każda operacja partycji jest niezależna od innych operacji.

Chociaż osiągają jest przykładem sortowania sieci , sortuje wszystkie kombinacje sekwencji wejściowych, w tym przykładzie sortuje sekwencji, w których długości są o mocy.

[!UWAGA]

W tym przykładzie użyto rutynowych równoległych sortowania dla ilustracji.Umożliwia także wbudowane algorytmy sortowania, które zapewnia PPL: concurrency::parallel_sort, concurrency::parallel_buffered_sort, i concurrency::parallel_radixsort.Aby uzyskać więcej informacji, zobacz Algorytmy równoległe.

Sekcje

W tym dokumencie opisano następujące zadania:

  • Wykonywanie osiągają seryjnie

  • Za pomocą parallel_invoke do wykonywania osiągają równolegle

Wykonywanie osiągają seryjnie

Poniższy przykład pokazuje szeregowego wersji bitonic algorytm sortowania.bitonic_sort Funkcja sekwencji są podzielone na dwie partycje, sortuje te partycje w przeciwnych kierunkach i następnie scala wyniki.Ta funkcja wymaga rekursywnie dwa razy, aby posortować każdej partycji.

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

Za pomocą parallel_invoke do wykonywania osiągają równolegle

W tej sekcji opisano, jak używać parallel_invoke algorytm przeprowadzać równolegle bitonic algorytm sortowania.

Dd728066.collapse_all(pl-pl,VS.110).gifProcedury

Przeprowadzać równolegle algorytm sortowania bitonic

  1. Dodaj #include dyrektywa dla ppl.h pliku nagłówka.

    #include <ppl.h>

  2. Dodaj using dyrektywa dla concurrency obszaru nazw.

    using namespace concurrency;

  3. Utwórz nową funkcję o nazwie parallel_bitonic_mege, który korzysta z parallel_invoke algorytm scalić sekwencji równolegle, jeśli istnieje wystarczająca ilość pracy.W przeciwnym wypadku wywołanie bitonic_merge połączyć szeregowo sekwencji.

    // 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. Wykonanie procesu, podobny do jednego w poprzednim kroku, ale bitonic_sort funkcji.

    // 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. Tworzenie wersji przeciążony parallel_bitonic_sort funkcja sortuje tablicę w porządku rosnącym.

    // 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 Algorytm zmniejsza obciążenie, wykonując w kontekście wywołującego ostatniej serii zadań.Na przykład w parallel_bitonic_sort funkcji, pierwsze zadanie będzie uruchamiane w kontekście oddzielnych i drugie zadanie będzie uruchamiane w kontekście wywołującego.

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

Poniższy przykład pełną wykonuje zarówno szeregowe i równoległe wersje bitonic algorytm sortowania.Przykład drukuje konsoli również czas wymagany do wykonania obliczeń każdego.

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

Następujące przykładowe dane wyjściowe jest na komputerze z czterema procesorami.

serial time: 4353
parallel time: 1248

Top

Kompilowanie kodu

Aby skompilować kod, skopiuj go i następnie wkleić go w projekcie programu Visual Studio lub wkleić go w pliku o nazwie równolegle bitonic-sort.cpp , a następnie uruchom następujące polecenie w oknie wiersza polecenia usługi Visual Studio.

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

Stabilne Programowanie

W tym przykładzie parallel_invoke algorytm zamiast concurrency::task_group klasy, ponieważ okres istnienia każdej grupy zadań nie wykracza poza funkcją.Zaleca się używanie parallel_invoke gdy można ponieważ mniej wykonanie obciążenie niż task group obiektów, a więc pozwala pisać lepsze wykonywanie kodu.

Niektóre algorytmy równoległe wersje lepiej wykonywać tylko wtedy, gdy wystarczająca pracy.Na przykład parallel_bitonic_merge funkcja wywołuje wersję szeregowego, bitonic_merge, jeśli istnieją elementy 500 lub mniejszej liczby w sekwencji.Można także zaplanować ogólnej strategii sortowania na podstawie ilości pracy.Na przykład może być bardziej efektywne użyć szeregowego wersja algorytmu szybkie sortowanie Jeśli tablica zawiera mniej niż 500 elementów, jak pokazano w następującym przykładzie:

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

Jak w przypadku wszelkich algorytmu równoległego zaleca się, profil i kod odpowiednio dostroić.

Zobacz też

Informacje

Funkcja parallel_invoke

Koncepcje

Zadanie równoległości (współbieżności Runtime)