Декомпозиция данных против декомпозиции задач

Урок про фундаментальный выбор: что именно мы делим между процессорами — данные или работу.

Декомпозиция — разбиение задачи на части, которые можно выполнять параллельно. Два базовых вида: по данным и по задачам.

Декомпозиция данных

Самый распространённый приём: одна и та же операция применяется к разным частям данных. Массив из миллиона элементов режут на N кусков, каждое ядро обрабатывает свой кусок. Так считают сумму, применяют фильтр к изображению (каждое ядро — свою полосу пикселей), умножают матрицы (каждое ядро — свои строки). Этот вид естественно масштабируется: больше данных — больше кусков, и они независимы.

# декомпозиция данных: applied одна и та же функция к разным кускам
data = list(range(1, 13))   # 1..12
workers = 3
chunk = len(data) // workers

def process(x):           # одинаковая операция для всех кусков
    return x * x

for w in range(workers):
    part = data[w*chunk:(w+1)*chunk]
    result = [process(x) for x in part]
    print(f"воркер {w}: {part} -> {result}")

Вывод:

воркер 0: [1, 2, 3, 4] -> [1, 4, 9, 16]
воркер 1: [5, 6, 7, 8] -> [25, 36, 49, 64]
воркер 2: [9, 10, 11, 12] -> [81, 100, 121, 144]

Декомпозиция задач

Здесь делят не данные, а разные виды работы. Пример — обработка видео: один поток декодирует кадр, другой накладывает фильтр, третий кодирует результат. Каждый делает свою операцию. Это естественно для конвейеров (pipeline) и для задач, где есть набор независимых подзадач разной природы. Декомпозиция задач масштабируется хуже: число разных задач ограничено, тогда как данных можно резать сколько угодно.

Их сочетают

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

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

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

Декомпозиция данных опирается на то, что элементы обрабатываются независимо — нет зависимостей между кусками. Если же результат для куска i зависит от куска i-1 (как в префиксной сумме), наивно разрезать нельзя, нужен специальный алгоритм (об этом — урок про scan). Декомпозиция задач опирается на то, что стадии конвейера могут работать над разными элементами одновременно: пока стадия 2 фильтрует кадр 5, стадия 1 уже декодирует кадр 6.

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

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

Итоги

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