ДонНТУ   Портал магістрів

Койбаш Олександр Андрійович

Факультет комп’ютерних наук та технологій

Кафедра комп’ютерної інженерії

Спеціальність Програмне забезпечення засобів обчислювальної техніки

Прогнозування траєкторії руху рухомого об’єкта розподіленого симулятора важкої інженерної техніки з використанням GPU

Науковий керівник: к. т. н., доц. Завадська Тетяна Володимирівна

Науковий консультант: ст. викл. Кривошеєв Сергій Васильович

Резюме Біографія Реферат

Реферат за темою випускної роботи

Зміст

• Вступ
• 1. Актуальність
• 2. Мета та завдання дослідження
• 3. Огляд досліджень та розробок
• 3.1. Огляд міжнародних джерел
• 3.2. Огляд локальних джерел
• 4. Використання алгоритму А* в обчисленні шляху
• 5. Паралельна реалізація алгоритму А* на CPU
• 6. Використання графічного процесора для дослідження оптимізації прогнозування поведінки
• Висновки
• Перелік посилань

Вступ

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

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

1. Актуальність

Рухомий об’єкт при різних діях і обставин може рухатися по абсолютно різних маршрутах. Сучасні комп’ютерні технології надають інструменти для ефективного вирішення проблеми оптимізації траєкторії руху. Прогнозування поведінки дає можливість прогнозувати подальші дії та відповідним чином коригувати лінію поведінки (маршрут руху). Це дозволить отримати значний виграш за часом і, як наслідок, витрат палива, а також зменшить знос техніки та дозволить пом’якшити вплив людського фактора.

Подібні обчислення є вкрай ресурсоємними. Використання оптимальних алгоритмів, а також використання розподілених систем дозволяє знизити навантаження та прискорити процес обчислення. У зв’язку з цим питання про оптимальну реалізацію прогнозування поведінки є вкрай актуальним.

2. Мета та завдання дослідженняя

Метою роботи є дослідний аналіз прогнозування траєкторії руху рухомого об’єкта розподіленого симулятора важкої інженерної техніки на графічних процесорах за допомогою CUDA, а також отримання порівняльної характеристики виконання прогнозування на CPU і GPU.

3. Огляд досліджень та розробок

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

3.1. Огляд міжнародних джерел

Оскільки обчислення траєкторії використовується відразу в декількох областях (наприклад, ігри), більш реалістичному розрахунку шляху присвячені статті Marco Pinter [1] и Amit Patel [2]. Також була проведена конференція Vehicle and Automotive Engineering, де опублікована стаття Akos Cservenak і Tamas Szabo  [3].

Багато уваги приділено й оптимізації обчислень. Існують роботи, присвячені прискоренню пошуку шляху за допомогою графічних процесорів [4], [5]. Опублікована стаття, в якій автори распараллелівають передбачення повітряного маршруту [6].

Також компанія NVIDIA підтримує власний ресурс, присвячений розробникам GPU [7].

3.2. Огляд локальних джерел

У Донецькому національному технічному університеті питаннями прогнозування поведінки займалися Кривошеєв Сергій Васильович, Анопрієнко Олександр Якович [8], [9], [10].

Моделювання руху транспортних засобів розглянуті під керівництвом наукових керівників у роботах магістрів: Кондратенко А. В. [11], Гапечкіна А. І. [12], Паршина О. М. [13], Порицького О. В. [14], Водолазського Д. С. [15] і Варича М. В. [16].

4. Використання алгоритму А* в обчисленні шляху

Існує безліч способів опису схеми поведінки, однак найбільш раціональним для траєкторії руху є опис за допомогою графів. В теорії графів існують різні методи, призначені для вирішення завдання пошуку найкоротшого шляху на графі. Оскільки граф не містить ребер з негативною вагою, так як шлях не може бути негативним – немає збиткових рухів [17],оптимальним рішенням є використання алгоритму Дейкстри. Даний алгоритм знаходить найкоротшу відстань від однієї з вершин графа до всіх інших.

