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

 

1. АССОЦИАТИВНОЕ ЗАПОМИНА1О- ЩЕЕ УСТРОЙСТВО, содержащее входнойи выходной регистры, блок управления, накопитель, состоящий из адресных и основных ассоциативных элементов памяти, формирователи сигналов состояния ячеек памяти, причем первые входы элементов памяти подключены к соответствующим шинс1м опросазаписи, которые соединены с выходами входного регистра, вторые входы - с шинами разрешения считывания, третьи • с шинами разрешения записи, выходы адресных и первые выходы основных ассоциативных элементов памяти подключены к соответствующим шинам считывания, соединенным с входами выходного регистра, вторые выходы ассоциативных элементов памяти подключены к соответствующим шинам считывания сигналов совпадения, шины разрешения считывания и записи подключены к одним из выходов блока управления и первым и вторым входам формирователей сигналов состояния ячеек памяти, входы которых с третьих по шестые соединены с шинами считывания сигналов совпадения и другими выходами блока управления, входы которого подключены к выходам формирователей сигналов состояния ячеек памяти, о тличающееся тем, что, с целью увеличения быстродействия, в него введены дополнительные ассоциативные элементы памяти, причем первые входы дополнительных ассоциативных элементов памяти подключены к одному из выходов входного регистра, вторые входы - к шинам разрешения считывания, третьи - к шинам разрешения записи, первые выходы дополнительных ассоциативных элементов памяти 'соединены с одним из входов выходного регистра, вторые выходы - с одним из входов соответствующего ; формирователя сигналов состояния ячеек памяти.2. Устройство по п. 1, о т л ичающееся тем, что каждый формирователь сигналов сост'ояния ячеек памяти содержит триггеры и элек менты И и ИЛИ, причем выходы первого" и второго элементов И подключены к единичным входам первого и второго триггеров, нулевые входы которых соединены с выходом первого элемента ИЛИ, а выходы - с входами третьего элемента И, выход третьего триггера подключен к одним из входов первого и второго элементов И и является первым выходом формирователя сигналов состояния ячеек памяти, вторым выходом которого является выход третьего элемента И, выход второго элемента И]Ш подключен к одним из входов первого элемента ИЛИ и третье го триггера, другие входы которых, а также другие входы первого и второ го элементов- И являются входами формирователя сигналов состояния ячеек памяти.(П

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

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

РЕСПУБЛИК

ЗС59 С 11 С 15 00

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ

1 Д

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

Н АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 3513567/18-24 (22) 23 ° 11 ° 82 (4б) 15 03.84. Бюл. М 10 (72) С.К. Колубай и Ю.В. Лопухин (71) Харьковский ордена Трудового

Красного Знамени институт радиоэлектроники им. акад. М.К. Янгеля (53) 681 ° 327 (088. 8) (56) 1. Однородные микроэлектронные ассоциативные процессоры. Под ред. И В. Прангишвили. М., Советское радио™, 1973, с. 11.

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

Р 773730, кл. G 11 С 29/00, 1979 (прототип). (54) (57) 1. АССОЦИАТИВНОЕ ЗАПОМИНАОЩЕЕ УСТРОЙСТВО, содержащее входной и выходной регистры, блок управления, накопитель, состоящий из адресных и основных ассоциативных элементов памяти, формирователи сигналов состояния ячеек памяти, причем первые входы элементов памяти подключены к соответствующим шинам опросазаписи, которые соединены с выходами входного регистра, вторые входы — с шинами разрешения считывания, третьи с шинами разрешения записи, выходы адресных и первые выходы основных ассоциативных элементов памяти подключены к соответствующим шинам считывания, соединенным с входами выходного регистра, вторые выходы ассоциативных элементов памяти подключены к соответствующим шинам считывания сигналов совпадения, шины. разрешения считывания и записи подключены к одним из выходов блока управления и первым и вторым входам формирователей сигналов состояния ячеек памяти, входы которых с третьих по шестые соединены с шинами считывания сигналов совпадения и другими выхода„.Я0„„1080213 А ми блока управления, входы которого подключены к выходам формирователей сигналов состояния ячеек памяти, о тл и ч а ю щ е е с я тем, что, с целью увеличения быстродействия, в него введены дополнительные ассоциативные элементы памяти, причем первые входы дополнительных ассоциативных элементов памяти подключены к

I одному из выходов входного регистра, вторые входы — к шинам разрешения считывания, третьи — к шинам разрешения записи, первые выходы дополнительных ассоциативных элементов памяти соединены с одним из входов выходного регистра, вторые выходы — с одним из входов соответствующего Pg формирователя сигналов состояния ячеек памяти.

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

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

1080213

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

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

Недостатком этого устройства является невысокое быстродействие.

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

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

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

