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

ГС П П ГОСУДАРСТВЕННЫЙ КОМИТЕТ РОССИЙСКОЙ ФЕДЕРАЦИИ I b W" ПО ВЫСШЕМУ ОБРАЗОВАНИЮ

8 Ш'И $95 КУРСНЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

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

Корольков Олег Филиппович

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

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

Автореферат диссертации на соискание ученой степени кандидата технических наук

КУРСК 1994

РаСота выполнена в Курском государственном техническом Л

университете,

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

Научные руководители: доктор физико-математических наук, профессор Захаров И.О.; кандидат технических наук, доцент Довгаль В.М.

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

кафедры ВТ КГТУ Типикин А.П.; кандидат технических наук, зам. главного конструктора ПО "Прибор" Лисов С.П.

Ведущее предприятие - в/ч 25714

Защита диссертации состоится ' января 1995 г. в

часов на заседании специализированного совета К 054.60.01 по заацпам диссертаций на соискание ученой степени 1'лндидата технических наук при Курском государственном техническом университете (305039, Курск, ул. 50 лет Октября, 94, ауд. Г-403).

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

Отзыеы на автореферат й двух экземплярах, заверенные печатью, просьба направлять по адресу: 305039, г.Курск, ул.50 лет Октября,94, ученому секретари специализированного совета K064.50.0i.

Автореферат разослан "50 " де«5рЯ 1994 г.

Ученый секретарь специализированного совета,

кандидат технических наук, доцент В.М.Ловгаль

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

Актуальность тени. Расширение областей применения вычислительной техники изменяет не только окружающую действительность, но' также концептуальный и терминологический каркас теории проектирования вычислительных систем. Совсем недавно фундаментальнымиатрибутами ЭВМ являлись программы и данные. Между тем, • в :.современных информационных системах доминируют тексты, поскольку и данные, и программы представляют собой тексты, например, . тексты /программ являются объектами обработки (редактирование, трансляция, оптимизация и т.д.). Текстами также являются знания из прикладных областей, они залают постановку проблем, а также последовательное по иерархии преобразование текстов высокого уровня к текстам, соответствующим уровню исполнительных устройств. Тексты - это слова а фиксированных языках. Языки, точнее тексты в них, нужно переводить один в другой, а сами языки нужно анализировать (синтаксический, семантический анализ). Тексты описывают изображения и их динамику, Все это создает предпосылки для того, чтобы ориентировать средства вычислительной техники на обработку текстов, особенно в системах реального времени. Кроме того, в последнее время • внимание специалистов привлекают высдкие информационные технологии на основе гипертекстов» Доминирование текстов и «к специфика требует новых подходов к решению проблем создания высокопроизводительных средств обработки текстов (символьной информации) потому, что современная массовая вычислительная техника является неэффективной при решении задач символьной обработки. Создан™ алгоритмических, программных и технических средств ОСИ посвящены национальные и региональные программы исследований: проект машин пятого поколения (Япония), стратегическая программа по компьютерам (США), программа ALVEY (Великобритания), программа ESPRIT (Западная Европа). Поэтому проблема обработки символьной информации (ОСИ) является актуальной.

Целью работ является разработка и исследование последовательных устройств ОСИ, реализующих модифицированные системы продукций А.Д.Маркова (нормальные алгоритмы).

Оспомшни задачами диссертационной работы являются;

1) исследование математических моделей процессов ОСИ;

2) разработка и моделирование последовательного устройства ОСИ, реализующего нормальные алгоритмы с алфавитными переменными:

3") разработка и моделирование последовательного устройства ОСИ с размеченными продукциями;

4) разработка и моделирование устройства ОСИ с расширенными функциональными возможностями;

5) анализ' характеристик разработанных устройств.

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

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

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

- проведена модификация марковской алгоритмической системы для достижения максимально" "'допустимой-"скорости обработки символьной информации;

- обоснована строгая' -.'■эквивалентность исходных и модифицированных - систем продукций;;

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

