Ячейка ассоциативной памяти Советский патент 1992 года по МПК G11C15/00 

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

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

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

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

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

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

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

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

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

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

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

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

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

0 третьего 3 и пятого 5 элементов И-НЕ являются выходом 19 ассоциативного поиска ячейки по столбцу. Кроме того, выход 18 ассоциативного поиска ячейки по строке, являющийся выходом указанных элементов

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

элементов И-НЕ ячеек соответствующего столбца ассоциативной памяти, через второй ограничительный элемент 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. В этом случае, если триггер 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% при использовании предлагаемых ячеек вместо базовых.

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

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

выходы которых объединены и являются выходом ассоциативного поиска ячейки по строке, а вторые входы являются соответственно первым и вторым входами опроса ячейки по столбцу, при этом прямой выход

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

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

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

0

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

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