Ячейка ассоциативной памяти

 

Изобретение относится к вычислительной технике, в частности к устройствам хранения информации, и может быть использовано в устройствах цифровой ассоциативной обработки данных, в системах распознавания образов, выполненных на узлах с большой степенью интеграции. Целью изобретения является увеличение производительности операций в ассоциативной памяти за счет реализации маскируемых записи и параллельного ассоциативного поиска по двум координатам в ячейках памяти. Ячейка ассоциативной памяти содержит триггер 1, элементы И-НЕ 2-6, элемент ИЛИ-НЕ 7, первый 8 и второй 9 элементы И, первый ,10м второй 11 входы записи ячейки по столбцу, первый 12 и второй 13 входы записи ячейки по строке, первый 14 и второй 15 входы опроса ячейки по столбцу, первый 16 и второй 17 входы опроса ячейки по строке, выход 18 ассоциативного поиска ячейки по строке, выход 19 ассоциативного поиска ячейки по столбцу. 1 ил. ,W J521 2 -в ч Ё НО 00 го XI ел

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК (5))5 6 11 С 15/00

ГОСУДАРСТВЕННЫЙ КОМИТЕТ

ПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ

ПРИ ГКНТ СССР

/

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

1g

12

18

3

К АВТОРСКОМУ СВИДЕТЕЛЬСТВУ (21) 4833214/24 (22) 30.05.90 (46) 07.03.92. Бюл. М 9 (71) Московский энергетический институт (72) И.B.Oãíåâ, В.В.Борисов, О.В,Исаев, В.И.Константинов и В.М.Константиновский (53) 681.327.6(088.8) (56) 1. Авторское свидетельство СССР

М 1265857, кл. G 11 С 15/00, 1986.

2. Кохонен Т, Ассоциативные запоминающие устройства. M. Мир, 1982, с. 159. рис.

3.3.б. (54) ЯЧЕЙКА АССОЦИАТИВНОЙ ПАМЯТИ (57) Изобретение относится к вычислительной технике, в частности к устройствам хранения информации, и может быть использовано в устройствах цифровой ассо-. циативной обработки данных, в системах

- Ж 1718275 А1 распознавания образов, выполненных на узлах с большой степенью интеграции.

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

И-НЕ 2-6, элемент ИЛИ-НЕ 7, первый 8 и второй 9 3ileMeHTbl И, llepBblA 10 и второй 11 входы записи ячейки по столбцу, первый 12 и второй 13 входы записи ячейки по строке, первый 14 и второй 15 входы опроса ячейки по столбцу, первый 16 и второй 17 входы опроса ячейки по строке, выход 18 ассоциативного поиска ячейки по строке, выход 19 ассоциативного поиска ячейки по столбцу. 1 ил. ,1Ц 15 21 2

1718275

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

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

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

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

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

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

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

"1" соединен с выходом четвертого элемента И-НЕ, первый вход которого является первым входом записи ячейки по строке, а второй вход — первым входом записи ячейки по столбцу. введены первый и второй элементы И и элемент ИЛИ-НЕ, выход которого соединен с вторым входом установки триггера в "0", а первый и второй входы соединены соответственно с выходами первого и второго элементов И, первый и второй вхо5

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

Ячейка ассоциативной памяти содержит RS-триггер 1, прямой выход которого подключен к первым входам первого 2 и третьего 3 элементов И-НЕ, а инверсный выход — к первым входам второго 4 и пятого

5 элементов И-НЕ. Первый вход установки триггера 1 соединен с выходом четвертого элемента И-НЕ 6, а второй вход установки триггера 1 — с выходом элемента ИЛИ-Н Е 7, первый и второй входы которого подключены соответственно к выходам первого 8 и второго 9 элементов И, Первым входом 10 записи ячейки по столбцу является второй вход четвертого элемента И-НЕ 6 и первый вход первого элемента И 8, а вторым входом

11 записи ячейки по столбцу — второй вход второго элемента И 9. Первым входом 12 записи ячейки по строке является первый вход четвертого элемента И-HE 6 и второго элемента И 9, а вторым входом 13 записи ячейки по строке — второй вход первого элемента И 8. Первым 14 и вторым 15 входами опроса ячейки по столбцу являются соответственно вторые входы первого 2 и второго 4 элементов И-НЕ, а первым 16 и вторым 17 входами опроса ячейки по строке — соответственно вторые входы третьего 3 и пятого 5 элементов И-НЕ. Выходы первого 2 и второго 4 элементов И-НЕ объединены и являются выходом 18 ассоциативного -поиска ячейки по строке, а объединенные выходы третьего 3 и пятого 5 элементов И-НЕ являются выходом 19 ассоциативного поиска ячейки по столбцу, Кроме того, выход 18 ассоциативного поиска ячейки по строке, являющийся выходом указанных элементов