Л^иогшссион ценностью диссертационной работы является разработка последовательных', устройств СОТ, реализующих системы продукций. Предлагаемые устройства могут использоваться как аппаратные средства баз знаний и экспертных систем, обработки языков, структурного распознавания'образов и управления, как^

серверы и рабочие станции в сетях ¡ЭВМ, сопроцессоры в составе распределенных вычислительны« систем, а тагсте в качестве процессорных элементов многопроцессорных систем ОСИ, электронных записных книжек и т.д. ; .

В коде выполнения диссертационной работы;

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

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

На ¡защиту выносятся следующие оогсшше положения;

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

- формальный метод разметки систем продукций, позволяющий существенно сократить временные затраты по сравнению с каноническими марковскими, система«! продукций;

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

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

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

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

Апробпмия Предварительные результаты работы

докладывались на Международной научной конференции "Оптико-электронные приборы и устройства в системах распознавания образен, обработки изображений и символьной информации" (Курск, 1993), Всесоюзной научно-практической конференции "Вопроси экономики и организации информационных технологий" (Гомель. 1932), Юбилейной научной . конференции Курского политехнического института (Курск, 199-1).

Виедрзш/е Результаты, диссертационной работы нашли

применение при выполнении госбюджетных фундаментальных НИР Курского государственного технического университета (г/б - ?, г/б - 15), а также хоздоговорных НИР (х/д " 378), использованы в

учебном процессе ("Архитектура вычислительных систем" - курс лекций. " Высокопроизводительные систем обработки информации" - -практический занятия) и внедрены в Курском ТОО "Автор", где были применены в качестве'технических средств акселерации поиска в полнотекстных базах данных, что подтверждается актом о внедрении. ...

Работа выполнена 'по. плану Госкомвуза Р1> (единому за!саз-наряду) на 1092-95 гг. от 16.03.92 г. N 10-36 - 41ин / 10-20-03,. (тема "Разработка и исследование характеристик процессорных элементов систем обработки символьной информации"), а также по распоряжению Госкомвуза № от 19.02.93 г. N10 "Технические системы обработки символьной информации и изображений" (Международный проект).

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

Структура и объем работы. Диссертационная работа состоит из введения, четырех глав и заключения, изложенных на ¿¿9 страницах; содержит ЧЦ рисунков, наименований библиографии и 49 Страниц приложений»-всего страниц -2-Иь,

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

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

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

Задачи ОСИ имеют следующие специфические особенности:

- обрабатываются большие объемы данных со сложной логической структурой; .

- программы решения задач этого класса также имеют большой объем и сложную логику;

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

; - ? -

непредсказуем; '

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

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

Анализ существующих технических средств ОСИ проведен по следуящ^м пунктам:

- архитектурные решения;

- аппаратные решения на микроуровне;

- субсиетемный уровень;- системный уровень. -

Ан&яиа показал» что существуют три основных взаимодополняющих принципа разработки технических средств ОСИ:

- аЕтоматный;

- матричный;

- ассоциативный.

В данной глазе проводится также анализ характеристик известных технических средств ОСИ. Внимание прежде всего акцентируется, ча. относительно низкой производительности (300 КЛипс з среднем). высокой стоююстк (десятки тысяч долл.) и технической сложности (сотни тысяч транзисторов). Отмечается, что потребности практики определяются производительностью в десятки МЛипс для автономных систем и в десятки ГЛипс - для распределенных систем массового назначения.

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

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

- У -

модификации Формул подстановок для минимизации временных затрат при выполнении модифицированных алгоритмов.

В результате анализа форм представления марковских г1лгоритмов установлено:

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

- существуют и определены условия для использования разных форм представления алфавитных переменных ' и введения дополнительных управляющих призьаков;

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

Основу нормального аагоритмэ составляют продукционные формулы:

• Т --> 5 , (1)

где Т - образец;

5 - подстановка;

5,-Г - любые слова в фиксированном алфавите -С А >;

—> - разделитель,' не принадлежащий алфавиту { А К

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

1) работа алгоритма начинается с первой 5 списке продукции;

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

