Parallele Algorithmen

Die Parallel Patterns Library (PPL) stellt Algorithmen bereit, die gleichzeitig Arbeiten an Sammlungen von Daten ausführen. Diese Algorithmen ähneln denen, die von der C++-Standardbibliothek bereitgestellt werden.

Die parallelen Algorithmen bestehen aus vorhandenen Funktionen in der Parallelitätslaufzeit. Beispielsweise verwendet der Algorithmus "concurrency::p arallel_for " ein Parallelitätsobjekt::structured_task_group zum Ausführen der parallelen Schleifeniterationen. Die parallel_for Algorithmuspartitionen funktionieren aufgrund der verfügbaren Anzahl von Rechenressourcen optimal.

Abschnitte

• Der parallel_for Algorithmus

• Der parallel_for_each Algorithmus

• Der parallel_invoke Algorithmus

• Die algorithmen parallel_transform und parallel_reduce

  • Der parallel_transform Algorithmus

  • Der parallel_reduce Algorithmus

  • Beispiel: Ausführen einer Karte und Reduzieren parallel

• Partitionierungsarbeit

• Parallele Sortierung

  • Auswählen eines Sortieralgorithmus

Der parallel_for Algorithmus

Die Parallelität::p arallel_for-Algorithmus führt wiederholt dieselbe Aufgabe parallel aus. Jede dieser Aufgaben wird durch einen Iterationswert parametrisiert. Dieser Algorithmus ist nützlich, wenn Sie über einen Schleifentext verfügen, der keine Ressourcen zwischen Iterationen dieser Schleife gemeinsam verwendet.

Der parallel_for Algorithmus partitioniert Aufgaben optimal für die parallele Ausführung. Es verwendet einen Arbeitsdiebstahlalgorithmus und einen Bereichsdiebstahl, um diese Partitionen auszugleichen, wenn Workloads nicht ausgeglichen sind. Wenn eine Schleifeniteration kooperativ blockiert wird, verteilt die Laufzeit den Bereich der Iterationen, die dem aktuellen Thread zugewiesen sind, auf andere Threads oder Prozessoren weiter. Wenn ein Thread einen Bereich von Iterationen abgeschlossen hat, verteilt die Laufzeit die Arbeit von anderen Threads auf diesen Thread. Der parallel_for Algorithmus unterstützt auch geschachtelte Parallelität. Wenn eine parallele Schleife eine weitere parallele Schleife enthält, koordiniert die Laufzeit die Verarbeitungsressourcen zwischen den Schleifenkörpern auf effiziente Weise für die parallele Ausführung.

Der parallel_for Algorithmus verfügt über mehrere überladene Versionen. Die erste Version verwendet einen Startwert, einen Endwert und eine Arbeitsfunktion (einen Lambda-Ausdruck, ein Funktionsobjekt oder einen Funktionszeiger). Die zweite Version verwendet einen Anfangswert, einen Endwert, einen Wert, um den Sie schrittieren möchten, und eine Arbeitsfunktion. Die erste Version dieser Funktion verwendet 1 als Schrittwert. Die verbleibenden Versionen verwenden Partitionerobjekte, mit denen Sie angeben können, wie parallel_for Partitionsbereiche zwischen Threads aufgeteilt werden sollen. Partitionierer werden im Abschnitt Partitionierungsarbeit in diesem Dokument ausführlicher erläutert.

Sie können viele for Schleifen konvertieren, um sie zu verwenden parallel_for. Der parallel_for Algorithmus unterscheidet sich jedoch auf folgende Weise von der for Anweisung:

• Der parallel_for Algorithmus parallel_for führt 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 kleiner als lastist.

• Der _Index_type Typparameter muss ein integraler Typ sein. Dieser integrale Typ kann signiert oder nicht signiert werden.

• Die Iteration der Schleife muss vorwärts erfolgen. Der parallel_for Algorithmus löst eine Ausnahme vom Typ "std::invalid_argument " aus, wenn der _Step Parameter kleiner als 1 ist.

