Algorytmy równoległe

Biblioteka wzorców równoległych (PPL) udostępnia algorytmy, które współbieżnie wykonują pracę nad kolekcjami danych. Te algorytmy przypominają te, które są dostarczane przez standardową bibliotekę języka C++.

Algorytmy równoległe składają się z istniejących funkcji w środowisku uruchomieniowym współbieżności. Na przykład algorytm concurrency::p arallel_for używa obiektu concurrency::structured_task_group do wykonywania iteracji pętli równoległej. Partycje parallel_for algorytmu działają w optymalny sposób, biorąc pod uwagę dostępną liczbę zasobów obliczeniowych.

Sekcje

• Algorytm parallel_for

• Algorytm parallel_for_each

• Algorytm parallel_invoke

• Algorytmy parallel_transform i parallel_reduce

  • Algorytm parallel_transform

  • Algorytm parallel_reduce

  • Przykład: wykonywanie mapowania i redukcji równolegle

• Praca partycjonowania

• Sortowanie równoległe

  • Wybieranie algorytmu sortowania

Algorytm parallel_for

Współbieżność ::p arallel_for algorytm wielokrotnie wykonuje to samo zadanie równolegle. Każde z tych zadań jest sparametryzowane przez wartość iteracji. Ten algorytm jest przydatny, gdy masz treść pętli, która nie współużytkuje zasobów między iteracjami tej pętli.

Algorytm parallel_for partycjonuje zadania w optymalny sposób na potrzeby wykonywania równoległego. Używa on algorytmu kradzieży pracy i kradzieży zakresu w celu zrównoważenia tych partycji, gdy obciążenia są niezrównoważone. Gdy iteracja jednej pętli blokuje współpracę, środowisko uruchomieniowe redystrybuuje zakres iteracji przypisanych do bieżącego wątku do innych wątków lub procesorów. Podobnie, gdy wątek ukończy zakres iteracji, środowisko uruchomieniowe ponownie dystrybuuje pracę z innych wątków do tego wątku. Algorytm parallel_for obsługuje również zagnieżdżony równoległość. Gdy jedna pętla równoległa zawiera inną pętlę równoległą, środowisko uruchomieniowe koordynuje zasoby przetwarzania między ciałami pętli w wydajny sposób na potrzeby równoległego wykonywania.

Algorytm parallel_for ma kilka przeciążonych wersji. Pierwsza wersja przyjmuje wartość początkową, wartość końcową i funkcję pracy (wyrażenie lambda, obiekt funkcji lub wskaźnik funkcji). Druga wersja przyjmuje wartość początkową, wartość końcową, wartość do wykonania krok i funkcję pracy. Pierwsza wersja tej funkcji używa wartości 1 jako wartości kroku. Pozostałe wersje przyjmują obiekty partycjonatora, które umożliwiają określenie, jak parallel_for powinny być podzielone zakresy partycji między wątkami. Partycjonatory zostały szczegółowo wyjaśnione w sekcji Partycjonowanie pracy w tym dokumencie.

Możesz przekonwertować wiele for pętli, aby użyć polecenia parallel_for. parallel_for Jednak algorytm różni się od instrukcji for w następujący sposób:

• Algorytm parallel_for parallel_for nie wykonuje zadań wstępnie określonej kolejności.

• Algorytm parallel_for nie obsługuje dowolnych warunków zakończenia. Algorytm zatrzymuje się, gdy bieżąca parallel_for wartość zmiennej iteracji jest mniejsza niż last.

• Parametr _Index_type typu musi być typem całkowitym. Ten typ całkowity może być podpisany lub niepodpisany.

• Iteracja pętli musi być przekazywana do przodu. Algorytm parallel_for zgłasza wyjątek typu std::invalid_argument , jeśli _Step parametr jest mniejszy niż 1.

• Mechanizm obsługi wyjątków dla algorytmu parallel_for różni się od for mechanizmu pętli. Jeśli wiele wyjątków występuje jednocześnie w treści pętli równoległej, środowisko uruchomieniowe propaguje tylko jeden z wyjątków do wątku o nazwie parallel_for. Ponadto, gdy iteracja jednej pętli zgłasza wyjątek, środowisko uruchomieniowe nie natychmiast zatrzymuje ogólnej pętli. Zamiast tego pętla jest umieszczana w stanie anulowanym, a środowisko uruchomieniowe odrzuca wszystkie zadania, które jeszcze nie zostały uruchomione. Aby uzyskać więcej informacji na temat obsługi wyjątków i algorytmów równoległych, zobacz Obsługa wyjątków.

parallel_for Mimo że algorytm nie obsługuje dowolnych warunków zakończenia, można użyć anulowania, aby zatrzymać wszystkie zadania. Aby uzyskać więcej informacji na temat anulowania, zobacz Anulowanie w PPL.

Uwaga

Koszt planowania wynikający z równoważenia obciążenia i obsługi funkcji, takich jak anulowanie, może nie przezwyciężyć korzyści wynikających z równoległego wykonywania treści pętli, zwłaszcza gdy treść pętli jest stosunkowo mała. Możesz zminimalizować to obciążenie, używając partycjonatora w pętli równoległej. Aby uzyskać więcej informacji, zobacz Partycjonowanie pracy w dalszej części tego dokumentu.

Przykład

