Игровой планировщик задач своими руками

В первый раз на demo party я попал в 2008 году, на Evoke в Германии. Я тогда говорил о многоядерной оптимизации в играх и использовании Intel® Threading Building Blocks (Intel® TBB) для эффективного распределения работы между потоками. Тогда же возник вопрос: могу ли я уместиться в 64КБ? Правила просты: 65536 байт максимум, один единственный исполняемый файл. Но результаты часто бывают ошеломительны. Intel® TBB – это элегантная худенькая библиотека, но здесь её 200КБ не проходят. Я не остановился и начал рассматривать идею уменьшенной модели Intel® Threading Building Blocks. Это должен был быть минимальный планировщик задач, нечто такое, что легко изучать, разбирать на части и вообще играться. Я почувствовал свою миссию!

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


Планирование задач

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

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

С точки зрения программирования в системе с n логическими ядрами, Nulstein создаёт n-1 рабочих потоков, которые помогают основному потоку игры выполнять задачи. Каждый рабочий поток имеет свою собственную «кучу работы» - список задач, готовых к запуску. Каждый раз, когда одна задача завершается, поток берёт следующую с самого верха кучи. Таким же образом при создании задача кладётся на вершину кучи. Это гораздо более эффективно, чем одна глобальная очередь задач, поскольку так каждый поток работает независимо, без всяких спорных моментов. Но тут есть один тонкий момент: некоторые кучи могут кончаться гораздо быстрее, чем остальные. В этом случае планировщик похищает нижнюю половину кучи занятого потока и передаёт её свободному. Такой метод значительно ограничивает количество спорных моментов, поскольку только два потока затрагиваются блокировкой обоюдного исключения, которая нужна для выполнения данной операции.


Задачи и пул задач



Код планировщика задач содержится в файлах TaskScheduler.h/.inl/.cpp (заголовки, инлайны и код). CTaskPool, в основном, является собранием CWorkerThread, в котором помещается вся логика. CInternalTask – это абстрактный суперкласс всех задач: в реализации ParallelFor и CSorter используются подклассы этого класса.

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

CSorter реализует простую параллельную сортировку, запуская новые задачи для блоков размером больше некоторого заданного порогового значения. Хотя моей целью было уменьшить размер кода, сортировщик был сделан на шаблоне C++, чтобы избежать издержек при вызове функции каждый раз, когда нужно сравнить два элемента.

Здесь есть очень удобный момент: код, использующий эти функции, всё ещё может восприниматься как последовательный. Код до и после команды ParallelFor выполняется так, как написано.

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

{
    CTaskCompletion Flag;
    CMyTask* pTask;
	
    pTask = new CMyTask(&Flag,…);
    pThread->PushTask(pTask);
    …
    pThread->WorkUntilDone(&Flag);
}

Отдельная задача реализуется с помощью CMyTaskи для отслеживания её завершения используется Flag. (Отметим, что pThread должен быть текущим потоком). После вызова PushTask эта задача может либо выполняться планировщиком, либо может быть похищена другим потоком. Текущий поток может продолжать выполнять другую работу, включая создание дополнительных задач, пока он не вызовет WorkUntilDone. Эта функция запускает задачу из очереди потока или пытается похитить её у другого потока, пока не будет выставлен флаг завершения. Опять же это выглядит так, как если бы задача выполнялась последовательно как часть вызова (что иногда и бывает).

{
     CMyTask* pTask;
	
     pTask = new CMyTask(pThread->m_pCurrentCompletion,…);
     pThread->PushTask(pTask);
}

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

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


Устройство планировщика

LЕсли мы посмотрим, что происходит внутри, то увидим, что CTaskPool является центральным объектом. Он создаёт и удерживает рабочие потоки. Сначала они блокированы и ожидают семафора, а планировщик находится в состоянии ожидания и не загружает процессор. Как только возникает первая задача, она разделяется между всеми потоками (если возможно) и семафор открывается одним шагом с помощью worker_count, пробуждая все потоки как можно быстрее. Пул наблюдает за флагом завершения этой корневой задачи, а рабочие потоки продолжают работу, пока флаг не будет установлен. После завершения все потоки снова засыпают, и ещё один семафор используется для гарантии того, что все потоки засыпают перед принятием новой задачи. Концептуально это означает, что все потоки всегда находятся в одном и том же состоянии: либо все работают, либо все спят.

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

Обработка – threadproc управляет вышеупомянутыми семафорами и в активном состоянии периодически вызывает DoWork(NULL). Этот метод берёт задачу из кучи, пока та не опустеет, когда это происходит, он пытается похищать задачи у других потоков и возвращает контроль в случае, если не может найти ни одной. DoWork также может вызываться из WorkUntilDone, если некоторая задача должна ожидать окончания другой, прежде чем продолжаться. В этом случае ожидаемый флаг завершения передаётся в качестве параметра и DoWork возвращается, как только флаг будет установлен.

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

