Высокопроизводительный программный комплекс для построения аппроксимации областей

Содержание Аннотация ....................................................................................................................4
Annotation .....................................................................................................................4
1.   Введение ...............................................................................................................6
2. Обзор литературы ....................................................................................................9
2.1Аналогичные непараллельные алгоритмы .......................................................9
2.2Области применения........................................................................................10
2.3Анализ бруса ....................................................................................................11
2.3.1Интервальный анализ................................................................................11
2.3.2Сеточная аппроксимация..........................................................................12
3. Алгоритм аппроксимации решения системы неравенств....................................13
3.1Формальное описание......................................................................................13
3.2Реализация и распараллеливание алгоритма ..................................................15
3.2.1Реализация сеточной аппроксимации ......................................................16
3.2.2Распараллеливание алгоритма..................................................................17
3.2.3Тестирование и сравнительный анализ реализаций................................19
4. Алгоритм аппроксимации решения неполной системы уравнений....................24
4.1Формальное описание......................................................................................24
4.2Сеточная аппроксимация и гармонический поиск в ADVCOV ....................26
4.2.1Сеточная аппроксимация..........................................................................26
4.2.2Гармонический поиск ...............................................................................27
4.3Тестирование и сравнительный анализ реализаций.......................................27
5. Сравнение времени работы двух алгоритмов.................................................. 31
6. Заключение........................................................................................................ 33
7. Список литературы........................................................................................... 35

1. Введение


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

геофизики [3] и других сфер научной деятельности. Ярким примером использования описанных ниже алгоритмов является проектирование рабочего пространства для механических манипуляторов (параллельных роботов). Определение рабочей области — это важный этап в разработке параллельных роботов, поскольку большинство из них страдают от небольшого объема этой области. [4]

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

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

Преимущество предложенных в этой ВКР алгоритмов - способность работать с системой, которая состоит из любых непрерывных неравенств или уравнений, благодаря использованию численных методов. Однако, численные методы обладают существенным недостатком – высокой вычислительной трудоемкостью, поэтому что бы минимизировать время исполнения предложенных алгоритмов, в их разработке были использованы платформы для высокопроизводительных вычислений: CUDA и OpenMP.

Добрый день! Уважаемые студенты, Вашему вниманию представляется курсовая работа на тему: «Высокопроизводительный программный комплекс для построения аппроксимации областей»

Аннотация





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



Annotation





There are many applied problems that reduce to solving a system of equations or inequalities. Accurate obtaining of many solutions is not always feasible. Sometimes it requires for methods of set approximating. Most often, for each specific task, a special program is developed to build the necessary approximation. This work is devoted to the creation of universal algorithms for constructing approximations of any system of equations or inequalities consisting of continuous functions. In the work, technologies are used for parallel computing to reduce the operating time of these algorithms. Next, a comparative analysis is carried out between different implementations of each algorithm, as well as a comparison of the two obtained algorithms on the same applied task of constructing a robot workspace. The work area consists of many possible positions of the tool and is one of the key characteristics of the robot.



Keywords:



System of nonlinear equations, System of nonlinear inequalities, parallel computing, OpenMP, GPU, CUDA, solution approximation.