W poniższym przykładzie przedstawiono podstawową strukturę algorytmu parallel_for . W tym przykładzie do konsoli jest drukowana każda wartość w zakresie [1, 5] równolegle.

// parallel-for-structure.cpp
// compile with: /EHsc
#include <ppl.h>
#include <array>
#include <sstream>
#include <iostream>

using namespace concurrency;
using namespace std;

int wmain()
{
   // Print each value from 1 to 5 in parallel.
   parallel_for(1, 6, [](int value) {
      wstringstream ss;
      ss << value << L' ';
      wcout << ss.str();
   });
}

W tym przykładzie są generowane następujące przykładowe dane wyjściowe:

1 2 4 3 5

parallel_for Ponieważ algorytm działa równolegle na każdym elemencie, kolejność drukowania wartości w konsoli będzie się różnić.

Pełny przykład użycia algorytmu parallel_for można znaleźć w temacie How to: Write a parallel_for Loop (Instrukcje: pisanie pętli parallel_for).

[Top]

Algorytm parallel_for_each

Współbieżność ::p arallel_for_each algorytm wykonuje zadania w kontenerze iteracyjnym, takim jak te dostarczane przez bibliotekę standardową języka C++, równolegle. Używa tej samej logiki partycjonowania, która jest używana przez parallel_for algorytm.

Algorytm parallel_for_each przypomina algorytm std::for_each biblioteki standardowej języka C++, z tą różnicą, że parallel_for_each algorytm wykonuje zadania współbieżnie. Podobnie jak inne algorytmy równoległe, parallel_for_each nie wykonuje zadań w określonej kolejności.

parallel_for_each Mimo że algorytm działa zarówno na iteratorach przesyłania dalej, jak i iteratorach dostępu losowego, działa lepiej z iteratorami dostępu losowego.

Przykład

W poniższym przykładzie przedstawiono podstawową strukturę algorytmu parallel_for_each . W tym przykładzie do konsoli jest drukowana każda wartość obiektu std::array równolegle.

// parallel-for-each-structure.cpp
// compile with: /EHsc
#include <ppl.h>
#include <array>
#include <sstream>
#include <iostream>

using namespace concurrency;
using namespace std;

int wmain()
{
   // Create an array of integer values.
   array<int, 5> values = { 1, 2, 3, 4, 5 };

   // Print each value in the array in parallel.
   parallel_for_each(begin(values), end(values), [](int value) {
      wstringstream ss;
      ss << value << L' ';
      wcout << ss.str();
   });
}
/* Sample output:
   5 4 3 1 2
*/

W tym przykładzie są generowane następujące przykładowe dane wyjściowe:

4 5 1 2 3

parallel_for_each Ponieważ algorytm działa równolegle na każdym elemencie, kolejność drukowania wartości w konsoli będzie się różnić.

Pełny przykład użycia algorytmu parallel_for_each można znaleźć w temacie How to: Write a parallel_for_each Loop (Instrukcje: pisanie pętli parallel_for_each).

[Top]

Algorytm parallel_invoke

Algorytm concurrency::p arallel_invoke wykonuje równolegle zestaw zadań. Nie zwraca się do momentu zakończenia każdego zadania. Ten algorytm jest przydatny, gdy masz kilka niezależnych zadań, które chcesz wykonać w tym samym czasie.

Algorytm parallel_invoke przyjmuje jako parametry serii funkcji roboczych (funkcje lambda, obiekty funkcji lub wskaźniki funkcji). Algorytm parallel_invoke jest przeciążony, aby przyjmować od dwóch do dziesięciu parametrów. Każda przekazana parallel_invoke funkcja musi przyjmować zero parametrów.

Podobnie jak inne algorytmy równoległe, parallel_invoke nie wykonuje zadań w określonej kolejności. W temacie Równoległość zadań wyjaśniono, jak parallel_invoke algorytm odnosi się do zadań i grup zadań.

Przykład

W poniższym przykładzie przedstawiono podstawową strukturę algorytmu parallel_invoke . Ten przykład współbieżnie wywołuje twice funkcję w trzech zmiennych lokalnych i wyświetla wynik w konsoli.

// parallel-invoke-structure.cpp
// compile with: /EHsc
#include <ppl.h>
#include <string>
#include <iostream>

using namespace concurrency;
using namespace std;

// Returns the result of adding a value to itself.
template <typename T>
T twice(const T& t) {
   return t + t;
}

int wmain()
{
   // Define several values.
   int n = 54;
   double d = 5.6;
   wstring s = L"Hello";

   // Call the twice function on each value concurrently.
   parallel_invoke(
      [&n] { n = twice(n); },
      [&d] { d = twice(d); },
      [&s] { s = twice(s); }
   );

   // Print the values to the console.
   wcout << n << L' ' << d << L' ' << s << endl;
}

Ten przykład generuje następujące wyniki:

108 11.2 HelloHello

Aby zapoznać się z kompletnymi przykładami korzystającymi z algorytmu parallel_invoke , zobacz How to: Use parallel_invoke to Write a Parallel Sort Routine ( Instrukcje: używanie parallel_invoke do wykonywania operacji równoległych).

[Top]

Algorytmy parallel_transform i parallel_reduce

