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

Изобретение относится к запоминаюишм устройствам. Известно ассоциативное запоминающее устройство (АЗУ) содержащее $Р1ейки памяти основной информации, ячейки памяти ассоциативных признаков, регистр опроса,схемы сравнения ассоциативных признаков с признаком опроса, индикатор совпадения l. Недостатком этого устройства является невысокое быстродействие при поиске информации, у которой совпадают одновременно два признака с любыми из признаков из множества признаков опрос Наиболее близким по технической сущ ности к предлагаемому устройству является АЗУ, содержащее входной блок, выходной блок, блок управления, ячейки памяти основной информации и ассоциативных признаков, шины опроса-записи, шины считывания, шины совпадения, шины разрешения записи и шины разрешения считывания, первые входы ячеек памяти соединены с соответствующими щинами опроса-оаписи вторые - с шинами разрешения считывания, третьи - с шинами разрешения записи, первые выходы ячеек памяти подключены к соответствующим шинам считывания, а вторые - к шинам совпадения, щины опроса-з иси соединены с соответствующими выходами входного блока, щины считывания - с соответствующими входами выходного блока, шины рагфешения записи и шины раз.решения считывания - с соответствующими выходами блока управления, а шины совпадения - с соответствующими входами блока управления 2. Недостатком этого АЗУ является невысокое быстродействие при поиске информшши, у которой должны совпадать одновременно два признака с любыми из IK () признаков из некоторого множества признаков опроса. При решении этой задачи на данном АЗУ требуется выделить в каждом слове ячеек памяти два бита для запоминания результатов шроса нежного признака отдельно. Затем 7 необходимо выполнить 2 К микрокоманд опроса и 2 К ми фокоманд записи, т.е. всего 4 К микрокоманд опроса-записи. Таким образом, данное АЗУ не позволяет найти необходимую информацию за К опросов. Цель изобретения - увеличение быстро действия АЗУ при поиске информации, у которой должны совпадать одновременно два признака с любым иа К (К 1) признаков из некоторого множества признаков опроса и осуществление этого поиска за К опросов. Поставленная цель достигается тем, что в АЗУ, содержащее входной и выходной регистры, блок управления, накопитель, состоящий из адресных и ассоциативных элементов памяти, причем первые входы элементов памяти подключены к соответствующим щинам опроса-записи, которые соединены с выходами входного регистра, вторые входы - с щинами разрещения считывания, третьи - с щинами разрешения записи, выходы адресных и первые выходы ассоциативных элементов памяти подключены к соответствующим щинам считывания, соединенным со входами выходного регистра, вторые выходы ассоциативных элементов памяти подключены к соответствующим шинам совпадения, шины разрешения считывания и записи подключены к одним из выходов блока управления, введены формирователи сигналов состояния ячеек памяти, и вторые входы которых соединены с соответствующими щинами совпадения, тре-тьи входы - с шинами разрешения считывания, четвертые входы - с шинами разрешения записи, а пятые и шестые с щ)угими выходами блока управления, первые и вторые выходы формирователей сигаалов состояния ячеек памяти подклю чены к соответствующим входам блока управления. При этом формирователь сигналов состояния ячеек памяти целесообразно выполнить содержащим триггеры и элеМеигг И и ИЛИ, гричем выходы первого и второго элеме1ггов И подключены к единичным входам первого и второго триггеров нулевые входы которых соединены с выходами элемента ИЛИ, а выходы - со входами третьего элемента И, выход тре тьего триггера подключен кодним.из вхо дов первого и второго элементов И и пе вому выходу формирователя «сигналов состояния ячеек памяти, второй выход которого соединен с выходом третьего элемента И, а входы подключены к другим 0 входам первого и второго элементов И и входам элемента ИЛИ и третьего триггера. На фиг. 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 подключены к соответ1С В1гющим входам блока 3 управления. Формирователь 7 содержит (см. фиг. ; 1Гёрвь1й 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 обозначаем парой (х, Xj), где X., X, - значения сигналов на выходах 14 и ISt При описании работы АЗУ считаем, что элементы памяти, расположенные в одной строке т.е. соединенные с од1шм и тем же формирователем 7, составляют одну ячейку памяти, соответствующую одному слову. Таким образом, после посылки сигнала Сброс на все формирователи 7 н их выходах установятся сигналы, равные (О, О), означающие, что все ячейки памяти находятся в состоянии Свободной Режим записи. Запись производится только в ячейки памяти, находящиеся в состоянии Свободно. Блок 3 управления выбирает одну из этих ячеек памяти и вырабатывает сигнал по соответствующей шине 1 разрешения записи. Одновременно основн информация и признаки выдаются из входного регистра 1 на соответствующие шины 18 опроса-записи, В результате . основная информация и признаки записываются в выбранную ячейку памяти. Сиг нал с, шины 16 разрешения записи поступает также на вход 11 формирювателя 7 и устанавливает триггер 21 в единичное состояние. На выходах формирователя формируется сигнал (1, О), означающий , что ячейка памяти находится в состоянии Занято. В режиме записи из блока 3 управления на входы 13 всех формирователей 7 подается нулевой сигнал, для того, чтобы предотвратить установку в единичное состояние триггеров 2.2. и 23 сигналами, которые могут появиться- на шинах 2О сов падения. Основная информация и призна- 1СИ записываются в другие ячейки памят аналогично. Таким образом, все ячейки памяти, в которые осуществлена запись, переходят в состояние Занято. Режим поиска. Пусть множество признаков опроса содержит К признаков. Для поиска всех слов ЗУ с первым и вторым признаками, сдновро ivieHHo хфинадлежащими множеству признаjcoB опроса, необходимо осуществить К опросов. При каждом опросе содержимое всехэле ментов 5 и 6 памяти сравнивается с соответствующим очередным 1физнаком опроса, вьщаваемым из входного регистра 1 на шины 18 опроса-записи, соединенные с элементами 5 и 6 памяти. Одновременно из блока управления 3 подается единичный сигнал на входы 13 всех формирователей 7. В результате сравнения на некоторых шинах 2О совпадения появляютчгя единичные сигналы, которые поступают на соответствующие входы формирователей 7. Если формирователь 7 И1щпиирует состояние Занято 3О6 и на его входе 8 или 9 поя15ляется еди-шгчный сигнал, то триггер 22 или 23 этого формирователя устанавливается в единичное состояние. Те формирователи 7, триггеры 22 и 23 которых в результате опросов устанавлршаются одновременно в единичное состояние, формируют на выходах 15 единичный сигнал, т.е. на выходах этих формирователей устанавливается сигнал (1, 1), означающий, что да1$ная ячейка памяти находится в состоянии Готово. После К опросов в такое состояние установятся все искомые ячейки память. Режим считывания. Считывание осуществляется только из ячеек памяти в состоянии Тотово. Для этого на ячейку пак-шти подается сигнал по шине 17 разрешения считывания. Считываемая информация принимается выходным регистром 2. Одновременно сигнал с шины разрешения считывания поступает на вход 10 соответствующего формирователя 7 и через элемент ИЛИ , 27 на нулевые входы триггеров 22 и 23. Это приводит к формированию на выходе 15 формирователя 7 нулевого сигнала, т.е. ячейка памяти после считывания информиции переходит в состояние Занято и может быть вновь опрошена при следующем поиске информации. Описанное АЗУ имеет следующие новые положительные свойства; поиск слов с первым и Вторым признаками, одновременно принадлежащими множеству из К признаков, осуществляется эа К опросов; в любой момент времени работы АЗУ известно, какие $иейки памяти находятся в состоянии Свободно и поэтому запись в Ш1Х новой информации и признаков может осуществляться без первоначального поиска свободных ячеек памяти, а значит нет необходимости в специальном признаке, помечающем свободные ячейки памяти. Формула изобретения 1. Ассоциативное запоминающее устройство, содержащее входной и выходной регистры, блок управления, накопиель, состоящий КЗ адресных и ассоциаивных элементов памяти, причем первые ходы элементов памяти подключены к сответствующим шинам опроса-записи, коорые соединены с выходами входного реистра, вторые входы - с шинами разрешеия считывания, третьи - с шинами разре77шения записи, выходы адресных и первые &ЫХОДЫ ассоциативных элементов памяти подключены к соответствующим шинам считывания, соединенным со входами выходного регистра, вторые выходы асе оциативных элементов памяти подключены к соответствующим щинам совпадения, шины разрешения считывания и записи подключены к одним из выходов блока управления, отличающееся тем, что, с целью увеличения быстродействия устройства, оно содержит формировате ли сигналов состояния ячеек памяти, первые вторые входы которых соединены с соответствующими щинами совпадения, третьи входы - с шинами разрешения считывания, четвертые входы - с шинами разрешения записи, а пятые и шестые с другими выходами блока управления, первые и вторые выходы формирователей сигналов состояния ячеек памяти подклкн чены к соответствующим входам блока управления. 2. Устройство по п. 1, отличаюе е с я тем, что формирователь сих 0 налов состояния ячеек памяти содержит триггеры и элементы И и ИЛИ, причем выходы первого и второго элементов И подключены к единичным входам первого и второго триггеров, нулевые входы которых соединены с выходом элемента ИЛИ, а выходы - со входами третьего элемента И, выход третьего триггера подключен к одним из входов первого и второго элементов И и первому выходу формирователя сигналов состояния ячеек памяти, второй выход которого соединен с выходом третьего элемента И, а входы подключены к другим входам первого и второго элементов И и входам элемента ИЛИ и третьего триггера. Источники информации, принятые во внимание при экспертизе 1. Майоров С. А., Новиков Г. И. Принципы организации цифровых машин. Л., Машиностроение , 1974, с. 393, рис. Ю. 20 2. Однородные микроэлектронные ассоциативные процессоры. Подред. И. В. Прангшивили, М. Советское радио , 1973, с. 11, рис. 1. 1 (прототип).

Ut. 1

1012 li

Риг.г