УСТРОЙСТВО ДЛЯ РЕАЛИЗАЦИИ ПРОДУКЦИЙ Российский патент 1995 года по МПК G06F17/00 G06F17/20 

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

Известно устройство для реализации нормальных алгоритмов, аппаратно поддерживающее продукционную систему А.Маркова (авт. св. N 1455345).

Известно также более быстродействующее устройство для реализации подстановок слов, реализующее продукции А. Маркова [1]
Известно также устройство для реализации подстановок слов, которое позволяет обрабатывать данные символьного и числового типов с помощью нормальных алгоритмов, состоящих исключительно из формул подстановок с двухбуквенными левыми и правыми частями. При этом все левые части (антецеденты) формул параллельно (одновременно) сопоставляются с двухбуквенным исходным словом (ситуацией) с помощью ассоциативного узла сравнения. По существу в этом устройстве реализуется одна из моделей продукционных систем таблица решений, причем левая и правая части таблицы содержат исключительно двухбуквенные слова [2]
Была поставлена задача: расширить класс аппаратно реализуемых продукций за счет переменной длины слов ситуации, а также переменной длины левых и правых частей продукций. Изобретение позволит обеспечить высокоскоростной ассоциативный процесс сопоставления слов ситуации и антецедентов, идентификацию активной продукции и выборку (считывание) соответствующего консеквента.

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

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

Продукции (продукционные правила) представляют собой операторы специального вида и состоят из двух основных частей:
Р ->> Q,
где левая часть (антецедент) Р описывает определенную ситуацию S внешней среды, а правая часть (консеквент) Q представляет собой действие, выполнение которого предполагается в случае обнаружения сопоставимой ситуации. Впервые метод продукции был предложен Е. Постом в 1936 г. и использован Н. Хомским для определения языков и формальных грамматик. С 1974 г. он находит широкое применение в многочисленных программах, которые получили название экспертных систем. В настоящее время системы продукций принято рассматривать как парадигму символьных вычислений.

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

На фиг. 1 изображена структурная схема устройства для реализации продукций; на фиг. 2 представлена структурная схема узла сравнения; на фиг. 3 функциональная схема ячейки узла сравнения; на фиг. 4 структурная схема блока тегов; на фиг. 5 функциональная схема ячейки 19-го блока тегов; на фиг. 6 функциональная схема ячейки 20-го блока тегов; на фиг. 7 структурная схема блока идентификации активной продукции; на фиг. 8 функциональная схема элемента блока идентификации активной продукции; на фиг. 9 содержательная ГСА работы устройства; на фиг. 10 размеченная ГСА работы устройства.

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

Для описания алгоритма блока 8 управления используются следующие идентификаторы:
1. "Сброс" команда сброса работы устройства.

2 "Пуск" команда запуска устройства.

3. ПрТС управляющий сигнал приема текущей ситуации в блок 1 памяти слов.

4. ЧтСМ управляющий сигнал чтения символа и маркеров ситуации из блока 1 памяти слов.

5. ЗпСМ управляющий сигнал записи символа и маркеров ситуации в регистр 2 символа ситуации и в регистр 3 маркеров ситуации.

6. ССС сигнал сопоставимости слова ситуации.

7. Сдв управляющий сигнал сдвига в регистр 7 сдвига указателя считывания.

8. ЧтК управляющий сигнал чтения консеквента из узла 4 сравнения.

9. КК сигнал конца консеквента.

10. НУ сигнал сброса в исходное состояние элементов хранения блока 6 идентификации активной продукции и регистра 7 сдвига указателя считывания.

11. МТ сигнал, сообщающий о типе слова (антецедент или консеквент), маркер типа слова.

12. МК сигнал, сообщающий о конце слова ситуации, маркер конца слова.

13. СНС сигнал несопоставимости слова ситуации с заданными антецедентами.