Algorytmy concurrency::p arallel_transform i concurrency::p arallel_reduce są równoległymi wersjami algorytmów biblioteki standardowej języka C++ std::transform i std::accumulate. Wersje środowiska uruchomieniowego współbieżności zachowują się jak wersje standardowej biblioteki języka C++, z tą różnicą, że kolejność operacji nie jest określana, ponieważ są wykonywane równolegle. Użyj tych algorytmów podczas pracy z zestawem, który jest wystarczająco duży, aby uzyskać korzyści z wydajności i skalowalności z przetwarzania równolegle.

Ważne

Algorytmy parallel_transform i parallel_reduce obsługują tylko losowy dostęp, dwukierunkowy i iteratory do przodu, ponieważ te iteratory generują stabilne adresy pamięci. Ponadto te iteratory muszą generować wartości inne niżconst l.

Algorytm parallel_transform

Algorytm umożliwia wykonywanie wielu operacji przetwarzania parallel transform równoległego danych. Można na przykład:

• Dostosuj jasność obrazu i wykonaj inne operacje przetwarzania obrazów.

• Sumuj lub weź kropkę między dwoma wektorami i wykonaj inne obliczenia liczbowe na wektorach.

• Wykonaj śledzenie promieni 3-W, gdzie każda iteracja odnosi się do jednego piksela, który musi być renderowany.

W poniższym przykładzie przedstawiono podstawową strukturę używaną do wywoływania algorytmu parallel_transform . Ten przykład neguje każdy element obiektu std::vector na dwa sposoby. Pierwszy sposób używa wyrażenia lambda. Drugi sposób używa metody std::negate, która pochodzi z std::unary_function.

// basic-parallel-transform.cpp
// compile with: /EHsc
#include <ppl.h>
#include <random>

using namespace concurrency;
using namespace std;

int wmain()
{
    // Create a large vector that contains random integer data.
    vector<int> values(1250000);
    generate(begin(values), end(values), mt19937(42));

    // Create a vector to hold the results.
    // Depending on your requirements, you can also transform the 
    // vector in-place.
    vector<int> results(values.size());

    // Negate each element in parallel.
    parallel_transform(begin(values), end(values), begin(results), [](int n) {
        return -n;
    });

    // Alternatively, use the negate class to perform the operation.
    parallel_transform(begin(values), end(values), begin(values), negate<int>());
}

Ostrzeżenie

W tym przykładzie pokazano podstawowe użycie metody parallel_transform. Ponieważ funkcja pracy nie wykonuje znacznej ilości pracy, znaczny wzrost wydajności nie jest oczekiwany w tym przykładzie.

Algorytm parallel_transform ma dwa przeciążenia. Pierwsze przeciążenie przyjmuje jeden zakres danych wejściowych i funkcję jednoargumentową. Funkcja jednoargumentowa może być wyrażeniem lambda, które przyjmuje jeden argument, obiekt funkcji lub typ pochodzący z unary_functionklasy . Drugie przeciążenie przyjmuje dwa zakresy danych wejściowych i funkcję binarną. Funkcja binarna może być wyrażeniem lambda, które przyjmuje dwa argumenty, obiekt funkcji lub typ pochodzący z std::binary_function. Poniższy przykład ilustruje te różnice.

//
// Demonstrate use of parallel_transform together with a unary function.

// This example uses a lambda expression.
parallel_transform(begin(values), end(values), 
    begin(results), [](int n) { 
        return -n;
    });

// Alternatively, use the negate class:
parallel_transform(begin(values), end(values), 
    begin(results), negate<int>());

//
// Demonstrate use of parallel_transform together with a binary function.

// This example uses a lambda expression.
parallel_transform(begin(values), end(values), begin(results), 
    begin(results), [](int n, int m) {
        return n * m;
    });

// Alternatively, use the multiplies class:
parallel_transform(begin(values), end(values), begin(results), 
    begin(results), multiplies<int>());

Ważne

Iterator, który podajesz dla danych wyjściowych, parallel_transform musi całkowicie nakładać się na iterator wejściowy lub nie nakładać się w ogóle. Zachowanie tego algorytmu jest nieokreślone, jeśli iteratory wejściowe i wyjściowe częściowo nakładają się na siebie.

Algorytm parallel_reduce

Algorytm parallel_reduce jest przydatny, gdy masz sekwencję operacji, które spełniają właściwość asocjacyjną. (Ten algorytm nie wymaga właściwości komutacyjnej). Poniżej przedstawiono niektóre operacje, które można wykonać za pomocą parallel_reducepolecenia :

• Mnożenie sekwencji macierzy w celu utworzenia macierzy.

• Mnożenie wektora przez sekwencję macierzy w celu utworzenia wektora.

• Oblicz długość sekwencji ciągów.

• Połącz listę elementów, takich jak ciągi, w jeden element.

Poniższy podstawowy przykład pokazuje, jak używać algorytmu parallel_reduce do łączenia sekwencji ciągów w jeden ciąg. Podobnie jak w przypadku przykładów dla parallel_transformprogramu , wzrost wydajności nie jest oczekiwany w tym podstawowym przykładzie.

// basic-parallel-reduce.cpp
// compile with: /EHsc
#include <ppl.h>
#include <iostream>
#include <string>
#include <vector>

using namespace concurrency;
using namespace std;

int wmain()
{
  // Create a vector of strings.
  vector<wstring> words{
      L"Lorem ",
      L"ipsum ",
      L"dolor ",
      L"sit ",
      L"amet, ",
      L"consectetur ",
      L"adipiscing ",
      L"elit."};
      
  // Reduce the vector to one string in parallel.
  wcout << parallel_reduce(begin(words), end(words), wstring()) << endl;
}

