автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.11, диссертация на тему:Методы и средства оптимизации автоматных моделей поиска информационных структур в потоке данных для реализации на реконфигурируемых вычислительных системах

На правах рукописи

Ильченко Дмитрий Николаевич

Методы и средства оптимизации автоматных моделей поиска информационных структур в потоке данных для реализации на реконфигурируемых вычислительных системах

Специальность 05.13.11 - Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей

Автореферат

диссертации на соискание ученой степени кандидата технических наук

1 6 ОКТ 2014

Таганрог - 2014

005553367

005553367

Работа , выполнена в Федеральном государственном автономном образовательном учреждении высшего профессионального образования «Южный федеральный университет» (ЮФУ) на кафедре «Интеллектуальные и многопроцессорные системы» (ИМС) и в Научно-исследовательском институте многопроцессорных вычислительных систем имени академика A.B. Каляева федерального государственного автономного образовательного учреждения высшего профессионального образования «Южный федеральный университет» (НИИ МВС ЮФУ).

НАУЧНЫЙ РУКОВОДИТЕЛЬ: доктор технических наук, профессор,

Левин Илья Израилевич

ОФИЦИАЛЬНЫЕ ОППОНЕНТЫ: Фатхи Владимир Ахатович,

доктор технических наук, профессор, ФГБОУ ВПО «Донской государственный технический университет», заведующий кафедрой «Вычислительные системы и информационная безопасность»

Титенко Евгений Анатольевич, кандидат технических наук, доцент, ФГБОУ ВПО «Юго-Западный государственный университет», кафедра «Информационные системы и технологии»

ВЕДУЩАЯ ОРГАНИЗАЦИЯ: ОАО «Научно-исследовательский

центр электронной вычислительной техники», г. Москва

Защита диссертации состоится «2Л_» ноября 2014 г. в 1420 на заседании диссертационного совета Д 212.208.24 при Южном федеральном университете по адресу: г. Таганрог, ул. Чехова, 2, корп. "И", комн. 347.

С диссертацией можно ознакомиться в библиотеке и на сайте Южного федерального университета, http://hub.sfedu.ru/diss/

Автореферат разослан «tö » октября 2014 г.

Ученый секретарь диссертационного совета А.П. Кухаренко

кандидат технических наук, доцент

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

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

Традиционные вычислительные системы, такие как многопроцессорные системы и графические ускорители, имеют жесткую архитектуру и при решении такого класса задач показывают невысокую реальную производительность.

Наиболее эффективным в данном случае является использование специализированных вычислителей на основе заказных специализированных интегральных схем (ASIC), имеющих максимальную производительность, но изменение алгоритмов поиска приведет к необходимости повторного производства таких микросхем.

Более целесообразным является использование реконфигурируемых вычислительных систем (РВС) на базе программируемых логических интегральных схем (ПЛИС). За счет адаптации архитектуры вычислителя под структуру решаемой задачи такие системы позволяют достичь высокой реальной производительности. Если в кластерных системах задача представляет собой набор процедур, которые последовательно выполняются на разных процессорах, то в РВС все вычислительные устройства аппаратно объединены для реализации информационного графа решаемой задачи. Это позволяет на одной аппаратной платформе решать задачи различных предметных областей с высокой производительностью.

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

создания автоматных моделей поиска информационных структур в потоке данных для их дальнейшей реализации на РВС.

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

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

Целью работы является повышение удельной производительности РВС при решении задач поиска информационных структур в потоках данных в режиме реального времени.

Объектом исследований являются методы оптимизации цифровых автоматных моделей поиска информационных структур.

Научная задача, решаемая в диссертационной работе, - создание методов оптимизации логической структуры автоматных моделей поиска информационных структур, направленных на сокращение аппаратного ресурса РВС для их реализации при заданной скорости входного потока данных.

Для достижения указанной цели необходимо решить следующие задачи:

1) провести анализ классических алгоритмов поиска, традиционных методов минимизации и синтеза цифровых автоматов для реализации на РВС;

2) разработать принципы структурной организации вычислений для обеспечения поиска информационных структур в потоке данных в реальном масштабе времени;

3) разработать методы оптимизации автоматных моделей поиска информационных структур, направленные на повышение удельной производительности пугем сокращения аппаратных ресурсов РВС, используемых для их реализации;

4) разработать программное обеспечение для генерации и оптимизации автоматных моделей поиска информационных структур в потоке данных, позволяющее сократить время их отладки и оптимизации;

5) выполнить синтез вычислительных структур поиска на РВС и провести анализ эффективности разработанных методов оптимизации автоматных моделей.

Методы исследований. В ходе исследований были использованы основы теории цифровых автоматов, теории графов, методы структурного синтеза автоматов, параллельно-конвейерной организации вычислений. Практические исследования проведены на реконфигурируемых вычислительных системах различных архитектур и конфигураций.

Достоверность и обоснованность полученных в диссертационной работе научных результатов подтверждены корректностью и непротиворечивостью математических выкладок, а также вычислительными экспериментами на ряде

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

Научная новизна диссертационной работы состоит в том, что в ней

разработаны:

1) метод векторизации вершин состояний цифровых автоматов, отличаюшиися минимизацией структуры графа автомата путем замены упорядоченного множества

вершин состояний вершиной-массивом;

2) метод векторизации вершин графа автомата, отличающиися сокращением вершин в графе путем оптимизации функций переходов между состояниями;

3) метод инициализации состояний цифрового автомата поиска, отличающиися введением в структуру автоматной модели поиска дополнительного устройства для хранения информации о текущем объекте поиска, что обеспечивает применение

других разработанных методов оптимизации;

4) метод векторизации изоморфных подграфов автоматной модели, отличающийся оптимизацией ее структуры путем замены множества подграфов, содержащих упорядоченную последовательность вершин состоянии, кортежем подграфов, в котором в каждый момент времени возможен доступ только к одному из них;

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

Положения, выдвигаемые на защиту:

1) применение разработанных методов (метод векторизации вершин состоянии, метод векторизации вершин графа, метод векторизации изоморфных подграфов) позволяет сократить аппаратные затраты на реализацию автоматных моделей поиска информационных структур в потоке данных на РВС, что повышает удельную

производительность;

2) при объединении состояний группы автоматов поиска невозможно сформировать переходы из общих эквивалентных состояний в неэквивалентные состояния без введения управления инициализацией символьных структур.

Результаты, выносимые на защиту:

1) метод векторизации вершин состояний цифровых автоматов, отличающиися минимизацией структуры графа автомата путем замены упорядоченного множества

вершин состояний вершиной-массивом;

2) метод векторизации вершин графа автомата, отличающийся сокращением вершин в графе путем оптимизации функций переходов между состояниями;

3) метод инициализации состояний цифрового автомата поиска, отличающиися введением в структуру автоматной модели поиска дополнительного устройства для хранения информации о текущем объекте поиска, что обеспечивает применение других разработанных методов оптимизации;

4) метод векторизации изоморфных подграфов автоматной модели, отличающийся оптимизацией ее струюуры путем замены множества подграфов, содержащих упорядоченную последовательность вершин состоянии, кортежем подграфов, в котором в каждый момент времени возможен доступ только к одному из

них;

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

Практическая ценность работы.

На основании методов оптимизации разработан программный комплекс для генерации автоматных моделей поиска информационных структур в потоке данных. Применение разработанных методов и средств позволяет сократить количество аппаратного ресурса для реализации автоматных моделей поиска до 2,1 раз и, как следствие, во столько же раз повысить удельную производительность РВС. При решении задачи поиска ключевых слов применение методов оптимизации позволило сократить аппаратный ресурс в 2,1 раза, при решении задачи поиска битовых последовательностей - в 1,9 раза, а при решении задачи сигнатурного.анализа данных - в 1,28 раза.