Для прискорення обчислень використовується алгоритм А*, який представляє собою евристичний підхід до алгоритму Дейкстри. Завдання алгоритму пошуку А* полягає в тому, що якийсь рухливий об’єкт повинен перейти з точки А в точку B по оптимальній траєкторії. Ділянка переміщення об’єкта містить різні перешкоди, які необхідно обійти. Крім цього, можливе додавання різних критеріїв (мінімальний / максимальний кут повороту, прискорення / уповільнення і т.п.) для переміщення по прогнозованої траєкторії.

Для вирішення цього завдання поле з максимально допустимою деталізацією представляється у вигляді мультиграфа. При цьому відстань є вагою ребра. Об’єкт може ходити по горизонталі і вертикалі, наприклад, з вартістю шляху 10. Також можливе переміщення по діагоналі, вартість якого є 14 (корінь із 10² + 10²). Таке поле представлено на малюнку 1. З підвищенням рівня дискретизації поля збільшується і точність результату.

У алгоритмі А* покроково проглядаються всі шляхи, що ведуть з вершини A в вершину B, доки не знайдеться шлях з мінімальною вартістю.

Алгоритм реалізується наступними кроками:

1. Формуються 2 списку вершин: вже розглянуті вершини і які очікують розгляду. У список розглянутих заноситься A.
2. Для кожної вершини вираховується вартість шляху:

   F = G + H,        (1)

   де:    G – вартість пересування до поточної вершини з початкової;

   H – евристична вартість пересування від поточної вершини до кінцевої.

3. Вибирається вершина з найменшим F. Якщо вона є B, то зберігається шлях, рухаючись від B тому до цільової точці. Інакше ця вершина вибирається поточною, видаляється з відкритого списку та заноситься в закритий.
4. Для кожної з точок, сусідніх з поточною, проводяться наступні дії:
   1. якщо сусідня точка вже розглянута, то вона пропускається.
   2. якщо сусідній точці немає в списку очікуючих на розгляд, то вона додається в цей список. Поточна клітка для неї стає батьківською. Розраховуються F, G, H.
   3. якщо сусідня клітина вже в списку чекають на розгляд, то перевіряється, чи не дешевше шлях через цю клітку. Вартість порівнюється по G. Якщо вартість менше, то батько клітини змінюється на поточну клітку і для неї перераховуються вартості G і F.
5. Якщо список очікуючих на розгляд порожній, а цілі немає, то це означає, що маршруту до мети не існує.

Таким чином, алгоритм А* не тільки проведе рухомий об’єкт безперешкодно до мети, але і при цьому обходить мінімальну кількість вершин, оскільки він ефективно використовує евристику [18]. Приклад повного шляху, розрахованого за алгоритмом А*, показаний на малюнку 2.

5. Паралельна реалізація алгоритму А* на CPU

Із анімації видно, що алгоритм змушений багаторазово проводити послідовний обхід 8 сусідніх вершин для кожної поточної позиції. Такі обчислення є вкрай ресурсоємними і в міру збільшення навантаження, пов’язаного з незручним позиціонуванням маршрутних точок і перешкод, сильно зростає час виконання програми. Суттєвого підвищення продуктивності можна домогтися шляхом багатопотокової реалізації програми.

Багатопотоковий процес має більш складну організацію, ніж однопотоковий. Він містить кілька паралельних потоків, для кожного з яких створюється свій стек і присутні власні значення регістрів [19]. Переваги такого підходу:

– підвищення продуктивності програми;

– економія пам’яті;

– ефективне використання многоядерной архітектури процесорів.

Для реалізації алгоритму використана мова C #, так як платформа .NET надає засоби розробки та синхронізації багатопоточних програм, а також за рахунок компіляції вихідного коду в байт-код CIL (Common Intermediate Language) з подальшим виконанням віртуальною машиною дає можливість створення кроссплатформних програм [20].

