Авторефераты по темам  >>  Разные специальности - [часть 1]  [часть 2]

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

Автореферат кандидатской диссертации

 

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

 

Евсюков Вячеслав Сергеевич

 

МЕТОДы параллельного поиска вхождений и пересечений СИМВОЛЬНЫХ ДАННЫХ и специализированные устройства для их реализации

05.13.05 Элементы и устройства вычислительной техники

и систем управления

 

АВТОРЕФЕРАТ

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

кандидата технических наук

 

 

КУРСК - 2009

Работа выполнена в ГОУ ВПО Курский государственный технический университет на кафедре программного обеспечения вычислительной техники.

Научный руководитель:а доктор технических наук, профессора а Атакищев Олег Игоревич

Официальные оппоненты:а доктор технических наук, профессора аа а Зотов Игорь Валерьевич

аа кандидат технических наук

Мусакин Евгений Юрьевич

Ведущая организация: Орловский государственный технический университет

Защита состоится л28 декабря 2009 г. в 16.00 на заседании совета по защите докторских и кандидатских диссертаций Д 212.105.02 при ГОУ ВПО Курский государственный технический университет по адресу: 305040, г. Курск, ул. 50 лет Октября, 94.

С диссертацией можно ознакомиться в библиотеке ГОУ ВПО Курский государственный технический университет по адресу: г. Курск, ул. 50 лет Октября, 94.

Автореферат разослан л27 ноября 2009 г.

 

Ученый секретарь совета по защите

докторских и кандидатских

диссертаций Д 212.105.02 аа ____________ Е.A. Титенко

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

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

Огромная значимость задач ОСИ подтверждается научно-техническими проектами и программами в оборонном комплексе, разработкой динамически реконфигурируемых вычислительных систем (семейство РВС на базе НИИ МВС ЮФУ), ориентированных на решение вычислительно трудоемких научно-технических задач в таких областях как системы обработки знаний, предсказание климатических условий, разработкой систем лексического анализа и технологии естественно-языковых интерфейсов к коммерческим СУБД (соответственно Alex и InBASE на базе НИИ Искусственного интеллекта), появлением сетей обмена разнородными данными и знаниями на основе метаграмматик и многими другими важными областями в науке, характеризуемыми недетерменированностью процессов обработки данных.

Важность и массовость операции поиска в задачах символьных вычислений отражена в научных трудах высших авторитетов в истории вычислительной техники А. Тьюринга, А. Черча, Э. Поста, Д. Кнута, (Jr) J.H. Morris, V.R. Pratt, R.S. Boyer, J.S. Moore, А.А. Маркова, А.Н. Колмогорова, Д.А. Поспелова, Б.А. Кулика, В.М. Довгаля и многих других отечественных и зарубежных исследователей.

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

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

Работа выполнялась в рамках госбюджетной составной части НИР Курского государственного технического университета УИсследование научно-технических путей обработки разнородных сложноструктурированных данных и знаний для распределенных систем управления в интересах оценки динамично-меняющейся обстановкиФ (шифр Притирка-2И-К, 2008 г.).

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

Предмет исследования: процессы и устройства параллельного сопоставления (поиска по образцу).

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

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

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

Методы исследования базируются на аппарате теории алгоритмов и исчислений, математической логики, продукционных системах ОСИ, а также теории проектирования ЭВМ и прикладного программирования.

Научная новизна результатов исследований:

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

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

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

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

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

3. Разработанные структурно-функциональные организации ассоциативного (ассоциативная запоминающая матрица, патент № 84615 РФ) и матричного устройств доведены до уровня функциональных схем, позволяющих создавать специализированные устройства ОСИ, обладающие повышенными скоростными показателями по отношению к существующим универсальным решениям, построенным на основе массовых процессорных архитектур.

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

5. Проведенные экспериментальные исследования скоростных и аппаратных характеристик разработанных устройств позволили получить зависимости скорости их работы от количественных характеристик образцов и обрабатываемых текстов, что позволяет определить как целесообразность, так и сферы применения разработанных методов и устройств поиска для решения специфических и разноплановых задач символьных вычислений. Ассоциативное устройство для практически значимых ситуаций имеет скоростное преимущество (по количеству сравнений символов) на порядок и более (от 1,1 до 34 раз) по отношению к устройству, реализующему алгоритм Бойера-Мура.

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

