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

00348ЭБ17

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

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

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

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

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических наук

о А л р н 7ппд

КУРСК-2009

003489617

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

Научный руководитель:

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

Официальные оппоненты:

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

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

Ведущая организация:

Орловский государственный технический университет

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

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

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

Ученый секретарь совета по защите докторских и кандидатских диссертаций Д 212.105.02

Е. А. Титенко

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

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

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

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

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

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

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

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

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

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

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

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

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

2. Разработка методов безвозвратной операции поиска и исследование их временных затрат.

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

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

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

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

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

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

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

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

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

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

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

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

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

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 патент №8461 РФ.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

В работе решаются задачи поиска всех вхождений и пересечений символь ных данных, которые формулируются следующим образом. Пусть заданы образе О длиной ш символов и текст Б длиной п символов, где п>0, т > 0 и т < п. Тре буется найти позиции всех вхождений О в 8, т.е. определить все наименьшие 1 при которых 1 + т- 1) = 0(1, т). Если собственное начало О пересекается собственным окончанием Б, то найти позицию максимального пересечения собст венного начала О с собственным окончанием Б, т.е. определить наименьшее ¡, пр

котором S(i, i + j - 1) = 0(1, j), где 0<j<mHÍ+j-l=n. Если собственное окончание О пересекается с собственным началом S, то найти позицию максимального пересечения собственного окончания О с началом S, т.е. определить наименьшее j, при котором S(l, m -j + 1) = 0(j, m). Ситуация пересечения слов О и S описывается следующей конструктивной дизъюнкцией:

(0H=SK)v(0K=SH) = l,

где Он, Ок - собственные начало и окончание О; SH, SK - собственные начало и окончание S.

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

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

Сравнение Сдвиг Сравнение Сдвиг Сравнение Сдвиг Сравнение

4 4 4 4 4444 4444 4444

а) 0) в) г) д) е) ж)

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

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

ется побитовой обработкой элементов строк и столбцов, входящих в диагонали матрицы, а направление поиска - от последнего символа к первому по каждой диагонали, как показано на рис. 2, причем обработка каждой диагонали осуществляется параллельно с остальными диагоналями характеристической матрицы, что является отличительной особенностью метода матричного поиска. Схема метода матричного поиска демонстрируется на рис. 2, для 8=АОСАВСАОАВС и 0=АВСА0, А = {А, В, С, Б}. Начальное состояние характеристической матрицы поисковых ячеек показано на рис. 2а.

юсм>

¡шслвсюис к в с А о

00010000100 11111111111

Ч> ^ Ч) М Ч) Ч) 'Ч! Ч1 'ч> \о

Ч1ЧчОчОМчОЧ)\)Ч1\1чО

Ч)\ГчГЧ)\) М Ч) Ч) N1 чГм

ч'Ч)\]'Ч)'Ч)'Ч) 4 4)4: ЧГЧ)

ч) м 4) 4> \) 4> 4> м \| 4)41

тпг

а)

11111111111 11111111111 1Н 11 С 11 1В с

б)

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

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

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

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

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

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

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

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

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

Операционный блок работает в одном из четырех состояний: запись, чтение, ассоциативный поиск, реконфигурация — при этом работа устройства в любом из его состояний начинается с подачи сигнала синхронизации "СЬОСК"=1.

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

Нмало )

( кои«ц ) символом образца

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

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

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

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

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

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

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

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

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

&(di) - конъюнкция результатов сопоставления символов образца и текста по диагоналям характеристической матрицы, где i = 1.. л + m -1

1-я диагональ проходит через поисковую ячейку ein;

2-я диагональ проходит через поисковые ячейки сгп

— C1(k*m-2);

1-я (I = 1..П+ m -1) диагональ проходит через поисковые ячейки се, где i = 1 ..m, j -1 ..п;

(п + m - 2)-я диагональ проходит через поисковые

ЯЧеЙКИ Cm2-C{m-1)i;

(п + т-диагональ проходитчерез поисковую ячейку Cmi.

( Конц )

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

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

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

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

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

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

Логически!« анлякитор ХШ . ЦТ]

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

