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

имя при ассоциативном поиске данных в случае, если их ориентация в ассоциативном накопителе не известна.

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

Поставленная цель достигается тем, что

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

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

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

регистра соединены с соответствующими входами данных второго анализатора многократного совпадения, управляющий вход которого является одновременно управляющим входом второго шифратора и вторым

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

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

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

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

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

На фиг.1 представлена схема ассоциативного запоминающего устройства; на фиг.2 - схема элемента-памяти1; на фиг.З - схема блока регистров Опроса м маскирования . данных. ;.:; .

Устройство (фиг.1) содержит накопитель 1, в состав которого входят элементы 2 памяти со входами с первого 3 по седьмой 9 и с первым 10 и вторым 11 выходами. Устройство также содержит дешифратор 12 адреса, блок 13 регистров опроса и маскинрования данных, первый 14 и второй 15 регистры фиксации реакций, первый 16 и второй 17 анализаторы многократного совпадения, первый 18 и втрой 19 шифраторы.

Информационные входы 20 блока 13 регистров опроса и маскирования данных служат информационными входами устройства а выходы с первого 21 по четвертый 24 каждой группы выходов этого блока соединены со входами элементов 2 памяти соответствующего столбца накопителя 1 следующим образом: первый 21 выход - с пятыми 7 входами элементов 2 памяти столбца, второй 22 выход - с четвертыми б входами, третий 23 выход - с шестыми 8 входами и четвертый 24 выход - с седьмыми 9 входами элементов 2 памяти. Кроме того, первый 21 и второй 22 выходы каждой группы выходов блока 13регистров опроса и маскирования данных соединены соответственно со вторыми 4 и третьими 5 входами элементов 2 памяти соответствующих строк накопителя 1. Вторые 11 выходы элементов 2 памяти соединены между собой-по столбцам и под- ключены к соответствующим информационным входам второго 15 регистра фиксации реакций, информационные выходы первой 25 группы которого служат информационными выходами второй группы устройства, а информационные выходы второй группы этого регистра соединены с соответствующими входами данных второго 17 анализатора многократного совпадения, выход 26 состояния которого является вторым вы хо- дом состояния устройства, указывающим на наличие некоторого числа совпадений в результате проведения параллельного ассоциативного поиска по столбцам ассоциатив- ного накопителя 1, а информационные выходы соединены с соответствующими информационными входами второго 19 шифратора, выходы которого являются адресными выходами второй 27 группы устройства.

Адресные входы 28 дешифратора 12 адреса служат адресными входами устройства. Выходы дешифратора 12 адреса подключены к первым 3 входам элементов 2 памяти соответствующих строк накопителя 1, а первые 10 выходы элементов 2 памяти также соединены между собой по строкам и подключены к соответствующим информационным входам первого 14 регистра фиксации реакций, информационные выходы первой 29 группы которого являются информационными выходами первой группы устройства, информационные выходы второй группы этого регистра соединены с соответствующими информационными входами первого 16 анализатора многократного совпадения, выход 30 состояния которого служит первым выходом состояния устройства, указывающим на наличие некоторого числа совпадений в результате проведения параллельного ассоциативного поиска по строкам ассоциативного накопителя 1, а информационные выходы присоединены к соответствующим информационным входам первого 18 шифратора, выходы которого являются адресными выходами первой 31 группы устройства.

Шина 32 управления устройством определяет следующие входы, являющиеся управляющими входами устройства: вход 33 - записи в накопитель 1, вход 34 - чтения из накопителя 1, вход 35 - записи в регистр опроса блока 13 регистров опроса и маскирования данных, вход 36- записи в регистр маскирования блока 13 регистров опроса и маскирования данных, вход 37 - сброса в О регистров опроса и маскирования блока 13 регистров опроса и маскирования данных, вход 38 - выборки дешифратора 12 адреса, вход 39 - первый вход задания режима, управляемый сигналом стробирова- ния отработанной и выборки следующей активной линии первым 16 анализатором многократного совпадения, а также выдачи первым 18 шифраторам на первую 31 группу адресных выходов устройства адреса активной линии, вход 40 - второй вход задания режима, управляемый сигнал стробирова- ния отработанной и выборки следующей активной линии вторым 17 анализатором многократного совпадения, а также, выдачи вторым 19 шифратором на вторую 27 группу адресных выходов устройства адреса активной линии.

На фиг.2 приведен пример реализации элемента 2 памяти, состоящего из триггера 41 и элементов И-НЕ с первого 42 по шестой 47. На фиг.2 также представлены не показанные на фиг.1 ограничительные элементы 48 и 49 в виде резисторов.

На фиг.З показан блок 13 опроса и маскирования данных, содержащий регистр 50 опроса и регистр 51 маскирования, первую 52 и вторую 53 группы инверторов, первую 54 и вторую 55 группы элементов И.

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

