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

 

Изобретение относится к вычислительной технике, в частности к запоминающим устройствам, и может быть использовано в специализированных системах хранение и цифровой обработки информации, в системах решения информационно-логических задач, задач сжатия, поиска и сортировки данных. Целью изобретения является увеличение гибкости использования устройства за счет обеспечения возможности фиксации, хранения и анализа результатов ассоциативного поиска в ассоциативном накопителе устройства. Устройство содержит накопитель 1, в состав которого входят элементы 2 памяти с входами с первого 3 по четвертый 6 и с первым 7 и вторым 8 выходами. В состав устройства также входят дешифратор 9 адреса, блок 10 регистров опроса и маскирования данных, ассоциативный буферный блок 11 памяти, регистр 12 выходных данных, регистр 13 фиксации реакций, анализатор 14 многократного совпадения, шифратор 15. 1 з. п.ф-лы, 4 ил.

Изобретение относится к вычислительной технике, в частности к запоминающим устройствам, и может быть использовано в специализированных системах хранения и цифровой обработки информации, в системах решения информационно-логических задач, задач сжатия, поиска и сортировки данных.

Известно ассоциативное запоминающее устройство, содержащее накопитель, дешифратор адреса, регистр дескрипторов, блок приоритета, коммутатор [1].

Недостатком этого устройства является отсутствие возможности фиксации и анализа результатов ассоциативного поиска в его накопителе.

Наиболее близким техническим решением к заявляемому устройству является ассоциативное запоминающее устройство, содержащее ассоциативный накопитель, блок регистров опроса и маскирования данных, дешифратор адреса, регистр фиксации реакций, анализатор многократного совпадения, шифратор [2].

Недостатком этого устройства является отсутствие возможности фиксации и анализа результатов ассоциативного поиска в накопителе и, как следствие этого, недостаточная гибкость при реализации алгоритмических методов сжатия, поиска и сортировки данных.

Целью изобретения является увеличение гибкости использования устройства за счет обеспечения возможности фиксации, хранения и анализа результатов ассоциативного поиска в ассоциативном накопителе устройства.

Цель достигается тем, что в ассоциативное запоминающее устройство, содержащее ассоциативный накопитель, блок регистров опроса и маскирования данных, регистр выходных данных, регистр фиксации реакций, анализатор многократного совпадения, шифратор, дешифратор адреса, управляющий вход которого является входом выборки, информационные входы являются адресными входами устройства, а выходы подключены к соединенным между собой первым входам элементов памяти соответствующих строк ассоциативного накопителя, причем управляющие входы блока регистров опроса и маскирования данных являются входами сигналов записи в регистры этого блока и входом начальной установки устройства, входы данных этого блока являются информационными входами устройства, а первый и второй выходы каждой группы подключены соответственно к соединенным между собой вторым и третьим входам элементов памяти соответствующего столбца ассоциативного накопителя, первые выходы элементов памяти соответствующих столбцов накопителя соединены между собой и подключены к соответствующим информационным входам регистра выходных данных, выходы которого являются первой группой информационных выходов устройства, а вход сигнала записи является сигналом опроса устройства и соединен с входом сигнала записи регистра фиксации реакций, информационные входы которого подключены к соединенным между собой вторым выходам элементов памяти соответствующих строк ассоциативного накопителя, первая группа выходов этого регистра является второй группой информационных выходов устройства, а вторая группа выходов регистра подключена к соответствующим входам данных анализатора многократного совпадения, управляющий вход которого соединен с управляющим входом шифратора и является входом задания режима работы устройства, выход состояния анализатора многократного совпадения является выходом состояния устройства, а информационные выходы анализатора подключены к соответствующим информационным входам шифратора, выходы которого являются адресными выходами устройства, введен ассоциативный буферный блок памяти, входы данных которого подключены к информационным входам устройства, выходы соединены с объединенными между собой четвертыми входами элементов памяти соответствующих столбцов накопителя, а управляющие входы являются входами сигнала записи, сигнала опроса и сигнала начальной установки устройства.