Узел 4 сравнения представляет собой однородную ассоциативную среду, организованную как N 8-битовых элементов, посимвольно хранящих продукционные правила. Таким образом, сравнение символа ситуации, поступающего на регистр 2 символа ситуации, осуществляется параллельно со всеми символами всех продукций. Аналогично организован блок 5 тегов, представляющий собой ассоциативную память 3х хN. Узел 4 сравнения и блок 5 тегов формируют соответственно пакеты сигналов сопоставимости СС1 и СС2. В блоке 6 идентификации активной продукции на каждом такте сравнения анализируются сигналы СС2 и определяется позиция консеквента, который необходимо прочесть из узла 4 сравнения в случае сопоставимости слова ситуации и соответствующего антецедента. При этом в регистре 7 сдвига указателя считывания фиксируется эта позиция и в цикле посимвольного считывания сдвигается до тега конца консеквента. После чего сигналом НУ: 1 ячейки хранения блока 6 идентификации активной продукции и регистра 7 сдвига указателя считывания сбраcываются в исходное состояние и начинается посимвольное сравнение следующего слова ситуации в узле 4 сравнения.

Рассмотрим подробнее организацию и функционирование устройства.

Работа устройства для реализации продукций заключается в следующем.

По команде "Сброс":1 все элементы устройства устанавливаются в исходное состояние. По команде "Пуск": 1 устройство начинает работать. По команде ПрТС:1 в блок 1 памяти слов осуществляется прием текущей ситуации (ТС) внешней среды. Текущая ситуация это совокупность слов, каждое из которых в левом и правом крыле содержит соответственно однобитовый признак начала и однобитовый признак своего конца (МН маркер начала слова, МК маркер конца слова). Все слова ситуации, кроме последнего слова, имеют еще маркер МТ:0. Указанные тройки маркеров, МН, МК и МТ, в блоке 1 памяти слов организованы в виртуальный массив, который будем называть "Маркеры ситуации", таким образом, что по командам ЧтСМ:1 и ЗпСМ:1 на каждом такте сравнения из блока 1 памяти слов в регистр 2 символа ситуации и в регистр 3 маркеров ситуации соответственно загружаются: символ слова ситуации и маркеры.

В одном такте сравнения происходит следующее.

В узле 4 сравнения, представляющем собой однородную ассоциативную среду, хранящую последовательно (друг за другом) левые и правые части продукций, параллельно сопоставляются все символы с символом, который находится на регистре 2 символа ситуации. Выходной вектор сигналов СС1 узла 4 сравнения, идентифицирующий все позиции совпадения, передается на блок 5 тегов, также представляющий собой ассоциативное устройство сопоставления, в котором хранятся теги слов продукций, по смыслу аналогичные маркерам слов ситуации. При этом маркер МТ соответствует тегу, который идентифицирует антецеденты и консеквенты продукций (в данном устройстве реализован режим сопоставления только с антецедентами, поэтому МТ:0 соответствует признаку антецедента). Заключительная фаза сравнения реализуется в блоке 6 идентификации активной продукции, который получает от блока 5 тегов пакеты сигналов сопоставимости СС2, ТН и ТК. Посимвольный процесс сопоставления (цикл сравнения) заканчивается, если на блок 8 управления из блока 6 идентификации активной продукции поступил сигнал ССС:1 сигнал сопоставимости слова ситуации с каким-либо антецедентом, или, если ССС:0, но МК:1, т. е. ни один антецедент не сопоставим со словом ситуации и тогда блок 8 управления выдает внешний сигнал СНС:1 сигнал несопоставимости слова и устройство заканчивает работу. В первом случае, когда ССС:1, начинается чтение консеквента.

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

В регистр 7 сдвига указателя считывания после завершения цикла сравнения из блока 6 идентификации активной продукции параллельно записывается вектор сигналов ССЗ. Это вектор содержит всего одну позицию, значение которой равно логической единице "1", названную "указателем считывания". На каждом такте посимвольного чтения консеквента в регистр 7 сдвига указателя считывания поступает управляющий сигнал сдвига Сдв:1, а узел 4 сравнения сигнал чтения консеквента ЧтК:1, кроме того, блок 8 управления анализирует сигнал КК конец консеквента, поступающий из блока 5 тегов; если КК=0 цикл чтения продолжается, если КК=1 заканчивается, а элементы хранения регистра 7 сдвига указателя считывания и блока 6 идентификации активной продукции устанавливаются в исходное состояние сигналом НУ:1.

