Гранулярность и баланс нагрузки

Урок про два рычага эффективности: размер порции работы и равномерность её распределения.

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

Крупная или мелкая гранулярность

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

мелко:  [.][.][.][.][.][.][.][.]  много кусков, много overhead
крупно: [....][....]              мало кусков, простой ядер
норма:  [..][..][..][..]          окупается и хватает на балансировку

Баланс нагрузки

Даже при хорошей гранулярности можно проиграть из-за неравномерности. Если 100 задач раздать трём воркерам поровну, кому-то достанется 34, кому-то 33 — почти ровно. Но если задачи разной длительности (одна считается 1 секунду, другая 100), равное число задач не значит равную нагрузку. Общее время определяет самый загруженный воркер.

# статическое распределение: раздаём задачи разной "стоимости" по кругу
costs = [10, 1, 1, 10, 1, 1, 10, 1, 1]   # три тяжёлых, шесть лёгких
workers = 3
load = [0, 0, 0]
assign = [[], [], []]
for i, c in enumerate(costs):
    w = i % workers          # round-robin
    load[w] += c
    assign[w].append(c)

for w in range(workers):
    print(f"воркер {w}: задачи {assign[w]}, нагрузка {load[w]}")
print("итоговое время = макс нагрузка =", max(load))
print("идеальное время =", sum(costs) / workers)

Вывод:

воркер 0: задачи [10, 10, 10], нагрузка 30
воркер 1: задачи [1, 1, 1], нагрузка 3
воркер 2: задачи [1, 1, 1], нагрузка 3
итоговое время = макс нагрузка = 30
идеальное время = 12.0

Катастрофа: round-robin собрал все три тяжёлых задачи на воркере 0. Время 30 вместо идеальных 12 — два других ядра почти простаивали. Равное число задач не спасло.

Статическое против динамического распределения

Статическое: работа распределяется заранее. Дёшево, но плохо при неизвестной или неравной стоимости задач. Динамическое: воркеры берут новую порцию, как только освободятся (общая очередь задач). Дороже из-за синхронизации очереди, зато само выравнивает нагрузку — медленные задачи не блокируют простаивающие ядра. Для неоднородных задач почти всегда выбирают динамическое распределение (master-worker или work stealing).

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

Динамический балансировщик держит общий пул заданий. Освободившийся воркер атомарно забирает следующее задание. Если заданий много и они мелкие, балансировка почти идеальна, но растёт overhead на синхронизацию очереди. Поэтому часто берут «порциями» (chunk): воркер забирает не одно задание, а пачку, уменьшая число обращений к очереди ценой чуть худшего баланса.

Гранулярность и баланс — два рычага, которые тянут в разные стороны, и искусство в том, чтобы найти равновесие. Мелкая гранулярность улучшает баланс (легче раздать ровно), но раздувает overhead. Крупная гранулярность снижает overhead, но ухудшает баланс (тяжёлый кусок некуда деть). Поэтому на практике подбирают размер порции экспериментально под конкретную машину и задачу: начинают с разумного значения, замеряют эффективность, корректируют. Универсального «правильного» размера не существует — он зависит от стоимости задания, числа ядер и цены синхронизации очереди.

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

Делить по числу задач, а не по их стоимости — тяжёлые задачи соберутся в одном месте.
Брать слишком мелкую гранулярность — overhead съест выигрыш.
Применять статическое распределение к задачам с непредсказуемой длительностью.

Итоги

Гранулярность — размер порции работы; нужен баланс между overhead и простоем.
Баланс нагрузки определяется самым загруженным воркером, а не средним.
Для неоднородных задач динамическое распределение (очередь, work stealing) бьёт статическое.