Algorytmy równoległe

Biblioteka wzorców równoległego (PPL) zawiera algorytmów, które jednocześnie wykonywania pracy na zbiory danych.Te algorytmy przypominają te, pod warunkiem standardowej biblioteki szablonów (STL).

Algorytmy równoległe składają się z istniejących funkcji w środowisku wykonawczym współbieżności.Na przykład concurrency::parallel_for korzysta z algorytmu concurrency::structured_task_group obiektowi wykonanie iteracji pętli równoległych.parallel_for Partycje algorytm działa w sposób optymalny, biorąc pod uwagę liczbę dostępnych zasobów komputerowych.

Sekcje

• Funkcja parallel_for Algorithm

• Funkcja parallel_for_each Algorithm

• Funkcja parallel_invoke Algorithm

• Funkcja parallel_transform and parallel_reduce Algorithms

  • Funkcja parallel_transform Algorithm

  • Funkcja parallel_reduce Algorithm

  • Przykład: Wykonywanie mapowania i zmniejszenie równoległości

• Partycjonowanie pracy

• Sortowanie równoległe

  • Wybieranie algorytmu sortowania

Funkcja parallel_for Algorithm

Concurrency::parallel_for algorytm wielokrotnie wykonuje to samo zadanie równolegle.Każdego z tych zadań jest parametryzowana przez wartość iteracji.Ten algorytm jest przydatne, gdy masz ciała pętli, która nie współużytkuje zasoby wśród iteracji pętli.

parallel_for Algorytm partycje zadań w sposób optymalny dla przetwarzania równoległego.Wykorzystuje algorytm kradzież pracy się i kradzież do zrównoważenia te partycje, gdy obciążenie pracą jest niezbilansowanej liczby instrukcji zakresu.Gdy jeden iteracji pętli blokuje wspólnie, środowiska wykonawczego rozkłada zakres iteracji, które jest przypisane do bieżącego wątku do innych wątków lub procesory.Podobnie gdy wątek wykonuje szereg iteracji, środowiska wykonawczego rozkłada pracy z innych wątków do tego wątku.parallel_for Algorytm obsługuje również równoległości zagnieżdżonych.Równoległe pętli zawiera innego równoległego pętli, środowiska wykonawczego koordynuje przetwarzania zasobów między organami pętli w efektywnym sposobem przetwarzania równoległego.

parallel_for Algorytm ma kilka wersji przeciążone.Pierwsza wersja przyjmuje wartość początkową, wartość końcową i funkcji pracy (wyrażenie lambda, funkcja obiektu lub wskaźnik funkcji).Druga wersja ma wartość początkową, wartość końcową, wartość o jaką krok, a funkcja pracy.Pierwsza wersja tej funkcji używa 1 jako wartość kroku.Pozostałe wersje wziąć partycjonowania obiektów, które można określić jak parallel_for należy podzielić na partycje waha się między wątków.Partitioners zostały omówione bardziej szczegółowo w sekcji Podziału pracy w tym dokumencie.

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

• parallel_for Algorytm parallel_for nie wykonuje zadań w ustalonej kolejności.

• parallel_for Algorytm nie obsługuje warunki dowolnego wypowiedzenia.parallel_for Algorytm zatrzymuje się, gdy bieżąca wartość zmiennej iteracji jest jeden mniej niż _Last.

• _Index_type Parametr typ musi być typem całkowitym.Ten typ integralny można podpisane lub niepodpisane.

• Iteracji pętli musi być do przodu.parallel_for Algorytm zgłasza wyjątek typu std::invalid_argument Jeśli _Step parametr jest mniejsza niż 1.

• Mechanizm obsługi wyjątków dla parallel_for algorytm różni się od for pętli.Jeżeli wiele wyjątków występują jednocześnie w treści pętli równolegle, środowiska wykonawczego propaguje tylko jeden z wyjątków do wątku, który wywołał parallel_for.Ponadto gdy jeden iteracji pętli zgłasza wyjątek, środowiska wykonawczego nie natychmiast zatrzymuje ogólnej pętli.Zamiast pętli jest umieszczona w stanie anulowane i środowiska wykonawczego odrzuca wszystkie zadania, które nie zostały jeszcze rozpoczęte.Aby uzyskać więcej informacji na temat obsługi wyjątków i równoległe algorytmów, zobacz Obsługa wyjątków we współbieżności środowiska wykonawczego.