Одним з варіантів оптимізації є розподіл прорахунку параметрів сусідніх вершин по потокам. Даний спосіб також є варіативним і є кілька шляхів реалізації: розподіл на 2 потоку, в якому перший обробляє 1 – 4 вершини, другий вершини 5 – 8; розподіл на 4 потоки, що обробляють по 2 сусіда; розподіл на 8 потоків, кожен з яких обробляє по одній вершині. Усі варіанти даного методу редагують загальні списки, тому доступ до пам’яті синхронізується м’ютексів [19].

Для тестування розроблено поле з безліччю перешкод і декількома можливими маршрутами, щоб ускладнити роботу для програми. Алгоритм перевірявся на двох різних процесорах, що підтримують багатопоточність – Intel Penuim CPU G2020 @ 2.90 GHz, 2.90 GHz і Intel Pentium CPU B970 @ 2.30 GHz, 2.30 GHz. Однак тести показали погіршення продуктивності як на коротких інтервалах, так і на довгих маршрутах. При розподілі на 2 потоку погіршення швидкодії незначно, на 4 потоках зниження результативності є більш серйозним, 8-потокова ж реалізація дала критичне падіння продуктивності. Результати тесту показані на малюнку 3.

За допомогою засобів профілювання Microsoft Visual Studio 2013 сформована статистика і визначена конкуренція потоків за ресурси [21]. Діаграма конкуренції при реалізації програми у 8 потоків представлена на малюнку 4.

Дана діаграма відображає інтенсивність конкуренції в секунду та показує конфлікти ресурсів. Підвищений рівень конкуренцій негативно впливає на продуктивність, так як потоки простоюють в очікуванні. Як видно з малюнка, частота конкуренції вкрай висока – 33 змагання. Таким чином, метод розподілу вершин по потокам має такі недоліки: загальний список оглянутих вершин, доступ до якого надається синхронізацією м’ютексів, що збільшує затримку при одночасному зверненні до одній ділянці пам’яті, а також синхронізація всіх потоків у одній ділянці, при якому потоки чекають завершення один одного. Даний недолік виникає при кожному переміщенні на сусідню вершину, у зв’язку з чим відбувається серйозне падіння продуктивності.

При виконанні алгоритму на 2 потоках також були виявлені конкуренції. Результат представлений на малюнку 5.

Однак, у порівнянні з 8-потокової реалізацією, конкуренція ресурсів менше. Засобами профілювальника визначено 10 змагань.

Альтернативним варіантом є одночасний розрахунок шляху відразу декількох об’єктів. В цьому випадку задаються попарно кілька стартових і кінцевих точок. При цьому кожен потік має свою ділянку пам’яті – всі змінні у функції є локальними. Кожному маршруту відповідає свій потік, який формує власний список відкритих і закритих вершин. Для випробування такої реалізації розроблено кілька варіантів виконання програми: для одного, двох, чотирьох і восьми маршрутів  [22]. Тестування проведені на процесорах Intel Penuim CPU G2020 @ 2.90 GHz, 2.90 GHz і Intel Pentium CPU B970 @ 2.30 GHz, 2.30 GHz. Результати тесту показані на малюнку 6.

Альтернативний варіант, у якому кожен потік прораховує свій маршрут, навпаки показав великий приріст у часі виконання – за один і той же час прораховуються два та чотири маршрути.

Порівняльний аналіз двох методів проведено на процесорі Intel Pentium CPU B970 @ 2.30 GHz, 2.30 GHz. Час виконання відображено на малюнку 7.

У лівому стовпчику відображений час обчислення одночасно декількох маршрутів, у правому - розподіл прорахунку вершин єдиного шляху по потокам. Час виконання однопоточному реалізації становить 0,12 мс.

Для 2-потокової реалізації сформована статистика і визначена конкуренція потоків за ресурси [21]. Діаграма конкуренції відображена на малюнку 8.

