Parallelisieren der "Reduce" in "MapReduce"

Question

Ich verstehe, wie Map leicht parallelisierbar ist - jeder Computer/CPU kann nur auf einen kleinen Teil des Arrays arbeiten.

Ist Reduce/foltl parallelisierbar? Es scheint, dass jede Berechnung von der vorherigen abhängt. Ist es für bestimmte Arten von Funktionen nur parallelisierbar?

Answer 1

Wenn 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 zu tun:

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

statt (((a + b) + c) + d)

Wenn Ihr Betrieb kommutativ ist, sind 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 nicht die auf effektiven Typen wie Floats natürlich.

Answer 2

nicht sicher, welche Plattform/Sprache Sie denken an, 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 leicht rekursiv ist. Sie teilen die Karte auf, bearbeiten jedes Teil in einem eigenen Thread und führen dann eine weitere Reduzierung durch, sobald diese Threads fertig sind, um die Teile zusammen zu bringen.

(Dies ist die programmatische Begründung Piotr Lesnick's answer.)

Answer 3

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

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

Dies funktioniert, weil (a + b) + c = a + (b + c), dh die Reihenfolge, in der die Additionen durchgeführt werden, keine Rolle .

Answer 4

Schauen Sie sich die kombinieren Phase in Hadoop

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

Answer 5

Es hängt von Ihrem Schritt zu reduzieren. In einer Hadoop-ähnlichen Implementierung von MapReduce wird Ihr Reducer einmal mit pro Schlüssel, mit allen für diesen Schlüssel relevanten Zeilen aufgerufen.

So könnte beispielsweise Ihr Mapper viele ungeordnete Webserver-Logs aufnehmen, einige Metadaten (z. B. Geocodierung) hinzufügen und [Schlüssel, Datensatz] -Paare mit einer Cookie-ID als Schlüssel ausgeben. Ihr Reducer würde dann einmal pro Cookie-ID aufgerufen und würde alle Daten für diesen Cookie erhalten. Er könnte aggregierte Informationen wie die Besuchshäufigkeit oder durchschnittliche Seiten pro Besuch berechnen. Oder Sie können Geokodierungsdaten eingeben und aggregierte Statistiken basierend auf Geografie sammeln.

Selbst wenn Sie keine Aggregatanalyse pro Schlüssel durchführen - in der Tat, selbst wenn Sie etwas über den gesamten Satz berechnen - könnte es möglich sein, Ihre Berechnung in Stücke zu zerlegen, von denen jedes einem zugeführt werden könnte Reduzierer.

Answer 6

Technisch ist ein Reduce nicht dasselbe wie ein Foldl (fold-left), das auch als Accumulate bezeichnet werden kann.

Das Beispiel von Jules gegebenen veranschaulicht einen Betrieb sehr gut reduzieren:

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

anzumerken, dass das Ergebnis bei jedem Schritt ein Array ist, einschließlich des Endergebnisses, das eine Anordnung von einem Artikel ist.

Klappbarer links ist wie die folgende:

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 

Nun Offensichtlich ist diese beide die gleichen Ergebnisse erzielen, aber ein foldl hat ein gut definierte Ergebnis, wenn einen nicht-assoziativen Operator gegeben (wie Subtraktion), wohingegen Ein Reduce-Operator tut dies nicht.