/* Output:
   Lorem ipsum dolor sit amet, consectetur adipiscing elit.
*/

W wielu przypadkach można traktować parallel_reduce jako skrót użycia algorytmu parallel_for_each razem z klasą concurrency::combinable .

Przykład: wykonywanie mapowania i redukcji równolegle

Operacja mapy stosuje funkcję do każdej wartości w sekwencji. Operacja redukcji łączy elementy sekwencji w jedną wartość. Możesz użyć standardowej biblioteki C++ std::transform i std::accumulate , aby wykonywać operacje mapowania i redukcji. Jednak w przypadku wielu problemów można użyć algorytmu parallel_transform , aby wykonać operację mapy równolegle, a parallel_reduce algorytm wykonuje operację redukcji równolegle.

Poniższy przykład porównuje czas potrzebny do obliczenia sumy liczb pierwszych w sposób seryjny i równoległy. Faza mapy przekształca wartości inne niż prime na 0, a faza redukcji sumuje wartości.

// parallel-map-reduce-sum-of-primes.cpp
// compile with: /EHsc
#include <windows.h>
#include <ppl.h>
#include <array>
#include <numeric>
#include <iostream>

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

// Determines whether the input value is prime.
bool is_prime(int n)
{
   if (n < 2)
      return false;
   for (int i = 2; i < n; ++i)
   {
      if ((n % i) == 0)
         return false;
   }
   return true;
}

int wmain()
{   
   // Create an array object that contains 200000 integers.
   array<int, 200000> a;

   // Initialize the array such that a[i] == i.
   iota(begin(a), end(a), 0);

   int prime_sum;
   __int64 elapsed;

   // Compute the sum of the numbers in the array that are prime.
   elapsed = time_call([&] {
       transform(begin(a), end(a), begin(a), [](int i) { 
         return is_prime(i) ? i : 0; 
      });
      prime_sum = accumulate(begin(a), end(a), 0);
   });   
   wcout << prime_sum << endl;   
   wcout << L"serial time: " << elapsed << L" ms" << endl << endl;

   // Now perform the same task in parallel.
   elapsed = time_call([&] {
      parallel_transform(begin(a), end(a), begin(a), [](int i) { 
         return is_prime(i) ? i : 0; 
      });
      prime_sum = parallel_reduce(begin(a), end(a), 0);
   });
   wcout << prime_sum << endl;
   wcout << L"parallel time: " << elapsed << L" ms" << endl << endl;
}
/* Sample output:
   1709600813
   serial time: 7406 ms
   
   1709600813
   parallel time: 1969 ms
*/

Aby zapoznać się z innym przykładem równoległym wykonywania operacji mapy i redukcji, zobacz Instrukcje: wykonywanie operacji mapowania i redukcji równolegle.

[Top]

Praca partycjonowania

Aby zrównoleglić operację w źródle danych, podstawowym krokiem jest podzielenie źródła na wiele sekcji, do których można uzyskiwać dostęp współbieżnie przez wiele wątków. Partycjonator określa, w jaki sposób algorytm równoległy powinien partycjonować zakresy między wątkami. Jak wyjaśniono wcześniej w tym dokumencie, PPL używa domyślnego mechanizmu partycjonowania, który tworzy początkowe obciążenie, a następnie używa algorytmu kradzieży pracy i zakresu kradzieży, aby zrównoważyć te partycje, gdy obciążenia są niezrównoważone. Na przykład po zakończeniu iteracji jednej pętli zakres iteracji środowisko uruchomieniowe ponownie dystrybuuje pracę z innych wątków do tego wątku. Jednak w przypadku niektórych scenariuszy warto określić inny mechanizm partycjonowania, który lepiej nadaje się do twojego problemu.

Algorytmy parallel_for, parallel_for_eachi parallel_transform zapewniają przeciążone wersje, które przyjmują dodatkowy parametr , _Partitioner. Ten parametr definiuje typ partycjonatora, który dzieli pracę. Oto rodzaje partycjonatorów, które definiuje PPL:

współbieżność::affinity_partitioner
Dzieli pracę na stałą liczbę zakresów (zazwyczaj liczbę wątków roboczych, które są dostępne do pracy w pętli). Ten typ partycjonatora static_partitionerprzypomina element , ale poprawia koligację pamięci podręcznej, mapując zakresy na wątki robocze. Ten typ partycjonatora może zwiększyć wydajność, gdy pętla jest wykonywana w tym samym zestawie danych wiele razy (na przykład pętla w pętli) i dane pasują do pamięci podręcznej. Ten partycjonator nie uczestniczy w pełni w anulowaniu. Nie używa również semantyki blokującej współpracy i dlatego nie może być używany z pętlami równoległymi, które mają zależność przesyłania dalej.

concurrency::auto_partitioner
Dzieli pracę na początkową liczbę zakresów (zazwyczaj liczbę wątków roboczych, które są dostępne do pracy w pętli). Środowisko uruchomieniowe domyślnie używa tego typu, gdy nie wywołujesz przeciążonego algorytmu równoległego, który przyjmuje _Partitioner parametr. Każdy zakres można podzielić na podzakresy, a tym samym umożliwić równoważenie obciążenia. Po zakończeniu szeregu zadań środowisko uruchomieniowe redystrybuuje zakresy podrzędne pracy z innych wątków do tego wątku. Użyj tego partycjonatora, jeśli obciążenie nie mieści się w jednej z innych kategorii lub potrzebujesz pełnej obsługi anulowania lub blokowania współpracy.