• Der Ausnahmebehandlungsmechanismus für den parallel_for Algorithmus unterscheidet sich von der einer for Schleife. Wenn mehrere Ausnahmen gleichzeitig in einem parallelen Schleifentext auftreten, verteilt die Laufzeit nur eine der Ausnahmen für den thread, der aufgerufen wurde parallel_for. Wenn eine Schleifeniteration eine Ausnahme auslöst, beendet die Laufzeit die gesamte Schleife nicht sofort. Stattdessen wird die Schleife im abgebrochenen Zustand platziert, und die Laufzeit verwirft alle Aufgaben, die noch nicht gestartet wurden. Weitere Informationen zur Ausnahmebehandlung und parallelen Algorithmen finden Sie unter "Ausnahmebehandlung".

Obwohl der parallel_for Algorithmus keine beliebigen Beendigungsbedingungen unterstützt, können Sie den Abbruch verwenden, um alle Aufgaben zu beenden. Weitere Informationen zum Abbruch finden Sie unter "Abbruch" in der PPL.

Hinweis

Die Planungskosten, die sich aus dem Lastenausgleich und der Unterstützung für Features wie z. B. abbruch ergeben, können die Vorteile der Ausführung des Schleifentexts nicht parallel überwinden, insbesondere, wenn der Schleifentext relativ klein ist. Sie können diesen Aufwand minimieren, indem Sie einen Partitionierer in ihrer parallelen Schleife verwenden. Weitere Informationen finden Sie unter Partitionierungsarbeiten weiter unten in diesem Dokument.

Beispiel

Das folgende Beispiel zeigt die grundlegende Struktur des parallel_for Algorithmus. In diesem Beispiel wird jeder Wert im Bereich [1, 5] parallel in der Konsole gedruckt.

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

1 2 4 3 5

Da der parallel_for Algorithmus parallel für jedes Element fungiert, variiert die Reihenfolge, in der die Werte in der Konsole gedruckt werden.

Ein vollständiges Beispiel, das den parallel_for Algorithmus verwendet, finden Sie unter How to: Write a parallel_for Loop.

[Nach oben]

Der parallel_for_each Algorithmus

Die Parallelität::p arallel_for_each Algorithmus führt Aufgaben für einen iterativen Container aus, z. B. die von der C++-Standardbibliothek bereitgestellten. Er verwendet die gleiche Partitionierungslogik wie der parallel_for-Algorithmus.

Der parallel_for_each Algorithmus ähnelt dem C++-Standardbibliotheksalgorithmus std::for_each , mit der Ausnahme, dass der parallel_for_each Algorithmus die Aufgaben gleichzeitig ausführt. Wie andere parallele Algorithmen parallel_for_each werden die Aufgaben nicht in einer bestimmten Reihenfolge ausgeführt.

Obwohl der parallel_for_each Algorithmus sowohl für Weiterleitungs iteratoren als auch für Iteratoren mit wahllosem Zugriff funktioniert, wird er mit Iteratoren mit zufälligen Zugriffen besser ausgeführt.

Beispiel

Das folgende Beispiel zeigt die grundlegende Struktur des parallel_for_each Algorithmus. In diesem Beispiel wird jeder Wert in einem std::array-Objekt parallel in der Konsole gedruckt.

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

Dieses Beispiel erzeugt die folgende Beispielausgabe:

4 5 1 2 3

Da der parallel_for_each Algorithmus parallel für jedes Element fungiert, variiert die Reihenfolge, in der die Werte in der Konsole gedruckt werden.

Ein vollständiges Beispiel, das den parallel_for_each Algorithmus verwendet, finden Sie unter How to: Write a parallel_for_each Loop.

[Nach oben]

Der parallel_invoke Algorithmus

Der Parallelitätsalgorithmus::p arallel_invoke führt eine Reihe von Aufgaben parallel aus. Sie wird erst zurückgegeben, wenn jeder Vorgang abgeschlossen ist. Dieser Algorithmus ist nützlich, wenn Sie mehrere unabhängige Aufgaben haben, die Sie gleichzeitig ausführen möchten.

