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 ein Algorithmus 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 parallel_transform-Algorithmus

  • Der parallel_reduce-Algorithmus

  • Beispiel: Paralleles Ausführen der Zuordnung und Reduzierung

• 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. Sie verwendet einen Arbeitsübernahme-Algorithmus und einen Bereich, die darauf zugreifen, der diese Verteilungen ausgleicht, wenn die Lastenverteilung nicht ausgeglichen ist. 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 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 verbleibenden Versionen verwenden Partitioniererobjekte, die Sie aktivieren, um anzugeben, wie Bereiche parallel_for zwischen Threads partitionieren soll. 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.

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.

[Nach oben]

Der parallel_for_each-Algorithmus

Der concurrency::parallel_for_each - Algorithmus führt Aufgaben für einen iterativen Container, z denen aus, die von STL bereitgestellten Aufgaben, parallel. 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), 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:

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.

[Nach oben]

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

In diesem Beispiel wird die folgende Ausgabe erzeugt:

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.

[Nach oben]

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, dass die Vorgangsreihenfolge wird nicht bestimmt, da sie parallel ausführen. Verwenden Sie diese Algorithmen, wenn Sie mit einem Satz arbeiten, der ausreicht, Leistungs- und Skalierbarkeitsvorteile von parallel verarbeitet werden abgerufen.

Der parallel_transform-Algorithmus

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

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

• Summieren Sie oder nehmen Sie das Skalarprodukt zweier Vektoren, und führen Sie andere numerische Berechnungen auf Vektoren aus.

• Führen Sie 3D-Strahlnablaufverfolgung aus, in der jede Iteration ein Pixel verweist, die 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 std::vector-Objekts 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>());
}

Der parallel_transform - Algorithmus verfügt über zwei Überladungen. Die erste Überladung akzeptiert einen Eingabebereich unäre und eine Funktion. Der 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, die 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>());

Der parallel_reduce-Algorithmus

