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

СОЮЗ СОВЕТ СКИХСОЦИАЛИСТИ ЕСКИХРЕСПУБЛИК 179341 С 15/00 А 1 ГОСУДАРСТВЕННОЕ ВЕДОМСТВО СССР (ГОСПАТЕНТ СССР АТЕНТНО ИЗОБРЕТЕНИЯ ИС ВТОРСКОМ ИДЕТЕЛЬСТВУ вычислительпоминающим пользовано в(71) Московский энергетический институт(57) Изобретение относится кной технике, в частности к заустройствам, и может быть ис Изобретение относится к вычислительной технике, в частности к запоминающим устройствам, и может быть использовано в специализированных системах хранения и цифровой обработки изображений, в ассоциативных параллельных процессорах, при решении информацион но-логических задач, задач поиска и сортировки данных, в устройствах цифровой обработки сигналов в реальном масштабе времени.Известно ассоциативное запоминающее устройство, содержащее ассоциативный накопитель, блок регистров опроса и маскирования данных, блок. селектора адреса и дешифратора, регистр фиксации реакций, анализатор многократного совпадения, шифратор. специализированных системах хранения и цифровой обработки изображений, в ассоциативных параллельных процессорах, при решении информационно-логических задач, задач поиска и сортировки данных, в устройствах цифровой обработки сигналов в реальном масштабе времени, Целью изобретения является упрощение устройства и повышение его быстродействия. Ассоциативное запоминающее устройство содержит ассоциативный матричный накопитель. в состав которого входят элементы памяти со входами с первого по седьмой и с первым и вторым выходами, Устройство также содержит дешифратор адреса, блок регистров опроса и маскирования данных, первый и второй регистры фиксации реакций, первый и второй анализаторы многократного совпадения, первый и второй шифраторы, 3 ил. Недостатком этого устройства является 0недостаточная производительность из-за ( )невозможности проведения параллельного дассоциативного поиска по столбцам ассоциативного накопителя.Наиболее близким техническим решением к заявляемому устройству является ассоциативное запоминающее устройство,содержащее ассоциативный накопитель, адешифратор адреса, первый и второй регистры фиксации реакций, первый и второйанализаторы многократного совпадения,первый и второй шифраторы,Недостатком этого устройства являетсянедостаточная производительность из-занеобходимости записи аргумента поиска вовторой блок регистров опроса и маскирования при"ассоцивтивйом поиске данных вслучае, если их ориентация в ассоциативном накопителе не известна,Целью изобретения является упрощение устройства й повышение его быстродействйя за счет обеспечения возможностиосуществления параллельного ассоциативного маскирующего поиска одного и того: же поискового аргумента одновременно построкам и столбцам ассоциативного накопителя в случае, если ориентация данных вассоциативном накопителе не известна,Поставленная цель достигаешься тем, чтов ассоциативном запоминающем устройстве, содержащем ассоциативный матричныйнакопитель, блок регистров оп роса и.маскирования данных. первый и второй регистры фиксации реакций, первый и второйанализаторы многократного совпадения,первый и второй шифраторы; дешифраторадреса, адресные ВхОды которбго являютсяадресными входами устройства, управляю щий вход- входом сигнала выборки, информационные входы блока регистров опросаи маскирования данных являются входамиданных устройства; упррвеляющие Входы яв-ляютсяя входами сигналов записи е регистрыэтого блока и сигналое записи и чтению ассоциативного накопителя, е выходы с первого по четвертый каждой груМы Выходовэтого блока соединены соответственно с пятым, четвертым, шестым и седьмым входамиэлементов памяти соответствующего столбца ассоциативного накопителя, первые выходы элементов памяти каждой строкиассоциативного накопителя соединенымежду собой и подключены к соответствующему информационному входу первого регистра Фиксации реакций, чей управляющийвход записи является управляющим входомзаписи второго регистра Фиксации реакций,а также входом сигнала чтения ассоциативного накопителя, информационньа ВЫхОды первой группы первого регистра фиксацииреакций являются информационнымивыходами первой группы устройства, а ин формационные выходы второй труппыэтогорегистра соединены с соотеетствующиМивходами данных первого анализатора мно гократного совпадения, управляющий входкоторого является Одновременно управляющим входом первого шифратора и первымвходом задания режима устройства выходсостояния первого анализатора многократного совпадения является первым выходомсостояния устройства, а информационныевыходы присоединены к соответствующиминформационным входам первого шифратора, выходы которого являются адреснь 1 мивыходами первой группы устройства, вторые выходы элементов памяти соответствующего столбца ассоциативного накопителя соединены между собой и подключены .к соответствующему информационному вхо.ду второго регистра фиксации реакций, информационные выходы первой группы которого являются информационными выходами второй группы устройства, а информационные выходы второй группы этого регистра соединены с соответствующими входами данных второго анализатора многократного совпадения, управляющий вход которого является одновременно управляющим входом второго шифратора и вторым входом задания режима устройства, выход состояния второго анализатора многократного совпадения является вторым выходом состояния устройства, а информационныевыходы присоединены к соответствующим20 информационным входам второго шифратора, выходы которого являются адресньми выходами второй группы устройства. причем выходы дешифратора адреса подключены к первым, соединенным между собой25 входам элементов памяти соответствующейстроки ассоциативного накопителя, первые ивторые выходы каждой группы выходов блокарегистров опроса и маскирования данныхподключены соответственно ко вторым иЗО третьим входам элементов памяти соответствующей строки ассоциативного накопителя,Таким образом, достигается цель изобретения заключающаяся в упрощении устройства и повышении быстродействия за35 счет обеспечения возможности осуществления параллельного ассоциативного маскируемого поиска одного и того же поисковогоаргумента без его записи во второй блокрегистров опроса и маскирования (см.про 40 тотип) одновременно по строкам и столбцамассоциативного накопителя в случае, еслиориентация данных в ассоциативном накопителе не известна,На фиг.1 представлена схема вссоциа 48 тивного запоминающего устройства; нафиг.2 - схема элемента памяти; на фиг,З -схема блока регистров опроса и маскированияданных;БО Устройство фиг,1) содержит накопитель 1, в состав которого входятэлементы 2 памяти со входами с первого 3 по седьмой 9 ис первым 10 и вторым 11 выходами. Устройство также содержит дешифратор 12 адреса, блок 13 регистров опроса и маскинрования данных, первый 14 и второй 15 регистры фиксации реакций; первый 1 б и второй 17 аналиэатооы многократного совпадения, первый 18 и втрой 19 шифраторы.Информационные входы 20 блока 13 регистров опроса и маскирования данных служат информационными входами устройства, а выходы с первого 21 по четвертый 24 каждой группы выходов этого блока соединены со входами элементов 2 памяти соответствующего столбца накопителя 1 следующим образом: первый 21 выход - с пятыми 7 входами элементов 2 памяти столбца, второй 22 выход - с четвертыми 6 входами, третий 23 выход - . с шестыми 8 входами и четвертый 24 выход - с седьмыми 9 входами элементов 2 памяти, Кроме того, первый 21 и второй 22 выходы каждой группы выходов блока 13 регистров опроса и маскирования данных соединены соответственно со вторыми 4 и третьими з входами элементов 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 по шес той 47, На фиг,2 также представлены не 45 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 группы элементов И устройство может работать в следующихрежимах, запись информации по заданному считывание битовых срезов информации, хранимой в накопителе столбцовое считыциативный поиск одного и того же ключевого аргумента одновременно по строкам и столбцам ассоциативного накопителя с маскированием произвольных разрядов и анализ сигналов совпадения, полученных в результате ассоциативного поиска, в порядке убывания приоритета их расположения с выдачей закодированных адресов рассматриваемого сигнала совпадения по двум координатам.В режиме записи по заданному адресу на информационные входы 20 блока 13 регистров опроса и маскирования данных подается записываемое слово, которое фиксируется в регистре 50 опроса блока 13 регистров опроса и маскирования данных по сигналу 35. Затем в регистр 51 этого блока с информационных входов 20 записывается маска по сигналу 36 (единицы в разрядах регистра маски определяют маскирование соответствующих разрядов накопителя 1). Затем на входы дешифратора 12 адреса подается и-разрядный код адреса строки (И=2" - разрядность накопителя по строкам и столбцам); И при подаче сигнала 33 записи и дешифрации адреса в дешифраторе 12 адреса по сигналу 38 на входы 8 и 9 элементов 2 памяти поступает одна из следующих комбинаций сигналов; "10" - код записи единицы, "01" код записи нуля, "00" - код маскирования, И, кроме того, подается активный уровень на первые входы 3 элементов 2 памяти выбранной дешифратором 12 адреса строки накопителя 1 И, таким образом, производится запись по выбранному адресу.При считывании 1-того слова из накопителя 1 в регистр 50 опроса блока 13 опроса и маскирования данных с информационных входов 20 этого блока записывается аргумент с единицей в 1-том разряде по сигналу 35, Затем в регистр 51 маскирования блока 13 заносится маска, маскирующая все .кроме 1-того разряды аргумента по сигналу 36. И при подаче на устройство сигнала 34 чтения на входы 4 и 5, а также 7 и 6 элементов 2 памяти выделенных соответственно строки и столбца накопителя поступает комбинация сигналов "10", а на такие же входы замаскированных элементов 2 памяти накопителя подается комбинация сигналов маскирования считывания: "00". При этом считываемое слово записывается во второй 15 регистр фйксации реакций и выводится на вторую группу информационных выходов 25 устройства. Одновременно с этим в первый 14 регистр фиксации реакций записывается 1-й разрядный срез, который выводйтся на первую группу информационных выходов 29 устройства,В режиме конъюнктивного считывания в регистр 50 опроса блока 13 записывается аргумент с единицами в разрядах, соответствующих считываемым словам по сигналу45 50 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 крегистра фиксации реакций, При этом наивысшим приоритетом из аргументов обладает аргумент с нулевым адресом,Формула изобретения Ассоциативное запоминающее устройство, содержащее ассоциативный матричный накопитель й х И, где й определяется емкостью памяти, блок регистров опроса и маскирования данных, первый и второй регистры фиксации реакций, первый и второй анализатор многократного совпадения, первый и второй шифраторы, дешифратор адреса, адресные входы каторга являются адресными входами устройства, входом выборки которого является управляющий вход дешифратора адреса, информационные входы блока регистров опроса и маскирования данных являются входами данных устройства, управляющими входами которого являются управляющие входы блока регистров опроса и маскирования данных, выходы с первого по четвертый каждой группы выходов которого соединены соответственно с пятым, четвертым, шестым и седьмым входами элементов памяти соответствующего столбца. ассоциативного накопителя, первые выходы элементов памяти каждой строки ассоциативного накопителя объединены и подключены к соответствующему информационному входу первого регистра фиксации реакций, управляющий вход записи которого, управляющий вход записи второго регистра фиксации реакций и вход чтения из ассоциативного накопителя объединены и являются управляющим входом устройства, информационными выходами первой группы которого являются информационные выходы первой группы первого регистра фиксации реакций, информационные выходы второй группы которого соединены с соответствующими входами данных первого анализатора многократного совпадения, управляющий вход которого и управляющий вход первого шифратора объединены и являются первым входом задания режима устройства, первым выходом состояния которого является выход состояния первого анализатора многократного совпадения, информационные выходы которого соеди нены с соответствующими информационными входами первого шифратора, выходы которого являются адресными выходами первой группы устройства, вторые выходы элементов памяти столбца ассоциативного10 накопителя объединены и подключены к соответствующему информацион ному входу второго регистра фиксации реакций информационные выходы первой группы которого являются информационными выходами15 второй группы устройства, информационные выходы второй группы второго регистра фиксации реакций соединены с соответствующими входами данных второго анализатора многократного совпадения,20 управляющий вход которого и управляющий вход второго шифратора объединены и являются вторым входом задания режима устройства, вторым выходом состояния которого является выход состояния второго25 анализатора многократного совпадения, информационные выходы которого соединены с соответствующими информационными входами второго шифратора, выходы которого являются адресными выходами30 второй группы устройства, о т л и ч а ю щ е ес я тем, что; с целью упрощения устройства и повышения его быстродействия, первые входы элементов памяти строки ассоциативного накопителя обьединены и подключены к35 соответствующему выходу дешифратора адреса. вторые входы элементов памяти 1-й (где= 1,М) строки ассоциативного накопителя объединены и подключены к первому выходу -й группы выходов блока регистров опро 40 са и маскирования данных, второй выход 1-й группы которого подключен к объединенным третьим входам элементов памяти 1-й строки ассоциативного накопителя, 17934751793475 Рректор Н,Слободяник СССР осуд изводственно-издательский комбинат "Патент", г, Ужгород, ул.Гагарина,РедакторЗаказ 50ВНИИ Составитель 8, Борисовехред М. Моргентау Тираж Подписноенного комитета по изобретениям и открытиям при ГК 3035,Москва, Ж, Раушская наб 45