Der parallel_invoke Algorithmus verwendet als Parameter eine Reihe von Arbeitsfunktionen (Lambda-Funktionen, Funktionsobjekte oder Funktionszeiger). Der parallel_invoke Algorithmus wird überladen, um zwischen zwei und zehn Parametern zu übernehmen. Jede Funktion, an parallel_invoke die Sie übergeben, muss null Parameter annehmen.

Wie andere parallele Algorithmen parallel_invoke werden die Aufgaben nicht in einer bestimmten Reihenfolge ausgeführt. Im Thema "Task Parallelism" wird erläutert, wie sich der parallel_invoke Algorithmus auf Aufgaben und Aufgabengruppen bezieht.

Beispiel

Das folgende Beispiel zeigt die grundlegende Struktur des parallel_invoke Algorithmus. In diesem Beispiel wird die twice Funktion gleichzeitig für drei lokale Variablen aufgerufen und das Ergebnis in der Konsole gedruckt.

// 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 die folgende Ausgabe:

108 11.2 HelloHello

Vollständige Beispiele, die den parallel_invoke Algorithmus verwenden, finden Sie unter How to: Use parallel_invoke to Write a Parallel Sort Routine and How to: Use parallel_invoke to Execute Parallel Operations.

[Nach oben]

Die algorithmen parallel_transform und parallel_reduce

Die Parallelversionen der Algorithmen "concurrency::p arallel_transform " und "concurrency::p arallel_reduce " sind parallele Versionen der C++-Standardbibliotheksalgorithmen "std::transform " bzw . "std::accumulate". Die Parallelitäts-Runtime-Versionen verhalten sich wie die C++-Standardbibliotheksversionen, mit der Ausnahme, dass die Vorgangsreihenfolge nicht bestimmt wird, da sie parallel ausgeführt werden. Verwenden Sie diese Algorithmen, wenn Sie mit einem Satz arbeiten, der groß genug ist, um Leistungs- und Skalierbarkeitsvorteile davon zu erhalten, dass sie parallel verarbeitet werden.

Wichtig

Die parallel_transform Algorithmen parallel_reduce unterstützen nur zufälligen Zugriff, bidirektionale und Weiterleitungs iteratoren, da diese Iteratoren stabile Speicheradressen erzeugen. Außerdem müssen diese Iteratoren nicht-l-Werteconst erzeugen.

Der parallel_transform Algorithmus

Sie können den parallel transform Algorithmus verwenden, um viele Daten-Parallelisierungsvorgänge auszuführen. Sie können zum Beispiel Folgendes:

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

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

• Führen Sie die 3D-Strahlenverfolgung durch, wobei jede Iteration auf ein Pixel verweist, das gerendert werden muss.

Das folgende Beispiel zeigt die grundlegende Struktur, die zum Aufrufen des parallel_transform Algorithmus verwendet wird. In diesem Beispiel werden die einzelnen Elemente eines std::vector-Objekts auf zwei Arten aufgehoben. Die erste Methode verwendet einen Lambda-Ausdruck. Die zweite Methode verwendet "std::negate", die von "std::unary_function" abgeleitet ist.

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

Warnung

In diesem Beispiel wird die grundlegende Verwendung von parallel_transform. Da die Arbeitsfunktion keine erhebliche Arbeit ausführt, wird in diesem Beispiel keine erhebliche Leistungssteigerung erwartet.

Der parallel_transform Algorithmus verfügt über zwei Überladungen. Die erste Überladung verwendet einen Eingabebereich und eine unäre Funktion. Die unäre Funktion kann ein Lambda-Ausdruck sein, der ein Argument, ein Funktionsobjekt oder einen Typ verwendet, von unary_functiondem abgeleitet wird. 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 verwendet, der von "std::binary_function" abgeleitet ist. Im folgenden Beispiel werden diese Unterschiede veranschaulicht.

