SCI Библиотека

В статье рассматриваются разбиения натурального числа n, части которого различны, нечетны и их произведение не является квадратом. Такие разбиения применимы для определения ранга группы центральных единиц целочисленного группового кольца знакопеременной группы. Количество разбиений растет экспоненциально, следовательно, задача перебора является вычислительно затратной. В статье предложен параллельный алгоритм в общей памяти для нахождения количества разбиений числа n с дополнительными условиями. Алгоритм основан на концепции распараллеливания по данным и использовании вложенного параллелизма. Выделяется множество длин K разбиения числа n, элементы которого обрабатываются параллельно. Во время обработки длины k разбиения числа n выделяется множество уровней L, рассмотрение которого также выполняется параллельно. Приемлемые значения ускорения и параллельной эффективности предложенного алгоритма получаются при использовании двух нитей на параллельный регион по длинам и двух - по уровням. Таким образом, ускорение при разных n превышает 2.1, а параллельная эффективность не опускается ниже 50 %. Полученные результаты использованы для проверки гипотез Каргаполова и анализа распределения значений нечетных разбиений на некоторых диапазонах. Предложен алгоритм поиска оптимального коэффициента c. С помощью этого алгоритма получена асимптотическая формула количества разбиения числа n, в котором части различны и нечетны, а их произведение является квадратом. Эта формула основана на экспериментальных данных и сформулирована как гипотеза.

Статья посвящена исследованию полурешеток, содержащих покрывающие автоматы для автомата Ватерлоо. В начальных разделах статьи описывается процесс построения покрывающих автоматов на основе подмножеств гридов исходного автомата (каждый грид представляет собой некоторое множество дуг, связанных с исходным автоматом), а также рассматриваются свойства полурешеток, образуемых покрывающими автоматами. Основным результатом статьи является полное описание полученных полурешеток с точки зрения эквивалентности входящих в них покрывающих автоматов исходному автомату Ватерлоо. Выделены три класса полурешеток, каждый из которых имеет особые свойства. Для полурешетки, построенной на базе минимального покрывающего автомата, получено графическое представление, которое позволяет наглядно отразить соотношения между ее наборами, состоящими из попарно эквивалентных автоматов. Кроме того, сформулирован критерий эквивалентности покрывающего автомата автомату Ватерлоо в терминах свойств подмножества гридов, определяющего покрывающий автомат. Исследование проводилось с применением библиотеки NFALib для анализа недетерминированных конечных автоматов, реализованной автором на языке C#. Актуальность изучения автомата Ватерлоо связана с его ролью в исследовании задачи вершинной минимизации недетерминированных конечных автоматов и разработке эвристических алгоритмов реального времени, используемых для ее решения.

Проектировать эффективные параллельные программы для многопроцессорных архитектур сложно, так как нет четких формальных правил, которых необходимо придерживаться. Для решения этой проблемы при реализации численных алгоритмов может применяться концепция Q-детерминанта. Данная теория позволяет проводить автоматизированный анализ ресурса параллелизма алгоритма, автоматизированное сравнение ресурсов параллелизма алгоритмов, решающих одну и ту же алгоритмическую проблему, проектировать эффективные программы для реализации алгоритмов с помощью специально разработанного метода проектирования, повысить эффективность реализации численных методов и алгоритмических проблем. Результаты, полученные на основе концепции Q-детерминанта, представляют собой один из вариантов решения проблемы эффективной реализации численных алгоритмов, методов и алгоритмических проблем на параллельных вычислительных системах. Однако пока остается не решенной фундаментальная проблема автоматизированного проектирования и исполнения для любого численного алгоритма программы, реализующей алгоритм эффективно. В статье описана разработка единой для численных алгоритмов программной системы проектирования и исполнения Q-эффективных программ - эффективных программ, спроектированных с помощью концепции Q-детерминанта. Система предназначена для использования на параллельных вычислительных системах с общей памятью. Она состоит из компилятора и виртуальной машины. Компилятор преобразует представление алгоритма в форме Q-детерминанта в исполняемую программу, использующую ресурс параллелизма алгоритма полностью. Виртуальная машина исполняет программу, полученную с помощью компилятора. В статье также приведено экспериментальное исследование созданной программной системы с применением суперкомпьютера «Торнадо ЮУрГУ».