Chociaż parallel_for algorytm nie obsługuje warunki wypowiedzenia dowolnego, anulowanie umożliwia zatrzymanie wszystkich zadań.Aby uzyskać więcej informacji dotyczących anulowania, zobacz Anulowanie w PPL.

[!UWAGA]

Koszt planowania, że wyniki z Równoważenie obciążenia i obsługę funkcji, takich jak anulowanie nie może pokonać korzyści wynikające z wykonywania ciała pętli równolegle, zwłaszcza gdy ciała pętli jest stosunkowo niewielka.To obciążenie można zminimalizować przy użyciu partycjonowania w sieci równoległe pętli.Aby uzyskać więcej informacji, zobacz Podziału pracy później w tym dokumencie.

Przykład

Poniższy przykład pokazuje podstawową strukturę parallel_for algorytm.W tym przykładzie jest drukowany na konsoli każdej wartości z zakresu [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();
   });
}

Ten przykład generuje następujące przykładowe dane wyjściowe:

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

Na przykład pełną korzystającej z parallel_for algorytmu, zobacz Porady: pisanie pętli parallel_for.

[U góry]

Funkcja parallel_for_each Algorithm

Concurrency::parallel_for_each algorytm wykonuje zadania na kontenerem iteracyjne, takich jak te dostarczane przez STL, równolegle.Używa tej samej logiki partycjonowania który parallel_for korzysta z algorytmu.

parallel_for_each Algorytm przypomina STL std::for_each algorytmu, chyba że parallel_for_each algorytm wykonuje zadania jednocześnie.Jak inne algorytmy równoległe, parallel_for_each nie wykonuje zadań w określonej kolejności.

Chociaż parallel_for_each algorytm działa zarówno na Iteratory do przodu i Iteratory, działały lepiej z Iteratory.

Przykład

Poniższy przykład pokazuje podstawową strukturę parallel_for_each algorytm.W tym przykładzie jest drukowany na konsoli każdej wartości w std::array obiektu 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
*/

Ten przykład generuje następujące przykładowe dane wyjściowe:

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

Na przykład pełną korzystającej z parallel_for_each algorytmu, zobacz Porady: pisanie pętli parallel_for_each.

[U góry]

Funkcja parallel_invoke Algorithm

Concurrency::parallel_invoke algorytm wykonuje zestaw zadań równolegle.Nie zwraca przed zakończeniem każdego zadania.Ten algorytm jest przydatne, gdy masz kilka niezależnych zadań, które mają zostać zrealizowane w tym samym czasie.

parallel_invoke Algorytm przyjmuje jako jego parametry szereg funkcji pracy (lambda obiekty function, funkcji lub wskaźników funkcji).parallel_invoke Algorytm jest przeciążony do trwać od dwóch do dziesięciu parametrów.Każda funkcja, który jest przekazywany do parallel_invoke musi podjąć zero parametrów.

Jak inne algorytmy równoległe, parallel_invoke nie wykonuje zadań w określonej kolejności.Temat Równoległość zadania (współbieżność środowiska wykonawczego) wyjaśnia sposób, w jaki parallel_invoke algorytm odnosi się do zadań i grup zadań.

Przykład

Poniższy przykład pokazuje podstawową strukturę parallel_invoke algorytm.W tym przykładzie jednocześnie wywołuje twice funkcji na trzy zmienne lokalne i drukuje wynik do 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:

Pełne korzystanie przykłady parallel_invoke algorytmu, zobacz Porady: używanie parallel_invoke do napisania procedury sortowania równoległego i Porady: korzystanie z parallel_invoke do przeprowadzania operacji równoległych.

[U góry]

Funkcja parallel_transform and parallel_reduce Algorithms

