Паттерны: master-worker, pipeline, stencil

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

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

Master-worker (хозяин-работник)

Один процесс-мастер раздаёт задания, а несколько воркеров их выполняют и возвращают результаты. Воркер, закончив, просит следующее задание. Это естественная динамическая балансировка: быстрые воркеры берут больше заданий, медленные — меньше, никто не простаивает. Идеально для задач из множества независимых единиц неравной или неизвестной стоимости: рендеринг кадров, обработка запросов, перебор вариантов.

# master-worker: мастер раздаёт задания, воркеры берут по мере готовности
from collections import deque

tasks = deque([("задача", c) for c in [5, 2, 8, 1, 3]])
workers = {0: 0, 1: 0}     # время каждого воркера

while tasks:
    free = min(workers, key=workers.get)   # самый свободный воркер
    name, cost = tasks.popleft()
    workers[free] += cost
    print(f"воркер {free} взял {name}(стоимость {cost}), занят до {workers[free]}")
print("время =", max(workers.values()))

Вывод:

воркер 0 взял задача(стоимость 5), занят до 5
воркер 1 взял задача(стоимость 2), занят до 2
воркер 1 взял задача(стоимость 8), занят до 10
воркер 0 взял задача(стоимость 1), занят до 6
воркер 0 взял задача(стоимость 3), занят до 9
время = 10

Pipeline (конвейер)

Данные проходят через цепочку стадий, и каждая стадия — отдельный процессор. Пока стадия 2 обрабатывает элемент 5, стадия 1 уже работает над элементом 6. Это декомпозиция задач: параллелизм возникает из того, что разные стадии трудятся над разными элементами одновременно. Применяется в обработке видео/звука, компиляции, сборочных линиях. Узкое место — самая медленная стадия: она определяет общую пропускную способность.

Конвейер из 3 стадий, поток элементов:
такт:  1     2     3     4     5
ст.1: [e1]  [e2]  [e3]  [e4]  [e5]
ст.2:       [e1]  [e2]  [e3]  [e4]
ст.3:             [e1]  [e2]  [e3]
после прогрева все 3 стадии заняты одновременно

Stencil (трафарет)

Каждый элемент обновляется по значениям своих соседей. Так устроены численные методы (теплопроводность, диффузия), обработка изображений (размытие, выделение границ), клеточные автоматы. Все элементы обновляются параллельно, но каждый читает окрестность. Сложность — на границах кусков нужны значения соседнего куска (halo/ghost-ячейки), которые приходится пересылать между процессорами на каждом шаге.

# stencil 1D: каждый элемент = среднее с соседями (один шаг)
a = [0, 0, 0, 9, 0, 0, 0]
n = len(a)
b = a[:]
for i in range(1, n-1):
    b[i] = (a[i-1] + a[i] + a[i+1]) / 3   # читаем окрестность
print("до: ", a)
print("после:", [round(x, 2) for x in b])

Вывод:

до:  [0, 0, 0, 9, 0, 0, 0]
после: [0, 0.0, 3.0, 3.0, 3.0, 0.0, 0]

Пик «растёкся» по соседям — классический шаг диффузии. Все обновления внутри шага независимы (читаем старое a, пишем новое b), поэтому параллельны.

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

Паттерны можно вкладывать друг в друга: master-worker, где каждый воркер внутри запускает stencil-вычисление на своём блоке. Pipeline часто комбинируют с декомпозицией данных внутри стадии. Распознав в задаче знакомый паттерн, вы получаете готовый рецепт коммуникации и балансировки, не изобретая их заново.

Ценность паттернов — в том, что они переводят расплывчатое «надо как-то распараллелить» в конкретный, проверенный рецепт. Увидев, что у вас поток данных через несколько преобразований, вы говорите «это pipeline» — и сразу знаете, что узким местом станет медленная стадия, что стадии надо балансировать, что между ними нужны буферы. Увидев множество независимых заданий неравной стоимости, вы говорите «это master-worker» — и сразу знаете про динамическую раздачу и риск перегрузки мастера. Паттерны экономят не код, а мышление: они дают словарь, на котором инженеры обсуждают параллельные системы, и набор готовых решений типичных проблем, которые иначе пришлось бы открывать заново и набивать те же шишки.

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

• В master-worker сделать мастера слишком «тяжёлым» — он станет узким местом, и воркеры будут ждать заданий.
• В pipeline не выровнять длительность стадий — медленная стадия задушит пропускную способность.
• В stencil забыть про обмен граничными (halo) ячейками — куски будут считать по устаревшим соседям.

Итоги

• Master-worker: мастер раздаёт задания, воркеры берут по готовности — динамический баланс.
• Pipeline: стадии-процессоры обрабатывают поток; ограничен самой медленной стадией.
• Stencil: обновление по соседям; требует обмена граничными ячейками между кусками.