SCI Библиотека

В работе предложен алгоритм решения задачи нахождении максимального общего подграфа. Описаны последовательный и параллельный вариант алгоритма, их программная реализация и произведено экспериментальное исследование их эффективности. Данная задача является одной из самых известных NP“=полных задач. Ее решение может потребоваться при решении многих практических задач, связанных с исследованием сложных структур. Мы решаем ее в постановке, в которой требуется найти все возможные изоморфизмы найденного общего подграфа. Ввиду чрезвычайно высокой трудоемкости задачи желание ускорить ее решение за счет распараллеливания алгоритма является вполне естественным. Для организации параллельных вычислений автором использовалась библиотека RPM_ParLib, которая позволяет создавать параллельные приложения, работающие в локальной вычислительной сети под управлением среды исполнения .NET Framework. Библиотека поддерживает рекурсивно-параллельный стиль программирования и обеспечивает эффективное распределение работы и динамическую балансировку загрузки вычислительных модулей в процессе исполнения программы. Она может быть использована для приложений, написанных на любом языке программирования, поддерживаемом .NET Framework. Целью численного эксперимента было исследование ускорения, достигаемого за счет рекурсивно“=параллельной организации вычислений. Для эксперимента автором было разработано специальное приложение на языке C#, предназначенное для генерации различных наборов исходных данных с заданными параметрами. В работе описаны характеристики сгенерированных исходных пар графов, а также результаты, полученные в ходе эксперимента.

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

Исследуется динамика систем автоматического управления (САУ) регулярно вращающимися по углу крена объектами, например малогабаритными вращающимися ракетами (МВР), структура которых на участке до модулятора, между модулятором и демодулятором и после демодулятора может быть представлена линейными двумерными (двухканальными) звеньями с несимметричными каналами и несимметричными перекрестными связями, а опорные сигналы модулятора и демодулятора -двумерными гармоническими функциями. Излагаются приемы и условия приведения описания таких САУ к стационарному виду с последующим анализом их устойчивости и точности.

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

В настоящей работе исследуется эффективность планирования очереди с помощью предобученных моделей. Суперкомпьютерный кластер применяет планировщик для распределения поступающего потока заданий между доступными вычислительными ресурсами. Для размещения задания в очереди планировщик использует данные, указанные пользователем, в том числе заказанное время работы программы. Однако пользователи часто неверно оценивают время работы и указывают верхнюю оценку. Если задание завершается раньше, чем указано, то планировщику необходимо перепланировать очередь. Большое количество подобных событий может снижать эффективность распределения ресурсов. В последнее время появилось множество работ, посвященных применению машинного обучения для предсказания времени работы задания. Это позволяет в процессе планирования использовать время работы, вычисленное с помощью предобученной модели. Однако все полученные модели содержат ошибку. Проблема заключается в необходимости оценки эффективности планирования при заданном значении ошибки модели. В данном исследовании для оценки эффективности планирования очереди с помощью предобученных моделей сравниваются два сценария: планировщик использует указанное пользователем время (сценарий 1) и реальное время работы задания (сценарий 2). С помощью симулятора планировщика SLURM была произведена симуляция на статистических данных суперкомпьютера МВС-10П ОП2, установленного в Межведомственном суперкомпьютерном центре РАН. Результаты показали, что среднее время ожидания в сценарии 2 уменьшилось на 25 %, а приведенное время ожидания - на 50 %. Утилизация ресурсов изменилась незначительно. Данные эксперимента доказывают целесообразность применения алгоритмов машинного обучения для предсказания времени работы заданий, поступающих на суперкомпьютерный кластер. Таким образом, в статье приводится оценка предельной оптимизации, так как эксперимент предполагает стопроцентную точность предсказания, что на сегодняшний день не демонстрирует ни одна из представленных работ по предсказанию времени работы заданий.