Concurrency::parallel_transform i concurrency::parallel_reduce algorytmy są równoległe wersje algorytmów STL std::transform i std::accumulate, odpowiednio.Wersji środowiska wykonawczego współbieżność zachowują się jak wersje STL, chyba że kolejność operacji nie jest określony, ponieważ one wykonać równolegle.Użyj tych algorytmów, podczas pracy z zestawu, który jest wystarczająco duży, aby uzyskać korzyści wydajność i skalowalność z przetwarzane równolegle.

Ważne
parallel_transform i parallel_reduce algorytmy obsługuje tylko, komunikacja dwukierunkowa, a do przodu Iteratory, ponieważ te Iteratory produkować adresy pamięci stabilny.Ponadto, muszą przedstawić te Iteratory non -const l wartości.

Funkcja parallel_transform Algorithm

Można użyć parallel transform algorytm do wykonywania wielu operacji Hyper danych.Na przykład można:

• Dopasuj jasność obrazu i wykonywać inne operacje przetwarzania obrazu.

• Suma lub produkt dot między dwoma wektorami i wykonywać inne obliczenia numeryczne na nosicieli.

• Wykonaj śledzenie promieni 3-w, gdzie każdej iteracji odnosi się do jednego piksela, który należy wyrenderować.

Poniższy przykład pokazuje podstawową strukturę, która jest wykorzystywana do wywołania parallel_transform algorytm.W tym przykładzie neguje każdy element std::vector obiektu na dwa sposoby.Pierwszym sposobem jest używane wyrażenie lambda.Druga metoda wykorzystuje std::negate, co wynika ze 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>());
}

Przestroga
W tym przykładzie zademonstrowano użycie podstawowe parallel_transform.Ponieważ funkcja pracy nie wykonuje znaczną część pracy, w tym przykładzie nie przewiduje się znaczny wzrost wydajności.

parallel_transform Algorytm ma dwa przeciążeń.Pierwszy przeciążenie zajmuje jeden zakres wejściowy i funkcja Jednoelementowy.Funkcja jednoargumentowy może być wyrażenie lambda, która pobiera jeden argument, obiekt funkcji lub typ, który pochodzi od unary_function.Przeciążenie druga trwa dwa zakresy wejściowe i binarne funkcji.Funkcja binary może być wyrażenie lambda, która pobiera dwa argumenty, obiekt funkcji lub typ, który pochodzi od 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
Sterująca, która zostanie podana dla wyjścia parallel_transform musi całkowicie pokrywają się wprowadzania sterująca lub nie mogą się pokrywać w ogóle.Zachowanie tego algorytmu jest nieokreślony, jeśli Iteratory wejściowe i wyjściowe częściowo pokrywają się.

Funkcja parallel_reduce Algorithm

parallel_reduce Algorytm jest przydatne, gdy masz sekwencję operacji, które spełniają asocjacyjne właściwość. (Ten algorytm nie wymaga właściwość przemienny). Oto niektóre operacje, które można wykonywać za pomocą parallel_reduce:

• Należy pomnożyć sekwencje matryce do produkcji macierzy.

• Instancja klasy vector należy pomnożyć przez sekwencję matryce do produkcji instancja klasy vector.

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

• Wykaz elementów, takich jak ciągi, połączyć w jeden element.

Następujący prosty przykład pokazuje, jak używać parallel_reduce algorytm połączyć sekwencji ciągów w jeden ciąg.Podobnie jak w przypadku przykłady dla parallel_transform, nie oczekuje wzrost wydajności w tym przykładzie podstawowe.

