Parallele Algorithmen

Die Parallel Patterns Library (PPL) stellt Algorithmen bereit, die Auflistungen von Daten gleichzeitig verarbeiten.Diese Algorithmen sind denen ähnlich, die von der Standardvorlagenbibliothek (STL) bereitgestellt werden.

Die parallelen Algorithmen werden aus vorhandenen Funktionen in der Concurrency Runtime erstellt.Beispielsweise verwendet der concurrency::parallel_for Algorithmus ein concurrency::structured_task_group-Objekt, um die parallelen Schleifeniterationen auszuführen.Der parallel_for-Algorithmus verteilt die Arbeit auf Grundlage der verfügbaren Computerressourcen auf optimale Weise.

Abschnitte

• Der parallel for-Algorithmus

• Der parallel for each-Algorithmus

• Der parallel invoke-Algorithmus

• Die parallel_transform und parallel_reduce Algorithmen

  • Der Algorithmus parallel_transform

  • Der Algorithmus parallel_reduce

  • Beispiel: Zuordnung ausgeführt und reduzieren Sie parallel

• Partitionieren der Arbeit

• Parallele Sortierung

  • Auswählen eines Sortieralgorithmus

Der parallel for-Algorithmus

Der concurrency::parallel_for Algorithmus führt die gleiche Aufgabe wiederholt parallel aus.Jede dieser Aufgaben wird mit einem Iterationswert parametrisiert.Dieser Algorithmus ist nützlich, wenn ein Schleifentext vorhanden ist, der die Ressourcen nicht zwischen Iterationen dieser Schleife freigibt.

Der parallel_for-Algorithmus verteilt die Aufgaben so, dass eine optimale parallele Ausführung gewährleistet wird.Er verwendet einen Arbeitsübernahme-Algorithmus und einen Bereich, die stehlen, der diese Partitionen, wenn die unausgeglichen sind.Wenn eine Schleifeniteration kooperativ blockiert wird, wird der Iterationsbereich für den aktuellen Thread von der Laufzeit auf andere Threads oder Prozessoren verteilt.Wenn ein Thread einen Bereich von Iterationen durchlaufen hat, wird von der Laufzeit Arbeit von anderen Threads auf diesen Thread verteilt.Der parallel_for-Algorithmus unterstützt auch die geschachtelten Parallelität.Wenn eine parallele Schleife eine andere parallele Schleife enthält, werden die Verarbeitungsressourcen zwischen den Schleifentexten von der Laufzeit möglichst effizient koordiniert, um eine parallele Ausführung zu ermöglichen.

Der parallel_for Algorithmus verfügt über mehrere überladene Versionen.Die erste Version verwendet einen Anfangswert, einen Endwert und eine Arbeitsfunktion (ein Lambda-Ausdruck, Funktionsobjekt oder Funktionszeiger).Die zweite Version verwendet einen Anfangswert, einen Endwert, einen Schrittwert sowie eine Arbeitsfunktion.Die erste Version dieser Funktion verwendet 1 als Schrittwert.Die übrigen Versionen nehmen Partitioniererobjekte, die Sie aktivieren, um anzugeben, wie parallel_for Bereiche zwischen Threads partitionieren sollte.Partitionierer werden ausführlich im Abschnitt Partitionieren der Arbeit in diesem Dokument erläutert.

Sie können viele for-Schleifen konvertieren, um parallel_for zu verwenden.Der parallel_for-Algorithmus unterscheidet sich jedoch wie folgt von der for-Anweisung:

• Der parallel_for-Algorithmus führt parallel_for die Aufgaben nicht in einer vordefinierten Reihenfolge aus.

• Der parallel_for-Algorithmus unterstützt keine beliebigen Beendigungsbedingungen.Der parallel_for-Algorithmus stoppt, wenn der aktuelle Wert der Iterationsvariable ein weniger als _Last ist.

• Der _Index_type-Typparameter muss ein ganzzahliger Typ sein.Dieser ganzzahlige Typ kann mit oder ohne Vorzeichen verwendet werden.

• Die Schleifeniteration muss vorwärts gerichtet sein.Der parallel_for-Algorithmus löst eine Ausnahme des Typs std::invalid_argument aus, wenn der _Step-Parameter kleiner als 1 ist.

