Распараллеливание «Уменьшить» в «MapReduce»

Question

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

Является ли Reduce / 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

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

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

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 5

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

// 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 6

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

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

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