И-НЕ ячеек соответствующей строки ассоциативной памяти, через первый ограничительный элемент 20 подключен к входу 21 потенциала логической "1". Выход 19 ассоциативного поиска ячейки по столбцу, являющийся выходом вышеуказанных

1718275

45

55 элементов И-HE ячеек соответствующего столбца ассоциативной памяти, через второй ограничительный элемент 22 подключен к входу 21 потенциала логической "1".

Первый 20 и второй 22 ограничительные элементы могут быть выполнены в виде резисторов.

Ячейка ассоциативной памяти работает следующим образом.

В исходном положении триггер 1 установлен в одно из состояний в соответствии со значением бита записанной информации.

Ячейка ассоциативной памяти помимо хранения бита позволяет выполнять следующие операции: маскируемую запись по строке, маскируемую запись по столбцу, считывание по строке, считывание по столбцу, ассоциативный маскируемый поиск по строкам, ассоциативный маскируемый поиск по столбцам, Маскируемая запись по строке реализуется подачей на входы 12 и 13 комбинации сигналов "10", а на входы 10 и 11 — сочетания "10" при записи единицы, сочетания

"01" при записи нуля и комбинации "00" при маскировании записи. Указанные сигналы подаются на все входы 10 и 11 ячеек ассоциативной запоминающей матрицы (матрица на чертеже не показана).

Маскируемая запись по столбцу осущеетвляется подачей на входы 10 и 11 комбинации сигналов "10", а на входы 12 и 13— сочетания "10" при записи единицы, сочетания "01" при записи нуля и комбинации "00" при маскировании записи.

Считывание по строке реализуется подачей на первый 16 и второй 17 входы опроса по строке ячейки ассоциативной памяти комбинации сигналов "01". В этом случае, если триггер 1 установлен в.единичное состояние, то уровень логической "1" сохранится на выходах элементов И-НЕ 3 и 5 и на выходе 19. В противном случае (если триггер 1 установлен в нулевое состояние) на выходе элемента И-НЕ 5 появляется низкий уровень, обнуляющий выход 19.

Считывание по столбцу осуществляется подачей на первый 14 и второй 15 входы опроса по столбцу комбинации сигналов

"01". B этом случае, если триггер 1 установлен в единичное состояние, то уровень логической "1" сохраняется на выходах элементов И-НЕ 2 и 4 и на выходе 18. В противном случае (если триггер 1 установлен в нулевое состояние) на выходе элемента И-НЕ 4 появляется низкий уровень, обнуляющий выход 18.

Ассоциативный маскируемый поиск но строкам осуществляется подачей на входы

14 и 15 сочетания сигналов "01" при признаке опроса (т.е„при значении бита поиска), равном единице, и сочетания "10" при признаке опроса, равном нулю. Соответственно сигнал единичного уровня сохраняется на выходе 18 в случае совпадения признака опроса с битом, хранимым в ячейке ассоциативной памяти, и выход 18 обнуляется в противном случае. Маскирование поиска реализуется подачей комбинации сигналов

"00" на входы 14 и 15.

Ассоциативный маскируемый поиск по столбцам осуществляется подачей на входы

16 и 17 сочетания сигналов "01" при признаке опроса, равном единице, и сочетания

"10" при признаке опроса, равном нулю.

Соответственно сигнал единичного уровня сохраняется на выходе 19 в случае совпадения признака опроса.с битом, хранимым в ячейке ассоциативной памяти, и выход 19 обнуляется в противном случае. Маскирование поиска реализуется подачей комбинации сигналов "00" на входы 16 и 17.

Операции ассоциативного маскируемого поиска по строкам и ассоциативного маскируемого поиска по столбцам могут выполняться одновременно.

Таким образом, достигается цель увеличения производительности выполняемых операций в ассоциативной памяти на величину до 100;4 при использовании предлагаемых ячеек вместо базовых.

Формула изобретения

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

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

20

30

40

50

Составитель И. Огнев

Редактор Т. Юрчикова Техред M.Mîðãåíòàë Корректор Т. Палий

Заказ 885 Тираж Подписное

ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР

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

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

5 входом опроса ячейки по строке является второй вход пятого элемента И-НЕ, первый вход которого подключен к инверсному выходу триггера, выход пятого элемента И-НЕ является выходом ассоциативного поиска

10 ячейки по столбцу.