wake-up-neo.com

Warum wurde in C++ 17 Std :: Reduce hinzugefügt?

Ich habe nach einer gründlichen Erklärung der Bedeutung von "Rückgabewert" für std::reduce gesucht, die laut cppreference.com wie folgt lautet:

 enter image description here

Nachdem ich die Idee hinter dem Abschnitt "Rückgabewert" richtig erkannt habe, kann ich vielleicht besser herausfinden, wo ich std::reduce über std::accumulate wählen sollte. 

33
Aria Pahlavan

Da Sie um eine gründliche Erklärung gebeten haben und die vorherige Antwort nur die Grundlagen abdeckt, erlaube ich mir, eine gründlichere hinzuzufügen.

std::reduce Soll den zweiten Hauptschritt des MapReduce-Programmiermodells ausführen. Die Grundidee ist, dass die Plattform (in diesem Fall die C++ - Implementierung) diese beiden primitiven Operationen zuordnet und reduziert und der Programmierer für jede der beiden Operationen, die die "eigentliche Arbeit" ausführen, Rückrufoperationen bereitstellt.

Grundsätzlich bildet der Rückruf für die Kartenoperation einen Eingabewert auf einen Zwischenwert ab. Der Callback for Reduce kombiniert zwei Zwischenwerte zu einem Zwischenwert. Der letzte verbleibende Zwischenwert wird zur Ausgabe des gesamten MapReduce. Es scheint an sich ein sehr restriktives Modell zu sein, hat aber dennoch ein großes Anwendungsspektrum.

Die Plattform muss natürlich mehr tun, wie z. B. "Mischen" (Verteilen der Eingaben, normalerweise in Gruppen, auf verschiedene Verarbeitungseinheiten) und Planen, aber dies ist für den Anwendungsprogrammierer von geringer Bedeutung.

Übrigens heißt in der C++ - Standardbibliothek die Operation "map" transform. Es hat auch in C++ 17 Parallelitätsunterstützung erhalten, aber ich werde später auf die Parallelität eingehen.

Hier ist ein erfundenes Beispiel: Nehmen wir an, wir haben eine Funktion, die eine Ganzzahl in eine Zeichenfolgendarstellung umwandelt. Nun wollen wir anhand einer Liste von ganzen Zahlen die Textdarstellung mit dem größten Verhältnis von Konsonanten zu Gesang. Z.B.

  • Eingabe: 1, 17, 22, 4, 8
  • Ausgabe: zweiundzwanzig

(Probieren Sie es aus, wenn Sie dieses Ergebnis nicht glauben.)

Wir könnten MapReduce hier verwenden, indem wir unsere Int-to-Text-Funktion als Rückruf für die Karte verwenden (rsp. std::transform) Und eine Funktion, die die Anzahl der Konsonanten und des Gesangs zählt und dann entweder die linke oder die rechte Hand auswählt Argument entsprechend. Hier gibt es einige Ineffizienzen, insbesondere sollte das "Verhältnis" zwischengespeichert werden, dies sind jedoch Details.

Nun könnte und sollte Ihre Frage lauten: Warum sollte es mich vielleicht interessieren? Schließlich haben Sie bisher nicht viel von der Verwendung von z. std::transform Und std::reduce Auf diese Weise, und Sie hätten auch std::accumulate Anstelle des letzteren verwenden können. Die Antwort bei einer ausreichend großen Anzahl von Eingabewerten sind natürlich Ausführungsrichtlinien - die beiden vorherigen Standardfunktionsschablonen weisen Überladungen auf, die implizite Parallelität ermöglichen. Aber das wirft immer noch die Frage auf, warum man MapReduce und nicht einen Thread-Pool oder std::async Und eine Reihe von handgeschriebenen Schleifen verwenden würde? Insbesondere für "reine" Berechnungen mit großen Vektoren oder anderen Containern ohne E/A ist es häufig praktischer, die beiden MapReduce-Rückrufe zu schreiben, da Sie nicht mit allen Details der Eingabedaten umgehen müssen auf verschiedene Fäden verteilen und dann kombinieren.

Zweitens unterstützt MapReduce eine Disziplin, bei der Ihre Berechnungen so strukturiert werden, dass sie sehr effektiv parallelisiert werden können. Natürlich können Sie in einer Programmiersprache, die das imperative Paradigma unterstützt, wie C++, immer noch Dinge durcheinander bringen, indem Sie eine Reihe von Mutexen sperren oder auf irgendeine Weise, die Sie haben könnten, andere Threads zu stören. Das MapReduce-Paradigma fordert jedoch zum Schreiben unabhängiger Mapping-Callbacks auf. Als einfache Faustregel gilt: Wenn diese Tasks Daten gemeinsam nutzen, sollten sie schreibgeschützt sein, damit Kopien derselben gleichzeitig in mehreren CPU-Caches gespeichert werden können. Gut geschriebene Aufgaben können in Kombination mit einer effizienten Plattformimplementierung der zugrunde liegenden Algorithmen auf Hunderte oder sogar Tausende von CPU-Kernen skaliert werden, wie die bereits häufig verwendeten MapReduce-Plattformen (wie Apache Hadoop) zeigen, dies jedoch nur als notwendig erachten Beispiel und nicht als kostenlose Werbung).

