Ассоциативное запоминающее устройство Советский патент 1984 года по МПК G11C15/00 

Изобретение относится к вычислительной технике и может быть использовано в устройствах для поиска информации. Известно ассоциативное запоминаю щее устройство, содержащее входной и выходной блоки, блок управления, ячейки памяти основной информации и ассоциативных признаков, связанные с шинами опроса-записи, считывания, совпадения, разрешения записи и считывания Г1. Недостатком этого устройства является невьзсокое быстродействие. Наиболее близким к предложенному по техническому решению является ассоциативное запоминающее устройство (АЗУ), содержащее входной и выходной регистры, блок управления, адресные элементы памяти, ассоциативные элементы памяти, служащие для хранения первых и вторых признаков, формирователи сигналов состояния ячеек памяти, шины разрешения записи, разрешения считывания, опроса - записи, считывания, совпадения, причем первы входы элементов памяти подключены к соответствующим шинам опроса-записи которые соединены с выходами входног регистра, вторые входы - с шинами разрешения считывания, третьи - с шинами разрешения записи, выходы адресных и первые выходы основных ассоциативных элементов памяти подключены к соответствующим шинам считыва ния, соединенным с входами выходного регистра, вторые выходы ассоциативных элементов памяти подключены к соответствующим шинам совпадения, шины разрешения считывания и записи подключены к одним из выходов блока управления, первые и вторые-входы формирователей сигналов состояния ячеек памяти соединены с.соответствующими шинами совпадения, третьи входы - с шинами разрешения считывания, четвертые входы - с шинами разрешения записи, а пятые и шестые с другими выходами блока управления первые и вторые выходы формирователей сигналов состояния ячеек памяти подключены к соответствующим входам блока управления, причем каждый формирователь сигналов состояния ячеек памяти содержит триггеры, элементы И и ИЛИ, причем выходы первого и второго элементов И подключены к еди ничным входам первого и второго триггеров,, нулевые входы которых соединены с выходом элемента ИЛИ, а выходы - с входами третьего элемента И, выход третьего триггера подключен к одним из входов первого и второго элементов И и первому выходу формирователя сигналов состояния яче.ек памяти, второй выход которого соединен с выходом третьего элемента И, а входы подключены к другим входам первого и второго элементов И, к входам элемента ИЛИ и третьего триггера 2. Однако это устройство характеризуется невысоким быстродействием в режиме перевода ячеек памяти в состояние Свободно, а также ограниченными функциональными возможностями, так как в нем невозможен перевод в состояние Свободно произвольной группы ячеек, содержащих одинаковый ассоциативный признак, без изменения состояний остальных ячеек памяти. Цель изобретения - повышение быстродействия и расширение функциональных возможностей АЗУ путем обеспечения возможности перевода в состояние Свободно произвольной группы ячеек памяти, содержащих одинаковый ассоциативный признак, без изменения состояний остальных ячеек памяти. Поставленная цель достигается тем, что в ассоциативное запоминающее устройство, содержащее входной и выходной регистры, блок управления, накопитель, состоящий из адресных и основных ассоциативных элементов памяти, формирователи сигналов состояния ячеек памяти, причем первые входы элементов памяти подключены к соответствующим шинам опроса-записи, которые соединены с выходами входного регистра, вторые входы - с шинами разрешения, считывания, третьи - с шинами разрешения записи, выходы адресных и первые выходы ассоциативных элементов памяти подключены к соответствующим шинам считывания, соединенным с входами выходного регистра, вторые выходы основных ассоциативных элементов памяти подключены к соответствующим шинам считывания сигналов совпадения, шины разрешения считывания и записи подключены к одним из выходов блока управления и первым и вторым входам формирователей сигналов состояния ячеек памяти, входы которых с третьих по шестые соединены с шинами считывания сигналов совпадения и другими выходами блока управления, входы которого подключены к выходам формирователей сигналов состояния ячеек памяти, введены дополнительные ассоциативные элементы памяти, причем первые входы дополнительных ассоциативных элементов памяти подключены к одному из выходов входного регистра, вторые входы - к шинам разрешения считывания, третьи - к шинам разрешения записи, первые выходы дополнительных ассоциативных элементов памяти соединены с одними из входов выходного регистра, вторые выходы с одним из. входов соответствуняцего формирователя сигналов состояния ячеек памяти. Каждый формирователь сигналов состояния ячеек памяти содержит три геры и элементы И и ИЛИ, причем выходы первого и второго элементов И подключены к единичным входам перво го и второго триггеров, нулевые вхо ды которых соединены с выходом пер вого элемента ИЛИ, а выходы - с вхо дами третьего элемента И, выход третьего триггера подключен к одним из входов первого и второго элементов И и является первым выходом фор мирователя сигналов состояния ячеек памяти, вторым выходом которого является выход третьего элемента И, в ход второго элемента ИЛИ подключен к одним из входов первого элемента ИЛИ и третьего триггера, другие вхо ды которых, а также другие входы пе вого и второго элементов И являются входами формирователя сигналов состояния ячеек памяти. На фиг.1 изображена структурная схема АЗУ; на фиг.2 - структурная схема формирователя сигналов состоя ния ячеек памяти. АЗУ содержит (фиг.1) входной регистр 1, выходной регистр 2, блок 3 управления, адресные 4 и ассоциатив ные основные 5, 6 и дополнительные 7 элементы памяти, служащие для хра нения первых, вторых и третьих приз наков, шины 8 разрешения записи, шины 9 разрешения считывания, шины 10 опроса-записи, шины 11 считывани шины 12 считывания сигналов совпаде ния, формирователи 13 сигналов состояния ячеек памяти с входами 14-20 и выходами 21-22. Каждый формирователь 13 содержит (фиг.2) первый 23, второй 24 итретий 25 триггеры, первый 26, второй 27 и третий 28 элементы И, первый 29 и второй 30 элементы ИЛИ. Первые 14, вторые 15 и третьи 16 входы формирователей 13 соединены с соответствующими шинами 12 совпаде ния, четвертые 17 - с шинами 9 разрешения считывания, пятые 18 - с шинами 8 разрешения записи, шестые 19 и седьмые 20 - с соответствующими выходами блока 3 управления, а первые 21 и вторые 22 выходы формирователей 13 подключены к соответствующим входам блока 3 управления. АЗУ работает следующим образом. Из блока 3 управления на входы 19 всех формирователей 13 выдается сигнал Сброс. В результате триггеры 23-25 каждого формирователя 13 переходят в нулевое состояние, т.е. на выходах 21 и 22 всех формирователей устанавливаются нулевые значения сигналов. Значения сигналов на выходах 21 и 22 любого формирователя 13 сЛ, и соответственно. Элементы памяти, расположенные в одной строке, т.е. соединенные с одним и тем же формирователем 13, составляют одну ячейку памяти, соответствующую одному слову. Таким образом, после посылки сигнала Сброс на все формирователи 13 все ячейки памяти находятся в состоянии Свободно. Режим записи. Запись производится только в ячейки памяти, находящиеся в состоянии Свободно. Блок 3 управления выбирает одну из этих ячеек памяти и вырабатывает сигнал по соответствующей шине 8 разрешения записи. Одновременно основная информация и признаки выдаются из входного регистра 1 на соответствующие шины 10 опроса-записи. В результате основная информация и признаки записываются в выбранную ячейку памяти. Сигнал с шины 8 разрешения записи поступает также на вход 18 формирователя 13 и устанавливает триггер 25 в единичное состояние. На выходах формирователя формируется сигнал (1,0), означающий, что ячейка памяЗанятоти находится в состоянии В режиме записи из блока 3 управления на входы 20 всех формирователей 13 подается нулевой сигнал для того, чтобы предотвратить установку в единичное состояние триггеров 23 и 24 сигналами, которые могут появиться на шинах 12. Основная информация и признаки записываются в другие ячейки памяти аналогично. Таким образом, все ячейки памяти, в которые осуществлена запись, переходят в состояние Занято . Режим поиска. Пусть множество признаков опроса содержит К признаков. Для поиска всех слов АЗУ с первым и вторым признаками, одновременно принадлежащими множеству признаков опроса, необходимо осуществить К опросов. При каждом опросе содержимое всех элементов 5 и 6 памяти сравнивается с соответствующим очередным признаком опроса, выдаваемым из входного регистра 1 на шины 10 опросазаписи, соединенные с элементс1ми 5 и 6 памяти. Одновременно из блока 3 управления подается единичный сигнал на входы 20 всех формирователей 13. В результате сравнения на некоторых шинах 12 появляются единичные сигналы, которые поступают на соответствующие входы формирователей 13. Если формирователь 13 индицирует Занято и на его входе состояние 14 или 15 появляется единичный сигнал, то триггер 23 или 24 этого формирователя устанавливается в единичное состояние. Те формирователи 13, триггеры 23 и 24 которых в результ те опросов устанавливаются одновременно в единичное состояние, форми руют на выходах 22 единичный сигнал т.е. на выходах этих формирователей устанавливается сигнгш (1,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 и через элемент ИЛИ 29 на нулевые входы триггеров 23 и 24. Это приводит к формированию на выходе формирователя сигнала (0,0), т.е. ячейка устанавливается в состояние Свободно. Таким образом, все ячейки, содержа щие одинаковый ассоциативный признак в элементах 7, переводятся в состояние Свободно при выдаче этого признака из входного регистра на шины 10 опроса-записи, соединенные с элементами 7 памяти.Состояние остальных ячеек при этом не изменяется. Предложенное ассоциативное запоминающее устройство имеет следующие преимущества по сравнению с прототипом: обеспечивается возможность перевода в состояние Свободно произвольной группы ячеек памяти, содержащих одинаковый ассоциативный признак, без изменения состояний остальных ячеек памяти, причем это действие осуществляется за время одного опроса АЗУ, что повышает быстродействие АЗУ; возможна замена некоторых массивов информации без перезаписи всех остальных путем перевода всех ячеек, занимаемых данным массивом, в состояние Свободно и последуклцей записи нового массива в любые свободные ячейки.

llf15

21 20

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

П 16 19 Г8 Фиг.2