//
// 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 parallel_transform bereitstellen, muss den Eingabe-Iterator vollständig überlappen oder überlappen. Das Verhalten dieses Algorithmus ist nicht angegeben, wenn sich die Eingabe- und Ausgabe iteratoren teilweise überlappen.

Der parallel_reduce Algorithmus

Der parallel_reduce Algorithmus ist nützlich, wenn Sie eine Abfolge von Vorgängen haben, die die assoziative Eigenschaft erfüllen. (Für diesen Algorithmus ist die kommutative Eigenschaft nicht erforderlich.) Hier sind einige der Vorgänge, mit parallel_reducedenen Sie folgendes ausführen können:

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

• Multiplizieren Sie einen Vektor mit einer Sequenz von Matrizen, um einen Vektor zu erzeugen.

• Berechnen sie die Länge einer Abfolge von Zeichenfolgen.

• Kombinieren Sie eine Liste von Elementen, z. B. Zeichenfolgen, in einem Element.

Das folgende grundlegende Beispiel zeigt, wie Sie den parallel_reduce Algorithmus verwenden, um eine Abfolge von Zeichenfolgen in einer Zeichenfolge zu kombinieren. Wie bei den Beispielen für parallel_transform, werden Leistungsgewinne in diesem grundlegenden Beispiel nicht 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{
      L"Lorem ",
      L"ipsum ",
      L"dolor ",
      L"sit ",
      L"amet, ",
      L"consectetur ",
      L"adipiscing ",
      L"elit."};
      
  // Reduce the vector to one string in parallel.
  wcout << parallel_reduce(begin(words), end(words), wstring()) << endl;
}

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

In vielen Fällen können Sie sich parallel_reduce die Verwendung des parallel_for_each Algorithmus zusammen mit der parallelen Klasse::kombinationsfähig vorstellen.

Beispiel: Ausführen einer Karte und Reduzieren parallel

Ein Kartenvorgang wendet eine Funktion auf jeden Wert in einer Sequenz an. Ein Reduzierter Vorgang kombiniert die Elemente einer Sequenz in einem Wert. Sie können die C++-Standardbibliothek std::transform and std::kumulierte Funktionen verwenden, um Zuordnungen durchzuführen und Vorgänge zu reduzieren. Bei vielen Problemen können Sie jedoch den parallel_transform Algorithmus verwenden, um den Kartenvorgang parallel auszuführen, und der parallel_reduce Algorithmus führt den reduzierten Vorgang parallel aus.

Im folgenden Beispiel wird die Zeit verglichen, die zum Berechnen der Summe von Primzahlen fortlaufend und parallel benötigt wird.The following example compares the time that it takes to compute the sum of prime numbers serially and in parallel. Die Kartenphase wandelt nicht prime-Werte in 0 um, und die Reduzierung der Phasen summiert 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 den Vorgang parallel reduziert, finden Sie unter How to: Perform Map and Reduce Operations in Parallel.

[Nach oben]

Partitionierungsarbeit

Zum Parallelisieren eines Vorgangs für eine Datenquelle besteht ein wesentlicher Schritt darin, die Quelle in mehrere Abschnitte zu partitionieren , auf die gleichzeitig von mehreren Threads zugegriffen werden kann. Ein Partitioner gibt an, wie ein paralleler Algorithmus Bereiche zwischen Threads partitionieren soll. Wie bereits in diesem Dokument erläutert, verwendet die PPL einen Standardpartitionierungsmechanismus, der eine anfängliche Arbeitsauslastung erstellt und dann einen Arbeitsdiebstahlalgorithmus und einen Bereichsdiebstahl verwendet, um diese Partitionen auszugleichen, wenn Arbeitsauslastungen nicht ausgeglichen sind. Wenn z. B. eine Schleifeniteration einen Bereich von Iterationen abgeschlossen hat, verteilt die Laufzeit die Arbeit von anderen Threads auf diesen Thread. Für einige Szenarien sollten Sie jedoch einen anderen Partitionierungsmechanismus angeben, der besser für Ihr Problem geeignet ist.