// 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;
    words.push_back(L"Lorem ");
    words.push_back(L"ipsum ");
    words.push_back(L"dolor ");
    words.push_back(L"sit ");
    words.push_back(L"amet, ");
    words.push_back(L"consectetur ");
    words.push_back(L"adipiscing ");
    words.push_back(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 myśleć o parallel_reduce jako skrót do stosowania parallel_for_each algorytm wraz z concurrency::combinable klasy.

Przykład: Wykonywanie mapowania i zmniejszenie równoległości

A mapy operacja dotyczy funkcji każdej wartości w sekwencji.A zmniejszyć operacji łączy w sobie elementy sekwencji w jedną wartość.Można użyć standardowej biblioteki szablonów (STL) std::transformstd::accumulate klasy do wykonywania mapy i zmniejszyć operacji.Jednak wiele problemów można użyć parallel_transform algorytm do wykonania operacji mapę równolegle i parallel_reduce algorytm wykonać operację redukuj równolegle.

Poniższy przykład porównuje czas potrzebny, aby obliczyć sumę liczb pierwszych szeregowo i równolegle.Faza mapę przekształca wartości-prime 0 i Zmniejsz fazy sumy 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
*/

Na przykład innego, która wykonuje mapy i zmniejszyć operacji równolegle, zobacz Porady: wykonywanie mapowania i zmniejszanie operacji wykonywane równolegle.

[U góry]

Partycjonowanie pracy

Do zrównoleglenia operacji w źródle danych, niezbędnym krokiem jest partycji źródło na kilka sekcji, które mogą być udostępniane jednocześnie przez wiele wątków.Partycjonowania Określa, jak algorytm równoległy należy podzielić waha się między wątków.Jak wyjaśniono wcześniej w tym dokumencie, PPL używa domyślnie partycjonowanie mechanizm, który tworzy początkowe obciążenia pracą i następnie używa algorytmu i kradzież do zrównoważenia te partycje, gdy obciążenie pracą jest niezbilansowanej liczby instrukcji zakresu kradzież pracy.Na przykład jeden iteracji pętli po zakończeniu szereg iteracji, środowiska wykonawczego rozkłada pracy z innych wątków do tego wątku.Jednak w niektórych scenariuszach można określić mechanizm dzielenia na partycje innego lepiej nadaje się do problemu.

parallel_for, parallel_for_each, I parallel_transform algorytmy zawiera przeciążone wersji, które mają dodatkowy parametr, _Partitioner.Ten parametr określa typ partycjonowania, która dzieli pracy.Oto rodzaje partitioners, które definiuje PPL:

• CONCURRENCY::affinity_partitioner
  Dzieli działa pod stałą liczbę zakresów (zazwyczaj liczba wątków roboczych, które są dostępne do pracy nad pętli).Ten typ partycjonowania przypomina static_partitioner, ale poprawia koligacji pamięci podręcznej na drodze mapuje zakresów wątków roboczych.Ten typ partycjonowania może zwiększyć wydajność, gdy pętla jest wykonywana przez ten sam zestaw danych wiele razy (na przykład pętli wewnątrz pętli) i wpisuje dane w pamięci podręcznej.To partycjonowania nie pełni uczestniczy w anulowania.To również nie używa spółdzielni blokującym semantykę i dlatego nie można użyć z równoległych pętli, które mają współzależności do przodu.

• CONCURRENCY::auto_partitioner
  Podziały pracy do początkową liczbę zakresów (zazwyczaj liczba wątków roboczych, które są dostępne do pracy nad pętli).Środowisko wykonawcze używa tego typu domyślnie, gdy nie zostanie wywołana przeciążone algorytm równoległy, które przekieruje _Partitioner parametru.Każdy zakres można podzielić na zakresy podrzędne, a tym samym umożliwia równoważenie obciążenia występuje.Po zakończeniu zakres pracy, środowiska wykonawczego rozkłada zakresy podrzędne pracy z innych wątków do tego wątku.Użyj tego partycjonowania, jeśli obciążenie nie podlega jednej z innych kategorii lub wymagają pełne poparcie dla anulowania lub blokowanie spółdzielni.

• CONCURRENCY::simple_partitioner
  Dzieli się pracować na zakresy powoduje, że każdy zakres ma co najmniej liczba iteracji, które są określone przez wielkość danego pakietu.Ten typ partycjonowania bierze udział w równoważeniu obciążenia; Jednak środowiska wykonawczego nie podzielić zakresów zakresy podrzędne.Dla każdego pracownika, środowiska wykonawczego sprawdza anulowania i wykonuje równoważenia obciążenia po _Chunk_size wykonania iteracji.

• CONCURRENCY::static_partitioner
  Dzieli działa pod stałą liczbę zakresów (zazwyczaj liczba wątków roboczych, które są dostępne do pracy nad pętli).Ten typ partycjonowania może zwiększyć wydajność, ponieważ nie używać kradzież pracy i dlatego wymaga mniejszego nakładu pracy.Użyj tego typu partycjonowania po każdej iteracji pętli równoległych wykonuje stałe i jednolite ilość pracy i nie wymagają obsługi anulowania lub przekazania blokowanie spółdzielni.

Przestroga
parallel_for_each i parallel_transform algorytmy obsługuje tylko kontenery, które używają Iteratory (takie jak obiekt Vector) dla partitioners statycznych, proste i koligacji.Wykorzystanie kontenerów, używające dwukierunkowy i Iteratory do przodu powoduje błąd kompilacji.Domyślne partycjonowania, auto_partitioner, obsługuje wszystkie trzy z tych typów iteratora.

Partitioners te są zazwyczaj używane w taki sam sposób, z wyjątkiem affinity_partitioner.Większość typów partycjonowania nie utrzymują stan i nie są modyfikowane w czasie wykonywania.Dlatego można utworzyć tych obiektów partycjonowania w witrynie rozmowy, jak pokazano w następującym 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());
}

