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

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

Лисицин Леонид Александрович

МЕТОДЫ, АЛГОРИТМЫ И УСТРОЙСТВО СОПОСТАВЛЕНИЯ ПО ОБРАЗЦУ

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

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

СЮ3469867

Курск 2009

003469867

Работа выполнена в ГОУ ВПО

«Курский государственный технический университет»

Научный руководитель: доктор технических наук, профессор Довгаль Виктор Митрофанович

Официальные оппоненты: доктор технических наук, с.н.с.

A.А. Бурмака

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

B.В.Елагин

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

Защита состоится 8 июня 2009 г. в 1600 часов на заседании диссертационного совета Д 212.105.02 при Курском государственном техническом университете по адресу: 305040, г. Курск, ул. 50 лет Октября, 94 (конференц-зал).

Заверенные отзывы на автореферат в двух экземплярах направлять по адресу: 305040, г. Курск, ул. 50 лет Октября, 94, ученому секретарю.

С диссертацией можно ознакомиться в библиотеке университета.

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

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

и кандидатских диссертаций Д212.105.02,

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

Титенко Е.А.

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

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

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

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

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

Работа выполнялась в рамках госбюджетных НИР кафедры программного обеспечения вычислительной техники Курского государственного технического университета, а также по гранту А04-3.16-695 Федерального агентства по образованию «Метода акселерации работы продукций и символьные мультипроцессоры автоматизированных систем ситуационного управления» при участии автора данной диссертационной работы.

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

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

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

Основные задач» диссертационного исследования:

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

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

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

4. Выполнить экспериментальное исследование характеристик устройств.

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

Научная новизна. В результате проведенных теоретических исследований получены следующие основные научные результаты:

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

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

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

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

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

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

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

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

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

Основные положения, выносимые на защиту:

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

2. Матричное устройство безотступного параллельного сопоставления и его структурно-функциональная организация.

3. Результаты экспериментальных исследований скоростных характеристик и аппаратных затрат разработанных устройств сопоставления.

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

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

Структура и объём работы. Диссертация состоит из введения, четырех глав и заключения, изложенных на 122 страницах машинописного текста, содержит 32 рисунка, 8 таблиц, список литературы из 65 наименований и 5 приложений объемом в 45 страниц.

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

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

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

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

Установлено, что при реализации символьных вычислений на различных аппаратных платформах во всем многообразии архитектур осуществления символьных вычислений, включая неймановскую архитектуру, используется широкий спектр алгоритмов выполнения операции сопоставления. При этом в основном используется программная поддержка КМП-алгоритма и алгоритма Бойера Мура, в микропроцессоре символьного компьютера Facom Alpha фирмы Fujitsu применяется программно-аппаратная реализация КМП-алгоритма, а в системе OPS-5 выполнена аппаратная поддержка операции сопоставления с анализируемой глубиной отступа. Установлено, что сопоставление является доминирующей операцией при обработке строк и списков, изображений и аудиофайлов на современных компьютерах и вычислительных системах. При этом разметка позиций вхождения образцов специальными символами-указателями, осуществляемая устройствами сопоставления, приводит к существенным искажениям обрабатываемого слова и созданию «мусора». Это обстоятельство требует введения дополнительных аппаратных средств при согласовании структуры данных с другими процессорами или типовыми устройствами вычислительной техники, в частности часто используются специальные аппаратные и/или программные сборщики мусора.

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

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

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

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

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

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

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

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

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

Рассмотрим два произвольных слова Уи№в виде цепочек символов:

где для 1 = 1, п, щ е А, для] = I, ш, А - рабочий алфавит.

Пусть — это образец, V — обрабатываемое слово, в котором требуется найти вхождение образца

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

• указатель на текущую букву обрабатываемого слова указатель на текущий символ образца у.=1;

(1) (2)

• если 1 < п и } < ш, где п - длина обрабатываемого слова, ш - длина образца, тогда после выполнения условия равенства букв V; и осуществляется переход к сравнению следующих букв (к=1+1, .|:=}+1);

• при неравенстве ^ и побуквенное сопоставление слов начинается с первой буквы образца (]:=1) и текущей буквы слова;

• алгоритм завершает работу с результатом «вхождение обнаружено» в позиции 0-3+1) слова V при истинности условия ] > ш или с результатом «вхождение не обнаружено» при выполнении условия 1 > п.

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

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

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