Як видно з малюнка, засоби профілювальника показали відсутність змагань за винятком синхронізації в головному потоці. Істотний плюс даного варіанту полягає в відсутності редагованої усіма потоками одної й тої ж ділянки пам’яті, а також необхідності постійного очікування потоками один одного в циклі [22].

Таким чином, розроблені та протестовані методи многоядерного прискорення алгоритму А*. Метод, у якому потоки циклічно прораховують параметри сусідніх вершин, показав падіння продуктивності. Це пов’язано з конкуренцією за загальні ділянки пам’яті, а також із-за синхронізації завершення потоків після прорахунку сусідів кожної вершини. Метод розподілу траєкторії на кілька маршрутів показав істотне поліпшення продуктивності.

Виходячи з дослідження, можна визначити два методи оптимізації на основі прорахунку різних шляхів:

1. Використання методів декомпозиції одного маршруту на кілька ділянок і мультіпоточний розрахунок кожної частини.

2. Попередній розрахунок шляху.

Перший метод являє собою поділ єдиного маршруту на безліч частин, після чого проводиться обчислення оптимального шляху для кожної ділянки. Недоліком цього методу є збіжність країв маршруту, а також додаткові витрати на обчислення необхідних проміжних точок.

Другий метод більше підходить для прогнозування траєкторії руху. Його суть полягає в тому, щоб попередньо розраховувати маршрути з тих точок, в які рухливий об’єкт може потрапити через певний інтервал часу. Таким чином, для об’єкта відразу буде наданий готовий шлях, куди б він не повернув.

Прорахунок маршруту необхідно виконувати під час пересування, щоб повідомляти об’єкту дії згідно траєкторії, яка обчислюється. Це необхідно для оптимального та своєчасного досягнення кінцевої мети. Приклад маршруту між точками A і B показаний на малюнку 9.

°

Одиниця важкої інженерної гусеничної техніки може змінювати напрямок руху, а також регулювати швидкість. Необхідна можливість повороту на 45° і на 90°, а також прискорення або гальмування. Поворот на 45° здійснюється відключенням від трансмісії тієї гусениці, в напрямку якої необхідно повернути. Для крутих поворотів на 90° потрібне додаткове гальмування гусениці. Швидкість змінюється перемиканням передачі та за допомогою педалі  [23]. Таким чином, виникає необхідність скласти черговість дій для досягнення мети. Список дій формується з використанням методу мультіфініша. При тривалому однонаправленому відрізку з’являється можливість прискорення для поліпшення тимчасової складової руху. Після досягнення максимальної швидкості тиск на педаль не змінюється, пересування залишається рівномірним. Перед поворотами на 45° відключається одна гусениця, для 90° гусениця гальмується. Якщо подальший шлях прямолінійний, відновлюється колишня швидкість руху. Перед фінішем необхідно гальмування [24].

Таким чином, для проходження траєкторії визначено алгоритм вибору послідовності дій. Відповідно до кожної дії виникає необхідність попереднього прорахунку шляху з точки, в яку може потрапити одиниця важкої техніки. Для підвищення ефективності обчислень необхідно розпаралелювання на GPU за допомогою CUDA. На відміну від CPU, графічні процесори націлені на максимальну многопоточність.

6. Використання графічного процесора для дослідження оптимізації прогнозування поведінки

Графічний процесор GPU – це пристрій, який виконує графічну обробку (рендеринг). Сьогодні GPU ефективно застосовується для обробки даних у комп’ютерній графіці. Основною особливістю є архітектура, яка максимально націлена на збільшення швидкості розрахунку.

Для графічного прорахунку необхідна паралельна обробка даних. Тому GPU мультіпоточен з самого початку. Архітектура спроектована так, щоб використовувати велику кількість ниток. Якщо сучасні CPU містять від 2 до 128 ядер, то в графічному процесорі їх кількість сягає кількох тисяч. CPU краще працює з послідовними завданнями, при великому ж обсязі потоків інформації перевагу має GPU.

