Введение к работе
Актуальность темы. Управление временной (вычислительной) сложностью класса задач обработки символьной информации (ОСИ) связывается с созданием высокопроизводительных устройств и вычислительных систем ОСИ, ориентированных на параллельную обработку символьных данных при реализации поисково-переборных вычислительных алгоритмов, имеющих доминирующий характер в современных устройствах вычислительной техники. При этом использование естественного параллелизма и учет особых отношений в обработке независимых элементов символьных данных и их фрагментов является достаточным, но не необходимым условием уменьшения временной сложности (временных затрат), так как класс задач ОСИ характеризуется недетерменированностью вычислений. Необходимым условием является ориентация на безвозвратные конвейерные и параллельные вычисления без введения ограничений на структуру данных, что позволяет исключать холостые шаги поисковых вычислений.
Огромная значимость задач ОСИ подтверждается научно-техническими проектами и программами в оборонном комплексе, разработкой динамически реконфигурируемых вычислительных систем (семейство РВС на базе НИИ МВС ЮФУ), ориентированных на решение вычислительно трудоемких научно-технических задач в таких областях как системы обработки знаний, предсказание климатических условий, разработкой систем лексического анализа и технологии естественно-языковых интерфейсов к коммерческим СУБД (соответственно 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 таблицы.
Области возможного использования. Результаты диссертационной работы могут быть использованы при проектировании высокоскоростных устройств ОСИ, в системах поддержки недетерменированных процессов логического вывода, в системах поддержки принятия решений.
