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

МИНИСТЕРСТВО ОБЩЕГО И ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ

КУРСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

Р Г Б ОД

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

1 5 ДЕК Шз

ЛЕОНОВ ЕВГЕНИЙ ИВАНОВИЧ

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

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

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

КУРСК 1996

РАБОТА ВЫПОЛНЕНА в Курском государственном техническом

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

НАУЧНЫЙ РУКОВОДИТЕЛЬ - доктор физ.-мат. наук,

профессор ЗАХАРОВ И.С.; кандидат технических наук, доцент ДОВГАЛЬ В.М.

ОФИЦИАЛЬНЫЕ ОППОНЕНТЫ: доктор технических наук,

профессор ТИПИКИН А.П. кандидат технических наук> старший научный сотрудник ПОТАПОВ В.П.

ВЕДУЩАЯ ОРГАНИЗАЦИЯ Опытно-конструкторское бюро

"Авиаавтоматика"

ЗАЩИТА СОСТОИТСЯ "26" декабря 1996 года в 16— на заседании диссертационного совета Д064.50.02 Курского государственного технического университета по адресу: 305040, г. Курск, ул. 50 лет Октября, д. 94, конференц-зал.

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

АВТОРЕФЕРАТ РАЗОСЛАН "¿5"" ноября 1996 г.

Ученый секретарь д.т.н., проф.

Кореневский Н.А.

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

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

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

Работа выполнена по плану Госкомвуза РФ на 1992-1995 г.г. от '16.03.92 г. » 10-36-41, ИН/10-20-03. (тема "разработка и исследование характеристик процессорных элементов систем обработки символьной информации"), а также по распоряжению Госкомвуза РФ от 19.02.93 г. К' 10 "Технические системы обработки символьной информации и изображений" (международный проект).

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

Для достижения поставленной цели были решены следующие задачи.

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

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

3. Разработка эффективных алгоритмов реализации процессов ОСИ на основе модифицированных систем марковских продукций.

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

5. Разработка структур высокопроизводительных устройств ОСИ.

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

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

матов, теория проектирования элементов и устройств вычислительной техники и систем управления.

Научная новизна работы состоит в следующем.

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

•счетные и строковые конструктивы.

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

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

Практическая ценность диссертационной работы:

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

- разработаны программные средства моделирования процессов ОСИ;

б

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

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

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

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

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

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

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

Реализация и внедрение результатов исследований. Результаты диссертационной работы нашли применение при выполнении госбюджетных и хоздоговорных НИР Курского государственного технического университета (г/б-7, г/б-15, х/д-378), а также практически реализованы и внедрены в информационном центре УВД Курской области и учебном про-

цессе Курского государственного технического университета .

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

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

Структура и объем работы. Диссертационная работа состоит из введения, пяти глав и заключения, содержащих 148 страниц основного текста, 55 рисунков и 27 таблиц, а также списка использованных источников из 84 наименований на 9 страницах и 14 приложений на 150 станицах;

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

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

В_первой главе проведен анализ особенностей задач

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

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

Процессы ОСИ применяются при решении задач обработки текстов к естественных языков, в СУБД и экспертных системах, при решении интеллектуальных задач и др.

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

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

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

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

зволяющие повысить эффективность их применения для решения практических задач ОСИ.

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

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

Оптимизирующая разметка осуществляется на основе логического индикатора, в качестве которого выступает следующая конструктивная дизъюнкция:

(Р1сн-Таск) V {Р^шТ^") V <Р1<=Тэ) V (Т^Р^, (2)

где Р^", Т3СН - собственные начала подстановки 1-й и образца ;)-й формул Ц<Л; Р1СК, Т]е|С- собственные концы подстановки и образца ;}-той продукций; Т3- слово-образец -}-й продукции; Р1- слово-подстановка 1-й продукции; ' знак графического равенства; 'с'- знак вхождения одного слова в другое; 'V'- знак конструктивной дизъюнкции.

Ситуацию, когда для пары продукций с номерами 1, 5 дизъюнкция (2) оказывается верной, условимся называть индукцией вчда j=>i. Выходные метки переходов расставляется для каждой незаключительной ^й продукции алгорифма в соответствии со следующим правилом: после срабатывания ■ той продукции переход выполняется на первую индуцируемую ею 1.-ю продукцию, а при отсутствии индукции переход выполняется на Зтю продукцию.

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

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

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

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

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

с

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

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

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

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

Гю=д1&д2&.. .&дк, (3)

где Еи- функция обнаружения вхождения для гп-й продукции исходного алгорифма; к- количество символов в формате входного слова; д1 Ц«>1+к) - идентификатор булевой переменной, принимающей в зависимости от конкретного значения символа в*, стоящего в 1-й позиции слова-вхождения данной продукции следующие значения: рх, если в! ='1'; д! = ■ если в* ='0'; , (4)

1, если г! - алфавитная переменная, где р1~ двоичная переменная в 1-той позиции формата входного слова.

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

и = (...((гп • р? • ^ • г""1 • йГ1 V г""1 • р?-1 • и?-1) • г""2 • йГг V

V Г"-2 • р?'г • и"-2) • Г1 • й,1 V Г1 • р} • и}, (5)

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

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

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

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

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

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

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

R = T/S, 16)

где Т - время решения задачи, S - ее сложность.

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

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

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

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

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

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

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

Аппаратная сложность микропроцессора 80286 составляет 130 ООО транзисторов, из них более 40% приходится на реализацию работы в защищенном мультизадачном режиме, но, таг как исследуемые нами устройства работают только в реальном однозадачном режиме, то для корректности сравнения сложность микропроцессора 80286 принята равной 76 000 транзисторам.