3) после всякого однократного срабатывания продукции из заданной системы, переход осуществляется на первую продукцию;

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

Подавляющее большинство нормальных алгоритмов содержит

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

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

На основе анализа систем продукций предлагается формальный метод расстановки меток. Вводятся следующие определения.

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

1 о

Б=3 Э ., (2)

где Б-любое слово, Болевое дополнение; о

Б -собственное окончание слова 5.

Определение 2. Правым дополнением любого непустого слова условимся называть такое непустое слово, которое' з своей конкатенации с собственным началом удовлетворяет графическому равенству:

» р

3=3 Б . (3)

Определение 3. Два непустых слова 3 и Т пересекаются тогда и только тогда, когда верна конструктивная дизъюнкция:

(з"= Т0)У(5°= т")У(3< Т)У(Т< 3). (4)

н н

где 5 , Т -собственные начала, а о о

Б , Т-собственные окончания, слов Б и Т соответственно; V -символ, обозначающий конструктивную дизъюнкцию; < -символ, обозначающий вхождение одного слова в другое.

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

Тсорот. Если непустая подстановка Ьтой формулы не пересекается ни с одним непустым образцом всех предшествующих ей „ формул в схеме алгоритма, то не существует 'такого обрабатываемого слова, на : котором мохег сработать любая предшествующая 3-тая (;)<!) формула после срабатывания 1-той формула Си £41,. ..М), где М-число формул в схеме алгоритма).

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

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

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

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

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

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

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

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

Первое устройство с алфавитными переменными (УАП) реализует нормальные алгоритмы канонической Формы, в том числе и такие, которые содержат продукции ' с &1фаЕитными переменными. Структурная схема данного устройства приведена на рис. 1. Устройство содержит блоки анализа вхождений-1, регистров приема формул-2, регистра вхождения и слова-3, памяти формул-4, первый буфер-5, второй буфер-б, память слова-?, устройство упрааления-8. Связи между блоками и алгоритм управления, приведенные в третьей главе, даот необходимые основания • для экспертизы работы устройства и служат для построения программ моделирования работы устройства.

Второе устройство с размеченными продукциями (УРП) предназначено для реализации размеченных, модифицированных алгоритмов. Структурная схема данного устройства приведена на рис.2. В состав устройства входят блок обнаружения вхождения-1, первый буфер-8, память вхождений-3, блоки анализа переходов-4, регистров и слова-5, память подстановок-б, второй буфер-7, память слое-8 и устройство у.правления-9. Приведенные в структурной схеме связи между блоками . и алгоритмы управления позволяют моделировать его работу. с использованием соответствующей программы, приведенной в Приложении 1 диссертации.

Третье устройство с расширенными ■ функциональными возможностями (УРФВ) позволяет сократить аппаратные затраты при технической реализации. Структурная схема устройства (рис.3) содержит в своем составе второе устройство управления-1, блок триггероз согласования-2, анализа совпадений-3, память продукционных формул-4, адресов формул и переходсв-5, памяти слов-б/ одинаковых алфавитных переменных-8, а также буфер-? ' и первое управляющее устройство-9. Как и для первых двух вариантов устройств разработаны программные продукты моделирования работы указанного устройства.

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

времени микропроцессора 80286. При этом для микропроцессора разработаны три варианта ассемблеровских программ MARK_, MARK-С и MARK-L. '

Скорость работы УР® при варьируемой длине обрабатываемого слова и фиксированной длине образца и подстановки более чем в 50 раз превышает скорость обработки на микропроцессоре при использовании программ MARK_, в 20 pas - при использовании программы MARK-С и в 50 раз - при использовании программы • MARK-L.

'При фиксированной длине обрабатываемого слова и подстановки и варьируемой длине образца скоростные преимущества УРФЗ составляют 40-кратное превышение скорости работы микропроцессора при MARK_, 30-краткое - при применении программы MARK-C и 70-кратное - при использовании программы MARK-L.

Варьирование длины подстановки при ' фиксировании длин образца и обрабатываемого слова, приводит к следующим результатам:

