Проектируем архитектуру параллельного игрового движка

Разработка параллельной среды игрового движка (PDF)

1. Введение

С приходом на рынок многоядерных процессоров необходимость разработки игровых движков с поддержкой параллельных вычислений становится все более очевидной. Все еще возможно передавать основную нагрузку на графический процессор и использовать однопоточный движок, однако прирост производительности при использовании всех доступных в системе процессоров – как CPU, так и GPU – сулит куда более богатые возможности. Например, при использовании игрой нескольких CPU можно увеличить количество физических объектов (твердых тел), что придаст игре реалистичности, или разработать более «умный» искусственный интеллект, действия которого будут максимально приближены к человеческим.

1.1. Обзор

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

1.2. Допущения

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

2. Режим параллельного выполнения

Режим параллельного выполнения является краеугольным камнем эффективной многопоточной игровой среды. Чтобы добиться по-настоящему параллельной работы игрового движка, с минимальными затратами на синхронизацию, необходимо сделать так, чтобы каждая система работала в своем собственном режиме выполнения, как можно меньше взаимодействуя с другими системами движка. Конечно, при этом не обойтись без совместного доступа к данным. Однако, вместо того, чтобы каждая система обращалась к общим данным, например, за координатами положения или ориентации объекта, каждой системе следует предоставить свою копию данных. Это устранит взаимную зависимость разных частей движка от данных. Уведомления об изменениях, внесенных какой-либо частью в общие данные, передаются менеджеру состояний (State Manager), который помещает все изменения в очередь – это называется режимом обмена сообщениями (messaging). После того, как разные системы завершили свой очередной цикл выполнения, они обрабатывают сообщения от менеджера состояний, в соответствие с которыми обновляют свои внутренние структуры данных. Использование подобного механизма позволяет значительно сократить накладные затраты на синхронизацию, обеспечивая независимую работу систем.

2.1. Режимы выполнения

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

На Рисунке 1 показано, как разные системы работают в «свободном режиме» пошагового выполнения (free step mode), при этом необязательно, чтобы все они завершали выполнение операции за один и тот же такт. Также возможен и жесткий режим пошагового выполнения (lock step mode, см. Рисунок 2), когда выполнение всех систем завершаются за один такт.

Состояние выполнения в свободном пошаговом режиме

Рисунок 1: Состояние выполнения в свободном пошаговом режиме

2.1.1. Свободный пошаговый режим

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

Как правило, в этом режиме недостаточно послать менеджеру состояний простое уведомление об изменении состояния, - вместе с уведомлением об изменении состояния потребуется также передать данные. Это вызвано тем, что система, которая изменила общие данные, может находиться в состоянии выполнения, в то время как другая система, ожидающая эти данные, уже готова выполнить обновление. В этом случае требуется больше памяти т.к. нужно создавать больше копий данных. Поэтому «свободный» режим нельзя считать универсальным решением на все случаи жизни.

2.1.2. Жесткий пошаговый режим

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

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

Состояние выполнения в жестком пошаговом режиме

Рисунок 2: Состояние выполнения в жестком пошаговом режиме

2.2. Синхронизация данных

Вероятна ситуация, когда несколько подсистем изменяют одни и те же общие данные. Чтобы разрешить проблему конкурентных изменений обмен сообщениями должен предусматривать некий механизм, позволяющий определять приоритет изменений. Существуют два подхода:

  • Время – правильное значение хранится в подсистеме, сделавшей последнее изменение.
  • Приоритет – правильное значение принадлежит системе, имеющей наибольший приоритет. Этот механизм может сочетаться с временным механизмом (для обработки изменений, внесенных подсистемами с одинаковым приоритетом).

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

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

3. Движок

При проектировании движка основное внимание следует уделять его гибкости, обеспечивающей легкое расширение функциональности. Такой подход позволит относительно легко модифицировать движок для работы на платформах, имеющих те или иные ограничения, например, ограничения по памяти. В целом движок состоит из двух частей - оболочки и набора «менеджеров». Оболочка (раздел 3.1) содержит части игры, которые тиражируются в процессе выполнения, т.е. существуют в нескольких экземплярах. В нее также входят элементы, участвующие в выполнении основного цикла игры. Менеджеры (раздел 3.2) представляют собой одноэлементные (singleton) объекты, с которыми взаимодействует логическая часть игры.