Die parallel_for, parallel_for_eachund parallel_transform Algorithmen bieten überladene Versionen, die einen zusätzlichen Parameter verwenden. _Partitioner Dieser Parameter definiert den Partitioniertyp, der arbeit teilt. Hier sind die Arten von Partitionierern, die von der PPL definiert werden:

concurrency::affinity_partitioner
Dividiert Arbeit in eine feste Anzahl von Bereichen (in der Regel die Anzahl der Arbeitsthreads, die für die Arbeit an der Schleife verfügbar sind). Dieser Partitionertyp ähnelt static_partitioner, verbessert jedoch die Cacheaffinität durch die Zuordnung von Bereichen zu Arbeitsthreads. Dieser Partitionertyp kann die Leistung verbessern, wenn eine Schleife mehrmals über dasselbe Dataset ausgeführt wird (z. B. eine Schleife in einer Schleife), und die Daten passen in den Cache. Dieser Partitioner nimmt nicht vollständig am Abbruch teil. Sie verwendet auch keine kooperativ blockierende Semantik und kann daher nicht mit parallelen Schleifen verwendet werden, die eine Vorwärtsabhängigkeit aufweisen.

concurrency::auto_partitioner
Dividiert Arbeit in eine anfängliche Anzahl von Bereichen (in der Regel die Anzahl der Arbeitsthreads, die für die Arbeit an der Schleife verfügbar sind). Die Laufzeit verwendet diesen Typ standardmäßig, wenn Sie keinen überladenen parallelen Algorithmus aufrufen, der einen _Partitioner Parameter verwendet. Jeder Bereich kann in Unterbereiche unterteilt werden und ermöglicht dadurch das Auftreten des Lastenausgleichs. Wenn ein Arbeitsbereich abgeschlossen ist, verteilt die Laufzeit Teilbereiche der Arbeit von anderen Threads zu diesem Thread. Verwenden Sie diesen Partitionierer, wenn Ihre Workload nicht unter eine der anderen Kategorien fällt oder Sie vollständige Unterstützung für stornierungs- oder kooperative Blockierung benötigen.

concurrency::simple_partitioner
Dividiert Arbeit in Bereiche, sodass jeder Bereich mindestens die Anzahl der Iterationen aufweist, die durch die angegebene Blockgröße angegeben werden. Dieser Partitionertyp nimmt am Lastenausgleich teil; Die Laufzeit unterteilt jedoch keine Bereiche in Unterbereiche. Für jeden Worker überprüft die Laufzeit nach Abschluss der Iteration den Abbruch und führt den Lastenausgleich aus _Chunk_size .

concurrency::static_partitioner
Dividiert Arbeit in eine feste Anzahl von Bereichen (in der Regel die Anzahl der Arbeitsthreads, die für die Arbeit an der Schleife verfügbar sind). Dieser Partitioniertyp kann die Leistung verbessern, da es keine Arbeitsdiebstahl verwendet und daher weniger Aufwand hat. Verwenden Sie diesen Partitioniertyp, wenn jede Iteration einer parallelen Schleife eine feste und einheitliche Menge an Arbeit ausführt und Sie keine Unterstützung für die Abbruch- oder Weiterleitungsblockierung benötigen.

Warnung

Die parallel_for_each Und parallel_transform Algorithmen unterstützen nur Container, die Zufällige Zugriffs iteratoren (z. B. std::vector) für statische, einfache und Affinitätspartitioner verwenden. Die Verwendung von Containern, die bidirektionale und Weiterleitungs iteratoren verwenden, erzeugt einen Kompilierungszeitfehler. Die Standardpartitionierung unterstützt auto_partitioneralle drei iteratortypen.

In der Regel werden diese Partitionierer auf die gleiche Weise verwendet, mit Ausnahme von affinity_partitioner. Die meisten Partitioniertypen behalten den Zustand nicht bei und werden von der Laufzeit nicht geändert. Daher können Sie diese Partitionerobjekte auf der Aufrufwebsite erstellen, wie im folgenden Beispiel gezeigt.