Местоположение итераций позволяет выделить следующие структуры сложных образцов: {Р^ - итерация слова по всей своей длине (1); {Р}Д - итерация в начале слова (префиксная итерация) (2); К{Р}; - итерация в конце слова (3);

{Р}|Л2 - итерация в середине слова (4); {Р1}Д{Р2}|- итерация в начале и конце слова.

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

Т=ш(к-ш+2) -1. (3)

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

Т=(к-<3)((1+1)+с1,

(4)

где с1 - число итераций в префиксе образца.

Для образцов вида ((а)2Ьс)зр будет справедлива формула Т=2^2+ё,

(5)

где g - общее число символов во внешних скобках с учетом внутренней итерации; с1 - число итераций внешних скобок.

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

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

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

Рассмотрим метод применения нуль-единичной характеристической матрицы. Пусть в общем алфавите Е мощностью 121 = заданы образец и обрабатываемое слово V как последовательности кодов символов из алфавита Е длиной впит символов (п < т) соответственно и пусть каждый символ образца и обрабатываемого слова (ОС) кодируется р=1о§2\у разрядами соответственно. Требуется определить все позиции начала вхождений V/ в V.

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

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

Работа устройства основана на обработке элементов двух множеств (при-

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

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

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

а - исходное состояние;

в — результат.

V 1 0 10 0 10 1 V

1 1 0 10 0 0 0 1 I

V 10 110 10 1 V

1 10100101 I

о 00100001 о

V IV! VIРУIVI О

в)

00

1 п п п п 1 Позиции начала двух 1 о и и о 1 вхождений

Ч'оЧ'ВЧ

ЧЧЧЧолчЧ

ЧГОЧ ЮЮ-ОЪ!

-ГГГГГГГГ"

11111111

V IV! VI Р V I V I О

в)

Рис. 1. Иллюстрация применения характеристической матрицы при сопоставлении

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

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

Рассмотрим организацию одного из перспективных для поисковых машин специализированных процессоров-акселераторов сопоставления. Приведем в доступной для экспертизы форме дескриптор его структурно-функциональной организации (патент № 72771 РФ). Функциональная схема устройства показана на

рисунке 2. Оно состоит из блока управления (БУ) и блока матричного поиска (БМП), связанных между собой управляющими шинами и шинами данных.

Старт БУ Нач .установка БМП

Чт. результ. Загрузка разр.

N Запись строк

к , 1 Дл. образца (Ы) ж .: ■ ,

„ ШДО / V

_ ШДР / к

^ ШДиА / / Р

Рис. 2 Обобщенная схема матричного устройства

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

Блок управления предназначен для формирования сигналов хранения исходных и результирующих данных, общего управления процессом поиска и представляет собой несложную комбинационную схему. Блок БУ содержит три управляющих входа: «Старт» (от внешнего устройства), вход N для задания размерности образца ( от внешнего устройства) и вход «Загрузка разрешена», также три выхода: «Начальная установка», «Запись строю) и выход N для задания размерности образца. Символы образца и ОС подаются по ШДО (шина данных образца) и по шина данных и адреса ОС (ЩДиА) в параллельном коде через информационные входы. Результат выдается по сигналу «Загрузка разрешена» по шина данных и адреса результата (ШДР).

Блок БМП (Рис. 3) содержит три управляющих входа: «Начальная установка» 1\ (первый вход) и вход «Запись строк» (второй вход), вход N для задания размерности образца, третий и четвертый - входы для подачи символов образца и ОС в параллельном коде через информационные входы 43 и 44 устройства, а также два информационных выхода - второй выход 52 устройства и выход «Загрузка разрешена».

Блок БМП содержит элемент задержки 1, состоящий из п пар инверторов, л регистров 2г2п для хранения кодов символов образца, ш регистров ЗрЗт для хранения кодов символов текста, характеристической матрицы ячеек 4)1-4пт и к триггеров 7 позиций, причем регистры 2, (¡=1-п) и (¡=1-т) содержат первый и второй управляющие входы, третий р-разрядный информационный вход и один выход соответственно. Первые и вторые входы п регистров 2 для хранения кодов символов образца и первые и вторые входы ш регистров 3 для хранения кодов символов текста соединены соответственно с первым и вторым управляющими входами БМП, третий вход которого разрядностью р*п бит предназначен для параллельной записи образца в регистры 2Г2„ и состоит из п групп разрядов по р разрядов каждая группа, кодирующих символы образца, причем 1-ая группа раз-