Время (с)

б0.000п 120.000п 180.000п 240.000п ЗОО.ОООп

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

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

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

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

Результаты экспериментальных исследований алгоритмических сложностей процессов поиска всех вхождений для моделируемых устройств приведены в таблицах 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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Статья

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

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

3. Евсюков, B.C. Стратегия равноправных выводов для быстрых символь ных вычислений [Текст] / B.C. Евсюков, Е.А. Семенихин // Будущее информаци онных технологий в России: материалы конференции. - Курск, ИндустриальныГ институт, 2006. - С. 13-17.

4. Евсюков, B.C. Аппаратный семафор для асинхронных устройств [Текст] B.C. Евсюков, Е.А. Семенихин // Теоретические и прикладные вопросы совре менных информационных технологий: Материалы Всероссийской научно технической конференции. - Улан-Удэ: Изд-во ВСГТУ, 2006. - Часть I. - С. 196 200.

5. Евсюков, B.C. Архитектура аппаратных средств для медицинских систе?

поддержки принятия решений [Текст] / B.C. Евсюков, ЕЛ. Титенко, Е.А. Семени-хин // X Международная научно-техническая конференция "Медико-экологические информационные технологии - 2007". Сборник научных статей. -Курск: Изд-во КурскГТУ, 2007. - С.121-126.

6. Евсюков, B.C. Многокритериальный анализ безвозвратных алгоритмов поиска символьной информации [Электрон, ресурс] / B.C. Евсюков, О.И. Атаки-щев, Е.А. Титенко, Е.А. Семенихин // Доклады VIII Всероссийской конференции молодых ученых по математическому моделированию и информационным технологиям, 27-29 ноября 2007 года. - Новосибирск, 2007. - Режим доступа: http://www.ict.nsc.ru/ws/YM2007/12889/evs.html.

7. Евсюков, B.C. Анализ модификаций алгоритма Кнута-Морриса-Пратга для параллельно-конвейерной реализации [Текст] / B.C. Евсюков, И.В. Атакище-ва, C.B. Малюк, Д.О. Соколов // Труды научно-технической конференции "Научное программное обеспечение в образовании и научных исследованиях". - СПб.: Изд-во Политехи, ун-та, 2008. - С. 153-157.

8. Евсюков, B.C. Аппаратно-ориентированный способ ассоциативного поиска битовой информации [Текст] / B.C. Евсюков, Е.А. Титенко, В.Ю. Мудрик, Е.А. Семенихин // Интеллектуальные системы: Труды Восьмого международного симпозиума (INTELS'2008). - Нижний Новгород: Изд-во НГТУ, 2008. - С. 238-242.

9. Евсюков, B.C. Способ параллельного поиска вхождений образцов [Текст] / B.C. Евсюков, Е.А. Титенко, В.Ю. Мудрик // Сборник материалов VIII Международной конференции "Распознавание-2008". - Курск: Изд-во КурскГТУ, 2009. -4.2.-С. 119-120.

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

Подписано в печать «27» ноября 2009 г. Формат 60x84 1/16. Печ. л. ЬО. Тираж 100 экз. Заказ

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

Патент

Соискатель

B.C. Евсюков

ВВЕДЕНИЕ.

ГЛАВА 1. ОБЗОР СУЩЕСТВУЮЩИХ АППАРАТНЫХ АРХИТЕКТУР И ПРОГРАММНЫХ СРЕДСТВ ДЛЯ ОБРАБОТКИ СИМВОЛЬНОЙ ИНФОРМАЦИИ И ВЫСОКОПРОИЗВОДИТЕЛЬ-НЫХ ПАРАЛЛЕЛЬНЫХ ВЫЧИСЛЕНИЙ.

1.1. Обработка символьной информации и быстрые символьные вычисления.

1.1.1. Введение в теорию обработки символьной информации.

1.1.2. Современное состояние процессов обработки символьной информации.

1.1.3. Символьные процессоры и архитектуры.

1.1.4. Быстрые символьные вычисления.

