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

1 0 MAP 1997

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

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

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

ТИТЕНКО ЕВГЕНИЙ АНАТОЛЬЕВИЧ

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

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

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

КУРСК 1997

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

НАУЧНЫЕ РУКОВОДИТЕЛИ - доктор технических наук.

профессор ТИТОВ B.C.

- кандидат технических наук, доцент ДОВГАЛЬ В.М.

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

профессор ДРЕЙЗИН В.Э.

- кандидат технических наук. С.Н.С. ПУСТОВОИ Н.П.

ВЕДУЩАЯ ОРГАНИЗАЦИЯ - В/Ч 25714

ЗАЩИТА СОСТОИТСЯ к2й" И^|»та 1997 года В ~°Ч. на заседании диссертационного совета Д064.50.02 при Курском .государственном техническом университете по адресу : 305040. г.Курск, ул. 50-лет Октября, д. 94. конференц-зал.

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

Автореферат разослан -й- feipat1/1997 г.

\

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

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

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

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

Задачи научного исследования :

1) разработка стратегии безвозвратных выводов:

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

3) создание абстрактной машины-генератора (исчислительной

машины) и технических решений устройств поддержки исчислитель-ных систем продукций на ее основе;

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

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

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

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

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

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

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

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

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

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

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

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

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

На защиту выносятся следующие положения:

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

2) продукционное исчисление на основе безвозвратной стратегии и обоснование тождественности предлагаемого исчисления марковскому алгорифму с канонической схемой управления:

3) абстрактная машина-генератор ветвящихся конструктивных процессов:

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

5) результаты моделирования работы мультипроцессора.

Реализация и внедрение результатов исследования. Результаты диссертационной работы нашли применение при выполнении госбюджетных НИР КурГТУ. внедрены на заводе АО "Счетмаш". а также в учебный процесс КурГТУ.

Апробация работы. Результаты диссертационной работы докладывались на всесоюзной конференции "оптико-электронные приборы и устройства в системах распознавания образов, обработки изображений и символьной информации" (Курск. 1993 г.). конференциях: "Тезисы докладов юбилейной конференции ученых Курского политехнического института"(Курск. 1994.г.) и "Труды юбилейной научной конференции" Часть 2. (КГТУ. Курск, 1995. ). а также на 2-ой международной конференции "Распознавание-95и. (Курск. 1995 г.).

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

Структура и объем работы. Диссертационная работа состоит из введения, пяти глав, заключения, списка литературы и приложений, изложена 129 на страницах (основного текста), содержит 39 рисунков. 17 таблиц. 80 наименований библиографии. Щ0 страниц приложений, всего страниц -26$.

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

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

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

Во второй главе проведен сравнительный анализ объектов теории алгоритмов - алгоритмов и исчислений.

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

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

возвратами.

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

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

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

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

X - 0 - Р. (1)

где 0 и Р - слова в алфавите символов I. X - пустое слово. «-,-•- мета-символы, не принадлежащие I. Работа продукции, называемой исчислительной. заключается в поиске вхождения слова О в обрабатываемое слово Б : если поиск результативный, то выполняется подстановка на место 0 слова Р; если поиск не результативен, выполняется аннуляция копии Б. т.е. Б=Х.

В работе исследовались дескрипторные и метрические свойс-

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

Теорема о тождественности.

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

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

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

Например, пусть на р-ом шаге вывода слово пос-

тупает на вход каждой продукции, что отражено на рис.1.

Шаг продукционного вывода

М,!?,

-•1,0,1?, X - 0, - р. X -1

X - 0, - Р1 X -

-Ь, 0,1*1 X - Р;

X - о„ - р„ X -

—Х#Х#. .Ь,Р,М. .Х-ЦР,!?,

Рис. 1

Работа исчисления заключается в параллельном срабатывании п продукций и формировании 5р.1-Ь1Р,К1. но фактически "актив-

ной" является только 1-ая продукция - она определяет ход процесса вывода. Следующий шаг процесса заключается в работе исчисления с Зр,,-Ь|Р1Я1. В случае вхождения в БрМ процесс вывода продолжится, но "активной" будет уже З-ая продукция. Таким образом, исчисление моделирует марковский вычислительный процесс в виде последовательности "активных" продукций I» - { ... и.к. ... }. тождественной 1А, Структура обработки (рис.1) соответствует теореме об объединении марковских алгоритмов с учетом модификации формы продукции (1).

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

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

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

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