рядов (¡=1-п) подается на третий р-разрядный вход регистра 2¡ (¡=1-п), четвертый вход БМП разрядностью рхгп бит предназначен для параллельной записи текста в регистры Зит и состоит из т групп разрядов по р разрядов в каждой группе, кодирующих символы текста, причем ]-я группа разрядов 0=1-т) подается на третий р-разрядный вход регистра Зj 0=1-т). Второй управляющий вход блока БМП также соединен со входом элемента задержки 1.

Рис. 3. Структурная схема устройства БМП

Характеристическая матрица ячеек 4П-4„„, (рис. 3) имеет размер пхк ячеек (к=ш-п+1 - количество строк, а также диагоналей в матрице), причем каждая поисковая ячейка имеет три входа и один выход и содержит двухвходовую схему 5у сравнения на равенство р-разрядных кодов символов образца и текста и двух-входовый элемент 6 (И). Каждая двухвходовая схема 5у сравнения на равенство в составе поисковой ячейки 4,, состоит из р двухвходовых элементов в^р суммы по модулю два с инверсией, на первые входы которых подается соответствующий разряд из ¡-й р-разрядной группы третьего входа блока БМП, а на вторые входы двухвходовых элементов 8].8р суммы по модулю два с инверсией - соответствующий разряд из ]-й р-разрядной группы четвертого входа блока 4 матричного поиска. Все выходы двухвходовых элементов 8Г8Р суммы по модулю два с инверсией в составе двухвходовой схемы 5у сравнения на равенство соединены с р-входовым элементом 9 (И), выход которого является выходом двухвходовой схемы 5у сравнения на равенство. Первый и второй р-разрядные входы поисковой ячейки 4у соответственно соединены с первым и вторым р-разрядными входами двухвходовой схемы сравнения на равенство, выход которой является первым входом двух-

входового элемент 6 (И), второй вход которого является третьим входом поисковой ячейки 4д, выходом которой является выход двухвходового элемента 6 И.

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

Рис.4. Схема одной ячейки матрицы

Первые р-разрядные входы к ячеек ьй строки матрицы (¡=1-п) соединены с р-разрядным выходом регистра 2,. Р-разрядный выход регистра (¡=1-т) соединен со вторыми р-разрядными входами всех ячеек, входящих в ^й столбец матрицы. Выход каждой поисковой ячейки кроме ¡=1 (первая строка матрицы), соединен с третьим входом поисковой ячейки 4^.1, кроме ¡=п (последняя строка матрицы). Выход поисковой ячейки 41У (у=1-к), расположенной в первой строке матрицы, соединен с информационным входом 3 триггера 7» позиции. На третий вход каждой поисковой ячейки, расположенной в последней строке матрицы, подается значение логической «1», задавая тем самым направление поиска по соответствующей диагонали от последней строки матрицы к первой строке включительно.

Триггеры 7г7к позиций хранят результат поиска в виде к-разрядного кода, в котором значением логической «1» отмечены позиции начала вхождений образца в текст. Триггер 7¡ позиции (¡=1-к) содержит три входа (первый и второй - управляющие, третий - одноразрядный информационный вход) и один выход. Первый вход БМП соединен соответственно с первыми входами к триггеров 7 позиций, вторые входы к триггеров 7 позиций соединены с выходом элемента 1 задержки.

Выходы триггеров 7г?к позиций образуют к-разрядный информационный выход БМП.

Данное устройство работает следующим образом.