На приводимой ниже схеме представлены части игрового движка:

Высокоуровневая архитектура движка

Рисунок 3: Высокоуровневая архитектура движка

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

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

Общее представление о такой блочной организации можно получить из Приложения А, «Пример схемы движка». Как указывалось в разделе 2 «Режим параллельного выполнения», системы, по своей сути, являются дискретными элементами. Благодаря этому они могут работать параллельно без вмешательства в работу других систем. В то же время, это порождает определенные проблемы в тех случаях, когда системам необходимо обмениваться информацией, ведь данные необязательно находятся в стабильном состоянии. Обмен информацией между системами может потребоваться по следующим двум причинам:

  • Чтобы сообщить другой системе об изменении, внесенном в общие данные (например, координаты положения или ориентации объектов),
  • Чтобы запросить некоторые функции, недоступные в рамках конкретной системы (например, система расчета ИИ обращается к системе расчета геометрии/физики для проверки пересечения лучей).

Первая проблема коммуникации между системами решается путем реализации менеджера состояний, как было описано в предыдущем разделе. Более подробно работа менеджера состояний рассматривается в разделе 3.2.2 «Менеджер состояний».

Для решения второй проблемы в системе предусматривается механизм для предоставления служб, которые могут потребоваться другой системе. Более подробное описание этого механизма содержится в разделе 3.2.3 «Менеджер служб».

3.1. Оболочка

Оболочка (внутренняя интегрированная среда) служит для объединения всех элементов движка. В оболочке происходит инициализация движка, за исключением менеджеров, экземпляры которых создаются глобально. В ней также хранится информация о сцене. Для обеспечения большей гибкости сцена реализуется в виде так называемой универсальной сцены, которая содержит универсальные объекты, представляющие собой контейнеры для соединения воедино различных функциональных частей сцены. Более подробное описание среды приводится в разделе 3.1.2.

Цикл игры также выполняется в оболочке и имеет следующий порядок:

Основной цикл игры

Рисунок 4: Основной цикл игры

На первом этапе цикла игры происходит обработка всех ожидающих сообщений окон операционной системы, так как движок, как правило, выполняется в оконной среде. Без этого движок не реагировал бы на вызовы операционной системы. На следующем этапе планировщик назначает задачи систем с помощью менеджера задач. Более подробно данный этап рассматривается в разделе 3.1.1 ниже. На последующем этапе все изменения, обработанные менеджером состояний (подробное описание в разделе 3.2.2), передаются требуемым элементам движка. На заключительном этапе интегрированная среда проверяет статус выполнения, определяя, следует ли завершить работу движка либо продолжить выполнение каких-либо операций, например, для перехода к следующей сцене. Статус выполнения движка хранится в менеджере окружения, описание которого приводится в разделе 3.2.4.

3.1.1. Планировщик

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

Планировщик передает системы на выполнение через менеджер задач за один такт генератора. В свободном пошаговом режиме (раздел 2.1.1) планировщик опрашивает системы, определяя, сколько тактовых шагов им понадобится, чтобы завершить выполнение. На основании опроса, планировщик определяет, какие системы готовы к выполнению, а какие завершат работу в конкретный шаг тактового генератора. Количество шагов может быть изменено планировщиком в том случае, если какой-либо системе требуется больше времени на выполнение. В жестком пошаговом режиме (раздел 2.1.2) все системы начинают и заканчивают исполнение в один тактовый шаг, соответственно, планировщик ожидает, когда завершится выполнение всех систем.

3.1.2. Универсальная сцена и объекты

