Параллельные примитивы: map и reduce

Урок вводит два базовых параллельных примитива, на которых стоят почти все остальные.

map применяет независимую функцию к каждому элементу (идеально параллельно). reduce сворачивает массив в одно значение ассоциативной операцией (параллельно за O(log n) шагов).

map: тривиальный параллелизм

Операция map берёт массив и применяет функцию к каждому элементу независимо. Поскольку элементы не зависят друг от друга, это embarrassingly parallel (бесстыдно параллельная) задача: раздай элементы по ядрам, и всё. Никакой синхронизации, никакого обмена. Возведение в квадрат, нормализация пикселей, применение модели к каждой строке датасета — всё это map.

# map: независимая функция к каждому элементу
data = [1, 2, 3, 4, 5, 6, 7, 8]

def f(x):
    return x * x + 1

result = [f(x) for x in data]   # каждый элемент независим -> идеально параллельно
print("вход: ", data)
print("map:  ", result)

Вывод:

вход:  [1, 2, 3, 4, 5, 6, 7, 8]
map:   [2, 5, 10, 17, 26, 37, 50, 65]

reduce: сворачивание в одно значение

reduce объединяет все элементы одной операцией: сумма, максимум, произведение, логическое И. Наивно это последовательный проход за O(n). Но если операция ассоциативна (порядок группировки не важен: (a+b)+c = a+(b+c)), её можно считать деревом за O(log n) параллельных шагов — об этом отдельный урок. Ассоциативность — ключевое требование: без неё дерево даст неверный результат.

from functools import reduce as freduce

data = [3, 1, 7, 0, 4, 1, 6, 3]

print("сумма:        ", freduce(lambda a, b: a + b, data))
print("максимум:     ", freduce(lambda a, b: a if a > b else b, data))
print("произведение: ", freduce(lambda a, b: a * b, data))

Вывод:

сумма:         25
максимум:      7
произведение:  0

map + reduce вместе

Самая частая связка: применить функцию к каждому элементу (map), потом свернуть результаты (reduce). Подсчёт суммы квадратов, скалярное произведение, средняя яркость изображения — это map с последующим reduce. Именно этот шаблон дал имя системе MapReduce для кластеров (отдельный урок).

data = [1, 2, 3, 4, 5]
# map: квадрат; reduce: сумма  ->  сумма квадратов
squares = [x * x for x in data]
total = sum(squares)
print("квадраты:", squares)
print("сумма квадратов:", total)

Вывод:

квадраты: [1, 4, 9, 16, 25]
сумма квадратов: 55

Как работает под капотом

map не требует коммуникации вовсе — каждое ядро работает со своим куском и пишет в свою область результата. reduce требует «собирающей» фазы: частичные результаты ядер нужно объединить. Обычно делают локальный reduce на каждом ядре (свернуть свой кусок), а потом объединить N частичных результатов деревом. Так коммуникация минимальна: вместо n значений пересылаются только N (по одному на ядро).

Сила map и reduce в том, что они композируемы: из них, как из кубиков, собирается удивительно много. Скалярное произведение двух векторов — это map (перемножить пары) плюс reduce (сложить произведения). Подсчёт, сколько элементов удовлетворяют условию, — map (вернуть 1 или 0) плюс reduce (сумма). Поиск максимума — reduce с операцией «больший из двух». Освоив эти два примитива и поняв, что любая ассоциативная свёртка параллелится деревом, вы получаете готовый параллельный алгоритм для целого класса задач, даже не задумываясь о потоках. Именно поэтому почти каждая параллельная библиотека начинается с реализации именно map и reduce.

Частые ошибки

Применять reduce с неассоциативной операцией (например, вычитанием) и параллельным деревом — результат будет неверным.
Думать, что map требует синхронизации — нет, если функция не трогает общее состояние.
Делать reduce наивно за O(n) там, где дерево дало бы O(log n).

Итоги

map — независимая функция к каждому элементу, идеально параллелен без синхронизации.
reduce — сворачивание ассоциативной операцией; параллельно за O(log n) деревом.
map+reduce — фундаментальный шаблон, давший имя одноимённой системе для кластеров.