concurrency::simple_partitioner
Dzieli pracę na zakresy, tak aby każdy zakres miał co najmniej liczbę iteracji określonych przez dany rozmiar fragmentu. Ten typ partycjonatora uczestniczy w równoważeniu obciążenia; jednak środowisko uruchomieniowe nie dzieli zakresów na podzakresy. Dla każdego procesu roboczego środowisko uruchomieniowe sprawdza anulowanie i wykonuje równoważenie obciążenia po _Chunk_size zakończeniu iteracji.

współbieżność::static_partitioner
Dzieli pracę na stałą liczbę zakresów (zazwyczaj liczbę wątków roboczych, które są dostępne do pracy w pętli). Ten typ partycjonatora może zwiększyć wydajność, ponieważ nie korzysta z kradzieży pracy i dlatego ma mniejsze obciążenie. Użyj tego typu partycjonatora, gdy każda iteracja pętli równoległej wykonuje stałą i jednolitą ilość pracy i nie wymaga obsługi anulowania ani blokowania współpracy.

Ostrzeżenie

Algorytmy parallel_for_each i parallel_transform obsługują tylko kontenery korzystające z iteratorów dostępu losowego (takich jak std::vector) dla partycji statycznych, prostych i koligacji. Użycie kontenerów korzystających z iteratorów dwukierunkowych i przesyłania dalej powoduje błąd czasu kompilacji. Domyślny moduł partycjonowania , auto_partitionerobsługuje wszystkie trzy z tych typów iteratorów.

Zazwyczaj te partycjonatory są używane w taki sam sposób, z wyjątkiem .affinity_partitioner Większość typów partycjonatora nie utrzymuje stanu i nie jest modyfikowana przez środowisko uruchomieniowe. W związku z tym można utworzyć te obiekty partycjonatora w lokacji wywołania, jak pokazano w poniższym przykładzie.

// static-partitioner.cpp
// compile with: /EHsc
#include <ppl.h>

using namespace concurrency;

void DoWork(int n)
{
    // TODO: Perform a fixed amount of work...
}

int wmain()
{
    // Use a static partitioner to perform a fixed amount of parallel work.
    parallel_for(0, 100000, [](int n) {
        DoWork(n);
    }, static_partitioner());
}

Należy jednak przekazać affinity_partitioner obiekt jako odwołanie inne niż l-wartośćconst, aby algorytm mógł przechowywać stan dla przyszłych pętli w celu ponownego użycia. W poniższym przykładzie przedstawiono podstawową aplikację, która wykonuje tę samą operację na zestawie danych równolegle wiele razy. Użycie funkcji może poprawić wydajność, affinity_partitioner ponieważ tablica może zmieścić się w pamięci podręcznej.

// affinity-partitioner.cpp
// compile with: /EHsc
#include <ppl.h>
#include <array>

using namespace concurrency;
using namespace std;

int wmain()
{
    // Create an array and fill it with zeroes.
    array<unsigned char, 8 * 1024> data;
    data.fill(0);

    // Use an affinity partitioner to perform parallel work on data
    // that is likely to remain in cache.
    // We use the same affinitiy partitioner throughout so that the 
    // runtime can schedule work to occur at the same location for each 
    // iteration of the outer loop.

    affinity_partitioner ap;
    for (int i = 0; i < 100000; i++)
    {
        parallel_for_each(begin(data), end(data), [](unsigned char& c)
        {
            c++;
        }, ap);
    }
}

Uwaga

Należy zachować ostrożność podczas modyfikowania istniejącego kodu, który opiera się na współpracy blokującej semantyki do użycia static_partitioner lub affinity_partitioner. Te typy partycjonatora nie używają równoważenia obciążenia ani kradzieży zakresu, a tym samym mogą zmieniać zachowanie aplikacji.

Najlepszym sposobem określenia, czy używać partycjonatora w danym scenariuszu, jest eksperymentowanie i mierzenie, jak długo trwa wykonywanie operacji w ramach reprezentatywnych obciążeń i konfiguracji komputerów. Na przykład partycjonowanie statyczne może zapewnić znaczną szybkość pracy na komputerze wielordzeniowym, który ma tylko kilka rdzeni, ale może to spowodować spowolnienie na komputerach, które mają stosunkowo wiele rdzeni.

[Top]

Sortowanie równoległe

PPL udostępnia trzy algorytmy sortowania: concurrency::p arallel_sort, concurrency::p arallel_buffered_sort i concurrency::p arallel_radixsort. Te algorytmy sortowania są przydatne, gdy masz zestaw danych, który może korzystać z sortowania równolegle. W szczególności sortowanie równoległe jest przydatne, gdy masz duży zestaw danych lub gdy używasz operacji porównywania kosztownego obliczeń w celu sortowania danych. Każdy z tych algorytmów sortuje elementy na miejscu.

