Все выпуски

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

The paper investigates the effectiveness of shared memory parallel programming approach for constructing approximate attainable sets of nonlinear control systems in a finite-dimensional Euclidean space. In this study, we propose a parallel iterative algorithm for constructing approximate attainable sets employing a regular Cartesian grid for spatial discretization. The proposed algorithm has been designed for implementation on SMP systems and handles such issues as data decomposition, threads synchronization and distribution of work between multiple threads. Numerical experiments on a system with two quad-core processors confirmed a high efficiency of shared memory parallel programming approach for applying grid-based methods to construct approximate attainable sets.

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

The paper considers a model of chemical kinetics for which the derivation of equations does not rely on the law of mass action, but is rather based on such principles as geometric probability and joint probability. For this model a generalization is constructed for the case of reaction-diffusion systems in heterogeneous medium, with respect to the convective and diffusive transfer of heat. The construction of this generalization is carried out by an alternative methodology, which is based fully on systems of ordinary differential equations, without a transition to partial derivatives. The description of this new method is a bit similar to the finite volume method, except that it uses statistical simplifying positions and geometric probability to describe diffusion processes. Such approach allows us to greatly simplify the numerical implementation of the resulting model, as well as to simplify its quantitative analysis by dynamical systems theory methods. Moreover, the efficiency of parallel implementation of the numerical method is increased for the resulting model. In addition, the author considers an application of this model for the description of some example reaction with quasi-periodic regime, as well as an algorithm for the transition from standard models with dimensional kinetic constants to its formalism.

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

We consider a problem of sequential traversal of megalopolises (nonempty finite sets) with travel cost functions depending on the set of pending tasks and precedence constraints. Its formulation is aimed at engineering problems in fission power generation connected with minimizing the exposure of staff to radiation and in machine engineering (routing of a CNC sheet cutting machine's tool). This discrete optimization problem is assumed to be sufficiently large-scale to necessitate the use of heuristics. We consider a procedure of local improvement for heuristics through a successive application of optimizing multi-inserts-finite disjoint sets of inserts. Each insert is assumed to be optimized by means of a broadly understood dynamic programming procedure. We show that in an “additive” routing problem of this kind (with precedence constraints and complex travel cost functions) the result's improvements are also aggregated additively. The proposed construction admits a parallel implementation for multiprocessor systems; in this case, the inserts are distributed to computational nodes and formed in an independent way.

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

The problem of minimizing the Hausdorff distance between two convex polygons is studied. The first polygon is supposed to be able to make any flat motions including parallel transportation and rotation with the center at any point. The second polygon is supposed to be fixed. Iterative algorithms of step-by-step displacements and rotations of the polygon which provide a decrease in the Hausdorff distance between the moving polygon and the fixed polygon are developed and realized in software programs. Some theorems of correctness of the algorithms are proved for a wide range of cases. Geometrical properties of the Chebyshev center of a compact set and differential properties of the function of Euclidean distance to a convex set are used. The possibility of a multiple launch is provided for in the implementation of the software complex for the purpose of identifying the best found position of the polygon. Modeling for several examples is performed.

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

The derivation of laws of kinematic control of motion of three-wheeled and four-wheeled carriages with hard wheels along an arbitrary smooth trajectory is considered in this paper. The independent angles of rotation of driving wheels are chosen as parameters of control for a three-wheeled carriage. The angle of rotation of a front wheel in the two-wheeled car models defined by the angles of rotation of front wheels on the basis of Ackermann steering is chosen as a control parameter for a four-wheeled carriage. It is established that the product of the velocity of any point of the vehicle body and the oriented curvature of its trajectory is a kinematic invariant determining the angular velocity of a vehicle. The paper presents the results of numerical modeling and animation of three-wheeled and four-wheeled carriages motion demonstrating the adequacy of the proposed model of kinematic control. The use of the proposed model can be a significant refinement of algorithms of parallel parking as well as the solution of navigation problems of management of motor vehicles using GPS and GLONASS navigation systems and problems of control of mobile robots with the help of tracking sensors. Also the proposed model can be useful for designing the motor roads, road interchanges, single-level and multilevel Parking lots, gasoline stations, on-the-go fast food stations and for the creation of car-simulators.

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

The aim of the study is to construct a parallel algorithm for solving a bottleneck (minmax) problem connected with partitioning a finite set of tasks between a finite number of agents. We describe the algorithm of finding an optimal partition of tasks through dynamic programming with a parallel computation of the Bellman function and provide a computational complexity estimate for the two algorithms (with and without the parallel construction). The algorithm was implemented for the Uran supercomputer, and a computational experiment was conducted; computation time was measured for the serial algorithm and for the parallel one on varying numbers of processor cores.

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

Particle-In-Cell (PIC) method is widely used for plasma simulation and the GPUs appear to be the most efficient way to run this method. In this work we propose a technique that enables one to speed up one of the most time-consuming operations in the GPU implementation of the PIC method. The operation is particle reordering, or redistribution of particles between cells, which is performed after pushing. The reordering operation provides data locality which is the key performance issue of the PIC method. We propose to divide the reordering into two stages. First, gather the particles that are going to leave a particular cell into arrays, the number of arrays being equal to the number of neighbor cells (26 for 3D case). Second, each neighbor cell copies the particles from the necessary array to its own particle array. The second operation is done in 26 threads independently with no synchronization or waiting and involves no critical sections, semaphores, mutexes, atomic operations etc. It results in the more than 10 times reduction of the reordering time compared to the straightforward reordering algorithm.

В работе исследуется алгоритм решения уравнения кристаллического фазового поля (Phase Field Crystal - PFC) в гиперболической постановке. Уравнение описывает фазовые превращения из метастабильного или неустойчивого состояния на масштабе атомной плотности и является дифференциальным уравнением шестого порядка по пространству и второго порядка по времени. Алгоритм основан на методе изогеометрического анализа (IGA) и реализован посредством библиотеки PetIGA. Полученный программный код допускает распараллеливание расчетов, что существенно ускоряет процесс решения задачи. Дана оценка эффективности используемых инструментов при проведении расчетов на высокопроизводительных вычислительных кластерах. Проведен анализ эффективности исследуемого алгоритма при работе с гетерогенными вычислительными системами.

The paper presents an algorithm for solving the equation of Phase Field Crystal (PFC) in a hyperbolic statement that allows to describe the phase transitions of metastable or unstable state at the nuclear density scale, described by a differential equation of the sixth order with respect to the space variable and the second order with respect to the time variable. The algorithm is based on the method of isogeometric analysis (IGA) and is implemented by PetIGA library. The resulting code allows parallel computations, which significantly speeds up the process of solving a problem. The effectiveness of used instruments during the calculations on high-performance computing clusters is evaluated. An analysis of the effectiveness of the current algorithm is carried out for heterogeneous computer systems.

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

The decomposition method  for adaptive FEM with refinement of a mesh which includes parallel algorithms is constructed: solutions of systems of the linear equations, a posteriori estimation of an error, local refinement of a mesh and dynamic balancing of computing loading. Their efficiency and structure of computing load is researched at performance on multicore computing systems.