Апробация работы. Основные результаты диссертационной работы докладывались и получили положительную оценку на VII Всероссийской научно-технической конференции "Теоретические и прикладные вопросы современных информационных технологий" (г. Улан-Удэ, 2006), X Международной научно-техническая конференция "Медико-экологические информационные технологии - 2007" (г. Курск, 2007), VIII Всероссийской конференции молодых ученых по математическому моделированию и информационным технологиям (г. Новосибирск, 2007), VIII Международном симпозиуме "Интеллектуальные системы (INTELSТ2008)" (г. Н.Новгород, 2008), VIII Международной конференции "Распознавание-2008" (г. Курск, 2009), а также на научных семинарах кафедры программного обеспечения вычислительной техники КурскГТУ в период с 2006 по 2009 гг.

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

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

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

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

Публикации по теме диссертации. Основные результаты проведенных исследований опубликованы в 10 работах, среди которых имеется 1 статья в научном издании, входящем в перечень ВАК Минобрнауки РФ, и 1 патент №84615 РФ.

ичный вклад соискателя. Все выносимые на защиту научные результаты получены соискателем лично. В работах по теме диссертации, опубликованных в соавторстве, личный вклад соискателя сводится к следующему: в [1] предложен способ разрешения конфликтных ситуаций в исчислительных продукционных системах; в [2] разработана структурно-функциональная схема ассоциативной запоминающей матрицы; в [3] разработана абстрактная машина-генератор параллельных выводов для быстрых символьных вычислений; в [4] разработана структурно-функциональная схема аппаратного семафора для контролирования завершения параллельных процессов; в [5] описан аппарат систем поддержки принятия решений с массовым параллелизмом; в [6] проведена оценка временной сложности алгоритмов поиска; в [7] проведен анализ применимости алгоритма Кнута-Морриса-Пратта для систем с конвейерной и параллельной организацией; в [8, 9] описаны методы безвозвратного поиска; в [10] разработано схемотехническое решение ассоциативного устройства поиска вхождений.

Структура и объем диссертации.Работа состоит из введения, четырех глав, заключения, приложений и списка литературы, включающего 72 наименования. Общий объем диссертации составляет 184 страницы машинописного текста вместе с приложениями. Диссертация содержит 31 рисунок и 22 таблицы.

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

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

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

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

Большинство из известных программных методов обработки символьной информации используют безвозвратные алгоритмы поиска вхождений символьных данных на основе алгоритма Бойера-Мура и его модификаций. Универсальность современных процессорных архитектур и ориентированность на обработку числовых данных негативно влияет на производительность задач обработки символьных данных.

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

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

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

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

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

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

O > P,

где O и P - слова в заданном алфавите А; а - метасимвол-разделитель, не принадлежащий А; O - вхождение (образец); P - подстановка (модификатор).

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

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

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

В работе решаются задачи поиска всех вхождений и пересечений символьных данных, которые формулируются следующим образом. Пусть заданы образец O длиной m символов и текст S длиной n символов, где n > 0, m > 0 и m ? n. Требуется найти позиции всех вхождений O в S, т.е. определить все наименьшие i, при которых S(i, i + m Ц 1) = O(1, m). Если собственное начало O пересекается с собственным окончанием S, то найти позицию максимального пересечения собственного начала O с собственным окончанием S, т.е. определить наименьшее i, при котором S(i, i + j Ц 1) = O(1, j), где 0 < j < m и i + j Ц 1 = n. Если собственное окончание O пересекается с собственным началом S, то найти позицию максимального пересечения собственного окончания O с началом S, т.е. определить наименьшее j, при котором S(1, m Ц j + 1) = O(j, m). Ситуация пересечения слов O и S описывается следующей конструктивной дизъюнкцией:

,

где OН, OК - собственные начало и окончание O; SН, SК - собственные начало и окончание S.

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

Метод ассоциативного параллельного поиска всех вхождений основан на принципе циклической смены представления текста: одномерная последовательностьлдвухмерная последовательность. Ассоциативный параллельный поиск всех начал вхождений обеспечивается путем представления исходной строки S длиной до N=n?m элементов в виде двухмерной матрицы из n строк по m элементов в каждой строке, где m соответствует длине образца O. При таком представлении строки S образец O длиной в m элементов подается на информационные входы ассоциативной запоминающей матрицы и параллельно сравнивается по m столбцам матрицы, что демонстрируется на схеме, представленной на рис. 1, для S=1100101011001100 и O=1001, А = {0, 1}.

Рис. 1. Схема метода ассоциативного параллельного поиска вхождений