Универсальная сцена и объекты выполняют функцию контейнеров функциональных блоков, реализованных в рамках определенных систем. Сами по себе, универсальная сцена и объекты не имеют никаких функций, кроме способности взаимодействовать с движком. Тем не менее, они должны быть достаточно гибкими, чтобы поддержать все доступные в той или иной системе функции. Таким образом, универсальная сцена и универсальные объекты не привязаны к конкретной системе, и обеспечивают свободное взаимодействие систем. Преимущество такого подхода заключается в независимости систем друг от друга, а следовательно - возможности их параллельной работы.

На приведенной ниже схеме показаны контейнеры универсальной сцены и универсального объекта:

Универсальная сцена и универсальный  объект

Рисунок 5: Универсальная сцена и универсальный объект

Принцип работы надстройки можно проиллюстрировать на следующем примере: универсальная сцена включает параметры графики, физики и других систем. Графическая часть сцены в таком случае отвечает за инициализацию дисплея и другие графические процедуры, физическая часть - за взаимодействие твердых тел, силу тяжести и т.п. Сцена содержит объекты, поэтому в универсальной сцене будет присутствовать несколько универсальных объектов. Универсальные объекты также могут быть включать параметрами графики, физики и т.п. Таким образом, графическая часть объекта будет отвечать за прорисовку объекта на экране, физическая - за взаимодействие твердого тела объекта с другими твердыми телами.

Более подробная схема взаимодействия движка с системами приводится в Приложении B - «Схема связи движка и системы».

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

Дополнительная информация о компонентах системы приводится в Разделе 5.2 «Компоненты системы».

3.2. Менеджеры

Менеджеры обеспечивают поддержку глобальных функций в рамках движка и реализуются в виде singleton-объектов, иными словами, менеджер каждого типа доступен только в одном экземпляре. Это обусловлено тем, что дублирование ресурсов менеджеров неизбежно приведет к избыточности и отрицательно скажется на производительности. Менеджеры также предоставляют общую функциональность, которая востребована всеми системами.

3.2.1. Менеджер задач

Менеджер задач отвечает за упорядочение системных задач в рамках пула потоков. В пуле потоков создается по одному потоку на процессор, чтобы обеспечить оптимальное n-кратное масштабирование и предотвратить назначение излишних потоков, исключая неоправданные издержки переключения задач в операционной системе.

Менеджер задач получает от планировщика список задач для выполнения, а также информацию о том, завершения каких задач необходимо дождаться. Планировщик, в свою очередь, получает список задач от разных систем. На каждую систему выделяется только одна главная задача - данный метод называется «функциональная декомпозиция». Однако, в рамках каждой главной задачи допускается порождать необходимое количество подзадач для обработки данных (что определяется спецификой системы), таким образом внутри системы вполне может быть реализована «декомпозиция по данным».

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

Пример пула потоков в менеджере  задач

Рисунок 6: Пример пула потоков в менеджере задач

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

Некоторые детали реализации менеджера задач можно найти в Приложении D – «Советы по реализации задач».

3.2.2. Менеджер состояний

Управление состояниями – это часть механизма обмена сообщениями, которые позволяет отслеживать внесенные системами изменения и распространять уведомления о них среди других задействованных систем. В целях сокращения числа уведомлений, системы должны быть зарегистрированы в менеджере состояний для отслеживания нужных им изменений. Данный механизм основывается на так называемой «модели наблюдателя» (observer design pattern), которая более детально рассматривается в Приложении C – «Модель наблюдателя». Вкратце, модель наблюдателя предполагает использование объекта-наблюдателя, который следит за изменениями в субъекте, при этом роль посредника между ними выполняет менеджер изменений.

Данный механизм работает следующим образом:

1) Наблюдатель регистрирует субъект, за изменениями в котором он планирует вести наблюдение, в менеджере изменений (или менеджере состояний);

2) когда субъект изменяет какое-либо из своих свойств, он направляет уведомление об изменении в менеджер изменений;

3) менеджер изменений выдает уведомление об изменении в субъекте наблюдателю по сигналу оболочки

4) наблюдатель запрашивает у субъекта фактически измененные данные.

