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

 

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

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

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

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

ЕДОМСТВО СССР

ОСПАТЕНТ СССР)

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

;:1 . - !

1.„- - °

Нлi (;! 4g- 1 „ - - ;,г, CTPOVICTHO

7) Кзо5ретвние относится к вычислительой технике, в частности к запоминающим стройствам, и может быть использовано в пециализированных системах хранения и ифровой обработки изображений, ассоцитивных параллельных процессорах при реении информационно-логических задач, I

Изобретение относится к вычислительой технике, .в частности к запоминающим стройствам, и может быть использовано в пециализированных системах хранения и ифровой обработки изображений, в ассоиативных параллельных процессорах при ешении информационно-логических задач, адач поиска и сортировки данных, в устойствах цифровой обработки сигналов в еальном масштабе времени, Целью изобретения является расширеФ ие области применения устройства за счет беспечения возможности проведения межлочного ассоциативного маскируемого поска по двум координатам, На фиг.1 представлена схема предлагамого ассоциативного запоминающего уст„„5U„„1837362 А1 выходами. Устроиство также содержит первый и второй блоки регистров опроса и маскирования данных, первый и второй регистры стробирования подматриц накопителя, первый и второй 20 регистры фикса- 3 ции реакций, первый и второй анализаторы многократного совпадения, первый и второй шифраторы. 4 ил, ройства; на фиг.2 — схема элемента памяти; на фиг.3 — схема первого блока регистров опроса и маскирования данных; на фиг.4— схема второго блока регистров опроса и маскирования данных.

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

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

1837362

Информационные входы первого 15 блока регистров опроса и маскирования данных подключены к первой 25 шине данных устройства, а выходы с первого 26 по четвертый 29 каждой группы выходов подключены соответственно к четвертым 7, третьим 6, пятым 8 и шестым 9 входам элементов памяти 3, соединенными с одноименными входами элементов памяти в соответствующем столбце.

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

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

5 входам всех элементов памяти 3 соответствующей вертикальной линейки подматриц 2 накопителя 1.

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

4 входам всех элементов памяти 3 соответствующей горизонтальной линейки подматриц 2 накопителя 1.

Первые 13 восходы элементов 3 памяти соответствующих строк накопителя 1 соединены между собой и подключены к соответствующим информационным входам первого 19 регистра фиксации реакций, к этим же соответствующим входам подключены объединенные таким же образом первые 13 выходы элементов памяти 3 соответствующей строки каждой горизонтальной линейки подматриц 2 накопителя 1, Первая группа информационных выходов первого 19 регистра фиксации реакций подключена к соответствующим выводам второй ЗО шины данных устройства, а вторая группа информационных выводов соединена с соответствующими входами данных первого 21 анализатора многократного совпадения, выход 34 состояния которого служит первым выходом состояния устройства,указывающим на наличие "некоторого числа" совпадений в результате проведения параллельного ассоциативного поиска по строкам ассоциативного накопителя 1, а информационные выходы анализатора присоединены к соответствующим информационным входам первого 23 шифратора, выходы которого служат первой 35 группой адресных выходов устройства.

Вторые 14 выходы элементов памяти 3 соответствующих столбцов накопителя 1 соединены между собой и подключены к соответствующим информационным входам

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

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

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

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

На устройство подаются следующие управляющие сигналы:

38 — сигнал записи в накопитель;

39 — сигнал опроса и считывания из накопителя;

40 — сигнал записи в регистр опроса блока 15;

41- сигнал записи в регистр маскирования блока 15;

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

43 — сигнал записи в регистр опроса блока 16;

44 — сигнал записи в регистр маскирования блока 16;

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

46 — сигнал записи в первый 17 регистр стробирования;

47 — сигнал сброса в "О" первого 17 регистра стробирования;

48- сигнал записи во второй 18 регистр стробирования;

49 — сигнал сброса в "0" второго 18 регистра стробирования;

1837362

20

30

50 — сигнал стробирования отработаной и выборки следующей активной линии локу 21, а также, выдачи первым 23 шифатором на первую 35 группу адресных выодов устройства адреса следующей ктивной линии;

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

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

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

