Hinweis
Für den Zugriff auf diese Seite ist eine Autorisierung erforderlich. Sie können versuchen, sich anzumelden oder das Verzeichnis zu wechseln.
Für den Zugriff auf diese Seite ist eine Autorisierung erforderlich. Sie können versuchen, das Verzeichnis zu wechseln.
Die Parallel Patterns Library (PPL) bietet Algorithmen, die gleichzeitig auf Datensammlungen arbeiten. Diese Algorithmen ähneln denen der C++ Standardbibliothek.
Die parallelen Algorithmen werden aus bestehenden Funktionen der Concurrency Runtime zusammengestellt. Beispielsweise verwendet der Algorithmus concurrency::parallel_for ein Objekt vom Typ concurrency::structured_task_group , um die parallelen Schleifeniterationen auszuführen. Die parallel_for Algorithmus partitioniert die Arbeit unter Berücksichtigung der verfügbaren Rechenressourcen auf optimale Weise.
Sections
Der parallel_for Algorithmus
Die concurrency::parallel_for führt dieselbe Aufgabe wiederholt parallel aus. Jede dieser Aufgaben wird durch einen Iterationswert parametrisiert. Dieser Algorithmus ist nützlich, wenn Sie einen Schleifenkörper haben, der keine Ressourcen zwischen den Iterationen dieser Schleife teilt.
Die parallel_for partitioniert Aufgaben optimal für die parallele Ausführung. Er verwendet einen Work-Stealing-Algorithmus und Range Stealing, um diese Partitionen auszugleichen, wenn die Workloads nicht gleichmäßig verteilt sind. Wenn eine Schleifeniteration kooperativ blockiert wird, verteilt die Laufzeit den Bereich der Iterationen, der dem aktuellen Thread zugewiesen ist, auf andere Threads oder Prozessoren um. Wenn ein Thread eine Reihe von Iterationen abschließt, verteilt die Laufzeitumgebung die Arbeit von anderen Threads auf diesen Thread um. Die parallel_for -Algorithmus unterstützt auch verschachtelte Parallelität. Wenn eine parallele Schleife eine andere parallele Schleife enthält, koordiniert die Laufzeit die Verarbeitungsressourcen zwischen den Schleifenkörpern in einer effizienten Weise für die parallele Ausführung.
Die parallel_for hat mehrere überladene Versionen. Die erste Version nimmt einen Startwert, einen Endwert und eine Arbeitsfunktion (einen Lambda-Ausdruck, ein Funktionsobjekt oder einen Funktionszeiger). Die zweite Version nimmt einen Startwert, einen Endwert, einen Wert, um den man schreitet, und eine Arbeitsfunktion. In der ersten Version dieser Funktion wird 1 als Schrittwert verwendet. Die übrigen Versionen verwenden Partitioner-Objekte, mit denen Sie festlegen können, wie parallel_for Bereiche auf Threads aufteilen soll. Partitionierer werden im Abschnitt Partitionierung der Arbeit dieses Dokuments näher erläutert.
Sie können viele for -Schleifen konvertieren, zur Nutzung von parallel_for. Der Algorithmus parallel_for unterscheidet sich jedoch in folgenden Punkten von der Anweisung for :
Die
parallel_for> does not execute the tasks in a pre-determined order.parallel_fordoes not execute the tasks in a pre-determined order.Die
parallel_foralgorithm does not support arbitrary termination conditions. Dieparallel_foralgorithm stops when the current value of the iteration variable is one less thanlast.Die
_Index_typetype parameter must be an integral type. Dieser Integraltyp kann vorzeichenbehaftet oder vorzeichenlos sein.Die Schleifeniteration muss vorwärts gerichtet sein. Die
parallel_foralgorithm throws an exception of type std::invalid_argument if the_Stepparameter is less than 1.Der Mechanismus zur Behandlung von Ausnahmen für den
parallel_for-Algorithmus unterscheidet sich von dem einerfor-Schleife. Wenn mehrere Ausnahmen gleichzeitig in einem parallelen Schleifentext auftreten, gibt die Runtime nur eine der Ausnahmen an den Thread weiter, derparallel_forangefragt hat. Wenn eine Schleifeniteration eine Ausnahme auslöst, hält die Runtime die gesamte Schleife nicht sofort an. Stattdessen wird die Schleife in den abgebrochenen Zustand versetzt und die Runtime verwirft alle Aufgaben, die noch nicht gestartet wurden. Weitere Informationen zur Ausnahmen Behandlung finden Sie unter Ausnahmebehandlung.
Obwohl der parallel_for-Algorithmus keine willkürlichen Abbruchbedingungen unterstützt, können Sie den Abbruch verwenden, um alle Aufgaben zu beenden. Weitere Informationen über Abbrüche, siehe Aufgabenabbruch in der PPL.
Note
Die Kosten für die Planung, die sich aus dem Lastausgleich und der Unterstützung von Funktionen wie der Stornierung ergeben, können die Vorteile der parallelen Ausführung des Schleifenkörpers nicht aufwiegen, insbesondere wenn der Schleifenkörper relativ klein ist. Sie können diesen Overhead minimieren, indem Sie einen Partitionierer in Ihrer parallelen Schleife verwenden. Weitere Informationen finden Sie unter Partitionierung der Arbeit later in this document.
Example
Das folgende Beispiel zeigt die Grundstruktur des parallel_for Algorithmus. In diesem Beispiel wird jeder Wert 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 parallel_for algorithm acts on each item in parallel, the order in which the values are printed to the console will vary.
Ein vollständiges Beispiel für die Verwendung des parallel_for Algorithmus finden Sie unter Anleitung: Schreiben einer parallel_for-Schleife.
Der parallel_for_each Algorithmus
Die concurrency::parallel_for_each algorithm performs tasks on an iterative container, such as those provided by the C++ Standard Library, in parallel. Er verwendet die gleiche Partitionierungslogik wie der parallel_for-Algorithmus.
Die parallel_for_each algorithm resembles the C++ Standard Library std::for_each algorithm, except that the parallel_for_each algorithm executes the tasks concurrently. Wie andere parallele Algorithmen auch, führt parallel_for_each die Aufgaben nicht in einer bestimmten Reihenfolge aus.
Although the parallel_for_each algorithm works on both forward iterators and random access iterators, it performs better with random access iterators.
Example
Das folgende Beispiel zeigt die Grundstruktur des parallel_for_each Algorithmus. This example prints to the console each value in a std::array -Objekt.
// 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 parallel_for_each algorithm acts on each item in parallel, the order in which the values are printed to the console will vary.
Ein vollständiges Beispiel, das den parallel_for_each Algorithmus verwendet, finden Sie unter Anleitung: Schreiben einer parallelen_for_each-Schleife.
Der parallel_invoke Algorithmus
Der concurrency::parallel_invoke Algorithmus führt eine Reihe von Aufgaben parallel aus. Er kehrt erst zurück, wenn jede Aufgabe abgeschlossen ist. Dieser Algorithmus ist nützlich, wenn Sie mehrere unabhängige Aufgaben haben, die Sie zur gleichen Zeit ausführen möchten.
Die parallel_invoke algorithm takes as its parameters a series of work functions (lambda functions, function objects, or function pointers). Die parallel_invoke algorithm is overloaded to take between two and ten parameters. Jede Funktion, die Sie übergeben an parallel_invoke darf keine null Parameter verwenden.
Wie andere parallele Algorithmen auch, führt parallel_invoke die Aufgaben nicht in einer bestimmten Reihenfolge aus. Im Thema "Task Parallelism" wird erläutert, wie sich der parallel_invoke Algorithmus auf Aufgaben und Aufgabengruppen bezieht.
Example
Das folgende Beispiel zeigt die Grundstruktur des parallel_invoke Algorithmus. In diesem Beispiel wird die Funktion twice gleichzeitig für drei lokale Variablen aufgerufen und das Ergebnis in 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 die folgende Ausgabe:
108 11.2 HelloHello
For complete examples that use the parallel_invoke algorithm, see How to: Use parallel_invoke to Write a Parallel Sort Routine und How to: Use parallel_invoke to Execute Parallel Operations.
Die Algorithmen parallel_transform und parallel_reduce
Die concurrency::parallel_transform und concurrency::parallel_reduce algorithms are parallel versions of the C++ Standard Library algorithms std::transform und std::accumulate, respectively. Die Versionen der Laufzeiten Parallelität verhalten sich wie die Versionen der C++-Standardbibliothek, mit dem Unterschied, dass die Reihenfolge der Operationen nicht festgelegt ist, da sie parallel ausgeführt werden. Verwenden Sie diese Algorithmen, wenn Sie mit einer Menge arbeiten, die groß genug ist, um Leistungs- und Skalierbarkeitsvorteile durch die parallele Verarbeitung zu erzielen.
Important
Die Algorithmen parallel_transform und parallel_reduce unterstützen nur zufälligen Zugriff, bidirektionale und Vorwärtsiteratoren, da diese Iteratoren stabile Speicheradressen erzeugen. Außerdem dürfen diese Iteratoren keine-const l-Werte erzeugen.
Der parallel_transform Algorithmus
Sie können den parallel transform-Algorithmus verwenden, um viele Datenparallelisierungsoperationen durchzuführen. Sie können zum Beispiel Folgendes:
Stellen Sie die Helligkeit eines Bildes ein und führen Sie andere Bildverarbeitungsvorgänge durch.
Summieren oder das Punktprodukt zwischen zwei Vektoren bilden und andere numerische Berechnungen mit Vektoren durchführen.
Führen Sie 3D-Raytracing durch, wobei sich jede Iteration auf ein Pixel bezieht, das gerendert werden muss.
The following example shows the basic structure that is used to call the parallel_transform Algorithmus. In diesem Beispiel werden die einzelnen Elemente eines std::vector-Objekts auf zwei Arten aufgehoben. Die erste Möglichkeit verwendet einen Lambda-Ausdruck. Die zweite verwendet std::negate, das 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>());
}
Warning
In diesem Beispiel wird die grundlegende Verwendung von parallel_transform veranschaulicht. Da die Arbeitsfunktion keinen nennenswerten Teil der Arbeit erledigt, ist in diesem Beispiel keine signifikante Leistungssteigerung zu erwarten.
Die parallel_transform algorithm has two overloads. Die erste Überladung benötigt einen Eingabebereich und eine unäre Funktion. Die unäre Funktion kann ein Lambda-Ausdruck sein, der ein Argument annimmt, ein Funktionsobjekt oder ein Typ, der sich von unary_function ableitet. Die zweite Überladung benötigt zwei Eingabebereiche und eine Binärfunktion. Die binäre Funktion kann ein Lambda-Ausdruck sein, der zwei Argumente annimmt, ein Funktionsobjekt oder ein Typ, der sich von std::binary_function ableitet. Das folgende Beispiel veranschaulicht 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>());
Important
Der Iterator, den Sie für die Ausgabe von parallel_transform liefern, muss den Eingabe-Iterator vollständig oder gar nicht überlappen. Das Verhalten dieses Algorithmus ist nicht spezifiziert, wenn sich die Eingabe- und Ausgabeiteratoren teilweise überlappen.
Der parallel_reduce Algorithmus
Die parallel_reduce algorithm is useful when you have a sequence of operations that satisfy the associative property. (Dieser Algorithmus erfordert keine Kommutativität.) Hier sind einige der Operationen, die Sie ausführen können mit parallel_reduce:
Multiplizieren Sie Sequenzen von Matrizen, um eine Matrix zu erzeugen.
Multiplizieren Sie einen Vektor mit einer Folge von Matrizen, um einen Vektor zu erzeugen.
Berechne die Länge einer Folge von Zeichenfolgen.
Kombinieren Sie eine Liste von Elementen, wie z. B. Zeichenfolgen, zu einem Element.
Das folgende einfache Beispiel zeigt, wie Sie den parallel_reduce-Algorithmus verwenden, um eine Folge von Zeichenketten zu einer einzigen Zeichenkette zu kombinieren. Wie bei den Beispielen für parallel_transform ist auch bei diesem einfachen Beispiel kein Leistungsgewinn zu erwarten.
// 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 many cases, you can think of parallel_reduce as shorthand for the use of the parallel_for_each zusammen mit der Klasse concurrency::combinable vorstellen.
Beispiel: Parallele Ausführung von Map und Reduce
Ein map -Operation wendet eine Funktion auf jeden Wert in einer Sequenz an. Ein reduce -Operation fasst die Elemente einer Sequenz zu einem Wert zusammen. Sie können die C++-Standardbibliotheksfunktionen std::transform und std::accumulate functions to perform map und reduce operations. Bei vielen Problemen können Sie jedoch den Algorithmus parallel_transform verwenden, um die Zuordnungsoperation parallel auszuführen, und den Algorithmus parallel_reduce , um die Reduktionsoperation parallel auszuführen.
Das folgende Beispiel vergleicht die Zeit, die benötigt wird, um die Summe der Primzahlen seriell und parallel zu berechnen. Die Map-Phase wandelt Nicht-Primzahlen in 0 um, und die Reduce-Phase 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 für die parallele Ausführung einer Map- und Reduce-Operation finden Sie unter Anleitung: Map- und Reduce-Operationen parallel ausführen.
Partitionierung der Arbeit
Ein essentieller Schritt, um einen Vorgang für eine Datenquelle zu parallelisieren, ist das Partitionieren der Quelle in mehrere Abschnitte, auf die mehrere Threads gleichzeitig zugreifen können. Das Verhalten dieses Algorithmus ist nicht spezifiziert, wenn sich die Eingabe- und Ausgabeiteratoren teilweise überlappen. Wie bereits in diesem Dokument erläutert, verwendet der PPL einen Standard-Partitionierungsmechanismus, der eine anfängliche Workload erstellt und dann einen Work-Stealing-Algorithmus und Range-Stealing verwendet, um diese Partitionen auszugleichen, wenn die Workloads unausgeglichen sind. Wenn zum Beispiel eine Schleifeniteration eine Reihe von Iterationen abschließt, verteilt die Laufzeitumgebung die Arbeit von anderen Threads auf diesen Thread um. Für einige Szenarien kann es jedoch sinnvoll sein, einen anderen Partitionierungsmechanismus anzugeben, der für Ihr Problem besser geeignet ist.
Die parallel_for, parallel_for_eachund parallel_transform bieten überladene Versionen, und akzeptieren den zusätzlichen Parameter _Partitioner. Dieser Parameter definiert den Partitionierer-Typ, der die Arbeit aufteilt. Hier sind die Arten von Partitionern, die die PPL definiert:
concurrency::affinity_partitioner
Teilt die Arbeit in eine feste Anzahl von Bereichen auf (in der Regel die Anzahl der Worker-Threads, die für die Arbeit an der Schleife verfügbar sind). Dieser Partitionertyp ähnelt static_partitioner, verbessert jedoch die Cache-Affinität durch die Art und Weise, wie Bereiche auf Worker-Threads abgebildet werden. Dieser Partitionierungstyp kann die Leistung verbessern, wenn eine Schleife mehrfach über denselben Datensatz aktiviert wird (z. B. eine Schleife innerhalb einer Schleife) und die Daten in den Cache passen. Dieser Partitionierer nimmt nicht vollständig an der Stornierung teil. Es verwendet auch keine kooperative Blockierungssemantik und kann daher nicht mit parallelen Schleifen verwendet werden, die eine Vorwärtsabhängigkeit haben.
concurrency::auto_partitioner
Teilt die Arbeit in eine anfängliche Anzahl von Bereichen ein (in der Regel die Anzahl der Worker-Threads, die für die Arbeit an der Schleife zur Verfügung stehen). Die Laufzeitumgebung verwendet diesen Typ standardmäßig, wenn Sie keinen überladenen parallelen Algorithmus aufrufen, der einen Parameter _Partitioner akzeptiert. Jeder Bereich kann in Teilbereiche unterteilt werden und ermöglicht so einen Lastausgleich. Wenn ein Arbeitsbereich abgeschlossen ist, verteilt die Laufzeitumgebung Teilbereiche der Arbeit von anderen Threads auf diesen Thread um. Verwenden Sie diesen Partitionierer, wenn Ihr Workload nicht unter eine der anderen Kategorien fällt oder Sie volle Unterstützung für Stornierung oder kooperatives Blockieren benötigen.
concurrency::simple_partitioner
Teilt die Arbeit in Bereiche auf, sodass jeder Bereich mindestens die Anzahl der Iterationen enthält, die durch die angegebene Blockgröße festgelegt sind. Dieser Partitionierer-Typ nimmt am Lastausgleich teil; die Laufzeit unterteilt die Bereiche jedoch nicht in Teilbereiche. Für jeden Worker überprüft die Laufzeit, ob eine Stornierung vorliegt, und führt nach Abschluss von _Chunk_size Iterationen einen Lastausgleich durch.
concurrency::static_partitioner
Teilt die Arbeit in eine feste Anzahl von Bereichen auf (in der Regel die Anzahl der Worker-Threads, die für die Arbeit an der Schleife verfügbar sind). Dieser Partitionierer-Typ kann die Leistung verbessern, da er nicht auf Work-Stealing zurückgreift und daher weniger Overhead hat. Verwenden Sie diesen Partitionierer-Typ, wenn jede Iteration einer parallelen Schleife eine feste und einheitliche Menge an Arbeit ausführt und Sie keine Unterstützung für Stornierung oder kooperative Vorwärtsblockierung benötigen.
Warning
Die parallel_for_each und parallel_transform Algorithmen unterstützen nur Container, die Zufallszugriffsiteratoren (z.B. std::vector) für statische, einfache und Affinitätspartitioner verwenden. Die Verwendung von Containern, die bidirektionale und Vorwärtsiteratoren verwenden, führt zu einem Kompilierungsfehler. Der Standard-Partitionierer auto_partitioner unterstützt alle drei Iterator-Typen.
In der Regel werden diese Partitionierer auf die gleiche Weise verwendet, mit Ausnahme von affinity_partitioner. Die meisten Partitionierer-Typen haben keinen Status und werden von der Laufzeit nicht verändert. Daher können Sie diese Partitionierungsobjekte auf der Aufrufseite 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-Referenz übergeben, damit der Algorithmus den Status für zukünftige Schleifen speichern und wiederverwenden kann. Das folgende Beispiel zeigt eine einfache Anwendung, die denselben Vorgang auf einem Datensatz mehrfach parallel aktiviert. Die Verwendung von affinity_partitioner kann die 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);
}
}
Caution
Seien Sie vorsichtig, wenn Sie vorhandenen Code ändern, der auf kooperativer Blocksemantik basiert, wenn dieser abhängt von static_partitioner oder affinity_partitioner. Diese Partitionierungstypen verwenden keinen Lastausgleich oder Range Stealing und können daher das Verhalten Ihrer Anwendung verändern.
Ob in einem gegebenen Szenario ein Partitionierer verwendet werden sollte, bestimmen Sie am besten, indem Sie durch Experimentieren und Messen feststellen, wie lange die Ausführung von Vorgängen unter repräsentativen Lasten und Computerkonfigurationen dauert. 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.
Paralleles Sortieren
Die PPL bietet drei Sortieralgorithmen: concurrency::parallel_sort, concurrency::parallel_buffered_sort und concurrency::parallel_radixsort. Diese Sortieralgorithmen sind nützlich, wenn Sie einen Datensatz haben, der von einer parallelen Sortierung profitiert. Insbesondere ist das parallele Sortieren nützlich, wenn Sie über einen großen Datensatz verfügen oder wenn Sie eine rechenintensive Vergleichsoperation zum Sortieren Ihrer Daten verwenden. Jeder dieser Algorithmen sortiert Elemente an Ort und Stelle.
Die parallel_sort und parallel_buffered_sort sind beide vergleichsbasierte Algorithmen. Das heißt, sie vergleichen Elemente anhand ihres Werts. Die parallel_sort benötigt keinen zusätzlichen Speicherplatz und eignet sich für allgemeine Sortieraufgaben. Die parallel_buffered_sort kann bessere Ergebnisse erzielen als parallel_sort, benötigt jedoch O(N) Speicherplatz.
Die parallel_radixsort ist hash-basiert. Das heißt, es verwendet ganzzahlige Schlüssel zum Sortieren von Elementen. Die folgende Tabelle fasst die wichtigsten Eigenschaften der drei parallelen Sortieralgorithmen zusammen. So wie parallel_buffered_sort benötigt dieser Algorithmus O(N) Speicherplatz.
Die folgende Tabelle fasst die wichtigsten Eigenschaften der drei parallelen Sortieralgorithmen zusammen.
| Algorithmus | Description | Sorting mechanism | Sort Stability | Speicheranforderungen | Time Complexity | Iterator access |
|---|---|---|---|---|---|---|
parallel_sort |
General-purpose compare-based sort. | Compare-based (ascending) | Unstable | Keine | O((N/P)log(N/P) + 2N((p-1)/P)) | Random |
parallel_buffered_sort |
Schnellere, auf Vergleichen basierende Sortierung für allgemeine Zwecke, die O(N) Speicherplatz benötigt. | Vergleichsbasiert (aufsteigend) | Unstable | Requires additional O(N) space | O((N/P)log(N)) | Random |
parallel_radixsort |
Ganzzahlige schlüsselbasierte Sortierung, die O(N) Speicherplatz benötigt. | Hashbasiert | Stabil | Benötigt zusätzlichen O(N)-Platz | O(N/P) | Random |
Die folgende Abbildung zeigt die wichtigen Eigenschaften der drei parallelen Sortieralgorithmen anschaulicher.
Diese parallelen Sortieralgorithmen folgen den Regeln der Auslagerung und Ausnahmebehandlung. For more information about cancellation und Ausnahmebehandlung in the Concurrency Runtime, see Parallele Algorithmen abbrechen und Exception Handling.
Tip
Diese parallelen Sortieralgorithmen folgen den Regeln der Auslagerung und Ausnahmebehandlung. Sie können einen Zuweisungsoperator für die Verschiebung definieren, um Tauschoperationen effizienter zu gestalten. Weitere Informationen zur Move-Semantik und zum Move-Zuweisungsoperator finden Sie in Rvalue Reference Declarator: &&, und Move-Konstruktoren und Move-Zuweisungsoperatoren (C++). IWenn Sie keinen Zuweisungsoperator zum Verschieben oder keine Tauschfunktion bereitstellen, verwenden die Sortieralgorithmen den Kopierkonstruktor.
Das folgende einfache Beispiel zeigt die Verwendung von parallel_sort zum Sortieren einer vector von int Werten. Standardmäßig verwendet parallel_sort > zum Vergleichen von Werten. 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
*/
Dieses Beispiel zeigt eine Anleitung zum Bereitstellen einer benutzerdefinierten Vergleichsfunktion. Es 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 die Anleitung zum Bereitstellen einer Hash-Funktion für den parallel_radixsort Algorithmus. Dieses Beispiel sortiert 3D-Punkte. Die Punkte werden anhand ihrer Entfernung zu einem 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
*/
Zur Veranschaulichung wird in diesem Beispiel ein relativ kleiner Datensatz verwendet. Sie können die Anfangsgröße des Vektors erhöhen, um mit Leistungsverbesserungen bei größeren Datensätzen zu experimentieren.
In diesem Beispiel wird eine Lambda-Ausdruck als Hash-Funktion 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 Hash-Funktionsobjekt 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 Hash-Funktion muss einen integralen Typ zurückgeben (std::is_integral::value muss sein true). Dieser Integraltyp muss konvertierbar sein in den Typ size_t.
Auswahl eines Sortieralgorithmus
In vielen Fällen bietet parallel_sort das beste Gleichgewicht zwischen Geschwindigkeit und Speicherleistung. Wenn Sie jedoch die Größe Ihres Datensatzes, die Anzahl der verfügbaren Prozessoren oder die Komplexität Ihrer Vergleichsfunktion erhöhen, kann parallel_buffered_sort oder parallel_radixsort eine bessere Leistung erzielen. Die beste Methode, um zu ermitteln, welcher Sortieralgorithmus in einem bestimmten Szenario verwendet werden sollte, besteht darin, zu experimentieren und zu messen, wie lange das Sortieren typischer Daten unter repräsentativen Computerkonfigurationen dauert. Beachten Sie bei der Wahl einer Sortierstrategie die folgenden Leitlinien.
Die Größe Ihres Datasets. In diesem Dokument enthält ein kleiner Datensatz weniger als 1.000 Elemente, ein mittlerer Datensatz zwischen 10.000 und 100.000 Elemente und ein großer Datensatz mehr als 100.000 Elemente.
Der Arbeitsaufwand, den Ihre Vergleichsfunktion oder Hash-Funktion ausführt.
Die Menge der verfügbaren Computing Ressourcen.
Die Eigenschaften Ihrer aktivierten Daten. Beispielsweise kann ein Algorithmus bei Daten, die bereits fast sortiert sind, gute Ergebnisse erzielen, bei vollständig unsortierten Daten jedoch weniger gute Ergebnisse.
Die Größe der Blöcke. Das optionale Argument
_Chunk_sizegibt an, wann der Algorithmus von einer parallelen zu einer seriellen Sortierimplementierung wechselt, wenn er die Gesamtsortierung in kleinere Arbeitseinheiten unterteilt. Wenn Sie beispielsweise 512 angeben, wechselt der Algorithmus zur seriellen Implementierung, wenn eine Arbeitseinheit 512 oder weniger Elemente enthält. Eine serielle Implementierung kann die Gesamtleistung verbessern, da sie den Overhead eliminiert, der für die parallele Verarbeitung von Daten erforderlich ist.
Es ist möglicherweise nicht sinnvoll, einen kleinen Datensatz parallel zu sortieren, selbst wenn Sie über eine große Anzahl verfügbarer Ressourcen verfügen oder Ihre Vergleichsfunktion oder Hash-Funktion relativ viel Arbeit erfordert. Mit std::sort können Sie kleine Datensätze zu sortieren. (parallel_sort und parallel_buffered_sort rufen sort auf, wenn Sie eine Blockgröße angeben, die größer ist als der Datensatz; allerdings müsste parallel_buffered_sort O(N) Speicherplatz zuweisen, was aufgrund von Sperrkonflikten oder Speicherzuweisungen zusätzliche Zeit in Anspruch nehmen könnte.)
Wenn Sie Speicher sparen müssen oder Ihr Speicher-Zuordner anfällig für Sperrkonflikte ist, verwenden Sie parallel_sort zum Sortieren eines mittelgroßen Datensatzes. parallel_sort benötigt keinen zusätzlichen Speicherplatz; die anderen Algorithmen benötigen O(N) Speicherplatz.
Verwenden Sie parallel_buffered_sort , um mittelgroße Datensätze zu sortieren und wenn Ihre Anwendung die zusätzlichen Speicherplatzanforderungen von O(N) erfüllt. parallel_buffered_sort kann besonders nützlich sein, wenn Sie über eine große Anzahl von Ressourcen oder eine teure Vergleichsfunktion oder Hash-Funktion verfügen.
Verwenden Sie parallel_radixsort , um große Datensätze zu sortieren und wenn Ihre Anwendung die zusätzlichen Speicherplatzanforderungen von O(N) erfüllt. parallel_radixsort kann besonders nützlich sein, wenn die äquivalente Vergleichsoperation aufwändiger ist oder wenn beide Operationen aufwändig sind.
Caution
Die Implementierung einer guten Hash-Funktion setzt voraus, dass Sie den Datensatzbereich kennen und wissen, wie jedes Element im Datensatz in einen entsprechenden Wert ohne Vorzeichen umgewandelt wird. Da die Hash-Operation mit vorzeichenlosen Werten arbeitet, sollten Sie eine andere Sortierstrategie in Betracht ziehen, wenn keine vorzeichenlosen Hash-Werte erzeugt werden können.
Das folgende Beispiel vergleicht die Leistung von sort, parallel_sort, parallel_buffered_sortund parallel_radixsort anhand derselben großen Menge zufälliger 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, bei dem davon ausgegangen wird, dass die Zuweisung von O(N) Speicherplatz während der Sortierung akzeptabel ist, erzielt parallel_radixsort auf diesem Computer mit dieser Konfiguration die beste Leistung für diesen Datensatz.
Verwandte Themen
| Titel | Description |
|---|---|
| Vorgehensweise: Schreiben einer parallel_for-Schleife | Zeigt eine Anleitung zur Verwendung des Algorithmus parallel_for zur Matrixmultiplikation. |
| Vorgehensweise: Schreiben einer parallel_for_each-Schleife | Zeigt eine Anleitung zur Verwendung des Algorithmus parallel_for_each zur parallelen Berechnung der Anzahl von Primzahlen in einem std::array -Objekt. |
| 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. |
| Anleitung: Verwendung von parallel_invoke zur Ausführung von parallelen Operationen | 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. |
| Anleitung: Parallele Ausführung von Map- und Reduce-Operationen | Zeigt eine Anleitung zur Verwendung des Algorithmus parallel_transform und parallel_reduce algorithms to perform a map und reduce operation that counts the occurrences of words in files. |
| Parallel Patterns Library (PPL) | Beschreibt die PPL, die ein imperatives Programmiermodell bereitstellt, das Skalierbarkeit und Benutzerfreundlichkeit bei der Entwicklung paralleler Anwendungen fördert. |
| Abbruch in der PPL | Erläutert die Rolle der Stornierung in der PPL, die Anleitung zum Stornieren paralleler Arbeiten und die Bestimmung, wann eine Aufgabengruppe storniert ist. |
| Ausnahmebehandlung | Erläutert die Rolle der Ausnahmebehandlung in den Laufzeiten Parallelität. |