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

 

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

СОЮЗ СОВЕТСКИХ

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

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

ГОСУДАРСТВЕННЫЙ КОМИТЕТ

ПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ

ПРИ ГКНТ СССР

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 4821212/24 (22) 09,04.90 (46) 07.03,92. Бюл. В 9 (71) Московский энергетический институт (72) И.В.Огнев, О.В.Исаев, В.В.Борисов и

В.М.Константиновский (53) 681.327.6(088.8) (56) 1, Авторское свидетельство СССР

М 760187, кл. G 11 С 15/00, 1978.

2. Кохонен Т. Ассоциативные запоминающие устройства. M.: Мир, 1982, с. 169, рис.

3,9. (54) АССОЦИАТИВНОЕ ЗАПОМИНАЮЩЕЕ

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

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

Известно ассоциативное запоминающее устройство, содержащее матричный накопитель, первый регистр опроса и маскирования данных, первый и второй дешифраторы, первую, вторую, третью и чет- . вертую группы элементов И, первую и.. Ж 1718274 А1 решении информационно-логических задач, задач поиска и сортировки данных, в устройствах цифровой обработки сигналов в реальном масштабе времени. Целью изобретения является повышение быстродействия устройства за счет обеспечения возможности осуществления параллельного ассоциативного маскируемого поиска одновременно по строкам,и столбцам ассоциативного накопителя. Ассоциативное запоминающее устройство. содержит накопитель, в состав которого входят элементы памяти с входами с первого по седьмой и с первым и вторым выходами, а также дешифратор адреса, первый и второй блоки регистров опроса и маскирования данных, первый и второй регистры фиксации реакций, первый и второй анализаторы многократного совпадения, первый и второй шифраторы. 4 ил, вторую группы элементов ИЛИ, первую и вторую группы индикаторов, первый и второй блоки извлечения мнОгозначного ответа, блок управления и второй регистр, служащий для хранения выходной информации (1).

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

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

15

20 ных, блок селектора адреса и дешифратора, регистр фиксации реакций, анализатор многократного совпадения, шифратор (2).

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

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

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

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

На фиг. 1 представлена схема ассоциативного запоминающего устройства; на фиг.

2 — схема элемента памяти; на фиг. 3 — схема первого блока регистров опроса и маскирования данных и дешифратора; на фиг. 4— схема второго блока регистров опроса и маскирования данных.

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

Информационные входы первого блока

13 регистров опроса и маскирования данных подключены к первой шине 21 данных устройства, а выходы с первого по четвертый (слева направо) каждой группы выходов соединены с входами элементов 2 памяти соответствующего столбца накопителя следующим образом; первый выход — с вторы1718274

10

55 ми входами 5 элементов 2 памяти, второй выход — с первыми входами 4, третий выход — с третьими входами 6 и четвертый выходс четвертыми входами 7 элементов 2 памяти. Вторые выходы элементов 2 памяти соединены между собой по столбцам и подключены к соответствующим информационным входам второго регистра 16 фиксаций реакций, информационные выходы первой группы которого подключены к соответствующим выводам первой шины 21 данных устройства, информационные выходы второй группы соединены с соответствующими информационными входами второго анализатора 18 многократного совпадения, выход 22 состояния которого является вторым выходом состояния устройства, указывающим на наличие "некоторого числа" совпадений в результате проведения параллельного ассоциативного поиска по столбцам ассоциативного накопителя 1, а информационные выходы — с соответствующими информационными входами второго шифратора 20, выходы которого являются адресными выходами 23 второй группы устройства.

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

24 данных устройства, информационные входы второй группы — к соответствующим выходам дешифратора адреса, адресные входы 25 которого являются адресными входами устройства, Первые, вторые и третьи (сверху вниз) выходы каждой группы выходов второго блока 14 регистров опроса и маскирования данных подключены соответственно к первым 3, седьмым 9 и шестым 8 входам элементов 2 памяти соответствующей строки накопителя 1. Первые выходы элементов 2 памяти соединены между собой по строкам и подключены к соответствующим информационным входам первого регистра 15 фиксации реакций, информационные выходы первой группы которого подключены к соответствующим выводам второй шины 24 данных устройства, информационные выходы второй группы соединены с соответствующими информационными входами первого анализатора 17 многократного совпадения, выход 26 состояния которого является первым выходом состояния устройства, указывающим на наличие

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

Шина 28 управления устройством определяет следующие входы, являющиеся управляющими входами устройства: вход 29 записи в накопитель 1, вход 30 чтения из накопителя 1, вход 31 выборки дешифратора 12 адреса, вход 32 записи в регистр onроса блока 13, вход 33 записи в регистр маскирования блока 13, вход 34 сброса в "0" регистров опроса и маскирования блока 13, вход 35 записи в регистр опроса блока 14, вход 36 записи в регистр маскирования блока 14, вход 37 сброса в "0" регистров опроса и маскирования блока 14, вход 38 — первый вход задания режима управлений сигналом стробирования отработанной и выборки следующей активной линии анализатором

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

На фиг. 2 приведен пример реализации элемента 2 памяти, состоящего из триггера