• Der parallel_for-Algorithmus verwendet einen anderen Mechanismus zur Ausnahmebehandlung als die for-Schleife.Wenn mehrere Ausnahmen gleichzeitig in einem parallelen Schleifentext auftreten, gibt die Laufzeit nur eine Ausnahmen an den Thread weiter, der parallel_for aufgerufen hat.Wenn eine Schleifeniteration eine Ausnahme auslöst, wird darüber hinaus nicht sofort die gesamte Schleife von der Laufzeit beendet.Stattdessen wird die Schleife in den abgebrochenen Zustand versetzt, und alle noch nicht gestarteten Aufgaben werden von der Laufzeit verworfen.Weitere Informationen zur Ausnahmebehandlung sowie zu parallelen Algorithmen finden Sie unter Ausnahmebehandlung in der Concurrency Runtime.

Obwohl der parallel_for-Algorithmus keine beliebigen Beendigungsbedingungen unterstützt, können Sie durch einen Abbruch alle Aufgaben beenden.Weitere Informationen über das Abbrechen finden Sie unter Abbruch in der PPL.

Hinweis

Die durch den Lastenausgleich und die Unterstützung von Funktionen wie Abbruch verursachen Planungskosten können die Vorteile der parallelen Ausführung des Schleifentexts möglicherweise nicht kompensieren; dies gilt insbesondere bei relativ kleinen Schleifentexten.Sie können diesen Mehraufwand minimieren, indem Sie einen Partitionierer in der parallelen Schleife verwenden.Weitere Informationen finden Sie unter Partitionieren der Arbeit weiter unten in diesem Dokument.

Beispiel

Im folgenden Beispiel wird die Grundstruktur des parallel_for-Algorithmus veranschaulicht.In diesem Beispiel werden die einzelnen Werte im Bereich [1, 5] parallel auf der Konsole ausgegeben.

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

Dieses Beispiel erzeugt die folgende Beispielausgabe:

Da der parallel_for-Algorithmus parallel auf die einzelnen Elemente angewendet wird, werden die Werte möglicherweise in unterschiedlicher Reihenfolge auf der Konsole ausgegeben.

Ein vollständiges Beispiel für den parallel_for-Algorithmus finden Sie unter Gewusst wie: Schreiben einer parallel_for-Schleife.

Anfang[]

Der parallel for each-Algorithmus

Der concurrency::parallel_for_each Algorithmus führt Aufgaben für einen iterativen Container, wie beispielsweise die aus, die STL, parallel bereitgestellt werden.Er verwendet die gleiche Partitionierungslogik wie der parallel_for-Algorithmus.

Der parallel_for_each-Algorithmus ähnelt dem std::for_each-Algorithmus der STL, mit dem Unterschied, dass der parallel_for_each-Algorithmus die Aufgaben gleichzeitig ausführt.Wie andere parallele Algorithmen führt auch der parallel_for_each-Algorithmus die Aufgaben nicht in einer bestimmten Reihenfolge aus.

Obwohl der parallel_for_each-Algorithmus sowohl für Vorwärtsiteratoren als auch zufällige Zugriffsiteratoren angewendet werden kann, funktioniert er für zufällige Zugriffsiteratoren besser.

Beispiel

Im folgenden Beispiel wird die Grundstruktur des parallel_for_each-Algorithmus veranschaulicht.In diesem Beispiel werden die einzelnen Werte in einem std::array-Objekt parallel auf der Konsole ausgegeben.

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

Dieses Beispiel erzeugt die folgende Beispielausgabe:

Da der parallel_for_each-Algorithmus parallel auf die einzelnen Elemente angewendet wird, werden die Werte möglicherweise in unterschiedlicher Reihenfolge auf der Konsole ausgegeben.

Ein vollständiges Beispiel für den parallel_for_each-Algorithmus finden Sie unter Gewusst wie: Schreiben einer parallel_for_each-Schleife.

Anfang[]

Der parallel invoke-Algorithmus

Der concurrency::parallel_invoke Algorithmus führt einen Satz von Aufgaben parallel aus.Die Rückgabe erfolgt erst dann, wenn jede Aufgabe ausgeführt wurde.Dieser Algorithmus ist nützlich, wenn mehrere voneinander unabhängige Aufgaben vorhanden sind, die zur gleichen Zeit ausgeführt werden sollen.

