Параллелизация "Уменьшить" в "MapReduce"

Ответ 1

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

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

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

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

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

Ответ 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), то есть порядок, в котором выполняются дополнения, не имеет значения.

Ответ 3

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

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

Ответ 4

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

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

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

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

Ответ 5

Технически сокращение - это не то же самое, что сложить (fold-left), который также можно описать как скопление.

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

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

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

Ответ 6

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

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

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