Paralelización del "Reducir" en "MapReduce"

Question

Entiendo cómo el Mapa se puede paralelizar fácilmente: cada computadora/CPU puede operar en una pequeña porción de la matriz.

¿Reduce/foldl parallelizable? Parece que cada cálculo depende del anterior. ¿Es simplemente paralelable para ciertos tipos de funciones?

Answer 1

Si su reducción operación subyacente es * asociativo, se puede jugar con el orden de las operaciones y la localidad. Por lo tanto, que a menudo tienen una estructura en forma de árbol en la fase de 'recoger', por lo que se puede hacer en varias pasadas en el tiempo logarítmica:

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

en lugar de (((a + b) + c) + d)

Si su operación es conmutativa, son posibles una mayor optimización que se puede recoger en diferente orden (que puede ser importante para la alineación de datos cuando dichas operaciones son operaciones de vectores, por ejemplo)

[*] sus operaciones matemáticas deseados reales , no aquellos en tipos efectivos como flotadores, por supuesto.

Answer 2

No está seguro de qué plataforma/idioma que está pensando, pero se puede paralelizar reducir los operadores de la siguiente manera:

// 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 se puede ver, una aplicación paralela es fácilmente recursiva. Divides el mapa, operas cada parte en su propio hilo y luego realizas otra reducción una vez que los hilos están hechos para juntar las piezas.

(Este es el razonamiento detrás de Piotr Lesnick's answer programática.)

Answer 3

Sí, si el operador es asociativo. Por ejemplo, se puede paralelizar sumando una 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 

Esto funciona porque (a + b) + c = a + (b + c), es decir, el orden en que las adiciones se llevan a cabo no importa .

Answer 4

Mira la fase de combinar en Hadoop

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

Answer 5

Depende de su paso Reducir. En una implementación al estilo Hadoop de MapReduce, su Reducer se llama una vez por clave, con todas las filas relevantes para esa clave.

Así, por ejemplo, su Mapper podría estar tomando muchos registros del servidor web desordenados, agregando algunos metadatos (por ejemplo, geocodificación) y emitiendo pares de [clave, registro] con una ID de cookie como clave. Su Reducer se llamaría una vez por ID de cookie y se alimentaría con todos los datos de esa cookie, y podría calcular información agregada, como la frecuencia de visitas o el promedio de páginas visitadas por visita. O puede ingresar datos de geocodificación y recopilar estadísticas agregadas basadas en la geografía.

Incluso si no está haciendo un análisis agregado por clave, de hecho, incluso si está calculando algo en todo el conjunto, podría ser posible dividir su cálculo en fragmentos, cada uno de los cuales podría alimentarse en un Reductor

Answer 6

Técnicamente, reducir no es lo mismo que un doblez (doblar a la izquierda) que también se puede describir como un acumulado.

El ejemplo dado por Jules ilustra una operación de reducir muy bien:

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

Tenga en cuenta que en cada paso el resultado es una matriz, incluyendo el resultado final, que es una matriz de un artículo.

Un pliegue-izquierda es como la siguiente:

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 

Ahora, obviamente estos tanto producir los mismos resultados, pero una foldl tiene un resultado bien definido cuando se administra un operador no asociativo (como la resta), mientras un operador de reducción no.