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

Реферат по теме выпускной работы

Содержание

Введение

Решение проблемы обеспечения безопасности движения транспортных средств является первостепенной задачей в связи с увеличением транспортных потоков. Проблема безопасности стоит особенно остро для судов внутреннего и смешанного плавания. В связи с этим, широкое распространение для решения задачи автономного судовождения получили интегрированные навигационные системы (ИНС) [1], основным назначением которых является повышение безопасности движения судна на внутренних водных путях благодаря освобождению судоводителя от выполнения навигационных расчетов, необходимых для предсказания траектории движения. В магистерской работе проводится исследование подсистемы ИНС, которая выполняет расчет координат траектории движения судна. Основной задачей данной подсистемы является прогнозирование параметров движения судна на основе его математической модели. В связи с тем, что подсистема расчета параметров движения требует больших вычислительных мощностей, то для ее эффективной работы необходимо применять высокопроизводительные системы. В магистерской работе выполняется анализ эффективности работы подсистемы расчета координат траектории движения судов при ее реализации на различных параллельных архитектурах.

1. Актуальность темы

Быстродействие функционирования подсистемы расчета координат траектории движения судна определяет эффективность работы всей ИНС. В связи с этим, повышение производительности данной подсистемы является актуальной задачей. Низкое быстродействие работы этой подсистемы делает работу всей ИНС неэффективной, что может привести к негативным последствиям. Проблема быстродействия возникает особенно остро при расчете параметров для группы судов. В магистерской работе исследуются вопросы обеспечения необходимого быстродействия работы подсистемы расчета координат траектории движения судов в составе ИНС.

2. Цель и задачи исследования

Целью работы является анализ эффективности работы подсистемы расчета координат траектории движения судов, реализованной на параллельных архитектурах.

В рамках магистерской работы необходимо решить следующие задачи:

3. Обзор исследований и разработок

На мировом уровне разработкой ИНС и моделированием движения транспортных средств активно занимаются совет по транспортным исследованиям Национальной академии наук США (Transportation Research Board of the National Academy of Sciences) [2], кафедра прикладной механики и управления механико-математического факультета Московского государственного университета имени М.В. Ломоносова [3], Институт динамики сложных технических систем общества имени Макса Планка (Германия) [4], который активно сотрудничает с кафедрой компьютерной инженерии факультета КНТ Донецкого национального технического университета (ДонНТУ). Исследования в этом направлении ведутся под управлением профессора Штутгартского университета (Германия) Эрнста Гиллеса (Ernst Dieter Gilles) [5]. Активную работу в области моделирования водных транспортных средств ведут в Норвежском университете науки и технологии под руководством профессора Тора Фоссена (Thor Fossen) [6]. Он является одним из авторов свободно распространяемых Matlab/Simulink библиотек [7] для моделирования движения водных транспортных средств.

В Украине вопросы создания электронных систем судовождения активно исследуются в Одесской национальной морской академии [8]. Исследования в этом направлении ведутся под управлением профессора Вагущенко Леонида Леонидовича [9].

В Донецком национальном техническом университете вопросами моделирования движения транспортных средств, созданием тренажерных систем и интегрированных навигационных систем занимаются сотрудники кафедры компьютерной инженерии факультета КНТ: ассистент Кривошеев Сергей Васильевич, профессор Аноприенко Александр Яковлевич и профессор Святный Владимир Андреевич [10, 11, 12, 13, 14]. Научная школа профессора Святного Владимира Андреевича активно занимается параллельным моделированием. Вопросы моделирования движения транспортных средств и использования навигационных систем рассмотрены в магистерских работах Кондратенко А.В. [15], Гапечкина А.И. [16], Паршина А.Н. [17] и Порицкого А.В. [18].

4. Обзор параллельных архитектур

Одним из способов повышения производительности вычислительных систем является использование параллельных архитектур. В этом разделе выполняется краткий обзор существующих параллельных систем, их аппаратной реализации и программной поддержки.

4.1 Общая классификация параллельных систем

Под параллельными архитектурами понимают такие архитектуры вычислительных систем, которые на аппаратном уровне позволяют организовать параллельную обработку данных. На рисунке 1 приведена общая классификация параллельных вычислительных систем [19].