Algorytmy parallel_sort i parallel_buffered_sort są algorytmami opartymi na porównaniach. Oznacza to, że porównują elementy według wartości. Algorytm parallel_sort nie ma dodatkowych wymagań dotyczących pamięci i jest odpowiedni do sortowania ogólnego przeznaczenia. Algorytm parallel_buffered_sort może działać lepiej niż parallel_sort, ale wymaga miejsca O(N).

Algorytm parallel_radixsort jest oparty na skrótach. Oznacza to, że używa kluczy całkowitych do sortowania elementów. Za pomocą kluczy ten algorytm może bezpośrednio obliczyć miejsce docelowe elementu zamiast porównywania. Podobnie jak parallel_buffered_sort, ten algorytm wymaga miejsca O(N).

Poniższa tabela zawiera podsumowanie ważnych właściwości trzech algorytmów sortowania równoległego.

Algorytm	opis	Mechanizm sortowania	Stabilność sortowania	Wymagania dotyczące pamięci	Złożoność czasu	Dostęp iteratora
parallel_sort	Sortowanie na podstawie porównania ogólnego przeznaczenia.	Na podstawie porównania (rosnąco)	Niestabilny	Brak	O((N/P)log(N/P) + 2N((P-1)/P))	Losowe
parallel_buffered_sort	Szybsze sortowanie oparte na porównaniach ogólnego przeznaczenia, które wymaga miejsca O(N).	Na podstawie porównania (rosnąco)	Niestabilny	Wymaga dodatkowego miejsca O(N)	O((N/P)log(N))	Losowe
parallel_radixsort	Sortowanie oparte na kluczach liczb całkowitych, które wymaga spacji O(N).	Oparte na skrótach	Stable	Wymaga dodatkowego miejsca O(N)	O(N/P)	Losowe

Na poniższej ilustracji przedstawiono ważne właściwości trzech algorytmów sortowania równoległego bardziej graficznie.

Te algorytmy sortowania równoległego są zgodne z regułami anulowania i obsługi wyjątków. Aby uzyskać więcej informacji na temat anulowania i obsługi wyjątków w środowisku uruchomieniowym współbieżności, zobacz Anulowanie algorytmów równoległych i obsługa wyjątków.

Napiwek

Te algorytmy sortowania równoległego obsługują semantyka przenoszenia. Możesz zdefiniować operator przypisania przenoszenia, aby umożliwić wydajniejsze wykonywanie operacji zamiany. Aby uzyskać więcej informacji na temat semantyki przenoszenia i operatora przypisania przenoszenia, zobacz Rvalue Reference Deklarator: &&, And Move Assignment Operators (C++). Jeśli nie podasz operatora przypisania przenoszenia lub funkcji zamiany, algorytmy sortowania używają konstruktora kopiowania.

Poniższy podstawowy przykład przedstawia sposób sortowania vector int wartości za pomocą polecenia parallel_sort . Domyślnie parallel_sort do porównywania wartości używa parametru std::less .

// basic-parallel-sort.cpp
// compile with: /EHsc
#include <ppl.h>
#include <random>
#include <iostream>

using namespace concurrency;
using namespace std;

int wmain()
{
    // Create and sort a large vector of random values.
    vector<int> values(25000000);
    generate(begin(values), end(values), mt19937(42));
    parallel_sort(begin(values), end(values));

    // Print a few values.
    wcout << "V(0)        = " << values[0] << endl;
    wcout << "V(12500000) = " << values[12500000] << endl;
    wcout << "V(24999999) = " << values[24999999] << endl;
} 
/* Output:
   V(0)        = -2147483129
   V(12500000) = -427327
   V(24999999) = 2147483311
*/

W tym przykładzie pokazano, jak udostępnić niestandardową funkcję porównywania. Używa metody std::complex::real, aby sortować wartości podwójne std::complex<> w kolejności rosnącej.

// For this example, ensure that you add the following #include directive:
// #include <complex>

// Create and sort a large vector of random values.
vector<complex<double>> values(25000000);
generate(begin(values), end(values), mt19937(42));
parallel_sort(begin(values), end(values),
    [](const complex<double>& left, const complex<double>& right) {
        return left.real() < right.real();
    });

// Print a few values.
wcout << "V(0)        = " << values[0] << endl;
wcout << "V(12500000) = " << values[12500000] << endl;
wcout << "V(24999999) = " << values[24999999] << endl;
/* Output:
   V(0)        = (383,0)
   V(12500000) = (2.1479e+009,0)
   V(24999999) = (4.29497e+009,0)
*/

W tym przykładzie pokazano, jak udostępnić algorytmowi funkcję skrótu parallel_radixsort . W tym przykładzie posortowane są punkty 3-W. Punkty są sortowane na podstawie ich odległości od punktu odniesienia.

// parallel-sort-points.cpp
// compile with: /EHsc
#include <ppl.h>
#include <random>
#include <iostream>

using namespace concurrency;
using namespace std;

// Defines a 3-D point.
struct Point
{
    int X;
    int Y;
    int Z;
};

// Computes the Euclidean distance between two points.
size_t euclidean_distance(const Point& p1, const Point& p2)
{
    int dx = p1.X - p2.X;
    int dy = p1.Y - p2.Y;
    int dz = p1.Z - p2.Z;
    return static_cast<size_t>(sqrt((dx*dx) + (dy*dy) + (dz*dz)));
}