Ассоциативный поиск всех начал вхождений состоит из m циклов, включающих параллельное сравнение и сдвиг битовой строки на 1 разряд в сторону начальной позиции. В текущем цикле процесса поиска после сравнения - положительного (рис. 1в) или отрицательного (рис. 1а, 1д, 1ж) - выполняется сдвиг битовой строки S на 1 разряд в сторону начальной позиции (рис. 1б, 1г, 1е) и осуществляется следующий цикл параллельного сравнения образца O по m столбцам матрицы. В случае положительного сравнения фиксируется начальная позиция одного из вхождений битового образца O в битовую строку S. При втором и последующих циклах параллельного сравнения результат опроса n-ой строки матрицы не учитывается. Таким образом, не более чем через m циклов сравнений обнаруживаются все вхождения.

Суть разработанного метода матричного параллельного поиска всех вхождений и пересечений символьных данных заключается в параллельной обработке характеристической матрицы размерностью n?m поисковых ячеек, построенной в результате посимвольного сопоставления двух символьных строк. Параллельный поиск характеризуется побитовой обработкой элементов строк и столбцов, входящих в диагонали матрицы, а направление поиска - от последнего символа к первому по каждой диагонали, как показано на рис. 2, причем обработка каждой диагонали осуществляется параллельно с остальными диагоналями характеристической матрицы, что является отличительной особенностью метода матричного поиска. Схема метода матричного поиска демонстрируется на рис. 2, для S=ADCABCADABC и O=ABCAD, А = {A, B, C, D}. Начальное состояние характеристической матрицы поисковых ячеек показано на рис. 2а.

а)

а

б)

аа

Рис. 2. Схема метода матричного параллельного поиска вхождений и пересечений

Поиск начинается с ячеек последней строки и последнего столбца характеристической матрицы (рис. 2б). Начальные n-битовый и m-битовый характеристические векторы, равные 11Е1, подаются соответственно на входы поисковых ячеек последней строки матрицы и последнего столбца матрицы, определяя тем самым направление параллельного поиска по всем диагоналям характеристической матрицы от поисковых ячеек последней строки и последнего столбца до поисковых ячеек первой строки и первого столбца включительно.

Наличие У1Ф в поисковых ячейках результатов поиска первой строки характеристической матрицы с координатами от (1, 1) до (1, k), где k = n Ц m + 1, свидетельствует о вхождении образца в текст и указывает на позицию вхождения в тексте, наличие в поисковых ячейках первого столбца характеристической матрицы с координатами от (2, 1) до (m, 1) в разряде информационного выхода - о пересечении собственного окончания образца с собственным началом текста и указывает на частичную позицию пересечения в образце, в поисковых ячейках первой строки характеристической матрицы с координатами от (1, k +1) до (1, n) - о пересечении собственного начала образца с собственным окончанием текста и указывает на частичную позицию пересечения в тексте. Таким образом, информационным выходом характеристической матрицы поиска является первая (верхняя) строка и первый (левый) столбец матрицы.

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

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

Ассоциативное устройство параллельного поиска вхождений реализует разработанный метод ассоциативного поиска и содержит блок синхронизации и выбора режима работы, блок адресации строк, блок хранения образцов, блок хранения строк, операционный блок, блок результатов опроса (рис. 3).

Рис. 3. Структурно-функциональная организация ассоциативного устройства

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

Основным блоком устройства является операционный блок. В работу операционного блока заложены принципы разработанного метода ассоциативного параллельного поиска вхождений. Операционный блок ассоциативного устройства параллельного поиска вхождений состоит из n?m ассоциативных запоминающих элементов (n - количество битовых строк, необходимых для представления входной битовой строки, m - количество разрядов битового образца), коммутационных элементов, представляющих собой 1-n-полюсники, элементов-селекторов, маскирующего элемента, имеет адресные входы, информационные входы, внешний вход УРЕЖИМФ, определяющий двумерный или одномерный вид структуры матрицы, внешний вход синхронизации УCLOCKФ, внешний вход УСБРОСФ, выходы результатов опроса.

Операционный блок работает в одном из четырех состояний: запись, чтение, ассоциативный поиск, реконфигурация - при этом работа устройства в любом из его состояний начинается с подачи сигнала синхронизации УCLOCKФ=1.

Граф-схема алгоритма работы операционного блока ассоциативного устройства изображена на рис. 4.

Рис. 4. Граф-схема алгоритма работы операционного блока ассоциативного устройства

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

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

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

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

Рис. 5. Функциональная схема операционного блока матричного устройства