Ассоциативный буферный блок памяти содержит регистр и группу элементов И, первые входы которых соединены с соответствующими выходами регистра, вторые входы объединены и подключены к управляющему входу буфера, при этом входы буфера являются установочным и входом записи буфера.

На фиг.1 представлена схема предлагаемого устройства; на фиг.2 - схема элемента памяти; на фиг.3 - схема блока регистров опроса и маскирования; на фиг.4 - схема ассоциативного буферного блока памяти.

Устройство (фиг. 1) содержит накопитель 1, в состав которого входят элементы 2 памяти с входами с первого 3 по четвертый 6 и с первым 7 и вторым 8 выходами. В состав устройства также входят дешифратор 9 адреса, блок 10 регистров опроса и маскирования данных, ассоциативный буферный блок 11 памяти, регистр 12 выходных данных, регистр 13 фиксации реакций, анализатор 14 многократного совпадения, шифратор 15. Входы 16 данных дешифратора 9 являются адресными входами устройства. Информационные входы 17 блока 10 регистров опроса и маскирования являются информационными входами устройства, а первый 18 и второй 19 выходы каждой группы выходов подключены соответственно к соединенным между собой вторым 4 и третьим 5 входам элементов 2 памяти соответствующего столбца ассоциативного накопителя. Выходы 20 данных регистра 12 являются первой группой информационных выходов устройства, а выходы 21 первой группы регистра 13 фиксации реакций - второй группой информационных выходов устройства. Выходы 22 шифратора 15 являются адресными выходами устройства. Выход 23 состояния анализатора 14 многократного совпадения является выходом состояния устройства, указывающим на наличие некоторого числа совпадений в результате проведения ассоциативного поиска.

На устройство подаются следующие управляющие сигналы: 24 - сигнал выборки дешифратора 9 адреса, 25 - сигнал опроса и считывания из накопителя 1, 26 - сигнал записи в регистр опроса блока 10, 27 - сигнал записи в регистр маскирования блока 10; 28 - сигнал записи в регистр блока 11, 29 - сигнал начальной установки устройства, 30 - сигнал стробирования отработанной и выборки следующей активной линии анализатором 14, а также выдачи шифратором 15 на адресные выходы 22 устройства адреса следующей активной линии.

Элемент 2 памяти (фиг.2) состоит из тактируемого фронтом D-триггера 31 с инверсными входами установки в "1" и "0", элементов И-НЕ с первого 32 по третий 34 и элемента 2И-ИЛИ-НЕ 35. На фиг.2 также представлены не показанные на фиг.1 ограничительные элементы 36 в виде резисторов.

Блок 10 регистров опроса и маскирования (фиг.3) содержит регистр 37 опроса, регистр 38 маскирования и группу элементов И 39.

Блок 11 памяти (фиг.4) содержит регистр 40 и группу элементов И 41.

Устройство может работать в следующих режимах: запись информации по заданному адресу с маскированием произвольных разрядов, считывание информации по заданному адресу, считывание разрядного среза, ассоциативный маскируемый поиск с возможностью осуществления фиксации, хранения и анализа результатов поиска в ассоциативном накопителе.

В режиме записи информации по заданному адресу на информационные входы 17 блока 10 подается записываемое слово, которое фиксируется в регистре 37 опроса этого блока по сигналу 26. Затем в регистр 38 маскирования этого блока записывается маска по сигналу 27 (единицы в разрядах регистра маски определяют маскирование соответствующих разрядов накопителя). При этом на входы 4 и 5 всех элементов памяти с соответствующих выходов 18 и 19 блока 10 поступает одна из следующих комбинаций сигналов: 10 - код единицы, 01 - код нуля, 00 - код маски. Затем на адресные входы 16 устройства подается код адреса, который, дешифруясь в дешифраторе 9 по сигналу 24, инициирует высоким логическим уровнем сигнала на входах 3 элементов 2 памяти соответствующей строки накопителя запись по заданному адресу.

