АССОЦИАТИВНАЯ ЗАПОМИНАЮЩАЯ МАТРИЦА Российский патент 2001 года по МПК G11C15/00 

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

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

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

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

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

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

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

На чертеже представлена схема ассоциативной запоминающей матрицы, состоящая из элементов памяти 1, логических блоков 2 по числу столбцов матрицы, а также адресных шин 3, первой 4 и второй 5 разрядных шин записи, первой 6 и второй 7 разрядных шин опроса, шин результатов опроса 8.

Каждый элемент памяти 1 содержит триггер 9, элементы И-НЕ с первого 10 по четвертый 13, элемент 2И-ИЛИ-НЕ 14, а также адресный вход 15, первый 16 и второй 17 разрядные входы записи, первый 18 и второй 19 разрядные входы опроса, выход результатов опроса 20, первый 21 и второй 22 разрядные выводы сравнения по совпадению элемента памяти соответствующего столбца матрицы, вход разрешения ассоциативного сравнения 23.

Каждый логический блок 2 содержит элементы ИЛИ с первого 24 по третий 26, а также первый 27 и второй 28 входы, разрядный вход задания режима опроса 29, выходы с первого 30 по третий 32.

На чертеже также показаны ограничительные элементы, выполненные в виде резисторов R, и иллюстрирующие реализацию функции "Монтажное И".

При маскируемой записи в матрицу по заданному адресу на первые 4 и вторые 5 разрядные шины записи и, следовательно, на входы 16 и 17 всех элементов памяти 1 поступает одна из следующих комбинаций сигналов: "10" - запись единицы; "01" - запись нуля; "00" - маскирование записи. Затем на соответствующую адресную шину 3 подается высокий логический уровень, инициирующий запись соответствующих значений по заданному адресу.

При считывании информации по заданному адресу на соответствующую адресную шину 3 подается высокий логический уровень, инициирующий чтение слова в инверсном коде с первых 21 разрядных выводов элементов памяти 1 соответствующей строки матрицы.

В режиме ассоциативного маскируемого поиска по внешнему поисковому аргументу все адресные шины 3 матрицы должны быть обнулены. На разрядные входы 29 задания режима опроса логических блоков 2 подается высокий логический уровень, а с первых 6 и вторых 7 разрядных шин опроса на первые 18 и вторые 19 разрядные входы опроса элементов памяти 1 поступает одна из следующих комбинаций сигналов (признаков сравнения): "10" - сравнение с нулем; "01" - сравнение с единицей; "00" - маскирование сравнения, инициируя сравнение с содержимым триггера соответствующего элемента памяти 1.

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

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

При этом если в триггерах 9 выбранных элементов памяти 1 какого-либо столбца матрицы хранятся лишь нули (единицы), то на выводах 21 и 22 всех элементов памяти 1 этого столбца матрицы установится сочетание сигналов "10" ("01") признак сравнения с нулем (единицей). В этом случае содержимое всех элементов памяти данного столбца матрицы будет сравниваться с единицей.

Если в триггерах 9 выбранных элементов памяти 1 какого-либо столбца матрицы хранятся как нули, так и единицы, то на выводах 21 и 22 всех элементов памяти 1 этого столбца матрицы установится сочетание сигналов "00". При этом на третьем выходе 32 соответствующего логического блока 2 установится уровень логического нуля, во-первых, блокирующий (маскирующий) сравнение в элементах 2И-ИЛИ-НЕ 14 всех элементов памяти 1 данною столбца матрицы и, во-вторых, индицирующий несовпадение содержимого элементов памяти 1 столбца матрицы, участвующих в формировании значения соответствующего разряда поискового аргумента.

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

Для осуществления этого режима при прочих прежних условиях на входах 29 логических блоков 2 должен быть установлен уровень логического нуля, а на разрядные шины опроса 6 и 7 подана одна из комбинаций сигналов: "10", "01", "00".

Подачей сочетания сигналов "00" на разрядные шины опроса 6, 7 (при "О" на входах 29) осуществляется внешнее маскирование сравнения в элементах 2И-ИЛИ- НЕ 14 всех элементов памяти 1 соответствующих столбцов матрицы.

При осуществлении совмещенного ассоциативного поиска для каждого столбца возможно индивидуальное задание режима: либо совмещенного ассоциативного поиска, либо ассоциативного поиска лишь по внешнему поисковому аргументу.

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

Источники информации
1. Ассоциативное запоминающее устройство. Патент РФ N 2045787, кл. G 11 C 15/00, 1995.

2. Ассоциативная запоминающая матрица. Патент РФ N 2065207, кл. G 11 C 15/00, 1996 (прототип).

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

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