Algorytmy równoległe

Biblioteka wzorców równoległego (PPL) zawiera algorytmów, które jednocześnie wykonywać pracę na zbiory danych.Te algorytmy przypomina funkcje dostarczane przez standardowe biblioteki szablonu (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

• Parallel_for algorytmu

• Parallel_for_each algorytmu

• Parallel_invoke algorytmu

• Algorytmy parallel_transform i parallel_reduce

  • Parallel_transform algorytmu

  • Parallel_reduce algorytmu

  • Przykład: Wykonywanie Map i zmniejszyć równolegle

• Partycjonowanie pracy

• Sortowanie równoległego

  • Wybieranie algorytmu sortowania

Parallel_for algorytmu

Concurrency::parallel_for algorytm wielokrotnie wykonuje to samo zadanie równolegle.Każdy z tych zadań jest parametryzowana przez wartość iteracji.Ten algorytm jest przydatne, gdy masz jednostkę pętla, 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.To używa algorytmu i zakresu kradzież do zrównoważenia te partycje, gdy obciążenie pracą jest nierównomierną kradzież pracy.Gdy jeden iteracji pętli blokuje wspólnie, środowiska wykonawczego rozkłada zakres iteracji, który jest przypisany do bieżącego wątku dla innych wątków lub przetwórców.Podobnie gdy wątek kończy szereg iteracji, środowiska wykonawczego rozpowszechnia 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 zainstalowano kilka wersji przeciążone.Pierwsza wersja przybiera wartości początkowej, wartość na koniec i funkcja pracy (wyrażenie lambda, funkcja obiektu lub wskaźnik funkcji).Druga wersja ma wartość początkowa, wartość końcową, wartość za pomocą której krok, a funkcja pracy.Pierwsza wersja tej funkcji używa 1 jako wartość kroku.Pozostałe wersje podjąć partycjonowania obiektów, które można określić jak parallel_for należy podzielić na partycje zakresów pomiędzy wątkami.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, który różni się od for instrukcji w następujący sposób:

• parallel_for Algorytm parallel_for nie są wykonywane zadania w odpowiedniej kolejności.

• parallel_for Nie obsługuje algorytmu warunki dowolnego wypowiedzenia.parallel_for Algorytm zatrzymywany po bieżącej wartości zmiennej iteracji jest jednym mniej niż _Last.

• _Index_type Parametru typu 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, który różni się od for pętli.Jeżeli wiele wyjątków występowania jednocześnie w treści pętli równoległe środowiska wykonawczego propaguje tylko jeden z wyjątków do wątku, który wywołał parallel_for.Ponadto po jednej iteracji pętli zgłasza wyjątek, środowiska wykonawczego nie natychmiast zatrzymuje ogólnej pętli.Zamiast pętli jest umieszczona w stanie unieważnioną i środowiska wykonawczego spowoduje odrzucenie wszystkich zadań, które nie zostały jeszcze rozpoczęte.Aby uzyskać więcej informacji na temat algorytmów obsługi wyjątków i równoległe, zobacz Obsługa wyjątków w Runtime współbieżności.

Chociaż parallel_for nie obsługuje algorytmu warunki wypowiedzenia dowolnego, można użyć odwołania zatrzymanie wszystkich zadań.Aby uzyskać więcej informacji o unieważnieniu, zobacz Anulowanie w PPL.

[!UWAGA]

Koszt planowania wyników z równoważenia obciążenia i obsługę funkcji, takich jak unieważnienia nie może pokonać z zalet wykonywanie pętli równolegle, zwłaszcza gdy pętli jest stosunkowo niewielka.Tego zapasu można zminimalizować przy użyciu partycjonowania w swojej pętli równoległych.Aby uzyskać więcej informacji, zobacz Podziału pracy później w tym dokumencie.

Przykład

W poniższym przykładzie pokazano podstawowej struktury 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, zależy od kolejności, w którym wartości są drukowane do konsoli.

Pełny przykład korzystającej z parallel_for algorytmu, zobacz Jak: zapis parallel_for pętli.

Top

Parallel_for_each algorytmu

Concurrency::parallel_for_each algorytm wykonuje zadania na kontenerem iteracyjne, takich jak dostarczone przez STL, równolegle.Używa tej samej logiki podziału na partycje, parallel_for korzysta z algorytmu.

parallel_for_each Algorytm jest podobna do STL std::for_each algorytm, chyba że parallel_for_each algorytm wykonuje zadania jednocześnie.Podobnie jak inne algorytmy równoległe, parallel_for_each nie są wykonywane zadania w określonej kolejności.

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

Przykład

W poniższym przykładzie pokazano podstawowej struktury 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), begin(values), [](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_each algorytm działa na każdym elemencie równolegle, zależy od kolejności, w którym wartości są drukowane do konsoli.

Pełny przykład korzystającej z parallel_for_each algorytmu, zobacz Jak: zapis parallel_for_each pętli.

Top

Parallel_invoke algorytmu

Concurrency::parallel_invoke algorytm wykonuje zestaw zadań jednocześnie.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 wykonuje w jego parametry serię działają funkcje (lambda funkcje jako obiekty, funkcji lub wskaźników funkcji).parallel_invoke Algorytm jest nadmiernie obciążony, aby trwać od dwóch do dziesięciu parametrów.Każda funkcja, który jest przekazywany do parallel_invoke musi podjąć zero parametrów.

Podobnie jak inne algorytmy równoległe, parallel_invoke nie są wykonywane zadania w określonej kolejności.Temat Zadanie równoległości (współbieżności Runtime) wyjaśnia, jak parallel_invoke algorytm, który odnosi się do zadań i grup zadań.

Przykład

W poniższym przykładzie pokazano podstawowej struktury 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:

Kompletne przykłady, które używają parallel_invoke algorytmu, zobacz Jak: za pomocą parallel_invoke zapisu równoległych rutynowych sortowania i Jak: Użyj parallel_invoke do wykonywania operacji równoległych.

Top

Algorytmy parallel_transform i parallel_reduce

Concurrency::parallel_transform i concurrency::parallel_reduce algorytmy są równoległe wersjach algorytmy STL std::transform i std::accumulate, odpowiednio.W wersjach środowiska wykonawczego współbieżności zachowują się jak wersje STL, z tym, że kolejność operacji nie jest określony, ponieważ realizują 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 produkcji adresów pamięci stabilne.Iteratory te należy wyprodukować non-const l wartości.

Parallel_transform algorytmu

Można użyć parallel transform algorytm przeprowadzać wiele operacji zrównoleglania danych.Na przykład możesz:

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

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

• Wykonaj śledzenie promieni 3-w, gdzie każda iteracja odnosi się o jeden piksel, który musi być renderowana.

Poniższy przykład pokazuje podstawową strukturę, która służy do wywołania parallel_transform algorytm.W tym przykładzie neguje każdy element std::vector obiektu na dwa sposoby.Pierwszy sposób 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 wymaga jednego zakresu wejściowego i funkcja Jednoelementowy.Funkcja jednoargumentowy może być wyrażenie lambda, która pobiera jeden argument, obiekt funkcji lub typu, który wynika z unary_function.Drugi przeciążenie trwa dwa zakresy wejściowe i funkcja binarne.Binarne funkcja może być wyrażenie lambda, która pobiera dwa argumenty, obiekt funkcji lub typu, który wynika 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
Sterująca podana dla wyjścia parallel_transform należy całkowicie pokrywają się wejściowy sterująca lub nakłada się na wszystkich.Zachowanie ten algorytm jest nieokreślony, jeśli Iteratory wejściowe i wyjściowe częściowo pokrywają się.

Parallel_reduce algorytmu

parallel_reduce Algorytm jest przydatne, gdy masz sekwencję operacji, spełniające łączność.(Ten algorytm nie wymaga właściwości przemienny). Oto niektóre z tych operacji, które można wykonać z parallel_reduce:

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

• Instancję klasy vector należy pomnożyć przez sekwencję matryce do produkcji instancję klasy vector.

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

• Listę elementów, takie 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, wzrost wydajności nie oczekuje się 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, mogą być traktowane parallel_reduce jako skrót do użytku parallel_for_each algorytm wraz z concurrency::combinable klasy.

Przykład: Wykonywanie Map i zmniejszyć równolegle

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ć standardowego szablonu biblioteki (STL) std::transformstd::accumulate klasy do wykonywania mapę 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.

W poniższym przykładzie porównanie czas potrzebny, aby obliczyć sumę liczb pierwszych szeregowo i równolegle.Faza mapę przekształca non-prime wartości 0 i kwot faza zmniejszenia 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
*/

Inny przykład, wykonuje mapie i ograniczeniu operacji równolegle, zobacz Jak: wykonywanie mapę i zmniejszyć operacji równolegle.

Top

Partycjonowanie pracy

Do zrównoleglenia operację na źródło 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ć zakresów pomiędzy wątkami.Jak wyjaśniono wcześniej, w tym dokumencie, PPL używana jest wartość domyślna partycjonowanie mechanizm, która tworzy początkowe obciążenia, a następnie używa algorytmu i zakresu kradzież do zrównoważenia te partycje, gdy obciążenie pracą jest nierównomierną kradzież pracy.Na przykład jeden iteracji pętli po zakończeniu szereg iteracji, środowiska wykonawczego rozpowszechnia pracy z innych wątków do tego wątku.Jednak w niektórych scenariuszach można określić inny mechanizm podziału na partycje, która jest lepiej dostosowany 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 ten PPL:

• CONCURRENCY::affinity_partitioner
  Dzieli pracę w ramach stałej liczby zakresów (zazwyczaj liczba wątków roboczych, które są dostępne do pracy na pętli).Podobny do tego typu partycjonowania 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ętla w pętli) i dane mieści się w pamięci podręcznej.Ta partycjonowania nie w pełni uczestniczy w anulowania.To również nie używa spółdzielni semantyką blokowania i dlatego nie można używać z pętli równoległych, które mają współzależności do przodu.