- при использовании программы NiARK_ для микропроцессора выигрыш устройства УРФВ в среднем составляет 40 раз;

- при применении программы MARK_ - в 20 раз;

- при использовании программы MARK-L - в 8 раз.

Следует подчеркнуть, что устройство УАГ1 в четыре раза (в среднем) превьшет. скорость работы устройства УРФВ при реализации алгоритмов, содержащих единственную продукционную формулу. •

Вместе с тем, устройство УРП имеет двухкратное скоростное преимущество по отношению к устройству УРФВ при реализации тех же алгоритмов.

Результаты моделирования работы продукционных формул, содержали алфавитные переменные, приведены на рис.4 и в х-абл.1 для устройства УРФВ, которое имеет 40-кратное скоростное преимуа;ество по отношению к микропроцессору.

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

СТРУКТУРНАЯ СХЕМА УСТРОЙСТВА УАЛ.

1-блок анализа вхождений, 2-6лок регистров приема формул, 3-блок регистров вхождения и слова, 4-память формул, 5-второй буфер, б-первый буфер, 7-память слова, 8-устройство управления.

Рис.1

СТРУКТУРНАЯ СХЕМА УСТРОЙСТВА УРП.

1-блок обнаружения вхождения, 2-переый буфер, 3-память вхождений, 4-0лок анализа переходов, 5-блок регистров вхождения и слова, 6 память подстановок. V второй буфер. 8 память слова, й-устройство управления.

Рис.2

- 14 -

СТРУКТУРНАЯ СХЕМА УСТРОЙСТВА УРФВ.

1- второе управляющее устройотЕС,2-Олок: триггеров согласования, 3-блок анализа совпадении, 4-блок памяти продукционных формул, 5-блок адресов формул и переходов, 6-блок памяти, слов 7-буфер, 8 блок одинаковых алфавитных переменных, 9-первое устравлящее устройство.

»

Рис. 3

СРАВНИТЕЛЬНАЯ ОЦЕНКА БЫСТРОДЕЙСТВИЯ отношение скоростей (ед.)

число алфавитных переменных (ед.)

Рис.4

Таблица 1.

Число алфавитных переменных 1 2 3 4 б 1

Т.МИК/Т.УСТЗ 35.6 38.6 41.2 43.5 45.5

длина образца 2 3 4 5 б

д. подстановки 2 3 4 5 6

СРАВНИТЕЛЬНАЯ ОЦЕНКА БЫСТРОДЕЙСТВИЯ отношение скоростей (ед.)

70 -

60 -

60

40 -

30 -

20 I 1

Таблица 2

Число частичных вхождений 1 2 3 4 5 6 Примечание.

Т.МИК/Т.УСТЗ 51.3 53.1 54.3 56.4 57.9 59.4

Т.МИК/Т.УСТЗ 35.5 37.2 38.8. 40.4 41.9 43.2 МЛКК-С

Т.МИК/Т.УСТЗ 25.5 35.5 44.9 53.9 62.4 70.4 МАРК-Ь

. 5 число у вхождент

6

астичных (ед.)

Рис.5

имеет, в среднем, 50-кратный выигрыш в скорости (см. рис,5 и табл.2).

При моделировании .работы устройства УРЮ при решении задач правой и левой конкатенации данное устройство в 4 и 17 раз, соответственно, превышает скоростные возможности

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

. В тоже время, решение задачи левой конкатенации на первом устройстве УАП дает 60-кратный выигрыш. При решении задачи "Ханойская Оал'ня" устройство УВГВ имеет трехкратное превышение скорости работы микропроцессора. : '

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

Проведена оценка аппаратных затрат (число транзисторов). Показано, что для первых двух устройств ?» затраты, зависят от длины обрабатываемого . сюза, а такие от максимально возмохной длины (Ьмах) слова-образца, которое мохет быть загружено в "гену" комгсарацни. .Результат, подсчета представлен в таблице 3. Аппаратные затраты преЕЫиают ; затраты микропроцессора 80266, однако, они значительно меньше, чем у иБР-процессоров или. ПРОЛОР-прсцессоров (около пятисот тысяч транзисторов).

