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

(51)5 6 11 С 15/00 СУДАРСТВЕННОЕ ПАТЕНТНОДОМСТВО СССРОСПАТЕНТ СССР) ИСАНИЕ ИЗОБРЕТЕНИЯ г слительнающим зовано в анения и , в ассоорах при их задач,х, в устгналов в асширеа за счет ния межмого по" редлагащего уст 7) Изобретение относится к вычислительой технике, в частности к запоминающим стройствам, и может быть использовано в пециализированных системах хранения и ифровой обработки изображений, ассоцитивных параллельных процессорах при реении информационно-логических задач,Изобретение относится к вычиой технике,;в частности к запомистройствам, и может быть испольпециализированных системах хрифровой обработки изображенийиативных параллельных процессешении информационно-логическадач поиска и сортировки данныойствах цифровой обработки сиеальном масштабе времени,Целью изобретения является рФие области применения устройствбеспечения возможности проведелочного ассоциативного маскируеска по двум координатам,На фиг.1 представлена схема имого ассоциативного запоминаю выходами. Устроиство также содержит первый и второй блоки регистров опроса и маскирования данных, первый и второй регистры стробирования подматриц накопителя, первый и второй 20 регистры фикса ции реакций, первый и второй анализаторы многократного совпадения, первый и второй шифраторы, 4 ил,роиства; на фиг.2 - схема элемента памяти; на фиг.3 - схема первого блока регистров опроса и маскирования данных; на фиг.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 соответствующего столбца каждой верти- "5 кальной линейки подматриц накопителя.Первая группа информационных выходов второго 20 регистра фиксации реакций присоединена к соответствующим выводам первой 25 шины данных устройства, а его 20 вторая группа информационных выходов.соединена с соответствующими информационными входами второго 22 анализатора многократного совпадения, выход 36 состояния которого служит вторым выходом со стояния устройства, сигнал с которого 30 40 45 50 55 указывает на наличие "некоторого числа" совпадения в результате проведения параллельного ассоциативного поиска по столбцам ассоциативного накопителя 1, а информационные выходы анализатора 22 присоединены к соответствующим информационным входам второго 24 шифратора, выход которого служат второй 37 группой адресных выходов устройства. На устройство подаются следующие управляющие сигналы:38 - сигнал записи в накопитель;39 - сигнал опроса и считывания из накопителя;40 - сигнал записи в регистр опроса блока 15;41- сигнал записи в регистр маскирования блока 15;42 - сигнал сброса в "0" регистров опроса и маскирования блока 15;43 - сигнал записи в регистр опроса блока 16;44 - сигнал записи в регистр маскирования блока 16;45 - сигнал сброса в "0" регистров опроса и маскирования блока 16;46 - сигнал записи в первый 17 регистр стробирования;47 - сигнал сброса в "0" первого 17 регистра стробирования;48 - сигнал записи во второй 18 регистр стробирования;49 - сигнал сброса в "0" второго 18 регистра стробирования;5 10 15 20 25 30 35 40 45 50 55 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 группы элементов И,Размерность подматрицы накопителя:Мха, где М - разрядность первой 25 и вто, рой 30 шин данных устройства.Количество вертикальных и горизональных линеек подматриц накопителя может не совпадать; оно определяется количеством разрядных линий соответственно первого 17 и второго 18 регистров стробирования,В режиме параллельного ассоциативного поиска по строкам активизированной регистрами стробирования 17 и 18 подматрицы накопителя в регистре 61 опроса первого 15 блока регистров опроса и маскирования по сигналу 40 фиксируется аргумент поиска, подаваемый с первой 25 шины данных устройства, Затем в регистр 62 маскирования этого блока с первой 25 шины данных устройства записывается маска по сигналу 41. И при подаче сигнала 39 на входы 6 и 7 элементов памяти поступает одна из следующих комбинаций сигналов:"01" - сравнение с единицей, "10" - сравнение с нулем, "00" - маскирование поиска, Результат ассоциативного поиска по активизированной подматрице фиксируется в первом 19 регистре фиксации реакций по заднему фронту сигнала 39. При этом при совпадении строк подматрицы с маскиро ванным. аргументом поиска в соответствующие таким строкам разряды первого 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 10 15 20 25 35 40 45 50 55 высшим приорйтетом из аргументов обладает аргумент с нулевым адресомАдрес активной линии, выбранный вторым 22 анализатором многократного совпадения, кодируется вторым 24 шифратором и выдается на вторую 37 группу адресных выходов устройства по сигналу 51. Повторной подачей этого сигнала осуществляется стробирование отработанной и инициализация следующей активной линии вторым 22 анализатором многократного совпадения.При активизации нескольких подматриц накопителя с помощью первого 17 и второго 18 регистров стробирования в режиме межблочного ассоциативного поиска по столбцам происходит ассоциативный поиск в каждой из этих подматриц накопителя по маскированному аргументу из второго 16 блока регистров опроса и маскирования; при этом происходит конъюнкция результатов ассоциативного поиска в этих подматрицах, осуществляемая благодаря соединению соответствующих выходных столбцовых разрядных линий подматриц накопителя. Ф о р мул а и зоб рете н ия Ассоциативное запоминающее устройство, содержащее накопитель, первый и второй блоки регистров опроса и маскирования данных, первый и второй регистры фиксации реакций, первый и второй анализаторы многократного совпадения, первый и второй шифраторы, управляющие входы первого блока регистров опроса и маскирования данных являются управляющими входами первой группы устройства, информационными входами (выходами первой группы которого являются информационные входы первого блока регистров опроса и маскирования данных, выходы с первого по четвертый каждой группы выходов которого соединены соответственно с четвертым, третьим, пятым и шестым входами элементов памяти соответствующего столбца каждой вертикальной линейки подматриц накопителя, первые входы элементов памяти каждой строки которого обьединены, вторые выходы элементов памяти каждой строки накопителя и вторые выходы элементов памяти соответствующего столбца каждой вертикальной линейки подматриц накопителя объединены и подключены к соответствующим информационным входам второго регистра фиксации реакций, управляющий вход которого является управляющим входом устройства, первые выходы элементов памяти соответствующих строк накопителя и первые выходы элементов памяти соответствующей строки каждой горизонтальной линейки подматриц накопителя объединены и подключены к соответствующим информационным входам первого регистра фиксации реакций,управляющий вход которого является управляющим входом устройства, информационные:выходы первой группы первого и второго регистров фиксации реакций являются соответственно информационными входами/выходами второй и первой групп устройства, информационные выходы второй группы первого и второго регистров фиксации реакций соединены с соответствующими входами данных первого и второго анализаторов многократного совпадения; управляющие входы которых соответственно объединены с управляющими входами первого и второго шифраторов и являются первым и вторым входами задания режима устройства, выходы состояния первого и второго анализаторов многократного совпадения являются соответственно первым и вторым выходами состояния устройства, информационные выходы первого и второго анализаторов многократного совпадения соединены с соответствующими информационными входами первого и второго шифраторов, выходы которых являются соответственно адресными выходами 30 первой и второй группы устройства, управляющими входами второй группы которого являются управляющие входы второго блока регистров опроса и маскирования данных, информационные входы которого являются информационными входами/выходами второй группы устройства, выходы с первого по третий каждой группы выходов второго блока регистров опроса и маскирования данных подключены соответственно к объединенным седьмым, девятым и восьмым входам элементов памяти соответствующей строки каждой горизонтальной линейки подматриц накопителя, о тл и ч а ю щ е е с я тем, что, с целью расширения области применения устройства эа счет обеспечения возможности проведения межблочного ассоциативного маскируемого поиска по двум координатам, в него введены первый и второй регистры стробирования подматриц накопителя, причем управляющие входы первого и второго регистров стробирования подматриц накопителя являются управляющими входами третьей и четвертой групп устройства, информационные входы первого и второго регистров стробирования подматриц накопителя подключены к соответствующим информационным входам/выходам первой и второй групп устройства, выходы первого регистра стробирования подматриц накопи 1837362 0еля подключены к объединенным вторым ходам элементов памяти соответствующей ертикальной линейки подматриц накопиеля, выходы второго регистра стробирования подматриц накопителя к обьединеннымпервымвходам элементов памяти соответствующей "оризонтальной линейки подматриц накопителя.1837362 Составитель М. КоролТехред М.МоргенталРедактор Корректор М, Самборск оизводственно-издательский комбинат "Патент", г. Ужгород, ул.Гагарина, 1 Закаэ 2869Тираж ПодписноеВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ ССС113035, Москва, Ж, Раушская наб., 4/5