Reduktions-Operator

aus Wikipedia, der freien Enzyklopädie

In der Informatik bezeichnet ein Reduktions-Operator (englisch: Reduction Clause) einen Operator, welcher oft in der parallelen Programmierung eingesetzt wird, um Elemente eines Arrays auf ein einzelnes Ergebnis zu reduzieren. Reduktions-Operatoren sind assoziativ und häufig (aber nicht immer) kommutativ.[1][2][3] Die Reduktion von Mengen ist ein wichtiger Bestandteil von Programmiermodellen wie MapReduce, in welchen ein Reduktions-Operator auf alle Elemente angewendet wird, bevor sie reduziert werden. Andere parallele Algorithmen benutzen Reduktions-Operatoren als primäre Operationen, um komplexere Probleme zu lösen. Viele dieser Operatoren können auch benutzt werden, um Daten auf alle Prozessoren zu verteilen.

Theorie

Ein Reduktions-Operator kann dabei helfen, ein Problem in viele Teilprobleme aufzuteilen, indem die Lösungen der Teilprobleme genutzt werden, um das finale Ergebnis zu erhalten. Sie ermöglichen es, bestimmte serielle Operationen parallel auszuführen und dadurch die Anzahl der notwendigen Berechnungsschritte zu reduzieren. Ein Reduktions-Operator speichert die Ergebnisse der Teilprobleme in einer privaten Kopie der Variable. Diese privaten Kopien werden am Ende zu einer gemeinsamen Kopie zusammengeführt.

Ein Operator ist ein Reduktions-Operator, falls

  • er ein Array auf einen einzelnen Wert reduzieren kann[1] und
  • das finale Ergebnis aus den Teilergebnissen erhalten werden kann.[1]

Diese beiden Voraussetzungen sind für kommutative und assoziative Operatoren erfüllt, welche auf alle Elemente des Arrays angewendet werden.

Beispiele hierfür sind die Addition und Multiplikation sowie bestimmte logische Operatoren (und, oder etc.).

Ein Reduktions-Operator Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \oplus} kann in konstanter Zeit auf eine Menge

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle V = \left\{v_0 = \begin{pmatrix} e_0^0 \\ \vdots \\ e_0^{m-1}\end{pmatrix}, v_1 = \begin{pmatrix} e_1^0 \\ \vdots \\ e_1^{m-1}\end{pmatrix}, \dots, v_{p-1} = \begin{pmatrix} e_{p-1}^0 \\ \vdots \\ e_{p-1}^{m-1}\end{pmatrix}\right\}}

von Vektoren mit jeweils Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle m} Elementen angewendet werden. Das Ergebnis Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle r} der Operation ist die Kombination der Elemente

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle r = \begin{pmatrix} e_0^0 \oplus e_1^0 \oplus \dots \oplus e_{p-1}^0 \\ \vdots \\ e_0^{m-1} \oplus e_1^{m-1} \oplus \dots \oplus e_{p-1}^{m-1}\end{pmatrix} = \begin{pmatrix} \bigoplus_{i=0}^{p-1} e_i^0 \\ \vdots \\ \bigoplus_{i=0}^{p-1} e_i^{m-1} \end{pmatrix}}

und muss nach der Ausführung bei einem designierten Prozessor gespeichert werden. Wenn das Ergebnis Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle r} auf allen Prozessoren zur Verfügung stehen soll, wird dies oft Allreduce genannt. Ein optimaler sequenzieller Linearzeit-Algorithmus für Reduktion kann nach und nach von vorne nach hinten angewendet werden, wobei jeweils zwei Vektoren mit dem Ergebnis der Operation auf diese Vektoren ersetzt werden, wobei die Menge der Vektoren jedes Mal um eins reduziert wird. Hierfür werden Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (p-1) \cdot m} Schritte benötigt. Sequenzielle Algorithmen sind nicht schneller als Linearzeit-Algorithmen, parallele Algorithmen hingegen können die Laufzeit verkürzen.

Beispiel

