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

ОП ИСАНИЕИЗОБРЕТЕ Н ИЯК АВТОРСКОМУ СВИДЕТЕЛЬСТВУ Союз СоветскикСоциалистическикРеспублик(22) Заявлено 04.04,79 (21) 2745595/18-24 с присоединением заявки РЙ Гесударстееннмй камитет(23) Приоритет 6 11 С 15/00 Опубликовано 23.10.80 Бюллетень Ле 39 по делам изебретений н открытий(53) УДК ,327 (088,8) Дата опубликования описания 02,11.80(72) Авторы изобретения А. Г. Мурашко и С. К. Колубай Харьковский институт радиоэлектроники(54) АССОЦИАТИВНОЕ ЗАПОМИНАКИЦЕЕ УСТРОЙСТВО Изобретение относится к запоминающим устройствам,Известно ассоциативное запоминающее устройство (АЗУ) содержащее ячейки памяти основной информации, ячейкипамяти ассоциативных признаков, регистропроса, схемы сравнения ассоциативныхпризнаков с признаком опроса, индикаторсовпадения (1.Недостатком этого устройства является невысокое быстродействие при поиске информации, у которой совпадаютодновременно два признака с любыми иэпризнаков из множества признаков опроса,Наиболее близким по технической сущности к предлагаемому устройству является АЗУ, содержащее входной блок,выходной блок, блок управления, ячейкипамяти основной информации и ассоциативных признаков, шины опроса-записи,шины считывания, шины совпадения, шиныразрешения записи и шины разрешениясчитывания, причем первые входы ячеекпамяти соединены с соответствующими шинами опроса-записи вторые - с шинами разрешения считывания, третьи - с шинами разрешения записи, первые выходы ячеек памяти подключены к соответствующим шинам считывания, а вторые - к шинам совпадения, шины опроса-записи соединены с соответствующими выходами входного блока, шины считывания - с соответствующими входами выходного блока, шины разрешения записи и шины разрешения считывания - с соответствующими выходами блока управления, а шины совпадения - с соответствующими входами блока управления 2.Недостатком этого АЗУ является невысокое быстродействие при поиске информиции, у которой должны совпадать одновременно два признака с любыми из 1 К (Кр 1) . признаков из некоторого множества признаков опроса. При решении этой задачи на данном АЗУ требуется выделить в каждом слове ячеек памяти два бита для запоминания результатов опроса каждого признака отдельно. Затем3 7737 необходимо выполнить 2 К микрокоманд опроса и 2 К мил.рокоманд записи, т,е.всего 4 К микрокоманд опроса-записи.Таким образом, данное АЗУ не позволяет найти необходимую информацию за К опросов.5Цель изобретения - увеличение быстродействия АЗУ при поиске информации, у которой должны совпадать одновременно два признака с любым из К (К1) признаков из некоторого множества признаков опроса и осуществление этого поиска за К опросов.Поставленная цель достигается тем, что в АЗУ, содержащее входной и выходной регистры, блок управления, накопитель, состоящий из адресных и ассоциативных элементов памяти, причем первые входы элементов памяти подключены к соответствующим шинам опроса-записи, которые соединены с выходами входного регистра, вторые входы - с шинами разрешения считывания, третьи - с шинами разрешения записи, выходы адресных и первые выходы ассоциативных элементов памяти подключены к соответствующим шинам считывания, соединенным со входами выходного регистра, вторые выходы ассоциативных элементов памяти подключены к соответствующим шинам совпадения, шины разрешения считывания и записи подключены к одним из выходов блока управления, введены формирователи, сигналов состояния ячеек памяти, первые и вторые входы которых соединены с соответствующими шинами совпадения, тре,тьи входы - с шинами разрешения считывания, четвертые входы - с шинами разрешения записи, а пятые и шестые - с другими выходами блока управления, 40 первые и вторые выходы формирователей сигналов состояния ячеек памяти подклю чены к соответствующим входам блока управления.При этом формирователь сигналов со стояния ячеек памяти целесообразно выполнить содержащим триггеры и элементь 1 И и ИЛИ, причем выходы первого и второго элементов И подключены к единичным входам первого и второго триггеров,Р 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 наих выходах установятся сигналы, равные (О, 0), означающие, что все ячейкипамяти находятся в состоянии Свободно.Режим записи.Запись производится только в ячейки памяти, находящиеся в состоянии"Свободно" Блок 3 управления выбираетодну из этих ячеек памяти и вырабатывает сигнал по соответствующей шине 16разрешения записи. Одновременно основная 15информация и признаки выдаются из входного регистра 1 на соответствующиешины 18 опроса-записи, В результате .основная информация и признаки записываются в выбранную ячейку памяти. Сигнал с, шины 16 разрешения записи поступает также на вход 11 формирователя 7 и устанавливает триггер 21 вединичное состояние. На выходах формирователя формируется сигнал (1, О),означающий, что ячейка памяти находитсЯ в состоЯнии Занятоф. В Режимезаписи из блока 3 управления на входы13 всех формирователей 7 подается нулевой сигнал, для того, чтобы предотвратить установку в единичное состояние триггеров 22 и 23 сигналами, которые могут появиться на шинах 20 совпадения. Основная информация и признаки записываются в другие ячейки памятианалогично. Таким образом, все ячейки35памяти, в которые осуществлена запись,переходят в состояние "Занято". 4Пусть множество признаков опроса содержит К признаков. Для поиска всех слов АЗУ с первым и вторым признаками, одновременно принадлежащими множеству призна-ов опроса, необходимо осуществить К опро сов. При каждом опросе содержимое всехэлементов 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. Ассоциативное запоминающее устройство, содержащее входной и выходной регистры, блок управления, накопитель, состоящий из адресных и ассоциативных элементов памяти, причем первые входы элементов памяти подключены к соответствующим шинам опроса-записи, которые соединены с выходами входного регистра, вторые входы - с шинами разрешения считывания, третьи - с шинами разрещения записи, выходы адресных и первыевыходы ассоциативных элементов памятиподключены к соответствующим шинамсчитывания, соединенным со входами вы.ходного регистра, вторые выходы ассоциативных элементов памяти подключенык соответствующим шинам совпадения,шины разрешения считывания и записиподключены к одним из выходов блокауправления, отличающеесятем, что, с целью увеличения быстродействия устройства, оно содержит формирователи сигналов состояния ячеек памяти, первые ивторые входы которых соединены с соответствующими шинами совпадения, третьи входы - с шинами разрешения считывания, четвертые входы - с шинамиразрешения записи, а пятые й шестые -с другими выходами блока управления,первые и вторые выходы формирователейсигналов состояния ячеек памяти подключены к соответствующим входам блокауправления. 2.Устройствопоп.1, о т л и ч а ю -щ е е с я тем, что формирователь сигпалов состояния ячеек памяти содержиттриггеры и элементы И и ИЛИ, причемвыходы первого и второго элементов Иподключены к единичным входам первогои второго триггеров, нулевые входы которых соединены с выходом элементаИЛИ, а выходы - со входами третьегоэлемента И, выход третьего триггера под.ключен к одним из входов первого и вто 1 О рого элементов И и первому выходу формирователя сигналов состояния ячеек памяти, второй выход которого соединен свыходом третьего элемента И, а входыподключены к другим входам первого и15 второго элементов И и входам элементаИЛИ и третьего триггераИсточники информации,принятые во внимание при экспертизе1. Майоров С. А., Новиков Г. И. Прини ципы организации цифровых машин, Л.,Машиностроение", 1974, с. 393,рис. 10,202, Спнородные микроэлектронные ас-социативные процессоры. Под ред.25 И, В. Прангишвили, М. "Советское радио",1973,. с. 11, рис. 1. 1 (прототип).773730 42 Н оставит ехредТ В. Рудаковд Н. Бабурка Коррекор М, Вигул едактор Г. Волк Подписноекомитета СССРи открытийРаушская наб., д. 4/5 517/69 Тираж 662 ВНИИПИ Государственного поф делам изобретений 113035, Москва, Ж