В статье описывается программа генерирования последовательности временных отсчетов комплексного гармонического колебания с флуктуацией фазы в виде фликкер-шума с заданной спектральной плотностью. Предлагается решение задачи оценки устойчивости современных каналов передачи цифровых данных к помехам и шумам, что на первом этапе проектирования канала выясняется с помощью моделирования. В моделирующей программе исходной характеристикой генерируемого колебания является желаемая спектральная плотность флуктуаций его начальной фазы. На ее основании рассчитывается амплитудно-частотная характеристика формирующего цифрового фильтра. На вход фильтра подается некоррелированная нормальная псевдослучайная последовательность, на выходе получается последовательность временных отсчетов флуктуирующей начальной фазы комплексного гармонического колебания с некоторой средней частотой (в частности, равной нулю). Для каждого из этих отсчетов вычисляются вещественная и мнимая компоненты выходного колебания генератора. Их совокупность и является искомым комплексным гармоническим колебанием с флуктуацией фазы. Программа написана на языке графического программирования NI LabVIEW, что позволяет видеть все этапы ее работы. Для оценки качества функционирования разработанной программы выполнено тестовое моделирование колебания высокостабильного генератора E5052B Signal Source Analyzer. Последующий численный анализ параметров полученного колебания и сравнение их с известными параметрами генератора подтвердили корректность работы программы. Предложенный в статье способ моделирования влияния фазовых шумов на сигналы в канале связи может быть полезен для специалистов в области исследования и проектирования различных систем беспроводной связи, а также в процессе изучения основ передачи радиосигналов в рамках образовательного процесса в высших учебных заведениях.

Исследование и описание свойств алгоритмов крайне важно для их эффективной реализации на различных типах целевых программно-аппаратных платформ. Этой актуальной задаче посвящен проект создания Открытой энциклопедии свойств алгоритмов AlgoWiki, начатый в Московском государственном университете имени М.В. Ломоносова в 2014 году. В рамках проекта была предложена единая универсальная схема описания свойств алгоритмов, в которой особое внимание уделялось свойствам, связанным с параллелизмом. Множество описанных по данной схеме алгоритмов послужило основой описания структуры предметной области в рамках иерархической схемы «Задача-Метод-Алгоритм-Реализация». Однако для дальнейшего развития проекта AlgoWiki потребовалось выделить реализации алгоритмов, ранее включенные в описания свойств алгоритмов, в отдельную сущность. В данной статье изложена схема описания свойств реализаций алгоритмов, также как и модификация изначальной схемы описания свойств самих алгоритмов. Преобразование описаний в энциклопедии AlgoWiki по данной схеме было выполнено для всех страниц проекта, и оно позволяет как более качественно описывать свойства реализаций алгоритмов, так и интегрировать проект энциклопедии AlgoWiki с проектом Algo500, реализующим масштабируемую цифровую платформу для совместного анализа свойств алгоритмов и компьютерных архитектур.

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

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

Рассмотрено моделирование гравитационной задачи N тел с использованием алгоритмов PM и P3M. Реализация алгоритмов для GPU осуществлена с применением вычислительных шейдеров. Предложенный подход использует CPU-код только для синхронизации и запуска шейдеров и не содержит вычислительных частей, реализуемых на CPU; в том числе полностью отсутствует копирование данных между CPU и GPU. Приводятся параллельный алгоритм размещения частиц по ячейкам сетки и параллельный алгоритм распределения масс по узлам сетки. Основой алгоритмов является параллельное построение списков, соответствующих ячейкам сетки. Алгоритмы полностью распараллелены и не содержат частей, исполняемых в один поток. Для расчета одновременно с визуализацией часть вычислений сделана в вершинном шейдере. Выполнить их позволило использование буферных объектов в вершинном шейдере и специально подготовленных данных вместо вершин в качестве входа. Приведены результаты численных расчетов на примере образования галактических скоплений в расширяющейся согласно модели Фридмана плоской вселенной. В качестве модели вселенной брался куб с периодическими краевыми условиями по всем осям. Максимальное число частиц, с которым проводились расчеты, - 108. Для моделирования использовались современный кроссплатформенный API Vulkan и язык GLSL. Результаты расчетов на процессорах Apple M1 и Ryzen 3700X сравниваются с результатами расчетов на обычных видеокартах Apple M1 и NVIDIA RTX 3060. Параллельный алгоритм для CPU реализован с помощью OpenMP. Проведено сравнение производительности алгоритма с результатами других авторов, причем делаются качественные сравнения самих результатов вычислений и сравнение времени работы алгоритмов. Также приведено сравнение времени работы программы для GPU и похожей программы для кластера из многих узлов.