Українська   Русский
DonNTU   Masters' portal

Abstract

Content

Introduction

Today information technologies allow actively to carry out new discoveries that require large computing power. Simulation plays a big role in the discoveries. One of its important aspects is the prediction of the behavior of the object. Many factors are used to do this, such as the probability of a certain action of the object, the possibility of performing an action, as well as the characteristics of the actions and the object.

Now there is an active integration of innovative technologies in many spheres of human activity. The role of vehicles greatly increased, engineering equipment and means of delivery are constantly being improved. However, in practice, the route is far from optimal, which leads to additional time and fuel costs.

1 Relevance

Movable object at different actions and circumstances can move along completely different routes. Modern computer technologies provide tools for effective solving of the problem of optimizing the trajectory. Behavior prognostication allows to predict further actions and adjust the behavior line (route of movement) accordingly. This will allow to obtain a significant gain in time and, as a result, fuel costs, as well as reduce wear and will mitigate the human factor.

Such calculations are extremely resource intensive. The use of optimal algorithms, as well as the use of distributed systems, can reduce the load and accelerate the calculation process. In this regard, the question of the optimal implementation of behavior predicting is extremely actual.

2 Research goals and objectives

The goal of the work is a research analysis of predicting the trajectory of a moving object of a distributed simulator of heavy engineering equipment on graphic processors using CUDA, and also obtaining a comparative performance characteristic of prediction on the CPU and GPU.

3 Researches and developments overview

The speed of computing the trajectory of motion is an important parameter in behavior predicting. However, today various methods for accelerating this process have been developed.

3.1 International sources overview

Since the calculation of the trajectory is used in several areas (games for example), the articles of Marco Pinter [1] and Amit Patel [2] are devoted to a more realistic calculation of the path. Also a conference Vehicle and Automotive Engineering was held, where an article by Akos Cservenak and Tamas Szabo was published [3].

Much attention is paid to optimizing calculations. There are works devoted to accelerating the search for paths using graphics processors [4], [5]. An article is published in which the authors parallelize the prediction of the air route  [6].

Also, NVIDIA supports its own resource dedicated to GPU developers [7].

3.2 Local sources overview

In the Donetsk National Technical University, the questions of prognostication of behavior were dealt by Sergey Krivosheev, Alexander Anoprienko [8], [9], [10].

Modeling the movement of vehicles considered under the guidance of scientific leaders in the work of masters: A. Kondratenko [11], A. Gapeckin [12], A. Parshin [13], A. Poritsky [14], D. Vodolazsky [15] and M. Varich [16].

4 Using the algorithm A* in computing the path

There are many ways to describe the scheme of behavior, but the most rational for the movement trajectory is a description using graphs. Since the graph does not contain edges with negative weight, since the path can’t be negative, there are no unprofitable motions [17], the optimal solution is the use of Dijkstra's algorithm.

To speed up the calculations, the algorithm A* is used. Algorithm A* will not only navigate the moving object unimpeded to the target, but also bypasses the minimum number of vertices, as it effectively uses heuristics [18]. An example of the full path calculated by the algorithm A* is shown on figure 1.

Figure 1 – Full path calculation from point A to destination B

Figure 1 – Full path calculation from point A to destination B (animation: 8 frames, 10 repetitions, 92 KB)

5 Parallel implementation of the algorithm A* on the CPU

A significant increase in performance can be achieved through multi-threaded implementation of the program.

A multi-threaded process has a more complex organization than a single-threaded process. It contains several parallel streams, each of which creates its own stack and its own register values [19]. C# is used to implement the algorithm. The .NET platform makes it possible to create a cross-platform application [20].

One of the optimization variants is multithreaded calculation of parameters of neighboring vertices. There are several ways to implement: distribution on 2 streams, in which the first stream processes 1 – 4 vertices, the second 5 – 8 vertices; distribution on 4 streams, each of which processes 2 neighbors; distribution on 8 streams, each of which processes one vertex. All variants of this method edit shared lists, so memory access is synchronized using mutexes [19].

The algorithm was tested on two different supporting multithreading processors: Intel Penuim CPU G2020 @ 2.90 GHz, 2.90 GHz and Intel Pentium CPU B970 @ 2.30 GHz, 2.30 GHz. Tests showed performance decreasing due to the need for regular synchronization [21]. The diagram of competition of the program implementation on 2 streams is shown on figure 2.

Figure 2 – Competition diagram of 2 streams

Figure 2 – Competition diagram of 2 streams

An alternative variant is to simultaneously calculate the path of several objects at once. The tests were carried out on Intel Penuim CPUs G2020 @ 2.90 GHz, 2.90 GHz and Intel Pentium CPU B970 @ 2.30 GHz, 2.30 GHz. Tests showed an increase in productivity – at the same time, several routes are calculated at once [22]. The competition diagram is shown on figure 3.

Figure 3 – Competition diagram of 2 streams at calculation of several routes

Figure 3 – Competition diagram of 2 streams at calculation of several routes

The route must be scanned during the movement. An example of a route between points A and B is shown on figure 4.

Figure 4 – Optimal movement route

Figure 4 – Optimal movement route

A unit of heavy engineering caterpillar vehicle can change the direction of movement, and also regulate the speed. The speed is changed by gear shifting and using the pedal [23]. So, it becomes necessary to make a sequence of actions to achieve the goal. The list of actions is formed using the multi-finish method [24].

To improve the efficiency of computations the algorithm can to be parallelized on the GPU using CUDA.

6 Using a graphics processor to research the optimization of behavior prediction

The GPU is a device that performs graphics processing (rendering). To develop programs that use the GPU, CUDA technology is used – the hardware-software architecture of parallel computing from Nvidia. CUDA technology includes a unified shader pipeline, which allows the program to use any ALU in the GPU [25].

So, the video card is a parallel system, therefore it is necessary to conduct a comparative analysis of the acceleration of the behavior prediction using the GPU.

Conclusion

So, to predict the optimal trajectory of motion, the algorithm A* was used, which effectively uses the heuristic. The method in which threads cyclically calculate the parameters of neighboring vertices showed a performance drop - the distribution of the route to 2, 4, and 8 streams showed a worse result than a single-threaded implementation. This is due to the competition for common parts of memory, and also because of the synchronization of the completion of threads after the calculation of the neighbors of each vertex. The method of trajectory distribution on several routes showed an improvement in performance due to shared memory. This is due to the separate memory and the absence of the need of threads waiting. The combination of this method with the decomposition of a single route into sections has a drawback in the convergence of the edges of the routes.

Using GPUs can speed up the process. Further research will provide the following analytical information:

– speed prediction of the trajectory using the GPU;

– minimum and maximum degree of discretization of the working field, its size for the timely execution of the algorithm;

– comparative characteristics of different implementation of the parallel algorithm;

– comparative analysis of parallel algorithm implementation on CPU and GPU;

– the expediency of using the GPU to predict behavior.


This abstract refers to a work that has not been completed yet. Estimated completion date: June 2018. Contant author or his scientific adviser after that date to obtain complete text.

References

  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.