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

 

(19) RU (11) (51) 5 б 11 С 15 00

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

К ПАТЕНТУ Э

С0

С0

4:ь

Комитет Российской Федерации по патентам и товарным знакам (21) 4896190/24 (22) 25.1 2.90 (46) 15.1093 Бюл. Йя 37 — 38 (71) Московаай энергетический институт (72) Огнев И.В. Борисов В.В. (73) Борисов Вадим Владимирович (54) АССОЦИАТИВНОЕ ЗАПОМИНАЮЩЕЕ

УСТРОЙСТВО (57) Изобретение относится к вычислительной технике, в частности к запоминающим устройствам, и может быть использовано в специализированных системах хранения и цифровой обработки изображений в ассоциативных параллельных процессорах при решении информационно-логических задач, задач поиска и сортировки данных, в устройствах цифровой обработки сигналов в реальном масинабе времени. Целью изобетения является расширение области применения устройства за счет обеспечения возможности осуществления ассоциативного параллельного маскируемого поиска одного и того же поискового аргумента, представляемого как в прямой, так и в зеркально отображенной форме, без его перезаписи в блоке регистров опроса и маскирования одновременно по строкам и столбцам ассоциативного накопителя Ассоциативное запоминающее устройство содержит ассоциативный матричный накопитель 1, в состав которого входят элементы 2 памяти, дешифратор 12 адреса, блок

13 регистров опроса и маскирования данных первый 14 и второй 15 регистры фиксации реакций, первый 16 и второй 17 анализаторы многократного совпадения, первый 18 и второй 19 шифраторы, инвертор 20, группы элементов ИЛИ с первого 21 по четвертый 24. 3 ил.

2001451

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

Недостатком этого устройства является недостаточное быстродействие из-за невозможности проведения параллельного ассоциативного поиска одновременно по строкам и столбцам матричного ассоциативного накопителя.

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

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

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

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

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

10

40

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 onроса и маскирования являются информационными входами устройства, первые 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

55 ра фиксации реакций, первая группа 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

40 шифраторов на первую 34 группу адресных выходов устройства адреса активной линии;

45 — сигнал стробирования отработанной и выборки следующей активной линии вторым 17 анализатором многократного совпадения, а также выдачи вторым 19 шифратором на вторую 37 группу адресных выходов устройства адреса активной линии, На фиг. 2 приведен пример реализации элемента 2 памяти, состоящего иэ R-S триггера 47 с инверсными входами установки в

"1" (S) и в "0" (R) и элементов И-НЕ с первого

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 адреса подается и-разрядный адрес строки.

n = logzN, где N — разрядность накопителя 1 по строкам и столбцам, На управляющий вход 29 подается уровень лог. "1", который стробирует сигналы с выходов первого 21 и второго 22 элементов

ИЛИ всех групп. И при подаче сигнала 38 и дешифрации адреса в дешифраторе 12 адреса по сигналу 43 на входы 8 и 9 всех элементов 2 памяти с выходов третьего 30 и

31 каждой группы блока 13 поступает одна из следующих комбинаций сигналов: "10"— код записи единицы, "01" — код записи нуля, 2001451

15

25

40

55

"00" — код маскирования; а на входы 3 элементов 2 памяти активизируемой строки накопителя подается активный уровень лог.

"1", И, таким образом, производится запись по выбранному адресу строки.

При считывании i-го слова в прямом коде из накопителя в регистр 58 опроса блока

13 заисывается аргумент с единицей в I-м разряде по сигналу 40. Затем в регистр 59 маскирования этого блока по сигналу 41 заносится маска, маскирующая все, кроме Iго, разряды аргумента. И при подаче на устройство сигнала 39 опроса и чтения при единице на входе 29 на входы 4 и 5, а также

7 и 6 элементов 2 памяти выделенных соответственно строки и столбца накопителя поступает комбинация сигналов "10". При этом считываемое слово записывается во второй 15 регистр фиксации реакций и выводится на вторую группу 35 информационных выходов устройства. Одновременно с этим в первый 14 регистр фиксации реакций записывается I-й разрядный срез, который выводится первую группу 32 информационных выходов устройства.

При считывании в инверсном коде в I-й разряд регистра 58 опроса блока 13 должен быть записан нуль при прочих прежних условиях, В режиме конъюнктивного считывания в регистр 58 опроса блока 13 записывается аргумент с единицами в разрядах, соответствующих считываемым словом. Затем в регистр маскирования заносится маска, . маскирующая все, кроме указанных, разря- 35 ды аргумента. И при единице на входе 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 N 760187,,кл. G 11 С 15/00, 1978.