1-кй банк содержит п блоков памяти слов-копий (БПС1). 2-ой банк включает в свой состав п блоков памяти обработанных

слов-копий (БПС2). 3-ий банк состоит из п блоков памятей контрольных точек (БПКТ).

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

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

Структурная схема ППУ приведена на рис.3 и состоит из следующих блоков : блок управления поиском .многократных вхождений БУПУ.В (6). блок поиска многократных вхождений БПМВ (7). арбитр АРБ (8). блок преобразования кода БПК (9). блок реализации подстановки БРП-1 (10). блок реализации подстановки БРП-2 (11). блок реализации подстановки БРП-3 (12). блоки управления реализацией подстановки и модификацией фрагмента БУРП/БУМОДИФ (13), счетчик контрольных точек СчКТ (14). блок памяти образца БПО (15). блок памяти подстановки БПП (16), триггер индикации подстановки ТрИП (17).

Основу блока обработки результатов БОР составляет п+1 входовой мультиплексор Нх2 и счетчик СчВКТ номера памяти БПС2. с помощью которых осуществляется посимвольная перезапись слов-дублей в п БПС1. чем и достигается возможность копирования данных на вход каждого ППУ. Кроме того, БОР содержит матрицы-столбцы {^-триггеров для выявления слов-дублей, обработка которых завершена. Выявление осуществляется с помощью п-раз-рядного мультиплексора Мх1, выполняющего побитное сканирование среза контрольных точек из п БПКТ.

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

Моделирование на мультипроцессоре и на абстрактной машине логического вывода с характеристиками РБГ-млшины пяти исчисли-

тельных систем продукций для решения задачи "обезьяна и банан" показало (табл.1), что с ростом количества путей (2-4-6-12-18) в каждом дереве вывода отношение временных затрат на осуществление логических выводов (ЛВ) между стратегией backtracking и безвозвратной стратегией составляет величины

1.1-1.8-2.6-3.3-4.8 соответственно: для наиболее разветвленного восьмиуровневого дерева вывода с пятью ИЛИ-вершинами временной выигрыш составляет более 4.8. Для корректности сравнения безвозвратной стратегии с стратегией backtracking было выполнено моделирование работы мультипроцессора и определены общее количество тактов его работы Т0вц. и количество тактов на этап "склеивания" Тс**. Анализ относительной величины Те*л./Тоби! показывает, что с ростом количества ИЛИ-вершин доля- вычислений на этап "склеивания" увеличивается и для наиболее разветвленного восьмиуровневого дерева составляет 55.035 Вместе с тем увеличение времени "склеивания" носит линейный характер, тогда как количество логических выводов, а следовательно и тактов работы машины логического вывода класса PSI. с линейным ростом дерева вывода увеличивается экспотенциально. поэтому для рассматриваемого восьмиуровневого дерева PSI-машина затрачивает 85 ЛВ. а мультипроцессор - 17.7 ЛВ.

Моделирование работы мультипроцессоре при реализации алгебраической системы продукций для решения задачи "оптимальный раскрой" продемонстрировало, что безвозвратная стратегия имеет ограниченную область эффективного применения, т.к. для целочисленных задач возникает нетипичная для ОСИ ситуация возникновения массовых копий-повторов слов. Моделирование работы ' мультипроцессора показало, что с линейным увеличением объема входных данных времена срабатывания продукций Трав и неповторяющегося "склеивания" ТЬаск увеличиваются нелинейно, но по абсолютному значению общее время Tie3i-Tpti+Tc„ меньше времени работы известного последовательного устройства с возвратами Тлен. Анализ относительной величины Твв311/ТЬ|Ск показывает, что с увеличением размерности задачи динамика увеличения времени работы мультипроцессора по безвозвратной стратегии Т4взв по, сравнению с стратегией backtracking ТЬас), изменяется медленнее: для М1-0 ТввЭ1/Тй4Ск-'6.3. а для М1-7 Тл,зв/ТЬлек-2.7 (при М2-5). Как показало моделирование при Ml) 21 - критическая точка - затраты времени мультипроцессора с безвозвратной

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

Моделирование работы продукционного процессорного устройства (ППУ) мультипроцессора в режиме конвейерного поиска и подстановки позволило установить, что скорость выполнения операций поиска и подстановки на конвейере составляет 1 симв/такт. в то время как скорость выполнения аналогичного и известного последовательного устройства реализации продукций составляет 0.5 симв/такт на операции поиска и не превышает 0.33 симв/такт на операции подстановки (при одинаковой тактовой частоте работы устройств).

