Программные продукты и системы

Статьи журнала №4 2023

1. Выделение из многоуровневого представления системы булевых функций  подсистем для совместной логической минимизации [№4 за 2023 год]
Авторы: Бибило П.Н. (bibilo@newman.bas-net.by) - Объединенный институт проблем информатики Национальной академии наук Беларуси (профессор, зав. лабораторией), доктор технических наук; Кириенко Н.А. (kir@newman.bas-net.by) - Объединенный институт проблем информатики Национальной академии наук Беларуси (старший научный сотрудник), кандидат технических наук; Романов В.И. (rom@newman.bas-net.by) - Объединенный институт проблем информатики Национальной академии наук Беларуси (доцент, ведущий научный сотрудник), кандидат технических наук;
Аннотация: В статье приводятся результаты экспериментальных исследований эффективности программ минимизации многоуровневых алгебраических представлений систем булевых функций, выполняемых при синтезе комбинационных схем. Результирующие минимизированные логические описания представлены в виде формул разложений Шеннона или формул, задающих булевы сети. Исследуются три подхода: совместная минимизация многоуровневых представлений систем булевых функций, раздельная минимизация и выделение из исходной системы связанных подсистем. При этом каждая из этих подсистем минимизируется отдельно, а функции, составляющие их, совместно. После получения минимизированных описаний схем, заданных в виде совокупности взаимосвязанных формул разложения Шеннона либо двухоперандных логических уравнений, соответствующих булевым сетям, осуществляется синтез логических схем в одной и той же библиотеке проектирования заказных цифровых сверхбольших интегральных схем, выполненных по КМОП СБИС (комплементарной метал-оксид-полупроводник технологии). Полученные логические схемы сравниваются по площади кристалла и по быстродействию (временной задержке). Были проведены эксперименты на 39 промышленных примерах схем. Pезультаты показали конкурентоспособность и целесообразность использования на практике всех трех рассмотренных подходов. Улучшение параметров схем (площадь, временная задержка) при выделении из исходной системы связанных подсистем достигается за счет того, что каждая выделенная подсистема минимизируется на основе разложений Шеннона по своей (для каждой подсистемы) перестановке переменных разложения. При этом для одной половины схем более эффективным является минимизация многоуровневых представлений на основе разложений Шеннона для исходных матричных описаний систем функций, а для другой – на основе разложений Шеннона систем функций, представленных в виде логических уравнений. Практическая значимость проведенного исследования заключается в том, что использование разработанной программы, реализующей предложенный алгоритм выделения подсистем булевых функций, позволяет во многих случаях сокращать площадь и увеличивать быстродействие функциональных блоков заказных КМОП СБИС.
Ключевые слова: кмоп-технология, сбис, vhdl, синтез логической схемы, булева сеть, BDD, дизъюнктивная нормальная форма, многоуровневое представление, система булевых функций
Keywords: cmos, vlsi, vhdl, digital logic synthesis, Boolean net, Binary Decision Diagram (BDD), disjunctive normal form, disjunctive normal form (DNF), the system of boolean functions
Просмотров: 3890

2. Quantum algorithmic gate-based computing: Grover quantum search algorithm design in quantum software engineering [№4 за 2023 год]
Авторы: Ulyanov S.V. (ulyanovsv46_46@mail.ru) - Государственный университет «Дубна» – Институт системного анализа и управления, Объединенный институт ядерных исследований – лаборатория информационных технологий (профессор), доктор физико-математических наук; Ulyanov V.S. (ulyanovik@mail.ru) - Московский государственный университет геодезии и картографии (МИИГАиК) (доцент), кандидат технических наук;
Abstract: The difference between classical and quantum algorithms (QA) is following: problem solved by QA is coded in the structure of the quantum operators. Input to QA in this case is always the same. Output of QA says which problem coded. In some sense, give a function to QA to analyze and QA returns its property as an answer without quantitative computing. QA studies qualitative properties of the functions. The core of any QA is a set of unitary quantum operators or quantum gates. In practical representation, quantum gate is a unitary matrix with particular structure. The size of this matrix grows exponentially with an increase in the number of inputs, which significantly limits the QA simulation on a classical computer with von Neumann architecture. Quantum search algorithm (QSA) – models apply for the solution of computer science problems as searching in unstructured data base, quantum cryptography, engineering tasks, control system design, robotics, smart controllers, etc. Grover’s algorithm is explained in details along with implementations on a local computer simulator. The presented article describes a practical approach to modeling one of the most famous QA on classical computers, the Grover algorithm.
Keywords: quantum operators design, quantum algorithmic gate, quantum circuits, quantum search algorithms
Ключевые слова: синтез квантовых операторов, квантовые алгоритмические вентили, квантовые схемы, алгоритмы квантового поиска
Просмотров: 3271