Кохонен Т. Ассоциативные запоминающие устройства. М.: Мир, 1982, с.169. Р.3.9, Ф о р м у л а и з О б Р е т е н и я пы устройства. вторые выходы элементов дссоциятивное здпоминдющее YcTPQAcT- 10 памяти столба ассоциативного накопителя во содержащее ассоциативный матричный Объединены и подключены к соответствуюнакопитель N ° N, где N - емкость памяти, щему информационному входу второго реблок регистров опроса и максирования гистра фиксации реакций, данных, пеРвый и втоРой РегистРы фикса- инф „„„„„„ ции Реакции, nepabIA Pl второи аналPIÇBTO 15 которого являются инфор и нн, ходами второй группы Устроиства второй шифраторы, дешифратор адреса, дресные вход которого влЯютсЯ дрес ги соответствующими входами данных BTððð

20 ro анализатора многократного совп шифратора адреса, информационные вхощий вход второго шифратора объе маскирования данных являю д и являются вторым входом задания режи данных устройства управляющими входа ма устройства вторым выходом состояния ми которого являются управляющие входы 25 которого является выход состояния второблока регистров опроса и маскиро гоанализатора многократного совпадеданных. выходы с первого по четвертыи ния, информационные выходы которого сокаждои группы выходов которого соедине единены с соответствующими ны соответственно с пятым, четaepTblM, информационными входами второго шифшестым и седьмым входами элементов па- ратора, выходы которого являются адрес- 30 мяти соответствующего столбца ассоциа- ными выходами второй группы устройства, ивного накопителя, первые выходы первые входы элементов памяти строки асэлементов памяти каждой строки ассОциа социативного накопителя объединены и тивного накопителя объединены и подклю- подключены к соответствующему выходу чены к соответствующему дешифратора адреса, вторые входы эле35 информационному входу первого регистра ментов памяти 1-й (где = 1 ...., N) строки асфиксации реакций, управляющий вход за социативного накопителя объединены и писи которого, управляющий вход записи подключены к первому выходу i-й группы второго региста фиксации реакций vl BxOA выходов блока регистров опроса и маски40 чтения из ассоциативного накопителя o6b рования данных, второй выход i-й группы единены и подключены к управляющему которого подключен к объединенным входу устрсйСтва, инфОРмаЦионными Bbl трЕтьим вхадам ЭлЕмЕнтОв памяти 1-й строходами первой группы которого являю ки ассоциативного накопителя, отличаюинформационные выходы первой группь 45 щееся тем, что, с целью расширения первого регистра фиксации Реакций HH области применения эа счет обеспечения формационные выходы второй группы Ко возможности осуществления ассоциативТорого соединены с соотвествующ м ного параллельного маскируемого поиска входам данных первого анализатора мно одного и того же поискового аргумента, гократного совпадения. управляющ и вход 50 представляемого как в прямой, так и в эеркоторого и управляющий BXOA первого кально отображенной форме без его перешифратора объединены и являются пер записи в блоке регистров опроса и вым входом задания режима усТроАсТВа маскирования данных, введены инвертор и

nepsblM.BûõpAoì состояния которого явля- группы элементов ИЛИ, причем первые и ется выход состояния первого анализатора 55вторые выходы каждой группы выходов многократного совпадения, информацион блока регистров опроса и маскирования ные выходы которого соединены с соответ- данных подключены к первым входам соствующими информационными вхОдами ответственно первого и третьего, второго и первого шифратора, выходы которого яв четвертого элементов ИЛИ соответствуюляются.адресными выходами первои груп щей группы, вторые входы третьего,и чет2001451

Составитель В. Борисов

Техред М.Моргентал Корректор М. Демчик

Редактор

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

НПО "Поиск" Роспатента

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

Заказ 3129

Производственно-издательскии комбинат "Патент", г. р д, у . р . Ужго о, л.Гагарина, 101 вертого элементов ИЛИ всех групп объединены и подключены к выходу инвертора, вход которого соединен с вторыми входами первого и второго элементов ИЛИ всех групп и является управляющим входом вы- 5 бора направления опроса устройства, выходы третьего и четвертого элементов ИЛИ каждой группы соединены соответственно с пятыми и четвертыми входами элементов памяти соответствующего столбца ассоциативного накопителя, выходы первого и второго элементов ИЛИ, начиная с первой группы, соединены соответственно с вторым и третьим входами элементов памяти строк ассоциативного накопителя, начиная с последней строки.