Der parallel_invoke-Algorithmus verwendet eine Reihe von Arbeitsfunktionen (Lambdafunktionen, Funktionsobjekte oder Funktionszeiger) als Parameter.Der parallel_invoke-Algorithmus wird überladen, sodass er zwischen zwei und zehn Parameter verwenden kann.Jede Funktion, die an parallel_invoke übergeben wird, muss 0 (null) Parameter akzeptieren.

Wie andere parallele Algorithmen führt auch der parallel_invoke-Algorithmus die Aufgaben nicht in einer bestimmten Reihenfolge aus.Im Thema Aufgabenparallelität (Concurrency Runtime) wird erläutert, welchen Bezug der parallel_invoke-Algorithmus zu Aufgaben und Aufgabengruppen aufweist.

Beispiel

Im folgenden Beispiel wird die Grundstruktur des parallel_invoke-Algorithmus veranschaulicht.In diesem Beispiel wird die twice-Funktion gleichzeitig für drei lokale Variablen aufgerufen, und das Ergebnis wird auf der Konsole ausgegeben.

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

Dieses Beispiel erzeugt folgende Ausgabe:

Vollständige Beispiele für den parallel_invoke-Algorithmus finden Sie unter Gewusst wie: Verwenden von parallel_invoke zum Schreiben einer Runtime für paralleles Sortieren und Gewusst wie: Ausführen von parallelen Vorgängen mithilfe von parallel_invoke.

Anfang[]

Die parallel_transform und parallel_reduce Algorithmen

Die concurrency::parallel_transform und concurrency::parallel_reduce Algorithmen sind parallele Versionen der STL-Algorithmen std::transform und std::accumulate, bzw.Die Concurrency Runtime-Versionen verhalten sich wie die STL-Versionen, außer dass die Vorgangsreihenfolge wird nicht bestimmt, da sie parallel ausführen.Verwenden Sie diese Algorithmen, wenn Sie mit einem Satz von arbeiten, der groß genug ist, Leistungs- und Skalierbarkeitsvorteile von parallel verarbeitet werden abzurufen.

Wichtig
Die parallel_transform und parallel_reduce Algorithmen unterstützen nur direkt, bidirektional und Vorwärtsiteratoren, da diese Iteratoren stabile Speicheradressen erzeugen.Außerdem müssen diese Iteratoren Nicht-const L-Werte erzeugen.

Der Algorithmus parallel_transform

Sie können den parallel transform Algorithmus verwenden, um viele Datenparallelisierungsvorgänge auszuführen.Sie haben unter anderem folgende Möglichkeiten:

• Passen Sie die Helligkeit eines Bilds, und führen Sie andere Bildverarbeitungsvorgänge aus.

• Summieren Sie oder verwenden Sie das Skalarprodukt zwischen zwei Vektoren, und führen Sie andere numerische Berechnungen für Vektoren aus.

• Führen Sie 3D-Strahlnablaufverfolgung aus, in der jede Iteration ein Pixel verweist, das gerendert werden muss.

Im folgenden Beispiel wird die grundlegende Struktur an, die verwendet wird, um den parallel_transform Algorithmus aufzurufen.Dieses Beispiel negiert jedes Element eines - Objekts std::vector auf zwei Arten.Die erste Methode verwendet einen Lambda-Ausdruck.Die zweite Methode verwendet std::negate, die von std::unary_function abgeleitet.

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

Vorsicht
In diesem Beispiel wird die grundlegende Verwendung von parallel_transform.Da die Arbeitsfunktion keinen beträchtlichen Arbeitsaufwand ausführt, wird ein bedeutender Anstieg in der Leistung in diesem Beispiel nicht erwartet.

Der parallel_transform Algorithmus verfügt über zwei Überladungen.Die erste Überladung akzeptiert einen Eingabebereich und eine unäre Funktion.Die unäre Funktion kann ein Lambda-Ausdruck sein, der ein Argument, ein Funktionsobjekt oder einen Typ akzeptiert, der von unary_function abgeleitet.Die zweite Überladung akzeptiert zwei Eingabebereiche und eine binäre Funktion.Die binäre Funktion kann ein Lambda-Ausdruck sein, der zwei Argumente, ein Funktionsobjekt oder einen Typ akzeptiert, der von std::binary_function abgeleitet.Das folgende Beispiel verdeutlicht diese Unterschiede.

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

