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

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

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

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

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

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

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

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

На фиг. 1 представлена схема ассоциативной запоминающей матрицы, на фиг. 2 - пример реализации ассоциативной ячейки.

Ассоциативная запоминающая матрица (фиг. 1) состоит из ассоциативных ячеек 1, каждая из которых содержит узел анализа входной информации 2, узел памяти 3, первую 4 и вторую 5 схемы ассоциативного сравнения, первый 6 и второй 7 буферные узлы, первый 8 и второй 9 коммутаторы, повторители сигналов с первого 10 по четвертый 13. В состав матрицы также входят: 14 - адресная шина; 15 - разрядная шина записи; 16-шина активизации столбца; 17- адресная шина задания режима сравнения; 18 - разрядная шина задания режима сравнения; 19- шина опроса по столбцам; 20- шина опроса по строкам; 21, 22, 23, 24 - соответственно шины результатов ассоциативного опроса: по направлению главной диагонали, по строкам, по столбцам и по направлению побочной диагонали матрицы.

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

На фиг. 2 показан пример реализации ассоциативной ячейки 1 матрицы. Узел анализа входной информации 2 состоит из первого 25 и второго 26 элементов 2И-НЕ. Узел памяти 3 может быть реализован на R- S-триггере 27. Первая 4 и вторая 5 схемы ассоциативного сравнения выполнены соответственно на элементах 2И-ИЛИ-НЕ 28 и 29, реализующих сравнение по критерию "равно". Каждый из буферных узлов 6 и 7 содержит первый 30 и второй 31 однонаправленные буферные элементы (повторители сигналов) с выходами, устанавливаемыми в высокоимпедансное ("третье") состояние, в котором они не оказывают влияние на общее состояние тех шин, к которым они подключены.

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

В режиме сравнения выделенной строки матрицы с поисковым аргументом-столбцом (в случае их произвольного сдвига друг относительно друга) элементы 30 и 31 узла 6 работают как повторители.

Аналогичные пояснения можно привести и для назначения элементов 30, 31 узла 7 при осуществлении режимов: (а) параллельного ассоциативного поиска по столбцам и (б) сравнения выделенного столбца матрицы с поисковым аргументом-строкой.

Узлы 6 и 7 управляются уровнями сигналов соответственно с адресной шины 14 и шины активизации столбца 16. Коммутаторы 8 и 9 представляют собой двухканальные двухразрядные мультиплексоры соответственно 32 и 33, позволяющие передавать на выход сигналы с первой или второй групп входов, в зависимости от уровней сигналов на входах управления, подаваемых соответственно с адресной шины задания режима сравнения 17 и разрядной шины задания режима сравнения 18. Повторителями сигналов с первого 10 по четвертый 13 являются буферные формирователи с открытым коллектором соответственно 34-37 (например, элементы "лог. И"), подключение которых к соответствующим шинам результатов ассоциативного опроса 21-24 позволяет реализовать в матрице функции "Монтажного И" при объединении соответствующих выходов ассоциативных ячеек матрицы по заданным направлениям. На фиг. 2 также представлены ограничительные элементы 38 в виде резисторов.

При записи информации в матрицу по заданному адресу на разрядные шины записи 15 поступает одна из следующих комбинаций сигналов: "01" - код записи нуля, "10" - код записи единицы, "00" - код маскирования записи. И при подаче высокого логического уровня на соответствующую адресную шину 14 записываемое слово фиксируется по заданному адресу.

Для осуществления режима параллельного ассоциативного поиска по строкам уровень логического "О" должен быть подан: (а) на шины 14, устанавливая выходы элементов 30 и 31 узла 6 всех ассоциативных ячеек матрицы в высокое импедансное состояние; (б) на шины 17, подключая входы первой группы мультиплексора 32 (выходы триггера 27) к его выходам. На шины опроса по строкам 20 поступает одна из следующих комбинаций сигналов: "10" - сравнение с нулем, "01" - сравнение с единицей, "00" -маскирование сравнения. При совпадении информации, хранимой в триггере 27, с признаком опроса выход элемента 2И-ИЛИ-НЕ 28 сохранит высокий уровень и обнулится в противном случае, устанавливая на шинах 21 и 22 уровень логического "О".

Для осуществления режима параллельного ассоциативного поиска по столбцам уровень логического "О" должен быть подан: (а) на шины 16, устанавливая выходы элементов 30 и 31 узла 7 всех ассоциативных ячеек матрицы в высокое импедансное состояние; (б) на шины 18, подключая входы первой группы мультиплексора 33 (выходы триггера 27) к его выходам. На шины опроса по столбцам 19 поступает одна из следующих комбинаций сигналов: "10" - сравнение с нулем, "01" - сравнение с единицей, "00" -маскирование сравнения. При совпадении информации, хранимой в триггере 27, с признаком опроса выход элемента 2И-ИЛИ-НЕ 29 сохранит высокий уровень, и обнулится в противном случае, устанавливая на шинах 23 и 24 уровень логического "О".

Режимы параллельного ассоциативного поиска по строкам и столбцам матрицы могут быть совмещены.

