Я понимаю, как Map легко распараллеливается - каждый компьютер/процессор может просто работать с небольшой частью массива.
Уменьшает/складывает параллелизуемость? Кажется, что каждое вычисление зависит от предыдущего. Является ли оно просто параллелизуемым для определенных типов функций?
Если ваша базовая операция сокращения ассоциативна *, вы можете играть с порядком операций и локальностью. Поэтому на фазе "собрать" у вас часто есть древовидная структура, поэтому вы можете сделать это за несколько проходов в логарифмическом времени:
a + b + c + d
\ / \ /
(a+b) (c+d)
\ /
((a+b)+(c+d))
вместо (((a + b) + c) + d)
Если ваша операция является коммутативной, возможна дальнейшая оптимизация, поскольку вы можете собирать в другом порядке (это может быть важно для выравнивания данных, если эти операции являются векторными операциями, например)
[*] ваши настоящие желаемые математические операции, а не те, которые относятся к эффективным типам, таким как плавающие, конечно.
Да, если оператор ассоциативен. Например, вы можете параллелизовать суммированию списка чисел:
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), то есть порядок, в котором выполняются дополнения, не имеет значения.
Проверьте фазу объединения в Hadoop
Не уверен, какую платформу/язык вы думаете, но вы можете распараллелить операторы сокращения следующим образом:
// 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);
Как вы можете видеть, параллельная реализация легко рекурсивна. Вы разбиваете карту вверх, работаете с каждой частью в своем потоке, а затем выполняете другое сокращение, как только эти потоки выполняются, чтобы собрать фрагменты.
(Это программная аргументация ответ Петра Лесника.)
Технически сокращение - это не то же самое, что сложить (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 имеет четко определенный результат при задании неассоциативного оператора (например, вычитания), тогда как оператор сокращения не имеет.
Это зависит от вашего шага "Уменьшить". В реализации MapReduce в стиле Hadoop ваш Reducer получает вызов один раз для каждого ключа со всеми строками, относящимися к этому ключу.
Итак, например, ваш Mapper может принимать множество журналов неупорядоченного веб-сервера, добавляя некоторые метаданные (например, геокодирование) и испуская пары [ключ, запись] с идентификатором файла cookie в качестве ключа. Затем ваш редуктор будет вызываться один раз за идентификатор файла cookie и будет загружать все данные для этого файла cookie и может вычислять агрегированную информацию, такую как частота посещений или средние страницы, просматриваемые за посещение. Или вы можете использовать данные геокода и собирать статистические данные на основе географии.
Даже если вы не выполняете агрегированный анализ на основе ключа - действительно, даже если вы что-то вычисляете по всему набору, возможно, можно разбить вычисление на куски, каждый из которых может быть передан в редуктор.