Содержание к диссертации
Введение
1. Анализ методов и средств мониторинга современных компьютерных систем 20
1.1. Классические алгоритмы поиска шаблонов 22
1.2. Классификация цифровых автоматов 30
1.3. Реконфигурируемые вычислительные системы 36
1.4. Принципы структурной организации вычислений при поиске информационных структур в потоке данных на РВС 45
1.5. Выводы 48
2. Методы оптимизации автоматных моделей поиска информационных структур 50
2.1. Векторизация состояний автоматной модели поиска информационных структур с масками 52
2.2. Комплексная оптимизация автоматной модели поиска информационных структур с масками 63
2.3. Инициализация состояний и векторизация изоморфных подграфов 74
2.4. Выводы 88
3. Программные средства синтеза автоматных моделей поиска информационных структур в потоке данных для реализации на РВС 90
3.1. Общая структура и алгоритмы работы транслятора 92
3.2. Общая структура и алгоритмы работы синтезатора 109
3.3. Графическая оболочка 112
3.4. Реализация автоматных моделей поиска в виде схемотехнических примитивов на РВС с помощью синтезатора Fire!Constructor 118
3.5. Выводы 120
4. Решение задач поиска информационных структур на РВС
4.1. Задача поиска ключевых слов 122
4.2. Задача поиска битовых последовательностей 132
4.3. Задача сигнатурного анализа данных 143
4.4. Выводы 154
Заключение 156
Список использованных источников 158
- Реконфигурируемые вычислительные системы
- Комплексная оптимизация автоматной модели поиска информационных структур с масками
- Графическая оболочка
- Задача поиска битовых последовательностей
Реконфигурируемые вычислительные системы
Широкую популярность РВС получили в начале XXI века. Основное применение такие системы находят при решении широкого класса трудоемких задач, к которым относятся задачи моделирования сложных процессов, задачи управления, а также задачи, требующие обработки данных в режиме реального времени. Одним из таких направлений является поиск информационных структур в потоке данных. Использование РВС позволяет устранить недостатки как специализированных вычислителей [6,7], так и систем с традиционной архитектурой [44].
В качестве основных вычислительных элементов в РВС используются микросхемы с реконфигурируемой структурой, к которым относятся ПЛИС (англ. Programmable Logic Device, PLD) [45]. Основными фирмами по производству подобных устройств являются Xilinx Inc. [46], Altera Corporation [47], Achronix Semiconductor [48], Actel Corporation [49]. Отличительной особенностью ПЛИС является то, что алгоритм работы задается путем их программирования.
Развитие ПЛИС началось в 70-х годах XX века с создания программируемых постоянных запоминающих устройств (ППЗУ -Programmable Read Only Memory – PROM), которые сначала применялись для хранения данных, а позже – для реализации логических выражений. Развитие PROM привело к появлению программируемых логических матриц (ПЛМ), программируемых матриц логики (ПМЛ или PAL) и сложных программируемых логических устройств (ComplexPLD – CPLD).
В настоящее время широкое распространение получили такие архитектуры ПЛИС как CPLD и FPGA - Field Programmable Gate Array [11], лидером в производстве которых является фирма Xilinx. Популярность FPGA обусловлена возможностью многократной реконфигурации, что позволяет решать задачи различных областей. Основными семействами ПЛИС фирмы Xilinx являются Virtex, Spartan, CoolRunner и XC9500.
Наиболее востребованными в настоящее время являются ПЛИС семейства Virtex-6 [50], которые выпускаются с 2009 года. Это семейство включает в себя высокопроизводительные ПЛИС на основе архитектуры FPGA, выполненные по 40-нм технологии и использующиеся при решении ресурсоемких задач.
Семейство Spartan-6 включает в себя менее производительные и более дешевые ПЛИС FPGA, которые широко применяются в устройствах с невысокой стоимостью комплектующих и выпускающихся большими партиями, например в бытовой электронике, в проводной и беспроводной связи. ПЛИС этого семейства выпускаются по 45-нм технологии.
CoolRunnerII и XC9500XL относятся к ПЛИС типа CPLD и используются в устройствах компактных размеров, например в мобильных телефонах. Данный тип микросхем характеризуется низкой потребляемой мощностью и небольшими размерами.
Среди продукции компании Altera можно выделить ПЛИС серии Stratix, а также ASIC микросхемы HardCopy [47]. Данная компания впервые применила в ПЛИС технологию, позволяющую изменять потребляемую мощность логических ячеек.
Рассмотрим более подробно структуру ПЛИС Virtex фирмы Xilinx как наиболее производительного и распространенного семейства в настоящее время. В общем виде структура ПЛИС содержит в себе следующие компоненты [50]: - конфигурируемые логические блоки (Сonfigurable logic block — CLB); - трассировочные ресурсы между всеми элементами ПЛИС; - блоки ввода/вывода, обеспечивающие связь между внешними выводами ПЛИС и логическими ячейками. Начиная с Virtex-4, ПЛИС данного семейства выполняются по архитектуре ASMBL (Advanced Silicon Modular Blocks), которая подразумевает выполнение микросхемы в виде вертикальных блоков с компонентами различных типов. К ним относятся конфигурируемые логические блоки CLB, блоки ввода/вывода, блочная память и блоки цифровой обработки сигналов DSP (Digital Signal Processor) [51,52].
Конфигурируемые логические блоки CLB состоят из двух секций, которые бывают двух видов – Slice_L и Slice_M. Каждая секция в ПЛИС семейства Virtex-6 содержит в себе 4 логических таблицы истинности (LUT – Look-upable), 8 элементов памяти (триггеров, FF – Flip-Flop), каждый из которых предназначен для хранения одного бита информации, мультиплексоры для коммутации выходов таблиц истинности LUT и схему ускоренного переноса. LUT представляет собой 6-входовое одноразрядное запоминающее устройство объемом 64 бита, обеспечивающее реализацию любых логических функций от входных переменных. Отличительной особенностью ПЛИС Virtex-6 является то, что на 1 LUT приходится 2 триггера.
Комплексная оптимизация автоматной модели поиска информационных структур с масками
Рассматриваемые до этого автоматы для поиска шаблонов с масками имели одинаковую начальную инициализацию, это было связано с самими шаблонами поиска. Каждый из искомых шаблонов начинался с одного и того же символа. Пример такого множества шаблонов P = {alb,aVc,amd}. При оптимизации структуры этих автоматов с помощью метода минимизации эквивалентных состояний такие автоматы довольно просто объединялись в один автомат, инициализация которого осуществлялась по входному воздействию x="a". Маски шаблонов объединялись с помощью операции векторизации в вершину-массив состояний, управляемую внешним устройством (счетчиком). При этом для каждого заданного шаблона автомат имел свое конечное состояние, что однозначно позволяло определить, какой шаблон будет найден при выходе из вершины-массива состояний в это конечное состояние. Основным ограничением при проведении такой комплексной минимизации является исключение символа инициализации автомата из возможных символов маски. Обозначим такое исключение как p0 е и p0 , где ро - некоторый символ инициализации синтезируемого автомата. Такая запись будет обозначать, что данный символ не принадлежит множеству возможных символов из таблицы ASCII, которые может принимать маска «?» и « », то есть в маске может быть любой символ, кроме исключенного символа. В рассматриваемом примере символ инициализации определен как р0=«а». При отсутствии такого ограничения нахождение шаблонов с помощью одного детерминированного автомата становится неоднозначным, так как очередной входной символ может быть как символом шаблона в маске, так и началом нового шаблона.
Если же имеется группа шаблонов с разными заголовками, то поиск таких шаблонов будет реализован с помощью автоматов, каждый из которых будет инициализирован входными воздействиями, отличающимися друг от друга. При использовании масок в шаблонах также необходимо исключить из маски символ инициализации каждого конкретного автомата, а при объединении группы автоматов в один автомат с помощью минимизации эквивалентных состояний из маски должны быть исключены все символы инициализации каждого автомата.
При слиянии группы автоматов с разной инициализацией и объединении всех эквивалентных состояний, соответствующих маскам нескольких шаблонов, в одну вершину-массив состояний, возникает необходимость однозначного определения выхода из вершины-массива в следующее состояние автомата. Неоднозначность заключается в том, что переход возможен как в состояние, соответствующее следующему символу искомого шаблона, так и в состояние, соответствующее другому шаблону, что не будет соответствовать действительности. Например, если заданы шаблоны P = {P0,P1} = {ab e,cb d}, то при поступлении на вход автомата последовательности символов X = {a,b,f,j,k,d} выход из вершины-массива состояний будет осуществлен в состояние, соответствующее символу «d», что будет ошибочно соответствовать нахождению шаблона i .
Эта проблема характерна не только при использовании векторизации состояний в вершину-массив, но и при объединении эквивалентных состояний, поскольку необходимо точно определять, по поиску какого шаблона автомат перешел в состояние, общее для нескольких шаблонов, и в какое состояние дальнейший переход будет возможен.
Для решения данной проблемы предлагается в устройство управления вершиной-массивом состояний передавать информацию о том, какой шаблон в данный момент инициализирован [82]. В зависимости от этой информации в устройстве управления для каждого шаблона будет сформирована своя функция выхода, что позволит корректно перейти из вершины-массива в следующее состояние и избежать ложного совпадения шаблона, что доказывает второе положение, выдвигаемое на защиту. Для хранения информации об инициализации необходимо использовать устройство управления инициализацией, которое будет определять состояния, соответствующие инициализации определенных шаблонов, и передавать информацию об этом в устройство управления состояниями в вершине-массиве. Это устройство будет представлять собой автомат с хранением состояний, где каждое состояние - это состояние инициализации нового шаблона. Количество состояний такого автомата будет определяться количеством шаблонов с разной инициализацией. Состояния в устройстве управления инициализацией будут меняться только при переходе автомата поиска в состояния с признаком инициализации шаблонов.
Инициализационные состояния определяются по следующим правилам: - приоритетным является использование состояний, переход в которые осуществляется по совпадению первого символа шаблона; - если начальные состояния автоматов для поиска множества шаблонов эквивалентны и при проведении минимизации объединяются в общее состояние, то в качестве состояний инициализации шаблонов используются ближайшие неэквивалентные состояния.
Информацию об инициализации того или иного шаблона необходимо передавать в устройство управления состояниями в вершине-массиве сразу после перехода либо из начального состояния автомата, либо из любого другого в состояние, соответствующее первому символу любого заданного шаблона. В случае переинициализации автомата информация в устройстве управления обновляется. Таким образом, формируя управляющие сигналы инициализации, мы можем использовать одну вершину-массив состояний и один счетчик состояний для всего множества заданных шаблонов и при этом точно определять, поиск какого шаблона в данный момент производится автоматом.
Графическая оболочка
Синтезатор Fire!Constructor предназначен для создания многокристальных решений прикладных задач. Он автоматически разбивает структурную составляющую параллельной программы на непересекающиеся фрагменты, каждый из которых реализуется в отдельном кристалле ПЛИС многокристальной РВС [84,85].
Входными данными для синтезатора Fire!Constructor при реализации автоматных моделей поиска информационных структур являются библиотека схемотехнических элементов, структура многокристальной РВС и описание автоматной модели в виде схемотехнических примитивов в формате xml-файла.
Библиотека схемотехнических элементов представляет собой набор элементов, разработанных на языках VHDL и Verilog, или в существующих графических средах под конкретные семейства кристаллов ПЛИС. Данные элементы реализуют различные арифметические и логические операции, блоки управления информационными потоками, блоки контроллеров распределённой памяти РВС и др.
Структура РВС содержит описание кристаллов ПЛИС (аппаратный ресурс, имена различных служебных выводов ПЛИС – сброс, тактовая частота, индикация и др.), входящих в состав РВС, а также описание пользовательских связей между микросхемами ПЛИС (разрядность связей и имена выводов ПЛИС).
На рисунке 3.18 приведен пример отображения объектного файла, полученного в результате синтеза автоматной модели с помощью разработанных программных средств, в синтезаторе схемотехнических решений Fire!Constructor.
Синтезатор Fire!Constructor имеет ряд настроек, которыми может управлять пользователь: - максимальный коэффициент разветвления выходных сигналов; - использование блочной памяти для длинных задержек; - используемые методы разветвления; - максимальные коэффициенты заполнения кристаллов ПЛИС по каждому из ресурсов.
Результатом работы синтезатора Fire!Constructor являются файлы VHDL-описаний и файлы временных и топологических ограничений (User Constraints Files). Файлы VHDL описывают структурные реализации фрагментов параллельной программы. На основании этих файлов и библиотеки схемотехнических элементов формируются проекты для синтезатора системы автоматизированного проектирования (САПР) [88] под каждую отдельную ПЛИС. Далее с помощью синтезатора САПР и программы генерации файлов топологических ограничений для вычислительных структур на ПЛИС [89] формируются конфигурационные файлы ПЛИС, которые в дальнейшем загружаются в РВС для решения задач поиска информационных структур.
Разработанный программный комплекс генерации автоматных моделей поиска информационных структур, а также алгоритмизированные методы оптимизации автоматных моделей внедрены в ряде организаций и ведомств, что подтверждается актами о внедрении, представленными в Приложении 2.
1) На основании 3.5. методов оптимизации автоматных моделей поиска разработана структура программного обеспечения, отличающаяся наличием процедур трансляции символьных структур в графы цифровых автоматов, комплексной оптимизации полученных автоматов в интерактивном режиме и синтеза минимизированных автоматных моделей для реализации на РВС. В отличие от традиционных трансляторов разработанный транслятор содержит новые алгоритмы структурной оптимизации автоматных моделей поиска информационных структур в потоке данных. 2) Разработаны алгоритмы трансляции входных символьных структур в графы цифровых автоматов, отличающиеся возможностью получения минимизированных автоматных моделей поиска информационных структур, обеспечивающих обработку данных в темпе их поступления. Алгоритмы трансляции включают в себя: алгоритмы построения графов автоматных моделей и новые алгоритмы оптимизации их структуры. 3) Разработаны алгоритмы синтеза полученных на этапе трансляции объектных схем, описывающих автоматные модели поиска информационных структур в виде схемотехнических примитивов для их последующего использования в синтезаторе схемотехнических решений Fire!Constructor. 4) Разработан графический интерфейс программной среды синтеза автоматных моделей поиска для реализации на РВС, позволяющий моделировать полученные автоматные модели на каждом этапе оптимизации. 5) Использование разработанного программного обеспечения сокращает время оптимизации и отладки автоматных моделей поиска информационных структур в потоке данных на РВС.
Задача поиска битовых последовательностей
Другой особенностью программной реализации автоматов поиска является невозможность использования метасимвола « » в маске сигнатуры. Все это приводит к необходимости применения новых способов построения и реализации автоматных моделей на РВС.
Построение цифрового автомата сигнатурного анализа данных осуществляется в несколько этапов. На первом этапе необходимо построить граф автомата, где будут отображены вершины состояний и условия прямых переходов с учетом всех возможных вхождений сигнатур друг в друга.
Такое построение можно выполнить двумя способами. Первый способ заключается в том, что строится ветка графа для одной сигнатуры, далее берется следующая сигнатура и посимвольно производится сравнение с уже существующей веткой, если какой-то символ сигнатуры, соответствующий прямому переходу, не совпадает с существующим переходом между состояниями, то формируется новая ветка. Такая процедура выполняется до полного построения графа автомата для всех сигнатур.
При этом граф автомата должен быть представлен в ярусной форме, где каждый ярус обозначает индекс символов в сигнатурах. Переходы из начального состояния автомата возможны только в состояния, условно принадлежащие первому ярусу. Важно отметить, что если некоторые сигнатуры являются составляющей частью другой сигнатуры, то состояния, соответствующие их последнему символу, помечаются как выходные в составной сигнатуре. Переход из начального состояния в состояние, не принадлежащее первому ярусу, невозможен. Поэтому если одна из сигнатур является окончанием другой, то для нее должна быть построена отдельная ветка в графе, но вхождение сигнатуры должно быть также отмечено выходной функцией. Пример графа автомата для поиска сигнатур {ab, abcd, afg, eab} представлен на рисунке 4.19.
Другим способом построения графа автомата на первом этапе является формирование для каждой сигнатуры отдельного графа с последующим применением процедуры минимизации эквивалентных состояний, которая описана во второй главе. На рисунке 4.20 представлена группа графов автоматов для поиска того же набора сигнатур.
Пунктирными линиями на рисунке обозначены группы эквивалентных состояний, после объединения которых получается граф автомата, представленный на рисунке 4.19. При этом на этапе предварительного анализа сигнатур должно быть учтено вхождение сигнатуры {ab} в сигнатуры {abcd} и {eab} и отображено в виде соответствующих выходных функций обобщенного автомата.
Вторым этапом построения автомата для сигнатурного анализа данных является формирование функций возвратов. Для этого на этапе предварительного анализа необходимо учесть все вхождения последовательностей символов друг в друга. В дальнейшем при выполнении функции неудачи, если часть сигнатуры является началом другой сигнатуры, то это должно быть учтено в формируемом переходе.
Рассмотрим формирование функций возвратов для обобщенного графа автомата, показанного на рисунке 4.19. При этом следует обратить внимание на формирование функций возвратов при программной реализации автоматной модели Ахо-Корасик, граф которой с функциями возвратов показан на рисунке 4.21.
Формирование функций возвратов при программной реализации алгоритма Ахо-Корасик для сигнатурного анализа данных Состояния 2,5,7,9 определяют вхождение образцов в текст. Состояние 2 определяет нахождение сигнатуры {ab}, состояние 5 – сигнатур {ab} и {eab}, состояние 7 – сигнатуры {afg}, состояние 9 – сигнатуры {abcd}.
Как видно из программной реализации, возвраты осуществляются в некоторые состояния, из которых производится анализ перехода в следующее состояние, что подразумевает выполнение перехода при функции неудачи минимум за два шага. В структурной реализации такие переходы недопустимы. В соответствии с рассмотренными принципами структурной организации вычислений для обеспечения поиска информационных структур в реальном масштабе времени переходы должны осуществляться за один такт работы автомата. При формировании переходов автоматной модели для сигнатурного анализа данных на РВС применяется два основных правила.
Первое правило заключается в организации обратных переходов, когда все переходы между вершинами заданы четко определенными символами входного алфавита без использования масок. В этом случае обратные переходы при функции неудачи выполняются непосредственно в вершины, определяющие нахождение определенной последовательности символов с учетом предыдущих совпадений. Такие преобразования показаны на рисунке 4.22, где представлен граф автомата, в котором все функции возвратов сформированы таким образом, что переходы по состояниям будут выполняться в темпе поступления данных за один такт работы автомата в отличие от программной реализации, показанной на рисунке 4.21.
Второе правило формирования переходов в автоматной модели сигнатурного анализа применяется в том случае, если в сигнатурах используются маски. Данное правило заключается в необходимости введения в структуру автоматной модели дополнительных вершин, позволяющих учитывать все возможные совпадения символов сигнатур при переходе между вершинами, соответствующими маскам сигнатур, для дальнейшего однозначного формирования функций возвратов при выполнении функций неудачи. Количество дополнительных вершин определяется количеством вершин, соответствующих маскам сигнатур, для каждой ветки графа автоматной модели сигнатурного анализа, в которых реализован поиск масок, и количеством параллельных веток графа автоматной модели сигнатурного анализа, в которые возможен переход при функции неудачи. При переходе из некоторой вершины графа автоматной модели в вершину, соответствующую маске, должны быть сформированы дополнительные ветки графа, позволяющие контролировать совпадения последовательности символов всех возможных сигнатур. Вершины и переходы между ними в таких ветках графа повторяют структуру автоматной модели от начального состояния до ближайшего состояния, соответствующего первому символу маски текущей сигнатуры или набора сигнатур. Такие преобразования показаны на рисунке 4.23, где представлен граф автоматной модели поиска сигнатур {ab?cd,msek}.
