Ассоциативное запоминающее устройство

 

Изобретение относится к вычислительной технике и может быть использовано преимущественно для отображения специальных семантических структур - пирамидальных сетей. Цель изобретения - расширение области применения устройства путем обеспечения хранения данных, организованных в виде пирамидальных сетей. Устройство содержит блок 1 управления, матричный блок 2 памяти, блок 3 обнаружения ассоциаций, коммутаторы 4 и 5 и дешифратор 6. Устройство работает в двух режимах: построение пирамидальной сети (запись информации) и анализ пирамидальной сети (ассоциативный поиск и чтение информации). 4 ил.

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК (5114 С 11 С 15/00

3.E.4q

ПИЕ1Tr.

Б 4 БА,:;

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

Н АВТОРСКОМУ СВИДЕТЕЛЬСТВУ

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

ПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ

ПРИ ГКНТ. СССР (21) 4187982/24-24 (22) 28.01.87 (46) 07,05.89. Бюл. Р 17 (71) Институт кибернетики им. В.М.Глушкова (72) Н.И.Галаган, Е.И,Ершов, 3.Л.Рабинович и В.Ф.Соломатин (53) 681.327 (088,8) (56) Авторское свидетельство СССР

N- 1056269, кл. G 11 С 15/00, 1982.

Авторское свидетельство СССР

N - 1127008, кл. С 11 С 15/00, 1983. (54) АССОЦИАТИВНОЕ ЗАПОМИНАЮЩЕЕ УСТРОЙСТВО (57) Изобретение относится к вычислительной технике и может быть исполь „„SU„„1478255 А 1 зовано преимущественно для отображения специальных семантических структур †пирамидальных сетей. Цель изобретения — расширение области применения устройства путем обеспечения хранения данных, организованных в виде пирамидальных сетей. Устройство содержит блок 1 управления, матричный блок 2 памяти, блок 3 обнаружения ассоциаций, коммутаторы 4 и 5 и дешифратор 6. Устройство работает в двух режимах: построение пирамидальной сети (запись информации) и анализ пирамидальной сети (ассоциативный поиск и чтение информации), 4 ил.

1478.255

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

На фиг. 1 изображена структурная схема ассоциативного запоминающего устройства; на фиг. 2 - структурная схема блока обнару ения ассоциаций) 15 на фиг. 3 — структурная схема матричного блока памяти; на фиг. 4 - блоксхема алгоритма функционирования блока управления при построении пирамидальной сети.

Устройство (фиг. 1) содержит блок

1 управления, матричный блок. 2 памяти, блок 3 обнаружения ассоциаций, первый 4 и,второй 5 коммутаторы и дешифратор 6. 25

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

7, второй 8 и третий 9 блоки совпадения, первый 10 и второй 11 счетчики импульсов, коммутатор 12 и блок

13 сравнения. Матричный блок 2 памяти (фиг,3) состоит из столбца БИС ОЗУ

14 (например, микросхем К155РУ5), количество которых равно количеству строк блока 2).

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

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

128 256-рязрядных БИС ОЗУ строится на базе однокристальной микроЭВМ серии К1816ВЕ48. Микросхема К1816ВЕ48 имеет три восьмиразрядных порта вво- 50 да-вывода. Для управления работой устройства необходимо иметь пять пор" тов ввода-вывода: два порта для задания адресов столбцов и строк блока 2, один порт для задания значения 55 порога, один порт для задания управляющих сигналов и сигналов синхронизации и один порт для организации интерфейсных связей с внешними устройствами. В микросхеме К1816ВЕ48 пред смотрена возможность увеличения числа портов за счет подключения внеш" них микросхем серии КР580.

Устройство может работать в режи ме построения пирамидальной сети (запись информации) и режиме анализа пирамидальной сети (ассоциативный поиск и чтение информации), Часть разрядов во всех БИС ОЗУ (столбцов блока 2) необходимо выделить под специальные поля меток.

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

Перад началом использования устройства очищаются все строки блока

2 путем записи нулей во все разряды

БИС ОЗУ по сигналам записи и групповой выборки из блока 1 управления, а также сбрасываются.в "0" счетчики 10 и 11 в блоке 3 по сигналам групповой выборки и установки. Счетчики 10 необходимо также сбрасывать каждый раз перед выполнением операции чтения содержимого строк блока

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

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

Первая Функция активности записывается в первую свободную строку блока 2. Эта строка в поле меток отмечается как занятая. Одновременно с за.писью строки в счетчике 11 подсчитывается и запоминается общее число активных входов (число единиц в строке), Так задаются связи ассо1478255 циативного элемента и порог, при котором наступает его полное возбуждение.

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

10 устройство переводится в режим чтения содержимого строк блока 2, В этом режиме блок 3 осуществляет операцию поразрядного логического умножения содержимого строк блока 2 и проверяемой функции активности, а

15 также подсчет числа возникающих при этом совпадений. Число совпадений по каждой строке сохраняется в счетчиках 10.

Возможны следующие ситуации: Iновая функция активности полностью совпадает с одной из ранее введенных;

II — новая функция активности полно" стью покрывает одну из ранее введенных; III — новая функция активности полностью входит в одну из ранее введенных; IV — новая функция активности и ранее введенные имеют частичные совпадения.(пересечения) описаний; V — новая функция активности не имеет общих связей с ранее введенными.

Для выявления ситуации I блок 1 управления настраивает коммутаторы

12 блока 3 на внутреннюю коммутацию. 35