При подаче на вход сигнала «Старт» блок БУ формирует на вход «Начальная установка» блока матричного поиска импульсный сигнал начальной установки, который сбрасывает в нулевое состояние к триггеров 7 позиций по их входу 1, п регистров 2 по их входу 1 и m регистров 3 по их входу 1. После окончания действия сигнала начальной установки на второй вход «Запись строк» блока матричного поиска подается импульсный сигнал. Данный импульсный сигнал по входу «Запись строк» блока матричного поиска подается соответственно на вторые входы разрешения записи п регистров 2 для хранения кодов символов образца и на вторые входы разрешения записи ш регистров 3 для хранения кодов символов текста, обеспечивая тем самым запись п символов образца и ш символов текста в параллельном коде с входов 3 и 4 устройства. Также импульсный сигнал по входу «Запись строк» блока 4 матричного поиска через элемент 1 задержки подается соответственно на вторые входы разрешения записи к триггеров 7 позиций. Элемент 1 задержки, выполненный в виде п пар инверторов, необходим для завершения процессов параллельного поиска вхождений по диагоналям характеристической матрицы, состоящей из поисковых ячеек 4П - 4^. Поиск начинается с ячеек последней строки характеристической матрицы. Начальный k-битовый характеристический вектор, равный 11...1, подается на третьи входы ячеек последней строки матрицы и определяет тем самым направление параллельного поиска по всем диагоналям характеристической матрицы - от поисковых ячеек последней строки до ячеек первой строки включительно. Время параллельного поиска вхождений не зависит от количества диагоналей, а определяется величиной Т=птц, где Ти - время задержки в элементе 6 (И). По завершении процессов поиска импульсный сигнал с выхода элемента 1 задержки через время Т'=п2т1ив (2тинв - время задержки на паре инверторов) записывает k-битовый результат поиска начала вхождений в триггеры 1-1 к позиций. Выходы триггеров 7j-7k позиций являются к-разрядным выходом блока БМП и образуют второй выход устройства 52 рис. 3.

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

В данной главе выполнены оценки аппаратных затрат защищаемого устройства и известных устройств сопоставления, разработанных на кафедре программного обеспечения вычислительной техники КурскГТУ. Аппаратные затраты в транзисторах на последовательное устройство 9607 транз., на конвейерное устройство составляют 19797 транз., на параллельное (ассоциативное) устройство 59558 транз., на матричное устройство 48014 транз. в виде одного модуля при n=m=16.

Таким образом, в третьей главе создана структурно-функциональная организация нового устройства-акселератора сопоставления, создающего основу для постановки НИОКР.

В четвертой главе приводятся результаты исследования скоростных характеристик разработанного устройства сопоставления и устройств-аналогов. Данная глава посвящена разработке программных моделей и экспериментальному исследованию скоростных характеристик разработанного устройства по отношению к аналогам, в том числе и к устройствам сопоставления, разработанным на кафедре программного обеспечения Курского государственного технического университета. В экспериментальных исследованиях использовались программные модели следующих устройств: последовательное; конвейерное; параллельное (ассоциативное); матричное. В качестве эталонной модели использовался микропроцессор Intel Pentium IV , реализующий строковую функцию strstr библиотеки <string.h> Borland С++ 6.0. Время, затрачиваемое устройством на процесс сопоставления, измеряется в машинных тактах. Под машинным тактом традиционно принимается фиксированный квант времени, за которое устройство реализует одну элементарную операцию символьного сравнения.

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

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

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

На рисунках устройства обозначены следующим образом: У1 - последовательное, У2 - конвейерное, УЗ- параллельное (ассоциативное ), Матр - матричное, УЭВМ - эталонный компьютер.

Таким образом, в четвертой главе завершено диссертационное исследование в соответствии с его целью и задачами.

8 о,г

&

-" ■ ■ УЗВМ Млгр.

6 8 10 12 16 20 24 2» 32 Ал мм* обраац«, бумми

Рис. 5. Графики зависимостей временных затрат исследуемых устройств (среда Б)

3 ;

12В 2 56 512 Ю24 2С148 4096 8192 16384 32768 ОвъСмоврабатыяммота спооа

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

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

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

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

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

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

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

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

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

Публикации по перечню ВАК:

1. Лисицын, JI.A. Быстрые символьные вычисления в медицинских системах поддержки принятия решений [Текст] / JI.A. Лисицин, С.Г. Емельянов, Е.А. Титенко // Вестник новых медицинских технологий. 2006. №2. С.158-160.

Публикации:

2. Лисицин, Л.А. Анализ стратегий выводов в экспертных системах для разработки методов быстрых символьных вычислений [Текст] / Л.А. Лисицин, В.М. Довгаль, Е.А. Титенко // Теоретические и прикладные вопросы современных информационных технологий: матер. VII Всерос. науч.-техн. конф. 1 Восточно-Сибирский гос. технол. ун-т., Улан-Удэ, 2006. С. 162-166.