// 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, l-Wert-Verweis übergeben, damit der Algorithmus den Zustand für zukünftige Schleifen speichern kann, um sie wiederzuverwenden. Das folgende Beispiel zeigt eine einfache Anwendung, die denselben Vorgang für einen Datensatz mehrmals ausführt. Die Verwendung kann die affinity_partitioner Leistung verbessern, da das Array wahrscheinlich in den Cache passt.

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

Achtung

Verwenden Sie Vorsicht, wenn Sie vorhandenen Code ändern, der auf kooperativ blockierter Semantik basiert, die verwendet oder affinity_partitionerverwendet werden sollstatic_partitioner. Diese Partitioniertypen verwenden keinen Lastenausgleich oder einen Bereichsdiebstahl und können daher das Verhalten Ihrer Anwendung ändern.

Die beste Möglichkeit, um zu bestimmen, ob ein Partitioner in einem bestimmten Szenario verwendet werden soll, besteht darin, zu experimentieren und zu messen, wie lange Vorgänge unter repräsentativen Lasten und Computerkonfigurationen ausgeführt werden müssen. Die statische Partitionierung könnte z.B. möglicherweise auf einem Mehrkerncomputer mit nur wenigen Kernen für erhebliche Beschleunigung sorgen, doch bei Computern mit relativ vielen Kernen zu Verlangsamungen führen.

[Nach oben]

Parallele Sortierung

Die PPL stellt drei Sortieralgorithmen bereit: concurrency::p arallel_sort, concurrency::p arallel_buffered_sort, and concurrency::p arallel_radixsort. Diese Sortieralgorithmen sind nützlich, wenn Sie über einen Datensatz verfügen, der davon profitieren kann, parallel sortiert zu werden. Insbesondere ist das Sortieren parallel nützlich, wenn Sie über ein großes Dataset verfügen oder einen rechenintensiven Vergleichsvorgang verwenden, um Ihre Daten zu sortieren. Jeder dieser Algorithmen sortiert Elemente an Ort und Stelle.

Die parallel_sort algorithmen parallel_buffered_sort sind beide vergleichsbasierte Algorithmen. Das heißt, sie vergleichen Elemente nach Wert. Der parallel_sort Algorithmus hat keine zusätzlichen Speicheranforderungen und eignet sich für die allgemeine Sortierung. Der parallel_buffered_sort Algorithmus kann besser parallel_sortals ausgeführt werden, erfordert jedoch O(N)-Leerzeichen.

Der parallel_radixsort Algorithmus ist hashbasiert. Das heißt, es werden ganzzahlige Schlüssel zum Sortieren von Elementen verwendet. Mithilfe von Schlüsseln kann dieser Algorithmus das Ziel eines Elements direkt berechnen, anstatt Vergleiche zu verwenden. Wie parallel_buffered_sortfolgt erfordert dieser Algorithmus O(N)-Leerzeichen.

In der folgenden Tabelle sind die wichtigen Eigenschaften der drei parallelen Sortieralgorithmen zusammengefasst.

Algorithmus	Beschreibung	Sortiermechanismus	Sortierstabilität	Speicheranforderungen	Zeitkomplexität	Iteratorzugriff
parallel_sort	Allgemeine vergleichsbasierte Sortierung.	Vergleichsbasiert (aufsteigend)	Unstable	Keine	O((N/P)log(N/P) + 2N((P-1)/P))	Zufällig
parallel_buffered_sort	Schnellere allgemeine vergleichsbasierte Sortierung, die O(N)-Leerzeichen erfordert.	Vergleichsbasiert (aufsteigend)	Unstable	Erfordert zusätzlichen O(N)-Speicherplatz.	O((N/P)log(N))	Zufällig
parallel_radixsort	Ganzzahlige schlüsselbasierte Sortierung, die O(N)-Leerzeichen erfordert.	Hashbasiert	Stable	Erfordert zusätzlichen O(N)-Speicherplatz.	O(N/P)	Zufällig

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

