Аннотация
Койбаш А. А., Кравченко А. Г. Эффективность использования многоядерных систем для прогнозирования траектории движения подвижного объекта распределенного симулятора тяжелой инженерной техники. Разработаны пути оптимизации алгоритма поиска кратчайшего пути А* для подвижных объектов на многоядерных системах. Исследована эффективность методов ускорения вычисления маршрута, определены достоинства и недостатки каждого метода. Определено поведение тяжелой техники для следования по заданной траектории с использованием метода мультифиниша.
Ключевые слова: прогнозирование поведения объекта, поиск кратчайшего пути, многопоточность, мультифиниш.
С развитием науки значительно возросла роль средств передвижения. Инженерная техника используется повсеместно, однако на практике маршрут далек от оптимального. Современные компьютерные технологии дают возможность эффективного решения проблемы оптимизации траектории движения. Это позволит получить значительный выигрыш по времени и, как следствие, затратам топлива, а также уменьшит износ техники и позволит смягчить влияние человеческого фактора.
Для решения этой задачи местность передвижения представляется в виде рабочего дискретного поля. Это поле представлено мультиграфом, клетки поля – вершинами, а расстояния между ними – весами рёбер. Таким образом, появляется возможность использовать математические методы просчета кратчайшего маршрута для графов. Так как вес рёбер неотрицательный, использован эвристический подход к алгоритму Дейкстры – алгоритм А* [1].
Для каждой вершины стоимость пути вычисляется по формуле:
F = G + H, (1)
где: G – стоимость передвижения к текущей вершине из начальной;
H – эвристическая стоимость передвижения от текущей вершины до конечной.
Следующей вершиной выбирается точка с минимальным параметром F. Таким образом, для каждой новой позиции алгоритм вынужден просчитывать по формуле (1) параметры 8 соседних вершин. Последовательный обход является крайне ресурсоёмким. Длительные вычисления негативно влияют на возможность актуального просчета пути тяжелой техники, так как увеличивается задержка просчета нового маршрута при отклонении от определенной ранее оптимальной траектории. Многопоточная реализация позволит ускорить алгоритм и повысить аппроксимирующую дискретизацию рабочего поля.
Алгоритм реализован средствами языка C# среды разработки Microsoft Visual Studio, так как платформа .NET позволяет реализацию кроссплатформенных приложений [2]. Одним из вариантов оптимизации является распределении просчета параметров соседних вершин по потокам. Данный способ также является вариативным и есть несколько путей реализации: распределение на 2 потока, в котором первый обрабатывает 1 – 4 вершины, второй вершины 5 – 8; распределение на 4 потока, обрабатывающих по 2 соседа; распределение на 8 потоков, каждый из которых обрабатывает по одной вершине. Все варианты данного метода редактируют общие списки, поэтому доступ к памяти синхронизируется мьютексами [3].
Альтернативным методом является разделение единой траектории на несколько вложенных маршрутов. Каждому вложенному маршруту соответствует свой поток. Синхронизация не требуется, так как каждый поток имеет собственные локальные переменные. Сравнительный анализ двух методов проведен на процессоре Intel Pentium CPU B970 @ 2.30 GHz, 2.30 GHz. Время выполнения отображено на рисунке 1.
Рисунок 1 – Время выполнения методов
В левом столбце отображено время вычисления одновременно нескольких маршрутов, в правом – распределение просчета вершин единого пути по потокам. Время выполнения однопоточной реализации составляет 0,12 мс. Как видно из графика, метод распараллеливания просчета вершин одного пути показывает существенное падение производительности. Средствами профилировщика Microsoft Visual Studio определены множественные конкуренции потоков за доступ к общей памяти, а также циклическое ожидание потоками завершения друг друга в месте синхронизации, которые представлены на рисунке 2 [1].
Рисунок 2 – Диаграмма конкуренции потоков
Альтернативный вариант, в котором каждый поток просчитывает свой маршрут, напротив показал существенный прирост во времени выполнения. Это связано с наличием раздельной памяти у каждого потока и отсутствием необходимости синхронизации потоков в цикле. Средства профилировщика показали отсутствие состязаний за исключением синхронизации в главном потоке.
Просчет маршрута необходимо выполнять во время передвижения, чтобы сообщать объекту действия согласно вычисляемой траектории. Это необходимо для оптимального и своевременного достижения конечной цели. Пример маршрута между точками A и B показан на рисунке 3.
Рисунок 3 – Оптимальный маршрут передвижения
Единица тяжелой инженерной гусеничной техники может менять направление движения, а также регулировать скорость. Необходима возможность поворота на 45° и на 90°, а также ускорение или торможение. Поворот на 45° осуществляется отключением от трансмиссии той гусеницы, в направлении которой необходимо повернуть. Для крутых поворотов на 90° требуется дополнительное торможение гусеницы. Скорость изменяется переключением передачи и с помощью педали [4]. Таким образом, возникает необходимость составить очередность действий для достижения цели. Список действий формируется с использованием метода мультифиниша. При продолжительном однонаправленном отрезке появляется возможность ускорения для улучшения временной составляющей движения. После достижения максимальной скорости давление на педаль не меняется, передвижение остаётся равномерным. Перед поворотами на 45° отключается одна гусеница, для 90° гусеница тормозится. Если дальнейший путь прямолинейный, возобновляется прежняя скорость движения. Перед финишем необходимо торможение.
Список литературы
1. Койбаш А. А., Кривошеев С. В. Прогнозирование траектории движения подвижного объекта распределенного симулятора тяжелой инженерной техники. В кн.: Информатика, управляющие системы, математическое и компьютерное моделирование (ИУСМКМ – 2016): материалы VII междунар. науч.-техн. конф., Донецк, 2016. / редкол. А.Ю. Харитонов и др. Донецк: ДонНТУ, 2016. С. 343–346.
2. Кристиан Нейгел и др. C# 5.0 и платформа .NET 4.5 для профессионалов. – М.: «Диалектика», 2013. – 1440 с.
3. Hughes C., Hughes T. Professional Multicore Programming: Design and Implementation for C++ Developers. – Indianapolis: Wiley Publishing, Inc., 2008. – 648 p.
4. Анилович В. Я., Водолажченко Ю. Т. Конструирование и расчет сельскохозяйственных тракторов. Справочное пособие. Изд. 2 переработанное и доп. – М.: «Машиностроение», 1976. – 456 с.