Wichtig
Der Iterator, den Sie für die Ausgabe von parallel_transform angeben, muss sich vollständig überlappen der Eingabeiterator oder gar nicht überschneiden.Das Verhalten dieses Algorithmus ist nicht angegeben, wenn die Eingabe und die Ausgabeiteratoren sich teilweise überschneiden.

Der Algorithmus parallel_reduce

Der parallel_reduce Algorithmus ist nützlich, wenn Sie eine Sequenz von Vorgängen verfügen, die die assoziative Eigenschaft erfüllen.(Dieser Algorithmus erfordert nicht die auswechselbare Eigenschaft.) Im Folgenden einige der Operationen, die Sie mit parallel_reduce ausführen können:

• Multiplizieren Sequenzen von Matrizen, um eine Matrix zu erzeugen.

• Multiplizieren eines Vektor durch eine Sequenz von Matrizen, um einen Vektor zu erzeugen.

• Leiten Sie die Länge einer Sequenz von Zeichenfolgen.

• Kombinieren Sie eine Liste von Elementen, wie Zeichenfolgen, in ein Element.

Die folgenden grundlegenden Beispiel zeigt, wie der parallel_reduce Algorithmus, um eine Sequenz von Zeichenfolgen in eine Zeichenfolge zu kombinieren.Wie bei den Beispielen für parallel_transform, Leistungsgewinne werden nicht in diesem grundlegenden Beispiel erwartet.

// 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.
*/

In vielen Fällen können Sie an parallel_reduce als Kurznotation für die Verwendung des - Algorithmus parallel_for_each zusammen mit der - Klasse concurrency::combinable vorstellen.

Beispiel: Zuordnung ausgeführt und reduzieren Sie parallel

Ein Reservierungsoperation wendet eine Funktion auf jedes Wert in einer Sequenz.Ein reduzierens vorgang kombiniert die Elemente einer Sequenz in einen Wert.Sie können die Klassen std::transformstd::accumulate der Standardvorlagenbibliothek (STL) verwenden, die Zuordnung ausführt und Vorgänge zu reduzieren.Für viele Probleme, können Sie den parallel_transform Algorithmus verwenden, um den Reservierungsoperation parallel auszuführen und die parallel_reduce Algorithmus übergeben den reduzierensvorgang parallel aus.

Im folgenden Beispiel wird die Zeit verglichen, der angenommen, um die Summe von Primzahlen seriell und parallel berechnet.Die Zuordnungsphase transformiert keine Primzahlen Werte auf 0 und die reduzierensphase zählt die Werte.

// 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
*/

Ein weiteres Beispiel, das eine Zuordnung ausführt und Vorgang parallel reduziert, finden Sie unter Gewusst wie: Paralleles Ausführen von Zuordnungs- und Reduzierungsoperationen.

Anfang[]

Partitionieren der Arbeit

Um einen Vorgang in einer Datenquelle zu parallelisieren, ist ein wichtiger Schritt die Quelle in mehrere Abschnitte zu partitionieren auf die von mehreren Threads gleichzeitig zugegriffen werden kann.Ein Partitionierer gibt an, wie ein paralleler Algorithmus Bereiche zwischen Threads partitionieren sollte.Wie in diesem Dokument zuvor erläutert, verwendet die PPL einen standardmäßigen Partitionierungsmechanismus, der eine ursprüngliche Arbeitsauslastung erstellt und dann einen Arbeitsübernahme-Algorithmus und einen Bereich verwendet, die stehlen, der diese Partitionen, wenn die unausgeglichen sind.Wenn eine Schleifeniteration einen Bereich von Iterationen abgeschlossen hat, verteilt die Laufzeit Arbeit von anderen Threads auf diesem Thread.Für einige Szenarien, sollten Sie einen anderen Partitionierungsmechanismus angeben, der besser zu dem Problem verarbeiten.

parallel_for, parallel_for_each und parallel_transform Algorithmen bieten überladene Versionen, die einen zusätzlichen Parameter annehmen, _Partitioner.Dieser Parameter definiert den Partitionierertyp, der Arbeit unterteilt.Im Folgenden sehen Sie die Arten von Partitionierern, die die PPL definiert:

