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

 

союз- советских

СОЦИАЛИСТИ (ЕСКИХ

РЕСПУБЛИК (я)л G 11 С 15/00

ГОСУДАРСТВЕННОЕ ПАТЕНТНОЕ

ВЕДОМСТВО СССР (ГОСПАТЕНТ СССР) ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 4833215/24 (22) 30.05.90 (46) 07.02.93. Бюл, f+ 5 (71) Московский энергетический институт (72) И.В.Огнев, В.В.Борисов и О,В.Исаев (56) Кохонен Т, Ассоциативные запоминающие устройства. M.: Мир, 1982, с.169, рис,3.9.

Авторское свидетельство СССР

М 1718274, кл. 6 11 С 15/00, 1990, Кохонен Т, Ассоциативные запоминающие устройства, М.; Мир, 1982, с,163, рис.3.4, Там же, с.174, рис.3,11. (54) АССОЦИАТИВНОЕ ЗАПОМИНАЮЩЕЕ

УСТРОЙСТВО (57) Изобретение относится к вычислительной технике, в частности к запоминающим устройствам, и может быть использовано в

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

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

„„5U„„1793475 Al специализированных системах хранения и цифровой обработки изображений, в ассоциативных параллельных процессорах, при решении информационно-логических задач, задач поиска и сортировки данных, в устройствах цифровой обработки сигналов в реальном масштабе времени. Целью изобретения является упрощение устройства и повышение его быстродействия. Ассоциативное запоминающее устройство содержит ассоциативный матричный накопитель. в состав которого входят элементы памяти со входами с первого по седьмой и с первым и вторым выходами. Устройство также содержит дешифратор адреса, блок регистров опроса и маскирования данных, первый и второй регистры фиксации реакций, первый и второй анализаторы многократного совпадения. первый и второй шифраторы, 3 ил.

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

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

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

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

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

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

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

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

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

35 счет обеспечения возможности осуществления параллельного ассоциативного маскируемого поиска одного и того же поискового аргумента без его записи во второй блок регистров опроса и маскирования {см.про40 тотип) одновременно по строкам и столбцам ассоциативного накопителя sслучае,,если ориентация данных в ассоциативном накопителе не известна, На фиг.1 представлена схема ассоциативного запоминающего устройства; на фиг.2 — схема элемента памяти ; на фиг,З— схема блока регистров опроса и маскирования данных;

БО Устройство (фиг,1) содержит накопитель

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

15 регистры фиксации реакций; первый 1б и второй 17 анализаторы многократного совпадения, первый 18 и втрой 19 шифраторы.

1793475

Информационные входы 20 блока 13 регистров опроса и маскирования данных служат информационными входами устройства, а выходы с первого 21 по четвертый 24 каждой группы выходов этого блока соединены со входами элементов 2 памяти соответствующего столбца накопителя 1 следующим образом: первый 21 выход — с пятыми 7 входами элементов 2 памяти столбца, второй 22 выход — с четвертыми 6 входами, третий 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 состояния которого служит первым выходом состояния устройства, указывающим на наличие "некоторого чис10 ной линии. вход 40 — второй вход задания

30 режима, управляемый сигнал стробирования отработанной и выборки следующей ак35 элемента 2 памяти, состоящего из триггера

41 и элементов И вЂ” НЕ с первого 42 по шес40 той 47, На фиг.2 также представлены не

50 адресу с маскированием произвольных разрядов записываемого слова, считывание информации по заданному адресу аргумента, 55 вание), конъюнктивное считывание строк и столбцов накопителя, параллельный ассо15

20 ла" совпадений в результате проведения параллельного ассоциативного поиска по строкам ассоциативного накопителя 1, а информационные выходы присоединены к соответствующим информационным входам первого 18 шифратора, выходы которого являются адресными выходами первой 31 группы устройства.

Шина 32 управления устройством определяет следующие входы, являющиеся управляющими входами устройства: вход 33— записи в накопитель 1, вход 34 — чтения из накопителя 1, вход 35 — записи в регистр опроса блока 13 регистров опроса и маскирования данных; вход 36 — записи в регистр маскирования блока 13 регистров опроса и маскирования данных, вход 37 — сброса в

"0" регистров опроса и маскирования блока