Свободный пошаговый режим выполнения (Раздел 2.1.1) вносит в этот механизм некоторые сложности. Во-первых, вместе с уведомлением об изменении потребуется передать и данные, так как система, которая внесла изменение в общие данные, может все еще выполняться и поэтому у нее нельзя запросить итоговое значение. Во-вторых, если система еще не готова к тому, чтобы получить изменения в конце тактового шага, менеджеру состояний потребуется удерживать измененные данные до тех пор, пока все зарегистрированные для их получения системы не придут в состояние готовности.

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

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

Уведомление о внутренних изменениях UObject

Рисунок 7: Уведомление о внутренних изменениях UObject

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

3.2.3. Менеджер сервисов

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

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

Пример работы менеджера сервисов

Рисунок 8: Пример работы менеджера сервисов

Другой задачей менеджера сервисов является предоставление разным системам доступа к свойствам друг друга. Свойства – это специфичные для каждой системы значения, которые не передаются при обмене сообщениями. Например, такими свойствами является разрешение экрана в графической системе, или значение силы тяжести в физической системе. Менеджер сервисов предоставляет разным системам доступ к этим свойствам, в то же время, не позволяя непосредственно управлять ими. Он также следит за тем, чтобы все изменения свойств помещались в очередь и публиковались только в случае последовательного выполнения. Следует учитывать, что доступ к свойствам другой системы требуется достаточно редко и является исключительным случаем. Это может понадобиться, например, при открытии окна консоли, для того, чтобы включить/выключить режим каркасной сетки в графической системе, или для системы интерфейса пользователя, чтобы изменить требуемое разрешение экрана. Фактически, данная возможность используется для установки параметров, которые не изменяются от кадра к кадру.

3.2.4. Менеджер среды

Менеджер среды (окружения) обеспечивает функциональность среды выполнения движка. К числу предоставляемых менеджером среды функциональных групп относятся:

  • Переменные – имена переменных и данные, совместно используемые в масштабах всего движка. Переменные обычно задаются при загрузке сцены или определенных настроек пользователя и запрашиваются движком или различными системами.
  • Выполнение – данные о статусе выполнения, например, о завершении сцены или завершении программы. Эти параметры могут быть заданы и запрошены как движком, так и системами.

3.2.5. Менеджер платформы

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

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

Менеджер платформы также отвечает за предоставление информации о процессоре, например, о поддерживаемых SIMD-инструкциях и подобных параметрах..

4. Интерфейсы

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

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

4.1. Интерфейсы субъекта и наблюдателя

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

4.2. Интерфейсы менеджеров

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

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

4.3. Системные интерфейсы

Системам необходимы интерфейсы, чтобы оболочка получила доступ к их компонентам. Без интерфейса оболочке пришлось бы поддерживать определенную реализацию каждой новой системы, которая добавляется в движок.

В системе содержатся четыре компонента, поэтому системе необходимо реализовать четыре интерфейса: сама система, сцена, объект и задача. Данные компоненты рассматриваются в разделе 5 «Системы». Интерфейсы – это средства доступа к таким компонентам. Системный интерфейс предлагает способы создания или уничтожения сцен. Интерфейсы сцен обеспечивают способы создания и уничтожения объектов, а также способ получения «главной задачи». Интерфейс задач используется менеджером задач при постановке задач в пул потоков.

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

4.4. Интерфейсы изменений

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

5. Системы

Системы – это то, что обеспечивает игровую функциональность движка. Чтобы избавить движок от необходимости знать все типы систем, они должны реализовать интерфейсы, описанные в пункте 4.3 «Системные интерфейсы». Это существенно облегчает процесс добавления новой системы в движок.

5.1. Типы

Движок должен иметь несколько предварительно заданных типов систем, которые подходят для стандартных компонентов игры. Например, - геометрия, графика, физика (столкновение твердых тел), аудио, ввод, ИИ и анимация.

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

5.2. Компоненты системы

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

На следующей схеме показана связь между компонентами:

Связь между компонентами системы

Схема 9: Компоненты системы

Более подробная схема связи систем с движком содержится в Приложении А «Схема связи движка и систем».

5.2.1. Система

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

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

5.2.2. Сцена