B этом случае на входы блока 3 поступают сигналы с выходов счетчиков

10 и 11. При равенстве кодов на выходах блоков 13 появляются сигналы.

Состояние выходов блока 3 (выходы 40 схем сравнения) опрашивается блоком

1 управления через коммутатор 5. Если

t обнаруживается активность в строке, отличная от вновь записанной, то блок 1 управления перенастраивает 45 коммутаторы 12 блока 3 на внешнюю коммутацию, d этом случае на входы блоков 13 поступают сигналы с выходов счетчиков 10 и с информационных выходов блока 1 управления, на которых выставляется значение текущего порога, равного числу единиц в новой функции активности, При обнаружении активности в строке, отличной от вновь записанной, блок 1 управления аннулирует последнюю произведенную запись, идентифицируя ее как полностью совпадающую с ранее произведенной.

Для выявления ситуации II необходимо наличие .активности при внутренней коммутации и отсутствие активности при внешней коммутации. В этом случае необходимо произвести перестройку связей в ПС, которая осуществляется следующим образом. Блок 1 управления выполняет поразрядно. операцию ИСКЛЮЧАЮЩЕЕ ИЛИ над содержимым активных строк, Результат. операции перезаписывается в строку, которая была введена последней. Необходимо дополнительно скорректировать разряд этой строки (записать 1"), находящийся на пересечении со столбцом, соответствующим элементу, с выходом которого должна быть установлена активная связь, т.е. элементом, функция активности которого полностью вошла .во вновь введенную.

Для выявления ситуации Ш необходимо отсутствие активности при внутренней коммутации и наличие ее при внешней коммутации. Блок 1 управления выполняет те же операции, что и в случае ситуации II, за исключе-. нием того, что перезаписи и коррек- ции подвергается содержимое не новой, а ранее записанной строки °

Если активность не обнаруживается ни при внешней коммутации, ни при внутренней, то имеет место ситуация

IV или V. Для их разграничения блок 1 управления уменьшает величину текущего порога вплоть до значения, равного двум, каждый раз опрашивая состояние выходов блока 3, Если активности в строках, кроме вве-. денной последней, не будет обнаружено, то имеет место ситуация Ч,никаких перестроек в сети производить не, требуется.

При обнаружении активности в результате последних операций (т.е. имеет место ситуация IV) блок 1 управления выполняет поразрядно логическую операцию И над содержимым активных строк, Результат операции, соответствующий пересечению описаний. объектов, записывается в новую свобод; ную строку. Далее блок 1 управления выполняет поразрядно операцию ИСКЛЮЧАЮЩЕЕ ИЛИ над содержимым найденных активных строк и вновь записанной, а соответствующие результаты перезаписывает в каждую из найденных строк.

Одновременно в этих строках производится коррекция разрядов для отобра78255 6 перешедшие в возбужденное состояние ассоциативные элементы, считывается с выхопов блока 3 через коммутаторы 5.

45

5 14 жения связей с вьделенным общим ассоциативным элементом.

Для.ситуации IV блок 1 управления проверяет наличие пересечений при всех значениях порогов, на каждом шаге выполняя описанные операции. Действия, производимые блоком 1 управления в ситуациях I-V являются элементарными операциями. При построении ПС они могут циклически повторяться, входить в разных комбинациях друг в друга в сочетании с просмотрами ПС снизу-вверх и сверхувниз (фиг.4), Работа устройства в режиме анализа пирамидальной сети заключается в просмотре связей в ПС как снизу" вверх, так и сверху-вниз, в отображении процесса распространения возбуждения в ПС и в организации поиска информации по меткам.

Связи выходов любого элемента сети с активными входами других элементов отмечены единицами в разрядах соответствующего столбца блока

2. Для их просмотра блок 1 управления задает режим чтения выбранного столбца блока 2 (операция битового среза) и при значении текущего порога, равного единице, опрашивает выходы блока 3 через коммутатор 5.

Для просмотра активных входных связей ассоциативных элементов блок

1 управления считывает содержимое вы-, бранной .строки блока 2 через коммутатор 4, Для отображения процесса распространения возбуждения в ПС устройство переводится.в режим чтения по всем строкам блока 2 (одновременная выборка строк осуществляется за счет подачи на управляющий вход дешифратора 6 управляющего сигнала групповой выборки из блока 1 управления), При этом блок 3 будет поразрядно выполнять логическую операцию И над содержимым каждой из строк блока 2 и информацией (функцией возбуждения), поступающей с информационного выхода блока 1 управления. Одновременно в счетчиках 10 осуществляется подсчет числа возникающих совпадений по каждой строке. Коммутаторы 12 должны быть настроены на внутреннюю коммутацию.

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

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

Ф когда новая функция возбуждения совпадает с ранее предъявленной.

Для поиска отмеченных строк блок

1 управления вьдает адреса полей меток и код метки поиска. Коммутаторы

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

Формула изобретения

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

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

1478255

Л

Ъ

Jg

Уу

ФигЕ

2> г, II

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

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

"Подтверждение считывания" устрой« ства. !

1478255

Составитель В,Рудаков

Техред JI.Îëèéíûê Корректор Э.Лончакова

Редактор А.Мотыль

Заказ 2367/50 Тираж 559 Подписное

ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР

113035, Москва, Ж-35, Раушская наб., д. 4/5

Производственно-издательский комбинат "Патент", r. Ужгород, ул. Гагарина, 101