1.2. Обзор аппаратных архитектур для высокопроизводительных вычислений.

1.2.1. Архитектура Фон Неймана.

1.2.2. Гарвардская архитектура.

1.2.3. CISC и RISC-архитектуры.

1.2.4. Суперскалярные и VLIW-процессоры.

1.2.5. Процессоры логического вывода.

1.3. Классификации вычислительных систем.

1.4. Параллелизм вычислений и его типы.

1.4.1. Параллелизм на уровне инструкций.

1.4.2. Параллелизм данных.

1.4.3. Параллелизм задач.

1.4.4. Кластеризация вычислительных систем.

1.4.5. Закон Амдала.

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

1.6. Экспертные системы и символьная обработка.

1.7. Исчислительные продукционные системы.

1.8. Сущность предлагаемого подхода к созданию методов параллельного поиска вхождений и пересечений символьных данных.

1.9. Выводы по главе.

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

2.1. Теоретический базис конструктивных символьных вычислений.

2.2. Продукционные исчисления.

2.3. Проблемы генерации ветвящихся конструктивных процессов.

2.4. Теорема о конфликтных словах.

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

2.5.1. Метод ассоциативного параллельного поиска вхождений.

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

2.6. Выводы по главе.

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

3.1. Технические устройства для поиска вхождений и пересечений.

3.2. Разработка ассоциативного устройства поиска вхождений.

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

3.2.2. Разработка структурных схем основных блоков устройства.

3.2.3. Разработка алгоритмов работы устройства и описание его функционирования.

3.3. Разработка матричного устройства поиска вхождений и пересечений.

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

3.3.2. Разработка структурных схем основных блоков устройства.

3.3.3. Разработка алгоритмов работы устройства и описание его функционирования.

3.4. Расчет аппаратной сложности разработанных устройств.

3.5. Выводы по главе.

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

4.1. Синтез имитационной модели и моделирование работы матричного устройства.

4.1.1. Описание моделирующей среды.

4.1.2. Синтез имитационной модели.

4.1.3. Моделирование работы устройства.

4.2. Программное моделирование работы разработанных методов поиска.

4.2.1. Описание программно-аппаратной среды моделирования.

4.2.2. Программные модели устройств.

4.2.3. Показатель скорости работы моделируемых устройств.

4.2.4. Экспериментальные исследования скорости работы моделируемых устройств.

4.3. Выводы по главе.

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

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

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

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

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

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

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

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

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

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

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

2. Разработка методов безвозвратной операции поиска и исследование их временных затрат.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

2008), VIII Международной конференции "Распознавание-2008" (г. Курск,

2009), а также на научных семинарах кафедры программного обеспечения вычислительной техники КурскГТУ в период с 2006 по 2009 гг.

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

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

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

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

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

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

4.3. Выводы по главе

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

2. Результаты моделирования работы имитационной модели матричного устройства для длины образца равной 3 символам и длины текста равной 6 символам показали, что устройство корректно выдает результаты поиска через —270 не после начала его работы.

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

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

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

ЗАКЛЮЧЕНИЕ

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

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

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

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

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

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

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

1. Roosta, S.H. Parallel processing and parallel algorithms Текст.: theory and computation / S.H. Roosta. Springer-Verlag New York, 2000.

2. Yang, L.T. High-performance computing Текст.: paradigm and infrastructure / L.T. Yang, M. Guo. John Wiley and Sons, 2006.

3. Хопкрофт, Д. Введение в теорию автоматов, языков и вычислений. Второе издание Текст. / Д. Хопкрофт, Р. Мотвани, Д. Ульман. М.: "Вильяме", 2008.

4. Смит, Б. Методы и алгоритмы вычислений на строках Текст. / Б. Смит. -М.: "Вильяме", 2006.

5. Авдеев, Ю. У порога пятого поколения Текст. / Ю. Авдеев // Газета "Красная звезда", 05.03.2008. М.: "Красная звезда", 2008.