3. Поиск решения задачи целочисленного программирования с помощью итеративного округления координат [№4 за 2023 год]
Авторы: Иванов А.В. (lexuzieel@gmail.com) - Тверской государственный технический университет (аспирант); Матвеев Ю.Н. (matveev4700@mail.ru) - Тверской государственный технический университет (профессор), доктор технических наук;
Аннотация: В статье предлагается алгоритм поиска целочисленного решения, использующий идею округления координат точки оптимального нецелочисленного решения и построения луча, направленного вглубь области допустимого решения. Алгоритм основан на итеративном процессе округления координат точки в направлении построенного луча. В ходе исследования обнаружено, что движение в сторону направления луча без перебора всех возможных вариантов упрощает алгоритм и позволяет избежать ветвления. Это выделяет данный подход из других существующих на данный момент открытых методов, таких как методы отсечений и ветвей и границ. В процессе работы осуществлялись описание и экспериментальная проверка данного алгоритма и возможности его применения при разных конфигурациях области допустимых решений. Теоретическая значимость исследования заключается в разработке нового алгоритма, который не требует выполнения симплекс-метода на каждом этапе и на каждом шаге использует луч вместо плоскости, что предотвращает рост пространственной сложности задачи по сравнению с другими методами. В ходе исследования стало видно, что предложенный алгоритм имеет ограничения, однако основная идея доказала свою работоспособность, и в дальнейшем планируется развивать ее.
Ключевые слова: покоординатный спуск, алгоритм, оптимизация, целочисленное программи-рование, линейное программирование, математическое программирование
Keywords: coordinate descent, algorithm, optimisation, , linear programming, mathematical programming
Просмотров: 3692

4. Автоматическая локализация ошибок времени выполнения в программном обеспечении с помощью нейронных сетей [№4 за 2023 год]
Авторы: Достовалова А.М. (dost.bmstu99@gmail.com) - Концерн «Моринсис-Агат», Федеральный исследовательский центр «Информатика и управление» РАН (техник-программист, инженер-исследователь); Шерминская А.А. (SherminskayaAA@yandex.ru) - Концерн «Моринсис-Агат» (начальник сектора);
Аннотация: Разработан метод автоматической локализации ошибок времени выполнения с помощью нейронной сети по данным трассировки осуществления функций программы. Метод сопоставляет каждой функции вероятность содержания ошибки, которая считается пропорциональной степени влияния значений параметров функции на результат выполнения программы. Влияние параметров определяется численной характеристикой (весом), вычисляемой по алгоритму Хашема. Метод применялся для отладки нескольких программ, различных по типам и причинам возникновения ошибок времени выполнения. Ошибки были расположены во вложенных функциях и проявлялись при определенных значениях входных данных. В каждой программе проведено сопоставление наиболее вероятных мест возникновения ошибок, которые определил метод, с их реальными местоположениями. Особенностями разработанного метода являются возможность работы с вложенными функциями, локализация множественных ошибок, а также ошибок, у которых место возникновения и место проявления в программе не совпадают. Во всех случаях параметры, содержащие ошибку, имели больший вес в сравнении с остальными, даже если ошибок в программе было несколько. При этом метод выделяет в программе полный путь ошибки, включающий в себя все параметры, связанные с ее возникновением. Благодаря этому с помощью предложенного метода можно определять положение логических ошибок в программах. Метод может применяться для отладки как программного, так и аппаратного обеспечения технических систем, поскольку логика его работы не зависит от источника исходных данных.
Ключевые слова: трассировка, нейронные сети, отладка ПО, ошибки времени выполнения, автоматическая локализация ошибок
Keywords: tracing, neural network, program debugging, runtime error, automatic bug localization
Просмотров: 3708

