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

 

ОП ИСАНИЕ

И„ЗОБРЕТЕ Н ИЯ

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

Союз Советскик

Социалистических

Республик

< 773730

l (6i ) Дополнительное к авт. саид-ву

Ь (51) М. Кл, . (22) Заявлено 04 04.7g (21) 2745595/18-24 с присоединением заявки РЙ

Государственный камитат (23) Приоритет

6 11 С 15/00

Опубликовано 2,3.10.80 Бюллетень Ле 3g по делам изебратений и открытий (53) УДК 681. .327 (088.8) Дата опубликования описания 02. 11.80 (72) Авторы изобретения

А. Г. Мурашко и С. К. Колубай

Харьковский институт радиоэлектроники (71) Заявитель (54) АССОЦИАТИВНОЕ ЗАПОМИНАКИЦЕЕ УСТРОЙСТВО

Изобретение относится к запоминающим устройствам.

Известно ассоциативное запоминающее устройство (АЗУ) содержащее ячейки памяти основной информации, ячейки

5 памяти ассоциативных признаков, регистр опроса, схемы сравнения ассоциативных признаков с признаком опроса, индикатор совпадения (1) .

Недостатком этого устройства является невысокое быстродействие при поиске информации, у которой совпадают одновременно два признака с любыми иэ признаков из множества признаков опроса, Наиболее близким по технической cymности к предлагаемому устройству является АЗУ, содержащее входной блок, выходной блок, блок управления, ячейки памяти основной информации и ассоциативных признаков, шины опроса-записи, шины считывания, шины совпадения, шины разрешения записи и шины разрешения считывания, причем первые входы ячеек памяти соединены с соответствующими шинами опроса-записи вторые — с шинами разрешения считывания, третьи — с шинами разрешения записи, первые выходы ячеек памяти подключены к соответствующим шинам считывания, а вторые — к шинам совпадения, шины опроса-записи соединены с соответствующими выходами входного блока, шины считывания — с соответствующими входами выходного блока, шины разрешения записи и шины разрешения считывания — с соответствующими выходами блока управления, а шины совпадения — с соответствующими входами блока управления (2).

Недостатком этого АЗУ является невысокое быстродействие при поиске информиции, у которой должны совпадать одновременно два признака с любыми из

iK (K)1) . признаков из некоторого множества признаков опроса. При решении этой задачи на данном АЗУ требуется выделить в каждом слове ячеек памяти два бита для запоминания результатов опроса каждого признака отдельно. Затем

3 7737 необходимо выполнить 2 К микрокоманд опроса и 2 К ми. рокоманд записи, т.е. всего 4 К микрокоманд опроса-записи.

Таким образом, данное АЗУ не позволяет найти необходимую информацию за

К опросов.

Цель изобретения — увеличение быстродействия АЗУ при поиске информации, у которой должны совпадать одновременно два признака с любым из К (К > 1) признаков из некоторого множества признаков опроса и осуществление этого поиска за

К опросов.

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

При этом формирователь сигналов со- 45 стояния ячеек памяти целесообразно выполнить содержащим триггеры и элементы

И и ИЛИ, причем выходы первого и второго элементов И подключены к единичным входам первого и второго триггеров, 50 нулевые входы которых соединены с выходами элемента ИЛИ, а выходы — со входами третьего элемента И, выход третьего триггера подключен к .одним, из входов первого и второго элементов И и пер вому выходу формирователя сигналов состояния ячеек памяти, второйвыходкотсо рого соединен с выходом третьего элемента И, а входы подключены к другим

30 4 входам первого и второго элементов И и входам элемента ИЛИ и третьего триг. герае

На фиг. 1 изображена структурная схема АЗУ; на фиг. 2 — структурная схема формирователя сигналов состояния яче ек памяти.

АЗУ содержит входной регистр 1, выходной регистр 2, блок 3 управления, адресные элементы 4 памяти, ассоциативные элементы 5 и 6 памяти, служа-. щие для хранения первых и вторых признаков, формирователи 7 сигналов состояния ячеек памяти с входами 8-13 и выходами 14-15, шины 16 разрешения записи, шины 17 разрешения считывания, шины 18 опроса -записи, шины 19 считывания, шины 20 совпадения.

Первые 8 и вторые 9 входы формирователей 7 соединены с соответствующими шинам

20 совпадения, входы 10 — с шинами 17 разрешения считывания, входы 11 — с шинами 16 разрешения записи, входы 12 и 13 с соответствующими выходами блока 3 управления, а выходы 14 и 15 фор. мирователей 7 подключены к соответ<с гвующим входам блока 3 управления"