Первый 15 блок резисторов опроса и аскирования данных (фиг.3) содержит регистр 61 опроса, регистр 62 маскирования, первую 63 и вторую 64 группы инверторов, первую 65 и вторую 66 группы элеменов И.

Второй 16 блок регистров опроса и маскирования данных (фиг.4) содержит регистр 61 опроса, регистра 62 маскирования, первую 63 и вторую 64 группы инверторов, первую 65 и вторую 66 группы элементов И.

Размерность подматрицы накопителя:

NxN, где N — разрядность первой 25 и вто, рой 30 шин данных устройства.

Количество вертикальных и горизональных линеек подматриц накопителя может не совпадать; оно определяется количеством разрядных линий соответственно первого 17 и второго 18 регистров стробирования, В режиме параллельного ассоциативного поиска по строкам активизированной регистрами стробирования 17 и 18 подматрицы накопителя в регистре 61 опроса первого 15 блока регистров опроса и маскирования по сигналу 40 фиксируется аргумент поиска, подаваемый с первой 25 шины данных устройства, Затем в регистр

62 маскирования этого блока с первой 25 шины данных устройства записывается маска по сигналу 41. И при подаче сигнала 39 на входы 6 и 7 элементов памяти поступает одна из следующих комбинаций сигналов:

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

Результат ассоциативного поиска по активизированной подматрице фиксируется в первом 19 регистре фиксации реакций по заднему фронту сигнала 39. При этом при совпадении строк подматрицы с маскиро ванным аргументом поиска в соответствую1 щие таким строкам разряды первого 19 регистра фиксации реакций установятся в единицу.

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

21 анализатором многократного совпадения.

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

В режиме параллельного ассоциативного поиска по столбцам активизированной регистрами стробирования 17 и 18 подматрицы накопителя в регистре 61 опроса второго 16 блока регистров опроса и маскирования по сигналу 43 фиксируется аргумент поиска. подаваемый со второй 30 шины данных устройства, Затем в регистр

62 маскирования этого блока со второй 30 шины данных устройства записывается маска по сигналу 44. И при подаче сигнала 39 на входы 11 и 12 элементов памяти поступает она из следующих комбинаций сигналов:

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

Результат ассоциативного поиска по активизированной подматрице фиксируется во втором 20 регистре фиксации реакций по заднему фронту сигнала 39. При этом, при совпадении столбцов подматрицы с маскированным аргументом поиска в соответствующие таким столбцам разряды второго 20 регистра фиксации реакций установятся в единицу, Второй 22 анализатор многократного совпадения служит для приоритетной выборки одной из активных линий второго 20 регистра фиксации реакций, При этом наи1837362

25

50

55 высшим приорйтетом из аргументов обладает аргумент с нулевым адресом..

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

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

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

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

30 первой и второй группы устройства, управляющими входами второй группы которого являются управляющие входы второго блока регистров опроса и маскирования данных, информационные входы которого являются информационными входами/выходами второй группы устройства, выходы с первого rio третий каждой группы выходов второго блока регистров опроса и маскирования данных подключены соответственно к объединенным седьмым, девятым и восьмым входам элементов памяти соответствующей строки каждой горизонтальной линейки подматриц накопителя, о тл и ч а ю щ е е с я тем, что, с целью расширения области применения устройства эа счет обеспечения возможности проведения межблочного ассоциативного маскируемого поиска по двум координатам, в него введены первый и второй регистры стробирования подматриц накопителя, причем управляющие входы первого и второго регистров стробирования подматриц накопителя являются управляющими входами третьей и четвертой групп устройства, информационные входы первого и второго регистров стробирования подматриц накопителя подключены к соответствующим информационным входам/выходам первой и второй групп устройства, выходы первого регистра стробирования подматриц накопи1837362 G еля подключены к объединенным вторым ходам элементов памяти соответствующей ертикальной линейки подматриц накопиеля, выходы второго регистра стробирования подматриц накопителя к объединенным первым входам элементов памяти соответствующей оризо: -,альной линейки подматриц накопителя 3 362

1837362

Редактор

Составитель М. Королев

Техред M.Ìîðãåíòàë Корректор М. Самборская Заказ 2869 !

Тираж Подписное

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

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

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