Реализация и внедрение результатов работы. Результаты диссертационной работы использовались при выполнении ряда НИОКР в НИИ многопроцессорных вычислительных систем ЮФУ, которые были направлены на создание системного и прикладного программного обеспечения РВС различных архитектур и конфигураций. К наиболее важным из них следует отнести:

- «Исследование и разработка программного обеспечения и испытания экспериментального образца унифицированного базового модуля многопроцессорной системы со структурной реализацией параллельной обработки информации», итоговый отчет о НИР, № гос. per. 01.2.00613841, Таганрог, НИИ МВС ТРТУ, шифр «ССПВ-Т2», 2006 г.;

- «Разработка эскизной конструкторской документации на макет базового модуля модульно-наращиваемой мультипроцессорной системы (МНМС) на основе реконфигурируемой элементной базы и программных средств поддержки масштабируемых программ для решения задач обработки информации и управления в реальном времени на различных конфигурациях МНМС, в том числе при деградации вычислительного ресурса», отчет о НИР, № гос. per. 01.2.00611470, инв. № 02.2.00606581, Таганрог, НИИ МВС ТРТУ, шифр «Триада», 2006 г.;

- «Разработка и исследование параллельных и конвейерных реализаций задач различных предметных областей на гетерогенных МВС», итоговый отчет о НИР, №гос. per. 01.2007 02728, инв. № 0220.0800098, Таганрог, НИИ МВС ЮФУ, шифр «Карнавал», 2007 г.;

- «Создание семейства высокопроизводительных многопроцессорных вычислительных систем с динамически перестраиваемой архитектурой на основе реконфигурируемой элементной базы и их математического обеспечения для решения вычислительно трудоемких задач», итоговый отчет об ОКР, № гос. per. 01.2.007 05707, Таганрог, НИИ МВС ЮФУ, шифр «Большая Медведица», 2007 г.;

- «Разработка методов и инструментальных систем для анализа эффективности работы параллельных программ и суперкомпьютеров. Этап 1. Выбор направления исследований. Теоретические исследования поставленных перед НИР задач», отчет о НИР, № гос. per. И110519102540, Таганрог, НИИ МВС ЮФУ, шифр «Рамка», 2011 г.;

- «Разработка теоретических основ построения сверхвысокопроизводительных реконфигурируемых вычислительных систем», отчет о НИР, № гос. per. 01201153442, Гаганрог,*НИЙ МВС ЮФУ, шифр «Маска», 2012 г.;

- «Разработка и исследование принципов построения программных средств для высокопроизводительных реконфигурируемых вычислительных комплексов», отчет о

НИР, № гос. per. 01201153442, инв. № 02201254407, Таганрог, НИИ МВС ЮФУ, шифр «Маска-2», 2013 г.

Созданные методы, алгоритмы и программные средства внедрены в следующих организациях: войсковая часть 26165 (г. Москва), ФГУП РНИИРС (г. Ростов-на-Дону), НИИ МВС ЮФУ (г. Таганрог).

Апробация работы. Основные результаты, представленные в диссертации, докладывались и обсуждались на международных, всероссийских и региональных научно-технических конференциях: VII, VIII, IX, X ежегодных научных конференциях студентов и аспирантов базовых кафедр ЮНЦ РАН, Ростов-на-Дону; международной научно-технической конференции «Многопроцессорные вычислительные и управляющие системы (МВУС-2009)», с. Дивноморское, Геленджик, 2009 г.; 2-ой Всероссийской научно-технической конференции «Суперкомпьютерные технологии (СКТ-2012)», с. Дивноморское, Геленджик, 2012 г.; 6-й Всероссийской мультиконференции по проблемам управления МКПУ-2013, с. Дивноморское, Геленджик, 2013 г.; международной научно-практической конференции «Интеграция науки и практики, вопросы модернизации, проблемы совершенствования в экономике, проектном менеджменте, образовании, юриспруденции, языкознании, культурологии, экологии, зоологии, химии, биологии, медицине, психологии, политологии, филологии, философии, социологии, информатике, технике, математике, физике», Санкт-Петербург, 27-28 февраля 2014 г., Всероссийском совещании по проблемам управления (ВСПУ-2014), Москва, 2014.

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

Публикации. Основные положения диссертации опубликованы в 17 печатных работах: из них 4 статьи, из которых 3 статьи опубликованы в ведущих рецензируемых научных журналах, входящих в Перечень ВАК РФ, 2 свидетельства об официальной регистрации программ для ЭВМ, а также тезисы и материалы 11 докладов на международных и российских научно-технических конференциях. Результаты работы отражены в 13 отчетах о НИОКР.

Структура и объем диссертации. Диссертация состоит из введения, четырех глав, заключения, списка использованных источников из 98 наименований и двух приложений. Основная часть работы изложена на 168 страницах и включает 76 рисунков.

КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ

Во введении изложены актуальность темы диссертации, цель и задачи исследования, научная новизна, практическая ценность, основные научные положения, выносимые на защиту, а также приведено краткое содержание каждой из глав.

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

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

1) для повышения удельной производительности устройств сетевого мониторинга необходимо проводить структурную оптимизацию цифровых автоматов под архитектурные особенности ПЛИС;

2) если интенсивность информационных потоков выше скорости обработки, то для обработки данных в режиме реального времени необходима параллельная организация вычислений, что обеспечивается структурной организацией вычислений и не обеспечивается программными средствами для фон-неймановских машин;

3) структурная обработка данных в темпе их поступления с помощью автоматных моделей возможна только при обеспечении переходов между состояниями за один такт.

Во второй главе разработаны методы оптимизации логической структуры автоматных моделей поиска информационных структур с масками: метод векторизации вершин состояний автоматной модели поиска, метод векторизации вершин графа, метод инициализации состояний и метод векторизации изоморфных подграфов.

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

*[1...к] = {?,.?1?г.?1?г?3.....

где в квадратных скобках указан диапазон возможного количества символов в маске от 1 до к.

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

Для поиска шаблонов используется автомат-распознаватель, в котором каждый символ шаблона соответствует новому состоянию автомата. Переход по состояниям осуществляется последовательно, при этом все состояния автомата характеризуются порядковым номером символа шаблона и признаком обнаружения совпадения. По определению состояния Sj и s, называются эквивалентными, когда для любой входной строки а функции выходов 4 одинаковы ¿;(s,,a) = ¿¡(s^a). В соответствии с определением эквивалентности и особенностью автоматов-распознавателей для определения эквивалентности состояний достаточно сравнить условия переходов для

парь, состояний с одинаковыми порядковыми индексами, где условиями переходов

являются символы шаблонов. «м „гам лп и

Графы автоматов поиска шаблонов с масками Р = {*?/>,ДО и после минимизации эквивалентных состояний представлены на рисунке 1. Пунктирными линиями обозначены группы эквивалентных состоянии. В данном случае можно выделить пять групп эквивалентных состоянии: О0 - К»,

с, = {*„.*„. <?. = {'«.».». = и

Г„Г2,У3,Г< - выходные функции нахождения шаблонов из массива шаблонов И. Обратные переходы не показаны на графе.

«— 9т | &и

I Sio 1 | Sin I | S12 I I Sl3 1 S,4

¡©Mto^

I Si5 I I S? I I S22 I I S23 I | S2< I S2S

Уз

I I S22 I I S23

'I I I

0

^взо

So

----

G

2

1 vfe

вг

JVTMi

4

it' G,

S35

Sse

a)

6)

а) граф автомата до минимизации эквивалентных состояний; б) граф автомата после минимизации эквивалентных состояний Рисунок 1 - Применение метода минимизации эквивалентных состоянии

Следующим методом оптимизации автоматной модели поиска является метод векторизации вершин состояний. Основная идея метода заключается в том, что в исходном графе определяются вершины, соответствующие состояниям автомата в которые он последовательно переходит при любых входных воздействиях Такие состояния соответствуют маске шаблона, подразумевающей под собой группу любых символов. В данном случае важно условие, которое выведет автомат в строго определенное состояние, соответствующее конкретному символу шаблона, либо переведет автомат в начальное состояние. Такое упорядоченное множество вершин состояний в графе автомата заменяется вершиной-массивом, и в структуру автоматной модели вводится устройство управления состояниями в верши^-масси^ Выходы из вершины-массива определяются либо выходными функциями управляющего автомата, либо условием перехода в следующее состояние. Метод векторизации состояний автомата не уменьшает количество его состоянии, но при

этом существенно упрощается его структура. D-/,.*h ,

На рисунке 2-а представлен граф автоматной модели поиска шаблона Р-{а Ь}. где *Г1 31 На рисунке 2-6 представлен граф после применения метода векторизации вершин состояний автоматной модели. Здесь R - выходная функция устройства управления Counter, Z - функция инициализации работы устройства управления, У-выходная функция автоматной модели, определяет нахождение шаблона Р-{а Ь}.

a) 6)

Рисунок 2 - Применение метода векторизации вершин состояний автоматной модели

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

На рисунке 3 представлен пример применения метода векторизации вершин автоматной модели поиска шаблонов с масками Р = {a?6,a??c,a???¿/,a????e}. На рисунке 3-а представлена автоматная модель после объединения эквивалентных состояний и применения метода векторизации состояний, где R-{Ri,R2,R},^4} ~ множество выходных функций счетчика Counter (R¡ = 1, Rj = 2, R3 = 3, R4 = 4), Z -функция инициализации счетчика, Y={Yi,Y2,Y¡,Y4} - выходные функции нахождения шаблонов Р. На рисунке З-б представлена автоматная модель после применения метода векторизации вершин, где RAM - память для хранения условий переходов в вершины графов, Ceq - выходная функция устройства сравнения, X - поток байтовых символов входной последовательности.

б)

Рисунок 3 - Применение метода векторизации вершин автоматной модели поиска

Для анализа эффективности применения методов объединения эквивалентных состояний, векторизации состояний и векторизации вершин получены формулы оценки аппаратных ресурсов РВС при оптимизации автоматных моделей ¿ = 2(М„ -С,-М,-+ М„[ + ]1ой2 + N = ]к>дг(ЛГ„-С, - М, - Мп)[+\оё2 Л/„[+]к^, А/„[ + 8М„, где Ь число логических элементов на реализацию автомата; N - число элементов памяти (триггеров) на реализацию автомата; М0 - общее число состояний начальных

автоматов для поиска всех заданных шаблонов; С, - разность общего числа эквивалентных состояний Мэ и числа групп эквивалентности (С, = М3 - О',); М, -число векторизированных состояний в вершине-массиве состояний после применения метода векторизации вершин состояний; Мп - число вершин, замененных ячейками памяти при применении метода векторизации вершин графа автомата (в данном случае ячейками памяти являются регистры); Ц - число логических элементов на реализацию устройства сравнения. При использовании аппаратных блоков памяти ПЛИС, составляющая 8М„, для оценки количества триггеров не используется. С помощью приведенных формул доказывается первое положение, выносимое на защиту. Полученные формулы оценки аппаратных затрат проиллюстрированы графическими зависимостями на рисунке 4, где I - число логических элементов на реализацию автомата, М- число оптимизируемых состояний автомата.

График 1 показывает эффективность минимизации эквивалентных состояний, график 2 - эффективность применения метода векторизации вершин состояний автомата, график 3 - эффективность применения метода векторизации вершин графа автомата. Рассмотренные методы оптимизации автоматных моделей поиска позволяют сократить до 90% число логических элементов, необходимых для их реализации.

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

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

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

Применение метода инициализации состояний обеспечивает возможность применения других методов оптимизации без ограничения функциональных

возможностей автоматной модели поиска.

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

триггеров , .

N = ]1оё2(М„ -С3 -М. -М„ -С„)[+ ]1оёг М,I■+ ]1ог2 М„[ + 8• М„ + /[,

где I - число шаблонов с разной инициализацией, С„ - число эквивалентных состояний в изоморфных подграфах, разбитых по группам эквивалентности; Сы = Ми - Си, где М„ - общее число состояний в изоморфных подграфах; - число групп эквивалентных состояний в этих подграфах.

Пример применения метода векторизации изоморфных подграфов автоматной модели поиска шаблонов Р = {Ра,Р,} = {а»Ьс<1е,т*, где *[1--3], приведен на рисунке 5. На рисунке 5-а представлена автоматная модель после объединения эквивалентных состояний, векторизации состояний и инициализации состояний, где подграф с состояниями 5.6,7,8 и подграф с состояниями 9,10,11.12 изоморфны. На рисунке 5-6 представлена автоматная модель после векторизации изоморфных подграфов, где 5_9, 6 10, 7_11. 8_12 - вершины изоморфных подграфов после объединения.

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

Ь Ко+д R1

Рисунок 5 - Применение метода векторизации изоморфных подграфов для оптимизации автоматной модели поиска

Транслятор, структура которого представлена на рисунке 6-6, выполняет синтаксическую проверку входных шаблонов, генерацию автоматной модели и ее оптимизацию в зависимости от выбранных методов оптимизации. Разработан обобщенный алгоритм трансляции входных шаблонов и генерации оптимизированной автоматной модели.

1°. Разбор входных цепочек символов, соответствующих шаблонам.

2°. Анализ входных цепочек символов.

3°. Генерация ориентированного графа для каждого шаблона.

4°. Поиск и формирование связей между узлами графа, соответствующих функциям прямых переходов.

5°. Поиск и формирование обратных связей для организации переходов между узлами по маске.

6°. Оптимизация построенных графов.

7°. Генерация объектной модели автомата.

8°. Выход.

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

Файл шаблонов

Файл Л шаблонов /

Программный комплекс

Транслятор

Ч Параметры >> трансляции

Объектная схема оптимизированной автоматной модели (хт!~Файл)

Графическая оболочка

Блок генерации автоматов

Г Список Л у объектов у

Блок оптимизации

Синтезатор

/ Список \ у объектов у

Г Файл описания автоматной

модели в виде схемотехнических I примитивов (хтЦфайл)

5

|Блок генерации объектной модели) а втомата_

Объектная схема оптимизированной

автоматной модели ?

а) б)

а) обобщенная структура программного комплекса; б) структура транслятора Рисунок 6 - Структура программного комплекса генерации автоматных моделей поиска информационных структур

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

настргчч'а ге» в&вяШШ ок. Зь^ЙЙ: -.23? _____.......

-о - О Р" -А Е О а О ■е.

ь к>- !е \ Л. А гО Е -о

о * о

о о

!е ! —П-........ в о.

: авггг-». и»"« жятжшвж&ш шшшюмш шш&г&ш т

Рисунок 7 - Визуальное представление автоматной модели в графической оболочке программного комплекса генерации автоматных моделей

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

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

а) б)

Рисунок 8 - Реализация задачи поиска ключевых слов на РВС

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

Задача сигнатурного анализа данных заключается в поиске большого количества шаблонов, которые могут входить друг в друга, и является актуальной в антивирусных системах для поиска вредоносных структур вирусов (сигнатур). При решении задачи сигнатурного анализа на РВС была синтезирована автоматная

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

для реализации в 1,28 раза.

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