3. Довгаль, В.М. Способ параллельной реализации подстановки [Текст] / Л.А. Лисицин, Е.А. Титенко, С.В. Малюк // Интеллектуальные системы (INTELS'2008): VIII Междунар. симпоз. Н.Новгород, 2008. С. 242-244.

4. Лисицин, Л.А. Повышение быстродействия работы путем организации параллельного поиска в характеристической нуль-единичной матрице [Текст]/ Л.А. Лисицин, В.М. Довгаль // Известия Курск, гос. техн. ун-та. 2008. №4. С. 39-41.

Патенты

5. Устройство для параллельного поиска и обработки данных [Текст]: Пат. на полез, модель 72771 РФ, МПК G 06 F 12/00 / Л.А. Лисицин, Е.А.Титенко, В.М. Довгаль; патентообладатель ГОУ ВПО «Курск, гос. техн. ун-т»; № 2007149075/22: заявл. 25.12.2007; опубл. 27.04.2008, Бюл.№12.

Соискатель

Л.А.Лисицин

Подписано в печать 05.05.2008. Формат 60x84 1/16. Бумага офсетная. Усл. печ. л. 1,0. Тираж 100 экз. Заказ 205. Курский государственный технический университет. Издательско-полиграфический центр Курского государственного технического университета. 305040, г. Курск, ул. 50 лет Октября, 94.

Оглавление

ВВЕДЕНИЕ.

ГЛАВА 1. Аналитический обзор систем обработки символьной информации на основе операции сопоставления и сущность предлагаемого подхода.

1.1. Особенности задач ОСИ.

1.2. Аппаратные средства ОСИ.

1.2.1. Основные направления развития технических средств ОСИ.

1.2.2. Особенности существующих технических средств ОСИ.

1.2.3. Специализированные процессоры ОСИ в составе универсальных вычислительных систем.

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

1.4. Выводы.

ГЛАВА 2. РАЗРАБОТКА ТЕОРЕТИЧЕСКИХ ОСНОВ.

АКСЕЛЕРАЦИИ ПРОЦЕССОВ СОПОСТАВЛЕНИЯ.

2.1, Основные понятия и определения конструктивной семиотики.

2.2. Исследование влияния структуры образца на скорость и корректность протекания процессов сопоставления.

2.4. Конвейеризация процесса сопоставления.

2.5. Алфавитный способ сопоставления (ассоциативный).

2.6 Повышение скорости путем организации параллельного поиска на основе характеристической нуль-единичной матрицы.

2.7. Выводы.

ГЛАВА 3. ОПИСАНИЕ ИЗВЕСТНЫХ УСТРОЙСТВ СОПОСТАВЛЕНИЯ И РАЗРАБОТКА МАТРИЧНОГО УСТРОЙСТВА.

3.1. Описание последовательного устройства сопоставления.

3.1.1. Описание структурной схемы устройства.

3.1.2. Описание алгоритмов и работа устройства.

3.2. Описание конвейерного устройства сопоставления.

3.2.1. Структурная схема устройства.

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

3.3. Описание ассоциативного устройства сопоставления.

3.3.1. Описание структурной схемы устройства.

3.3.2. Описание и функционирование алгоритмов работы устройства.

3.4. Разработка матричного устройства сопоставления.

3.4.1. Структура устройства.

3.4.2. Структура блока управления БУ.

3.4.3. Структура устройства БМП.

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

3.5. Расчет аппаратной сложности устройств сопоставления.

Выводы.

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

4.1. Разработка программных моделей устройств сопоставления.

4.2. Разработка способа измерения времени, затрачиваемого эталонным компьютером на выполнение процессов сопоставления.

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

4.4. Исследование временных характеристик моделируемых устройств.

4.4.1. Исследование временных характеристик устройств на образцах, в структуре которых нет итерации.

4.4.2. Исследование скорости работы устройств на образцах, в структуре которых имеется итерация в начале слова.

4.4.3. Исследование скорости работы устройств на образцах, в структуре которых имеется итерация в конце слова.

4.4.4. Исследование скорости работы устройств на образцах, в структуре которых имеется итерация в начале и конце слова.

4.4.5. Исследование работы устройств на образцах, в структуре которых есть итерация в середине слова.