5. Создание инструментария для векторизации тела плоского цикла с помощью векторных инструкций AVX-512 [№4 за 2023 год]
Авторы: Рыбаков А.А. (rybakov@jscc.ru ) - Межведомственный суперкомпьютерный центр РАН – филиал ФНЦ НИИСИ РАН (ведущий научный сотрудник), кандидат физико-математических наук; Швиндт А.Н. (shvindt@ispras.ru) - Институт системного программирования им. В.П. Иванникова РАН (ИСП РАН) (докторант), кандидат технических наук;
Аннотация: Работа направлена на изучение подходов по сокращению времени исполнения программ с помощью инструкций из набора AVX-512 для повышения эффективности векторизации программного кода. Векторизация является основной низкоуровневой оптимизацией, с помощью которой возможно кратно ускорить выполнение программы, а набор инструкций AVX-512 обладает рядом уникальных особенностей, позволяющих применять векторизацию в сложных программных контекстах. В работе исследуется программный контекст специального вида – плоский цикл, который при удовлетворении ряда требований может быть векторизован с помощью инструкций AVX-512 при практически произвольной сложности тела. Однако довольно часто оптимизирующий компилятор не в состоянии выполнить автоматическую векторизацию плоских циклов по причине наличия в них сложного управления, вызовов функций, гнезд циклов и других конструкций. Это приводит к тому, что векторизацию приходится выполнять вручную с использованием специальных функций-интринсиков. Эффективность векторизации напрямую зависит от плотности масок векторных операций, которые оказываются разреженными при сильно разветвленном управлении внутри тела плоского цикла. В работе предлагается инструментарий, позволяющий параллельно создавать скалярную и векторную версии плоского цикла и анализировать эффективность выполненной векторизации. При этом поддерживаются два режима сборки тестируемого кода: скалярная версия с эмуляцией и мониторингом векторных инструкций и векторная версия для исполнения на целевой машине. С одной стороны, это позволяет контролировать корректность выполненных преобразований кода, а с другой – отслеживать пути исполнения программы с низкой вероятностью для их локализации или выноса из тела цикла. С помощью созданного инструментария удалось выделить горячие плоские циклы ряда реальных приложений и повысить эффективность их векторизации.
Ключевые слова: компьютерные приложения, низкоуровневая оптимизация, avx-512, плоский цикл, векторизация
Keywords: computer applications, low-level optimization, avx-512, flat loop, vectorization
Просмотров: 3399