• concurrency::affinity_partitioner
  Verteilungsarbeit in eine feste Anzahl von Bereichen (in der Regel die Anzahl der Arbeitsthreads, die verfügbar sind, an der Schleife arbeiten).Dieser Partitionierertyp ähnelt static_partitioner, verbessert jedoch die Cacheaffinität, je nachdem, das sie Bereiche zu den Arbeitsthreads zugeordnet wird.Dieser Partitionierertyp kann die Leistung, wenn eine - Schleife über dem gleichen Dataset mehrmals (ausgeführt wird wie eine Schleife in einer Schleife) und die Datenpassung im Cache verbessern.Dieser Partitionierer nicht komplett gehört zum Abbruch beteiligt.Es wird außerdem nicht kooperative Blockierungssemantiken und kann nicht mit parallelen Schleifen deshalb verwendet werden, die eine Abhängigkeit vorwärts haben.

• concurrency::auto_partitioner
  Dividiert funktionieren in eine Anfangszahl Bereiche (in der Regel die Anzahl der Arbeitsthreads, die verfügbar sind, an der Schleife arbeiten).Die Laufzeit verwendet diesen Typ standardmäßig, wenn Sie keinen überladenen parallelen Algorithmus aufrufen, der einen _Partitioner-Parameter akzeptiert.Jeder Bereich kann in SubBereiche unterteilt werden und aktiviert dadurch Lastenausgleich, um fungiert.Wenn ein Leistungsbereich abschließt, verteilt die Laufzeit SubBereiche der Arbeit von anderen Threads auf diesem Thread.Verwenden Sie diesen Partitionierer, wenn die Arbeitsauslastung nicht unter einer der anderen Kategorien fällt, oder Sie vollständige Unterstützung für das Abbruch- oder die kooperative benötigen.

• concurrency::simple_partitioner
  Dividiert funktionieren in Bereiche so, dass jeder Bereich mindestens die Anzahl der Iterationen hat, die von der angegebenen Segmentgröße angegeben werden.Dieser Partitionierertyp hat im Lastenausgleich beteiligt; jedoch weist die Laufzeit Bereiche nicht in SubBereiche unter.Für jeden Worker führt die Laufzeit die Abbruch und Lastenausgleich nach vollständige _Chunk_size Iterationen aus.

• concurrency::static_partitioner
  Verteilungsarbeit in eine feste Anzahl von Bereichen (in der Regel die Anzahl der Arbeitsthreads, die verfügbar sind, an der Schleife arbeiten).Dieser Partitionierertyp kann die Leistung verbessern, da er nicht Arbeitsübernahme verwendet und daher weniger Aufwand hat.Verwenden Sie diesen Partitionierertyp, wenn jede Iteration einer parallelen Schleife einen festen und einheitlichen Arbeitsaufwand ausgeführt wird und Sie keine Abbruchunterstützung benötigen oder die die kooperative weiterleiten.

Vorsicht
Die parallel_for_each und parallel_transform Algorithmen unterstützen nur Container, die direkte Iteratoren (z std::vector) für das statische verwenden, einfach, und Affinitätspartitionierer.Die Verwendung von Containern, die bidirektionale verwenden und von Vorwärtsiteratoren erzeugt einen Fehler.Der standardmäßige Partitionierer, auto_partitioner, unterstützt alle drei dieser Iteratortypen.

In der Regel werden diese Partitionierer genauso, außer affinity_partitioner verwendet.Die meisten Partitionierertypen behalten keine Zustand bei und werden nicht zur Laufzeit geändert.Daher können Sie diese Partitioniererobjekte auf der Aufrufsite, wie im folgenden Beispiel gezeigt erstellen.

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

Sie müssen jedoch ein affinity_partitioner-Objekt als Nicht-const übergeben, L-Werts-Verweis, sodass der Algorithmus Zustand speichern kann, dass zukünftige Schleifen wiederverwenden.Im folgenden Beispiel wird eine einfache Anwendung, die den gleichen Vorgang in einem Dataset mehrmals parallel ausführt.Die Verwendung von affinity_partitioner kann die Leistung verbessern, da das Array wahrscheinlich ist, im Cache angepasst.

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