4.4.6. Исследование скорости работы устройств на образцах, состоящих из итерации.

4.5. Выводы.

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

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

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

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

Работа выполнялась в рамках госбюджетных НИР кафедры программного обеспечения вычислительной техники Курского государственного технического университета, а также по гранту А04-3.16-695 Федерального агентства по образованию «Методы акселерации работы продукций и символьные мультипроцессоры автоматизированных систем ситуационного управления» при участии автора данной диссертационной работы.

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

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

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

Основные задачи диссертационного исследования:

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

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

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

4. Выполнить экспериментальное исследование характеристик устройств.

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

Научная новизна. В результате проведенных теоретических исследований получены следующие основные научные результаты:

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

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

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

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

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

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

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

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

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

Основные положения, выносимые на защиту:

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

2. Матричное устройство безотступного параллельного сопоставления и его структурно-функциональная организация.

3. Результаты экспериментальных исследований скоростных характеристик и аппаратных затрат разработанных устройств сопоставления.

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

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

Структура и объём работы. Диссертация состоит из введения, четырех глав и заключения, изложенных на 122 страницах машинописного текста, содержит 32 рисунка, 8 таблиц, список литературы из 65 наименований и 5 приложений объемом в 45 страниц.

4.5. Выводы

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

2. Определены с помощью разработанных программ временные характеристики устройств на наборе тестов.

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

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

ЗАКЛЮЧЕНИЕ

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

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

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

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

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

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

2. Эйсымонт, Л.К. Компьютеры для обработки символьной информации Текст. / Л.К. Эйсымонт / /Зарубежная радиоэлектроника. 1990. №4. С.3-28.

3. Левин К. Избавится ли машинный перевод от косноязычия? Текст. / К.Левин, М. Джинно //PC Magazine/RE. 1994. №8. С.183.

4. The Jellybean Machine (electronic resource)// MIT Artificial Intelligence Laboratory/ http://www.cva.stanford.edu/j-machine/cvajmachine.html, July 7, 1998.

5. Фу, К. Структурные методы в распознавании образов Текст.: К. Фу// М.: Мир, 1977.319 с.

6. Тамура, Н. Последовательная Пролог-машина РЕК Текст. :Н. Тамура и др. // Язык Пролог в пятом поколении ЭВМ. М.: Мир, 1988. С.310-325.

7. Попов, В.Э. Экспертные системы реального времени Текст. / В.Э.

8. Попов // Открытые системы. 1995. №10. С.66-71.

9. Лорьер, Ж.-Л. Системы искусственного интеллектаТекст. / Ж.-Л Лорьер //М.: Мир. 1991.568 с.

10. Поспелов, Д.А. Семиотическая модель искусственного интеллекта Текст.: Д.А. Поспелов // Программные продукты и системы, 1996. N5 С. 10-15.

11. Ю.Энн, Ноулз Распознавание речи в процессе ростаТекст. / Энн Ноулз, Ллойд Грей // PC Week, №30-31, 1998. С. 22.

12. Данкельбергер, Д. Резервное копирование массивов данныхТекст. / Д. Данкельбергер // LAN, №11, 1998.

13. Асадуллаев, С. Фирменные архитектуры хранилищ данныхТекст. / С. Асадуллаев //PC Week, №32-33, 1998. С. 17-19.

14. Искусственный интеллект: в 3 кн. Кн 1. Системы общения и экспертные системы Текст. / Справочник: под ред. Э.В. Попова.// М. : Радио и связь, 1990. 464 с.

15. Рихман, Д. Микрофон вместо клавиатуры: три примера внедрения систем распознавания и синтеза речи Текст.: Д. PHXMaH//ComputerWeek-MocKBa, 1995, N36. С. 42.

16. Джонсон, К. Нечеткая логика в системах распознавания образов Текст.: К. Джонсон //ComputerWeek. 1995. N 47. С.32.

17. Кузнецов, В.Е. Представление в ЭВМ неформальных процедур: продукционные системы Текст. / В.Е. Кузнецов//М.: Наука,1989. 158 с.

18. Типикин, А.П. Самообучение автоассоциативной модели нейронной сети высокого порядка Текст.: А.П. Типикин, А.В. Малышев, К.Ю. Тараненко //Известия КурскГТУ. N 2. 1998. С. 63-68.