• CONCURRENCY::auto_partitioner
  Dzieli pracę w ramach początkową liczbę zakresów (zazwyczaj liczba wątków roboczych, które są dostępne do pracy na 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że być podzielona na zakresy podrzędne, a tym samym umożliwia równoważenie obciążenia występuje.Po zakończeniu zakres pracy, środowiska wykonawczego rozpowszechnia 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 jest wymagana pełna obsługa anulowania lub blokowanie współpracy.

• CONCURRENCY::simple_partitioner
  Dzieli pracę w ramach zakresów, 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, sprawdza, czy unieważnienie środowiska wykonawczego i wykonuje równoważenia obciążenia po _Chunk_size wykonania iteracji.

• CONCURRENCY::static_partitioner
  Dzieli pracę w ramach stałej liczby zakresów (zazwyczaj liczba wątków roboczych, które są dostępne do pracy na pętli).Ten typ partycjonowania może zwiększyć wydajność, ponieważ nie używa kradzież pracy i dlatego wymaga mniejszego nakładu pracy.Po każdej iteracji pętli równoległych wykonuje stałe i jednolite ilość pracy i nie wymagają obsługi anulowania lub przesłać dalej blokowanie spółdzielni, należy użyć tego typu partycjonowania.

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

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

Jednak trzeba przekazać affinity_partitioner obiektu jako non-const, l wartość odniesienia tak, aby algorytm można przechowywać stan dla przyszłych pętli do ponownego użycia.Poniższy przykład pokazuje podstawowych aplikacji, która wykonuje tę samą operację na zestaw danych równolegle wiele razy.Użycie affinity_partitioner można 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;

int wmain()
{    
    // Create an arry 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 semantyką blokowania obsłudze 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żna zmienić zachowanie aplikacji.

Najlepszym sposobem ustalenia, czy mają być używane w każdym danym scenariuszu partycjonowania 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 na komputerze wielordzeniowe, który ma tylko kilka rdzeni, ale może to spowodować spowolnienie na komputerach, które mają stosunkowo wielu rdzeni.

Top

Sortowanie równoległego

PPL zawiera trzy algorytmy sortowania: concurrency::parallel_sort, concurrency::parallel_buffered_sort, i concurrency::parallel_radixsort.Są one sortowanie algorytmy przydatne, gdy masz zestaw danych, które mogą korzystać z zastosowano sortowanie równolegle.W szczególności sortowanie równolegle przydaje, gdy wystąpi duża baza danych lub kiedy sortowanie danych za pomocą operacja porównania obliczeniowo drogie.Każdy z tych algorytmów Sortuje elementy w miejscu.

parallel_sort i parallel_buffered_sort algorytmy są oba algorytmy oparte na porównanie.Oznacza to służą do porównywania elementów przez wartość.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 używa kluczy liczba całkowita, aby posortować elementy.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 ważne właściwości trzy równoległe algorytmy sortowania.

Algorytm	Opis	Mechanizm sortowania	Stabilność sortowania	Wymagania dotyczące pamięci	Złożoność.	Sterująca dostępu
parallel_sort	Ogólnego zastosowania sortowania opartego na porównanie.	Oparte na Porównaj (rosnąco)	Niestabilny	Brak	O((N/P)log(N/P) + 2N((P-1)/P))	Losowe
parallel_buffered_sort	Szybciej ogólnego przeznaczenia na bazie Porównaj rodzaju, że wymaga miejsca O(N).	Oparte na Porównaj (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).	Oparty na procesie mieszania	Stabilne	Wymaga dodatkowych O(N) miejsca	O(N/P)	Losowe

Ilustracja przedstawia bardziej graficznie ważne właściwości trzy równoległe algorytmy sortowania.

Wynikają one równolegle sortowania algorytmy regulamin unieważnienia umowy lub obsługi wyjątków.Aby uzyskać więcej informacji na temat unieważnienia umowy lub obsługi wyjątków w czasie wykonywania współbieżności, zobacz Anulowanie algorytmy równoległe i Obsługa wyjątków w Runtime współbieżności.

Porada

Obsługują one równolegle sortowania algorytmy semantykę ruch.Można zdefiniować ruch operator przypisania, aby umożliwić operacje wymiany nastąpić efektywniej.Aby uzyskać więcej informacji na temat semantyki ruch i operator przypisania ruch, zobacz Odwołanie Rvalue; niewłaściwy deklarator: & &, i Jak: Konstruktor Przenieś zapisu.Jeśli nie podasz operator przypisania ruch 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 funkcji Porównaj niestandardowych.Używa std::complex::real metoda sortowania std::complex <double> 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)
*/

Ten przykład pokazuje, jak zapewnienie funkcją mieszania, aby parallel_radixsort algorytm.W tym przykładzie sortuje 3-w punktach.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ć rozmiar początkowy wektora do eksperymentowania z wydajności nad większych zestawów danych.

W tym przykładzie używa wyrażenia lambda jako funkcja mieszania.Możesz także użyć jednego z wbudowanych implementacje std::hash klasy lub zdefiniować własne specjalizacji.Można również użyć obiektu funkcji skrótu niestandardowego, 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 kompromis między wydajnością szybkość i pamięć.Jednakże, jak zwiększyć rozmiar zestawu danych, liczba dostępnych procesorów lub złożoność naszą funkcję porównaj parallel_buffered_sort lub parallel_radixsort mogą działać lepiej.Najlepszym sposobem oceny algorytm sortowania, który w każdym danym scenariuszu jest do eksperymentowania i pomiaru, jak długo trwa sortowanie typowych danych w obszarze konfiguracji komputerów reprezentatywnych.Po wybraniu 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, a dużych zestaw danych zawiera więcej niż 100 000 elementów.

• Ilość pracy, którą wykonuje funkcji Porównaj lub funkcji mieszania.

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

• Charakterystyka zbioru danych.Na przykład jeden algorytm prawdopodobnie będą wykonywać dobrze w przypadku danych, który jest już prawie posortowany, ale nie tak dobrze dla danych, który jest całkowicie bez sortowania.

• Rozmiar segmentu.Opcjonalny _Chunk_size argument określa, kiedy algorytm przełącza z równolegle do wykonania sortowania szeregowego zgodnie z ogólną sortowania to dzieli na mniejsze jednostki pracy.Na przykład, jeśli zostanie wprowadzony 512 algorytm przełącza się na realizacji szeregowego gdy jednostka pracy zawiera 512 lub mniejszej liczby elementów.Szeregowy wykonania może poprawić ogólną wydajność, ponieważ eliminuje obciążenie, które jest wymagane do przetwarzania danych równolegle.

Może nie warto posortować małych zestawu danych jednocześnie, nawet wtedy, gdy masz dużą liczbę dostępnych zasobów komputerowych lub towarzystwa funkcja lub funkcją mieszania wykonuje stosunkowo dużej ilości pracy.Można użyć pochodzących funkcji, aby posortować małych zestawów danych.(parallel_sort i parallel_buffered_sort call sort określając rozmiar segmentu, który jest większy niż zestaw danych; Jednakże, parallel_buffered_sort musi przydzielić O(N) wolnego miejsca, co 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 sortowania średnie zestawów danych, a gdy aplikacja spełnia dodatkowe O(N) zabudowy.parallel_buffered_sortmoże być szczególnie przydatne w przypadku, gdy 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 gdy aplikacja spełnia dodatkowe O(N) zabudowy.parallel_radixsortmoże być szczególnie przydatne w przypadku, gdy operacja porównania równoważne są droższe lub kiedy obie operacje są drogie.

Przestroga
Wykonania funkcji mieszania dobrej wymaga, że znasz zakresu zestawu danych i jak każdy element w zestawie danych jest przekształcany do odpowiedniej wartości bez znaku.Ponieważ operacji obliczania skrótu działa na wartości bez znaku, należy rozważyć innych strategii sortowania, jeśli wartości mieszania bez znaku nie mogą być produkowane.

W poniższym przykładzie porównanie wydajności sort, parallel_sort, parallel_buffered_sort, i parallel_radixsort przeciwko ten sam zestaw duże zdarzeń 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, który zakłada, że jest to dopuszczalne przydzielić O(N) miejsce podczas sortowania, parallel_radixsort działa najlepiej na tego zestawu danych na tej konfiguracji komputera.

Top

Tematy pokrewne

Tytuł	Opis
Jak: zapis parallel_for pętli	Przedstawiono sposób użycia parallel_for algorytm, aby wykonać mnożenie macierzy.
Jak: zapis parallel_for_each pętli	Przedstawiono sposób użycia parallel_for_each algorytm obliczania liczbę elementów w zachodniej std::array obiektu równolegle.
Jak: za pomocą parallel_invoke zapisu równoległych rutynowych sortowania	Przedstawiono sposób użycia parallel_invoke algorytm, aby zwiększyć wydajność algorytmu sortowania bitonic.
Jak: Użyj parallel_invoke do wykonywania operacji równoległych	Przedstawiono sposób użycia parallel_invoke algorytmu w celu poprawy wydajności programu, który wykonuje wiele operacji na z udostępnionego źródła danych.
Jak: wykonywanie mapę i zmniejszyć operacji równolegle	Przedstawiono sposób użycia parallel_transform i parallel_reduce algorytmy do wykonywania mapie i zmniejszyć operacji, który zlicza liczbę wystąpień słów w plikach.
Biblioteka desenie równoległe (PPL)	W tym artykule opisano, PPL, która zapewnia konieczne model programowania, który promuje skalowalność i łatwość użycia dla rozwoju aplikacji.
Anulowanie w PPL	W tym artykule wyjaśniono roli odwołania w PPL, jak anulować równoległą pracę i sposobu ustalania, kiedy zostanie anulowane grupy zadań.
Obsługa wyjątków w Runtime współbieżności	W tym artykule wyjaśniono roli Obsługa wyjątków w czasie wykonywania współbieżności.

Informacje o odwołaniach

Funkcja parallel_for

Funkcja parallel_for_each

Funkcja parallel_invoke

Klasa affinity_partitioner

Klasa auto_partitioner

Klasa simple_partitioner

Klasa static_partitioner

Funkcja parallel_sort

Funkcja parallel_buffered_sort

Funkcja parallel_radixsort