Vorsicht
Seien Sie vorsichtig, wenn Sie vorhandenen Code ändern, der im kooperativer Blockierungssemantiken basiert, um static_partitioner oder affinity_partitioner zu verwenden.Diese Partitionierertypen verwenden keine Lastenausgleich oder reichen stehlender und können das Verhalten der Anwendung daher ändern.

Die beste Möglichkeit, zu bestimmen, ob ein Partitionierer in einem gegebenen Szenario ist durch Experimentieren zu messen verwendet, wie viel Zeit Vorgänge verwendet, um bei repräsentativer Auslastung und Computerkonfigurationen abzuschließen.Statische Partitionierung kann z. B. für beträchtliche Geschwindigkeitssteigerungen auf einem Multikerncomputer sorgen, der nur einige Kerne besitzt, doch auf Computern mit verhältnismäßig vielen Kernen kann es zu einer Verlangsamung kommen.

Anfang[]

Parallele Sortierung

Die PPL bietet drei Sortieralgorithmen festlegen: concurrency::parallel_sort, concurrency::parallel_buffered_sort und concurrency::parallel_radixsort.Diese Sortieralgorithmen sind nützlich, wenn Sie ein Dataset verfügen, das von parallel profitieren sortiert werden kann.Insbesondere parallel sortieren ist nützlich, wenn Sie ein großes Dataset ist, oder wenn Sie einen rechenintensiven Vergleich verwenden, um die Daten zu sortieren.Jedes dieser Algorithmussortierungselemente an der Stelle.

Die parallel_sort und parallel_buffered_sort Algorithmen sind beide verglichene-basierten Algorithmen.Das heißt, sie vergleichen Elemente durch einen Wert.Der parallel_sort Algorithmus hat keine zusätzlichen Arbeitsspeicheranforderungen, und ist für allgemeine Sortierung entsprechend.Der parallel_buffered_sort Algorithmus kann eine bessere Leistung als parallel_sort, aber er benötigt O(N) Leerzeichen.

Der parallel_radixsort Algorithmus ist hashbasiert.Das heißt, verwendet er ganzzahlige Schlüssel sortieren, wenn Elemente.Durch die Schlüssel verwendet, kann dieser Algorithmus das Ziel eines - Elements direkt ableiten, anstatt, Vergleiche zu verwenden.Wie parallel_buffered_sort erfordert dieser Algorithmus O(N) Leerzeichen.

In der folgenden Tabelle werden die wichtigen Eigenschaften der drei parallelen Sortieralgorithmen zusammen.

Algorithmus	Beschreibung	Sortiervorrichtung	Sortierungs-Stabilität	Arbeitsspeicheranforderungen	Zeit-Komplexität	Iteratorzugriff
parallel_sort	Allgemeine verglichene-basierte Sortierung.	Verglichene-basiert (aufsteigend)	Instabil	Keine	O((N/P)log(N/P) + 2N((P-1)/P))	Random
parallel_buffered_sort	Schnellere allgemeine verglichene-basierte Sortierung, erfordert die O (n) Leerzeichen.	Verglichene-basiert (aufsteigend)	Instabil	Erfordert O(N) zusätzliches Leerzeichen	O((N/P)log(N))	Random
parallel_radixsort	Ganzzahlige auf Schlüsseln basierende Sortierung, erfordert die O (n) Leerzeichen.	Hashbasiert	Stabil	Erfordert O(N) zusätzliches Leerzeichen	O(N/P)	Random

Die folgende Abbildung zeigt die wichtigen Eigenschaften der drei parallelen Sortieralgorithmen grafischer an.

Diese parallelen Sortieralgorithmen folgen den Regeln des Abbruchs und der Ausnahmebehandlung.Weitere Informationen zum Abbruch und Ausnahmebehandlung in der Concurrency Runtime, finden Sie unter Abbrechen von parallelen Algorithmen und Ausnahmebehandlung in der Concurrency Runtime.

Tipp

Diese parallelen Sortieralgorithmen unterstützen Verschiebesemantik.Sie können einen Verschiebungszuweisungsoperator definieren, um Swapgeschäfte ermöglichen, effizienter ausgeführt werden.Weitere Informationen zu Verschiebesemantik und den Verschiebungszuweisungsoperator, finden Sie unter Rvalu-Verweis-Deklarator: && und Gewusst wie: Schreiben Sie einen Verschiebungskonstruktor.Wenn Sie keine Verschiebungszuweisungsoperator- oder -austauschfunktion angeben, verwenden die Sortieralgorithmen den Kopierkonstruktor.

