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

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

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

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

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

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

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

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

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

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

Вторые 14 выходы элементов памяти 3 соответствующих столбцов накопителя 1 соединены между собой и подключены к соответствующим информационным входам второго 20 регистра фиксации реакций, к этим же соответствующим входам подключены объединенные таким же образом вторые выходы элементов памяти 3 соответствующего столбца каждой вертикальной линейки подматриц накопителя. Первая группа информационных выходов второго 20 регистра фиксации реакций присоединена к соответствующим выводам первой 25 шины данных устройства, а его вторая группа информационных выходов соединена с соответствующими информационными входами второго 22 анализатора многократного совпадения, выход 36 состояния которого служит вторым выходом состояния устройства, сигнал с которого указывает на наличие некоторого числа совпадения в результате проведения параллельного ассоциативного поиска по столбцам ассоциативного накопителя 1, а информационные выходы анализатора 22 присоединены к соответствующим информационным входам второго 24 шифратора, выход которого служат второй 37 группой адресных выходов устройства.

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

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

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

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

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

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

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

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

45- сигнал сброса в О регистров опроса и маскирования блока 16;

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

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

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

49 - сигнал сброса в О второго 18 регистра стробирования;

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

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

На фиг.2 приведен пример реализации элемента памяти 3, состоящего из триггера 52 и элементов И-НЕ с первого 53 по шестой 58. На фиг.2 также представлены не показанные на фиг.1 ограничительные 59 и 60 элементы в виде резисторов 7.

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

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

Размерность подматрицы накопителя: vJxN, где N - разрядность первой 25 и вто- эой 30 шин данных устройства.

Количество вертикальных и горизонтальных линеек подматриц накопителя может не совпадать; оно определяется количеством разрядных линий соответственно первого 17 и второго 18 регистров стробирования,

j В режиме параллельного ассоциативного поиска по строкам активизированной регистрами стробирования 17 и 18 подматрицы накопителя в регистре 61 опроса первого 15 блока регистров опроса и маскирования по сигналу 40 фиксируется аргумент поиска, подаваемый с первой 25 шины данных устройства. Затем в регистр 62 маскирования этого блока с первой 25 шины данных устройства записывается маска по сигналу 41. И при подаче сигнала 39 на входы 6 и 7 элементов памяти поступает одна из следующих комбинаций сигналов: 01 - сравнение с единицей, 10 - сравнение с нулем, 00 - маскирование поиска. Результат ассоциативного поиска по активизированной подматрице фиксируется в первом 19 регистре фиксации реакций по заднему фронту сигнала 39. При этом при совпадении строк подматрицы с маскированным аргументом поиска в соответствующие таким строкам разряды первого 19 регистра фиксации реакций установятся в единицу.

Первый 21 анализатор многократного

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

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

0При активизации нескольких подматриц накопителя с помощью первого 17 и второго 18 регистров стробирования в режиме межблочного ассоциативного поиска по строкам происходит ассоциативный

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

В режиме параллельного ассоциативного поиска по столбцам активизированной

5 регистрами стробирования 17 и 18 подматрицы накопителя в регистре 61 опроса второго 16 блока регистров опроса и маскирования по сигналу 43 фиксируется аргумент поиска, подаваемый со второй 30

0 шины данных устройства. Затем в регистр 62 маскирования этого блока со второй 30 шины данных устройства записывается маска по сигналу 44. И при подаче сигнала 39 на входы 11 и 12 элементов памяти поступа5 ет она из следующих комбинаций сигналов: 01 - сравнение с единицей, 10 -сравнение с нулем, 00 - маскирование поиска. Результат ассоциативного поиска по активизированной подматрице фиксируется во

0 втором 20 регистре фиксации реакций по заднему фронту сигнала 39. При этом, при совпадении столбцов подматрицы с маскированным аргументом поиска в соответствующие таким столбцам разряды второго 20

5 регистра фиксации реакций установятся в единицу.

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

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

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

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

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

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

еля, выходы второго регистра стробирова-риц накопителя.

ния подматриц накопителя к объединенным

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

jswa

Щ45

J

фс/e.f

15

61

63

ff

-О

IS

27

28

13

26

27 2В 23

ФигЛ