При считывании информации по заданному адресу (после установки устройства в начальное состояние) с адресных входов 16 устройства на дешифратор 9 подается код считываемого слова, который дешифрируется по сигналу 24, инициируя подачу уровня логической "1" на входы 3 элементов 2 памяти соответствующей строки накопителя. По сигналу 25 опроса и считывания из накопителя считываемое слово с выходов 7 элементов 2 памяти соответствующей строки накопителя в инверсном коде записывается в регистр 12 выходных данных и поступает на первую группу 20 информационных выходов устройства.

При считывании содержимого элементов памяти выделенного столбца (разрядного среза) накопителя в соответствующем разряде регистра 37 блока 10 должна быть записана единица. Остальные разряды должны быть замаскированы маской из регистра 38 этого блока. При этом на входы 4 и 5 элементов памяти выделенного столбца поступает комбинация 10 - сравнение с единицей, а на этих же входах остальных элементов памяти сочетание 00 - маскирование сравнения. При подаче сигнала 25 опроса содержимое элементов памяти выделенного столбца с выходов 8 записывается в регистр 13.

В режиме ассоциативного маскируемого поиска (после установки устройства в начальное состояние) в регистр 37 блока 10 записывается аргумент поиска по сигналу 26, а в регистр 38 этого блока - маска по сигналу 27. При этом на входы 4 и 5 всех элементов 2 памяти поступает одна из следующих комбинаций: 10 - код единицы, 01 - код нуля, 00 - код маскирования, инициируя сравнение с содержимым триггера 31 соответствующего элемента 2 памяти. По сигналу 25 в регистре 13 фиксации реакций записывается результат ассоциативного поиска, который поступает на вторую группу 21 информационных выходов устройства. Если маскируемый аргумент поиска совпадает с какой-либо строкой накопителя, то шина, соединяющая выходы 8 элементов 2 памяти соответствующей строки, сохраняет уровень логической "1". Если хотя бы в одном разряде этой строки происходит несовпадение, то выход 8 соответствующего элемента 2 памяти обнуляется, следовательно, обнуляется и соответствующая шина, что указывает на наличие несовпадения.

Анализатор 14 многократного совпадения служит для приоритетной выборки одной из активных линий регистра 13 фиксации реакций. При этом наивысшим приоритетом из аргументов обладает аргумент с нулевым адресом. Адрес активной линии, выбранной анализатором 14, кодируется шифратором 15 и поступает на адресные выходы 22 устройства по сигналу 30. Повторной подачей этого сигнала осуществляется стробирование отработанной и инициализация следующей активной линии анализатором 14 многократного совпадения.

При выполнении ассоциативного поиска в устройстве может быть реализована возможность фиксации полученных результатов в элементах 2 памяти выделенного столбца (разрядного среза) накопителя. Для этого перед выполнением ассоциативного поиска в регистр 40 блока 11 должен быть занесен аргумент, единица в соответствующем разряде которого определяет разрядный срез накопителя, куда будет занесен результат по заднему фронту сигнала 25 опроса, инициирующего подачу отрицательного перепада уровня сигнала на входы 6 элементов памяти выделенного столбца.

Аналогично в различные выделенные разрядные срезы могут быть занесены другие полученные результаты ассоциативного поиска, и, таким образом, эти результаты могут служить исходной информацией для анализа, например, посредством последующего ассоциативного поиска, что может быть использовано в алгоритмах сжатия, поиска и сортировки данных.

Таким образом, достигается увеличение гибкости использования устройства за счет обеспечения возможности фиксации, хранения и анализа результатов ассоциативного поиска в его ассоциативном накопителе.

Формула изобретения

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

2. Устройство по п.1, отличающееся тем, что ассоциативный буферный блок памяти содержит регистр и группу элементов И, первые входы которых соединены с соответствующими выходами регистра, вторые входы объединены и подключены к управляющему входу буфера, входы регистра являются установочным и входом записи буфера.

РИСУНКИ

Рисунок 1, Рисунок 2, Рисунок 3, Рисунок 4