Parallele Algorithmen

Artikel
08/10/2011

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. Der Concurrency::parallel_for-Algorithmus führt die parallelen Schleifeniterationen zum Beispiel mithilfe eines Concurrency::structured_task_group-Objekts aus. Der parallel_for-Algorithmus verteilt die Arbeit auf Grundlage der verfügbaren Computerressourcen auf optimale Weise.

Abschnitte

In diesem Thema werden die folgenden parallelen Algorithmen detailliert beschrieben:

parallel_for-Algorithmus
parallel_for_each-Algorithmus
parallel_invoke-Algorithmus

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. Darüber hinaus verwendet wer einen Arbeitsübernahme-Algorithmus, 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 über zwei ü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.

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.

Tipp

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.

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:

1 2 4 3 5

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]

parallel_for_each-Algorithmus

Der Concurrency::parallel_for_each-Algorithmus führt Aufgaben für einen iterativen Container, z. B. die von STL bereitgestellten Aufgaben, parallel aus. 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(values.begin(), values.end(), [](int value) {
      wstringstream ss;
      ss << value << L' ';
      wcout << ss.str();
   });
}

Dieses Beispiel erzeugt die folgende Beispielausgabe:

4 5 1 2 3

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]

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: