Аннотация
Койбаш А. А., Кривошеев С. В. Подсистема прогнозирования траектории движения подвижного объекта распределенного симулятора тяжелой инженерной техники. Выполнен анализ алгоритма поиска кратчайшего пути А* для подвижных объектов, исследована оптимизация вычисления пути при помощи средств управления потоками. Проведен сравнительный анализ работы алгоритма на одном и нескольких ядрах.
Ключевые слова: прогнозирование поведения объекта, поиск кратчайшего пути, многопоточность.
Введение
Развитие информационных технологий неизбежно приводит к внедрению новейших разработок во многие сферы жизни. Значительную роль в открытии инновационных технологий играет моделирование. Одним из важнейших аспектов моделирования является предсказание поведения объекта. Прогнозирование поведения объекта позволяет предсказывать его дальнейшие действия и соответствующим образом корректировать линию поведения (например, маршрут движения). Для этого используется множество факторов, такие как вероятность определенного действия объекта, возможность выполнения какого-либо действия, а также характеристики действий и самого объекта. Точность любого прогноза обусловлена объемом верифицированных данных, а также свойствами системы. Таким образом, компьютерная модель объекта должна обладать достаточным набором параметров, чтобы иметь возможность сообщить, как и каким способом может быть выполнено следующее действие. Есть множество способов описать схему поведения, и наиболее оптимальным является описание при помощи графов.
Просчет кратчайшего маршрута
Для решения графов существует множество различных методов. В случае просчета оптимального пути, поле перемещения объекта с максимально допустимой детализацией представляется в виде мультиграфа, где расстояние является весом ребра. Объект может перемещаться по вертикали, горизонтали и диагонали. Поле перемещения объекта с просчетом пути из точки A в точку B представлено на рис. 1.
Рисунок 1 – Поле перемещения объекта с просчетом пути
Наиболее рациональным методом для просчета оптимального пути тяжелой техники является алгоритм А*, который представляет собой эвристический подход к алгоритму Дейкстры. Данный алгоритм использует оценочную стоимость. Просчитываются все 8 соседних вершин рядом с текущей позицией и в качестве следующей текущей выбирается вершина с минимальной стоимостью. В качестве эвристического приближения используется расстояние Чебышева. Преимущество данного алгоритма в том, что в нём пошагово просматриваются все пути, ведущие из вершины A в вершину B, пока не найдется путь с минимальной стоимостью. При этом алгоритм А* обходит минимальное количество вершин, поскольку он эффективно использует эвристику [1].
Оптимизация вычислений
Из рисунка видно, что при вычислении просчитываются параметры для всех соседних клеток текущей позиции. Такие вычисления являются очень ресурсоёмкими. В связи с этим вопрос об оптимальном программировании вычисления поведения является крайне актуальным, так как оптимальность играет очень важную роль – во времени и энергопотреблении.
Существенной производительности можно добиться путём распараллеливания программы. В алгоритме есть циклы, которые целесообразно распределить по потокам [2]. Если операционная система поддерживает концепции потоков в рамках одного процесса, она называется многопоточной. Схема организации однопоточного и многопоточного процесса изображена на рис. 2.
Рисунок 2 – Диаграмма конкуренции 2 потоков разных маршрутов
Как видно из схемы, однопоточный процесс использует код, данные в основной памяти и файлы, с которыми он работает. Процесс также использует определенные значения регистров и стек, на котором исполняются его процедуры.
Многопоточный процесс организован несколько сложнее. Он имеет несколько параллельных потоков, для каждого из которых ОС создает свой стек и хранит свои собственные значения регистров. Потоки работают в общей основной памяти и используют то же адресное пространство, что и процесс-родитель, а также разделяют код процесса и файлы [3].
Многопоточные приложения имеют ряд преимуществ:
– улучшенная реакция приложения;
– более эффективное использование мультипроцессирования;
– улучшенная структура программы;
– эффективное использование ресурсов системы.
Одним из решений является распределение двойного цикла обхода соседних вершин на 8 потоков – по одному на каждую вершину. Обработка соседних вершин аналогична алгоритму для одного потока. При нахождении соседней вершины вызывается завершение потоковой процедуры и строится траектория. Это очень удобно, так как система сама управляет потоками и распределит ядра для их выполнения. Платформа .NET предоставляет ряд функций для работы и синхронизации многопоточных приложений, поэтому для реализации использован язык C#. Чтобы избежать гонок памяти, при которых разные потоки одновременно начнут редактировать один участок памяти, проведена синхронизация при помощи мьютексов [4]. Таким образом, выполняется синхронизация доступа к спискам, что позволит избежать задействования одной и той же переменной несколькими потоками.
Для сравнения быстродействия необходимо зафиксировать время вызова программного модуля, дождаться обработки и зафиксировать время окончания выполнения. Для этого были внесены изменения в код программы. Также для фиксации результатов был написан внешний сценарий вызова программы, который фиксирует время начала и время завершения работы программы. Тестирование проводится на двух разных процессорах, время выполнения считается как разница между временем запуска и временем завершения программы.
Тест показал, что распределение модуля на 8 потоков показало ухудшение производительности по сравнению с однопоточной реализацией. Падение производительности связано с тем, что все потоки обращаются и обрабатывают одни и те же переменные. Каждый поток при обработке общего участка памяти вынужден ожидать в очереди, если этот участок уже обрабатывается другим потоком, что негативно влияет на скорость выполнения программы [5].
Для формирования статистики средствами Micrisoft Visual Studio 2013 произведено профилирование конкуренции за ресурсы при параллельной обработке. Результат представлен на рис. 3.
Рисунок 3 – Диаграмма конкуренции 8 потоков
На диаграмме конкуренции изображена интенсивность конкуренции в секунду, отложенную по оси времени. На ней отображены конфликты ресурсов. Из изображения следует, что частота конкуренции крайне высока – 33 состязания.
Алгоритм программы перестроен для двух потоков, первый обрабатывает 1 – 4 вершины, второй 5 – 8 вершины. Координаты остались теми же. Доступ к редактированию открытого списка также синхронизируется. При коротком маршруте тестирование обеих реализаций дало одинаковое время выполнения. Для полноценного теста было разработано поле с множеством препятствий и альтернативными способами добраться до цели. Это должно осложнить работу алгоритма, заставив его обрабатывать большее количество вершин. Тестирование на разных процессорах показали более чем двукратное падение производительности. Причина также в конкуренции ресурсов – потоки ожидают разрешение на обработку переменных. Результат представлен на рис. 4.
Рисунок 4 – Диаграмма конкуренции 2 потоков
Однако, сравнив результат с предыдущим тестированием видно, что конкуренция ресурсов снизилась. Средствами профилировщика определено 10 состязаний.
Альтернативным вариантом оптимизации алгоритма является одновременный расчет пути сразу двух объектов. При этом задаются две стартовые точки и две конечные цели. Также для каждого потока задается свой список препятствий. Положительной стороной является отсутствие разделяемой памяти и как следствие, необходимости синхронизации мьютексами, так как все переменные будут локальными в каждом потоке. Результаты показывают увеличение производительности. То есть, за меньшее время вместо одного пути прогнозируются сразу два. Результат представлен на рис. 5.
Рисунок 5 – Диаграмма конкуренции 2 потоков разных маршрутов
Конкуренция практически отсутствует, за исключением конкуренции за главный поток в месте синхронизации. На обоих процессорах зафиксировано повышение производительности.
Вывод
Таким образом, была проведена оптимизация при помощи средств управления потоками. Были проведены тестирования разных вариантов оптимизации: распределение на 8 потоков, распределение на 2 потока, одновременное вычисление пути двух объектов. При распараллеливании на несколько потоков результаты по времени выполнения ухудшились. Это связано с активной работой с памятью, доступ к которой необходимо синхронизировать. Однако вычисление сразу двух траекторий дало положительный результат, так как отсутствуют общие переменные и не требуется синхронизация доступа к ним. Такое решение можно использовать для деления одного маршрута на участки. Это позволит усилить детализацию для более детального просчета маршрута.
Литература
1. Койбаш А. А., Кривошеев С. В. Прогнозирование траектории движения подвижного объекта распределенного симулятора тяжелой инженерной техники. В кн.: Информатика, управляющие системы, математическое и компьютерное моделирование (ИУСМКМ – 2016): материалы VII междунар. науч.-техн. конф., Донецк, 2016. / редкол. А. Ю. Харитонов и др. Донецк: ДонНТУ, 2016. С. 343–346.
2. Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн. Алгоритмы: построение и анализ – 3-е изд. – М.: «Вильямс», 2013. – 1328 с.
3. Hughes C., Hughes T. Professional Multicore Programming: Design and Implementation for C++ Developers. – Indianapolis: Wiley Publishing, Inc., 2008 – 648 p.
4. Эндрю Троелсен. Язык программирования C# 5.0 и платформа .NET 4.5 – 6-е издание. – М: «Вильямс», 2013. – 1312 с.
5. Кристиан Нейгел и др. C# 5.0 и платформа .NET 4.5 для профессионалов. – М.: «Диалектика», 2013. – 1440 с.