Классификация параллельных архитектур

Рисунок 1 – Классификация параллельных архитектур

Архитектура SIMD (Single Instruction stream Multiple Data stream – один поток команд, несколько потоков данных) лежит в основе вычислительных систем, управляемых одним потоком команд, обрабатывающим несколько потоков данных. К разновидностям таких систем относятся массивно-параллельные и векторные процессоры (компьютеры).

Массивно-параллельный процессор, с точки зрения общей структуры, можно представить как решетку достаточно большого размера, с узлами которой связаны однотипные процессоры определенной производительности, каждый из которых имеет свою локальную память. Единый блок управления активизирует процессоры на выполнение одной и той же последовательности команд, но над разными данными, загружаемыми в локальные модули памяти.

Основой векторного процессора является векторное арифметико-логическое устройство (АЛУ). Векторное АЛУ – это набор параллельно функционирующих обычных АЛУ, выполняющих одновременно одно и тоже действие (предписанное командой) над соответствующими элементами векторов данных, хранящимися в специальных векторных регистрах.

Архитектура MISD (Multiple Instruction stream Single Data stream – несколько потоков команд, один поток данных) не используется на макроуровне (уровне машинных команд) известных вычислительных систем. На микроуровне MISD представляет собой конвейерную суперскалярную организацию вычислений.

MIMD архитектура (Multiple Instruction stream Multiple Data stream – несколько потоков команд, несколько потоков данных) лежит в основе мультипроцессоров и мультикомпьютеров.

Мультипроцессор – это набор процессоров, оперирующих параллельно в одном адресном пространстве и использующих единую копию операционной системы. При блокировке какого-либо процесса его процессор сохраняет свое состояние в таблицах операционной системы и передает управление другому процессору. Единое отображение вычислительного процесса, используемое всеми процессорами, хранится в памяти совместного пользования.

В соответствии со способом реализации памяти совместного использования различают три типа архитектур мультипроцессоров:

Мультикомпьютер – вычислительная система без общей памяти, состоящая из большого числа взаимосвязанных компьютеров, у каждого из которых имеется собственная память. Процессоры мультикомпьютера отправляют друг другу сообщения, для чего используется сетевая топология.

Основой особенностью мультикомпьютеров является то, что каждый процессор системы может использовать только свою локальную память, в то время как для доступа к данным, располагаемых на других узлах системы, необходимо явно выполнить операции передачи сообщений (message passing operations). Для передачи данных между узлами используется высокоскоростная сеть передачи данных (коммуникационная сеть). На рисунке 2 приведена структура мультикомпьютера.

Структура мультикомпьютера

Рисунок 2 – Структура мультикомпьютера

В настоящее время различают два основных класса мультикомпьютеров:

Следует отличать понятия кластера от сети компьютеров. Для построения локальной компьютерной сети, как правило, применяют более простые сети передачи данных. Компьютеры сети обычно более рассредоточены и могут быть использованы пользователями для выполнения каких-либо дополнительных работ, кроме параллельных вычислений.

В составе каждого узла мультикомпьютера содержится коммутатор, который подключается к сети передачи данных. Топология коммуникационной сети определяет схему размещения линий связи и коммутаторов.

4.2 Аппаратная реализация параллельных систем

В последние годы среди производителей центральных процессоров (CPU) имеется тенденция увеличивать не тактовую частоту работы CPU, а увеличивать число вычислительных ядер. Под многоядерным процессором [20] понимается центральный процессор, который содержит два или более вычислительных ядра на одном процессорном кристалле или в одном корпусе. Под ядром понимается часть процессора, осуществляющая выполнение одного потока команд. В многоядерном процессоре можно осуществлять независимое параллельное выполнение нескольких потоков команд одновременно. Число независимых выполняющихся потоков соответствует числу ядер в процессоре. Многоядерные процессоры являются простейшей MIMD системой. В настоящее время число ядер в CPU может достигать нескольких десятков.