Устройство заканчивает свою работу, если на регистр 3 маркеров ситуации из блока 1 памяти слов поступает сигнал МТ:1, в противном случае (МТ:0) начинается следующий цикл сравнения.

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

Структурная схема узла 4 сравнения представлена на фиг. 2.

Символ-компаранд СимС1 (символ слова ситуации) является входным пакетом сигналов, а пакет СС1 выходным в цикле сравнения. В цикле считывания на вход узла 4 сравнения поступает разрешающий сигнал ЧтК:1 чтения консеквента и вектор УСч указатель считывания, а выходным в цикле считывания является символ консеквента, обозначенный переменной К. Узел 4 сравнения организован как однородная "прозрачная" память, в которой элементарной ячейкой является блок 10 на фиг. 2. Функциональная схема ячейки 10 представлена на фиг. 3. Ячейка узла сравнения состоит из: элемента хранения Т11, представленного DV-триггером; схемы полусумматора с отрицанием, включающей элементы И12, И13 или ИЛИ-НЕ14, которая фиксирует совпадение; элемента И15, требуемого для организации "сквозного переноса" сигнала совпадения по битам символа; и схемы считывания, состоящей из элементов И16 и ИЛИ17.

Структурная схема блока 5 тегов представлена на фиг. 4.

Блок 5 тегов как и узел 4 сравнения представляет собой однородную ассоциативную среду. В отличие от узла 4 сравнения блок 5 тегов содержит два вида элементарных ячеек, что обусловлено их различным функциональным назначением. Теги конца слов продукций хранятся в ячейках 19, а теги начала слов продукций и теги типа слов продукций (антецедент или консеквент) в ячейках 20 (фиг. 4). На фиг. 5 представлена функциональная схема ячейки 19. Здесь Т21 элемент хранения; И23, И24 и ИЛИ-НЕ26 составляют схему сопоставления; И22 и И25 "переносят" сигнал конца консеквента; И21 "переносит" сигнал совпадения. На фиг. 6 представлена функциональная схема ячейки 20, которая включает Т28 элемент хранения; И29, И30 и ИЛИ-НЕ31 схему сопоставления; И32 элемент "переноса" сигнала сопоставления.

Cтруктурная схема блока 6 идентификации активной продукции представлена на фиг. 7.

Входные пакеты сигналов СС2, ТН и ТК поступают из блока 5 тегов (фиг. 1), анализируются в элементарных блоках 33 (фиг. 7) и на основе этого анализа выдается вектор СС3 для регистра 7 сдвига указателя считывания (фиг. 1). На фиг. 8 представлена функциональная схема элемента 33 блока 6 идентификации активной продукции. Сигнал пакета СС2 (фиг. 8, вход 2) поступает на элемент хранения Т34. Элементы И35, И36 и ИЛИ37 составляют первый каскад схемы 33, в котором определяется ситуация сопоставимости начала слова и ситуация сопоставимости очередного символа слова. Второй каскад схемы 33 представлен: элементом хранения Т38, который фиксирует одну из указанных выше ситуаций; элементами ИЛИ41, И42 и СТ2 43, составляющими схему, которая распознает особую ситуацию, когда начальные символы и последний символ слова ситуации совпадают с антецедентом, но при этом слово ситуации по количеству символов превосходит антецедент, например, слово ситуации "КУСОЧЕК", а антецедент "КУСОК". Элемент СТ2 43 отслеживает эту ситуацию и в случае ее появления Т38 сбрасывается И, наконец, третий каскад включает элементы И39 и ИЛИ40, разрешающие выдачу указателя считывания по тегу конца ТК и "переносящие" сигнал ССС сопоставимости слова.

Устройство может быть использовано как электронный переводчик с иностранного языка слов и словосочетаний.

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

Содержательная ГСА приведена на фиг. 9 и отражает работу блока 8 управления. По команде "Сброс:1" (блок 2 граф-схемы алгоритма) происходит установка в ноль всех элементов устройства. По сигналу "Пуск:1" (блок 3) устройство начинает работу.