Diese parallelen Sortieralgorithmen folgen den Regeln der Abbruch- und Ausnahmebehandlung. Weitere Informationen zur Abbruch- und Ausnahmebehandlung in der Parallelitätslaufzeit finden Sie unter Abbrechen paralleler Algorithmen und Ausnahmebehandlung.

Tipp

Diese parallelen Sortieralgorithmen unterstützen die Bewegungssemantik. Sie können einen Verschiebungszuweisungsoperator definieren, um Swap-Vorgänge effizienter zu ermöglichen. Weitere Informationen zum Verschieben der Semantik und zum Verschiebungszuweisungsoperator finden Sie unter Rvalue Reference Declarator: &&, und Move Constructors and Move Assignment Operators (C++). Wenn Sie keinen Verschiebungszuweisungsoperator oder eine Swap-Funktion bereitstellen, verwenden die Sortieralgorithmen den Kopierkonstruktor.

Das folgende grundlegende Beispiel zeigt, wie parallel_sort Sie werte vector int sortieren. Verwendet standardmäßig parallel_sort "std::less" zum Vergleichen von Werten.

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

In diesem Beispiel wird gezeigt, wie Eine benutzerdefinierte Vergleichsfunktion bereitgestellt wird. Es verwendet die std::complex::real-Methode zum Sortieren von std::complex<double> values 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)
*/

In diesem Beispiel wird gezeigt, wie Sie dem Algorithmus eine Hashfunktion parallel_radixsort bereitstellen. In diesem Beispiel werden 3D-Punkte sortiert. Die Punkte werden basierend auf ihrem Abstand von einem Bezugspunkt 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
*/

In diesem Beispiel wird eine relativ kleine Datenmenge verwendet. Sie können die anfängliche Größe des Vektors erhöhen, um mit Leistungsverbesserungen über größere Datenmengen zu experimentieren.

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

// 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 integralen Typ zurückgeben (std::is_integral::value muss sein true). Dieser integrale Typ muss in Typ size_tkonvertierbar sein.

Auswählen eines Sortieralgorithmus

In vielen Fällen parallel_sort bietet die beste Balance zwischen Geschwindigkeit und Speicherleistung. Wenn Sie jedoch die Größe Ihres Datasets erhöhen, die Anzahl der verfügbaren Prozessoren oder die Komplexität Ihrer Vergleichsfunktion parallel_buffered_sort parallel_radixsort oder die Leistung verbessern können. Die beste Methode, um zu bestimmen, welcher Sortieralgorithmus in einem bestimmten Szenario verwendet werden soll, besteht darin, zu experimentieren und zu messen, wie lange es dauert, typische Daten nach repräsentativen Computerkonfigurationen zu sortieren. Beachten Sie beim Auswählen einer Sortierstrategie die folgenden Richtlinien.

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

• Die Menge der Arbeit, die ihre Vergleichsfunktion oder Hashfunktion ausführt.

• Die Menge der verfügbaren Computerressourcen.

• Die Merkmale Ihres Datasets. Beispielsweise kann ein Algorithmus gut für Daten funktionieren, die bereits fast sortiert sind, aber nicht auch für Daten, die völlig unsortiert sind.

• Die Blockgröße. Das optionale _Chunk_size Argument gibt an, wann der Algorithmus von einer parallelen zu einer seriellen Sortierimplementierung wechselt, da die Gesamtsortierung in kleinere Arbeitseinheiten unterteilt wird. Wenn Sie beispielsweise 512 bereitstellen, wechselt der Algorithmus zur seriellen Implementierung, wenn eine Arbeitseinheit 512 oder weniger Elemente enthält. Eine serielle Implementierung kann die Gesamtleistung verbessern, da dadurch der Aufwand für die parallele Verarbeitung von Daten beseitigt wird.