6. Разработка модели жизненного цикла мобильных приложений для людей с ограниченными интеллектуальными возможностями [№4 за 2023 год]
Авторы: Гурьев В.В. (vladgurjev@mail.ru) - Волгоградский государственный технический университет (аспирант); Шабалина О.А. (o.a.shabalina@gmail.com) - Волгоградский государственный технический университет (доцент), кандидат технических наук; Садовникова Н.П. (npsn1@ya.ru) - Волгоградский государственный технический университет (профессор), доктор технических наук; Воронина А.А. (angelina.vaa@gmail.com) - Волгоградский государственный технический университет (аспирант);
Аннотация: В статье рассмотрены модели жизненного цикла мобильных приложений и программные средства поддержки их разработки. Описаны особенности создания мобильных приложений, доступных для людей с ограниченными интеллектуальными возможностями. Одним из способов повышения доступности приложений является их адаптируемость. Такая настройка может потребовать поддержки динамического контента приложения, поэтому данные возможности необходимо предусматривать уже на этапах проектирования и реализации. Предложена модель жизненного цикла мобильных приложений для людей с ограниченными интеллектуальными возможностями, обеспечивающая сквозную поддержку этапов проектирования, реализации и эксплуатации. Разработана технология проектирования мобильных приложений на основе многомодульной архитектуры, включающая применение готовых архитектурных шаблонов для генерации базового кода приложения и повторное использование успешных проектных решений. Представлена технология проектирования адаптируемого интерфейса мобильных приложений, включающая разработку шаблонов экранов приложения, разделение элементов шаблонов на обязательные и опциональные элементы, сопоставление каждому элементу предопределенного набора возможных визуальных представлений на экране и прикрепление всех элементов по месту. Разработана система управления мобильными приложениями на основе CALS-технологии сквозной поддержки этапов проектирования, реализации и эксплуатации адаптируемых мобильных приложений. Предложен способ адаптации интерфейса мобильного приложения с помощью конфигурационной панели, встраиваемой в систему управления. Описан пример применения предложенных моделей, технологий и средств к разработке мобильной игры для тренировки навыков совершения покупок для людей с ограниченными интеллектуальными возможностями. Показано, что применение разработанной системы управления мобильными приложениями позволяет существенно сократить временные затраты на разработку приложений. Возможность применения шаблонов архитектур и готовых решений расширяет круг пользователей системы и делает ее доступной разработчикам, профессиональная деятельность которых связана с поддержкой людей с ограниченными интеллектуальными возможностями.
Ключевые слова: адаптируемое мобильное приложение, пользователи с ограниченными интеллектуальными возможностями, MADLC-модель, модель жизненного цикла, жизненный цикл мобильных приложений
Keywords: adaptable mobile application, user with intellectual disabilities, MADLC model, mobile application life cycle model, mobile application life cycle
Просмотров: 2986

7. Моделирование динамики гидроприводов в системах виртуального окружения [№4 за 2023 год]
Автор: Страшнов Е.В. (strashnov_evg@mail.ru) - Федеральное государственное учреждение «Феде-ральный научный центр Научно-исследовательский институт системных исследований Российской академии наук» (ФГУ ФНЦ НИИСИ РАН) (научный сотрудник); Мироненко И.Н. (vstudio@niisi.ras.ru) - Федеральное государственное учреждение «Феде-ральный научный центр Научно-исследовательский институт системных исследований Российской академии наук» (ФГУ ФНЦ НИИСИ РАН) (научный сотрудник);
Аннотация: Системы виртуального окружения активно применяются во многих областях деятельности человека. В частности, широкое распространение получили виртуальные (компьютерные) тренажеры для моделирования и управления сложными механическими системами. Некоторые из таких систем оснащены гидроприводами в качестве исполнительных устройств. В данной работе рассматривается задача моделирования динамики гидроприводов в системах виртуального окружения в масштабе реального времени. Предлагаемое решение этой задачи базируется на подходе, когда осуществляется совместное моделирование динамики гидропривода и системы шарнирно связанных тел. Для этого задействован метод последовательных импульсов, в рамках которого получены ограничения относительно координат и скоростей поршня и двух связанных тел. Идея такого подхода состоит в том, что сначала путем интегрирования уравнений гидравлики с помощью полунеявной схемы Эйлера вычисляется скорость движения поршня без учета нагрузки, а затем эта скорость корректируется с помощью импульса, который обеспечивает ограничения скоростей поршня и двух связанных тел. Предлагаемый подход является итерационным и позволяет реализовать динамику систем шарнирно связанных тел с гидроприводом в масштабе реального времени. Основной результат заключается в том, что разработанный подход является универсальным и позволяет обрабатывать все ограничения в системе тел единым образом. В отличие от других аналогичных методов он не требует громоздких матричных вычислений и решения систем линейных уравнений большой размерности. Апробация в созданном программном комплексе VirSim показала адекватность и эффективность предложенных решений. Практическая значимость работы заключается в том, что предложенные методы и подходы для моделирования динамики гидроприводов могут быть использованы при реализации тренажеров, предназначенных для обучения операторов навыкам управления роботами, машинами различного типа, механизмами, техникой и т.д.
Ключевые слова: система виртуального окружения, полунеявная схема Эйлера, метод последовательных импульсов, гидрораспределитель, гидропривод, моделирование динамики
Keywords: virtual environment systems, semi-implicit Euler scheme, sequential impulses method, directional control valve, hydraulic actuator, dynamics modeling
Просмотров: 2959