6. Каляев, И.А. Реконфигурируемые вычислительные системы Текст. / И.А. Каляев, И.И. Левин, Е.А. Семерников // Гироскопия и навигация. М.: Изд-во ЦНИИ "Электроприбор", 2009.

7. Болдасов, М.В. О генераторе естественно-языковых высказываний для системы ЕЯ-интерфейсов к базам данных InBASE Текст. / М.В. Болдасов// Материалы научно-технической конференции "Искусственный Интеллект 2002". Таганрог-Донецк, 2002 - Т.2. - С. 23-25.

8. Кононенко, И.С. Система ALEX как средство для многоцелевой автоматизированной обработки текстов Текст. /И.С. Кононенко // Труды Международного семинара "Диалог 2002" по компьютерной лингвистике и ее приложениям. Протвино, 2002. - Т.2.

9. Гриценко, А.В. Метод и алгоритмы синтеза топологической структуры сети обмена разнородными данными и знаниями в социально-экономических системах Текст.: диссертация кандидата технических наук: 05.13.10 / А.В. Гриценко. Курск, 2007.

10. Pirklbauer, К. A study of pattern-matching algorithms Текст. / К. Pirklbauer // Structured Programming, Vol. 13. Springer-Verlag New York, 1992.

11. Crochemore, M. Algorithms on Strings Текст. / M. Crochemore, C. Hancart, T. Lecroq. Cambridge University Press, 2007.

12. Matooane M. A Parallel Symbolic Computation Environment Текст.: Structures and Mechanics / M. Matooane, A. Norman // Proceedings of the 5th International Euro-Par Conference on Parallel Processing. — SpringerVerlag London, 1999.

13. Бройдо, В. JI. Архитектура ЭВМ и систем Текст. / В. JI. Бройдо, О. П. Ильина. СПб.: Изд.-во "Питер", 2009.

14. Von Neumann, J. Collected Works Текст. / J. von Neumann. New York, Oxford, London, Paris: Pergamon Press, 1961-1963. - V.l-6.

15. Воеводин, Вл.В. Методы описания и классификации вычислительных систем Текст. / Вл.В. Воеводин, А.П. Капитонова. — М.: Изд.-во МГУ, 1994.

16. Flynn, М. Very high-speed computing system Текст. / M. Flynn. Proc. IEEE. 1966.-N54.

17. Hockney, R. Classification and Evaluation of ParallelComputer Systems Текст. / R. Hockney // Lecture Notes in Computer Science. Springer Berlin/Heidelberg, 1987. -N 295.

18. Skillicorn, D. A Taxonomy for Computer Architectures Текст. / D. Slcillicorn // Los Alamitos, CA, USA: IEEE Computer Society Press, 1988. V.21. N 11.

19. Воеводин, B.B. Параллельные вычисления Текст. / В.В. Воеводин, Вл.В. Воеводин. СПб.: БХВ-Петербург, 2004.

20. Ва, Б.У. ЭВМ для обработки символьной информации Текст. / Б.У. Ва, М.Б. Лоурай, Ли Гоцзе // ТИИЭР. 1989. - Т.77. №4.

21. Эйсымонт, Л.К. Компьютеры для обработки символьной информации Текст. / Л.К. Эйсымонт // Успехи современной радиоэлектроники. Зарубежная радиоэлектроника. М.: Издательство "Радиотехника", 1990. -№4.

22. Feigenbaum. Е.А. The Fifth Generation Текст.: Aritficial Intelligence and Japan's Computer Challenge to the World / E.A. Feigenbaum, P. McCorduck. -Boston, MA, USA: Addison-Wesley Longman Publishing Co., Inc., 1983.

23. Amdahl, G. The Validity of Single Processor Approach to Achieving Large Scale Computing Capabilities Текст. / G. Amdahl // AFIPS Conference Proceedings. AFIPS Press, Reston, Va., 1967. -V.30.

24. Комолкин, A.B. Программирование для высокопроизводительных ЭВМ Текст. Учебно-методическое пособие по курсу лекций "Современные технологии программирования" / А.В. Комолкин, С.А. Немнюгин. - СпбГУ, 1998.