Die folgenden grundlegenden Beispiel zeigt, wie parallel_sort verwendet, um zu sortieren vector von int-Werten.Standardmäßig verwendet parallel_sortstd::less, um Werte zu vergleichen.

// 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
*/

Dieses Beispiel zeigt, wie eine benutzerdefinierte Compare-Funktion bereitstellt.Er verwendet die - Methode std::complex::real sortieren, wenn std::complex<double>-Werte in aufsteigender Reihenfolge.

// 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)
*/

Dieses Beispiel zeigt, wie eine Hashfunktion zum parallel_radixsort Algorithmus bereitgestellt werden.Dieses Beispiel sortiert 3D-Punkten.Die Punkte werden auf Grundlage der Abstand eines Daten sortiert.

// 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
*/

Für Abbildung verwendet dieses Beispiel ein relativ kleines Dataset.Sie können die ursprüngliche Größe des Vektors erhöhen, um mit Leistungsverbesserungen zu größeren Sätzen von Daten zu experimentieren.

In diesem Beispiel wird ein Lambda-Ausdruck als die Hashfunktion.Sie können eine der integrierten Implementierungen der std::hash-Klasse verwenden oder eine eigene Spezialisierung definieren.Sie können ein benutzerdefiniertes Hashfunktionsobjekt, wie in diesem Beispiel gezeigt auch verwenden:

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

Die Hashfunktion muss einen ganzzahligen Typ zurückgeben (std::is_integral::value muss true sein).Dieser ganzzahlige Typ konvertierbar sein muss, size_t einzugeben.

Auswählen eines Sortieralgorithmus

In vielen Fällen stellt parallel_sort die beste Gleichgewicht der Geschwindigkeits- und Arbeitsspeicherleistung.Wie Sie die Größe des Datasets, der Anzahl der verfügbaren Prozessoren oder der Komplexität der Compare-Funktion vergrößern, können parallel_buffered_sort oder parallel_radixsort optimiert werden.Die beste Möglichkeit, zu bestimmen, die in einem gegebenen Szenario zu verwenden, ist der Sortieralgorithmus durch Experimentieren zu ermitteln, wie lange die benötigt, um typische Daten mit von repräsentativen Computerkonfigurationen zu sortieren.Führen Sie die folgenden Richtlinien kennen, wenn Sie eine Sortierungsstrategie auswählen.

• Die Größe des Datasets.In diesem Dokument enthält ein kleines Dataset weniger als 1.000 Elemente enthält, ein Dataset Center zwischen 10.000 und 100.000 Elementen, und ein großes Dataset enthält mehr als 100.000 Elemente.

• Der Wert, den die Compare-Funktion oder Hashfunktion ausführt.

• Die Menge von verfügbaren Computerressourcen.

• Die Eigenschaften des Datasets.Beispielsweise kann ein Algorithmus gut für Daten, die bereits nahezu sortiert wird, nicht aber auch für Daten aus, die vollständig unsortiert ist.

• Die Segmentgröße.Das optionale _Chunk_size-Argument gibt wenn die Algorithmusschalter aus einer entlang einer seriellen Sortierungsimplementierung an, während es die gesamte Sortierung in kleinere Arbeitseinheiten unterteilt.Wenn Sie beispielsweise 512 bereitstellen, die Algorithmusschalter zur seriellen Implementierung, wenn eine Arbeitseinheit enthält 512 oder weniger Elemente.Eine serielle Implementierung kann Gesamtleistung verbessert, da sie den Mehraufwand entfernt, der erforderlich ist, Daten parallel zu verarbeiten.

Parallel zu sortieren kann nicht empfehlenswert, ein kleines Dataset, auch wenn viele verfügbaren Computerressourcen haben, oder die Compare-Funktion oder Hashfunktion einen relativ großen Arbeitsaufwand ausführt.Sie können std::sort-Funktion verwenden, um zu sortieren kleine Datasets.(parallel_sort und parallel_buffered_sort rufen sort auf, wenn Sie eine Segmentgröße angeben, die größer als ist, das Dataset; jedoch würde parallel_buffered_sortO(N) Leerzeichen zuordnen müssen, das zusätzliche Zeit aufgrund des Sperrenkonflikts oder der Speicherbelegung müssen konnte.)