В работу операционного блока заложены принципы разработанного метода матричного параллельного поиска вхождений и пересечений. Операционный блок матричного устройства для параллельного поиска вхождений и пересечений символьных данных содержит два управляющих входа: Начальная установка и Запись строк, информационные входы для подачи символов образца и текста в параллельном коде, вход логической л1, m?n поисковых ячеек, триггеры позиций полного вхождения, триггеры позиций частичного пересечения собственного окончания образца с собственным началом текста (1), триггеры позиций частичного пересечения собственного начала образца с собственным окончанием текста (2), m регистров для хранения кодов символов образца, n регистров для хранения кодов символов текста, элемент задержки, выполненный в виде (m + 1) пар инверторов, а также информационный k-разрядный выход результата поиска позиции полного вхождения образца в текст, информационный m Ц 1-разрядный выход результата поиска позиции частичного пересечения (1) и информационный m Ц 1-разрядный выход результата поиска позиции частичного пересечения (2).

Граф-схема алгоритма работы операционного блока матричного устройства изображена на рис. 6.

Рис. 6. Граф-схема алгоритма работы операционного блока матричного устройства

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

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

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

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

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

а

Рис. 7. Схема имитационной модели операционного блока матричного устройства в системе моделирования Multisim

Результат моделирования работы имитационной модели устройства в системе Multisim представлен на рис. 8 в виде временной диаграммы работы со следующими параметрами: поисковый образец - abc, текст - bcabca.

Рис. 8. Временная диаграмма работы имитационной модели матричного устройства в системе Multisim

Анализ временной диаграммы работы имитационной модели показывает, что устройство корректно выдает результаты поиска через ~270 нс после начала его работы. Уровень логической У1Ф получен на триггере 41_1 частичного пересечения собственного окончания образца и собственного начала текста, на триггере 37_3 вхождения образца в текст, триггере 40_2 частичного пересечения собственного начала образца и собственного окончания текста.

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

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

Результаты экспериментальных исследований алгоритмических сложностей процессов поиска всех вхождений для моделируемых устройств приведены в таблицах 1-2. При этом варьируемым параметром являлась длина поискового образца, а статичными - мощность алфавита (2 символа) и длина генерируемого текста (1000 символов). Поиск производился по следующей схеме:

1. Генерация текста для поиска.
2. Полный перебор всех возможных вариантов образца в соответствии с заданным алфавитом и текущей длиной образца.
3. Обнаружение в соответствии с алгоритмами и методами поиска всех вхождений каждого образца из всего сгенерированного множества образцов в пространстве сгенерированного текста с фиксацией промежуточных результатов.
4. Получение средних значений количества сопоставлений символов и количества сдвигов образцов в пространстве текста.

Таблица 1 - Результаты экспериментальных исследований

Длина образца - 5 символов

Метод/алгоритм	Все вхождения		1-е вхождение
	Количество сравнений символов	Количество сдвигов	Количество сравнений символов	Количество сдвигов
Алгоритм прямого поиска	1930	995	58	29
Алгоритм Кнута-Мориса-Пратта	1235	547	41	16
Алгоритм Бойера-Мура	860	393	29	13
Метод ассоциативного поиска	25	4	5	0
Метод матричного поиска	5	5	5	5

Таблица 2 - Результаты экспериментальных исследований

Длина образца - 20 символов

Метод/алгоритм	Все вхождения		1-е вхождение
	Количество сравнений символов	Количество сдвигов	Количество сравнений символов	Количество сдвигов
Алгоритм прямого поиска	1962	980	966	475
Алгоритм Кнута-Мориса-Пратта	1210	490	610	242
Алгоритм Бойера-Мура	444	191	236	95
Метод ассоциативного поиска	400	19	200	9
Метод матричного поиска	20	20	20	20

В заключениисформулированы основные результаты и выводы диссертации.

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

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

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

Основными результатами диссертации являются следующие.

1. Созданы новые безвозвратные методы параллельного поиска всех вхождений и пересеченийсимвольных данных - ассоциативный и матричный. Метод ассоциативного параллельного поиска всех вхождений основан на динамической реконфигурации связей (структуры обрабатываемых данных) и параллельном сопоставлении символов по столбцам в ассоциативной матрице. Метод матричного параллельного поиска всех вхождений и пересечений основан на параллельном сопоставлении символов и обработке результатов сопоставлений по диагоналям матрицы.

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

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

4. Проведенные экспериментальные исследования скоростных и ресурсных характеристик разработанных устройств позволили получить зависимости скоростных показателей их работы от количественных параметров поисковых образцов и текстов, что позволяет потенциальным пользователям определять сферы эффективного применения разработанных методов и устройств поиска при разных ресурсных ограничениях для решения специфических задач ОСИ. Ассоциативное устройство для практически значимых ситуаций имеет скоростное преимущество (по количеству сравнений символов) на порядок и более (от 1,1 до 34 раз) по отношению к устройству, реализующему алгоритм Бойера-Мура.

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