Для определения сходства записанной в матрицу строки с поисковым аргументом-столбцом в случае их произвольного сдвига друг относительно друга должны быть выполнены следующие условия. На все шины 16, а также шины 14 матрицы кроме сравниваемой строки подается уровень логического "О". Таким образом на шинах 20 в качестве признака сравнения установится аргумент, соответствующий выделенной строке. На всех шинах 17 должен быть установлен уровень логической "1", благодаря чему будет инициировано сравнение признаков сравнения с соответствующих шин 19ис шин 20 в элементах 2И-ИЛИ-НЕ 28 всех ячеек матрицы. Эта операция сравнения, как и другие, выполняется за одно обращение к ассоциативной матрице.

В результате действия указанных сигналов элементы 28 ассоциативного сравнения всех ассоциативных ячеек матрицы (как, впрочем, и элементы 29) используются для сравнения только двух объектов, в данном случае, поискового аргумента-столбца и выделенной строки матрицы.

Если в результате сравнения не произойдет обнуления какой-либо шины 21 результатов ассоциативного опроса по направлению главной диагонали, то, значит эти объекты совпадают. Причем на соседней с любой рассматриваемой шиной 21 формируется результат ассоциативного сравнения выделенной строки матрицы со сдвинутым на один компонент (бит, в данном случае) поисковым аргументом-столбцом, относительно рассматриваемого результата сравнения. Разница (L-I) определяет сдвиг совпавших объектов друг относительно друга, где I - номер выделенной строки матрицы, а L - номер диагонали матрицы с не обнуленной в результате ассоциативного опроса шиной 21, параллельной главной диагонали.

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

Если в результате сравнения не произойдет обнуления какой-либо шины 24 результатов ассоциативного опроса по направлению побочной диагонали, то значит, эти объекты совпадают. А разница (M-I) определяет их сдвиг друг относительно друга, где M - номер диагонали матрицы с не обнуленной в результате ассоциативного опроса шиной 24, параллельной побочной диагонали.

Для определения сходства объектов: записанного в матрицу столбца и поискового аргумента-строки в случае их произвольного сдвига друг относительно друга должны быть выполнены следующие условия. На все шины 14, а также шины 16 матрицы кроме сравниваемого столбца подается уровень логического "О". Таким образом, на шинах 19 в качестве признака сравнения установится аргумент, соответствующий выделенному столбцу. На всех шинах 17 должен быть установлен уровень логической "1", благодаря чему будет инициировано сравнение признаков сравнения с соответствующих шин 19 и с шин 20 в элементах 2И-ИЛИ-НЕ 28 всех ячеек матрицы.

Если в результате сравнения не произойдет обнуления какой-либо шины 21 результатов ассоциативного опроса по направлению главной диагонали, то значит, эти объекты совпадают. А разница (L-J) определяет их сдвиг друг относительно друга, где J - номер выделенного столбца матрицы.

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

Если в результате сравнения не произойдет обнуления какой-либо шины 24 результатов ассоциативного опроса по направлению побочной диагонали, то значит, эти объекты совпадают. А разница (M-J) определяет их сдвиг друг относительно друга.

Для одновременного (за одно обращение к матрице) определения как прямого сходства самих поисковых аргументов - строки и столбца - между собой, так и в случае, если один из них представлен в зеркально отображенной форме, при их возможном сдвиге друг относительно друга все шины 14 и 16 должны быть обнулены, а на всех шинах 17 и 18 матрицы установлен уровень логической "1". Если в результате сравнения эти аргументы совпадут, то в первом случае сдвиг их друг относительно друга равен L, а во втором - M.

Изобретение относится к вычислительной технике, в частности, к устройствам хранения информации, и может найти приме нение в специализированных системах хранения и обработки изображений, в ассоциативных параллельных процессорах при решении информационно-логических задач, задач поиска и сортировки данных, в устройствах обработки сигналов в реальном масштабе времени. Целью изобретения является увеличение эффективности определения сходства записанной в матрицу информации с поисковыми аргументами, а также поисковых аргументов между собой, представленных как в прямой, так и в зеркально отображенной форме, в случае их произвольного сдвига друг относительно друга за счет увеличения возможностей покомпонентного ассоциативного сравнения в матрице. Ассоциативная запоминающая матрица состоит из ассоциативных ячеек 1, каждая из которых содержит узел анализа входной информации 2, узел памяти 3, первую 4 и вторую 5 схемы ассоциативного сравнения, первый 6 и второй 7 буферные узлы, первый 8 и второй 9 коммутаторы, повторители сигналов с первого 10 по четвертый 13. В состав матрицы также входят: 14 - адресная шина; 15 - разрядная шина записи; 16 - шина активизации столбца; 17 - адресная шина задания режима сравнения; 18 - разрядная шина задания режима сравнения; 19 - шина опроса по столбцам; 20 - шина опроса по строкам; 21, 22, 23, 24 - соответственно шины результатов ассоциативного опроса: по направлению главной диагонали, по строкам, по столбцам и по направлению побочной диагонали матрицы. 2 ил.

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