Wenn Sie Speicherplatz sparen müssen, oder die Speicherbelegungsfunktion abhängig von Sperrkonflikten ist, verwendet parallel_sort, Sortieren ein mittelgroßes Dataset.parallel_sort erfordert kein zusätzliches Leerzeichen; die anderen Algorithmen müssen O(N) Leerzeichen.

Verwenden Sie parallel_buffered_sort sortieren, wenn mittelgroße Datasets und die Anwendung die zusätzliche O(N) Speicherplatzanforderung erfüllt.parallel_buffered_sort kann besonders hilfreich sein, wenn Sie viele Computerressourcen oder eine umfangreiche Compare-Funktion oder eine Hashfunktion haben.

Verwenden Sie parallel_radixsort sortieren, wenn große Datasets und die Anwendung die zusätzliche O(N) Speicherplatzanforderung erfüllt.parallel_radixsort kann besonders nützlich sein, wenn der entsprechende Vergleich teurer ist, oder wenn beide Vorgänge ressourcenintensiv sind.

Vorsicht
Das Implementieren einer guten Hashfunktion erfordert, dass Sie den Datasetbereich kennen und wie jedes Element im Dataset auf einen geeigneten Wert ohne Vorzeichen transformiert wird.Da der Hashvorgang an Werten ohne Vorzeichen funktioniert, sollten Sie eine andere Sortierungsstrategie, wenn Hashwerte ohne Vorzeichen nicht erzeugt werden können.

Im folgenden Beispiel wird die Leistung von sort, von parallel_sort, von parallel_buffered_sort und von parallel_radixsort durch denselben großen Satz von zufälligen Daten.

// 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.
*/

In diesem Beispiel das ausgegangen wird, dass sie zulässig ist, O(N) Leerzeichen bei der Sortierung zuzuordnen, führt parallel_radixsort die besten auf diesem Dataset auf dieser Computerkonfiguration aus.

Anfang[]

Verwandte Themen

Titel	Beschreibung
Gewusst wie: Schreiben einer parallel_for-Schleife	Erläutert, wie der parallel_for-Algorithmus für die Matrixmultiplikation verwendet wird.
Gewusst wie: Schreiben einer parallel_for_each-Schleife	Erläutert, wie die Anzahl der Primzahlen in einem std::array-Objekt mit dem parallel_for_each-Algorithmus parallel berechnet wird.
Gewusst wie: Verwenden von parallel_invoke zum Schreiben einer Runtime für paralleles Sortieren	Erläutert, wie die Leistung des bitonischen Sortieralgorithmus mit dem parallel_invoke-Algorithmus verbessert werden.
Gewusst wie: Ausführen von parallelen Vorgängen mithilfe von parallel_invoke	Erläutert, wie die Leistung eines Programms mit dem parallel_invoke-Algorithmus verbessert werden kann, das mehrere Vorgänge in einer freigegebenen Datenquelle ausführt.
Gewusst wie: Paralleles Ausführen von Zuordnungs- und Reduzierungsoperationen	Zeigt, wie die parallel_transform und parallel_reduce Algorithmen verwendet, um eine Zuordnung ausführt und Vorgang zu reduzieren, die die Vorkommen von Wörtern in Dateien zählt.
Parallel Patterns Library (PPL)	Beschreibt die PPL, die ein obligatorisches Programmiermodell bereitstellt, das Skalierbarkeit und Benutzerfreundlichkeit beim Entwickeln gleichzeitiger Anwendungen unterstützt.
Abbruch in der PPL	Erläutert die Rolle des Abbruchs in der PPL, wie die parallele Verarbeitung abgebrochen wird und wie ermittelt wird, wann eine Aufgabengruppe abgebrochen wird.
Ausnahmebehandlung in der Concurrency Runtime	Beschreibt die Rolle der Ausnahmebehandlung in der Concurrency Runtime.

Verweis

parallel_for-Funktion

parallel_for_each-Funktion

parallel_invoke-Funktion

affinity_partitioner-Klasse

auto_partitioner-Klasse

simple_partitioner-Klasse

static_partitioner-Klasse

parallel_sort-Funktion

parallel_buffered_sort-Funktion

parallel_radixsort-Funktion