Для розробки програм, що використовують GPU, застосовується технологія CUDA – програмно-апаратна архітектура паралельних обчислень від компанії Nvidia. У технологію CUDA включений уніфікований шейдерний конвеєр, що дозволяє програмі задіяти будь-яке АЛП у GPU [25].

Таким чином, відеокарта є паралельною системою, тому необхідно провести порівняльний аналіз прискорення прогнозування поведінки за допомогою GPU.

Висновки

Таким чином, для прогнозування оптимальної траєкторії руху був використаний алгоритм А*, ефективно використовує евристику. Метод, в якому потоки циклічно прораховують параметри сусідніх вершин, показав падіння продуктивності – розподіл маршруту на 2, 4 і 8 потоків показав погіршення результату в порівнянні з однопоточною реалізацією. Це пов’язано з конкуренцією за загальні ділянки пам’яті, а також із-за синхронізації завершення потоків після прорахунку сусідів кожної вершини. Метод розподілу траєкторії на кілька маршрутів показав поліпшення продуктивності через розділяєму пам’ять. Це пов’язано з роздільною пам’яттю та відсутністю необхідності очікування потоків. Комбінація даного методу з декомпозицією єдиного маршруту на ділянки має недолік у збіжності країв маршрутів.

Використання графічних процесорів може прискорити процес. Подальші дослідження дозволять отримати наступну аналітичну інформацію:

– швидкість прогнозування траєкторії з використанням GPU;

– мінімальна та максимальна ступінь дискретизації робочого поля, його розміри для своєчасного виконання алгоритму;

– порівняльні характеристики різної реалізації паралельного алгоритму;

– порівняльний аналіз виконання паралельного алгоритму на CPU і GPU;

– доцільність використання GPU для передбачення поведінки.

При написанні даного реферату магістерська робота ще не завершена. Остаточне завершення: червень 2018 року. Повний текст роботи та матеріали по темі можуть бути отримані у автора або його керівника після зазначеної дати.

Перелік посилань