8. Идентификация фейк-новостей с помощью веб-ресурса на основе нейронных сетей [№4 за 2023 год]
Авторы: Тумбинская М.В. (tumbinskaya@inbox.ru) - Казанский национальный исследовательский технический университет (доцент), кандидат технических наук; Галиев Р.А. (renat5390@yandex.ru) - Казанский национальный исследовательский технический университет им. А.Н. Туполева (студент);
Аннотация: Активное распространение информации средствами телекоммуникаций обусловило актуальность проблемы идентификация фейк-новостей на основе их заголовков. Целью данного исследования является повышение уровня достоверности информации пользователей в браузерной среде. Достижение ее возможно путем автоматизированного распознавания фейк-новостей на основе их заголовков в браузерной среде. В работе предложено использовать нейронные сети, которые позволяют проводить семантический анализ заголовков фейк-новостей и обрабатывать большие объемы данных. В статье рассмотрены популярные зарубежные и отечественные веб-ресурсы по идентификации фейк-новостей, их отличительные особенности. Проведены анализ и выбор нейросетевых моделей BERT-MLP, BERT-CNN, BERT-LSTM, которые были заложены в основу разработки веб-ресурса. Для обучения нейросетевых моделей использованы выборки русскоязычных заголовков новостей. Про-ведено экспериментальное исследование оценки качества и адекватности нейросетевых моделей на тестовых и валидационных выборках данных, в том числе на новостных заголовках различных тематик. Исходя из результатов оценки, разработанный веб-ресурс, в основу которого заложены модели BERT-CNN, BERT-GRU, BERT-LSTM, показал высокую результативность. Достоверность идентификации фейк-новостей составила 86,29 %. Практическая ценность работы заключается в том, что созданный веб-ресурс может быть использован в качестве инструмента для распознавания фейк-новостей специалистами по противодействию деструктивным политическим технологиям, а также специалистами по информационной безопасности. Для повышения точности классификации целесообразно расширить обучающую выборку данных, что позволит выявлять в данных более сложные зависимости.
Ключевые слова: нелегитимные новости, веб-ресурс, заголовок новости, lstm, GRU, CNN, BERT, нейросетевая модель, фейк-новость
Keywords: illegitimate news, web resource, news headline, lstm, GRU, CNN, BERT, a neural network, fake news
Просмотров: 3276

