Parallelizzare il "Riduci" in "MapReduce"

Question

Capisco come Map sia facilmente parallelizzabile: ogni computer / CPU può funzionare solo su una piccola porzione dell'array.

Riduci / piega è parallelizzabile? Sembra che ogni calcolo dipenda dal precedente. È solo parallelizzabile per alcuni tipi di funzioni?

Answer 1

Se l'operazione sottostante alla riduzione è associativa *, puoi giocare con l'ordine delle operazioni e la località. Quindi spesso hai una struttura ad albero nella fase di 'raccolta', quindi puoi farlo in diversi passaggi in tempo logaritmico:

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

anziché (((a + b) + c) + d)

Se l'operazione è commutativa, sono possibili ulteriori ottimizzazioni in quanto è possibile riunirle in un ordine diverso (può essere importante per l'allineamento dei dati quando tali operazioni sono operazioni vettoriali, ad esempio)

[*] le tue reali operazioni matematiche desiderate, non quelle su tipi efficaci come i float ovviamente.

Answer 2

Sì, se l'operatore è associativo. Ad esempio, puoi parallelizzare sommando un elenco di numeri:

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

Questo funziona perché (a + b) + c = a + (b + c), ovvero l'ordine in cui vengono eseguite le aggiunte non importa.

Answer 3

Guarda la fase di associazione in Hadoop

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

Answer 4

Non sei sicuro di quale piattaforma / lingua stai pensando, ma puoi parallelizzare ridurre gli operatori in questo modo:

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

Come puoi vedere, un'implementazione parallela è facilmente ricorsiva. Suddividi la mappa, operi su ogni parte nel suo thread, quindi esegui un'altra riduzione una volta che quei thread sono stati fatti per unire i pezzi.

(Questo è il ragionamento programmatico dietro La risposta di Piotr Lesnick .)

Answer 5

Tecnicamente una riduzione non è la stessa di una piega (piega a sinistra) che può anche essere descritta come un accumulo.

L'esempio fornito da Jules illustra molto bene un'operazione di riduzione:

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

Nota che ad ogni passaggio il risultato è un array, incluso il risultato finale che è un array di un elemento.

Una piega a sinistra è come la seguente:

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

Ora ovviamente entrambi producono gli stessi risultati, ma un foldl ha un risultato ben definito quando viene dato un operatore non associativo (come la sottrazione) mentre un operatore di riduzione no.

Answer 6

Dipende dal passaggio Riduci. In un'implementazione di MapReduce in stile Hadoop, il tuo Reducer viene chiamato una volta per chiave, con tutte le righe rilevanti per quella chiave.

Quindi, ad esempio, il tuo Mapper potrebbe ricevere molti registri di server Web non ordinati, aggiungere alcuni metadati (ad es. geocodifica) ed emettere coppie [chiave, registrazione] con un ID cookie come chiave. Il tuo riduttore verrebbe quindi chiamato una volta per ID cookie e verrebbero forniti tutti i dati per quel cookie e potrebbe calcolare informazioni aggregate come la frequenza di visita o le pagine medie visualizzate per visita. Oppure puoi digitare i dati del geocodice e raccogliere statistiche aggregate basate sulla geografia.

Anche se non stai eseguendo un'analisi aggregata per chiave - anzi, anche se stai calcolando qualcosa sull'intero set - potrebbe essere possibile suddividere il tuo calcolo in blocchi, ognuno dei quali potrebbe essere inviato a un Riduttore .