СПИСОК ПУБЛИКАЦИЙ ПО ТЕМЕ ДИССЕРТАЦИИ

Статья в научном издании по перечню ВАК Минобрнауки РФ

1. Евсюков, В.С. Продукционные системы и теорема о конфликтных словах [Текст] / В.С. Евсюков, Е.А. Титенко // Известия Тульского государственного университета. Серия "Технологическая системотехника". Выпуск 15. ЦТула: Изд-во ТуГУ, 2008. - С. 92-98.

Статья

1. Евсюков, В.С. Устройство и алгоритм ассоциативного поиска вхождений / В.С. Евсюков, Е.А. Семенихин // Известия Курского государственного технического университета. - Курск: Изд-во КурскГТУ, 2009. - № 2 (27). - С. 52-62.

Материалы конференций и тезисы докладов

1. Евсюков, В.С. Стратегия равноправных выводов для быстрых символьных вычислений [Текст] / В.С. Евсюков, Е.А. Семенихин // Будущее информационных технологий в России: материалы конференции. - Курск, Индустриальный институт, 2006. - С. 13-17.
2. Евсюков, В.С. Аппаратный семафор для асинхронных устройств [Текст] / В.С. Евсюков, Е.А. Семенихин // Теоретические и прикладные вопросы современных информационных технологий: Материалы Всероссийской научно-технической конференции. - Улан-Удэ: Изд-во ВСГТУ, 2006. - Часть I. - С. 196-200.
3. Евсюков, В.С. Архитектура аппаратных средств для медицинских систем поддержки принятия решений [Текст] / В.С. Евсюков, Е.А. Титенко, Е.А. Семенихин // X Международная научно-техническая конференция "Медико-экологические информационные технологии - 2007". Сборник научных статей. - Курск: Изд-во КурскГТУ, 2007. - С.121-126.
4. Евсюков, В.С. Многокритериальный анализ безвозвратных алгоритмов поиска символьной информации [Электрон. ресурс] / В.С. Евсюков, О.И. Атакищев, Е.А. Титенко, Е.А. Семенихин // Доклады VIII Всероссийской конференции молодых ученых по математическому моделированию и информационным технологиям, 27-29 ноября 2007 года. - Новосибирск, 2007. - Режим доступа:
5. Евсюков, В.С. Анализ модификаций алгоритма Кнута-Морриса-Пратта для параллельно-конвейерной реализации [Текст] / В.С. Евсюков, И.В. Атакищева, С.В. Малюк, Д.О. Соколов // Труды научно-технической конференции "Научное программное обеспечение в образовании и научных исследованиях". - СПб.: Изд-во Политехн. ун-та, 2008. - С. 153-157.
6. Евсюков, В.С. Аппаратно-ориентированный способ ассоциативного поиска битовой информации [Текст] / В.С. Евсюков, Е.А. Титенко, В.Ю. Мудрик, Е.А. Семенихин // Интеллектуальные системы: Труды Восьмого международного симпозиума (INTELSТ2008). - Нижний Новгород: Изд-во НГТУ, 2008. - С. 238-242.
7. Евсюков, В.С. Способ параллельного поиска вхождений образцов [Текст] / В.С. Евсюков, Е.А. Титенко, В.Ю. Мудрик // Сборник материалов VIII Международной конференции "Распознавание-2008". - Курск: Изд-во КурскГТУ, 2009. - Ч.2. - С. 119-120.

Патент

1. Пат. 84615 Российская Федерация, МПК G11C 15/00. Ассоциативная запоминающая матрица [Текст] / Титенко Е.А., Евсюков В.С, Семенихин Е.А., Атакищев А.О.; заявитель и патентообладатель Курск. гос. тех. ун-т.  - № 2009104196/22 ; заявл. 09.02.2009 ; опубл. 10.07.2009, Бюл. № 19.  - 14 с. : ил.

 

Соискатель а В.С. Евсюков

Подписано в печать л27 ноября 2009 г. Формат 60x84 1/16.

Печ. л. 1.0. Тираж 100 экз. Заказ

Курский государственный технический университет. Издательско-полиграфический центр Курского государственного технического университета 305040, г. Курск, ул. 50 лет Октября, 94.

     Авторефераты по темам  >>  Разные специальности - [часть 1]  [часть 2]