Кроме того, моделирование показало, что длительность конвейерного поиска прямо пропорциональна длине регистра-конвейера . на котором ведется поиск, и обратно пропорционально времени поиска первого вхождения в слове. Длительность подстановки не зависит от длины регистра-конвейера, а определяется соотношением длин образцов и подстановок. Зависимость длительности модификации фрагмента является наиболее сложной и определяется размером фрагмента, позицией вхождения образца, соотношением длин слова и регистра-конвейера, способом выравнивания слова, некратного длине регистра-конвейера, по его левой или правой границе. Моделирование выявило, что потенциально "узкими" местами мультипроцессора являются арбитр АРБ для поиска первого вхождения в конвейере, блок преобразования кода БПК и сумматор. С целью повышения быстродействия работы были предложены технические решения названных блоков и оценена их эффективность. Например, длительность, работы используемого пятиразрядного сумматора, в среднем, уменьшается в.два раза за' счет динамического учета переносов и прекращения процесса суммирования при обнаружении нулевых переносов.

Сравнение аппаратных затрат'моделируемого. ППУ мультипро-

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

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

В приложениях приводятся вспомогательные материалы и листинги программ моделирования.

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

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

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

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

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

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

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

5. Осуществлено машинное моделирование работы продукционного процессорного устройства (ППУ). являющегося основным функциональным блоком и определяющим основные скоростные и аппаратные параметры мультипроцессора. Показано, что скорость выполнения поиска и подстановки ППУ составляют 1симв/такт, тогда как аналогичное устройство для реализации продукций (последовательный марковский процессор) характеризуется вдвое меньшей скоростью выполнения поиска и втрое меньшей скоростью выполнения подстановки, но аппаратные затраты аналога в 3.75 раза меньше, чем у ППУ. Кроме того, моделирование работы мультипроцессора выявило пятикратное (4.8 раза) скоростное преимущество мультипроцессора с семнадцатью ППУ по сравнению с PSI-машиной при решении типовой задачи ИИ.

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

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

1. Титенко Е.А. Параллельный однородный сумматор. // Тезисы докладов юбилейной конференции ученых Курского политехнического института. Курск. 1994 г. С. 100.

2. Титенко Е.А. Метод структурного распознавания образов. //Сб. материалов 2-ой международной конференции "Распозна-вание-95". Курск. 2-6 октября 1995 г. С. 260.

3. Титенко Е. А. Специализированное устройство восстановления грамматики.// Труды юбилейной научной конференции. Часть 2 КГТУ. Курск. 1995. С. 60-62.

4. Положительное решение от 14.01.97 о выдаче патента на изобретение (Россия), МЛК Н 03 М 7/02. Устройство преобразования двоичного кода в двоичный унитарна код / Титенко Е. А. и др.. (Россия). - N94010177/09; Заявлено 22.03.94.

5. Положительное решение от 09.01.97 о выдаче патента на изобретение (Россия). МПК й 06 Г 7/50. Параллельный асинхронный сумматор. / Титенко Е.А. и др. (Россия). - N94010178/09; Заявлено 22.03.94.

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

ГОТ.П1 КОНЕЦ лаост ВХЩ ВЫХОД ПУСК ввод

Рис. 2

СТРУКТУГ! 1ЛЯ СХЕМА 11|ЧЛДУК1Ц1< И ИI« И « > I Н'< >4 U Х'С< Hill HO УС1ТОЙСТИЛ

График зависимости количества выводов от стратегии ЛВ

Таблица I

Таблица оценок работы мультипроцессора на задаче "обезьяна и банан"

' СИСТЕМЫ -------------- X АГАКГГРШСТИКИ^--^- «•wi> I IM) l ) («-ПМ1»*) 4 )

ОГлоде кплчеспо тдпо« работ ТиСм 41 1) »1 134 140

Кмичсспо п*тси м "смсиыммс" т„ 1 и 36 67 77

ТУт 16.7 30.« 39.6 30.0 ал

U^iTKfipcucccop, Jlii 1.« 10 10 11.4 11.4

Ыупияпримсссор. ЛЦ ( с юрреникй ) 10 13 м 17 17.7

Кшичеспо путей 2 4 6 13 II

rSl4ipo(K<co(4 ilj} II и 36 57 13

Соискатель Е.А.Титенко

Подписано к печати_ . Формат 60x84 1/16

Печатных листов_. Тираж 100 эю. Заказ /6

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