Устройство БР1 аппаратно поддерживает выполнение размеченных систем канонических марковских продукций, для его реализации требуется 5 352 транзистора (почти в 14 раз меньше, чем для микропроцессора 80286);

Устройство БР2 ориентировано на реализацию модифицированных систем марковских продукций с алфавитными и счетными конструктивами, оно содержит оригинальный меха-

низм "безмусорного" управления списковой памятью, конвейер команд и арифметико-логический блок и его сложность на 9 тыс. транзисторов выше сложности ЗР1 и составляет 20% от сложности микропроцессора 80286;

Система команд устройства БРЗ расширена средствами поддержки строковых конструктивов, "окон просмотра" обрабатываемых слов, а также формул конкатенации и условных переходов, поэтому он имеет на 2 тыс. транзисторов больше, чем устройство БР2 и его аппаратная сложность составляет 22% от сложности микропроцессора 80286.

На рис 2. представлена структурная схема устройства БРЗ Оно состоит из четырех блоков: блока адресации памяти программы (БАПП), блока управления памятью слова (БУПС), блока анализа (ЕА) и блока управления (БУ).

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

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

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

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

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

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

2. Результаты исследования эффективности разработанных на основе модифицированных нормальных алгорифмов трех вариантов устройств ОСИ (SP1, SP2, SP3), полученные путем компьютерного моделирования их работы для решения тестовых задач символьной обработки, показывают, что при выполнении таких базовых операций символьного уровня, какими являются: сопоставление, замена, вставка, конкатенация и сортировка, названными устройствами достигается 20-ти кратное скоростное преимущество (от 2-х - при сортировке до 40 - при сопоставлении) по сравнению с прототипом, а при реализации сложных алгоритмов ОСИ, связанных с циклическим перебором, отступами и рекурсией, все моделируемые

с

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

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

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

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

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

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

1. В.М. Довгаль, Е.И. Леонов. Об одном способе сокращения затрат времени при работе нормального алгорифма /Деп. рукопись.- М.: ВИНИТИ, №4077-В90 от 19.07.90, №11, б/о 650.

2. В.М. Довгаль, О.Ф. Корольков, Е.И. Леонов. Об одном способе минимизации числа шагов работы нормального алгорифма /Деп. рукопись.- М.: ВИНИТИ, №3259-В90 от 8.06.90, .N'10, б/о 115.

3. Е. И. Леонов. Архитектура специализированного символьного сопроцессора //Тезисы докладов международной конференции "Оптико-электронные приборы и устройства в системах распознавания образоз, обработки изображений и символьной информации".- Курск: КПИ, 1993.- С. 176-177.

4. В.М. Довгаль, Е.И. Леонов, О.Ф. Корольков. Метод акселерации работы последовательных устройств, реализующих марковские продукции /Тезисы докладов международной конференции "Оптико-электронные приборы и устройства в

системах распознавания образов, обработки изображений и символьной информации".- Курск: КПИ, 1993.- С. 184-185.

5. Е.И. Леонов Метол структурного синтеза комбинационных схем по заданной системе продукций /Тезисы докладов Юбилейной конференции ученых Курского политехнического института. Курск: КПИ, 1994.- С. 71-74.

6. A.c. 1667097 СССР, МКИ5 G06 F15/20. Устройство для реализации подстановок с двухкомпонентными вхождениями /Леонов Е.И. и др. (СССР).- №4735877/24; заявл. 11.09.89; опубл. 30.07.91, Бюл. №28.

7. A.c. 1683025 СССР, МКИ5 G06 F15/04, 9/44. Устройство-" для реализации подстановок /Леонов Е.И. и др. (СССР).-' №4735882/24; заявл. 11.9.89; опубл. 7.10.91, Бюл. №37.

8. A.c. 1727120 СССР, МКИ5 G06 F7/49. Устройство для параллельного сложения чисел, представленных в двоичной знакоразрядной системе счисления ./Леонов Е.И. и др. (СССР).- №4772255/24; заявл. 22.12.89; опубл. 15.04.92, Бюл. №14.

9. A.c. 1741147 СССР, МКИ5 G06" F15/20. Устройство для реализации подстановок /Леонов Е.И. и др. (СССР).- № 4799324/24; заявл. 5.03.90; опубл. 15.06.92, Бюл. №22.

10. A.c. 1805478 СССР, МКИ5 G06 F15/31, 15/16. Устройство для реализации подстановок /Леонов Е.И. и др. (СССР). -№4873212/24; заявл. 10.10.90; опубл.30.03.93, Бюл. №12.

11. Пат. 2039375 РФ, МКИ6 G06 F17/00, 17/20. Устройство для реализации продукций /Леонов Е.И. и др. (Россия).-№504871/24; заявл. 22.06.92; опубл. 9.07.95, Бюл. №19.

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

Прав, конкатенация (такт/симв.) г

120 -100- .

Замена (такт/симв)^ 80: -Лев. конкатенация (такт/сима.)

60-

Поисх (тахт/снив.)

-■ Сортировка (такт/симв.)

"Ханойская башня" (тагг/симв.)" ' Задача о ферзях (такт/симв.)

□60236 DSP2 BSP3

РИС. 1 .

Устройство для реализации модифицированных марковских

алгоритмов

ШАПП

Л

шдпп

ШАПС

ПКА

КОП

тзв

РЕЖ

ТНС

ПКС

\1/ V W V V V \1/ '

T1ID

МП

О

шдпс

шо

шз

БАПП шл БА БУПС

ком п

пп

БУ

Рис. 2.

Соискатель ^¿р^5"1 Е.И. Леонов

Подписано к печати 1.5Н. ■ Формат 60 х 84 1/16

Печатных листов __. . Тираж 100 экз. Заказ /¿¿>

Курский государственный технический университет. 305040, г. Курск, ул. 50 лет Октября, 94.