9. Интеграция методов обучения с подкреплением и нечеткой логики для интеллектуальных систем реального времени [№4 за 2023 год]
Авторы: Еремеев А.П. (eremeev@appmat.ru) - Национальный исследовательский университет «Московский энергетический институт» (профессор), доктор технических наук; Сергеев М.Д. (SergeevMD@mpei.ru) - Национальный исследовательский университет «Московский энергетический институт» (аспирант); Петров В.С. (PetrovVS@mpei.ru) - Национальный исследовательский университет «Московский энергетический институт» (студент);
Аннотация: В данной работе рассмотрены возможности интеграции методов обучения с подкреплением и нечеткой логики в плане повышения эффективности алгоритмов обучения с подкреплением. Главное внимание уделяется применению таких интегрированных методов в интеллектуальных системах реального времени, особенно в системах поддержки принятия решений для мониторинга и управления сложными техническими объектами. Как основа используется метод обучения с подкреплением на базе темпоральных различий, состояние среды и сигнал вознаграждения формируются с применением нечеткой логики. Представлена программная реализация и приводятся данные компьютерного моделирования методов глубокого обучения с подкреплением на основе темпоральных различий, полученные при сравнительном анализе алгоритма на основе нечеткой логики и алгоритмов на основе нейронных сетей. Показано, что основными достоинствами алгоритмов обучения с подкреплением с применением нечеткой логики являются: эффективность обучения, выражающаяся в минимизации количества эпизодов, что особенно важно, когда доступность данных для обучения ограничена или обучение в реальном времени требует быстрой адаптации; устойчивость к шуму и выбросам в данных, что важно в реальных средах, где присутствуют шумы или изменяются данные; интерпретируемость – алгоритмы с нечеткой логикой предоставляют интерпретируемые правила и выводы на основе нечеткой логики; расширение области применения обучения с подкреплением на предметные/проблемные области и задачи с непрерывным пространством состояний. Данные исследования и разработки выполняются в рамках конструирования интеллектуальных систем поддержки принятия решений реального времени. Эти системы предназначены для помощи оперативно-диспетчерскому персоналу (лицам, принимающим решения) при мониторинге и управлении сложными техническими и организационными системами в условиях достаточно жестких временных ограничений и при наличии различного типа неопределенностей (неточности, нечеткости, противоречивости) в поступающей в систему информации, то есть так называемых зашумленных данных.
Ключевые слова: поддержка принятия решений, реальное время, интеллектуальная система, нечеткая логика, обучение с подкреплением, искусственный интеллект
Keywords: decision support, real time, intellectual system, fuzzy logic, time, reinforcem ent learnin, artificial intelligence
Просмотров: 4002

10. Использование библиотеки MPI для параллельной реализации алгоритма полного перебора вариантов [№4 за 2023 год]
Авторы: Ай Мин Тайк (ayeminthike52@gmail.com) - Национальный исследовательский университет «МИЭТ» (докторант), кандидат технических наук; Лупин С.А. (lupin@miee.ru) - Национальный исследовательский университет «МИЭТ», Межведомственный суперкомпьютерный центр РАН (профессор), кандидат технических наук; Федяшин Д.А. (fedyashinda@gmail.com) - Национальный исследовательский университет «МИЭТ» (начальник ВЦ);
Аннотация: В работе представлены результаты исследования эффективности параллельного приложения для решения задачи квадратичного назначения. Приложение использует алгоритм полного перебора и интерфейс пере-дачи сообщений (MPI) для организации взаимодействия процессов в распределенной вычислительной среде. Для генерации вариантов решений использован метод лексикографической перестановки, который хорошо распараллеливается и обеспечивает балансировку нагрузки узлов. Для расширения диапазона использования алгоритма перебора на оптимизационные задачи большой размерности пространство поиска решений разбивается на части, что позволяет существенно сократить число рассматриваемых вариантов. Эксперименты проводились в распределен-ной среде, содержащей 50 узлов с процессорами Intel ® Core™ i5 7-го поколения. Параллельное приложение при решении задачи большой размерности (n = 24) продемонстрировало достижимость ускорения вычислений в диапазоне от 99 до 95 % от максимально возможного, причем во всех случаях было найдено точное решение. Это подтверждает корректность методов, использованных для распределения нагрузки и снижения вычислительной сложности задач. Дальнейшая работа будет направлена на исследование возможности применения предлагаемых подходов при реализации алгоритма перебора и в виде гибридных приложений, что актуально для гетерогенных вычислительных сред. Поскольку задача квадратичного назначения относится к задачам дискретной оптимизации, полученные результаты дают основание считать, что предлагаемые решения будут эффективными и для других задач этого класса.
Ключевые слова: hpc, mpi, распределенные вычисления, алгоритм полного перебора, задача квадратичного назначения, дискретная оптимизация
Keywords: hpc, MPI, distributed computing, brute-force algorithm, quadratic assignment problem, combinatorial optimization
Просмотров: 3570

| 1 | 2 | Следующая → ►