Все выпуски

Статья посвящена исследованию эффективности применения технологии параллельных вычислений на многопроцессорных системах с общей памятью для задач приближенного расчета множеств достижимости нелинейных управляемых систем в конечномерном евклидовом пространстве. В рамках исследования предложен параллельный алгоритм приближенного построения множеств достижимости, основанный на пошаговой вычислительной схеме с использованием узлов «кубических» сеток для аппроксимации множеств. Предложенный алгоритм предназначен для проведения расчетов на ЭВМ архитектуры SMP и решает вопросы разделения задачи на отдельные подзадачи, синхронизации работы параллельных частей алгоритма и равномерного распределения нагрузки между процессорами. Численное моделирование примеров на ЭВМ с двумя 4-ядерными процессорами с использованием предложенного в статье параллельного алгоритма показало высокую эффективность применения технологии параллельных вычислений для расчета множеств достижимости сеточными методами.

Рассматривается задача маршрутизации перемещений с ограничениями и усложненными функциями стоимости. Предполагается, что объекты посещения суть мегаполисы (непустые конечные множества), при посещении которых должны выполняться некоторые работы, именуемые далее внутренними. По постановке задачи имеются ограничения в виде условий предшествования. Стоимость перемещений зависит от списка заданий, которые не выполнены на момент перемещения. Ситуация такого рода возникает, в частности, при аварийных ситуациях, связанных с работой АЭС и подобных происходящим в Чернобыле и Фукусиме. Речь идет об утилизации источников радиоактивного излучения, осуществляемой последовательно во времени; в этом случае исполнитель находится под воздействием источников, которые не были демонтированы на момент соответствующего перемещения. За счет этого в функциях стоимости, оценивающих воздействие радиации на исполнителя, возникает зависимость от списка невыполненных заданий. Последние состоят в том или ином варианте выключения соответствующего источника. В настоящем исследовании излагается подход к решению данной задачи параллельным алгоритмом, реализуемым на суперкомпьютере «УРАН».

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

Рассматривается задача последовательного обхода мегаполисов (непустых конечных множеств) с условиями предшествования и функциями стоимости, зависящими от списка заданий. Постановка ориентирована на инженерные задачи, возникающие в атомной энергетике и связанные со снижением облучаемости работников, а также в машиностроении (маршрутизация движения инструмента при листовой резке на машинах с ЧПУ). Предполагается, что исследуемая задача дискретной оптимизации имеет ощутимую размерность, что вынуждает к использованию эвристик. Обсуждается процедура локального улучшения качества последних посредством применения оптимизирующих мультивставок, определяемых всякий раз в виде конечного дизъюнктного набора вставок. Предполагается, что в каждой вставке используется процедура оптимизации на основе широко понимаемого динамического программирования. Показано, что в «аддитивной» маршрутной задаче вышеупомянутого типа (с ограничениями и усложненными функциями стоимости) улучшения достигаемого результата также агрегируются аддитивно. Предлагаемая конструкция допускает реализацию в виде параллельной процедуры с использованием МВС; при этом отдельные вставки выделяются вычислительным узлам и формируются независимо.

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

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

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

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

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