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

0 Я)5 О 11 АТЕНТНОЕ ГОСУДАРСТВЕННОЕВЕДОМСТВО СССР:ЬгДЩТЕЯА ЗОБРЕТЕН ПИСАН ВТОРСКОМУ СВИДЕТЕЛЬСТВ Ю 1 1 14 21) 4878858/24(71) Московский энергетический институт (72) И,В,Огнев и В,ВБорисов(54) АССОЦИАТИВНОЕ ЗАПОМИНАЮЩЕЕ УстройСТВО(57) Изобретение относится к вычислительной технике, в частности к запоминающим устройствам, и может быть использовано в специализированных системах храненйя и цифровой обработки информации, в сйстемах решения информационно-логических Изобретение относится к вычислительной технике, в частности, к эапоминающим устройствам, и может быть использовано в специализированных системах хранения и цифровой обработки информации, всистемах решения информационно-логических задач, задач поиска и сортировки данйох, в устройствах цифровой обработки сигналов в реальном масштабе времениИзвестно ассоциативное запоминающее устройство последовательное по сло вам и параллельное по разрядам, содержащее сдвиговые регистры, логйку се- лектора записи, регистры считыванйя аргументы поиска и конечного адреса, счетчик адреса, генератор тактовых импульсов, первый и второй компараторы (1). Й 2 1785039 А 21задач, задач поиска и сортировки данных, в устройствах цифровой обработки сигналов в реальном масштабе времени. Целью изобретения является расширение области применения устройства за счет обеспечения возможности одновременного осуществления ассоциативного поиска и фиксации количества неСовпадеййй аргумента поиска как с отдельной выделенной строкой ассоциативного накопителя, так и с конъюнкцией выделенных строк. Ассоциативное запоминающее устройство содержит накопитель; в состав которого входят элементы памяти со входами с первого по пятый и с первым и вторым выходами, блок регистров опроса и маскирования данных, дешифратор адреса, блок маскирования, первый и второй регистры фиксации реакций, анализатор многократного совпадения, шифратор. 4 ил. Недостатком этого устройства является йевозможность фиксации количества несовпадений аргумента поиска с конъюнкцией выделенных строк,Наиболее близким техническим решением к заявляемому устройству является ассоциативное запоминающее устройство, содержащее ассоциативный накопитель, блок регистров опроса и маскирования данных, дешифратор адреса, регистр фиксации реакции, анализатор многократного совпадения, шифратор (2).Недостаток этого устройства заключается в невозможности одновременного осуществления ассоциативного поиска и фиксации количества несовпадений аргумента поиска как с отдельной выделеннойстрокой ассоциативного накопителя, так и с конъюнкцией выделенных строк.Целью изобретения является расширение области применения устройства за счет обеспечения возможностйодновременного осуществления ассоциативного поиска и фиксации количества несовпадений аргумента поиска как с отдельной выделенной строкой ассоциативного накопителя, так и с конъюнкцйей выделенных строк.Поставленная цель достигается тем, что 10 в ассоциативное запоминающее устройство, содержащее накопитель, блок регистров опроса и маскирования данных, первый и второй регистры фиксации реакций; анализатор многократного совпадения, шифратор, дешифратор адреса, управляющие входы блока региСтров опроса и маскирования данных являются управляющими входами устройства, информационными входами 20 группы которого являются ийформационные входы блока регистров опроса и маскирования данных, выходы с первого по четвертый каждой группы которого подключены соответственно к пятому, четвертому, 25второму и третьему информационным входам элементов памяти соответствующего столбца накопителя, вторые выходы элементов памяти каждого столбца накопителя объединены и подключены к соответствующйм информационным входам второго регистра фиксации реакций, управляющий вход которого является входом чтения устройства, информационными выходами 30 35 группы которого являются информационные выходы второго регистра фиксВ 4 йй реакций, первые выходы элементов памяти каждой строки накопителя объединены и подключены к соответствующим входам 40 первого регистра фиксации реакций, управляющий вход которого является входом чтения устройства, информационные выходы первой группы первого регистра фиксации реакций являются входами-выходами дан 4550 нце выходы анализатора многократного совпадения соединены с соответствующими информационными входами шифратора, выходы которого соедйнены с информационными входами дешифратора и являются адресными входами-выходами устройства,ньсх устройства, информационные выходы второй группы первого регистра фиксации г.реакций соединены с соответствующимивходами данных анализатора многократно.го совпадения, управляющий вход которого соединен с управляющим входом шифратора и является входом задания режима устройства, вйход состояния анализатора многократного совпадения является выходом состояния устройства, информационвходом выборки которого является управляющий вход дешифратора, введен блок маскирования, к информационным входампервой группы которого подключены выходы дешифратора адреса, информационныевходы второй группы блока маскированияявляются входами-выходами данных устройства, управляющим входом которого является управляющий вход блокамаскирования, выходы которого подключены к объединенным первым входам элементов памяти соответствующих строкнакопителя,На фиг, 1 представлена схема ассоциативного запоминающего устройства,На фиг, 2 - схема элемента памяти,На Фиг. 3 - схема блока регистров опроса и маскирования.На фиг, 4- дешифратор и блок маскирования,Устройство (фиг, 1) содержит накопитель 1, в состав которого входят элементыпамяти 2 со входами с первого 3 по пятый 7и с первым 8 и вторым 9 выходами, блок 10регистров опроса и маскирования данных,дешифратор 11 адреса, блок 12 маскированйя, первый 13 и второй 14 регистры фиксации реакций, анализатор 15 многократногосовпадения, шифратор 16.Информационные входы 17 блока 10 регистров опроса и маскирования даннь 1 х служат второй группой информационныхвходов устройства. а выходы с первого пОчетвертый каждой группы выходов подключены соответственно к соединенным междусобой пятым 7, четвертым 6, вторым 4 итретьим 5 входам элементов памяти 2 соответствующего столбца накопителя.Входы дешифратора 11 подключены ксоответствующим адресным входам-выходам 18 устройства, а выходы соединены ссоответствующими входами первой группывходов блока 12 маскирования, ко входамвторой группы входов которого подключенысоответствующие входы-выходы 19 данныхустройства, а выходы подключены соответственно к соединенным между собой первым 3 входамэлементов памяти 2соответствувщих строк накопителя 1.Первые 8 выходы элементов 2 памятисоответствующих строк накопителя соединены между собой и подключены к соответствующим информационным входампервого 13 регистра фиксации реакций, йервая группа информационных выходов которого подключена к соответствующимвходам-выходам 19 данных устройства. авторая группа информационных выходовсоединена с соответствующими входамиданных анализатора 15 многократного соввающими на наличие "некоторого числа" совпадений в результате проведения параллельного ассоциативного поиска в накопи устройства, .-10 Вторые 9 выходы элементов памяти 222 - сигнал записи в накопитель;, 20 23 - сигнал опроса и считывания из йакопителя; элемента 2 памяти, состоящего из триггера 40 Блок 10 регистров опроса и маскирова ния данных (фиг. 3) содержит регистр 40 опроса, регистр 41 маскирования; первую 42 и вторую 43 группы инверторов, первую 44 и вторую 45 группы элементов И.На фиг. 4 показаны связи дешифратора 50 11 адреса и блока 12 маскирования, содержащего регистр 46 и группу элементов ИЛИ 47,В (2) приведен пример реализации.энападения, выход 20 состояния которого слукит выходом состояния устройства, указытеле 1, а информационные выходы присоединены к соответствующим информационным входам шифратора, выходы которого подключены к адресной шине 18 соответствующих столбцов накопителя соединены между собой и подключены к соответствующим информационным входам второго 14 регистра фиксации реакций, выходы которого служат группой 21 информациойных выходов устройства."2 ЯНа устройство подаются следующие управляющие сигналы; 24 - сигнал записи в регистр опроса блока 10;.у.25 - сигнал записи в регистр маскирования блока 10;26 - сигнал сброса в "0" регистров опроса и маскирования блока 10;27 - сигнал записи в регистр блока 12;28 - сигнал сброса в "0" регистра блока 12;29 - сигнал выборки дешифратора 11 адреса;30 - сигнал стробирования отработанной и выборки следующей активной линйи блоком 15, а также выдачи шифратором 16 нэ адресную шину 18 устройства адреса следующей активной линии,Нэ фиг, 2 приведен пример реализации 31 и элементов И-НЕ с первого 32 по шестой 37. На фиг. 2 также представлены не показанные на фиг. 1 ограничительные 38 и39 элементы в виде резисторов. лизатора многократного совпадения Устройство может работать в следующих режимах: запись информации по заданному адресу (груп пе адресов) с маскированием произвольных разрядов; считывание информации по заданному ад 25 30 ресу строки накопителя; считывания битовых срезов данных из накопителя (столбцовое считывание); конъюнктивное считывание строк и столбцов накопителя; параллельный ассоциативный маскируемый поиск с возможностью одновременной фиксации количества несовпадений аргумента поиск как с отдельной выделенной строкой ассоциативного накопителя, так и с конъюнкцией выделенных строк,В режиме записи по заданному адресу с адресной 18 шины устройства на дешифратор 11 адреса поступает код адреса слова, который дешифрируется по сигналу 29,инициируя подачу уровня логическои едийицы на входы 3 элементов памяти 2 соответствующей строки накопителя, Кроме того, дешифрированный адрес слова может подаваться непосредственно с входом-выходом 19 данных устройства и инициировать тот же процесс при записи этого дешифрированного адреса в регистр 46 блока 12 по сигналу 27; Одновременно с этим нэ информационные входы блока 10 регистров опроса и маскирования со входов 17 подается записываемое слово, которое фиксируется в регистр 40 блока по сигналу 24. Затем в регистр 41 этого же блока записывается маска по сигналу 41 (единицы в разрядах регистра маски определяют маскирование соответствующих разрядов слов накопителя). И при подачесигнала 22 записи в накопитель на входы 4 и 5 всех элементов 2 памяти поступит одна из следующих комбинаций сигналов: "10" - код записи единицы, "01" - код записи нуля, "00" - код маскирования записи. И, таким образом, запись осуществляется по выбранному адресу.В случае записи по группе адресов в регистр 46 блока 12 должен быть записан аргумент, в котором единицы соответствуют этим адресам,При считывании информации по заданному адресу строки накопителя перед ини.- циализацией этого режима сигналов 23 во все разряды регистра 40 опроса блока 10 должны быть записаныединицы, а дешифратором 11 адреса или регистром 46 блока 12 активизирована соответствующая строчная адресная линейка (см. предыдущий. режим), И при подаче сигнала 23 на входы 6 и 7 элементов памяти выбранной строки накопителя поступает комбинация "01", и, слово считываемое у выходов 9 элементов памяти этой строки, фиксируется во втором 14 регистре фиксации реакции по заднему фронту этого же 23 сигнала с выдачей результата на группу 21 выходов данных устройства,10 20 ны в те разряды регистра 40 блока 10, кото- ЗОрые соответствуют считываемым столбцам в этом случае после проведения считывания 35 В режиме строчного конюнктивного считывания единицы должны быть записаны в те разряды регистра 46 блока 12, которые соответствуют адресам считываемых строк накопителя, И в этом случае после проведения считывания во второй 14 регистр фиксации реакций запишется слово, каждый разряд которого будет содержать коньюнкцию соответствующих разрядов считываемых строк накопителя.При считывании информации из заданногостолбцового среза перед инициализацией этого режима единица должна быть записана в соответствующий разряд регистра 40 блока 10. При этом остальные разряды должны быть замаскированы соответствующей маской, записанной в регистр 41 этого блока. И при поддаче сигнала 23 на входы 6 и 7 элементов памяти выбранного столбца накопителя поступает комбинация "01", и содержимое столбцового среза, считываемого с выходов 8 элементов памяти этого столбца накопителя, фиксируется в первом 13 регистре фиксации реакции по заднему фронту этОго же столбца 23 с выдачей результата на входы-выхады 19 данных устройства. В режиме столбцового каныонктивногосчитывания единицы должны быть записанакопителя, Остальные же разряды должны быть замаскированы соответствующей маской, записанной в регистр 41 этого блока. И в первый 13 регистр фиксации реакций запишется слово, каждый разряд которого будет содержать коныонкцию соответствующих разрядов считываемых столбцов накопителя,В режиме параллельного ассоциативного маскируемога поиска в регистре 40 блока 10 регистров опроса и маскирования дан ных па сигналу 24 фиксируется аргумент поиска, подаваемый с входов 17. Затем в регистр 41 маскирования этого блока со входов 17 записывается маска по сигналу 25. И при подачесигнала 23 на входы 6 и 7 всех . элементов памяти поступает одна из следующих комбинаций сигналов: "01" - сравнение с единицей, "10" - сравнение с нулем, "00" - маскирование поиска. Если маскируемый аргумент поиска совпал с какай-то строкой накопителя, та шина, соединяющая выходы 8 элементов памяти соответствующей строки сохранит уровень логической единицы, Если же хотя бы в одном разряде этой строки произошло несовпадение, то выход 8 соответствующего элемента памяти обнулится, абнулится, следовательно, и са 40 45 ответствующая шина, что укажет на наличие несовпадения. Результат ассоциативного поиска фиксируется в первом 13 регистре фиксации реакции по заднему фронту сигнала 23. Анализатор 15 многократного совпадения служит для приоритетной выборки одной из активных линий первого 13 регистра фиксации реакций, При этом наивысшим приоритетом из аргументов обладает аргумент с нулевым адресом.Адрес активной линии, выбранной анализатором 15 многократного совпадения, кодируется шифратором 16 и выдается на адресные входы-выходы 18 устройства по сигналу ЗО, Повторной подачей этого сигнала осуществляется стробирование отработанной и инициализация следующей активной линии анализатором 15 многократного совпадения.Одновременно с осуществлением вышерассмотренного режима ассоциативного поиска можно провести фиксацио числа несовпадений маскированного аргумента поиска с выделенной дешифратором 11 или регистром 46 блока 12 строкой ассоциативного накопителя. При этом на выходах 9 элементов памяти этой строки накопителя установится либо признак совпадения (сохранится уровень лог, "1"), либо признак несовпадения(уровень лог. "О"), И результат запишется во второй 14 регистр фиксации реакций,В этом режиме можетбыть также осуществлена фиксация во втором 14 регистре фиксации реакций числа несовпадений аргумента поиска с коныюнкцией строк, выделенных регистром 46 блока 12,Таким образом, достигается цель расширения области применения устройства за счет обеспечения возможности одновременного осуществления ассоциативного поиска и фиксации количества несовпадений аргумента поиска как с отдельной строкой ассоциативного накопителя, так и с конъюнкцией выделенных строк.Формула изобретения Ассоциативное запоминающее устройство, содержащее накопитель, блок регистров опроса и маскирования данных, первый и второй регистры фиксации реакций, анализатор многократного совпадения, шифратор, дешифратор адреса, управляющие входы блока регистров опроса и маскирования данных являются управляющими входами устройства, информационными входами группы которого являются информационные входы блока регистров опроса и маскирования данных, выходы с первого по четвертый каждой группы которого подключены соответственно к пятому, четвертому,второму и третьему информационным входам элементов памяти соответствующего столбца накопителя, вторые выходы элементов памяти каждого столбца накопителя объединены и подключены к 5 соответствующим информационнйм входам второго регистра фиксации реакЦий, управляющий вход которого является входом чтения устройства, информационными выходами группы которого являются 10 информационные выходы второго регистра фиксации реакций, первые выходы элементов памяти каждой строки накопителя объединены и подключены к соответствующим входам первого регистра фиксации 15 реакций, управляющий вход которого является входом чтения устройства, информационные выходы первой группы первого регистра фиксации реакций являются входами-выходами данных устройст ва, информационные выходы второй группы первого регистра фиксации реакций соединены с соответствующими входами данных анализатора многократного совпадения, управляющий вход которого 25 соединен с управляющим входом шифратора и является входом задания режима устройства. выход состояния анализатора многократного совпадения является выходом состояния устройства, информационные выходы анализатора многократного совпадения соединены с соответствующими информационными входами шифратора, выходы которого соединены с информационными входами дешифратора и являются адресными входами-выходами устройства, входом выборки которого является управляющий вход дешифратора, отличающееся тем,что, с целью расширения области применения устройства за счет обеспечения возможности одновременного ассоциативного поиска и фиксации количества несовпадений аргумента поиска, в него введен блок маскирования, к информационным входам первой группы которого подключены выходы дешифратора адреса, информационные входы второй группы блока маскирования являются входами-выходами данных устройства, управляющим входом которого является управляющий вход блока маскированиявыходы которого подключены к объединенным первым входам элементов памяти соответствующих строк накопителя,1785039 Составитель В, БорисоКулакова Техред М. Моргентал ректор А, Мотыль Редакт оизводственно-издательский комбинат "Патент, г. Ужгород, ул.Гагарина, 10 акаэ 4368 Тираж Подписное ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ С 113035, Москва, Ж, Раушская наб 4/5