Aber die Frage war hauptsächlich nach std::reduce - wir könnten dieses hochskalierbare Mapping trotzdem durchführen und dann std::accumulate Für die Zwischenergebnisse ausführen, oder? Und hier kommen wir zu dem, was François Andrieux zuvor geschrieben hat. accumulate führt aus, was Mathematiker eine linke Falte nennen. Wenn Sie die Operationen und ihre Operanden als Binärbaum anzeigen, ist dies ein linksgerichteter Baum, z. um 1, 2, 3 und 4 hinzuzufügen:

   +
  / \
  + 4
 / \
 + 3
/ \
1 2

Wie Sie sehen, ist das Ergebnis jeder Operation eines der Argumente der nächsten Operation. Dies bedeutet, dass es eine lineare Kette von Datenabhängigkeiten gibt, und das ist der Fluch aller Parallelität. Um eine Million Zahlen hinzuzufügen, benötigen Sie eine Million aufeinanderfolgende Vorgänge, die einen einzelnen Kern blockieren, und Sie können keine zusätzlichen Kerne verwenden. Sie werden die meiste Zeit nichts zu tun haben, und der Kommunikationsaufwand wird die Kosten der Berechnungen bei weitem überwiegen. (Es ist schlimmer, weil moderne CPUs mehrere einfache Berechnungen pro Takt ausführen können. Dies funktioniert jedoch nicht, wenn so viele Datenabhängigkeiten vorliegen, dass die meisten ALUs oder FPUs ungenutzt bleiben.)

Durch Aufheben der Einschränkung, dass eine linke Falte verwendet werden muss, ermöglicht std::reduce Der Plattform, Rechenressourcen effizienter zu nutzen. Selbst wenn Sie die Single-Threaded-Überladung verwenden, könnte die Plattform zum Beispiel SIMD verwenden, um eine Million Ganzzahlen in viel weniger als einer Million Operationen hinzuzufügen. und die Anzahl der Datenabhängigkeiten wird stark reduziert. Eine 10-fache Beschleunigung bei einer gut geschriebenen Integer-Addition würde mich nicht überraschen. Zugegeben, dieser spezielle Fall könnte wahrscheinlich unter der As-If-Regel optimiert werden, da die C++ - Implementierung "weiß", dass die Ganzzahladdition (fast, siehe unten) assoziativ ist.

Die Reduzierung geht jedoch, wie bereits erwähnt, noch weiter, indem Ausführungsrichtlinien unterstützt werden, d. H. In den meisten Fällen Mehrkernparallelität. Theoretisch könnte ein ausgeglichener binärer Operationsbaum verwendet werden. (Denken Sie daran, dass ein Baum ausgeglichen ist, wenn die Tiefe weniger als zwei oder die Tiefe des linken Teilbaums höchstens um 1 von der Tiefe des rechten Teilbaums abweicht.) Ein solcher Baum hat nur eine logarithmische Tiefe. Wenn wir eine Million Ganzzahlen haben, beträgt die minimale Baumtiefe 20, sodass wir - theoretisch - bei ausreichenden Kernen und ohne Kommunikationsaufwand eine Beschleunigung um den Faktor 50.000 erreichen können, selbst bei der optimierten Single-Thread-Berechnung. In der Praxis ist das natürlich eine Menge Wunschdenken, aber wir können immer noch große Beschleunigungen erwarten.

Lassen Sie mich dennoch kurz darauf hinweisen, dass Leistung nicht mit Effizienz gleichzusetzen ist. Die Verwendung von 64 Kernen für jeweils 100 ms bedeutet eine viel höhere Leistung als die Verwendung eines Kerns für 1.000 ms, jedoch eine viel geringere CPU-Effizienz. Eine andere Möglichkeit ist, dass Leistung Effizienz im Sinne einer Minimierung der verstrichenen Zeit ist. Es gibt jedoch auch andere Maßstäbe für die Effizienz - insgesamt verwendete CPU-Zeit, RAM verwendet, Energieverbrauch usw.) Die Hauptmotivation von parallelem MapReduce ist die Bereitstellung einer höheren Leistung. Ob dies die CPU-Zeit oder den Energieverbrauch verringert, ist unklar, und es wird sehr wahrscheinlich den Spitzenwert erhöhen RAM Verwendung.

