Статические DAG-графы: почему TBB иногда избыточен и как сделать планировщик с гарантированным временем выполнения

Проблема: Современные планировщики вроде TBB оптимизированы для динамических workload'ов, но в реальности до 40% случаев (игровые движки, оффлайн-рендеринг) используют фиксированные DAG-графы, где важнее предсказуемость, чем гибкость.
В большинстве случаев, когда разработчику нужен параллелизм, он использует либо std::async, либо полноценный thread-пул (например, oneTBB). Эти инструменты отлично подходят для динамически растущих множеств задач, где граф неизвестен заранее и задачи могут порождать друг друга в ходе выполнения.

Но в реальных проектах довольно часто встречается совершенно другой сценарий:

граф исполнений известен полностью заранее,
выполняется один раз (или ограниченное число раз),
и при этом критичны предсказуемость, affinity и жёсткий контроль памяти.

Хороший пример — кадр игрового движка (один вызов → фиксированный DAG), оффлайн пайплайны, симуляции, инструменты, где граф описан статически.
Там throughput сам по себе не так важен - важнее гарантированное время выполнения, без всплесков и очередей.

Именно под такие задачи я сделал небольшой single-run DAG runtime, который не пытается быть ещё одним TBB, а целенаправленно решает фиксированный граф → один вызов → bounded execution (гарантированное время выполнения, без всплесков).

Почему обычный thread-pool здесь не подходит

Если в середине пайплайна есть узкое место (например, heavy stage), producer просто заваливает очередь задачами, и pool начинает “раздуваться”. Ни одна обычная арена не блокирует верхний уровень пока не появятся свободные consumer’ы — она просто продолжает enqueue.

Что если допустить, что граф известен полностью?

Оказалось, что в этом случае runtime можно заметно упростить и сделать жёстко ограниченным по поведению:

1. Пользователь явно строит граф зависимостей, через submit → then → when_all

2. При вызове run() граф seal’ится:

   • проверяется наличие циклов,

   • вычисляются начальные indegree для всех нод,

   • создаются inbox’ы

3. Воркеры начинают исполнять tokens:

   • work-first (push_bottom)

   • при отсутствии работы → range stealing по Chase–Lev deque

4. У каждой ноды есть:

   • max_concurrency

   • capacity inbox’а

   • Overflow = {Block, Drop, Fail}

5. При заполнении inbox’а producer блокируется (или задача отбрасывается), т.е. backpressure является частью runtime, а не пользовательского кода

Что находится внутри(Архитектура runtime)

Это не “обёртка вокруг TBB” — pool является отдельным самодостаточным минимальным runtime (его можно использовать отдельно, как лёгкий аналог std::async, только без глобальных аренд и аллокаторов).

Как выглядит выполнение

• если у ноды есть capacity = 4, producer не создаст 5й token → блокируется

• если affinity = 2, все её tokens будут исполняться на воркере #2

• если priority = High, token помещается в hi deque → вытесняет low priority tasks

Когда это полезно

✔ Хорошо подходит для:

• статических графов (game frame, simulation step, offline pipeline)

• real-time сценариев, где нужно bounded latency

• случаев, где важна hard affinity / priority, а не “примерно так”

✖ Не подходит для:

• динамического spawn (рекурсивный fork)

• long-living серверов / task арены

• general-purpose scheduling

Как это выглядит в коде: знакомство с API
Философия "сначала опиши, потом запусти" напрямую отражена в API. Вместо того чтобы дёргать std::async по одному, мы сначала декларативно описываем весь граф задач внутри специального объекта TaskScope, а затем запускаем его на выполнение одной командой.

Давайте посмотрим на простой пример:

Есть задача A (например, загрузка модели).

Есть задача B, которая может начаться только после A (обработка модели).

Есть задача C, которая ждёт завершения и A, и B (например, отправка на рендер).

В коде это будет выглядеть так:

#include <api.hpp>

tp::Pool pool;
tp::TaskScope scope(pool);

auto a = scope.submit([] { /* … */ });
auto b = scope.then(a, [] { /* … */ });
auto c = scope.when_all({a, b}, [] { /* … */ });

scope.run_and_wait();

В TBB это был бы параллельный spawn + join, но его нельзя заранее запечатать — здесь мы явно описываем граф.

Benchmarks (Ryzen 7 6800H, MSVC 19.44)

• 20-кратное замедление на миллионе пустых задач — это не показатель производительности на реальной работе. Этот тест измеряет чистый оверхед на создание и передачу токена. Да, в моей системе он выше, потому что каждая задача проходит через более строгую систему контроля (проверка capacity, indegree и т.д.). Зато на реальных задачах, где само 'тело' функции занимает время, этот оверхед нивелируется, а выгоды от предсказуемости становятся ключевыми В сценариях с длинными цепочками зависимостей или сложной логикой ветвления TBB оказывается быстрее. Его алгоритмы work-stealing и общая архитектура лучше заточены под такие динамические графы. Мой рантайм выигрывает в другом — в предсказуемости и контроле, а не в чистой пропускной способности на сложных графах

Если вам интересен такой statically-scheduled подход — код полностью открыт, можно поэкспериментировать с графами, способами размещения и посмотреть поведение backpressure вживую.

GitHub: https://github.com/cpp20120/DagFlow