В заключении работы изложен основной научный результат диссертации, сформулированы теоретические и прикладные результаты, полученные в диссертационной работе, а также предложены рекомендации и перспективы дальнейшей разработки темы.

ОСНОВНЫЕ РЕЗУЛЬТАТЫ И ВЫВОДЫ

Основной научный результат диссертации заключается в решении актуальной научной задачи создания методов оптимизации логической структуры автоматных моделей поиска информационных структур, направленных на сокращение аппаратного ресурса РВС для их реализации, при заданной скорости

входного потока данных.

При проведении исследований и разработок по теме настоящей работы получены следующие теоретические и прикладные результаты, обладающие научной новизной:

1) метод векторизации вершин состояний автоматной модели поиска, отличающийся минимизацией структуры графа автомата путем замены упорядоченного множества вершин состояний вершиной-массивом;

2) метод векторизации вершин графа автоматной модели поиска, отличающийся сокращением вершин в графе путем оптимизации функций переходов

между состояниями;

3) метод инициализации состояний цифрового автомата поиска, отличающиися введением в структуру автоматной модели поиска дополнительного устройства для хранения информации о текущем объекте поиска;

4) метод векторизации изоморфных подграфов автоматной модели, отличающийся оптимизацией ее структуры путем замены множества подграфов, содержащих упорядоченную последовательность вершин состояний, кортежем подграфов, в котором в каждый момент времени возможен доступ только к одному из них;

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

ОСНОВНЫЕ ПУБЛИКАЦИИ ПО ТЕМЕ ДИССЕРТАЦИИ

1. Ильченко, Д.Н. Применение операции векторизации состояний для синтеза цифровых автоматов [Электронный ресурс] / Д.Н. Ильченко // «Инженерный вестник Дона», 2013, №4 - Режим доступа: http://www.ivdon.ru/magazine/archive/n4y2013/2028

(доступ свободный) - Загл. с экрана. - Яз. рус. ISSN 2073-8633 (ведущий рецензируемый журнал, входит в перечень ВАК).

2. Ильченко, Д.Н. Комплексная минимизация цифровых автоматов при решении задачи поиска шаблонов [Текст] / И.И. Левин, Д.Н. Ильченко // Вестник компьютерных и информационных технологий. - М.: Машиностроение, 2014. - №5. -С. 3-7 (ведущий рецензируемый журнал, входит в перечень ВАК).

3. Ильченко, Д.Н. Преобразования структуры автоматов поиска шаблонов с масками [Текст] / Д.Н. Ильченко // Известия ЮФУ. Технические науки. — Таганрог: Изд-во ТТИ ЮФУ, 2014. - №6 (155), С.108-116. (ведущий рецензируемый журнал, входит в перечень ВАК).

4. Ильченко, Д.Н. Программа синтеза и оптимизации цифровых автоматов для мониторинга компьютерных сетей / Ильченко Д.П., Гудков В.А., Бовгсун A.B. // Свидетельство об официальной регистрации программы для ЭВМ №2014617297, РФ. Зарегистр. в Реестре программ для ЭВМ 16.07.2014 г. Правообладатель: федеральное государственное автономное образовательное учреждение высшего профессионального образования «Южный федеральный университет».

5. Ильченко, Д.Н. Генератор файлов топологических ограничений для вычислительных структур и интерфейсов на ГШИС / Ильченко Д.Н., Дордопуло А.И., Доронченко Ю.И. // Свидетельство об официальной регистрации программы для ЭВМ № 2013619581, РФ. Зарегистр. в Реестре программ для ЭВМ 10.10.2013 г. Правообладатель: федеральное государственное автономное образовательное учреждение высшего профессионального образования «Южный федеральный университет».