1. Marco Pinter: Toward More Realistic Pathfinding – [Электронный ресурс]. – Режим доступа: https://www.gamasutra.com/...
2. Amit Patel: Amit’s A* Pages [Электронный ресурс]. – Режим доступа: http://theory.stanford.edu/...
3. Akos Cservenak, Tamas Szabo. Dynamical Modelling of Vehicle’s Maneuvering. In book: Vehicle and Automotive Engineering: Proceedings of the JK2016, Miskolc, Hungary / editors: Jarmai Karoly, Bollo Betti (Eds.), 2017. – 516 p.
4. Avi Bleiweiss. GPU Accelerated Pathfinding / In proceedings of Graphics Hardware, 2008, Pages 65 – 74, 2008.
5. RAFIA INAM: A* Algorithm for Multicore Graphics Processors [Электронный ресурс]. – Режим доступа: http://publications.lib.chalmers.se/...
6. Maximilian Gotzinger, Martin Pongratz, Amir M. Rahmani and Axel Jantsch: Parallelized Flight Path Prediction Using a Graphics Processing Unit [Электронный ресурс]. – Режим доступа: https://www.researchgate.net/...
7. The Essential Resource for GPU Developers. Official NVIDIA site – [Электронный ресурс]. – Режим доступа: https://developer.nvidia.com
8. Аноприенко А. Я., Кривошеев С. В. Разработка подсистемы моделирования движения судна по заданной траектории // Научные труды Донецкого национального технического университета. Выпуск 12. Серия Вычислительная техника и автоматизация. – Донецк, ДонГТУ, ООО Лебедь, 1999. С. 197–202.
9. Аноприенко А. Я., Кривошеев С. В. Моделирование динамики речного судна на базе системы Matlab/Simulink // Прогрессивные технологии и системы машиностроения: Международный сборник научных трудов. – Донецк: ДонГТУ, 2000. Вып. 9. С. 13–20.
10. Кривошеев С. В. Исследование эффективности параллельных архитектур вычислительных систем для расчета параметров движения транспортного средства // Научные труды Донецкого национального технического университета. Выпуск № 1(10)-2(11). Серия Проблемы моделирования и автоматизации проектирования. – Донецк, ДонНТУ, 2012. С. 207–214.
11. Кондратенко А. В. Моделирование алгоритмов определения координат в модуле отображения систем логистики [Электронный ресурс]. – Режим доступа: http://masters.donntu.ru/...
12. Гапечкин А. И. Анализ поведения подвижного объекта в замкнутом пространстве [Электронный ресурс]. – Режим доступа: http://masters.donntu.ru/...
13. Паршин А. Н. Вычисление координат подвижного объекта [Электронный ресурс]. – Режим доступа: http://masters.donntu.ru/...
14. Порицкий А. В. Алгоритмы генерации траектории движения подвижного объекта [Электронный ресурс]. – Режим доступа: http://masters.donntu.ru/...
15. Водолазский Д. С. Разработка параллельных алгоритмов движения 3D объектов [Электронный ресурс]. – Режим доступа: http://masters.donntu.ru/...
16. Варич М. В. Разработка модели параллельной вычислительной системы для расчета параметров подвижного объекта [Электронный ресурс]. – Режим доступа: http://masters.donntu.ru/...
17. Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн. Алгоритмы: построение и анализ – 3-е изд. – М.: Вильямс, 2013. – С. 499–502.
18. Койбаш А. А., Кривошеев С. В. Прогнозирование траектории движения подвижного объекта распределенного симулятора тяжелой инженерной техники. В кн.: Информатика, управляющие системы, математическое и компьютерное моделирование (ИУСМКМ – 2016): материалы VII междунар. науч.-техн. конф., Донецк, 2016. / редкол. А. Ю. Харитонов и др. Донецк: ДонНТУ, 2016. С. 343–346.
19. Hughes C., Hughes T. Professional Multicore Programming: Design and Implementation for C++ Developers. – Indianapolis: Wiley Publishing, Inc., 2008 – 648 p.
20. Кристиан Нейгел и др. C# 5.0 и платформа .NET 4.5 для профессионалов. – М.: Диалектика, 2013. – 1440 с.
21. Койбаш А. А., Кривошеев С. В. Подсистема прогнозирования траектории движения подвижного объекта распределенного симулятора тяжелой инженерной техники. В кн.: Программная инженерия: методы и технологии разработки информационно-вычислительных систем (ПИИВС – 2016): сборник научных трудов I научно-практической конференции (студенческая секция), Донецк, 2016. / Донецк: ДонНТУ, 2016. С. 262–265.
22. Койбаш А. А., Кривошеев С. В. Пути снижения времени прогнозирования траектории движения подвижного объекта распределенного симулятора тяжелой инженерной техники. В кн.: Современные тенденции развития и перспективы внедрения инновационных технологий в машиностроении, образовании и экономике: материалы IV междунар. науч.-практ. конф., Азов 2017. / редкол. С. В. Жуков и др. Азов: Технологический институт (филиал) ДГТУ, 2017. С. 51–54.
23. Анилович В. Я., Водолажченко Ю. Т. Конструирование и расчет сельскохозяйственных тракторов. Справочное пособие. Изд. 2 переработанное и доп. – М.: Машиностроение, 1976. – 456 с.
24. Койбаш А. А., Кравченко А. Г. Эффективность использования многоядерных систем для прогнозирования траектории движения подвижного объекта распределенного симулятора тяжелой инженерной техники. В кн.: Информатика, управляющие системы, математическое и компьютерное моделирование (ИУСМКМ – 2017): материалы VIII междунар. науч.-техн. конф., Донецк, 2017. / редкол. Ю. К. Орлов и др. Донецк: ДонНТУ, 2017. С. 622–625.
25. Джейсон Сандерс, Эдвард Кэндрот Технология CUDA в примерах. Введение в программирование графических процессоров. – ДМК Пресс, 2011. – С. 21.