Um das Ganze abzurunden, hier sind einige Einschränkungen . Wie bereits erwähnt, ist reduce nicht deterministisch, wenn die Operationen nicht assoziativ oder nicht kommutativ sind. Glücklicherweise sind die wichtigsten arithmetischen Operationen wie Addition und Multiplikation assoziativ und kommutativ, oder? Wir alle wissen, dass beispielsweise die Ganzzahl- und die Gleitkommazugabe beide Eigenschaften haben. Und natürlich bin ich scherzhaft. In C++ sind weder vorzeichenbehaftete Ganzzahl- noch Gleitkommazugaben assoziativ. Dies ist bei Gleitkommazahlen auf mögliche Rundungsunterschiede bei Zwischenergebnissen zurückzuführen. Dies lässt sich leicht veranschaulichen, wenn wir als Beispiel ein einfaches dezimales Gleitkommaformat mit zwei signifikanten Ziffern auswählen und die Summe 10 + 0,4 + 0,4 berücksichtigen. Wenn dies durch die normalen C++ - Syntaxregeln als Linksfalt gemacht wird, erhalten wir (10 + 0,4) + 0,4 = 10 + 0,4 = 10, da jedes Mal das Ergebnis auf 10 abgerundet wird. Wenn wir es jedoch als 10 machen + (0,4 + 0,4), das erste Zwischenergebnis ist 0,8, und 10 + 0,8 wird dann auf 11 aufgerundet. Außerdem können Rundungsfehler durch eine hohe Tiefe des Operationsbaums stark vergrößert werden, so dass eine linke Falte tatsächlich eine ist der schlimmsten Dinge, die man tun könnte, wenn es um Genauigkeit geht. Es gibt verschiedene Möglichkeiten, mit diesem Verhalten umzugehen, angefangen beim Sortieren und Gruppieren der Eingaben bis hin zur Verwendung einer erhöhten Zwischengenauigkeit. Wenn es jedoch um reduce geht, gibt es möglicherweise keine Möglichkeit, 100% Run-for-Run zu erzielen Konsistenz.

Die andere, möglicherweise überraschendere Beobachtung ist, dass die Ganzzahladdition mit Vorzeichen in C++ nicht assoziativ ist. Der Grund dafür ist die Möglichkeit eines Überlaufs, um es klar auszudrücken: (-1) + 1 + INT_MAX. Entsprechend den normalen Syntaxregeln oder accumulate lautet das Ergebnis INT_MAX. Wenn Sie jedoch reduce verwenden, wird dies möglicherweise als (-1) + (1 + INT_MAX) Umgeschrieben, das einen Ganzzahlüberlauf und damit undefiniertes Verhalten enthält. Da reduce die Reihenfolge der Operanden willkürlich ändern kann, ist dies sogar dann der Fall, wenn die Eingaben { INT_MAX, -1, 1 } Sind.

Ich empfehle hier, sicherzustellen, dass der Rückruf von reduce keinen Überlauf hervorruft. Dies kann erreicht werden, indem der zulässige Eingabebereich begrenzt wird (z. B. wenn Sie 1000 ints hinzufügen, stellen Sie sicher, dass keine größer als INT_MAX / 1000 Oder kleiner als INT_MIN / 1000, Gerundet ist B. oder äquivalent dazu, indem Sie einen größeren Integer-Typ verwenden oder als absolutes letztes Mittel (da dies sowohl teuer als auch schwierig zu handhaben ist) zusätzliche Überprüfungen im Rückruf reduce vornehmen. In den meisten praktischen Fällen ist reduce jedoch in Bezug auf einen Ganzzahlüberlauf nur unwesentlich weniger sicher als accumulate.

39
Arne Vogel

std::accumulate durchläuft den Container in der Reihenfolge wo std:reduce möglicherweise nicht. Da die Bestellung nicht garantiert wird, führt std::reduce zusätzliche Anforderungen ein: 

Das Verhalten ist nicht deterministisch, wenn binary_op nicht assoziativ oder kommutativ ist. Das Verhalten ist undefiniert, wenn binary_op ein Element ändert oder einen Iterator in [first; last], einschließlich des End-Iterators.

std::reduce bietet jedoch Überladungen, die Parallelisierung unterstützen, die mit std::accumulate nicht verfügbar sind. Mit std::reduce können Sie Ihren Betrieb automatisch parallelisieren, vorausgesetzt, er erfüllt die oben genannten Anforderungen.

29
  • Das Zulassen von Parallelität ist der Hauptgrund für das Hinzufügen von std :: reduz

  • Außerdem muss sichergestellt sein, dass die Operation, die Sie mit std :: verkleinern möchten, sowohl assoziativ als auch kommutativ ist.

    • Addition ist beispielsweise assoziativ und liefert die gleichen Ergebnisse, wenn die Akkumulation mithilfe von std :: verkleinert wird.
      100 + 50 + 40 + 10 = 200 (100 + 40) + (50 + 10) = 200

    • Aber wenn die Subtraktion nicht assoziativ ist, kann std :: verkleinern zu falschen Ergebnissen führen.
      100 - 50 - 40 - 10 = 0 NOT SAME AS (100 - 40) - (50 - 10) = 20

  • Effizienz
    std::vector<double> v(100000, 0.1); double result = std::accumulate(v.begin(), v.end(), 0.0); double result = std::reduce(std::execution::par,v.begin(),v.end()) //Faster

0
kbagal