25. Левин, М.П. Параллельное программирование с использованием ОрепМР Текст. / М.П. Левин. М.: Бином. Лаборатория знаний, 2008.

26. Антонов, А.С. Параллельное программирование с использованием технологии MPI Текст. / А.С. Антонов. М.: Изд-во МГУ, 2004.

27. Geist, A. PVM Текст.: Parallel Virtual Machine. A Users' Guide and Tutorial for Networked Parallel Computing / A. Geist. Massachusetts Institute of Technology, 1994.

28. Фридл, Дж. Регулярные выражения Текст. / Дж. Фридл. — СПб.: "Питер", 2001.

29. Hume, A. Fast string searching Текст. / A. Hume, D. Sunday // Software Practice and Experience, Vol. 21, No. 11, November 1991. Addison-Wesley Publishing Company, Inc., Reading, MA, 1991.

30. Boyer, R.S. A fast string searching algorithm Текст. / R.S. Boyer, J.S. Moore // Communications of the ACM. New York, NY, USA: ACM, 1977. - V.20, N.10.

31. Успенский, B.A. Теория алгоритмов Текст.: основные открытия и приложения / В.А. Успенский, A.JI. Семенов. М.: Наука, 1987.

32. Нильсон, Н. Д. Искусственный интеллект. Методы поиска решений Текст. / Н. Д. Нильсон. М.: Мир, 1973.

33. Таунсенд, К. Проектирование и программная реализация экспертных систем на персональных ЭВМ Текст. / К. Таунсенд, Д. Фохт. — М.: Финансы и статистика, 1990.

34. Чекинов, С.Г. Экспертные системы в системах управления Текст.: состояние и перспективы / С.Г. Чекинов // Информационные технологии. -М.: Изд-во "Новые технологии", 2001. — №4.

35. Кузнецов, Д.Н. Процессор КРОНОС в мультипроцессорной системе Текст. / Д.Н. Кузнецов, А.Е. Нед оря, А.В. Осипов, Е.В. Тарасов // Вычислительные системы и программное обеспечение. ВЦ СОАН СССР. -Новосибирск, 1986.

36. Котов, В.Е. Архитектура макета системы МАРС Текст. / В.Е. Котов, А.Г. Марчук // Вычислительные системы и программное обеспечение. ВЦ СОАН СССР. Новосибирск, 1986.

37. King, A. Distributed Parallel Symbolic Execution Текст. / A. King. B.S., Kansas State University, 2005.

38. Abad, A. ATESAT Текст.: A symbolic processor for artificial satellite theory / A. Abad, A. Elipe, J. F. Palacian у J. F. San Juan // Mathematics and Computers in Simulation, vol. 45. Elsevier Science Publishers B.V. Amsterdam, The Netherlands, 1998.

39. Navarro, J. A New Symbolic Processor for the Earth Rotation Theory Текст. / J. Navarro, J. Ferrandiz // Celestial Mechanics and Dynamical Astronomy, Volume 82, Number 3, March 2002. Springer-Verlag Netherlands, 2002.

40. Chapman, B. Shared memory parallel programming with OpenMP Текст. / В. Chapman // 5th International Workshop on OpenMP Applications and Tools, WOMPAT 2004, Houston, TX, USA, May 17-18, 2004. Springer-Verlag Berlin Heidelberg, 2005.

41. Salton, G. Automatic Text Processing Текст. / G. Salton. Addison-Wesley Publishing Company, Inc., Reading, MA, 1989.

42. Gonnet, G.H. Handbook of Algorithms and Data Structures in Pascal and C, 2nd edition Текст. / G.H. Gonnet, R. Baeza-Yates. Addison-Wesley, Wokingham UK, 1991.

43. Кохонен, Т. Ассоциативные запоминающие устройства Текст. / Т. Кохонен.-М.: "Мир", 1982.

44. Пирс, Ч. С. Логические основания теории знаков Текст. / Ч.С. Пирс. — СПб.: Лаборатория метафизических исследований философского факультета СпбГУ, Алетейя, 2000.