Es lohnt sich möglicherweise nicht, ein kleines Dataset parallel zu sortieren, auch wenn Sie über eine große Anzahl verfügbarer Rechenressourcen verfügen oder ihre Vergleichsfunktion oder Hashfunktion eine relativ große Menge Arbeit ausführt. Sie können die Funktion "std::sort" verwenden, um kleine Datasets zu sortieren. (parallel_sort und parallel_buffered_sort rufen Sie auf sort , wenn Sie eine Blockgröße angeben, die größer als das Dataset ist. Es wäre jedoch erforderlich, parallel_buffered_sort O(N)-Speicherplatz zuzuweisen, der aufgrund der Sperrverknügung oder speicherzuordnung zusätzliche Zeit in Anspruch nehmen kann.)

Wenn Sie Arbeitsspeicher sparen müssen oder der Speicherverknennungsverknügungsschutz unterliegt, verwenden parallel_sort Sie diese, um ein mittelgroßes Dataset zu sortieren. parallel_sort erfordert keinen zusätzlichen Platz; die anderen Algorithmen benötigen O(N)-Leerzeichen.

Wird parallel_buffered_sort verwendet, um mittelgroße Datasets zu sortieren und wenn Ihre Anwendung die zusätzlicheN O(N)-Speicherplatzanforderungen erfüllt. parallel_buffered_sort kann besonders nützlich sein, wenn Sie über eine große Anzahl von Rechenressourcen oder eine teure Vergleichsfunktion oder Hashfunktion verfügen.

Wird parallel_radixsort verwendet, um große Datasets zu sortieren und wenn Ihre Anwendung die zusätzlicheN O(N)-Speicherplatzanforderungen erfüllt. parallel_radixsort kann besonders hilfreich sein, wenn der entsprechende Vergleichsvorgang teurer ist oder beide Vorgänge teuer sind.

Achtung

Die Implementierung einer guten Hashfunktion erfordert, dass Sie den Datasetbereich kennen und wie jedes Element im Dataset in einen entsprechenden nicht signierten Wert transformiert wird. Da der Hashvorgang für nicht signierte Werte funktioniert, sollten Sie eine andere Sortierstrategie in Betracht ziehen, wenn nicht signierte Hashwerte nicht erstellt werden können.

Im folgenden Beispiel wird die Leistung von sort, parallel_sort, , parallel_buffered_sortund mit parallel_radixsort demselben großen Satz zufälliger Daten verglichen.

// 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 davon ausgeht, dass es akzeptabel ist, während der Sortierung O(N)-Speicherplatz zuzuweisen, parallel_radixsort führt die beste Leistung für dieses Dataset auf dieser Computerkonfiguration aus.

[Nach oben]

Verwandte Themen

Titel	Beschreibung
Vorgehensweise: Schreiben einer parallel_for-Schleife	Zeigt, wie der Algorithmus zum Ausführen der parallel_for Matrixmultiplizierung verwendet wird.
Vorgehensweise: Schreiben einer parallel_for_each-Schleife	Zeigt, wie der parallel_for_each Algorithmus verwendet wird, um die Anzahl der Primzahlen in einem std::array-Objekt parallel zu berechnen.
Vorgehensweise: 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.
Vorgehensweise: 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.
Vorgehensweise: Paralleles Ausführen von Zuordnungs- und Reduzierungsoperationen	Zeigt, wie Sie mithilfe der parallel_transform Algorithmen parallel_reduce eine Zuordnung ausführen und den Vorgang reduzieren, der die Vorkommen von Wörtern in Dateien zählt.
Parallel Patterns Library (PPL)	Beschreibt die PPL, die ein imperatives Programmiermodell bereitstellt, das Skalierbarkeit und Benutzerfreundlichkeit für die Entwicklung gleichzeitiger Anwendungen fördert.
Abbruch in der PPL	Erläutert die Rolle des Abbruchs in der PPL, das Abbrechen der parallelen Arbeit und die Bestimmung, wann eine Aufgabengruppe abgebrochen wird.
Ausnahmebehandlung	Erläutert die Rolle der Ausnahmebehandlung in der Parallelitätslaufzeit.

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