Найти

Результаты поиска

• АППАРАТНО-ОРИЕНТИРОВАННЫЙ МЕТОД УСКОРЕННОГО ПОИСКА ВХОЖДЕНИЙ ОБРАЗЦА НА ОСНОВЕ СТРУКТУРНО-ПРОЦЕДУРНЫХ ВЫЧИСЛЕНИЙ

  Е. А. Титенко , Э.И. Ватутин , М.А. Титенко , А. П. Локтионов , Э.В. Мельник

  2024-11-10

  Аннотация ▼

  Операция поиска вхождений образца в тексте является общезначимой в современных вы-
  числительных средствах при решении проблемно-поисковых задач. Наибольший интерес пред-
  ставляют аппаратно-программные решения, имеющие однородную структуру и регулярные связи
  между вычислительными блоками. Целью работы является сокращение временных затрат на
  поиск вхождений на основе применения параллельного поиска в ассоциативной памяти и метода
  распараллеливания по итерациям. Предлагаемый метод использует ассоциативную память для
  параллельного поиска вхождений и динамическую реконфигурации структуры исходной строки из
  одномерного вида в матричную форму. Вовлечение в реконфигурацию всех элементов влечет из-
  быточные затраты внутренней блочной памяти на последовательный просмотр частичных вхо-
  ждений по одному множеству стартовых позиций, кратных длине образца (второй символьный
  операнд. Вместо этого предложен метод совмещения во времени поиска частичных вхождений по
  двум наборам подстрок, кратных длине образца, с одновременным пропорциональным уменьшени-
  ем элементов разрядного среза ассоциативной памяти по каждому набору, что позволяет на те-
  кущем шаге поиска обрабатывать несколько символов образца. Количественные оценки времени
  поиска определяются количеством операций сравнения и записи подстрок в общем цикле работы,
  а также пропорциями времени данных операций. Показано, что для образцов более 10 элементов
  временной выигрыш составляет примерно в 1,8-2 раза. Данный эффект получен за счет исключе-
  ния шагов последовательного сдвига с переходами между граничными элементами строк. Разра-
  ботанный метод обеспечивает конвейерную обработку потока строковых операндов с совмеще-
  нием просмотра на текущем шаге поиска неединичного множества символов обрабатываемой
  строки. Сокращение времени поиска обеспечивается введением конвейера, количество ступеней которого зависит от коэффициента редукции размера разрядного среза, что позволяет аппарат-
  но реализовать структурно-процедурный подход, применяемый в реконфигурируемых вычисли-
  тельных системах

• РАСШИРЕННАЯ ПРОДУКЦИОННАЯ МАШИНА ВЫВОДА ДЛЯ РЕАЛИЗАЦИИ ПАРАЛЛЕЛЬНЫХ ВЫЧИСЛЕНИЙ

  Е.A. Титенко , И.Е. Чернецкая , М.А. Титенко , Э. В. Мельник , Д. А. Трокоз

  2024-05-28

  Аннотация ▼

  Актуальность. В работе развивается теоретический подход организации параллельных
  вычислений на основе продукционной модели управления потоком данных. Продукционная пара-
  дигма параллельных вычислений имеет необходимые условия построения новых архитектур и ор-
  ганизации высокопроизводительных параллельных вычислений. Рассматриваются продукционные
  системы, управляющие наборами левых частей продукций (образцами). Цель – повышение эффек-
  тивности параллельного вывода решений за счет сокращения непродуктивных затрат времени на
  перебор возможных альтернатив в пространстве графа вывода. Метод решения основан на соз-
  дании расширенной машины символьного вывода для реализации параллельных вычислений. Маши-
  на символьного вывода – это абстрактная система, систематизирующая продукционный вывод
  как последовательность четырех вычислительно-поисковых этапов. Машина вывода задает об-
  щий вид однородной вычислительной системы. Главное отличие – декомпозиция базы продукцион-
  ных правил на отдельные подмножества на основе алгебры продукций и структуризации отноше-
  ний между продукциями. Вместо единой «плоской» структуры предлагается базу продукций де-
  композировать на части – ввести систему независимых подмножеств продукций. Параллельный
  вывод реализуется по отдельным подмножествам без потери общности, при этом перебор воз-
  можных альтернатив является сокращенным. Каждое подмножество продукций имеет специ-
  альное слово-маркер, по значению которого активизируется только одно подмножество продук-
  ций. Оно загружается в операционную часть однородной вычислительной системы для параллель-
  ного исполнения. Результаты. Показано, что количественные оценки сокращения времени вывода
  зависят от общего числа продукций, количества образуемых подмножеств и их размера. Модели-
  рование показало, что даже простейшая декомпозиция на два подмножества (одно подмножест-
  во состоит из 2-х продукций) дает временной выигрыш (1,07-1,52) раз, пропорциональный общему
  числу продукций. Выводы. Построенная расширенная машина символьного вывода является осно-
  вой для последующего создания архитектуры однородной вычислительной системы с комбинацией
  централизованного и локального управления, что позволяет вычислительным блокам однородной
  операционной части параллельно работать без избыточного обращения к обшей памяти.

• АППАРАТНО-ОРИЕНТИРОВАННЫЙ МЕТОД РЕКОНФИГУРАЦИИ ГРУППИРОВКИ ПОДВИЖНЫХ ОБЪЕКТОВ

  Е. А. Титенко , И.Е. Чернецкая , Л. А. Лисицын , М. А. Титенко , С.И. Егоров

  2023-10-23

  Аннотация ▼

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

• ПРЕОБРАЗОВАТЕЛИ УНИТАРНЫХ КОДОВ ДЛЯ ОДНОРОДНЫХ ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМ

  Е.А. Титенко

  104-115

  2025-11-10

  Аннотация ▼

  Актуальность. Эффективная работа вычислительных систем, в том числе, основывается на общезначимых обеспечивающих вычислениях по планированию параллельных вычислений и анализу результатов. Достаточно важными вычислительными средствами являются преобразователи (формирователи) унитарных кодов, совмещающих свойства числовой и символьной информации. Цель работы – создание высокопроизводительных вычислительных схем для обработки унитарных кодов на единой теоретической основе. Методы исследования. Известные одномерные и двумерные итерационные сети являются основой для создания однородных преобразователей унитарных кодов. Такие сети имеют необходимые и достаточные условия для организации параллельных вычислений. Для синтеза преобразователей унитарных кодов были выделены следующие принципы обработки, свойственные для чисел и строк: двунаправленность обработки, разбиение на множество локальных процессов с собственными стартовыми точками, иерархия, мультифункцинальность, дуализм цифра/символ. Описанные преобразователи используют известные и привносят новые схемотехнические решения. Описаны цифровой компрессор, формирователь серии логических «1», арбитр, пороговый элемент весовых и унитарных кодов. Результаты и обсуждения. Созданы практически значимые схемы прямых и обратных преобразователей кодов «8-4-2-1 – нормализованный код», используемые в однородных вычислительных системах – мультипроцессорах, ассоциативных процессорах и др. Количественные оценки преобразователей унитарных кодов проведены для порогового элемента весового и унитарного кодов. Данный преобразователь основан на дуальной трактовке элементов кода как цифры или символа, что позволило на завершающей фазе вычислений (против стандартного метода) исключить линейную временную зависимость для вычисления результата сравнения двух кодов. Показано, что для унитарных кодов размеров от 12 до 36 бит временной выигрыш составляет 14-16%. Данный эффект получен за счет исключения последовательных вычислений между ячейками итерационной сети. Выводы. Для построения эффектных по времени схем преобразования унитарных кодов использован и развит аппарат итерационных сетей, на основе которых созданы одномерные, двумерные итерационные сети с регулярными связями, а также преобразователи на основе универсальных логических модулей.

• АППАРАТНО-ПРОГРАММНЫЕ СРЕДСТВА ДИНАМИЧЕСКОЙ РЕКОНФИГУРАЦИИ ГРУППИРОВКИ МАЛЫХ КОСМИЧЕСКИХ АППАРАТОВ

  С.Г. Емельянов , С.Н. Фролов , Е.А. Титенко , Д.П. Тетерин , А.П. Локтионов

  2024-08-12

  Аннотация ▼

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

• АРХИТЕКТУРА НЕЙРОННЫХ СЕТЕЙ НА ОСНОВЕ КОДОВ НА ГРАФАХ

  В.С. Усатюк , С.И. Егоров , А.П. Локтионов , Е. А. Титенко , И.Е. Чернецкая

  2023-12-11

  Аннотация ▼

  Одним из важных достижений теории помехоустойчивого кодирования является
  открытие кодов на графах и их важного подмножества низкоплотностных кодов
  (LDPC-кодов). Используя проверочную матрицу кода на графе, можно получить марков-
  ское случайное поле. LDPC-код может быть вложен в модель Изинга (разновидность мар-
  ковского случайного поля) путем использования топологии тора с отрицательной
  кривизной. При этом кодовые слова соответствуют седловым точкам (экстремумам) в
  модели, а треппин-сеты соответствуют локальным минимумам. Использование
  LDPC-кодов с увеличенным кодовым расстоянием позволяет максимально разнести седло-
  вые точки, и таким образом повысить устойчивость нейронной сети к шуму и мощность
  представления. При этом блочная и разряженная структура, характерная для тора отри-
  цательной кривизны, упрощает мультиплексирование и снижает число обучаемых пара-
  метров нейронной сети. Целью исследования являются снижение вычислительной сложно-
  сти и увеличение точности нейронных сетей за счёт применения априорных структурных
  (квазициклических) разряженных графов для широкого класса задач машинного обучения на
  марковских случайных полях. В работе представлен новый подход, позволяющий осуществлять синтез архитектур нейронных сетей на основе кодов на графах. Предложенный под-
  ход осуществляет эффективное представление марковских случайных полей за счёт при-
  менения разряженных блочных (квазициклических) матриц (тензоров). Предложенный под-
  ход позволяет снизить число обучаемых параметров и логарифмически снизить слож-
  ность мультиплексирования тензора. Полученная на основе предложенного подхода архи-
  тектура трансформера в задаче поиска пути (pathfinder) с конкурса трансформеров (long
  range arena) заняла пятое место по точности классификации изображений 94.95% (1.72%
  от первого места) при значительно меньшей сложности (число параметров (умножений)
  синтезированной сети меньше в более чем 5 раз). Применение предложенного подхода к
  задачам факторизации на плотных графах, сетевых задачах, поверхностных сетках, кова-
  риационных матрицах позволило увеличить точность реконструкции по метрике Фробе-
  ниуса (на отдельных задачах на 8 порядков) в сочетание с упрощением структуры мульти-
  плексора в сравнение с методами усеченного сингулярного разложения TSVD и хордовой
  разряженной факторизации.

• МЕТОД ОБЕСПЕЧЕНИЯ ЗАЩИТЫ ПЕРЕДАВАЕМЫХ СООБЩЕНИЙ В СИСТЕМЕ ADS-B С ИСПОЛЬЗОВАНИЕМ АППАРАТА КЛЕТОЧНЫХ АВТОМАТОВ

  Д. М. Зарубин , В. П. Добрица , Е.A. Титенко

  2023-02-17

  Аннотация ▼

  Цель исследования – разработка метода кодирования передаваемых ADS-B сообще-
  ний между воздушными судами в процессе полета. Открытый формат 1090ES передавае-
  мых данных является критическим в плане проведения различных типов атак, которые
  могут привести к нарушению безопасности полетов воздушных судов. Работа направлена
  на применение средств кодирования и декодирования сообщений с закрытым ключом. Ме-
  тоды исследования основаны на применении и развитии потокового шифрования данных с
  использованием одномерных клеточных автоматов. Они работают в режиме генератора
  псевдослучайных последовательностей, преобразующих элементарных состояний ячейки
  одномерного клеточного автомата на основе типовых аппаратно-ориентированных опе-
  раций. В основу процессов кодирования и декодирования полей данных положена аналити-
  ческое выражение, использующее типовые логические операции (дизъюнкция, сумма по
  модулю два). Это свойство позволяет вести параллельную обработку полей данных сооб-
  щения и создавать неповторяющиеся последовательности кодов. Результаты – создан
  метод обеспечения защиты передаваемых данных, дополнительно кодирующий на передаче
  и декодирующий на приеме сообщения. Отличительная особенность метода – сохранение
  формата протокола. Выполнена оценка вычислительной сложности работы клеточного
  автомата. Метод использует одномерный клеточный автомат, который выполняет ко-
  дирование и декодирование целевых полей (координаты, курс и др.) с использованием гене-
  ратора псевдослучайных чисел. Разработанный метод относится к классу аппаратно-
  ориентированных методов. Критические для кодирования и декодирования свойства пе-
  риодичности полей данных и длины ключа устраняются путем выбора начального ирра-
  ционального значения и организации «потоковой» работы кодировщика. Если кодирующий
  автомат работает в потоковом режиме, текущее значение зависит от предыстории
  некоторой глубины, определение длины «автоматического ключа» из ADS-B сообщениябудет алгоритмически невозможно в силу потери данных. Линейная сложность метода
  позволяет выполнять преобразования со скоростью потока передачи данных. Вывод – раз-
  витие аппаратно-ориентированных методов шифрования данных позволяет повысить
  эффективность использования системы ADS-B за счет противодействия различным ти-
  пам деструктивных акций.

• РЕКОНФИГУРАЦИОННЫЕ МЕТАГРАММАТИКИ ДЛЯ ОПИСАНИЯ И МОДЕЛИРОВАНИЯ МНОГОЭТАПНЫХ КОМПЛЕКСНЫХ АТАК

  О.И. Атакищев , В.Г. Грибунин , В.Е. Ананьев , Е.А. Титенко

  2023-02-17

  Аннотация ▼

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

• КОММУТАЦИОННАЯ МОДЕЛЬ ПАРАЛЛЕЛЬНЫХ СРАВНЕНИЙ ЭЛЕМЕНТОВ ДЛЯ ПРОДУКЦИОННЫХ СИСТЕМ, УПРАВЛЯЕМЫХ ПОТОКОМ ДАННЫХ

  E.A. Титенко, E.В. Талдыкин

  2021-02-25

  Аннотация ▼

  В статье достигается цель - сокращение временных затрат на генерацию сочетаний
  элементов множества. Элементы множества формируются из образцов (левых частей) про-
  дукционных правил. Основная задача заключается в построении эффективных по времени схем
  (алгоритмов) параллельной генерации сочетаний элементов массива. Применительно к продук-
  ционным системам такие схемы необходимы для активации подмножества продукций, приме-
  нимых к символьным данным на текущем шаге. За основу взят и развит известный алгоритм
  параллельного пузырька. Схема коммутации «параллельный пузырек» состоит из двух чере-
  дующихся вариантов коммутации элементов в пары. Эти коммутации основаны на локальном
  объединении в пары элементов массива, имеющих смежные индексы. Такое локальное объеди-
  нение элементов в пары приводит к «малым» перемещениям элементов по длине массива и ре-
  гулярному характеру генерации пар. В каждой паре выполняется операция сравнения-обмена
  операндов. Для продукционных систем операция сравнения сводится к поиску пересечений об-
  разцов и формированию списка конфликтных слов. Сокращение времени генерации сочетаний
  основывается на построении вариантов коммутации с распределенным объединением элемен-
  тов в пары с шагом, равным 4. Разработанная схема коммутации содержит на нечетных ша-
  гах коммутации с локальным объединением элементов в пары. На четных шагах выполняется
  коммутация-ускоритель с распределенным объединением элементов в пары. Моделирование
  работы разработанной схемы коммутации осуществлялось на типовых задачах сортировки и
  полного перебора пар элементов. Установлено сокращение временных затрат по сравнению с
  четно-нечетной сортиовкой на 15-18%. В работе определена линейная зависимость времени
  сортировки с углом наклона меньше 1. Это позволяет использовать схему коммутации для
  продукционных систем большого размера. Локальные и распределенные связи в схеме коммута-
  ции сохраняют свойство регулярности. Эта особенность определяет аппаратную реализацию
  схемы в виде параллельного коммутатора с естественным масштабированием. Данная схема
  может использоваться в специализированном продукционном устройстве для декомпозиции
  продукционной системы на независимые подмножества продукций.