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

(51) 5 0 11 С 15 00 ОПИСАНИЕ ИЗОБРЕТЕНИЯ К ПАТЕНТУ СР СР 4:ь М Комитет Российской Федерации по патентам и товарным знакам(71) Московаай энергетический институт(73) Борисов Вадим Владимирович(7) Изобретение относится к вычислительной технике, в частности к запоминающим устройствам, иможет быть использовано в специализированныхсистемах хранения и цифровой обработки изображений в ассоциативных параллельных процессорахпри решении информационно-логических задач,задач поиска и сортировки данных, в устройствахцифровой обработки сигналов в реальном масштабе времени. Целью изобетения является расширение области применения устройства за счет обеспечения воэможности осуществления ассоциативного параллельного маскируемого поиска одного и того же поискового аргумента, представляемого как в прямой, так и в зеркально отображенной форме, без его перезаписи в блоке регистров опроса и маскирования одновременно по строкам и столбцам ассоциативного накопителя Ассоциативное запоминающее устройство содержит ассоциативный матричный накопитель 1, в состав которого входят элементы 2 памяти, дешифратор 12 адреса, блок 13 регистров опроса и маскирования данных первый 14 и второй 15 регистры фиксации реакций, первый 16 и второй 17 анализаторы многократного совпадения, первый 18 и второй 19 шифраторы, инвертор 20, группы элементов ИЛИ с первого 21 по четвертый 24. 3 ил.Изобретение относится к вычислительной технике, в частности к запоминающим устройствам, и может быть использовано в специализированных системах хранения и цифровой обработки иэображений, в ассоциативных параллельных процессорах, при решении информационно-логических задач, задач поиска и сортировки данных, в устройствах цифровой обработки сигналов в реальном масщтабе времени,Известно ассоциативное запоминающее устройство, содержащее матричный накопитель, первый регистр опроса и маскирования данных, первый и второй дешифраторы, первую, вторую, третью и четвертую группы элементов И, первую и вторую группу элементов ИЛИ, первую и вторую группы инверторов, первый и второй блоки извлечения многоэначного ответа, блок управления и второй регистр, служащий для хранения выходной информации.Недостатком этого устройства является недостаточное быстродействие из-за невозможности проведения параллельного ассоциативного поиска одновременно по строкам и столбцам матричного ассоциативного накопителя.Наиболее близким техническим решением к заявляемому устройству является ассоциативное запоминающее устройство, содержащее ассоциативный накопитель, дешифратор адреса, блок регистров опроса и маскирования данных, первый и второй регистры фиксации реакций, первый и второй анализаторы многократного совпадения, первый и второй шифраторы.Недостаток этого устройства заключается в недостаточном быстродействии из-за неизбежной перезаписи зеркально отображенного аргумента поиска в блок регистров опроса и маскирования при ассоциативном поиске данных в случае, если их ориентация в ассоциативном накопителе неизвестна.Целью изобретения является расширение области применения устройства за счет обеспечения возможности осуществления ассоциативного параллельного маскируемого поиска одного и того же поискового аргумента представляемого как в прямой, так и в зеркально отображенной форме, без его перезаписи в блоке регистров опроса и маскирования, одновременно по строкам и столбцам ассоциативного накопителя,Поставленная цель достигается тем, что в ассоциативное запоминающее устройство, содержащее ассоциативный матричный накопитель, дешифратор адреса, блок регистров опроса и маскирования данных, первый и второй регистры фиксации реакций,5 10 15 20 25 30 35 40 45 50 55 первый и второй анализаторы многократного совпадения, первый и второй шифраторы, адресные входы дешифратора адреса являются адресными входами устройства, вход выборки - одновременно управляющим входом устройства, а выходы подключены соответственно к первым, гоединенным между собой, входами элементов памяти соответствующих строк ассоциативного накопителя, вторые и третьи входы элементов памяти строк ассоциативного накопителя соединены между собой и подключены соответственно к пятым и четвертым соединенным между собой входами элементов памяти столбцов ассоциативного накопителя, соответствующих этим строкам, первые выходы элементов памяти каждой строки накопителя также соединены между собой и подключены к соответствующему информационному входу первого регистра фиксации реакций, чей управляющий вход записи является управляющим входом записи второго регистра фиксации реакций, а также управляющим входом опроса и чтения устройства, первая группа информационных выходов является первой группой информационных выходов устройства, а вторая группа информационных выходов этого регистра соединена с соответствующими входами данных первого анализатора многократного совпадения, чей вход стробирования является одновременно входом стробирования первого шифратора и управляющим входом устройства в целом, выход состояния первого анализатора многократного совпадения является первым выходом состояния устройства, а информационные выходы присоединены к соответствующим информационным входам первого шифратора, выходы которого являются первой группой адресных выходов устройства, вторые выходы элементов памяти каждого столбца накопителя соединены между собой и подключены к соответствующему информационному входу второго регистра фиксации реакций, первая группа информационных выходов которого служит второй группой информационных выходов устройства, а вторая группа информационных выходов :того регистра соединена с соответствующими входами данных второго анализатора многократного совпадения, чей вход стробирования является одновременно входом стробирования второго шифратора и управляющим входом устройства в целом, выход состояния второго анализатора многократного совпадения является вторым выходом состояния устройства, а информационные выходы присоединены к соответствующим информационным вхо 20014515 10 15 20 25 30 35 40 45 50 55 дам второго шифратора, выходы которого являются второй группой адресных выходов устройства, информационные входы блока регистров опроса и маскирования данных являются информационными входами устройства, а управляющие входы являются входами записи и сброса регистров этого блока, а также управляющими сигналами записи и опроса устройства в целом, третьи и четвертые выходы каждой группы выходов этого блока соединены соответственно с шестыми и седьмыми входами элементов памяти соответствующего столбца накопителя, введены инвертор и группы элементов ИЛИ, причем первые и вторые выходы каждой группы выходов блока регистров опроса и маскирования присоединены с первым входам соответственно первого и третьего. а также второго и четвертого элементов ИЛИ соответствующей группы, вторые входы третьего и четвертого элементов ИЛИ всех групп присоединены к выходу инвертора, вход которого соединен с управляющим сигналом выбора направления опроса устройства и со вторыми входами первого и второго элементов ИЛИ всех групп, выходы третьего и четвертого элементов ИЛИ каждой группы соединены соответственно с пятыми и четвертыми входами элементов памяти соответствующего столбца накопителя, а выходы первого и второго элементов ИЛИ, начиная с первой группы, соединены соответственно со вторым и третьим входами элементов памяти строк ассоциативного накопителя, начиная с последней строки.Сопоставительный анализ с прототипом показывает, что заявляемое устройство отличается наличием новых элементов; инвертора и групп элементов ИЛИ и их связями с остальными элементами схемы.Сравнение заявляемого технического решения с другими показывает, что предложенное устройство обладает новым техническим свойством, заключающимся в возможности осуществления ассоциативного параллельного маскирующего поиска одного и того же поискового аргумента, представляемого как в прямой, так и в зеркально отображенной форме, без его перезаписи в блоке регистров опроса маскирования, одновременно по строкам и столбцам ассоциативного накопителя, не присущим известным объектам, содержащим признаки, выступающие как отличия от прототипа,На фиг, 1 представлена схема ассоциативного запоминающего устройства; на фиг. 2 - схема элемента памяти; на фиг. 3 - схема блока регистров опроса и маскирования данных. Устройство (см, фиг. 1) содержит накопитель 1, в состав которого входят элементы 2 памяти с входами с первого 3 по седьмой 9 и с первым 10 и вторым 11 выходами, Устройство также содержит дешифратор 12 адреса, блок 13 регистров опроса и маскирования данных, первый 14 и второй 15 регистры фиксации реакций, первый 16 и второй 17 анализаторы многократногосовпадения, первый 18 и второй 19 шифраторы,инвертор 20. группы элементов ИЛИ с первого 21 по четвертый 24,Адресные входы 25 дешифратора 12 адреса являются адресными входами устройства, а выходы подключены соответственно к первым 3, соединенным между собой входами элементов 2 памяти соответствующих строк ассоциативного накопителя 1, вторые 4 и третьи 5 входы элементов 2 памяти строк ассоциативного накопителя соединены между собой и подключены соответственно к пятым и четвертым соединенным между собой входами элементов 2 памяти столбцов ассоциативного накопителя, соответствующих этим строкам. Кроме того, выходы первого 21 и второго 22 элементов ИЛИ, начиная с первой группы элементов ИЛИ, соединены соответственно со вторым 4 и третьим 5 входами элементов 2 памяти строк ассоциативного накопителя, начиная с последней строки.Информационные входы 26 блока 13 опроса и маскирования являются информационными входами устройства, первые 27 и вторые 28 выходы каждой группы выходов этого блока подключены соответственно к первым входам первого 21 и третьего 23, а также второго 22 и четвертого 24 элементов ИЛИ соответствующей группы. Вторые входы третьих 23 и четвертых 24 элементов ИЛИ всех групп соединены между собой и подключены к выходу инвертора 20, вход которого соединен с управляющим сигналом 29 выбора направления опроса устройства и со вторыми входами первого 21 и второго 22 элементов ИЛИ всех групп, Пятые 7, четвертые 6, шестые 8 и седьмые 9 входы элементов 2 памяти соответствующих столбцов ассоциативного накопителя соединены между собой и подключены соответственно к выходам третьего 23 и четвертого 24 элементов ИЛИ соответствующей группы, к третьему 30 и четвертому 31 выходам соответствующей группы выходов блока 13 регистров опроса и маскирования,Первые 10 выходы элементов 2 памяти каждой строки накопителя соединены между сооой и подключены к соответствующему информационному входу первого 14 регист 200145ра фиксации реакций, первая группа 32 информационных выходов является первой группой информационных выходов устройства, а вторая группа информационных выходов этого регистра соединена с соответствующими входами данных первого 16 анализатора многократного совпадения, Выход 33 состояния первого 16 анализатора многократного совпадения является первым выходом состояния устройства, указывающим на наличие "некоторого числа" совпадений в результате проведения параллельного ассоциативного поиска по строкам ассоциативного накопителя.Информационные выходы блока 16 присоединены к соответствующим информационным входам первого 18 шифратора, выходы которого служат первой группой 34 адресных выходов устройства,Вторые 11 выходы элементов 2 памяти каждого столбца накопителя. соединены между собой и подключены к соответствующему информационному входу второго 15 регистра фиксации реакций, первая 35 группа информационных выходов является второй группой информационных выходов устройства, а вторая группа информационных выходов этого регистра соединена с соответствующими входамиданных второго 17 анализатора многократного совпадения. Выход 36 состояния второго 17 анализатора многократного совпадения является вторым выходом состояния устройства, указывающим на наличие "некоторого числа" совпадений в результате проведения параллельного ассоциативного поиска по столбцам ассоциативного накопителя,Информационные выходы блока 17 присоединены к соответствующим информационным входам второго 18 шифратора, выходы которого служат второй группой 37 адресных выходов устройства,На устройство подаются следующие управляющие сигналы;38 - сигнал записи в накопителе 1;39 - сигнал опроса и чтения из накопителя 1;40 - сигнал записи в регистр опроса блока 13;41 - сигнал записи в регистр маскирования блока 13;42 - сигнал сброса в "0" регистров опроса и маскирования блока 13;43 - сигнал выборки дешифратора 12 адреса;44 - сигнал стробирования отработанной и выборки следующей активной линии первым 16 анализатором многократного совпадения, а также выдачи первым 18 5 10 15 20 25 30 35 40 45 50 55 шифраторов на первую 34 группу адресных выходов устройства адреса активной линии;45 - сигнал стробирования отработанной и выборки следующей активной линии вторым 17 анализатором многократного совадения, а также выдачи вторым 19 шифратором на вторую 37 группу адресных выходов устройства адреса активной линии,На фиг, 2 приведен пример реализации элемента 2 памяти, состоящего иэ В-Я триггера 47 с инверсными входами установки в "1" (Я) и в "0" (В) и элементов И-НЕ с первого 47 по шестой 52, На фиг, 2 также представлены не показанные на фиг, 1 ограничительные элементы 53, 54, 55 и 56 в виде резисторов, 57 - вывод логической единицы,На фиг, 3 показан блок 13 опроса и маскирования данных, содержащий регистр 58 опроса и регистр 59 маскирования, первую 60 и вторую 61 группы инверторов, первую 62 и вторую 63 группы элементов И.Устройство может работать в следующих режимах; запись информации по заданному адресу с маскированием произвольных разрядов записываемого слова; считывание информации по строкам и столбцам в прямом и инверсном коде; конъюнктивное считывание строк и столбцов накопителя; параллельный ассоциативный поиск одного и того же поискового аргумента, представляемого как прямой, так и в зеркально отраженной форме, беэ его перезаписи в блоке регистра опроса и маскирования, одновременно по строкам и столбцам накопителя.В режиме записи до подачи сигнала 38 записи в накопитель 1 в регистр 58 опроса блока 13 с входов 36 по сигналу 40 записывают поисковый аргумент. Затем в регистр 59 маскирования этого же блока записывается маска по сигналу 41 (единицы в разрядах регистра 59 маскирования определяют маскирование соответствующих разрядов накопителя 1). Затем на входы 25 дешифратора 12 адреса подается и-разрядный адрес строки,и = 1 од 2 М,где й - разрядность накопителя 1 по строкам и столбцам,На управляющий вход 29 подается уровень лог. "1", который стробирует сигналы с выходов первого 21 и второго 22 элементов ИЛИ всех групп. И при подаче сигнала 38 и дешифрации адреса в дешифраторе 12 адреса по сигналу 43 на входы 8 и 9 всех элементов 2 памяти с выходов третьего 30 и 31 каждой группы блока 13 поступает одна из следующих комбинаций сигналов: "10" - код записи единицы, "01" - код записи нуля, 2001451"00" - код маскирования; а на входы 3 элементов 2 памяти активизируемой строки накопителя подается активный уровень лог, "1", И, таким образом, производится запись по выбранному адресу строки.При считывании 1-го слова в прямом коде из накопителя в регистр 58 опроса блока 13 заисывается аргумент с единицей в 1-м разряде по сигналу 40. Затем в регистр 59 маскирования этого блока по сигналу 41 заносится маска, маскирующая все, кроме 1- го, разряды аргумента. И при подаче на устройство сигнала 39 опроса и чтения при единице на входе 29 на входы 4 и 5, а также 7 и 6 элементов 2 памяти выделенных соответственно строки и столбца накопителя поступает комбинация сигналов "10". При этом считываемое слово записывается во второй 15 регистр фиксации реакций и выводится на вторую группу 35 информационных выходов устройства. Одновременно с этим в первый 14 регистр фиксации реакций записывается 1-й разрядный срез, который выводится первую группу 32 информационных выходов устройства.При считывании в инверсном коде в 1-й разряд регистра 58 опроса блока 13 должен быть записан нуль при прочих прежних условиях,В режиме конъюнктивного считывания в регистр 58 опроса блока 13 записывается аргумент с единицами в разрядах, соответствующих считываемым словом, Затем в регистр маскирования заносится маска, маскирующая все, кроме указанных, разряды аргумента. И при единице на входе 29 при подаче на устройство сигнала 39 чтения в первый 14 и второй 15 регистры фиксации реакций запишутся результаты конъюнктивного считывания соответственно выделенных разрядных срезов и выделенных слов(см, режим простогосчитывания). В том случае. если в немаскированные разряды регистра 58 опроса блока 13 записаны нули, то конъюнкция будет проводиться с инверсными кодами соответствующих этим разрядам строк и столбцов.В режиме параллельного ассоциативного маскируемого поиска одного и того же поискового аргумента, представленного в прямой форме, одновременно по строкам и столбцам на управляющем входе 29 выборки направления опроса устройства должен быть установлен уровень логической "1" (как и во всех вышеописанных режимах). В регистр 58 блока 13 записывается аргумент поиска по сигналу 40, Затем в регистр 59 этого блока заносится маска по сигналу 41. И при подаче на устройство сигнала 39 чтения на входы 4 и 5 (входы столбцового опроса), а также на входы 7 и 6 (входы строчного опроса) элементов Я памяти поступает одна из следующих комбинаций сигналов: "10" - сравнение с единицей, "О 1" - сравнение с нулем, "00" - маскирование сравнения, Результаты строчного и столбцового ассоциативного поиска фиксируются соответственно в первом 14 и втором регистрах фиксации реакций по сигналу 39, При этом, если выявляются слова или разрядные срезы, совпавшие с маскированным аргументом поиска, то соответствующие им разряды соответствующих регистров фиксации реакций установятся в единицу,Первый 16 анализатор многократного совпадения служит для приоритетной выборки одной иэ активных линий первого 14 регистра фиксации реакций. При этом наивысшим приоритетом иэ аргументов обладает аргумент с нулевым адресом,Адрес активной линии, выбранной первым 16 анализатором многократного совпадения кодируется первым 18 шифратором и выдается на первую 34 группу адресных выходов устройства по сигналу 44, Повторной подачей этого сигнала осуществляется стробирование отработанной и инициализация следующей активной линии первым 16 анализатором многократного совпадения.Все вышесказанное о первом 16 анализаторе многократного совпадения и о первом 18 шифраторе справедливо и для второго 17 анализатора многократного совпадения и второго 19 шифратора в собственном контексте. В режиме ассоциативного параллельного маскируемого поиска одного и того же поискового аргумента, представленного в зеркально отображенной форме, беэ его перезаписи в блоке регистров опроса и маскирования, одновременно по строкам и столбцам ассоциативного накопителя, на управляющем входе 29 выбора направления опроса устройства должен быть установлен уровень логического нуля. В этом случае при подаче сигнала 39 признаки сравнения с единицей "10", нулем "01" или признаки маскирования сравнения снимаются не с выходов третьих 23 и четвертых 24 элементов ИЛИ всех групп, а с выходов первых 21 и вторых 22 элементов ИЛИ. Причем, благодаря тому, что выходы первого 21 и второго 22 элементов ИЛИ, начиная с первой группы, соединены соответственно со вторым 4 и третьим 5 входами элементов 2 памяти строк ассоциативного накопителя, начиная с последней строки, в этом режиме происходит переориентация маскированно12 2001451 если ориентация данных в ассоциативномнакопителе не известна,го аргумента поиска из прямой в зеркально отображенную форму,Далее описание этого режима соответствует описанию предыдущего режима,Таким образом, достигается цель изобретения, заключающаяся в расширении области применения устройства в случае,(56) Авторское свидетельство СССР5 М 760187, кл, 6 11 С 15/00, 1978,Кохонен Т. Ассоциативные запоминающие устройства. М.: Мир, 1982, с,169. Р.3,9,Ф о р м у л а и з о б Р е т е н и я пы устройства. вторые выходы элементов дссоцидтивное здпоминдющее Устройст памяти столба ассоциативного накопителя во, содержащее ассоциативный матричный объединены и подключены к соответствую- накопитель Й ф Й, где Й - емкость памяти щему информационному входу второго реблок регистров опроса и максирования гистра фиксации реакций, данных, первый и второй Регисры фса информационные выходы первой группы, ции реакций, первый и втоРой анализато 15 которого являются информационными выры многократного совпадения, первыи " ходами второй группы устройства, инфорвторой шифраторы, дешифРатор адреса мационные выходы второй группы второго адресные входы которого являются адрес регистра фиксации реакций соединены с ными входами устройства, входом выборки соответствующими входами данных второ- которого .является управляющий вход де 20 го анализатора многократного совпадения, шифратора адреса, информационные вхо- управляющий вход которого и управляюды блока регистРов опроса " щий вход второго шифратора объединены маскирования данных являются входами и являются вторым входом задания режи- данных устройства, управляющими входа- ма устройства, вторым выходом состояния ми которого являются управляющие входы 25 которого является выход состояния второ- блока регистров опроса и маскирования гоанализатора многократного совпадеданных. выходы с первого по четвертыи ния, информационные выходы которогосокаждой группы выходов которого соедине- единеныс соответствующими ны соответственно с пятым, четвеРтым информационными входами второго шифшестым и седьмым входами элементов па- ратора, выходы которого являются адрес мяти соответствующего столбца ассочиа- ными выходами второй группы устройства, тивного накопителя, первые выходы первые входы элементов памяти строки асэлементов памяти каждой строки ассоциа- социативного накопителя объединены и тивного накопителя объединены и подклю- подключены к соответствующему выходу чены к соответствующему дешифратора адреса, вторые входы эле 35информационному входу первого регистра ментов памяти 1-й (где= 1, й) строки асфиксации реакций, управляющий вход за социативного накопителя объединены и писи которого, управляющий вход записи подключены к первому выходу -й группы второго региста фиксации реакций и вход выходов блока регистров опроса и маски 40чтения из ассоциативного накопителя объ- рования данных, второй выход -й группы единены и подключены к управляющему которого подключен к объединенным входу устройства, информационными вы- третьим входам элементов памяти 3-й строходами первой группы которого являются ки ассоциативного накопителя, отличаю- информационные выходы пеРвой группы 45 щееся тем, что, с целью расширения первого регистра фиксации реакций, ин- области применения эа счет обеспечения формационные выходы второй группы ко возможности осуществления ассоциативторого соединены с соотвествующии ного параллельного маскируемого поиска входами данных первого анализатоРа мно- одного и того же поискового аргумента, гократного совпадения. управляющий вход 50 представляемого как в прямой, так и в эеркоторого и управляющий вход ероо кально отображенной форме без его пере- шифратора объединены и являются пер- записи в блоке регистров опроса и вым входом задания режима устройства маскирования данных, введены инвертор и первым, выходом состояния которого явля- группы элементов ИЛИ, причем первые и ется выход состояния первого анализатора 55 вторые выходы каждой группы выходов многократного совпадения, информацион блока регистров опроса и маскирования ные выходы которого соединены с соответ- данных подключены к первым входам соствующими информационными входами ответственно первого и третьего, второго и первого шифратора, выходы которого яв- четвертого элементов ИЛИ соответствуюляются адресными выходами первой груп- щей группы, вторые входы третьего,и чет2001451 Фа. 3овКорректор М Демчик Составитель В. Б Техред М.Моргент Редакт Тираж Подписное НПО "Поиск" Роспатента113035, Москва, Ж, Раушская наб 4/5 Заказ 3129 гарина, 101 Производственно-издательский комбинат "Патент", г. Ужгор вертого элементов ИЛИ всех групп объединены и подключены к выходу инвертора, вход которого соединен с вторыми входами первого и второго элементов ИЛИ всех групп и является управляющим входом вы бора направления опроса устройства, выходы третьего и четвертого элементов ИЛИ каждой группы соединены соответственно с пятыми и четвертыми входами элементов памяти соответствующего столбца ассоциативного накопителя, выходы первого и второго элементов ИЛИ, начиная с первой группы, соединены соответственно с вторым и третьим входами элементов памяти строк ассоциативного накопителя, начиная с последней строки.