RUS  ENG
Полная версия
ЖУРНАЛЫ // Информатика и её применения // Архив

Информ. и её примен., 2020, том 14, выпуск 3, страницы 20–25 (Mi ia674)

Аппроксимация множества решений систем нелинейных неравенств с использованием графических ускорителей

М. В. Попов, М. А. Посыпкин

Федеральный исследовательский центр «Информатика и управление» Российской академии наук

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

Ключевые слова: оптимизация, параллельные вычисления, графический ускоритель, GPU, CUDA, нелинейные неравенства.

Поступила в редакцию: 08.10.2019

DOI: 10.14357/19922264200303



© МИАН, 2024