Проблема повышения эффективности параллельных вычислений чрезвычайно актуальна. В статье впервые продемонстрировано применение концепции Q-детерминанта для эффективной реализации алгоритма на графах. Концепция Q-детерминанта основана на унифицированном представлении численных алгоритмов в форме Q-детерминанта. Q-детерминант позволяет выразить и оценить внутренний параллелизм алгоритма, а также показать способ его параллельного исполнения. В работе приведены основные понятия концепции Q-детерминанта, необходимые для понимания приведенного исследования. Также описан основанный на концепции Q-детерминанта метод проектирования эффективных программ для численных алгоритмов. Результатом применения метода является программа, полностью использующая ресурс параллелизма алгоритма. Такая программа называется Q-эффективной. В качестве первого применения метода проектирования Q-эффективных программ для алгоритмов на графах описано проектирование программ для реализации алгоритма Дейкстры на параллельных вычислительных системах с общей и распределенной памятью. Приведены также результаты экспериментального исследования разработанных программ, проведенного с помощью суперкомпьютера «Торнадо ЮУрГУ». На основе анализа результатов экспериментального исследования определяются динамические характеристики разработанных программ и выявляются особенности их выполнения. Проведенные в статье исследования дают возможность сделать вывод, что применение концепции Q-детерминанта с целью разработки эффективных программ возможно не только для численных алгоритмов, но и для алгоритмов на графах.

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

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

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

В статье описывается программная реализация быстрого алгоритма поиска распределенных рассеивателей для задачи построения скоростей смещений земной поверхности на базе платформы Apache Spark. Рассматривается полная схема расчета скоростей смещений методом постоянных рассеивателей (PS). Предложенный алгоритм интегрируется в схему после этапа совмещения с субпиксельной точностью стека изображений временной серии радарных снимков космического аппарата Sentinel-1. Поиск распределенных рассеивателей происходит независимо в окнах сдвига по всей площади снимка. Наличие последних определяется путем предположения о гомогенности пар выборок в окне, составленных из векторов комплексных значений пикселей в каждом из N изображений. Данное предположение вытекает из выполнимости критерия Колмогорова–Смирнова для каждой из пар. Для оценки значений фаз гомогенных пикселей решается задача максимизации. Показано, что предложенный алгоритм не является итерационным и может быть реализован в парадигме параллельных вычислений. Применяемая платформа Apache Spark позволила распределенно обрабатывать массивы стека радарных данных (от 60 изображений) в памяти на большом количестве физических узлов в сетевой среде. При этом, время поиска распределенных рассеивателей удалось снизить в среднем в 10 раз по сравнению с однопроцессорной реализацией алгоритма. Приведены сравнительные результаты тестирования вычислительной системы на демонстрационном кластере. Алгоритм реализован на языке программирования Python c подробным описанием объектов и методов алгоритма.

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

HPC systems are complex in architecture and contain millions of components. To ensure reliable operation and efficient output, functioning of most subsystems should be supervised. This is done on the basis of collected data from various logging and monitoring systems. This means that different data sources are used, and accordingly, data analysis can face multiple issues processing this data. Some of the data subsets can be incorrect due to the malfunctioning of used sensors, monitoring system data aggregation errors, etc. This is why it is crucial to preprocess such monitoring data before analyzing it, taking into the consideration the analysis goals. The aim of this paper is, being based on the MSU HPC Center monitoring data, to propose an approach to data preprocessing of HPC monitoring systems, giving some real life examples of issues that may be faced, and recommendations for further analysis of similar datasets.