13 регистров опроса и маскированйя данных; вход 38 — выборки дешифратора 12 адреса, вход 39 — первый вход задания режима, управляемый сигналом стробирования отработанной и выборки следующей активной линии первым 16 анализатором многократного совпадения, а также выдачи первым 18 шифраторам на первую 31 группу адресных выходов устройства адреса активтивной линии вторым 17 анализатором многократного совпадения, а также, выдачи вторым 19 шифратором на вторую 27 группу адресных выходов устройства адреса активной линии.

На фиг.2 приведен пример реализации показанные на фиг.1 ограничительные элементы 48 и 49 в виде резисторов.

На фиг,3 показан блок 13 опроса и маскирования данных, содержащий регистр 50 опроса и регистр 51 маскирования, первую

52 и вторую 53 группы инверторов, первую

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

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

2 памяти поступает одна из следующих комбинаций сигналов; "10" — код записи единицы, "01" код записи нуля, "00" — код маскирования, И, кроме того, подается активный уровень на первые входы 3 элементов 2 памяти выбранной дешифратором 12 адреса строки накопителя 1 И, таким образом, производится запись по выбранному адресу.

При считывании i-того слова из накопителя 1 в регистр 50 опроса блока 13 опроса и маскирования данных с информационных входов 20 этого блока записывается аргумент с единицей в i-том разряде по сигналу 35, Затем в регистр 51 маскирования блока 13 заносится маска, маскирующая все .кроме i-того разряды аргумента по сигналу

36. И при подаче на устройство сигнала 34 чтения на входы 4 и 5, а также 7 и 6 элементов 2 памяти выделенных соответственно строки и столбца накопителя поступает комбинация сигналов "10", а на такие же входы замаскированных элементов 2 памяти накопителя подается комбинация сигналов маскирования считывания: "00". При этом считываемое cllo80 записывается во второй

15 регистр фйксации реакций и выводится на вторую группу информационных выходов

25 устройства. Одновременно с этим в первый 14 регистр фиксации реакций записывается 1-й разрядный срез, который выводйтся на первую группу информационных выходов 29 устройства, В режиме конъюнктивного считывания .в регистр 50 опроса блока 13 записывается аргумент с единицами в разрядах, соответствующих-считываемым словам по сигналу

55

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

18 шифраторе справедливо и для второго 17 анализатора многократного совпадения и второго 19 шифратора в собственном контексте, 35. Затем в регистр 51 маскирования заносится маска, маскирующая все, кроме указанных, разряды аргумента по сигналу 36. И при подаче на устройство сигнала 34 чтения

5 в первый 14 и второй 15 регистры фиксации реакций записываются результаты коньюнктивного считывания соответственно выделенных разрядных срезов и выделенных слов (см. режим простого считывания), 10 В режиме параллельного ассоциативного поиска одного и того же аргумента поиска одновременно по строкам и столбцам ассоциативного накопителя с маскированием произвольных разрядов в регистр 50 опроса

15 блока 13 с информационных входов 20 этого блока записывается аргумент поиска по сигналу 35, Затем с этих же информационных входов в регистр 51 маскирования этого блока заносится маска по сигналу 36. И при

20 подаче на устройство сигнала 34 чтения на входы 4 и 5 (входы сравнения для столбцового параллельного ассоциативного поиска), а также 6 и 7 (входы сравнения для строчного параллельного ассоциативного

25 описка) элементов 2 памяти поступает одна из следующих комбинаций сигналов, "10"— сравнение с единицей, "01" сравнение с нулем, "00" — маскирование поиска. Результаты строчного и столбцового ассоциативного

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

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

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

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

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

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

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

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

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

35 соответствующему выходу дешифратора адреса. вторые входы элементов памяти 1-й (где

I = 1...N) строки ассоциативного накопителя объединены и подключены к первому выходу I-й группы выходов блока регистров опро40 са и маскирования данных, второй-выход i-й группы которого подключен к объединенным третьим входам элементов памяти 1-й строки ассоциативного накопителя.

1793475

1793475

Фиг.5

Составитель В. Борисов

Техред М.Моргентау Корректор Н,Слободяник

Редактор

Производственно-издательский комбинат "Патент", г. Ужгород, ул.Гагарина, 101

Заказ 507 Тираж Подписное

ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР

113035, Москва, Ж-35, Раушская наб,, 4/5