Paralelizar el "Reducir" en "MapReduce"

Question

Entiendo cómo Map es fácilmente paralelizable: cada computadora / CPU puede operar en una pequeña porción de la matriz.

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

Answer 1

Si su operación subyacente de reducción es asociativa *, puede jugar con el orden de las operaciones y la localidad. Por lo tanto, a menudo tiene una estructura similar a un árbol en la fase de 'reunión', por lo que puede hacerlo en varios pasos en tiempo logarítmico:

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, es posible una mayor optimización, ya que puede recopilar en un orden diferente (puede ser importante para la alineación de datos cuando esas operaciones son operaciones vectoriales, por ejemplo)

[*] sus operaciones matemáticas reales deseadas, no las de tipos efectivos como flotadores, por supuesto.

Answer 2

Sí, si el operador es asociativo. Por ejemplo, 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 se realizan las adiciones no importa.

Answer 3

Echa un vistazo a la fase de combinación en Hadoop

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

Answer 4

No estoy seguro de qué plataforma / lenguaje está pensando, pero puede paralelizar operadores de reducción como este:

// 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 puede ver, una implementación paralela es fácilmente recursiva. Divide el mapa, opera cada parte en su propio hilo, luego realiza otra reducción una vez que esos hilos están hechos para unir las piezas.

(Este es el razonamiento programático detrás de la respuesta de Piotr Lesnick .)

Answer 5

Técnicamente, una reducción no es lo mismo que un pliegue (pliegue a la izquierda) que también puede describirse como una acumulación.

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

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, incluido el resultado final, que es una matriz de un elemento.

Un doblez a la izquierda es el 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, ambos producen los mismos resultados, pero un pliegue tiene un resultado bien definido cuando se le da un operador no asociativo (como la resta), mientras que un operador de reducción no.

Answer 6

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

Entonces, por ejemplo, su Mapper podría estar recibiendo muchos registros de servidores web desordenados, agregando algunos metadatos (por ejemplo, geocodificación) y emitiendo pares [clave, registro] con una ID de cookie como clave. Luego se llamaría a su Reductor una vez por ID de cookie y se enviarían todos los datos para esa cookie, y podría calcular información agregada, como la frecuencia de visita o el promedio de páginas vistas por visita. O podría 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 a un Reductor .