Roman Lut

Презентация заняла второе место в Intel Game Demo 2008 contest.

Лекция прочитана на конференции разработчиков компьютерных игр КРИ 2009

Конспект лекции

Сегодня я расскажу о вопросах, которые возникают при распараллеливании движка «вообще», и о том, что мы сделали в двух своих последних проектах, в частности.

Технологии в играх развиваются с огромной скоростью: сложнее алгоритмы, больше объектов. Соответственно, требуется бОльшая процессорная мощность. Но если раньше всё компенсировалось увеличением тактовой частоты процессора, то примерно 2 года назад все изменилось. Рост тактовой частоты остановился, теперь процессоры наращивают количество ядер.

Для того, чтобы использовать всю мощность современных процессоров, кроме знания классических алгоритмов, которые все мы долго учили, нужно изучать программирование под мультипроцессорные системы – а это целая отдельная область, со своими нюансами.

Я хочу обратить внимание, что сегодня уже поздно просто интересоваться этим – пора внедрять. Если кто-то не до конца проникся тем, какое мощное концептуальное изменение произошло в последние годы, я рекомендую прочитать статью Herb Shatter “Free lunch is over” – там все очень красиво философски описано.

Реально, на сегодняшний день, Core 2 Duo – это уже минимальный процессор для геймера. Поэтому игры уже просто вынуждены использовать несколько ядер, если хотят оставаться конкурентоспособными.

Когда разработчики это осознают, они задумываются, как же изменить движок, чтобы он использовал побольше ядер, и в результате выбирают определённые модели, архитектурные решения, с обзора которых я начну.

Начну с неправильного решения.

Первое, что приходит на ум программисту, который недавно узнал, что можно создавать потоки и они исполняются параллельно – это создать несколько потоков и как-то что-то в них исполнять.

Такой подход  ни к чему хорошему не приводит. Очень скоро вся программа превращается в кашу, где один поток читает данные другого непонятно когда и непонятно, что он в результате прочитает. Чтобы исправить ошибки, программист начинает вставлять критические секции везде, в результате ядра начинают ждать друг друга, и все работает даже медленнее, чем до такой «оптимизации».

Чтобы программа работала правильно, нужен четкий, понятный дизайн системы, четкие и понятные правила и протоколы взаимодействия компонентов.

Распараллеливание начинается с анализа.

Итак, имея «линейную» программу, мы должны распределить работу так, чтобы все ядра все время выполняли полезную работу, без простоев.

Очевидно, что распараллеливанию программы мешает её линейный характер исполнения – следующий блок использует данные, созданные предыдущим. Поэтому первое, о чем приходится думать при распараллеливании – это возможно ли разделить программу на относительно независимые компоненты, с минимальным, четко описанным взаимодействием.

Четко представляя компоненты системы и их взаимодействие, приступаем к выбору модели распараллеливания. На самом деле моделей, как и паттернов проектирования, не так уж и много. Я перечислю самые распространенные.

Модель 1: Независимые компоненты движка работают в разных потоках. 

Примеры удачных решений: 

Если в  игровом кадре сначала происходит обновление состояния игрового мира, а потом его рендеринг – мы можем выделить рендеринг во второй поток, и параллельно апдейтить мир под следующий кадр.

При наличии клиент-сервер архитектуры (при одиночной игре клиент и сервер работают на одной машине) – сервер в одном потоке, клиент – в другом.

Можно выделить расчёт систем частиц под следующий кадр – в отдельный поток.

Модель 2: Producer – consumer.

С сожалению, далеко не всегда цикл кадра имеет такую четкую структуру. Например, игра обходит иерархию объектов, определяет, что именно нужно рендерить, апдейтит только эти объекты и их рисует. В кадре нет четкого разделения между апдейтом и рендерингом.

В этом случае можно применять producer-consumer модель: первый поток обходит сцену, апдейтит объекты и складывает запросы на рендеринг в очередь. Параллельно, второй поток изымает из очереди задания и рисует объекты.

Апдейт и рендеринг приведены в качестве частного примера. На самом деле, система применима везде, где есть односторонне взаимодействие между блоками программы (команды направлены в одну сторону, без feedback).

Модель 3: Расщепление нити исполнения.

Если при анализе кода удается найти последовательные блоки программы, которые не зависят друг от друга, то блоки можно выполнять параллельно.

В приведенном абстрактном примере блоки 2 и 3 готовят входные данные для блока 4. Они не зависят друг от друга, и поэтому могут быть выполнены параллельно. Это так называемый Task parallel approach – в потоках выполняются разные алгоритмы.