Gegeben sei ein Array Fehler beim Parsen (Konvertierungsfehler. Der Server („https://wikimedia.org/api/rest_“) hat berichtet: „Cannot get mml. Server problem.“): {\displaystyle [2,3,5,1,7,6,8,4]} . Die Summe des gesamten Arrays can seriell berechnet werden, indem das Array sequenziell auf eine einzelne Summe mit Hilfe des '+' Operators reduziert wird. Startet man von vorne, ergibt sich folgende Berechnung:

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle ((((((2 + 3) + 5) + 1) + 7) + 6) + 8) + 4 = 36}

Da '+' sowohl assoziativ als auch kommutativ ist, ist '+' ein Reduktions-Operator. Daher kann diese Reduktion auch parallel auf mehreren Kernen erfolgen, wobei jeder Kern nur die Summe einer Teilmenge des Arrays berechnet und der Reduktions-Operator diese Teilergebnisse zusammenführt. Mit Hilfe eines Binärbaums können auf 4 Kernen jeweils Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (2 + 3)} , Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (5 + 1)} , Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (7 + 6)} und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (8 + 4)} berechnet werden. Daraufhin können zwei Kerne Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (5 + 6)} und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (13 + 12)} berechnen und am Ende berechnet ein einzelner Kern Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle (11 + 25) = 36} . Mit 4 Kernen kann die Summe also in Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \log_{2}8 = 3} statt Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 7} Schritten berechnet werden, wie es bei dem seriellen Algorithmus der Fall ist. Der Algorithmus berechnet Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle ((2 + 3) + (5 + 1)) + ((7 + 6) + (8 + 4))} , was auf Grund der Assoziativität der Addition dem gleichen Ergebnis entspricht. Die Kommutativität wäre wichtig, wenn es einen Hauptkern gäbe, welcher die Teilaufgaben auf andere Kerne verteilt, da hierbei die Teilergebnisse in unterschiedlicher Reihenfolgen zurückkommen könnten. Die Eigenschaft der Kommutativität würde hier garantieren, dass das Ergebnis weiterhin das gleiche ist.

Gegenbeispiel

Matrixmultiplikation ist kein Reduktions-Operator, da diese Operation nicht kommutativ ist. Würden die Kerne ihre Teilergebnisse in beliebiger Reihenfolge zurückgeben, wäre das Endergebnis höchstwahrscheinlich falsch. Allerdings ist Matrixmultiplikation assoziativ, weshalb das Endergebnis korrekt ist, wenn man dafür sorgt, dass die Teilergebnisse in der richtigen Reihenfolge sind. Dies ist bei der Benutzung von Binärbäumen der Fall.

Algorithmen

Binomial-Baum Algorithmen

Bezüglich der parallelen Algorithmen gibt es hauptsächlich zwei Modelle, die Parallel Random Access Machine als eine Erweiterung des Arbeitsspeichers mit gemeinsamen Speicher zwischen den Kernen und Bulk Synchronous Parallel Computers, bei welchen die Kerne kommunizieren und synchronisiert werden. Beide Modelle haben unterschiedliche Effekte auf die Zeitkomplexität, weshalb hier beide vorgestellt werden.

PRAM-Algorithmus

Dieser Algorithmus nutzt eine weit verbreitete Methode, wobei Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle p} eine Zweiterpotenz ist. Eine Umkehrung wird häufig genutzt um die Elemente zu verteilen.[4][5][6]

Eine Visualisierung des Algorithmus mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle p = 8, m = 1} und Addition als Reduktions-Operator
for Fehler beim Parsen (Konvertierungsfehler. Der Server („https://wikimedia.org/api/rest_“) hat berichtet: „Cannot get mml. Server problem.“): {\displaystyle k\gets 0} to Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \lceil\log_2 p\rceil - 1} do
for Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle i \gets 0} to do in parallel
if Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle p_i} is active then
if bit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle k} of Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle i} is set then
set Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle p_i} to inactive
else if Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle i + 2^k < p}
Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x_i \gets x_i \oplus^{\star} x_{i+2^k}}

Der binäre Operator für Vektoren ist elementweise definiert, sodass

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \begin{pmatrix} e_i^0 \\ \vdots \\ e_i^{m-1}\end{pmatrix} \oplus^\star \begin{pmatrix} e_j^0 \\ \vdots \\ e_j^{m-1}\end{pmatrix} = \begin{pmatrix} e_i^0 \oplus e_j^0 \\ \vdots \\ e_i^{m-1} \oplus e_j^{m-1} \end{pmatrix}} .