19. Храмцов, П. Internet в сетях гипермедиа Текст.: П. Храмцов //Открытые системы сегодня, 1995. N 14. С. 1-11.

20. Юрвис, Дж. Последние достижения в области разработки Java-приложений Текст.: Дж. Юрвис //ComputerWeek-Москва, 1996. N 32. С.23-25, 40-41.

21. Pattern search apparatus and method (electronic resource): Пат. 5963942 США, МКИ G 06 F 017/30 // Igata Nobuyuki: Fujitsu Ltd. (Япония) -№773295; заявл. 24.12.1996; опубл. 5.10.99; приор. 16.01.96 №8005236, НКИ 707/006.

22. Устройство сортировки символов Текст.: Пат. 2067317 РФ, МКИ G 06 F 17/28./Довгаль В.М. и др.- 1996, Бюл. N 27.

23. Коллинз, Г., Блей Дж. Структурные методы разработки систем: от стратегического планирования до тестирования. Текст.: Г. Коллинз, Дж. Блей //Пер. с англ./ Под ред. и с предисл. В.М. Савинкова. М.: Финансы и статистика, 1986. 264 с.

24. Cray подтверждает свою репутацию самого мощного суперкомпьютера

25. Текст. //PC Week. 1996. №47. С. 27.

26. Клерк П. XILINX интегрирует технологии FPGA и Интернет Текст. / П.Клерк // Chip News, №2(35), 1999, с. 13-14.

27. NAL supercomputer sets new world record for processing speedTeKCT. // Atoms Japan,1996 . 40, №10. C. 20.

28. Multiprocessor-Server Текст. // Thechnica (Suisse). 1997. 46, №1-2. C.35.

29. Кузьминский, M. Современные архитектуры. Японский дракон. Текст. /М. Кузьминский //Computerworld Россия, 1996. №42. С. 17, 19.

30. Рудометов, Е. Перспективы развития многоядерных процессоров для ПК Текст.: статья //«IT News», 2007г.31 .Московская корпорация Intel (electronic resource):// Москва, 2008г.

31. Сайт http://www.ixbit/com/cpu/insides SPEC CPU2000-part-l.stml (electronic resource):/ 2008 г.

32. Lee, К., , Herman G.E. VLSI accelerators for large base systems Текст. /К. Lee, T.M. Hickey, V.W. Mak//"IEEE Micro", 1991, 11, №6, 8-20.

33. Church, A. The calculi of lambda-conversion. Ann. Math. Текст.: A. Church // Studies, N 6, Princeton, N. J., 1941; 2nd ed., 1951.

34. Data searching apparatus (electronic resource): Пат. 5915248 США, МКИ G 06 F 017/30 // Kinoshita Tetsuya, Oyama Takamasa, Kikuchi Chuichi:

35. Matsushita Electric Industrial Co., Ltd. (Япония) //№797085; заявл. 10.02.1997/ опубл. 22.06.1999; приор. 12 .03.1996 №8054588, НКИ 707/001.

36. Method and apparatus or searching a database of records (electronic resource): Пат. 5924090 США, МКИ G 06 F 017/30 // Krellenstein Marc F.: Northern Light Technology LLC (Кэмбридж, США) №846850; заявл. 1,05.1997; опубл. 13.07.1999; НКИ 707/005.

37. Kimbrell, R. Е. "Searching For Text?. Send An N-Gram"Текст. / R. E. Kimbrell //Byte, vol.13, No. 5, May 1, 1998. Pp. 297-312, XP000576194.

38. Колмогоров, A.H. О понятии алгоритма Текст.: А.Н.Колмогоров // УМН. Т. 8, вып. 4(50). С. 175-176.

39. Марков, А.А.Теория алгорифмов Текст. /А. А. Марков, P.M. Нагорный// М. : Наука, 1984. 432с.

40. Успенский, В.А. Теория алгоритмовТекст. / В.А. Успенский, А.А. Семенов М.: Наука, 1987. 218с.

41. Кулик, Б.А. Система поиска слов в произвольном тексте Текст. / Б.А. Кулик//Программирование. 1987. №1. С.49-50.

42. Максимов, В. Алгоритмы поиска, или как искать неизвестно что Текст. / В. Максимов // Монитор. 1995. №6. С.10-15.