Jednakże, należy przekazać affinity_partitioner obiektu jako nie -const, l wartość odniesienia tak, że algorytm można przechowywać stan dla przyszłych pętli do ponownego użycia.Poniższy przykład pokazuje podstawowych aplikacji, który wykonuje tę samą operację na zestaw danych równolegle wiele razy.Użycie affinity_partitioner może zwiększyć wydajność, ponieważ tablica jest prawdopodobne 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);
    }
}

Przestroga
Należy zachować ostrożność podczas modyfikowania istniejącego kodu, który opiera się na współpracy blokującym semantykę używać static_partitioner lub affinity_partitioner.Te typy partycjonowania nie należy używać Równoważenie obciążenia sieciowego lub kradzież zakresu, a zatem może zmienić działanie aplikacji.

Najlepszym sposobem, aby ustalić, czy należy użyć partycjonowania w każdym danym scenariuszu jest do eksperymentowania i pomiaru, ile czasu zajmuje czynności do wykonania w obszarze reprezentatywnymi obciążeniem i konfiguracji komputerów.Na przykład statyczny partycjonowanie może stanowić znaczne przyspieszenie komputera Wielordzeniowe procesory, który ma tylko kilka rdzeni, ale może to spowodować spowolnienie na komputerach, które mają stosunkowo wielu rdzeni.

[U góry]

Sortowanie równoległe

PPL zawiera trzy algorytmy sortowania: concurrency::parallel_sort, concurrency::parallel_buffered_sort, i concurrency::parallel_radixsort.Te algorytmy sortowania są przydatne, gdy masz zestaw danych, które mogą korzystać z sortowane równolegle.W szczególności sortowanie równolegle jest przydatne, gdy masz dużego zestawu danych lub kiedy sortowanie danych za pomocą operacji obliczeniowo kosztowne porównaj.Każdy z tych algorytmów sortowania elementów w jednym miejscu.

parallel_sort i parallel_buffered_sort algorytmy są oba algorytmy oparte na porównania.To znaczy służą do porównywania elementów według wartości.parallel_sort Algorytm nie ma żadnych wymagań dodatkowej pamięci i nadaje się do ogólnego zastosowania sortowania.parallel_buffered_sort Algorytm można wykonywać lepiej niż parallel_sort, ale wymaga O(N) miejsca.

parallel_radixsort Algorytm jest oparty na procesie mieszania.Oznacza to, że wymaga użycia kluczy całkowitą do sortowania elementów.Za pomocą klawiszy, ten algorytm można bezpośrednio obliczyć docelowego elementu zamiast porównań.Jak parallel_buffered_sort, wymaga tego algorytmu O(N) miejsca.

W następującej tabeli podsumowano właściwości ważne trzy równoległe algorytmy sortowania.

Algorytm	Opis	Mechanizm sortowania	Stabilność sortowania	Wymagania dotyczące pamięci	Złożoność czasu	Dostęp iteratora
parallel_sort	Ogólnego zastosowania sortowania opartego na porównania.	Oparte na porównania (rosnąco)	Niestabilny	Brak	O((N/P)log(N/P) + 2N((P-1)/P))	Losowe
parallel_buffered_sort	Szybciej ogólnego przeznaczenia opartych na porównanie sortowania wymagającej miejsca O(N).	Oparte na porównania (rosnąco)	Niestabilny	Wymaga dodatkowych O(N) miejsca	O((N/P)log(N))	Losowe
parallel_radixsort	Liczba całkowita oparte na kluczach rodzaju, że wymaga miejsca O(N).	Oparta na mieszaniu	Stabilny	Wymaga dodatkowych O(N) miejsca	O(N/P)	Losowe