Der Algorithmus beruht außerdem auf den Annahmen, dass am Anfang Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x_i = v_i} für alle Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle i} gilt und dass die Kerne Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle p_0, p_1,\dots p_{n-1}} genutzt werden. In jeder Iteration wird die Hälfte der Kerne inaktiv, diese tragen nicht mehr zur Berechnung bei. Die Animation zeigt eine Visualisierung des Algorithmus mit Addition als Operator. Senkrechte Linien stellen die Kerne dar, in welchen die Berechnung der Elemente auf der Linie berechnet werden. Unten sind die acht Elemente der Eingabe dargestellt. Jeder Schritt in der Animation entspricht einem parallelen Schritt in der Ausführung des Algorithmus. Ein aktiver Kern Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle p_i} wendet den Operator auf ein für ihn lokal verfügbares Element Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x_i} sowie Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x_j} an, wobei Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle j} der kleinste Index mit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle j > i} ist, sodass im aktuellen Schritt Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle p_j} inaktiv wird. Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x_i} und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x_j} sind nicht notwendigerweise Teil der Eingabe, da diese Speicherstellen überschrieben und für vorher berechnete Ausdrücke wiederverwendet werden. Um die Kerne untereinander zu koordinieren ohne weiteren Aufwand durch Kommunikation zwischen ihnen zu verursachen, macht sich der Algorithmus die Indexierung der Kerne durch Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 0} bis Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle p-1} zunutze. Jeder Kern macht von seinem Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle k} -ten least significant bit abhängig, ob er inaktiv wird oder den Operator auf sein eigenes Element sowie das Element mit dem Index, bei welchem das Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle k} -te last significant bit nicht gesetzt ist, anwendet. Das zugrundeliegende Schema hierfür ist ein Bionomial-Baum, daher der Name des Algorithmus.

Am Ende das Algorithmus liegt das Ergebnis nur Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle p_0} vor. Für eine Allreduce-Operation muss das Ergebnis allen Kernen vorliegen, was durch einen anschließenden Broadcast ermöglicht wird. Die Anzahl der Kerne Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle p} sollte eine Zweiterpotenz sein, ansonsten kann die Anzahl bis zur nächsten Zweierpotenz aufgefüllt werden. Es gibt Algorithmen, welche speziell auf diesen Fall zugeschnitten sind.[7]

Laufzeitanalyse

Die äußerste Schleife wird Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \lceil\log_2 p\rceil} Mal ausgeführt. Die Zeit für jeden parallelen Durchlauf liegt in Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \mathcal{O}(m)} , da jeder Kern entweder zwei Vektoren kombiniert oder inaktiv wird. Daher gilt für die parallele Zeit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle T(p, m) = \mathcal{O}(\log(p) \cdot m)} . Um Schreib-Lese-Konflikte zu vermeiden, kann Exclusive Read, Exclusive Write verwendet werden. Für den Speedup gilt

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle S(p, m) \in \mathcal{O}\left(\frac{T_\text{seq}}{T(p, m)}\right) = \mathcal{O}(\frac{p}{\log(p)})} ,

daher gilt für die Effizienz

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle E(p, m) \in \mathcal{O}\left(\frac{S(p, m)}{p}\right) = \mathcal{O}\left(\frac{1}{\log(p)}\right)} .

Die Effizienz leidet unter der Tatsache, dass in jedem Schritt die Hälfte aller Kerne inaktiv wird, d. h. im Schritt Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle i} sind Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \frac{p}{2^i}} Kerne aktiv.

Verteilte Speicher Algorithmen

Im Gegensatz zu den PRAM-Algorithmen, teilen sich die Kerne hier keinen gemeinsamen Speicher. Daher müssen die Daten explizit zwischen den Kernen ausgetauscht werden, wie der folgende Algorithmus zeigt.

for Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle k \gets 0} to Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \lceil\log_2 p\rceil - 1} do
for Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle i \gets 0} to Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle p - 1} do in parallel
if Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle p_i} is active then
if bit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle k} of Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle i} is set then
send Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x_i} to Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle p_{i-2^k}}
set Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle p_k} to inactive
else if Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle i + 2^k < p}
receive Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x_{i+2^k}}
Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x_i \gets x_i \oplus^\star x_{i+2^k}}