Компонент «сцена», иногда называемый «системной сценой», отвечает за управление ресурсами, относящимися к текущей сцене. Универсальная сцена использует системные сцены для расширения своей функциональности, наследуя свойства, предлагаемые данной системной сценой. Примером данного компонента является физическая сцена, создающая новый мир и задающая гравитацию для мира при инициализации сцены.

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

5.2.3. Объект

Компонент «объект», также называемый «системным объектом», представляет собой объект в сцене и обычно связан с тем, что пользователь видит на экране. Универсальный объект использует системные объекты для расширения своей функциональности, таким образом, свойства объектов системы доступны в универсальном объекте.

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

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

5.2.4. Задача

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

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

Какие-либо изменения объектов записываются менеджером состояний в период обновления задачи сцены. Подробная информация о менеджере задач содержится в пункте 3.2.2.

6. Связываем все вместе

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

6.1. Инициализация

Работа движка начинается с инициализации менеджеров и оболочки.

  • Оболочка обращается к загрузчику сцен для загрузки сцены.
  • Загрузчик определяет, какие системы используются в сцене, затем обращается к менеджеру платформы для загрузки каждого из модулей.
  • Менеджер платформы загружает соответствующие модули и передает их менеджеру интерфейсов. Системный модуль возвращает загрузчику указатели на системы, которые содержат системный интерфейс.
  • Системный модуль также регистрирует в менеджере сервисов любые сервисы, которые он предлагает.

Инициализация движка и оболочки

Схема 10: Инициализация движка и оболочки

6.2. Этап загрузки сцены

Управление возвращается загрузчику, который загружает сцену.

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

Инициализация универсальной сцены и объекта

Схема 11: Инициализация универсальной сцены и объекта

6.3. Цикл игры

  • Менеджер платформ вызывается для обработки всех оконных сообщений и (или) других системных вызовов, необходимых для работы на текущей платформе.
  • Затем исполнение передается планировщику, который ждет окончания такта для продолжения работы.
  • Планировщик в свободном шаговом режиме проверяет, какие из системных задач были исполнены в предшествующем такте. Все выполненные задачи передаются менеджеру задач.
  • Затем планировщик определяет, какие задачи будут завершены в текущем такте, и ждет их завершения.
  • При жестком шаговом режиме планировщик выдает менеджеру все задачи и ждет их выполнения в каждом такте.

6.3.1. Исполнение задач

Исполнение менеджером задач.

  • Менеджер задач выстраивает очередь из направленных ему задач и начинает обрабатывать каждую задачу, по мере появления свободных потоков. (Выполнение задач специфично для каждой системы. Системы могут работать, используя только одну или несколько задач. Во втором случае используется менеджер задач, создавая, таким образом, возможность параллельного исполнения.)
  • Задачи выполняются как на всей сцене, так и на определенных объектах, изменяя внутренние структуры данных.
  • Любые данные, которые считаются общими, например, положение и ориентация должны передаваться в другие системы. Системная задача осуществляет это посредством системной сценой или системного объекта (в зависимости от того, что менялось), информируя своего наблюдателя об изменении. В данном случае наблюдатель, по сути, является менеджером изменений.
  • Менеджер изменений ставит в очередь информацию об изменении. При этом те типы изменений, в которых наблюдатель не заинтересован, просто игнорируются.
  • Если задаче требуется какие-либо сервисы, она обращается к менеджеру сервисов. Менеджер задач также может использоваться для изменения свойств другой системы, не использующей механизм сообщений (например, система ввода пользователя меняет разрешение экрана графической системы).
  • Задачи также могут обращаться к менеджеру среды для получения переменных среды, изменения состояния исполнения (например, приостановка исполнения, переход к следующей сцене и т.д.).

Менеджер задач и задачи

Схема 12: Менеджер задач и задачи

6.3.2. Распределение

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

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

6.3.3. Динамическая проверка и выход

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

7. Заключительные соображения

Ключевым моментом всего вышесказанного является раздел 2 – «Состояние параллельного исполнения». Проектирование систем для функциональной декомпозиции в сочетании с декомпозицией данных позволит добиться значительного распараллеливания, а также обеспечит масштабируемость и поддержку будущих процессоров с еще большим количеством ядер. Не забывайте использовать менеджеры состояний вместе с механизмом сообщений для синхронизации всех данных с минимальными издержками.

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

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

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

