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

СОЮЗ СОВЕТСКИХСОЦИАЛИСТИЧЕСКИХРЕСПУБЛИК 1 С 15 0 Й ОПИ Е ИЗОБРЕТЕН т т ктронныеод ред.етское ОСУДАРСТВЕККЫЙ КОМИТЕТ СС ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЬ ВТОРСНОМУСВИДЕТЕЛЬСТВ(71) Харьковский ордена ТрудовогоКрасного Знамени институт радиоэлроники им. акад. М.К. Янгеля(56) 1. Однородные микроэлеассоциативные процессоры. ПИ.В. Прангишвили. М., Соврадиоф, 1973, с. 11. 2, Авторское свидетельство ССС 9 773730 кл. 6 11 С 29/00, 1979 (прототип).(54)(57) 1. АССОЦИАТИВНОЕ ЗАПОМИНАЮЩЕЕ УСТРОЙСТВО, содержащее входной и выходной регистры, блок управления, накопитель, состоящий из адресных и основных ассоциативных элементов памяти, формирователи сигналов состояния ячеек памяти, причем первые входы элементов памяти подключены к соответствующим шинам опроса- записи, которые соединены с выходами входного регистра, вторые входы - с шинами разрешения считывания, третьи с шинами разрешения записи, выходы адресных и первые выходы основных ассоциативных элементов памяти подключены к соответствующим шинам считывания, соединенным с входами выходного регистра, вторые выходы ассоциативных элементов памяти подключены к соответствующим шинам считывания сигналов совпадения, шины. разрешения считывания и записи подключены к одним из выходов блока управления и первым и вторым входам формирователей сигналов состояния ячеек памяти, входы которых с третьих по шестые соединены с шинами считывания сигналов совпадения и другими выхода,Я 01080213 А ми блока управления, входы которогоподключены к выходам формирователейсигналов состояния ячеек памяти, ол и ч а ю щ е е с я тем, что, сцелью увеличения быстродействия, внего введены дополнительные ассоциативные элементы памяти, причем первые входы дополнительных ассоциативных элементов памяти подключены кодному из выходов входного регистра,вторые входы - к шинам разрешениясчитывания, третьи - к шинам разрешения записи, первые выходы дополнительных ассоциативных элементов памя.ти соединены с одним из входов выходного регистра, вторые выходы - содним из входов соответствующего формирователя сигналов состоянияячеек памяти.2. Устройство по п. 1, о т л и"ч а ю щ е е с я тем, что каждый формирователь сигналов состоянияячеек памяти содержит триггеры и эле менты И и ИЛИ, причем выходы первого и второго элементов И подключены к единичным входам первого и второго триггеров, нулевые входы которых соединены с выходом первого элемента ИЛИ, а выходы - с входами третьего элемента И, выход третьего триггера подключен к одним из входов первого и второго элементов И и является первым выходом формирователя сигналов состояния ячеек памяти, вторым выходом которого является выходтретьего элемента И, выход второго элемента ИЛИ подключен к одним из входов первого элемента ИЛИ и третье го триггера, другие входы которых, а также другие входы первого и второ го элементов И являются входами формирователя сигналов состояния ячеек памяти.Изобретение относится к вычислительной технике и может быть использовано в устройствах для поиска инФормации.Известно ассоциативное запоминающее устройство, содержащее входной и выходной блоки, блок управления, ячейки памяти основной информации и ассоциативных признакон, связанные с шинами опроса-записи, считывания, совпадения, разрешения записи и считывания 11.Недостатком этого устройства является невысокое быстродействие.Наиболее близким к предложенному по техническому решению является ас социативное запоминающее устройство (АЗУ), содержащее входной и выходной регистры, блок управления, адресные элементы памяти, ассоциативные элементы памяти, служащие для хранения 20 первых и вторых признаков, формирователи сигналов состояния ячеек памяти, шины разрешения записи, разрешения считывания, опроса - записи, считывания, совпадения, причем первые 5 входы элементов памяти подключены к соответствующим шинам опроса-записи, которые соединены с выходами входного регистра, вторые входы - с шинами разрешения считывания, третьи - с шинами разрешения записи, выходы адресных и первые выходы основных ассоциативных элементов памяти подключены к соответствующим шинам считывания, соединенным с входами выходного регистра, вторые выходы ассоциативных элементов памяти подключены к соответствующим шинам совпадения, шины разрешения считывания и записи подключены к одним из выходов блока управления, первые и вторые входы 40 формирователей сигналов состояния ячеек памяти соединены с.соответствующими шинами совпадения, третьи входы - с шинами разрешения считывания, четвертые входы - с шинами Раз решения записи, а пятые и шестые - с другими выходами блока управления, первые и вторые выходы формирователей сигналов состояния ячеек памяти подключены к соответствующим входам блока управления, причем каждый формирователь сигналов состояния ячеек памяти содержит триггеры, элементы И и ИЛИ, причем выходы первого и второго элементов И подключены к единичным входам первого и второго триггеров нулевые входы которых соединены с выходом элемента ИЛИ, а выходы - с входами третьего элемента И, выход третьего триггера подклю- чен к одним из входов первого и 60 второго элементов И и первому выходу формирователя сигналов состояния ячеек памяти, второй выход которого соединен с выходом третьего элемента И, а входы подключены к другим вхо дам первого и второго элементов И, к нходам элемента ИЛИ и третьего триггера 23.Однако это устройство характеризуется невысоким быстродействием в режиме перевода ячеек памяти н состояние Свободно, а также ограниченными функциональными возможностями, так как в нем невозможен перевод в состояние Свободно произвольной группы ячеек, содержащих одинаковый ассоциативный признак, без изменения состояний остальных ячеек памяти.Цель изобретения - повышение быстродействия и расширение функциональных возможностей АЗУ путем обеспечения возможности перевода н состояние Свободно произвольной группы ячеек памяти, содержащих одинаковый ассоциативный признак, без изменения состояний остальных ячеек памяти.Поставленная цель достигается тем, что в ассоциативное запоминающее устройство, содержащее входной и выходной регистры, блок управления, накопитель, состоящий из адресных и основных ассоциативных элементов памяти, Формирователи сигналов состояния ячеек памяти, причем первые входы элементов памяти подключены к соответствующим шинам опроса-записи, которые соединены с выходами входного регистра, вторые входы - с шинами разрешения. считывания, третьи - с шинами разрешения записи, выходы адресных и первые выходы ассоциативных элементов памяти подключены к соответстнующим шинам считывания, соединенным с входами выходного регистра, вторые выходы основных ассоциативных элементов памяти подключены к соответствующим шинам считывания сигналов совпадения, шины разрешения считывания и записи подключены к одним из выходов блока управления и первым и вторым входам Формирователей сигналон состояния ячеек памяти, входы которых с третьих по шестые соединены с шинами считывания сигналов совпадения и другими выходами блока управления, входы которого подключены к выходам Формирователей сигналов состояния ячеек памяти, введены дополнительные ассоциативные элементы памяти, причем первые входы дополнительных ассоциативных элементов памяти подключены к одному из выходов входного регистра, вторые входы - к шинам разрешения считывания, третьи - к шинам разрешения записи, первые выходы дополнительных ассоциативных элементов памяти соединены с одними из входон выходного регистра, вторые выходы - с одним из, входов соответстнующего формирователя сигналов состояния ячеек памяти.Каждый Формирователь сигналовсостояния ячеек памяти содержит триггеры и элементы И и ИЛИ, причем выходы первого и второго элементов Иподключены к единичным входам первого и второго триггеров, нулевые входы которых соединены с выходом первого элемента ИЛИ, а выходы - с входами третьего элемента И, выходтретьего триггера подключен к однимиз входов первого и второго элементов И и является первым выходом формирователя сигналов состояния ячеекпамяти, вторым выходом которого является выход третьего элемента И, выход второго элемента ИЛИ подключен 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, второй 4027 и третий 28 элементы И, первый29 и второй 30 элементы ИЛИ.Первые 14, вторые 15 и третьи 16входы Формирователей 13 соединеныс соответствующими шинами 12 совпаде ния, четвертые 17 - с шинами 9 разрешения считывания, пятые 18 - с шинами 8 разрешения записи, шестые19 и седьмые 20 - с соответствующимивыходами блока 3 управления, апервые 21 и вторые 22 выходы формирователей 13 подключены к соответствующим входам блока 3 управления.АЗУ работает следующим образом.Из блока 3 управления на входы19 всех формирователей 13 выдаетсясигнал Сброс 1. В результате триггеры 23-25 каждого формирователя13 переходят в нулевое состояние,т.е. на выходах 21 и 22 всех формирователей устанавливаются нулевыезначения сигналовЗначения сигналов на выходах 21 и 22 любого формирователя 13 сР иГ соответственно. 65 Элементы памяти, расположенные в одной строке, т.е. соединенные с одним и тем же формирователем 13, составляют одну ячейку памяти, соответствующую одному слову.Таким образом, после посылки сигнала Сброс на все формирователи 13 все ячейки памяти находятся в состоянии Свободно.Режим записи, Запись производится только в ячейки памяти, находящиеся в состоянии Свободно, Блок 3 управления выбирает одну из этих ячеек памяти и вырабатывает сигнал по соответствующей шине 8 разрешения записи, Одновременно основная информация и признаки выдаются из входного регистра 1 на соответствующие шины 10 опроса-записи. В результате основная информация и признаки записываются в выбранную ячейку памяти. Сигнал с шины 8 разрешения записи поступает также на вход 18 Формирователя 13 и устанавливает триггер 25 в единичное состояние. На выходах формирователя формируется сигнал (1,0), означающий, что ячейка памяти находится в состоянии Занято, В режиме записи иэ блока 3 управления на входы 20 всех формирователей 13 подается нулевой сигнал для того, чтобы предотвратить установку в единичное состояние триггеров 23 и 24 сигналами, которые могут появиться на шинах 12.Основная информация и признаки записываются в другие ячейки памяти аналогично, Таким образом, все ячейки памяти, в которые. осуществлена запись, переходят в состояние Занято.Режим поиска. Пусть множество признаков опроса содержит К признаков. Для поиска всех слов АЗУ с первым и вторым признаками, одновременно принадлежащими множеству признаков опроса, необходимо осуществить К опросов. При каждом опросе содержимое всех элементов 5 и 6 памяти сравнивается с соответствующим очередным признаком опроса, выдаваемым из входного регистра 1 на шины 10 опроса- записи, соединенные с .элементами 5 и 6 памяти, Одновременно из блока 3 управления подается единичный сигнал на входы 20 всех Формирователей 13. В результате сравнения на некоторых шинах 12 появляются единичные сигналы, которые поступают на соответствующие входы формирователей 13. Если формирователь 13 индицирует состояние Занято и на его входе 14 или 15 появляется единичный сигнал, то триггер 23 или 24 этого формирователя устанавливается в единичное состояние. Те формирователи 13, триггеры 23 и 24 которых в результ - те опросов устанавливаются одновре 10 В 0213менно в единичное состояние, Форми-руют на выходах 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 и через эле 10 мент ИЛИ 29 на нулевые входы триггеров 23 и 24. Это приводит к Формированию на выходе Формирователя сигнала (О,О), т.е. ячейка устанавливается в состояние фСвободно.15 Таким образом, все ячейки, содержащие одинаковый ассоциативный признак в элементах 7, переводятся всостояние Свободно при выдачеэтого признака из входного регистрана шины 10 опроса-записи, соединенные с элементами 7 памяти,Состояниеостальных ячеек при этом не изменяется,Предложенное ассоциативное запо 25 минающее устройство имеет следующиепреимущества по сравнению с прототипом: обеспечивается возможностьперевода в состояние гСвободнопроизвольной группы ячеек памяти,содержащих одинаковый ассоциативныйпризнак, без изменения состоянийостальных ячеек памяти, причем этодействие осуществляется за времяодного опроса АЗУ, что повышаетбыстродействие АЗУ; возможна заменанекоторых массивов информации безперезаписи всех остальных путем перевода всех ячеек, занимаемых данныммассивом, в состояние фСвободнои последующей записи нового массива40 в любые свободные ячейки.10 й 0213 Составитель В. РудаковТехред М.Кузьма Корректор С. Шекм актор 3. Веселовская аказ 1366/52 Тираж 575 ВНИИПИ Государственного ко по делам изобретений и о 3035, Москва, Ж, Раушская