Der parallel_reduce - Algorithmus ist nützlich, wenn Sie eine Sequenz von Operationen haben, die die Eigenschaft assoziative erfüllen. (Dieser Algorithmus ist 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 einen Vektor von einer 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.

Das folgende einfache Beispiel zeigt, wie der parallel_reduce Algorithmus verwendet, um eine Sequenz von Zeichenfolgen in eine Zeichenfolge zu kombinieren. Wie mit Beispielen für parallel_transform, Leistungssteigerung 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 sich parallel_reduce als Kurzform für die Verwendung des parallel_for_each - Algorithmus mit der Klasse concurrency::combinable vorstellen.

Beispiel: Paralleles Ausführen der Zuordnung und Reduzierung

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

Im folgenden Beispiel wird die Zeit verglichen, der sie verwendet, um die Summe von Primzahlen sowohl seriell als auch parallel berechnet. Die Zuordnungsphase transformiert keine Primzahlen Werte auf 0 und die reduzierensphase 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 Vorgang parallel reduziert, finden Sie unter Gewusst wie: Paralleles Ausführen von Zuordnungs- und Reduzierungsoperationen.

[Nach oben]

Partitionieren der Arbeit

Um einen Vorgang in einer Datenquelle zu parallelisieren, ist ein wichtiger Schritt das Partitionieren der Quelle in mehrere Abschnitte auf die gleichzeitig von mehreren Threads zugegriffen werden kann. Ein Partitionierer gibt an, wie paralleler Algorithmus Bereiche geteilt Threads partitionieren soll. Wie zuvor in diesem Dokument erläutert, verwendet die PPL einen Standardpartitionierungsmechanismus, der eine ursprüngliche Arbeitsauslastung erstellt und dann einen Arbeitsübernahme-Algorithmus und ein Bereich verwendet, die darauf zugreifen, der diese Verteilungen ausgleicht, wenn die Lastenverteilung nicht ausgeglichen ist. Wenn eine Schleifeniteration einen Bereich von Iterationen durchlaufen hat, verteilt der Laufzeit Arbeit von anderen Threads auf diesen Thread neu. Für einige Szenarien, sollten Sie einem anderen Partitionierungsmechanismus angeben, der besser zu dem Problem verarbeiten.

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

• concurrency::affinity_partitioner
  Verteilungsarbeit in eine feste Anzahl der Fensterbereiche (normalerweise die Anzahl der Arbeitsthreads, die verfügbar sind, an der Schleife arbeiten). Dieser Partitionierertyp ähnelt static_partitioner, verbessert jedoch die Cacheaffinität, durch die Art und Weise, die die Bereiche zu den Arbeitsthreads zuordnet. Dieser Partitionierertyp kann die Leistung, wenn eine Schleife über das gleiche Dataset (mehrmals ausgeführt wird wie eine Schleife in einer Schleife) und die Datenpassung im Cache verbessern. Dieser Partitionierer nicht komplett hat im Abbruch beteiligt. Außerdem verwendet nicht kooperative Blockierungssemantiken und kann nicht mit parallelen Schleifen deshalb verwendet werden, die eine Vorwärtsabhängigkeit haben.

• concurrency::auto_partitioner
  Dividiert arbeiten in eine Anfangszahl Bereiche (normalerweise 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, bevor sie sichtbar wird. Wenn ein Leistungsbereich Abschluss, verteilt die Laufzeit SubBereiche der Arbeit von anderen Threads auf diesen Thread neu. Verwenden Sie den Partitionierer, wenn die Arbeitsauslastung nicht in einer der anderen Kategorien schlägt, oder Sie vollständige Unterstützung zum Abbruchs- oder die kooperative benötigen.

• concurrency::simple_partitioner
  Dividiert bearbeiten in Bereiche, sodass jeder Bereich mindestens die Anzahl der Iterationen hat, die von der angegebenen Segmentgröße angegeben werden. Dieser Partitionierertyp hat im Lastenausgleich teil; Allerdings wird die Laufzeit Bereiche nicht in SubBereiche unter. Für jeden Mitarbeiter überprüft die Laufzeit für Abbruch und führt Arbeiten aus, nachdem _Chunk_size Iterationen abgeschlossen haben.

• concurrency::static_partitioner
  Verteilungsarbeit in eine feste Anzahl der Fensterbereiche (normalerweise die Anzahl der Arbeitsthreads, die verfügbar sind, an der Schleife arbeiten). Dieser Partitionierertyp kann die Leistung verbessern, da er keine Arbeit stehlenden verwendet und daher weniger Aufwand hat. Verwenden Sie diesen Partitionierertyp, wenn jeder Iteration einer parallelen Schleife einen festen und einheitlichen Arbeitsaufwand ausführt und Sie keine Abbruchunterstützung benötigen oder das die kooperative weiterleiten.

Normalerweise werden diese Partitionierer auf, außer für affinity_partitioner verwendet. Die meisten Partitionierertypen behalten keine Zustand bei und werden nicht zur Laufzeit geändert. Daher können Sie diese Partitioniererobjekte an der Aufrufsite, wie im folgenden Beispiel 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 anderen Objekten als const übergeben, L-Werts-Verweis, sodass der Algorithmus Zustand speichern kann, dass zukünftige Schleifen wiederverwenden. Im folgenden Beispiel wird eine grundlegende 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, dass im Cache zu passen.

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

Die beste Möglichkeit, zu bestimmen, ob ein Partitionierer in einem gegebenen Szenario besteht darin durch Experimentieren zu ermitteln, wie viel Zeit Vorgänge verwendet, um bei repräsentativer Auslastung und mit entsprechenden Computerkonfigurationen in Anspruch nehmen. 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.

[Nach oben]

Parallele Sortierung

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

Die parallel_sort und parallel_buffered_sort Algorithmen sind beide verglichene-basierten Algorithmen. Das heißt, Vergleich von Elementen als Wert. Der parallel_sort - Algorithmus verfügt keine zusätzlichen Arbeitsspeicheranforderungen, und ist für allgemeine Sortierung geeignet. Der parallel_buffered_sort Algorithmus kann eine bessere Leistung als parallel_sort, erfordert aber O(N).

Der parallel_radixsort - Algorithmus ist hashbasiert. Das heißt, verwendet er ganzzahlige Tasten, um Elemente zu sortieren. Indem 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 Merkmalen der drei parallelen Sortieralgorithmen zusammen.

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

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

Diese parallele Sortieralgorithmen folgen den Regeln des Abbruchs und der Ausnahmebehandlung. Weitere Informationen zu Abbrüchen und Ausnahmebehandlung in der Concurrency Runtime, finden Sie unter Abbrechen von parallelen Algorithmen und Ausnahmebehandlung in der Concurrency Runtime.

Das folgende einfache Beispiel zeigt, wie parallel_sort verwendet, um den vector von int-Werten zu sortieren. Standardmäßig verwendet parallel_sortstd::less, um Werte.

// 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, um std::complex <Double>-Werte in aufsteigender Reihenfolge zu sortieren.

// 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 ihrer Entfernung von einen Referenzpunkt 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
*/

Zu Illustrationszwecken wird dieses Beispiel ein verhältnismäßig kleines Dataset. Sie können die ursprüngliche Größe des Vektors erhöhen, um mit Abfragevorgang zur größeren Sätzen von Daten zu testen.

Dieses Beispiel verwendet einen Lambda-Ausdruck als Hashfunktion. Sie können eine der integrierte Implementierungen der std::hash-Klasse auch verwenden oder 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, zu size_t.

Auswählen eines Sortieralgorithmus

In vielen Fällen stellt parallel_sort die beste Balance der Geschwindigkeits- und Arbeitsspeicherleistung. Wie Sie die Größe des DataSets, der Anzahl der verfügbaren Prozessoren oder der Komplexität Ihrer Compare-Funktion erhöhen, können parallel_buffered_sort oder parallel_radixsort optimiert werden. Die beste Möglichkeit, zu bestimmen, die in einem gegebenen Szenario verwenden der Sortieralgorithmus, besteht darin durch Experimentieren zu ermitteln, wie lange verwendet, um mit typischen Daten von repräsentativen Computerkonfigurationen zu sortieren. Halten 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 einen großen Dataset enthält mehr als 100.000 Elemente.

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

• Die Menge verfügbarer Computerressourcen.

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

• Die Segmentgröße. Das optionale Argument _Chunk_size gibt wenn die Algorithmusschalter einer entlang einer seriellen Sortierungsimplementierung an, während es die Gesamtsortierung 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 verbessern, da sie den Mehraufwand entfernt, der erforderlich ist, Daten parallel verarbeiten.

Es ist nicht empfehlenswert, ein kleines Dataset parallel zu sortieren, wenn Sie zahlreiche verfügbaren Computerressourcen haben, oder die Compare-Funktion oder Hashfunktion einen relativ große Menge ausführt. Sie können std::sort-Funktion verwenden, um kleine Datasets zu sortieren. (parallel_sort und parallel_buffered_sort rufen sort auf, wenn Sie eine Segmentgröße angeben, die größer, Dataset-; O(N) wird von parallel_buffered_sort jedoch Speicherplatz belegen müssen, das zusätzliche Zeit aufgrund des Sperrenkonflikts oder der Speicherbelegung müssen kann.)

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

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

Verwenden Sie parallel_radixsort, um große Datasets zu sortieren und die Anwendung eine 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 aufwändig sind.

Im folgenden Beispiel wird mit sort, parallel_sort, parallel_buffered_sort und parallel_radixsort für den gleichen 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 wird, dass es akzeptabel, O(N) Leerzeichen bei der Sortierung zuzuordnen, wird parallel_radixsort am besten auf dieses Dataset auf dieser Computerkonfiguration aus.

[Nach oben]

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