Na poniższej ilustracji przedstawiono ważne właściwości trzy równoległe algorytmy sortowania bardziej graficznie.

Te równolegle sortowanie algorytmy zgodne z regułami anulowania i obsługi wyjątków.Aby uzyskać więcej informacji o anulowanie i obsługi wyjątków w czasie wykonywania współbieżności, zobacz Algorytmy równoległe anulowanie i Obsługa wyjątków we współbieżności środowiska wykonawczego.

Porada

Obsługują one równolegle sortowanie algorytmów przenoszenia semantyka.Można zdefiniować operator przypisania przenoszenia umożliwiające swapy występuje bardziej efektywnie.Aby uzyskać więcej informacji na temat semantyki przenoszenia i Przenieś operator przypisania, zobacz Deklarator odwołania do wartości R: &&, i Porady: zapisywanie konstruktora przenoszenia.Jeśli nie podasz operator przypisania przenoszenia lub funkcja swap, algorytmy sortowania Użyj konstruktora kopii.

Następujący prosty przykład pokazuje, jak używać parallel_sort do sortowania vector z int wartości.Domyślnie parallel_sort korzysta z std::less do porównywania wartości.

// 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 przedstawiono zapewnienia funkcji Porównaj niestandardowych.Używa std::complex::real metoda sortowania std::complex<Podwójna> wartości 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 przedstawiono sposób zapewnienie funkcją mieszania do parallel_radixsort algorytm.W tym przykładzie sortuje 3-punktów.Punkty są sortowane w oparciu o ich odległość 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 niewielki zestaw danych.Można zwiększyć jego początkowy rozmiar wektora do eksperymentowania z poprawę wydajności nad większych zestawów danych.

W tym przykładzie wyrażenie lambda jako funkcja mieszania.Można także użyć jednego z wbudowanych implementacje std::hash klasy lub zdefiniować własne specjalizacji.Umożliwia także funkcja obiektu niestandardowego skrótu, jak pokazano w poniższym 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 mieszania musi zwracać typ integralny (std::is_integral::value musi być true).Ten typ integralny musi być konwertowany na typ size_t.

Wybieranie algorytmu sortowania

W wielu przypadkach parallel_sort zapewnia najlepszy stosunek wydajności szybkość i pamięć.Jednak, jak zwiększyć rozmiar zestawu danych, liczba dostępnych procesorów lub złożoność funkcji Porównaj, parallel_buffered_sort lub parallel_radixsort mogą działać lepiej.Najlepszym sposobem, aby określić, który algorytm sortowania do używania w każdym danym scenariuszu jest do eksperymentowania i pomiaru, jak długo trwa sortowanie typowe danych w ramach konfiguracji komputerów reprezentatywnych.Po wybraniu opcji sortowania strategii, należy pamiętać o następujących wytycznych.

• Rozmiar zestawu danych.W tym dokumencie małych zestaw danych zawiera mniej niż 1000 elementów Średni zestaw danych zawiera się między 10 000 do 100 000 elementów i dużych zestaw danych zawiera więcej niż 100 000 elementów.

• Ilość pracy wykonuje swoje funkcji Porównaj lub funkcji mieszania.

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

• Charakterystyka zbioru danych.Na przykład jeden algorytm może wykonywać również dla danych, który jest już prawie posortowany, ale nie tak dobrze dla danych, które jest całkowicie posortowany.

• Rozmiar segmentu.Opcjonalny _Chunk_size argument określa, kiedy algorytm przełącza z równolegle do wykonania sortowania serial jak dokonuje podziału sortowania Ogólny na mniejsze jednostki pracy.Na przykład jeśli podasz 512 algorytm przełącza się na szeregowego wykonania gdy jednostka pracy zawiera 512 lub mniej elementów.Szeregowy wykonania może poprawić ogólną wydajność, ponieważ eliminuje obciążenie, które jest wymagane do danych procesu równolegle.