8. Информация об авторе

Джеф Эндрюз – Application Engineer Intel, занимающийся оптимизацией программного кода игрового ПО. Он также изучает различные технологии повышения производительности игр. Джф являлся ведущим архитектором демонстрационной оболочки Smoke компании Intel.

Приложение A. Схема примерного движка

Главный цикл игры начинает обработку (см. Схему 4, «Главный цикл игры»).

Схема связи движка и системы

Приложение B. Схема связи движка и системы

Схема связи движка и системы

Приложение C. Модель наблюдателя

Модель наблюдателя описана в книге “Design Patterns: Elements of Reusable Object-Oriented Software”, Эриха Гамма (Erich Gamma) и др., первоначально изданной Addison-Wesley в 1995 г.

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

Конструктивный шаблон наблюдателя

Схема 13: Конструктивный шаблон наблюдателя

Ниже приводится поток операций:

  1. Наблюдатель регистрируется в субъекте, за изменениями которого он планирует наблюдать, посредством менеджера изменений.
  2. Менеджер изменений в реальности является наблюдателем. Вместо регистрации наблюдателя в субъекте, он сам регистрируется в субъекте и ведет собственный перечень, где указывается, какой наблюдатель зарегистрирован в каком субъекте.
  3. Субъект вносит наблюдателя (на самом деле менеджер изменений) в свой список наблюдателей, которые заинтересованы в его состоянии; иногда дополнительно применяется тип изменений, который определяет, в каких именно изменениях заинтересован наблюдатель, что позволяет оптимизировать процесс распространения уведомления об изменении.
  4. Когда субъект осуществляет изменение своих данных или состояния, он уведомляет наблюдателя посредством механизма обратного вызова и передает информацию об измененных типах.
  5. Менеджер изменений выстраивает в очередь уведомления об изменениях и ждет сигнала для их распределения по объектам и системам.
  6. Во время распределения менеджер изменений обращается к реальным наблюдателям.
  7. Наблюдатели запрашивают субъект в отношении измененных данных или состояния (или получают данные из сообщений).
  8. Когда наблюдатель более не заинтересован в субъекте, он снимает свою регистрацию из субъекта посредством контроллера изменений.

Приложение D. Советы по реализации задач

Хотя распределение задач может быть реализовано различными путями, лучше всего поддерживать количество рабочих потоков равным количеству доступных логических процессоров платформы. Избегайте привязки задач к определенному потоку, поскольку задачи из различных систем не будут завершаться одновременно, что может привести к дисбалансу нагрузки между рабочими потоками, по сути, сокращая степень параллелизма. Также стоит изучить библиотеки управления задачами, например, Intel® Threading Building Blocks, что может упростить разработку.

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

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

Список схем

Схема 1: Состояние исполнения, используя свободный шаговый режим 5
Схема 2: Состояние исполнения, используя жесткий пошаговый режим 6
Схема 3: Высокоуровневая архитектура движка 8
Схема 4: Главный цикл игры 9
Схема 5: Расширение универсальной сцены и объекта 10
Схема 6: Пример пула потоков менеджера задач 11
Схема 7: Внутреннее уведомление об изменении универсального объекта 12
Схема 8: Пример менеджера сервисов 13
Схема 9: Компоненты системы 17
Схема 10: Инициализация менеджера движка и системы 19
Схема 11: Инициализация универсальной сцены и объекта 19
Схема 12: Менеджер задач и задачи 20
Схема 13: Конструктивный шаблон наблюдателя 25

Литература

Gamma, E., Helm, R., Johnson, R., Vlissides, J., (1995-2000). Design Patterns: Elements of Reusable Object-Oriented Software. USA: Addison-Wesley.

Домашняя страница Intel® Threading Building Blocks (TBB).

Для получения подробной информации о возможностях оптимизации компилятора обратитесь к нашему Уведомлению об оптимизации.