Разработан программный модуль диспетчера, распределяющего задачи, связанные с формированием изображения при помощи технологии OpenGL, по нескольким потокам выполнения. Разработанный диспетчер использует новый алгоритм распределения задач по потокам, основанный на сочетании двух существующих методов. Для описания зависимостей между задачами по данным используется граф выполнения. Разработанный модуль предназначен для использования в системе визуализации авиатренажёра.
Ключевые слова: диспетчер задач, параллельное программирование, технология OpenGL, система визуализации, авиатренажёр, граф выполнения
В настоящее время активно развивается как военная, так и гражданская авиационная промышленность. В связи с этим, возникает всё большая потребность в высокотехнологичных тренажёрах для обучения пилотов. Авиатренажёры должны позволять обучать пилотов в условиях, приближенных к реальным. Одним из основных критериев реалистичности является качество симуляции внекабинного пространства. Для достижения реалистичного изображения применяются современные средства трёхмерной компьютерной графики. В авиатренажёрах необходимо обеспечивать высокую плавность восприятия движения, для чего требуется отображать изменения обстановки в реальном времени, формируя при этом реалистичное изображение не менее 60-ти раз в секунду.
Каждый кадр формируется в результате выполнения порядка ста различных задач. Некоторые их этих задач можно выполнять одновременно, а другие — нельзя, так как между ними существуют зависимости по данным. Время выполнения задач варьируется от порядка ста микросекунд до нескольких миллисекунд, при этом, в зависимости от условий симулируемого виртуального мира, выполнение одной и той же задачи может занимать различное время.
OpenGL (англ. OpenGraphicsLibrary) — спецификация, определяющая независимый от языка программирования, платформо-независимый программный интерфейс для написания приложений, использующих двумерную и трёхмерную компьютерную графику. Программный интерфейс обеспечивает взаимодействие с графическим процессором для достижения аппаратного ускорения визуализации [1].
Использование в системе визуализации технологии OpenGL накладывает на выполнение некоторых задач дополнительное ограничение: все задачи, использующие функции OpenGL, необходимо запускать в одном потоке выполнения, так как контекст OpenGL «привязан» к программному потоку [1].
Система визуализации авиатренажёра использует высокопроизводительные ПК, укомплектованные многоядерными процессорами. В связи с этим, возможно параллельное выполнение нескольких задач на нескольких программных потоках выполнения. В результате параллелизации исполнения задач может быть достигнуто существенное увеличение производительности системы визуализации. Ввиду выше описанных ограничений на параллельное исполнение некоторых задач, необходимо использование метода распределения задач по потокам выполнения, учитывающего все зависимости по данным между задачами, а также выполняющего задачи формирования изображения (с использованием OpenGL) на одном потоке.
В результате исследования было выявлено, что существует два основных метода распределения задач по потокам: метод функциональной декомпозиции и граф выполнения [2, 3].
В основе метода функциональной декомпозиции лежит деление множества всех задач на несколько видов по сходности их функционала [4]. Такое разделение проводится, так как между смежными по функционалу задачами, зачастую, существует большое количество зависимостей по данным, и их параллельное выполнение может привести к большому числу потенциальных конфликтов. Для каждого вида выделяется поток выполнения, на котором выполняются задачи этого вида.
Необходимо отметить, что между задачами разных видов также существуют зависимости, например, обработать источники освещения и геометрические объекты, принадлежащие городу, можно только после завершения их загрузки, а задачи, использующий OpenGL для формирования изображения, должны ожидать готовности данных, подготавливаемых задачами других видов. Таким образом, для удовлетворения зависимостей некоторых задач необходимо производить блокирующее ожидание (то есть простой) в текущем потоке.
Преимуществом данного метода является то, что разработчику всегда известно, в каком порядке и на каком потоке будут выполняться задачи, что может упростить отладку. К основным недостаткам метода относится снижение КПД использования вычислительных ресурсов при изменении условий виртуального мира и высокая сложность ручного распределения задач по потокам на этапе разработки.
Граф выполнения — специальная структура данных, связывающая задачи и зависимости между ними. Узлы графа представляют задачи и промежуточные данные, а направленные рёбра — зависимости между задачами и данными [5].
Граф выполнения строится разработчиком системы и подаётся на вход диспетчеру задач, который на основе него обеспечивает выполнение всех задач на рабочих потоках. Задачи, готовые к выполнению помещаются в очередь, из которой они передаются на выполнение в свободные рабочие потоки. Особенностью этого метода является требование к равноправности всех задач: диспетчер может запустить любую задачу на любом потоке.
К главным достоинствам метода относится адаптивное распределение нагрузки по вычислительным потокам, отсутствие блокирующего ожиданиязависимостей задач и простота добавления задачи для разработчика. Недостатком является отсутствие возможности выполнения задач, использующих OpenGL на одном потоке.
Сравнение существующих, а также гибридного (разработанного), методов представлено в таблице 1.
Таблица 1
Сравнение методов распределения задач
|
Критерий оценки |
Функциональная декомпозиция |
Граф выполнения |
Гибридный метод |
|
Масштабируемость |
Нет |
Есть |
Есть |
|
Равномерное использование ресурсов |
Нет |
Да |
Да |
|
Разработчику известен поток выполнения каждой задачи |
Да |
Нет |
Только для задач формирования изображения |
|
Адаптивный порядок выполнения задач |
Нет |
Да |
Да |
|
Отдельный поток для OpenGL |
Есть |
Нет |
Есть |
|
Блокирующее ожидания результатов других задач |
Есть |
Нет |
Нет |
В результате анализа существующих методов решения было установлено, что необходимо разработать новый, гибридный, метод распределения задач, объединяющий преимущества существующих методов и учитывающий особенности работы с технологией OpenGL.
За основу был взят граф выполнения, так как он обладает большим количеством достоинств и имеет ряд преимуществ по производительности и масштабируемости. Основным недостатком графа выполнения является однородность задач, из-за которой невозможно организовать выполнение задач, использующих функции OpenGL, в одном потоке. Для решения данной проблемы был использован метод функциональной декомпозиции.
Выделяется два вида задач: вычислительные задачи и задачи формирования изображения (с использованием графического процессора и технологии OpenGL). При помощи такого разделения, диспетчер может определить вид задачи и выполнить её в верном потоке. Пример разработанного гибридного графа выполнения представлен на рисунке 1.
Рис. 1. Пример гибридного графа выполнения. Двойными окружностями обозначены задачи, формирующие изображение при помощи технологии OpenGL
Диспетчер задач создаёт заданное количество потоков выполнения, затем выделяет один из них для задач формирования изображения. При готовности к выполнению каждой задачи, диспетчер получает её вид и организует её выполнение либо на одном из вычислительных потоков, либо на потоке формирования изображения.
Главной особенностью использования графа выполнения является возможность ожидания всех зависимостей задачи без использования блокирующей синхронизации. За счёт этого, избегается простой рабочих потоков. Для обеспечения адаптивной и равномерной загрузки рабочих потоков применяются очереди задач. Для вычислительных потоков используется общая очередь вычислительных задач, а для потока формирования изображения — отдельная очередь с задачами, использующими OpenGL.
Исполнение задач графа выполнения начинается с входной задачи (так называемой «точки входа»), не имеющей зависимостей. Результатом её выполнения является удовлетворение зависимостей некоторых других задач и их готовность к выполнению. Как только все зависимости задачи оказываются удовлетворёнными, она обрабатывается диспетчером, который получает её вид и, в зависимости от него, помещает её либо в очередь вычислительных задач, либо в очередь задач формирования изображения. Исполнение графа завершается после выполнения последней задачи, от которой не зависит ни одна другая задача («точка выхода»).
Непосредственное выполнение задач производится в функции рабочего потока. Каждый поток находится в цикле, из которого он выходит только после выставления флага конца работы диспетчера. В теле цикла происходит извлечение задачи из очереди, соответствующей типу потока, и её выполнение. Если в результате выполнения очередной задачи оказываются полностью удовлетворёнными все зависимости некоторой другой задачи, то готовая задача помещается в очередь, соответствующую её типу.
Отдельный интерес представляет выбор реализации очередей задач. К обоим используемым очередям производится одновременное обращение из нескольких потоков. В связи с этим, необходимо наличие механизма синхронизации доступа к ним [6]. Самый простой и распространённый вариант синхронизации — использование критических секций, например, мьютексов. Такая реализация имеет серьёзные недостатки по производительности, так как блокирует выполнение рабочего потока до получения доступа в критическую секцию. Для избежания блокировки можно использовать неблокирующий (lock-free) алгоритм синхронизации. Существует множество реализаций потокобезопасных очередей, рассчитанных на различное количество одновременно обращающихся потоков, использующих неблокирующую синхронизацию, чаще всего, на основе атомарных переменных.
В результате использования описанного метода распределения задач по потокам достигается:
– масштабируемость системы визуализации при изменении количества рабочих потоков;
– адаптивное распределение вычислительной нагрузки по потокам в зависимости от конкретных условий симулируемого мира;
– удовлетворение требований стандарта OpenGL;
– удобство добавления задачи для разработчика;
– отсутствие блокирующей синхронизации в рабочих потоках.
На основе гибридного метода была разработана реализация диспетчера задач системы визуализации. Результаты тестирования его производительности при помощи профилировочных инструментов, таких как IntelVTuneAmplifier [7], подтвердили все преимущества данного метода. Так как система визуализации авиатренажёра во многом схожа с другими системами симуляции виртуального мира, разработанный метод может быть применён в любых системах, использующих технологию OpenGL, таких как компьютерные игры и системы дополненной реальности.
Литература:
- OpenGLAPIDocumentation [Электронный ресурс]. URL: https://www.opengl.org/documentation/ (дата обращения: 18.03.2016).
- Gregory, J. Game Engine Architecture [Текст] / Jason Gregory. — 2nd ed. — Boca Raton, FL: CRC Press, 2014. — 1052 p.
- Andrews, J. Designing the Framework of a Parallel Game Engine [Электронный ресурс] / Jeffrey Andrews. Intel Developer Zone, 2009–2015. URL: https://software.intel.com/en-us/articles/designing-the-framework-of-a-parallel-game-engine (дата обращения: 15.02.2016).
- Богачёв, К. Ю. Основы параллельного программирования [Текст] / К. Ю. Богачёв. — М.: БИНОМ. Лаборатория знаний, 2003. — 342 с.
- Parallelizing Data Flow and Dependence Graphs [Электронный ресурс]. Intel Developer Zone. URL: https://software.intel.com/en-us/node/517340 (дата обращения: 20.03.2016).
- Herlihy, M., Shavit, N. The Art of Multiprocessor Programming [Текст] / Maurice Herlihy, Nir Shavit. — Revised reprint, 1st ed. — San Francisco, CA: Morgan Kaufmann, 2012. — 536 p.
- Intel VTune Amplifier Performance Profiler [Электронныйресурс]. URL: https://software.intel.com/en-us/intel-vtune-amplifier-xe (дата обращения: 20.05.2016).
