Parallelizing the "Reduce" w "MapReduce"

Question

Rozumiem, jak Mapę można łatwo zrównoważyć - każdy komputer/CPU może po prostu działać na małej części tablicy.

Czy można zracjonalizować/foldować równolegle? Wygląda na to, że każde obliczenie zależy od poprzedniego. Czy jest to możliwe do zrównoleglenia dla niektórych typów funkcji?

Answer 1

Jeśli obniżenie podstawowej operacji jest łączne *, można grać z rzędu operacji i miejscowości. Dlatego często trzeba się drzewiastą strukturę w fazie „zbierać”, więc można zrobić to w kilku przejściach w czasie logarytmicznym:

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

zamiast (((a + b) + c) + d)

Jeśli operacja jest przemienne, dalsza optymalizacja są możliwe, jak można zebrać w innej kolejności (może to być ważne dla wyrównania danych, gdy te operacje są operacje wektorowe na przykład)

[*] Twoje prawdziwe żądane operacje matematyczne nie te, które są skuteczne w typach takich jak pływaki.

Answer 2

Nie wiesz, co platforma/język myślisz, ale można parallelize zmniejszyć operatorów tak:

// 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); 

Jak widać, równoległa realizacja jest łatwo rekurencyjne. Rozdzielacie mapę, operujecie na każdej części w jej własnym wątku, a następnie wykonujemy kolejną redukcję po wykonaniu tych wątków, aby połączyć te elementy razem.

(Jest to programowy Rozumowanie Piotr Lesnick's answer.)

Answer 3

Tak, jeśli operator jest asocjacyjny. Na przykład, można parallelise zsumowanie listę numerów:

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

To działa, ponieważ (a + b) + c = a + (b + c), czyli takiej kolejności, w której dodatki są wykonywane nie ma znaczenia .

Answer 4

Sprawdź fazy łączą w Hadoop

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

Answer 5

To zależy od Reduce kroku. W implementacji MapReduce w stylu Hadoop, Twój Reducer jest wywoływany po za klucz, ze wszystkimi wierszami powiązanymi z tym kluczem.

Na przykład twój Mapper może przyjmować wiele nieuporządkowanych dzienników serwera WWW, dodając pewne metadane (np. Geokodowanie) i emitując [klucz, rekord] par z identyfikatorem pliku cookie jako kluczem. Twój Redukcja byłby wtedy wywoływany raz na jeden identyfikator pliku cookie i byłby zasilany wszystkimi danymi tego pliku cookie, i mógł obliczać zagregowane informacje, takie jak częstotliwość odwiedzin lub średnie strony przeglądane podczas wizyty. Możesz też wprowadzić dane geokodowe i zebrać statystyki zbiorcze na podstawie geografii.

Nawet jeśli nie wykonujesz analizy zagregowanej na klucz - nawet, jeśli coś obliczysz w całym zestawie - możliwe będzie złamanie obliczeń na kawałki, z których każda może być Reduktor.

Answer 6

Technicznie redukcja nie jest taka sama jak fałd (fałd-lewy), który można również opisać jako kumulację.

Podany przykład Jules ilustruje zmniejszenie działania dobrze:

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

Należy zauważyć, że w każdym stopniu w wyniku to tablica, w tym w efekcie końcowym, która jest tablicą jednego elementu.

rozkładanego lewej jest jak następuje:

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 

teraz oczywiście te oba dają takie same wyniki, ale foldl ma dobrze określony rezultat podawany operator nie-asocjatywnym (jak odejmowania), natomiast operator redukcji nie.