В режиме записи по заданному адресу на информационные входы 20 блока 13 регистров опроса и маскирования данных подается записываемое слово, которое фиксируется в регистре 50 опроса блока 13 регистров опроса и маскирования данных по сигналу 35. Затем в регистр 51 этого блока с информационных входов 20 записывается маска по сигналу 36 (единицы в разрядах регистра маски определяют маскирование соответствующих разрядов накопителя 1). Затем на входы дешифратора 12 адреса подается п-разрядный код адреса строки ( - разрядность накопителя по строкам и столбцам). И при подаче сигнала 33 записи и дешифрации адреса в дешифраторе 12 адреса по сигналу 38 на входы 8 и 9 элементов 2 памяти поступает одна из следующих комбинаций сигналов: 10 - код записи единицы, 01 код записи нуля, 00 - код маскирования, И, кроме того, подается актирный уровень на первые входы 3 элементов 2 памяти выбранной дешифратором 12 адреса строки накопителя 1 И, таким обра- зом, производится запись по выбранному адресу.

При считывании i-того слова из накопителя 1 в регистр 50 опроса блока 13 опроса и маскирования данных с информационных входов 20 этого блока записывается аргумент с единицей в l-том разряде по сигналу 35. Затем в регистр 51 маскирования блока 13 заносится маска, маскирующая всё кроме l-того разряды аргумента по сигналу 36. И при подаче на устройство сигнала 34 чтения на входы 4 и 5, а также 7 и б элементов 2 памяти выделенных соответственно строки и столбца накопителя поступает ком- бинация сигналов 10, а на такие же входы замаскированных элементов 2 памяти накопителя подается комбинация сигналов маскирования считывания: 00. При этом считываемое слово записывается во второй 15 регистр фиксации реакций и выводится на вторую группу информационных выходов 25 устройства. Одновременно с этим в первый 14 регистр фиксации реакций записывается 1-й разрядный срез, который выводится на первую группу информацией- ны х выходов 29 устройства.

В режиме конъюнктивного считывания в регистр 50 опроса блока 13 записывается аргумент с единицами в разрядах, соответ- ствующих считываемым словам по сигналу

35. Затем в регистр 51 маскирования заносится маска, маскирующая все, кроме указанных, разряды аргумента по сигналу 36. И при подаче на устройство сигнала 34 чтения в первый 14 и второй 15 регистры фиксации реакций записываются результаты конъюнктивного считывания соответственно выделенных разрядных срезов и выделенных слов (см. режим простого считывания).

В режиме параллельного ассоциативного поиска одного и того же аргумента поиска одновременно по строкам и столбцам ассоциативного накопителя с маскированием произвольных разрядов в регистр 50 опроса блока 13с информационных входов 20 этого блока записывается аргумент поиска по,сигналу 35. Затем с этих же информационных входов в регистр 51 маскирования этого блока заносится маска по сигналу 36. И при подаче на устройство сигнала 34 чтения на входы 4 и 5 (входы сравнения для столбцового параллельного ассоциативного поиска), а также 6 и 7 (входы сравнения для строчного параллельного ассоциативного описка) элементов 2 памяти поступает одна из следующих комбинаций сигналов, 10 - сравнение с единицей,01 сравнение с нулем, 00 - маскирование поиска. Результаты строчного и столбцового ассоциативного поиска фиксируются соответственно в первом 14 и втором 15 регистрах фиксации реакций по сигналу 34. При этом, если выявляются слова или разрядные срезы, совпадающие с маскированным аргументом описка, то соответствующие им разряды соответствующих регистров фиксации реакций устанавливаются в единицу.

Первый 16 анализатор многократного совпадения служит для приоритетной выборки одной из активной линии первого 14к регистра фиксации реакций. При этом наивысшим приоритетом из аргументов обладает аргументе нулевым адресом.

Адрес активной линии, выбранной первым 1.6 анализатором многократного совпадения кодируется первым 18 шифратором и выдается на первую 31 группу адресных входов устройства по сигналу 39. Повторной подачей этого сигнала осуществляется стробирование отработанной и инициализация следующей активной линии первым 16 анализатором многократного совпадения.

Все вышесказанное о первом 16 анализаторе многократного совпадения и первом 18 шифраторе справедливо и для второго 17 анализатора многократного совпадения и второго 19 шифратора в собственном контексте.

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

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

устройства, первым выходом состояния которого является выход состояния первого анализатора многократного совпадения, информационные выходы которого соединены с соответствующими информационными входами первого шифратора, выходы которого являются адресными выходами первой группы устройства, вторые выходы элементов памяти столбца ассоциативного накопителя объединены и подключены к соответствующему информационному входу второго регистра фиксации реакций, информационные выходы первой группы которого являются информационными выходами второй группы устройства, информационные выходы второй группы второго регистра фиксации реакций соединены с соответствующими входами данных второго анализатора многократного совпадения, управляющий вход которого и управляющий вход второго шифратора объединены и являются вторым входом задания режима устройства, вторым выходом состояния которого является выход состояния второго анализатора многократного совпадения, информационные выходы которого соединены с соответствующими информационными входами второго шифратора, выходы которого являются адресными выходами второй группы устройства, отличающее- с я тем, что; с целью упрощения устройства и повышения его быстродействия, первые входы элементов памяти строки ассоциативного накопителя объединены и подключены к соответствующему выходу дешифратора адреса, вторые входы элементов памяти 1-й (где I 1...N) строки ассоциативного накопителя объединены и подключены к первому выходу i-й группы выходов блока регистров опроса и маскирования данных, второй выход 1-й группы которого подключен к объединенным третьим входам элементов памяти 1-й строки ассоциативного накопителя.

I sa г|Л

ГУ

«р.

Фи ъ.З