int wmain()
{
    // The central point of reference.
    const Point center = { 3, 2, 7 };

    // Create a few random Point values.
    vector<Point> values(7);
    mt19937 random(42);
    generate(begin(values), end(values), [&random] {
        Point p = { random()%10, random()%10, random()%10 };
        return p;
    });

    // Print the values before sorting them.
    wcout << "Before sorting:" << endl;
    for_each(begin(values), end(values), [center](const Point& p) {
        wcout << L'(' << p.X << L"," << p.Y << L"," << p.Z 
              << L") D = " << euclidean_distance(p, center) << endl;
    });
    wcout << endl;

    // Sort the values based on their distances from the reference point.
    parallel_radixsort(begin(values), end(values), 
        [center](const Point& p) -> size_t {
            return euclidean_distance(p, center);
        });

    // Print the values after sorting them.
    wcout << "After sorting:" << endl;
    for_each(begin(values), end(values), [center](const Point& p) {
        wcout << L'(' << p.X << L"," << p.Y << L"," << p.Z 
              << L") D = " << euclidean_distance(p, center) << endl;
    });
    wcout << endl;
} 
/* Output:
    Before sorting:
    (2,7,6) D = 5
    (4,6,5) D = 4
    (0,4,0) D = 7
    (3,8,4) D = 6
    (0,4,1) D = 7
    (2,5,5) D = 3
    (7,6,9) D = 6

    After sorting:
    (2,5,5) D = 3
    (4,6,5) D = 4
    (2,7,6) D = 5
    (3,8,4) D = 6
    (7,6,9) D = 6
    (0,4,0) D = 7
    (0,4,1) D = 7
*/

Na ilustracji w tym przykładzie użyto stosunkowo małego zestawu danych. Możesz zwiększyć początkowy rozmiar wektora, aby eksperymentować z ulepszeniami wydajności w przypadku większych zestawów danych.

W tym przykładzie użyto wyrażenia lambda jako funkcji skrótu. Możesz również użyć jednej z wbudowanych implementacji klasy std::hash lub zdefiniować własną specjalizację. Można również użyć niestandardowego obiektu funkcji skrótu, jak pokazano w tym przykładzie:

// Functor class for computing the distance between points.
class hash_distance
{
public:
    hash_distance(const Point& reference)
        : m_reference(reference)
    {
    }

    size_t operator()(const Point& pt) const {
        return euclidean_distance(pt, m_reference);
    }

private:
    Point m_reference;
};

 

// Use hash_distance to compute the distance between points.
parallel_radixsort(begin(values), end(values), hash_distance(center));

Funkcja skrótu musi zwracać typ całkowity (std::is_integral::value musi mieć wartość true). Ten typ całkowity musi być konwertowany na typ size_t.

Wybieranie algorytmu sortowania

W wielu przypadkach parallel_sort zapewnia najlepszą równowagę szybkości i wydajności pamięci. Jednak wraz ze wzrostem rozmiaru zestawu danych, liczbą dostępnych procesorów lub złożonością funkcji parallel_buffered_sort porównania lub parallel_radixsort lepszą wydajnością. Najlepszym sposobem określenia algorytmu sortowania używanego w danym scenariuszu jest eksperymentowanie i mierzenie, jak długo trwa sortowanie typowych danych w ramach reprezentatywnych konfiguracji komputerów. Podczas wybierania strategii sortowania należy pamiętać o poniższych wskazówkach.

• Rozmiar zestawu danych. W tym dokumencie mały zestaw danych zawiera mniej niż 1000 elementów, średni zestaw danych zawiera od 10 000 do 100 000 elementów, a duży zestaw danych zawiera ponad 100 000 elementów.

• Ilość pracy wykonywanej przez funkcję porównywania lub funkcję skrótu.

• Ilość dostępnych zasobów obliczeniowych.

• Cechy zestawu danych. Na przykład jeden algorytm może działać dobrze w przypadku danych, które są już prawie posortowane, ale nie są również danymi, które są całkowicie niesortowane.

• Rozmiar fragmentu. Opcjonalny _Chunk_size argument określa, kiedy algorytm przełącza się z równoległej do implementacji sortowania szeregowego, ponieważ dzieli ogólny sortowanie na mniejsze jednostki pracy. Jeśli na przykład podasz wartość 512, algorytm przełącza się do implementacji szeregowej, gdy jednostka pracy zawiera 512 lub mniej elementów. Implementacja szeregowa może poprawić ogólną wydajność, ponieważ eliminuje obciążenie wymagane do równoległego przetwarzania danych.