Nie może być warto posortować małe dataset równolegle, nawet, jeśli masz dużą liczbę dostępnych zasobów komputerowych lub swojej funkcji Porównaj lub mieszania wykonuje stosunkowo dużej ilości pracy.Można użyć pochodzących funkcji sortowania małych zestawów danych. (parallel_sort i parallel_buffered_sort call sort po określeniu wielkości segment, który jest większy niż zestaw danych; Jednakże, parallel_buffered_sort musi przydzielić O(N) przestrzeń, która może zająć więcej czasu ze względu na blokada alokacji pamięci lub rywalizacji.)

Jeśli trzeba zachować więcej wolnej pamięci lub Twój program przydzielania pamięci jest przedmiotem rywalizacji blokad, użyj parallel_sort do sortowania zestawu danych małych i średnich.parallel_sortwymaga bez dodatkowych spacji; algorytmy, inne wymagają O(N) miejsca.

Użycie parallel_buffered_sort do sortowania średnie zestawów danych i kiedy spełnia dodatkowych aplikacji O(N) wymagań dotyczących miejsca.parallel_buffered_sortmoże być szczególnie przydatne, jeśli masz dużą liczbę zasobów komputerowych lub kosztowne porównaj funkcji lub funkcji mieszania.

Użycie parallel_radixsort sortowania dużych zestawów danych, a kiedy spełnia dodatkowych aplikacji O(N) wymagań dotyczących miejsca.parallel_radixsortmoże być szczególnie przydatne w przypadku, gdy operacja porównania równoważne jest droższe lub kiedy obie operacje są drogie.

Przestroga
Wdrażanie funkcji mieszania dobre wymaga wiedzą z zakresu zestawu danych i jak każdy element w zestawie danych jest przekształcany do odpowiedniej wartości bez znaku.Operacja mieszania działa na wartości bez znaku, dlatego należy rozważyć możliwość sortowania różnych strategii Jeśli wartości mieszania bez znaku nie mogą być produkowane.

Poniższy przykład porównuje wyniki z sort, parallel_sort, parallel_buffered_sort, i parallel_radixsort przeciwko samej duży zestaw 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 zakłada się dopuszczalne przydzielić O(N) miejsce podczas sortowania, parallel_radixsort działa najlepiej na tego elementu dataset w tej konfiguracji komputera.

[U góry]

Tematy pokrewne

Tytuł	Opis
Porady: pisanie pętli parallel_for	Pokazuje, jak użyć parallel_for algorytm, aby wykonać mnożenie macierzy.
Porady: pisanie pętli parallel_for_each	Pokazuje, jak użyć parallel_for_each algorytm obliczania liczby liczb w std::array obiektu równolegle.
Porady: używanie parallel_invoke do napisania procedury sortowania równoległego	Pokazuje, jak użyć algorytm parallel_invoke, aby zwiększyć wydajność algorytmu sortowania bitonicznego.
Porady: korzystanie z parallel_invoke do przeprowadzania operacji równoległych	Pokazuje, jak użyć algorytm parallel_invoke, aby zwiększyć wydajność programu, który wykonuje wiele operacji na udostępnionym źródle danych.
Porady: wykonywanie mapowania i zmniejszanie operacji wykonywane równolegle	Pokazuje, jak użyć parallel_transform i parallel_reduce algorytmy do wykonywania mapy i zmniejszyć operacji, która zlicza liczbę wystąpień słów w plikach.
Biblioteka równoległych wzorców (PLL)	W tym artykule opisano PPL, który zapewnia konieczne model programowania, który promuje skalowalność i łatwość użycia do tworzenia aplikacji współbieżnych.
Anulowanie w PPL	W tym artykule wyjaśniono rolę anulowania w PPL, jak anulować równoległą pracę i sposobu ustalania, kiedy grupa zadań zostało anulowane.
Obsługa wyjątków we współbieżności środowiska wykonawczego	W tym artykule wyjaśniono roli Obsługa wyjątków w Runtime 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