Распараллеливание «Reduce» в «MapReduce»

Question

Я понимаю, насколько легко распараллелить Map — каждый компьютер/процессор может работать только с небольшой частью массива.

Можно ли распараллелить сокращение/foldl?Кажется, что каждое вычисление зависит от предыдущего.Можно ли его распараллелить только для определенных типов функций?

Answer 1

Если основная операция сокращения является ассоциативной *, вы можете играть с порядком операций и местностью. Поэтому у вас часто есть древовидная структура в фазе «сбора», поэтому вы можете сделать это за несколько проходов в логарифмическом времени:

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

вместо (((a + b) + c) + d)

Если ваша операция является коммутативной, возможна дальнейшая оптимизация, поскольку вы можете собирать данные в другом порядке (это может быть важно для выравнивания данных, когда эти операции, например, являются векторными операциями)

[*] ваши реальные желаемые математические операции, а не операции с эффективными типами, например, с плавающей точкой.

Answer 2

Да, если оператор ассоциативный. Например, вы можете распараллелить суммирование списка чисел:

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

Это работает, потому что (a + b) + c = a + (b + c), т. е. порядок выполнения дополнений не имеет значения.

Answer 3

Проверьте фазу объединения в Hadoop

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

Answer 4

Не уверен, о какой платформе / языке вы думаете, но вы можете распараллелить операторы типа Reduce следующим образом:

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

Как видите, параллельная реализация легко рекурсивна. Вы разбиваете карту на части, работаете с каждой частью в ее собственном потоке, а затем выполняете еще одно сокращение, как только эти потоки будут сделаны, чтобы собрать части вместе.

(Это программное обоснование ответа Петра Лесника .)

Answer 5

Технически уменьшение - это не то же самое, что сложение (влево), которое также можно назвать накоплением.

Пример, приведенный Жюлем, очень хорошо иллюстрирует операцию сокращения:

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

Обратите внимание, что на каждом шаге результат представляет собой массив, включая конечный результат, который представляет собой массив из одного элемента.

Сгиб влево выглядит следующим образом:

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

Теперь очевидно, что оба они дают одинаковые результаты, но сложение имеет четко определенный результат, если дан неассоциативный оператор (например, вычитание), а оператор сокращения - нет.

Answer 6

Это зависит от вашего шага уменьшения.В реализации MapReduce в стиле Hadoop ваш Редюсер вызывается один раз. за ключ, со всеми строками, соответствующими этому ключу.

Так, например, ваш Mapper может принимать множество неупорядоченных журналов веб-сервера, добавлять некоторые метаданные (например, геокодирование) и выдавать пары [ключ, запись] с идентификатором cookie в качестве ключа.Затем ваш Редюсер будет вызываться один раз для каждого идентификатора файла cookie и получать все данные для этого файла cookie, а также может вычислять совокупную информацию, такую ​​​​как частота посещений или среднее количество страниц, просмотренных за посещение.Или вы можете ввести данные геокодирования и собрать совокупную статистику на основе географического положения.

Даже если вы не выполняете агрегатный анализ по каждому ключу (даже если вы что-то вычисляете по всему набору), возможно, можно разбить ваши вычисления на фрагменты, каждый из которых можно передать в редуктор.