Формироввтель 7 содержит (см. фиг. ри йбрвый 21, второй 22 и третий 23 триг геры, первый 24, второй 25 и третий 26 элементы И, элемент ИЛИ 27. Выходы элементов И 24 и 25 подключены к единичным входам триггеров 21 и 22, нулевые входы которых соединены с выходом элемента ИЛИ 27, а выходы — со входами,рлемента И 26, выход триггера

23 подключен к одним из входов элементов И 24 и 25 и первому выходу формирователя 7, второй выход которого соединен с выходом элемента И 26, à вхо ды подключены к другим входам элементов И 24 и 25 и входам элемента 27 и триггера 23.

АЗУ работает следующим образом.

Начальная установка состояния всех ячеек памяти АЗУ.

Из блока 3 управления на входы 12 всех формирователей 7 выдается сигнал

Сброс . В результате триггеры 21, 22 и 23 каждого формирователя 7 переходят в нулевое состояние, т.е. на выходах 14 и 15 всех формирователей установятся нулевые значения сигналов. Значения сигналов на выходах любого формирователя 7 обозначаем парой (х х )

1 где х, х1 — значения сигналов на выходах 14 и 1Ь При описании работы АЗУ считаем, что элементы памяти, расположенные в одной строке т.е. соеди7737 ненные с одним и тем же формирователем 7, составляют одну ячейку памяги, соответствующую одному слову.

Таким образом, после посылки сигнала Сброс" на все формирователи 7 на их выходах установятся сигналы, рав= ные (О, О), означающие, что все ячейки памяти находятся в состоянии Свободно.

Режим записи.

Запись производится только в ячейки памяти, находящиеся в состоянии Свободно Блок 3 управления выбирает одну из этих ячеек памяти и вырабатывает сигнал по соответствующей шине 16 разрешения записи. Одновременно основная 1 информация и признаки выдаются из входного регистра 1 на соответствующие шины 18 опроса-записи, В результате . основная информация и признаки записываются в выбранную ячейку памяти. Сигнал с, шины 16 разрешения записи поступает также на вход 11 формирователя 7 и устанавливает триггер 21 в единичное состояние. На выходах формирователя формируется сигнал (1, О), означающий, что ячейка памяти находитсЯ в состоЯнии Занято", В Режиме записи из блока 3 управления на входы

13 всех формирователей 7 подается нулевой сигнал, для того, чтобы предотвратить установку в единичное состояние триггеров 22 и 23 сигналами, которые могут появиться на шинах 20 совпадения. Основная информация и признаки записываются в другие ячейки памяти аналогично. Таким обрезом, все ячейки

35 памяти, в которые осуществлена запись, переходят в состояние Занято .

Режим поиска.

Щ

Пусть множество признаков опроса содержит К признаков. Для поиска всех слов

АЗУ с первым и вторым признаками, одновременно принадлежащими множеству призна«ов опроса, необходимо осуществить К опросов. При каждом опросе содержимое всехэлементов 5 и 6 памяти сравнивается с соответствующим очередным признаком опроса, выдаваемым из входного регистра 1 на шины 18 опроса-записи, со- у> единенные с элементами 5 и 6 памяти.

Одновременно из блока управления 3 подается единичный сигнал на входы 13 всех формирователей 7. В результате сравнения на некоторых шинах 20 совпадения появляются единичные сигналы, которые поступают на соответствующие входы формирователей 7. Если формирователь 7 иццлпирует состояние "Занято"

30 6 и на его входе 8 или 9 появляется единпчный сигнал, то триггер 22 или 23 этого формирователя устанавливается в единичное состояние. Те формирователи

7, триггеры 22 и 23 которых в результате опросов устанавливаются одновременно в единичное состояние, формируют на выходах. 15 единичный сигнал, т.е. на выходах этих формирователей устанавливается сигнал (1, 1), означающий, что данная ячейка памяти находится в состоянии

"Готово". После К опросов в такое ñîстояние установятся все искомые ячейки памяти.

Режим считывания.

Считывание осуществляется только из

Ячеек памЯти в состоЯнии Готово Дли этого на ячейку памяти подается сигнал по шине 17 разрешения считывания. Считываемая информация принимается выходным регистром 2. Одновременно сит нал с шины разрешения считывания поступает на вход 10 соответствующего формирователя 7 и через элемент ИЛИ

27 на нулевые входы триггеров 22 и 23.

Это приводит к формированию на выходе

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

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

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

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

2.Устройствопоп.1, о т л и ч а ю— щ е еся тем,,что формирователь сигпалов состояния ячеек памяти содержит триггеры и элементы И и ИЛИ, причем выходы первого и второго элементов И подключены к единичным входам первого и второго триггеров, нулевые входы которых соединены с выходом элемента

ИЛИ, а выходы — со входами третьего элемента И, выход третьего триггера подключен к одним из входов первого и вт 10 рого элементов И и первому выходу формирователя сигналов состояния ячеек памяти, второй выход которого соединен с выходом третьего элемента И, а входы подключены к другим входам первого и и второго элементов И и входам элемента

ИЛИ и третьего триггера.

Источники информации, принятые во внимание при экспертизе

1. Майоров С. А., Новиков Г. И. Принщ ципы организации цифровых машин, Л., Машиностроение", 197 Ф, с. 393, рис. 10. 20

2. Спнородные микроэлектронные ассоциативные процессоры. Под ред.

zs И. В. Прангишвили, М. "Советское радио", 1973, с. 11, рис. 1. 1 (прототип).

Ю

Ц

42 Н

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

Редактор Г. Волкова ТехредТехред Н. Бабурка Коррекор М. Вигула

Заказ 7517/69 Тираж 662 Подписное

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

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

Филиал П! !П "Патент", г. Ужгород, ул. Проектная, 4