В настоящее время широкое распространение получило использование графических процессоров (GPU) для проведения вычислений общего назначения, в частности параллельных вычислений. Такая техника использования GPU получила название GPGPU (General-purpose graphics processing units – «GPU общего назначения»). Графические процессоры изначально являются параллельными устройствами SIMD. GPU принимает на входе группу полигонов, проводит все необходимые операции, и на выходе выдает пиксели. Обработка полигонов и пикселей независима, их можно обрабатывать параллельно, отдельно друг от друга. Из-за параллельной организации работы в GPU используется большое количество исполнительных блоков, которые легко загрузить. Кроме того, современные GPU могут выполнять более одной инструкции за такт (dual issue). На рисунке 3 показана разница в структуре CPU и GPU.

Разница в структуре CPU и GPU

Рисунок 3 – Разница в структуре CPU и GPU

Как видно из рисунка большую часть кристалла CPU занимает кэш-память (cache), а вычислительные модули (ALU) занимают лишь четвертую часть кристалла. Большую часть кристалла GPU занимают вычислительные модули (ALU), а доля кэш-памяти (cache) и устройств управления (control) очень мала. Поэтому GPU целесообразно использовать для параллельных вычислений.

Одним из примером реализации параллельных вычислений общего назначения на графических процессорах является программно-аппаратная архитектура CUDA [21] от компании NVIDIA.

В настоящее время широкое распространение получила идея создания высокопроизводительных кластеров [22] из персональных компьютеров на базе обычных центральных процессоров, используя недорогие коммуникационные сети, например сети Ethernet. Производительность таких кластеров может достигать вычислительных мощностей суперкомпьютеров при в десятки раз меньшей стоимости.

4.3 Программная поддержка параллельных систем

Для эффективного использования аппаратных возможностей параллельных архитектур необходимо использовать соответствующие программные средства.

Одним из простейших способов реализации параллельных вычислений на базе многоядерных и многопроцессорных систем является создание многопоточных приложений. Для создания многопоточных приложений требуется поддержка многопоточности со стороны операционной системы и наличие специальных библиотек для работы с потоками в высокоуровневом языке программирования. В качестве примера такой библиотеки можно привести OpenMP (Open Multi-Processing) [23]. OpenMP – открытый стандарт для распараллеливания программ на языках С, С++ и Fortran. Стандарт описывает совокупность директив компилятора, библиотечных процедур и переменных окружения, которые предназначены для программирования многопоточных приложений на многопроцессорных системах с общей памятью. Многие современные интегрированные среды разработки поддерживают стандарт OpenMP.

В качестве примера программной поддержки параллельных вычислений на базе графических процессоров можно привести аппаратно-программную платформу NVIDIA CUDA. Для работы с этой платформой необходимо наличие видеокарты компании NVIDIA, которая поддерживает GPGPU, и установка среды разработки CUDA (CUDA Toolkit). CUDA Toolkit можно скачать с официального сайта NVIDIA [24] для конкретной операционной системы. Среда разработки CUDA (CUDA Toolkit) включает:

Таким образом, разработчик получает возможность создавать параллельные программы для графического процессора, используя привычные языки высокого уровня. Компания NVIDIA выпускает специальные утилиты, которые позволяют разрабатывать CUDA-программы в составе других интегрированных сред разработки.

Одним из наиболее распространенных способов организации параллельных вычислений на мультикомпьютерах является использование программного интерфейса MPI [25]. Message Passing Interface (интерфейс передачи сообщений) – программный интерфейс (API) для передачи информации, который позволяет обмениваться сообщениями между процессами, выполняющими одну задачу. Существует множество коммерческих и бесплатных реализаций MPI для различных операционных систем и компьютерных платформ.

MPI-программа представляет собой набор независимых процессов, каждый из которых выполняет свою собственную программу. Процессы MPI-программы взаимодействуют друг с другом посредством вызова коммуникационных процедур. Как правило, каждый процесс выполняется в своем собственном адресном пространстве, однако допускается и режим разделения памяти. MPI не специфицирует модель выполнения процесса – это может быть как последовательный процесс, так и многопоточный. MPI не предоставляет никаких средств распределения процессов на вычислительных узлах и запуска их на выполнение. Эти функции возлагаются либо на операционную систему, либо на программиста. MPI не накладывает никаких ограничений на то, как процессы будут распределены по процессорам, в частности, возможен запуск MPI-программы с несколькими процессами на обычной однопроцессорной системе.