Похищение – StealTasks управляет похищением задач. Эта функция просматривает все рабочие потоки, проверяя, не хочет ли какой из них сделать GiveUpSomeWork. Если в очереди потока находится только одна задача, то он попытается разделить её на две и передать одну «половину» незагруженному потоку. Если задача не делится или если задач больше одной, то он возвращает половину всех задач (округляя количество). Тот факт, что рабочие потоки обращаются к StealTasks в случае, если их очереди пустеют, позволяет им снова начинать работу, как только появляется очередная задача. Это особенно важно в контексте игры, где задержка становится более критичной, чем пропускная способность.

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


Параллельный цикл игры


Рис. 2: Традиционный цикл обработки фрейма разделяется на большее количество частей

Традиционно фрейм разделяют на две фазы: обновление во времени и рисование картинки. В Nulstein эти фазы были еще дополнительно разделены, чтобы получить дополнительный параллелизм.

Фаза обновления разбивается на две. Первая – предобновление, в которой каждый объект имеет возможность читать статус всех остальных, но не может менять свой официальный статус. Это позволяет каждому объекту принимать решения на основе состояния как в «предыдущем фрейме». Во второй фазе объекты применяют принятые решения, что и является реальным обновлением. Правило второй фазы таково: объект может менять свой статус, но не должен обращаться к другим объектам. Это позволяет обеим этим фазам работать в простом режиме ParallelFor и их просто реализовать, кроме случаев возникновения каких-нибудь жёстких зависимостей между объектами, при которых нельзя использовать состояние предыдущего фрейма. Классический пример – камера, установленная на машину: вид с камеры не должен переходить внутрь машины и нужно знать точную позицию и ориентацию машины перед обновлением вида камеры. В таких случаях объект может объявить себя зависимой от другого объекта (или нескольких объектов) и обновляться только после их обновления. И, когда известно, что они уже закончили своё обновление, зависимый объект может спокойно читать их обновлённый статус. Именно таким образом в моей демке реализуется то, что маленькие кубики остаются плотно прижатыми к углам больших кубов.


Рис. 3: Экран приложения Nulstein.

Фаза рисования делится на три фазы. При рисовании каждый объект должен указать элементы, которые нуждаются в рендеринге, и добавляет их в список отображения. Список имеет 64-битный ключ, в котором закодирован ID и другие данные, такие как z-order, alpha-blending, материал и т.д. Это делается с помощью команды ParallelFor, при этом каждый поток добавляет данные в независимые блоки массива. В этой фазе такие вещи, как отсечение невидимого (visibility culling) и заполнение динамических буферов, могут проходить параллельно. После того, как каждый объект объявит о том, что конкретно он желает нарисовать, массив подвергается сортировке, которая тоже может проходить параллельно (хотя здесь при количестве объектов порядка тысячи это не сильно влияет). Наконец, происходит рендеринг сцены, и каждый элемент отсортированного списка вызывает своего родителя, который и выполняет реальный вызов рисования.

Рис. 4: Intel® Thread Profiler - работа приложения с включенным и выключенным профилировщиком

На рис. 4 приведены два фрагмента экрана Intel® Thread Profiler, отображающие работу окончательной версии программы на процессоре Intel® Core™ i7 3.2GHz в одинаковом масштабе с включённым и выключенным планировщиком задач. Выигрыш от использования планировщика, тем не менее, очевиден: работа показана зелёным цветом, последовательное выполнение вверху, параллельное выполнение внизу. Фаза, выполняющаяся последовательно – это фаза рендеринга, которая проходит в основном в DirectX и графическом драйвере, а серая линия отображает время, затраченное на ожидание vblank.

На рис. 5 показана работа демки в режиме профилирования с оснасткой, реальная работа показана как непрерывные секции. Это изображение даёт нам представление, как задачи распределяются по потокам.


Рис. 5: Распределение задач по потокам

Итоговый исполняемый файл нашего проекта имеет размер менее 40КБ, а если использовать пакованный ехе, например, с помощью kkrunchy от Farbrausch, то размер становится 16КБ. Таким образом, если вы сегодня спросите меня, могу ли я использовать планировщик задач в пределах 64К, то я определённо скажу «да»! В дополнение к данному достижению, скажу, что я верю, мы должны экспериментировать с вещами, чтобы действительно их понять, я надеюсь, что данный проект сможет стать интересной игрушкой для людей, интересующихся параллельным программированием.

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


Библиография

Reinders, James. Intel Threading Building Blocks. USA: O'Reilly Media, Inc., 2007.

Pietrek, Matt. Remove Fatty Deposits From Your Applications Using Our 32-Bit Liposuction Tools. Microsoft Systems Journal, October 1996 issue.

Ericson Christer. Order your graphics draw calls around! http://realtimecollisiondetection.net/blog/?p=86


Об авторе

Джером Муффат-Меридол (Jérôme Muffat-Méridol) на протяжении последних 20 лет занимается созданием программ, и в особенности графическими приложениями. Перед переходом в Интел он написал deepViewer – браузер фотографий, построенный на очень прогрессивном интерфейсе point & zoom, где он применил свои навыки, полученные за 10 лет разработок видеоигр: перед этим он был техническим директором в Bits Studios – студии в Лондоне, специализирующейся на консольных играх.

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