Paralelização o “Reduzir” em “MapReduce”

Question

Eu entendo como Mapa é facilmente paralelizável - cada computador / CPU apenas podem operar em uma pequena porção do array

.

É Reduzir / foldl paralelizável? Parece que cada computação depende da anterior. É apenas paralelizável para certos tipos de funções?

Answer 1

Se a sua redução operação subjacente é associativa *, você pode jogar com a ordem das operações e localidade. Por isso muitas vezes você tem uma árvore-como estrutura na fase de 'recolher', para que possa fazê-lo em vários passes em tempo logarítmica:

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

em vez de (((a + b) + c) + d)

Se a sua operação é comutativa, maior otimização são possíveis, como você pode se reunir em ordem diferente (pode ser importante para o alinhamento de dados quando essas operações são operações de vetor, por exemplo)

[*] o seu verdadeiro desejado operações matemáticas, e não aqueles em tipos eficazes como carros alegóricos, é claro.

Answer 2

Sim, se o operador é associativa. Por exemplo, você pode parallelise soma uma lista de números:

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

Isto funciona porque (a + b) + c = a + (b + c), isto é, a ordem na qual as adições são realizadas não importa.

Answer 3

Confira a fase combinam em Hadoop

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

Answer 4

Não sei o que plataforma / idioma que você está pensando, mas você pode paralelizar reduzir operadores como esta:

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

Como você pode ver, uma implementação paralela é facilmente recursiva. Você dividir o mapa, operar em cada parte, no seu segmento, em seguida, executar outra reduzir uma vez que esses tópicos são feitas para trazer as peças.

(Este é o raciocínio por trás programático do Piotr Lesnick resposta .)

Answer 5

Tecnicamente um reduzir, não é o mesmo que um foldl (fold-esquerda), o qual também pode ser descrito como um acumular.

O exemplo dado por Jules ilustra uma operação de reduzir muito bem:

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

Note-se que em cada passo, o resultado é uma matriz, incluindo o resultado final que é uma matriz de um item.

Uma dobra-esquerda é como o seguinte:

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

Agora, obviamente, estes ambos produzem os mesmos resultados, mas um foldl tem um resultado bem definido quando dado um operador não associativo (como subtração) enquanto que um reduzir operador não.

Answer 6

Depende do seu Reduzir etapa. Em uma implementação Hadoop-estilo de MapReduce, o redutor está sendo chamado uma vez per chave, com todas as linhas relevantes para essa chave.

Assim, por exemplo, o seu Mapper pode ser tomada em um monte de logs do servidor web não ordenadas, acrescentando alguns metadados (por exemplo, geocodificação) e emitindo [Key, ficha] pares com um ID do cookie como a chave. Seu redutor, então, ser chamado uma vez por ID do cookie e seriam alimentados todos os dados para esse cookie, e poderia computar informações agregado tais como frequência de visita ou Média de páginas visualizadas por visita. Ou você pode digitar em dados geocode, e reunir estatísticas agregadas com base na geografia.

Mesmo se você não está fazendo per-chave análise agregada - na verdade, mesmo se você está computando algo sobre todo o conjunto - que poderia ser possível quebrar o cálculo em pedaços, cada um dos quais poderia ser alimentados a um redutor .