45. Лингвистический энциклопедический словарь Текст. / Гл. ред. В.Н. Ярцева. -М.: Советская энциклопедия, 1990.

46. Марков, A.A. Избранные труды Текст. Т. II. Теория алгорифмов и конструктивная математика, математическая логика, информатика и смежные вопросы / A.A. Марков. М.: Изд-во МЦНМО, 2003.

47. Кушнер, Б.А. Лекции по конструктивному математическому анализу Текст. / Б.А. Кушнер. М.: Наука, 1973.

48. Кондаков, Н.И. Логический словарь-справочник Текст. / Н.И. Кондаков. -М.: Наука, 1975.

49. Рузавин, Г.И. О природе математического знания Текст. / Г.И. Рузавин. — М.: 1968.

50. Философский энциклопедический словарь Текст. / Гл. ред. С.С. Аверинцев. -М.: Советская энциклопедия, 1989.

51. Маслов, С.Ю. Теория дедуктивных систем и ее применения Текст. / С.Ю. Маслов. -М.: Радио и связь, 1986.

52. Довгаль, В.М. Основы теории быстрых символьных вычислений в продукционных системах Текст.: методы акселерации работы автономных продукций: Учебное пособие / В.М. Довгаль, Ф.А. Старков, О.И. Атакищев. -Курск, гос. тех. ун-т, Курск, 2002.

53. Кулик, Б.А. Система поиска слов в произвольном тексте Текст. / Б.А. Кулик // Программирование. М.: МАИК "Наука/Интерпериодика", 1987. -№1.

54. Рабаи, Ж.М. Цифровые интегральные схемы. Методология проектирования Текст. / Ж.М. Рабаи, А. Чандракасан, Б. Николич. 2-е изд. -М.: "Вильяме", 2007.

55. Точи, Р.Дж. Цифровые системы. Теория и практика Текст. / Р.Дж. Точчи, Н.С. Уидмер. 8-е изд. -М.: "Вильяме", 2004.

56. Уилкинсон, Б. Основы проектирования цифровых схем Текст. / Б. Уилкинсон. М.: "Вильяме", 2007.

57. Патент №2168216. Ассоциативная запоминающая матрица Текст. / Борисов В.В. и др. (РФ). — М.: Роспатент; опубликовано: 27.05.2001.

58. Патент №2197778. Информационно-поисковая система Текст. / Довгаль В.М., Шевелев С.С. (РФ). М.: Роспатент; опубликовано: 27.02.2003, бюл. №6.

59. Патент №72771. Устройство для параллельного поиска и обработки данных Текст. / Лисицын JI.A., Титенко Е.В., Довгаль В.М. (РФ). М.: Роспатент; опубликовано: 27.04.2008, бюл. №12.

60. Шило, B.JI. Популярные микросхемы КМОП Текст. Справочник (МРБ1246). Серии К176, К561, К564, КР1561, К1554, К1564, К1594 / В.Л. Шило. М.: Изд.-во "Горячая линия - Телеком", 2001.

61. Угрюмов, Е.П. Цифровая схемотехника Текст. / Е.П. Угрюмов. СПб.: БХВ-Петербург, 2004.

62. Хернитер, М.Е. Multisim. Современная система компьютерного моделирования и анализа схем электронных устройств Текст. / М.Е. Хернитер. М.: Изд.-во "ДМК Пресс", 2006.

63. Загидуллин, Р.Ш. Multisim, Labview, Signal Express. Практика автоматизированного проектирования электронных устройств Текст. / Р.Ш. Загидуллин. М.: Изд.-во "Горячая Линия - Телеком", 2009.

64. Шамис, В. С++ Builder Borland Developer Studio 2006 Текст. / В. Шамис. СПб.: Изд.-во "Питер", 2006.

65. Феррари, Д. Оценка производительности вычислительных систем / Д. Феррари. -М.: Мир, 1981.

66. Французов, Д. Оценка производительности вычислительных систем / Д. Французов // Журнал "Открытые Системы". М.: Изд.-во "Открытые системы". - №2(16).