Для идентификации наборов процессов вводится понятие группы, объединяющей в себе все или какую-то часть процессов. Каждая группа образует область связи, с которой связывается специальный объект – коммуникатор области связи. Процессы внутри группы нумеруются целым числом в диапазоне 0,…,(groupsize-1). Все коммуникационные операции с некоторым коммуникатором будут выполняться только внутри области связи, описываемой этим коммуникатором. При инициализации MPI создается определенная область связи, которая содержит все процессы MPI-программы, с ней связывается определенный коммуникатор MPI_COMM_WORLD. В большинстве случаев на каждом процессоре запускается один отдельный процесс, и тогда термины «процесс» и «процессор» становятся синонимами, а величина groupsize становится равной числу процессоров, выделенных задачи.

5. Модель параллельной системы для расчета параметров подвижного объекта

Основной задачей подсистемы расчета координат траектории движения судна является прогнозирование параметров движения судна на основе заданных начальных условий с использованием математической модели движения. Математическая модель движения судна определяет работу подсистемы расчета параметров. Выбор математической модели определяется требуемым уровнем детализации движения. Можно выделить следующие математические модели движения судна: модель движения с шестью степенями свободы (движение судна в трехмерном пространстве), модель движения с тремя степенями свободы (движение судна только в горизонтальной плоскости) и модель Номото.

5.1 Общая структура подсистемы расчета параметров движения судна

Общая структура подсистемы расчета параметров траектории движения судна приведена на рисунке 4.

Общая структура подсистемы расчета параметров траектории движения судна

Рисунок 4 – Общая структура подсистемы расчета параметров траектории движения судна

Подсистема расчета параметров движения содержит следующие модули: интерфейс приема информации, база данных параметров судна, интерфейс передачи информации и вычислитель. Интерфейс приема информации получает начальные параметры траектории движения судна от других модулей ИНС и передает полученную информацию на вычислитель. База данных параметров судна содержит характеристики, которые описывают конкретное судно, для которого выполняется прогнозирование параметров. Интерфейс передачи информации передает спрогнозированные параметры траектории движения судна, поступившие с вычислителя, на другие модули ИНС. Вычислитель является основным элементом подсистемы расчета координат траектории движения судна. Этот модуль выполняет расчет параметров движения на основе математической модели движения судна с использованием его параметров из базы данных и полученных начальных параметров движения.

5.2 Математическая модель движения судна

Расчет параметров движения судна выполняется на основе математической модели. Рассмотрим математическую модель движения судна в горизонтальной плоскости. Система координат судна приведена на рисунке 5.

Система координат судна

Рисунок 5 – Система координат судна

Маневры судна в горизонтальной плоскости можно описать с помощью следующей модели [26]:

Система уравнений 1

где m – масса судна; vX и vY – скорость судна по оси X и Y соответственно; ω – угловая скорость судна; L – длина судна; JZ – момент инерции массы судна; lR – расстояние от центра судна до движительно-рулевого комплекса (ДРК); ZP – число ДРК; XA, YA, MA – продольная, боковая силы и момент аэродинамических сил, действующих на надводную часть судна; TRi и YRi – полезная тяга и боковая сила i-го ДРК; k11, k22 – присоединенные массы судна при движении по осям X и Y соответственно; k66 – присоединенный момент инерции судна; k26 – присоединенный статический момент; R – сопротивление воды; YK – боковая гидродинамическая сила неинерционной природы; MK – момент гидродинамических сил относительно вертикальной оси, проходящей через центр судна.

В системе уравнений (1) три неизвестные величины – vX, vY, ω. Все остальные параметры либо известны для конкретного судна, либо рассчитываются по формулам. Неизвестные величины находятся в ходе решения системы дифференциальных уравнений. Скорости по оси X и Y и угловая скорость в каждый момент времени исчерпывающе описывают динамику движения судна в горизонтальной плоскости.

При некоторых режимах движения и при пренебрежении некоторыми параметрами система уравнений (1) может значительно упрощаться. Например, при круговом (циркулярном) движении судна система уравнений (1) принимает вид:

Система уравнений 2

где Xr, Yr и Mr – корпусные гидродинамические усилия.

Подсистема расчета координат траектории движения решает задачу Коши для системы уравнений (1): зная значение vX, vY, ω в начальный момент времени t0 для судна, находит значения параметров vX, vY, ω в последующие моменты времени. Предварительно система уравнений (1) преобразуется к виду, удобному для применения численных методов. Постановка задачи Коши для системы уравнений (1) выглядит следующим образом:

Система уравнений 3

где t0 – начальное время исследования движения судна; vX0, vY0 – скорость движения судна по оси X и Y соответственно в начальный момент времени t0; ω0 – угловая скорость судна в t0.

Для решения системы уравнений (3) применяется численный метод Рунге-Кутта 4-го порядка. Этот метод является одним из наиболее распространенных численных методов решения дифференциальных уравнений и их систем. На рисунке 6 показан данный метод на примере решения обыкновенного дифференциального уравнения 1-го порядка.

Метод Рунге-Кутта 4-го порядка

Рисунок 6 – Решение дифференциального уравнения методом Рунге-Кутта 4-го порядка
(анимация: 10 кадров, 5 циклов повторения, 1 секунда интервал между кадрами, размер 80,3 килобайта)
(h – шаг интегрирования, n – количество шагов интегрирования)

6. Результаты экспериментов

Исследование производительности подсистемы расчета координат траектории движения судов выполнялось при реализации на двух различных параллельных системах: с использованием двуядерного центрального процессора (Intel Core 2 Duo E8500, 3.16 ГГц) и видеокарты NVIDIA GeForce GTS 250 с графическим процессором NVIDIA G92b, который содержит 128 потоковых процессора и поддерживает технологию CUDA. Результаты экспериментов приведены на рисунке 7.

Результаты расчетов на CPU и GPU

Рисунок 7 – Зависимость времени расчета (мс) координат траектории от количества судов при моделировании на центральном и графическом процессорах

Как видно из графика, при малом количестве судов использование CPU эффективнее, чем использование GPU. GPU целесообразно использовать при 75 и более количестве судов.

Выводы

На момент написания данного реферата в рамках проведенных исследований выполнены:

Дальнейшие исследования планируется направить на следующие аспекты:

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