Der einzige Unterschied zu der PRAM Version von oben liegt in der Verwendung von expliziten Primitiven für die Kommunikation. Das Prinzip bleibt jedoch das gleiche.

Laufzeitanalyse

Die Kommunikation zwischen den Kernen verursacht etwas Overhead. Eine einfache Analyse des Algorithmus nutzt das BSP-Modell und beachtet die notwendige Zeit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle T_\text{start}} , um einen Datenaustausch zu initiieren sowie die notwendige Zeit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle T_\text{byte}} , um ein Byte Daten zu senden. Die resultierende Laufzeit ist dann Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle \Theta((T_\text{start} + n \cdot T_\text{byte}) \cdot \log(p))} , wobei Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle m} Elemente eines Vektors die Größe Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n} haben.

Pipeline Algorithmus

Visualization of the pipeline-algorithm with Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle p = 5, m = 4} and addition as the reduction operator.

Für die verteilte Speicher Modelle kann es Sinn ergeben, die Daten in Form einer Pipeline auszutauschen. Dies gilt insbesondere, wenn Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle T_\text{start}} klein im Vergleich zu Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle T_\text{byte}} ist. Normalerweise teilen lineare Pipelines die Daten in kleinere Teile auf und verarbeiten diese stufenweise. Im Gegensatz zu den Bionomial-Baum Algorithmen macht sich der Pipeline Algorithmus die Tatsache zunutze, dass Vektoren nicht untrennbar sind: Der Operator kann auch auf einzelne Elemente anwendet werden.[8]

for Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle k \gets 0} to Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle p+m-3} do
for Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle i \gets 0} to Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle p - 1} do in parallel
if Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle i \leq k < i+m \land i \neq p-1}
send Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x_i^{k-i} } to Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle p_{i+1} }
if Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle i-1 \leq k < i-1+m \land i \neq 0}
receive Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x_{i-1}^{k+i-1}} from Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle p_{i-1}}
Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle x_{i}^{k+i-1} \gets x_{i}^{k+i-1} \oplus x_{i-1}^{k+i-1}}

Es ist wichtig, dass das Senden und Empfangen gleichzeitig ausgeführt wird, damit der Algorithmus korrekt funktioniert. Das Ergebnis befindet sich am Ende in Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle p_{p-1}} . Die Animation zeigt die Ausführung des Algorithmus auf Vektoren der Größe 4 mit 5 Kernen. Zwei Schritte in der Animation entsprechen einem Schritt in der parallelen Ausführung.

Laufzeitanalyse

Die Anzahl der Schritt in der parallelen Ausführung beträgt Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle p + m -2} , es braucht Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle p-1} Schritte bis der letzte Kern sein erstes Element erhält und weitere Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle m-1} Schritte, bis alle Elemente angekommen sind. Im BSP-Modell beträgt die Laufzeit daher Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle T(n, p, m) = (T_\text{start} + \frac{n}{m}T_\text{byte})(p+m-2)} , wobei Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n} die Größe eines Vektors in Bytes ist.

Auch wenn Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle m} ein fester Wert ist, so ist es möglich, Elemente von Vektoren logisch zu gruppieren und dadurch Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle m} zu reduzieren. Zum Beispiel kann eine Probleminstanz mit Vektoren der Länge vier gelöst werden, indem die Vektoren in ihre ersten und letzten beiden Elemente aufgeteilt werden, welche dann immer gemeinsam gesendet und verrechnet werden. In diesem Fall werden in jedem Schritt doppelt so viele Daten gesendet, allerdings hat sich die Anzahl der Schritte etwa auf die Hälfte verringert. Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle m} ist also halbiert, während die Größe in Bytes Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle n} gleich bleibt. Die Laufzeit Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle T(p)} für diesen Ansatz hängt also von Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle m} ab, was optimiert werden kann, wenn Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle T_\text{start}} und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle T_\text{byte}} bekannt sind. Es ist optimal für

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle m = \sqrt{\frac{n \cdot (p-2)T_\text{byte}}{T_\text{start}}}} ,

wobei angenommen wird, dass dies in einem kleineren Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle m} resultiert, welches das ursprüngliche teilt.

Anwendungen

