Parallelisierung „Reduce“ in „MapReduce“

Question

Ich verstehe, wie Karte leicht parallelisierbar ist -. Jeder Computer / CPU kann nur auf einem kleinen Teil des Arrays arbeitet

Ist Verkleinern / foldl parallelizable? Es scheint, wie jede Berechnung auf der vorhergehenden abhängt. Ist es nur parallelizable für bestimmte Arten von Funktionen?

Answer 1

Wenn Sie Ihre Reduktion zugrunde liegende Operation assoziativ * ist, können Sie mit der Reihenfolge der Operationen und Ort spielen. Deshalb haben Sie oft eine baumartige Struktur in der Phase ‚sammeln‘, so können Sie es in mehreren Stichen in logarithmischer Zeit tun:

a  +  b  +  c  +  d
 \   /       \   /
 (a+b)       (c+d)
     \       /
   ((a+b)+(c+d))

anstelle von (((a + b) + c) + d)

Wenn Ihr Betrieb kommutativ ist, ist weitere Optimierung möglich, wie Sie in einer anderen Reihenfolge sammeln können (es kann für Datenabgleich wichtig sein, wenn diese Operationen Vektoroperationen zum Beispiel sind)

[*] Ihre realen gewünschten mathematischen Operationen, diese nicht auf wirksame Typen wie Schwimmer natürlich.

Answer 2

Ja, wenn der Bediener ist assoziativ. Zum Beispiel können Sie eine Liste von Zahlen parallelisieren Summieren:

step 1: 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8
step 2:   3   +   7   +   11  +   15
step 3:       10      +       26
step 4:               36

Das funktioniert, weil (a + b) + c = a + (b + c), das heißt die Reihenfolge, in der die Additionen durchgeführt werden, keine Rolle.

Answer 3

Überprüfen Sie die kombinieren Phase in Hadoop out

http://wiki.apache.org/hadoop/HadoopMapReduce

Answer 4

Nicht sicher, was Plattform / Sprache Sie jetzt denken, aber Sie können Operatoren wie diese parallelisieren reduzieren:

// Original
result = null;
foreach(item in map) {
    result += item;
}

// Parallel
resultArray = array();
mapParts = map.split(numThreads);
foreach(thread) {
    result = null;
    foreach(item in mapParts[thread]) {
        result += item;
    }
    resultArray += result;    // Lock this!
}
waitForThreads();
reduce(resultArray);

Wie Sie sehen können, eine parallele Implementierung ist einfach rekursiv. Sie spalten die Karte auf, arbeiten in einem eigenen Thread auf jedem Teil, führen Sie dann eine andere zu reduzieren, sobald diese Fäden die Stücke zusammen zu bringen fertig sind.

(Dies ist die programmatische Argumentation hinter Piotr Lesnick Antwort .)

Answer 5

Technisch reduzieren a ist nicht das gleiche wie ein foldl (zerlegbare links), die auch als accumulate beschrieben werden kann.

Das Beispiel von Jules gegeben zeigt eine Verringerung des Betriebs sehr gut:

step 1: 1 + 2 + 3 + 4 
step 2:   3   +   7   
step 3:       10      

beachten, dass an jedem das Ergebnis ist ein Array Schritt wird das Endergebnis enthält, die eine Anordnung von einem Artikel ist.

Eine Falte links ist wie folgt aus:

step 0: a = 0
step 1: a = a + 1 
step 2: a = a + 2 
step 3: a = a + 3
step 4: a = a + 4
step 5: a

Jetzt offensichtlich diese beide die gleichen Ergebnisse liefern, sondern ein foldl verfügt über ein gut definiertes Ergebnis, wenn einen nicht-assoziativen Operator (wie Subtraktion) gegeben, während ein Betreiber nicht reduziert.

Answer 6

Es hängt von Ihrem Reduce Schritt. In einer Hadoop-Stil Implementierung von MapReduce ist Ihr Reducer einmal aufgerufen zu werden pro Taste mit allen Zeilen relevant für diesen Schlüssel.

So zum Beispiel Ihres Mapper könnte in vielen ungeordneten Webserver-Logs nehmen, das Hinzufügen einiger Metadaten (zum Beispiel Geokodierung) und emittierende [key, record] Paare mit einer Cookie-ID als Schlüssel. Ihr Reducer würde dann einmal pro Cookie-ID aufgerufen werden und würde alle Daten für dieses Cookie zugeführt werden, und aggregierte Informationen, wie zB Besuchsfrequenz oder durchschnittliche Seiten pro Besuch aufgerufen berechnen konnte. Oder Sie auf geocode Daten eingeben können, und aggregierte Statistiken sammeln basierend auf Geographie.

Auch wenn Sie nicht pro-Schlüssel Aggregat Analyse tun - in der Tat, auch wenn Sie etwas über den gesamten Satz sind Rechen - es könnte möglich sein, Ihre Berechnung in Stücke zu brechen, von denen jede mit einem Reducer zugeführt werden könnte, .