6. Ильченко, Д.Н. Организация доступа к вычислительным устройствам в реконфигурируемых вычислительных системах с высокой степенью распараллеливания [Текст] / Д.Н. Ильченко, Ю.И. Доронченко, М.К. Раскладкип // Материалы Международной научно-технической конференции «Многопроцессорные вычислительные и управляющие системы» (МВУС-2009). - Таганрог: Изд-во ТТИ ЮФУ, 2009,- Т.1. - С.43-45.

7. Ильченко, Д.Н. Сигнатурный анализ множества каналов Ethernet с помощью алгоритма Ахо-Корасик с использованием реконфигурируемых вычислителей [Текст] / Д.Н. Ильченко // Труды молодых ученых ЮФУ и ЮНЦ РАН «Высокопроизводительные вычислительные системы». Таганрог: Изд-но ГГИ ЮФУ, 2011.-С.60-63.

8. Ильченко, Д.Н. Устройство поиска битовых последовательностей в потоке данных, передаваемых по сети Ethernet [Текст] / Д.Н. Ильченко // Труды молодых ученых ЮФУ и ЮНЦ РАН «Высокопроизводительные вычислительные системы» Выпуск 2. - Таганрог: Изд-во ЮФУ, 2012. -С.12-15.

9. Ильченко, Д.Н. Реализация алгоритма Ахо-Корасик для поиска сигнатур в потоке данных в сети Ethernet с использованием рекопфш урируемых вычислительных систем [Текст] / Д.Н. Ильченко // Тезисы докладов Седьмой ежегодной научной конференции студентов и аспирантов базовых кафедр Южного научного центра РАН 11-25 апреля 2011 года. - Ростов-на-Дону: Изд-ио ЮНЦ РАН, 2011.-С. 121-122.

10. Ильченко, Д.Н. Устройство для лексемного анализа данных в сеч и Ethernet в режиме реального времени [Текст] / Д.Н. Ильченко // Тезисы докладов Восьмой ежегодной научной конференции студентов и аспирантов базовых кафедр Южного

научного центра РАН 11-25 апреля 2012 года. - Ростов-на-Дону: Изд-во ЮНЦ РАН,

2012.-С. 125-126.

11. Ильченко, Д.Н. Реализация поиска ключевых слов в текстовых файлах, передаваемых по сети Ethernet [Текст] / Д.Н. Ильченко // Материалы Второй Всероссийской научно-технической конференции СКТ-2012. - Таганрог: Изд-во ТТИ ЮФУ, 2012.-С.118-120.

12. Ильченко, Д.Н. Поиск символьных структур в сети Ethernet [Текст] / Д.Н. Ильченко // Сборник трудов Девятой ежегодной научной конференции студентов и аспирантов базовых кафедр, 15-20 апреля 2013 г., г. Ростов-на-Дону. - Ростов н/Д: Изд-во ЮНЦ РАН, 2013. С. 106-107.

13. Ильченко, Д.Н. Доступ к реконфигурируемым вычислительным системам через Ethernet-канал [Текст] / Д.Н. Ильченко // Труды 6-й Всероссийской мультиконференции по проблемам управления МКПУ-2013, 30 сентября-5 октября 2013 г., с. Дивноморское, Геленджик, Россия. - Т. 4. - Ростов-на-Дону: Изд-во ЮФУ,

2013.-С. 153-156.

В совместных работах автором получены следующие результаты: в работе [2] предложен комплексный подход к оптимизации автоматных моделей поиска; в [6] разработан интерфейс информационных обменов между вычислительными устройствами в ПЛИС.

Подписано к печати Ю .09.2014 г. Формат 60x84"". Бумага офсетная. Печать ризография. Усл. пл. -1.25. Уч.-изд.л. -1,15.

Заказ № /3^/ Тираж 130 экз.

Отпечатано в Секторе обеспечения полиграфической продукцией в г Таганроге отдела полиграфической, корпоративной и сувенирной продукции ИПК КИБИ МЕДИА ЦЕНТРА ЮФУ ГСП 17А, г.Таганрог, 28, Энгельса, 1 тел.(8634)371717