И, а входы подключены к другим входам первого и второго элементов И, к входам элемента ИЛИ и третьего триггера (21.

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

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

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

1080213

Элементы памяти, расположенные в одной строке, т.е. соединенные с одним и тем же формирователем 13, составляют одну ячейку памяти, соответствующую одному слову.

Таким образом, после посылки сигнала Сброс на все формирователи

13 все ячейки памяти находятся в состоянии Свободно .

Режим записи. Запись производится только в ячейки памяти, находящиеся в состоянии Свободно . Блок 3 управления выбирает одну из этих ячеек памяти и вырабатывает сигнал по соответствующей шине 8 разрешения записи. Одновременно основная информация и признаки выдаются из входного регистра 1 на соответствующие шины 10 опроса-записи. В результате основная информация и признаки записываются в выбранную ячейку памяти.

-Сигнал с шины 8 разрешения записи поступает также на вход 18 формирователя 13 и устанавливает триггер 25 в единичное состояние. На выходах формирователя формируется сигнал (1,0), означающий, что ячейка памяти находится в состоянии Занято .

В режиме записи иэ блока 3 управления на входы 20 всех формирователей

13 подается нулевой сигнал для того, чтобы предотвратить установку в единичное состояние триггеров 23 и 24 сигналами, которые могут появиться на шинах 12.

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

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

Для поиска всех слов АЗУ с первым и вторым признаками, одновременно принадлежащими множеству признаков onроса, необходимо осуществить К опросов. При каждом опросе содержимое всех элементов 5 и 6 памяти сравнивается с соответствующим очередным признаком опроса, выдаваемым из входного регистра 1 на шины 10 опросазаписи, соединенные с .элементами 5 и 6 памяти. Одновременно из блока 3 управления подается единичный сигнал на входы 20 всех формирователей

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

Если формирователь 13 индицирует состояние Занято и на его входе

14 или 15 появляется единичный сиг нал, то триггер 23 или 24 этого формирователя устанавливается в единичное состояние. Те формирователи 13, триггеры 23 и 24 которых в результ<— те опросов устанавливаются одновреЗначения сигналов на выходах 21 и 22 любого формирователя 13 сР„ и ф соответственно.

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

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

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

АЗУ содержит (фиг.1) входной регистр 1, выходной регистр 2, блок 3 управления, адресные 4 и ассоциативные основные 5, 6 и дополнительные

7 элементы памяти, служащие для хранения первых, вторых и третьих признаков, шины 8 разрешения записи, шины 9 разрешения считывания, шины

10 опроса-записи, шины 11 считывания, шины 12 считывания сигналов совпадения, формирователи 13 сигналов состояния ячеек памяти с входами 14-20 и выходами 21-22.

Каждый формирователь 13 содержит (фиг.2) первый 23, второй 24 и .третий 25 триггеры, первый 26, второй 40

27 и третий 28 элементы И, первый

29 и второй 30 элементы ИЛИ.

Первые 14, вторые 15 и третьи 16 входы формирователей 13 соединены с соответствующими шинами 12 совпаде-45 ния, четвертые 17 — с шинами 9 разрешения считывания, пятые 18 — с шинами 8 разрешения записи, шестые

19 и седьмые 20 — с соответствующими выходами блока 3 управления, а первые 21 и вторые 22 выходы формирователей 13 подключены к соответствующим входам блока 3 управления.

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

Из блока 3 управления на входы

19 всех формирователей 13 выдается сигнал Сброс . В результате триггеры 23-25 каждого формирователя

13 переходят в нулевое состояние, т.е. на выходах 21 и 22 всех формирователей устанавливаются нулевые значения сигналов °

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

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

Режим считывания. Считывание осуществляется только из ячеек памяти в состоянии Готово . Для этого на ячейку памяти подается сигнал по шине 9 разрешения считывания.

Считываемая информация принимается выходным регистром 2.Одновременно сигнал с шины 9 разрешения считывания поступает на вход 17 формирователя 13 и через элемент ИЛИ 29 на нулевые входы триггеров 23 и 24.

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

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

7. В результате сравнения на некоторых шинах 12 появляются единичные сигналы, которые поступают на входы

16 соответствующих формирователей

13. С вкода 16 единичный сигнал через элемент ИЛИ 30 поступает на нулевой вход триггера 25 и через эле1О мент ИЛИ 29 на нулевые входы триггеров 23 и 24. Это приводит к Формированию на выходе Формирователя сигнала (0,0), т.е. ячейка устанавливается в состояние Свободно .

15 Таким образом, все ячейки, содержащие одинаковый ассоциативный признак в элементах 7, переводятся в состояние Свободно при выдаче этого признака из входного регистра на шины 10 опроса-записи, соединенные с элементами 7 памяти.Состояние остальных ячеек при этом не изменяется.

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

40 в любые свободные ячейки.

1б 1ß rS

Фи .2

Заказ 1366/52

Тираж 575 Подписное

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

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

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

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

Редактор 3!. Веселовская Техред М.Кузьма Корректор C. Шекмар