Paralléliser le & 8282; Réduire & # 8221; dans & # 8220; MapReduce & # 8221;

Question

Je comprends comment Map est facilement parallélisable - chaque ordinateur / processeur ne peut fonctionner que sur une petite partie du tableau.

Est-ce que Réduire / foldl est parallélisable? Il semble que chaque calcul dépend du précédent. Est-ce simplement parallélisable pour certains types de fonctions?

Answer 1

Si votre opération sous-jacente à la réduction est associative *, vous pouvez jouer avec l'ordre des opérations et la localité. Par conséquent, vous avez souvent une structure arborescente dans la phase de collecte, vous pouvez donc le faire en plusieurs passes en temps logarithmique:

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

au lieu de (((a + b) + c) + d)

Si votre opération est commutative, d'autres optimisations sont possibles car vous pouvez les regrouper dans un ordre différent (cela peut être important pour l'alignement des données lorsque ces opérations sont des opérations vectorielles, par exemple)

[*] vos opérations mathématiques souhaitées, pas celles sur des types efficaces tels que float bien sûr.

Answer 2

Oui, si l'opérateur est associatif. Par exemple, vous pouvez paralléliser la somme d’une liste de nombres:

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

Cela fonctionne car (a + b) + c = a + (b + c), c’est-à-dire que l’ordre dans lequel les ajouts sont effectués n’importe pas.

Answer 3

Découvrez la phase de combinaison dans Hadoop

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

Answer 4

Vous n'êtes pas sûr de la plate-forme / du langage que vous envisagez, mais vous pouvez paralléliser des opérateurs de réduction comme ceci:

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

Comme vous pouvez le constater, une implémentation parallèle est facilement récursive. Vous divisez la carte, vous exploitez chaque partie dans son propre fil, puis vous effectuez une autre réduction une fois que ces filets sont terminés pour rassembler les éléments.

(C’est le raisonnement programmatique derrière la réponse de Piotr Lesnick .)

Answer 5

Techniquement, une réduction n’est pas identique à un foldl (pli à gauche), qui peut également être décrit comme une accumulation.

L'exemple donné par Jules illustre très bien une opération de réduction:

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

Notez qu'à chaque étape le résultat est un tableau, y compris le résultat final qui est un tableau d'un élément.

Un pli gauche ressemble à ceci:

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

Évidemment, ces deux méthodes produisent les mêmes résultats, mais un foldl a un résultat bien défini lorsqu'un opérateur non associatif (comme la soustraction) est attribué, contrairement à un opérateur réduit.

Answer 6

Cela dépend de votre étape de réduction. Dans une implémentation de MapReduce de style Hadoop, votre réducteur est appelé une fois par clé, avec toutes les lignes pertinentes pour cette clé.

Ainsi, par exemple, votre mappeur peut enregistrer de nombreux journaux de serveur Web non ordonnés, ajouter des métadonnées (par exemple, un géocodage) et émettre des paires [clé, enregistrer] avec un ID de cookie comme clé. Votre réducteur serait alors appelé une fois par ID de cookie, recevrait toutes les données de ce cookie et pourrait calculer des informations globales telles que la fréquence des visites ou le nombre moyen de pages consultées par visite. Vous pouvez également saisir des données de géocodage et collecter des statistiques globales basées sur la géographie.

Même si vous n'effectuez pas d'analyse globale clé par clé - en fait, même si vous calculez quelque chose sur l'ensemble de la série - il peut être possible de diviser votre calcul en morceaux, chacun pouvant être transmis à un réducteur. .