Есть также Data parallel approach – когда в разных потоках выполняется один и тот же алгоритм, но каждый экземпляр обрабатывает разные данные. Простейший пример – обработка элементов массива. Алгоритм внутри цикла можно запустить на разных потоках, каждый экземпляр обрабатывает один элемент массива.

Плюс этого метода в том, что у нас сохраняется примерно линейное исполнение программы, и при желании мы даже можем исполнить все линейно в одном потоке, если это нужно для отладки.

Этот подход также позволяет постепенно оптимизировать участки кода, не ломая всю архитектуру приложения.

С другой стороны, мы имеем слишком много простоев, потому после расщепления и выполнения, мы должны синхронизировать завершение задач, чтобы продолжить линейное исполнение. Естественно, одна из задач будет выполняться дольше, чем другие, поэтому остальные ядра будут простаивать.

На самом деле, указанный подход – это лишь способ немного оптимизировать существующий код, но он никогда не даст 100% загрузки ядер. Дело в самой концепции. Но, если проанализировать минусы этой  модели, мы приходим к совершенной архитектуре: Граф  зависимости задач.

Модель 4: Task dependency graph

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

Рисунок следует понимать так: прежде чем мы можем выполнить блок 1, мы должны выполнить блоки 2, 3 и 4, потому что они готовят необходимые данные. Прежде чем мы можем выполнить блок 2, мы должны выполнить блоки 5 и 6, и т.д.

В чем преимущество такой системы? В том, что теперь мы знаем, какие блоки можно выполнять параллельно. Например,  в начале исполнения мы знаем, что можем стартовать выполнение блоков 6, 8, 9, и 10 на всех доступных ядрах.

При достаточно мелком разбиении, загрузка ядер и масштабируемость стремятся к 100%.

Эта система даст максимальную производительность, и у нее всего один недостаток: сложность реализации и поддержки. Для того, чтобы построить такой движок, нужно мыслить понятиями «Функциональным блок» и «Зависимость» с самого начала. Если разработка движка уже начата, переход на такую архитектуру практически обозначает переписывание с нуля.

Кроме того,  такую программу чрезвычайно сложно отлаживать. Скажем, в текущем кадре блок А был исполнен в первом потоке, перед независимыми блоками Б и В, а в следующем кадре он будет исполнен в другом потоке после блоков Б и В, из-за того, что выполнения задач сдвинулось по времени. Искать баги будет очень  сложно.

Мне известны всего две игры, использующие такую архитектуру: Lost Planet и Kill Zone 2. По обоим играм есть отдельные лекции, ссылки будут на последнем кадре.

Теперь о реализации Task Dependency graphs.

Во всех перечисленных методиках используется понятие «Запускаем задачу во втором потоке». Наивный программист попробует создать поток. Для справки: создание и удаление потоков – очень длительная операция. От момента создания до момента выполнения может пройти 100мс, в то время как кадр игры – это 33 мс.

Для эффективной реализации указанных методов требуется библиотека более высокого уровня, которая создает потоки заранее и самостоятельно распределяет на них задачи.

Для реализации метода расщепления нити исполнения вполне подойдет OpenMP. С помощью OpenMP можно реализовывать Data-parallel и Task-parallel секции. Но в OpenMP нет возможности отслеживать зависимости между задачами, и нет понятия «задача» вообще.

Сейчас я немного пропиарю библиотеку Intel Threading Building Blocks. Во-первых, я крайне не рекомендую пытаться писать такую библиотеку самостоятельно. Для того, чтобы реализовать все грамотно и без ошибок, нужен специальный опыт и масса времени. Я сомневаюсь, что один человек сможет завершить аналог  хотя бы за полгода. Тем более, что Intel распространяет библиотеку бесплатно.

Библиотека объекто-ориентированная. Для пользователя, библиотека выглядит очень просто. Мы наследуем класс от базового класса tbb::task и переопределяем метод run(). После этого мы может добавлять наш класс в очередь исполнения, и библиотека исполнит его на доступном потоке. Можно спавнить новые задачи в методе run() и ожидать их завершения, то есть практически, динамически строить граф зависимостей.

Вернемся на предыдущий слайд: как будет выглядеть реализация Task Dependency Graph под Intel TBB.

Block1 – это, грубо говоря, финальная задача, скажем, задача «вывести кадр на экран. Мы спавним эту задачу, она начинает выполняться. Задача знает, что чтобы вывести экран, нужно проапдейтить мир, рассчитать скелетную анимацию и отрендерить  мир. Задача в своем методе Run() спавнит три задачи  методом task::spawnChild() и ожидает их исполнения. Задача «Проапдейтить мир», в свою очередь, спавнит 100 задач «проапдейтить объект» и т.д.