Może nie być warto sortować małego zestawu danych równolegle, nawet jeśli masz dużą liczbę dostępnych zasobów obliczeniowych lub funkcji porównania lub funkcji skrótu wykonuje stosunkowo dużą ilość pracy. Do sortowania małych zestawów danych można użyć funkcji std::sort . (parallel_sort i parallel_buffered_sort wywołanie sort podczas określania rozmiaru fragmentu, który jest większy niż zestaw danych; jednak parallel_buffered_sort konieczne byłoby przydzielenie miejsca O(N), co może zająć dodatkowy czas z powodu rywalizacji o blokadę lub alokację pamięci.

Jeśli musisz zaoszczędzić pamięć lub alokator pamięci podlega rywalizacji o blokadę, użyj polecenia parallel_sort , aby posortować zestaw danych o średniej wielkości. parallel_sort nie wymaga dodatkowego miejsca; inne algorytmy wymagają miejsca O(N).

Służy parallel_buffered_sort do sortowania średnich zestawów danych i gdy aplikacja spełnia dodatkowe wymaganie dotyczące miejsca O(N). parallel_buffered_sort może być szczególnie przydatne, gdy masz dużą liczbę zasobów obliczeniowych lub kosztowną funkcję porównywania lub funkcji skrótu.

Służy parallel_radixsort do sortowania dużych zestawów danych i gdy aplikacja spełnia dodatkowe wymagania dotyczące miejsca O(N). parallel_radixsort może być szczególnie przydatne, gdy równoważna operacja porównania jest droższa lub gdy obie operacje są kosztowne.

Uwaga

Zaimplementowanie dobrej funkcji skrótu wymaga znajomości zakresu zestawów danych i sposobu przekształcania każdego elementu w zestawie danych na odpowiadającą niepodpisaną wartość. Ponieważ operacja skrótu działa na niepodpisanych wartościach, rozważ inną strategię sortowania, jeśli nie można wygenerować niepodpisanych wartości skrótu.

Poniższy przykład porównuje wydajność sort, parallel_sort, parallel_buffered_sorti parallel_radixsort z tym samym dużym zestawem danych losowych.

// choosing-parallel-sort.cpp
// compile with: /EHsc
#include <ppl.h>
#include <random>
#include <iostream>
#include <windows.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 size_t DATASET_SIZE = 10000000;

// Create
// Creates the dataset for this example. Each call
// produces the same predefined sequence of random data.
vector<size_t> GetData()
{
    vector<size_t> data(DATASET_SIZE);
    generate(begin(data), end(data), mt19937(42));
    return data;
}

int wmain()
{
    // Use std::sort to sort the data.
    auto data = GetData();
    wcout << L"Testing std::sort...";
    auto elapsed = time_call([&data] { sort(begin(data), end(data)); });
    wcout << L" took " << elapsed << L" ms." <<endl;

    // Use concurrency::parallel_sort to sort the data.
    data = GetData();
    wcout << L"Testing concurrency::parallel_sort...";
    elapsed = time_call([&data] { parallel_sort(begin(data), end(data)); });
    wcout << L" took " << elapsed << L" ms." <<endl;

    // Use concurrency::parallel_buffered_sort to sort the data.
    data = GetData();
    wcout << L"Testing concurrency::parallel_buffered_sort...";
    elapsed = time_call([&data] { parallel_buffered_sort(begin(data), end(data)); });
    wcout << L" took " << elapsed << L" ms." <<endl;

    // Use concurrency::parallel_radixsort to sort the data.
    data = GetData();
    wcout << L"Testing concurrency::parallel_radixsort...";
    elapsed = time_call([&data] { parallel_radixsort(begin(data), end(data)); });
    wcout << L" took " << elapsed << L" ms." <<endl;
} 
/* Sample output (on a computer that has four cores):
    Testing std::sort... took 2906 ms.
    Testing concurrency::parallel_sort... took 2234 ms.
    Testing concurrency::parallel_buffered_sort... took 1782 ms.
    Testing concurrency::parallel_radixsort... took 907 ms.
*/

W tym przykładzie przyjęto założenie, że dopuszczalne jest przydzielenie miejsca O(N) podczas sortowania, parallel_radixsort najlepiej sprawdza się w tym zestawie danych w tej konfiguracji komputera.

[Top]

Tematy pokrewne

Nazwa	opis
Instrukcje: pisanie pętli parallel_for	Pokazuje, jak używać algorytmu parallel_for do mnożenia macierzy.
Instrukcje: pisanie pętli parallel_for_each	Pokazuje, jak użyć algorytmu parallel_for_each do obliczenia liczby liczb pierwszych w obiekcie std::array równolegle.
Instrukcje: używanie parallel_invoke do napisania procedury sortowania równoległego	Pokazuje, jak za pomocą algorytmu parallel_invoke poprawić wydajność algorytmu sortowania bitoicznego.
Instrukcje: korzystanie z parallel_invoke podczas przeprowadzania operacji równoległych	Pokazuje, jak za pomocą algorytmu parallel_invoke zwiększyć wydajność programu, który wykonuje wiele operacji na udostępnionym źródle danych.
Instrukcje: równoległe wykonywanie operacji mapowania i zmniejszania	Pokazuje, jak używać parallel_transform algorytmów i parallel_reduce do wykonywania operacji mapy i redukcji, która zlicza wystąpienia wyrazów w plikach.
Biblioteka równoległych wzorców (PLL)	Opisuje PPL, który zapewnia imperatywnego modelu programowania, który promuje skalowalność i łatwość użycia do tworzenia współbieżnych aplikacji.
Anulowanie w PPL	Wyjaśnia rolę anulowania w PPL, jak anulować równoległą pracę i jak określić, kiedy grupa zadań jest anulowana.
Obsługa wyjątków	Wyjaśnia rolę obsługi wyjątków w środowisku uruchomieniowym współbieżności.

Odwołanie

parallel_for, funkcja

parallel_for_each, funkcja

parallel_invoke, funkcja

affinity_partitioner, klasa

auto_partitioner, klasa

simple_partitioner, klasa

static_partitioner, klasa

parallel_sort, funkcja

parallel_buffered_sort, funkcja

parallel_radixsort, funkcja