Таблица 3.

1 ив 1=16 1-32

Устройство 1 21148 40576 60492

Устройство 2 21486 38206 71838

Аппаратные затраты третьего устройства составляют около 10 тысяч транзисторов я не зависят как от длины ПФ, так и от длины обрабатываемого слова.

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

Первый класс устройств (УАП, УРП) рекомендуется использовать ь ; --.чостве технических ' средств для решения задач информационно?поискового характера, структурного распознавания

обрезов, синтаксического анализа формальных языков и др;

Второй класс устройств, создаваемых на основе архитектуры УРЙ рекомендуется использовать в качестве субпроцессоров многопроцессорных систем, серверов сетей -ЭВМ, а также в.качестве процессоров-акселеоаторов . в вычислительных системах, Преимущества устройств данного класса наследуются от устройств первого класса, и, кроме того, в этом классе устройств используется принцип опережавшего определения адресов передачи управления, а также пояьляется • ■ возможность использовать продукционные формулы переменной длины.

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

И «¡млолепиях представлены тексты программ алгоритмического моделирования разработанных последовательных устройств, схемные решения некоторых .блоков устройства ' У РИЗ, а также результаты моделирования.

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

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

При достижении поставленной цели в ■ диссертационной работе • получены следующие научные результаты:

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

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

алгоритмов позволяют использовать их сочетания (композиция, разветвление и т.д.), .

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

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

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

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

Основные результаты диссертации наши отражение в работах:

1. Корольков О.Ф. и др. К вопросу об особенностях обработки символьной информации// Материалы Всесоюзной научно-практической конференции "Вопросы экономики И организации информационных технологий". Часть 2. - Гомель, 1991. - С.iO - 12.

2. Корольков О.Ф. Последовательные устройства для обработки символьной информации (ОСИ) // Материалы Международной научной конференции "Оптико-электронные приборы и устройства в системах распознавания образов, обработки изображений и символьной информации". - Курск, 5-8 октября 1993 г. - С. 182-183.

3. Корольков О.Ф. и др. Об одном способе сокращения затрат времени при работе нормального алгорифма: Деп. рукопись,-И. : ВИНИТИ, N4077-890 от 19.07 1990 Н11, б/о 650.

4. Корольков О.Ф, и др. Об одном способо минимизации числа (патов работы Нормального алгорифма! ДеН. рукопись.-М.: ВИНИТИ, N3259-B90 от 03.06 1990 НЮ, б/о 115.

5. Корольков О.Ф. Последовательное устройство для обработки символьной информации (ОСИ) // Юбилейная конференция ученых Курского политехнического института: Тез. докл./ Курский политехнический институт. Курск, 1994. - С.67-68!

6. А,с. 1635192 СССР, МКИ G 06 F 15/20/ Устройство для реализации подстановок слов. / Корольков О.Ф. и др. (СССР)'. -N4684324; заявлено 3.05.89; Опубл. 15.03.91, Бкмь N.10.

7. A.c. , 1683025 СССР, МКИ G Об F 15/044 Устройство .для реализации подстановок. / Король'коч О.Ф. . И др. (СССР). -N4735882; заявлено 11.09.89; Опубл. 07.10.91, Бюл. N 37.

8. A.c. 1688253 СССР, МКИ G Об F 15/20/ Устройство для реализации подстановок слов. / Корольков 0. Ф. и др. (СССР). -N4673921; заявлено 04.04.89; Опубл. 30.10.91, Бюл. N 40.

9. Д.с. 1741147 СССР, МКИ G Об F 15/20/ Устройство для реализации подстановок. / Корольков О.Ф. и др. (СССР). -N4799324; заявлено 05.03.90; Опубл. 15.06.92, Бюл. N 22.

10. A.c. 1805478 СССР, МКИ G Об F 15/20/ Устройство для реализации подстановок. / Корольков О.Ф. и др. (СССР). -