Причем когда мы вызываем task::waitforall(), то, на самом деле, никакого простоя не происходит. Библиотека, внутри метода waitforall(), не простаивает, а вынимает зависимые задачи из очереди и выполняет их вместе с остальными потоками.

Библиотека написана оптимально, использует lockless алгоритмы, оптимизирована под кеш и доступна для PC и XBOX 360.

Задачи могут быть очень мелкими – меньше миллисекунды и меньше.

После обзора, вернемся к нашим баранам – какая ситуация была у нас в Deep Shadows.

Если бы у меня была масса времени, и я мог программировать  в свое удовольствие, я бы конечно начал писать все с нуля и реализовал Task Dependency Graph. К сожалению, в реальности всякие milestones мешают получать удовольствие от работы, и начинать глобальную переделку «движка» за полгода до релиза означает завал проекта. Поэтому сделать Task Dependency Graph пока так и остается в мечтах.

С другой стороны, нас никто и не заставляет делать все идеально. У нас есть конкретная задача: обеспечить 30FPS на target hardware.

Поэтому в самого начала я уже рассчитывал использовать Producer-consumer и расщепление нити исполнения.

У нас сложилась следующая ситуация. Игра показывала примерно 20-23 FPS. Мы оптимизировали «движок» как только можно: алгоритмы, batching, SSE, prefetch, но добиться повышения FPS до 30 никак не удавалось. В игровом мире просто очень много объектов и деталей, и всех их нужно обрабатывать. Ситуация, когда нет чего-то такого, что тормозит, но в целом – все медленно.

Вот распределение времени кадра.

Вот так выглядела игра под Vtune. Vital.dll и game.dll – это апдейт мира. VERender2 – это обход сцены. DX9render и ShaderLib – наша графическая библиотека, надстройка над DirectX 9. Здесь заметно, что игра уже настолько оптимизирована, что ускорив, скажем обход сцены на 20% (а это не так уж и просто), мы получим повышение FPS всего на 2-3%, а нам нужно 150%.

Так мы пришли к выводу, что без распараллеливания мы результата не добьемся. Нужно что-то вытеснять во второй поток.

Что же именно?

Тут видно, что DirectX и Driver занимают очень много времени, и оптимизировать их у нас нет никакой возможности – мы и так сократили количество drawcalls, как могли.

Вот и решение: графическая библиотека – отличный кандидат для модели Producer-consumer. Поток данных идет в одну сторону. У нас было несколько вызовов GetViewPort(), GetWorldMatrix(), но мы от них избавились. Можно было вытеснять только DirectX API, но мы вывести во второй поток всю нашу графическую библиотеку, линия раздела – API нашей библиотеки.

Работает всё следующим образом.

Обход сцены, вместо вызова методов API графической библиотеки записывает команды в циклический буфер. Второй поток параллельно изымает команды и исполняет их.

Результат: 60% зелёной линии вытеснено во второй поток. Рендеринг происходит параллельно с апдейтом мира. Точка синхронизации находится перед проверкой состояния кешей игры (ждём окончания рендеринга).

Вот как это выглядит под Vtune: DirectX, driver и наша графическая библиотека работают во втором потоке.

Результат: повышение FPS на >150% !

Благодаря такой простой системе, параллельный рендеринг работал уже через 2 недели, и делал его один человек. В течении следующих трёх месяцев мы периодически вылавливали забытые баги. 

Примерно пару месяцев назад в одном программистоском блоге я натктулся на лекцию программиста из Emergent Technologies. В свой лекции он описывает, как они внедряли параллельный рендеринг в GameBrio.

Они тоже стремились всё сделать с минимальными изменениями кода. За линию раздела был выбран Direct3DDevice интерфейс. 

Буквально, вместо указателя на устройство, “движку” подсовывается указатель на свой класс, который складывает все методы в Ring Buffer. Я очень рекомендую посмотреть эту лекцию, т.к.  Они сделали библиотеку open source. Это, может быть, наиболее простой способ внедрить параллельный рендеринг в “движок”. Там есть некоторые нюансы, связанные с созданием вершинных буферов, с последующим локом, но, в принципе, всё достаточно просто.

Future work.

На данный момент, загружено только 2 ядра.

DirectX 9 и 10 являются однопоточными API, и поэтому там уже особо ничего не улучшить. Что мы реально можем сделать – это писать несколько очередей, обрабатывая игровые объекты параллельно. Полученные очереди должны присоединяться в основной Ring buffer.

Тут, кстати, очень удобно использовать ITBB.

В DirectX 11 наконец-то появятся т.н. Defferred contexts – объекты с интерфейсом IDirect3DDevice, которые не рендерят, а записывают вызовы. Полученную очередь можно выполнить на основном устройстве.

Кстати, на XBOX 360 это есть уже сегодня.

Ссылки