43. Устройство для адресации по содержанию блока памятиТекст. : пат. 1485254 СССР, МКИ G 06 F 12/00. / А.С.Кулик, Э.В.Рахов, Н.Н. Востров, Т.П. Кониец // №4313200/24-24, заявл. 05.10.87; опубл. 07.06.89, Бюл.№21. 10 е., ил.

44. Устройство поиска вхождения образца Текст.: пат. № 2223539 РФ,

45. МКИ7 G 06 F 17/00, 17/30. / B.M. Довгаль, Р.И. Писаненко и др. (Россия). 2002110719/09; заявлено 22.04.2002; опубл. 10.02.2004, Бюл. №4.

46. Довгаль, В.М. Способ параллельной реализации подстановки Текст. / Л.А. Лисицин, Е.А. Титенко, С.В. Малюк // Интеллектуальные системы (INTELS'2008): Труды VIII Междунар. симпоз. Н.Новгород, 2008. С. 242244.

47. Лисицин, Л.А. Быстрые символьные вычисления в медицинских системахгподдержки принятия решений Текст. / Л.А. Лисицин, С.Г. Емельянов/ Е.А. Титенко // Вестник новых медицинских технологий. Тула, 2006. №2. С.158-160. £

48. Леонов, Е.И. Устройства для реализации модифицированных марковских алгортмов Текст. : дис. к.т.н.: 05.13.05/ Е.И. Леонов // Курск, гос. техн. ун-т Курск: КГТУ, 1996. 341 с.

49. Белов, В.Г., Шуклина Е.В. Метод представления и обработки символьных данных для ускорения операций сопоставления и подстановки Текст./

50. B.Г.Белов, Е.В. Шуклина // Информационные технологии моделирования и Управления. Межвузовский сб. науч. трудов. Воронеж: ВГТУ, 1998.1. C. 136-141.

51. Шуклина, Е.В. Устройство для реализации марковских алгорифмов над символьными данными, представленными в параллельной позиционной формеТекст./ Е.В. Шуклина: Деп. в ВИНИТИ №3381-В98 от 18.11.98.

52. Якубовский, С.В. Справочник по микросхемам Текст.: С.В. Якубовский и др.// М.: Радио и связь, 1990. 496с.:ил.

53. Устройство поиска вхождения образца Текст.: Пат. RU 2223539 С2, МПК 7 G 06 F 17/300 / В.М. Довгаль, И.С. Захаров, Р.И. Писаненко, Ф.А. Старков; патентообладатель «Курск, гос. тех. ун-т»; № 2223539/С2: заявл. 22.04.2002; опубл. 10.04.2004, Бюл.№4.

54. Довгаль, В.М., Быстрое сопоставление с двумерным образцом по строке и столбцу Текст. / В.М., Довгаль, Р.И. Писаненко : // Известия Курск. Гос. Техн. Ун-та. № 2, 2003. С. 89-96.

55. Потемкин, И.С., Функциональные узлы цифровой автоматики. Текст. / И.С. Потемкин : М.:Энергоатомиздат, 1988.-320с.:ил.

56. Довгаль, В.М., Быстрые символьные вычисления: акселерация работы нормальных алгоритмов Текст. / В.М. Довгаль, В.В. Рассолов // Известия

57. КГТУ. № 1. 2006. С. 108-111

58. Довгаль, В.М. Быстрые символьные вычисления: акселерация работыпродукций. Текст. / В.М. Довгаль// «Изв. вузов Приборостроение».]^ 2, 2005. С. 37-42.

59. Довгаль, В.М. Подход к теоретико-множественному описаниюадаптивной продукционной системы Текст. / В.М. Довгаль, Е.А.Титенко // Известия КГТУ. № 1.2006. С.113-116.

60. Довгаль В.М., Процессор быстрых символьных вычислений Текст./ В.М. Довгаль, В.Е.Сорокин, А.В Шанцев// Сборник материалов 6-ой Международной научно-технической конференции "Медико-экологические информационные технологии-2003", Курск, 2003. С. 157159.

61. Довгаль, В.М., Интерактивный метод распознавания точечных образовТекст./ В.М. Довгаль, М.В. Невзорова, И.С. Захаров // Телекоммуникации, № 8, 2007. С. 8-13