Список источников

  1. Анучин О.Н., Емельянцев Г.И. Интегрированные системы ориентации и навигации для морских подвижных объектов. СПб.: Электроприбор, 2003. – 390 с.
  2. Transportation Research Board [Электронный ресурс]. – Режим доступа: http://www.trb.org/Main/Home.aspx
  3. Кафедра прикладной механики и управления механико-математического факультета МГУ имени М.В. Ломоносова [Электронный ресурс]. – Режим доступа: http://www.damc.ru/
  4. Max Planck Institute for Dynamics of Complex Technical Systems [Электронный ресурс]. – Режим доступа: http://www.mpi-magdeburg.mpg.de/
  5. Bittner R., Driescher A., Gilles E.D. Entwurf einer Vorsteuerung zur hochgenauen Bahnführung von Binnenschiffen. 3. Wismarer Automatisierungssymposium, September 2002. ss. 4-11
  6. Professor Thor I. Fossen [Электронный ресурс]. – Режим доступа: http://www.itk.ntnu.no/ansatte/Fossen_Thor/
  7. Marine Systems Simulator [Электронный ресурс]. – Режим доступа: http://www.marinecontrol.org/index.html
  8. Кафедра Электронные Комплексы Судовождения [Электронный ресурс]. – Режим доступа: http://nav-eks.org.ua/
  9. Вагущенко Л.Л. Судовые навигационно-информационные системы. – Одесса, Латстар, 2004. – 302 с.
  10. Аноприенко А.Я., Кривошеев С.В. Разработка подсистемы моделирования движения судна по заданной траектории // Научные труды Донецкого национального технического университета. Выпуск 12. Серия «Вычислительная техника и автоматизация». – Донецк, ДонГТУ, ООО «Лебедь», 1999. С. 197-202. http://ea.donntu.ru:8080/jspui/bitstream/123456789/3462/1/1999-anopriyenko-krivosheeev-ship-simulation.pdf
  11. Аноприенко А.Я., Кривошеев С.В. Моделирование динамики речного судна на базе системы Matlab/Simulink // «Прогрессивные технологии и системы машиностроения»: Международный сборник научных трудов. – Донецк: ДонГТУ, 2000. Вып. 9. С. 13-20. http://ea.donntu.ru:8080/jspui/bitstream/123456789/3692/1/2000-anopriyenko-krivosheeev-ship-simulation.pdf
  12. Кривошеев С.В. Исследование эффективности параллельных архитектур вычислительных систем для расчета параметров движения транспортного средства // Научные труды Донецкого национального технического университета. Выпуск № 1(10)-2(11). Серия «Проблемы моделирования и автоматизации проектирования». – Донецк, ДонНТУ, 2012. С. 207-214. http://ea.donntu.ru:8080/jspui/bitstream/123456789/17309/1/12ksvotv.pdf
  13. Аноприенко А.Я., Кривошеев С.В., Потапенко В.А. Моделирование процесса обработки информации в интегрированной навигационной системе // Тези доповідей міждержавної науково-методичної конференції "Комп'ютерне моделювання" 30 червня – 2 липня 1999 р., м. Дніпродзержинськ. – Дніпродзержинськ. – 1999. С. 114-115. http://ea.donntu.ru:8080/jspui/bitstream/123456789/3694/1/1999-06-30-anopriyenko-krivosheeev-potapenko-ins-simulation.pdf
  14. Святный В.А., Аноприенко А.Я., Кривошеев С.В., Потапенко В.А. Имитация радиолокационной информации в интегрированной навигационной системе //Сборник трудов VI международной научно-технической конференции «Машиностроение и техносфера на рубеже XXI века» 13-18 сентября 1999 г. В г. Севастополе. – Том 3. – Донецк. – 1999, с. 12-15. http://ea.donntu.ru:8080/jspui/bitstream/123456789/3693/1/1999-09-15-svjatnyj-anopriyenko-krivosheeev-radiolocation-information.pdf
  15. Кондратенко А.В. Моделирование алгоритмов определения координат в модуле отображения систем логистики [Электронный ресурс]. – Режим доступа: http://masters.donntu.ru/2011/fknt/kondratenko/diss/index.htm
  16. Гапечкин А.И. Анализ поведения подвижного объекта в замкнутом пространстве [Электронный ресурс]. – Режим доступа: http://masters.donntu.ru/2011/fknt/gapechkin/diss/index.htm
  17. Паршин А.Н. Вычисление координат подвижного объекта [Электронный ресурс]. – Режим доступа: http://masters.donntu.ru/2010/fknt/parshin/diss/index.htm
  18. Порицкий А.В. Алгоритмы генерации траектории движения подвижного объекта [Электронный ресурс]. – Режим доступа: http://masters.donntu.ru/2010/fknt/poritskiy/diss/index.htm
  19. Классификация архитектур по параллельной обработке данных [Электронный ресурс]. – Режим доступа: http://www.csa.ru/analitik/distant/q_4.html
  20. Multi-core processor [Электронный ресурс]. – Режим доступа: http://en.wikipedia.org/wiki/Multi-core_processor
  21. Казеннов А. М. Основы технологии CUDA // Компьютерные исследования и моделирование Т. 2 № 3. – 2010. – c. 295-308.
  22. Linux. Кластер. Практическое руководство по параллельным вычислениям [Электронный ресурс]. – Режим доступа: http://cluster.linux-ekb.info/
  23. The OpenMP API specification for parallel programming [Электронный ресурс]. – Режим доступа: http://openmp.org/wp/
  24. CUDA Parallel Computing Platform [Электронный ресурс]. – Режим доступа: http://www.nvidia.com/object/cuda_home_new.html
  25. Message Passing Interface Forum [Электронный ресурс]. – Режим доступа: http://www.mpi-forum.org/
  26. Ходкость и управляемость судов. Под ред. В.Г. Павленко. М.: Транспорт, 1991. – 396 с.