40 и элементов И-НЕ с первого 41 по шестой

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

47 и 48 в виде резисторов.

Первый блок 13 регистров опроса и маскирования данных (фиг. 3) содержит регистр 49 опороса, регистр 50 маскирования, первую и вторую группы инверторов 51 и 52, первую и вторую группы элементов И 53 и

54.

Второй блок 14 регистров опроса и маскирования данных (фиг. 4) содержит регистр 49 опроса, регистр 50 маскирования, первую и вторую группы инверторов 51 и 52, первую и вторую группы элементов И 53 и

54, группу элементов ИЛИ 55.

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

1718274

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

B режиме записи по заданному адресу на первую шину 21 данных устройства подается записываемое слово, которое фиксируется в регистре 49 опроса первого блока 13 регистров опроса и маскирования данных по сигналу на входе 32. Затем в регистр 50 этого блока с первой шины 21 данных устройства записывается маска по сигналу на входе 33 (единицы в разрядах регистра маски определяют маскирование соответствующих разрядов накопителя). Одновременно с этим на входы дешифратора 12 адреса подается и-разрядный код адреса строки (й = 2" — разрядность первой 21 и второй

24 шин дан н ых устройства).

При подаче сигнала по входу 29 записи в накопитель 1 и дешифрации адреса в дешифраторе 12 адреса по сигналу на входе

31 выборки на входы 6 и 7 элементов 2 памяти поступает одна из следующих комбинаций сигналов: "10" — код записи единиц, "01" — код записи нуля, "00" — код маскирования. Кроме того, подается активный уровень на входы 3 элементов 2 памяти выбранной строки накопителя 1. Таким образом, производится запись по выбранному адресу, В случае записи слова по группе адресов в регистр 49 опроса второго блока 14 регистров опроса и маскирования с второй шины 24 данных устройства по сигналу на входе 35 записывается аргумент, в котором единицы соответствуют активизированным строкам накопителя 1.

В режиме считывания информации по заданному адресу на входы дешифратора 12 адреса с адресных входов 25 устройства подается код адреса строки, при дешифрации которого по сигналу на входе 31 выборки при подаче сигнала на вход чтения из накопителя 1 на входы 8 и 9 элементов 2 памяти выбранной строки поступает комбинация

"01", и слово, считываемое с выходов 11 элементов 2 памяти этой строки накопителя

1, фиксируется во втором регистре 16 фиксации реакций по этому же сигналу на входе

30 чтения с выдачей результата на первую шину 21 данных устройства.

В режиме столбцового считывания в регистр 49 опроса первого блока 13 регистров и маскирования данных с первой шины 21 данных устройства по сигналу на входе 32 записывается дешифрированный адрес столбца, который при поступлении сигнала

55 на вход 30 чтения из накопителя 1 организует подачу комбинации сигналов "01" на входы 4 и 5 элементов 2 памяти выбранного столбца накопителя, При этом данные, считываемые с выходов 10 элементов 2 памяти считываемого столбца, фиксируются в первом регистре 15 фиксации реакций по этому же сигналу на входе 30 чтения с выдачей результата на вторую шину 24 данных устройства.

В режиме параллельного ассоциативного поиска по строкам на первую шину 21 данных устройства подается аргумент поиска, который фиксируется в регистре 49 первого блока 13 регистров опроса и маскирования данных по сигналу на входе 32, Затем в регистр 50 этого блока с первой шины 21 данных устройства записывается маска по сигналу на входе 33. При подаче сигнала на вход 30 чтения из накопителя 1 на входы 4 и 5 элементов 2 памяти поступает одна из следующих комбинаций сигналов;

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

15 фиксации реакций устанавливаются в единицу.

Первый анализатор 17 многократного совпадения служит для приоритетной выборки одной из активных линий первого ре-. гистра 15 фиксации реакций. При этом наивысшим приоритетом из аргументов обладает аргумент с нулевым адресом, Адрес активной линии, выбранной первым анализатором 17 многократного совпадения, кодируется первым шифратором 19 и выдается на адресные выходы 27 первой группы устройства по сигналу на входе 38 задания режима. Повторной подачей этого сигнала осуществляются стробирование отработанной и инициализация следующей активной линии первым анализатором 17 многократного совпадения.

В режиме параллельного ассоциативного поиска по столбцам на вторую шину 24 данных устройства подается аргумент поиска, который фиксируется в регистре 49 второго блока 14 регистров опроса и маскирования данных по сигналу на входе 35.

Затем в регистр 50 этого блока с второй шины 24 данных устройства записывается маска по сигналу на входе 36. При подаче сигнала на вход 30 чтения из накопителя 1 на входы 8 и 9 элементов 2 памяти поступает одна из следующих комбинаций сигналов:

1718274 10

10

"01" — сравнение с единицей, "10" — сравнение с нулем, "00" - маскирование поиска.

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

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

Режимы ассоциативного поиска по строкам и столбцам могут быть совмещены.

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

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

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

1718274 иг.

Фл 50

Яю

1718274

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

Редактор Т. Юрчикова . Техред M,Ìîðãåíòàë Корректор И. Муска

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

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

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

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