Reduktion ist eine der wichtigsten kollektiven Operationen im Message Passing Interface, wo die Leistung des genutzten Algorithmus wichtig ist und ständig für verschiedene Anwendungsfälle ausgewertet wird.[9] Operatoren können als Parameter für MPI_Reduce und MPI_Allreduce verwendet werden, wobei der Unterschied darin liegt, ob das Ergebnis am Ende in allen oder nur einem Kern vorliegt. Für MapReduce sind effiziente Reduktions-Algorithmen wichtig, um große Datensätze zu verarbeiten, auch in großen Clustern.[10][11]

Manche parallele Sortieralgorithmen nutzen Reduktionen um große Datensätze zu verarbeiten.[12]

Literatur

  • Rohit Chandra: Parallel Programming in OpenMP. Morgan Kaufmann, 2001, ISBN 1558606718, S. 59–77.
  • Yan Solihin: Fundamentals of Parallel Multicore Architecture. CRC Press, 2016, ISBN 978-1-4822-1118-4, S. 75.

Weblinks

Einzelnachweise

  1. ↑ a b c Solihin
  2. ↑ Chandra p. 59
  3. ↑ Murray Cole: Bringing skeletons out of the closet: a pragmatic manifesto for skeletal parallel programming. In: Parallel computing. 30, 2004, S. 393.
  4. ↑ Amotz Bar-Noy, Shlomo Kipnis: Broadcasting multiple messages in simultaneous send/receive systems. In: Discrete Applied Mathematics. 55, Nr. 2, 1994, S. 95–105. doi:10.1016/0166-218x(94)90001-9.
  5. ↑ Eunice E. Santos: Optimal and Efficient Algorithms for Summing and Prefix Summing on Parallel Machines. In: Journal of Parallel and Distributed Computing. 62, Nr. 4, 2002, S. 517–543. doi:10.1006/jpdc.2000.1698.
  6. ↑ P. Slater, E. Cockayne, S. Hedetniemi: Information Dissemination in Trees. In: SIAM Journal on Computing. 10, Nr. 4, 1. November 1981, ISSN 0097-5397, S. 692–701. doi:10.1137/0210052.
  7. ↑ Rolf Rabenseifner, Jesper Larsson Träff: More Efficient Reduction Algorithms for Non-Power-of-Two Number of Processors in Message-Passing Parallel Systems. In: Lecture Notes in Computer Science. Band 3241. Springer, Berlin, Heidelberg 2004, ISBN 978-3-540-23163-9, Recent Advances in Parallel Virtual Machine and Message Passing Interface, S. 36–46, doi:10.1007/978-3-540-30218-6_13 (englisch).
  8. ↑ A. Bar-Noy, S. Kipnis: Designing broadcasting algorithms in the postal model for message-passing systems. In: Mathematical Systems Theory. 27, Nr. 5, 1. September 1994, ISSN 0025-5661, S. 431–452. doi:10.1007/BF01184933.
  9. ↑ Jelena Pješivac-Grbović, Thara Angskun, George Bosilca, Graham E. Fagg, Edgar Gabriel, Jack J. Dongarra: Performance analysis of MPI collective operations. In: Cluster Computing. 10, Nr. 2, 1. Juni 2007, ISSN 1386-7857, S. 127–143. doi:10.1007/s10586-007-0012-0.
  10. ↑ Ralf Lämmel: Google's MapReduce programming model — Revisited. In: Science of Computer Programming. 70, Nr. 1, 2008, S. 1–30. doi:10.1016/j.scico.2007.07.001.
  11. ↑ Hermes Senger, Veronica Gil-Costa, Luciana Arantes, Cesar A. C. Marcondes, Mauricio Marín, Liria M. Sato, Fabrício A.B. da Silva: BSP cost and scalability analysis for MapReduce operations. In: Concurrency and Computation: Practice and Experience. 28, Nr. 8, 10. Juni 2016, ISSN 1532-0634, S. 2503–2527. doi:10.1002/cpe.3628.
  12. ↑ Michael Axtmann, Timo Bingmann, Peter Sanders, Christian Schulz: Practical Massively Parallel Sorting. , S. 13–23. doi:10.1145/2755573.2755595
Abgerufen von „https://de.wikiup.org/index.php?title=Reduktions-Operator&oldid=223947246“