По команде ПрТС:1 (блок 4 алгоритма) происходит прием текущей ситуации в блок 1 памяти слов.

По команде ЧтСМ:1 и ЗпСМ:1 блока 5 алгоритма из блока 1 памяти слов считываются символ ситуации и маркеры ситуации и записывается соответственно в регистр 2 символа ситуации и регистр 3 маркеров ситуации.

В блоке 8 алгоритма происходит проверка признака сопоставимости слова ситуации ССС.

В блоке 7 алгоритма по команде Сдв:1 происходит сдвиг в регистре 7 сдвига указателя считывания.

В блоке 8 алгоритма по команде ЧтК:1 читается символ консеквента из узла 4 сравнения.

В блоке 9 алгоритма проверяется признак конца консеквента "КК".

Блок 10 алгоритма содержит команду НУ:1 команду начальной установки элементов хранения блока 6 идентификации активной продукции и регистра 7 сдвига указателя считывания.

В блоке 11 алгоритма проверяется признак МТ.

В блоке 12 алгоритма анализируется маркер конца МК.

Блок 13 алгоритма содержит внешний сигнал СНС:1 сигнал несопоставимости слова ситуации антецедентам системы продукций.

В блоке 14 алгоритма фиксируется конец его работы.

Блок 8 управления (фиг. 1) синтезируется на основе ГСА алгоритма управления (фиг. 9) известным способом. Размеченная ГСА работы блока 8 управления приведена на фиг. 10, где обозначено:
Логические условия:
Х1: "Пуск" Х4: МТ
Х2: ССС Х5: МК
Х3: КК
Операторы:
Y1: Сброс:1 Y4: ЗпСМ:1 Y7: НY:1
Y2: ПрТС:1 Y5: Сдв:1 Y8: СНС:1
Y3: ЧтСМ:1 Y6: ЧтК:1

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

УСТРОЙСТВО ДЛЯ РЕАЛИЗАЦИИ ПРОДУКЦИЙ, содержащее блок памяти слов, узел сравнения, блок управления, отличающееся тем, что дополнительно введены регистр символа ситуации, регистр маркеров ситуации, блок тегов, блок идентификации активной продукции, регистр сдвига указателя считывания, причем первый и второй выходы блока управления соединены соответственно с первым и вторым управляющими входами блока памяти слов, информационный вход которого является входом текущей ситуации устройства, третий выход блока управления соединен с управляющими входами записи регистра символа ситуации и регистра маркеров ситуации, информационные входы которых соединены соответственно с первым и вторым информационными выходами блока памяти слов, информационный выход регистра символа ситуации соединен с первым информационным входом узла сравнения, первый информационный выход которого является выходом консеквента устройства, первый управляющий выход регистра маркеров ситуации соединен с первым управляющим входом блока тегов и пятым входом блока управления, четвертый вход которого соединен с третьим управляющим выходом регистра маркеров ситуации и третьим управляющим входом блока тегов, второй управляющий вход которого соединен с вторым управляющим входом регистра маркеров ситуации, четвертый выход блока управления соединен с управляющим входом чтения узла сравнения, второй информационный выход которого соединен с первым информационным входом блока тегов, управляющий выход которого соединен с третьим входом блока управления, шестой вход которого соединен с управляющим выходом блока идентификации активной продукции, первый, второй и третий информационные входы которого соединены соответственно с первым, вторым и третьим информационными выходами блока тегов, пятый выход блока управления соединен с входом установки в "О" регистра сдвига указателя считывания и входом установки в начальное состояние блока идентификации активной продукции, информационный выход которого соединен с информационным входом регистра сдвига указателя считывания, информационный выход которого соединен с вторым информационным входом узла сравнения и вторым информационным входом блока тегов, шестой выход блока управления соединен с управляющим входом регистра сдвига указателя считывания, первый и второй входы блока управления являются входами пуска и сброса устройства, седьмой выход блока управления является выходом несопоставимости слова устройства.