Ассоциативная запоминающая матрица

 

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

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

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

1 с.п. ф-лы, 5 ил.

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

Известна информационно-поисковая система, содержащая блок памяти вхождений, блок памяти слов, блок управления, n блоков определения вхождений (патент RU 2199778 С1, МПК G06F 17/30, опубликован 2003.02.27).

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

Наиболее близким устройством к заявленному является ассоциативная запоминающая матрица, состоящая из n×m ассоциативных запоминающих элементов, содержащих n×m бит исходной битовой строки S, и коммутационных элементов, представляющих собой 1-n-полюсники (патент RU 2025797 С1, МПК G11C 15/00, опубликован 1994.12.30). Коммутационные элементы, с помощью загружаемого в них настроечного кода, обеспечивают статическую настраиваемую реконфигурацию соединительных элементов перед поиском.

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

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

Техническая задача решается тем, что в ассоциативную запоминающую матрицу, содержащую n×m ассоциативных запоминающих элементов, первые входы которых в соответствующих строках матрицы объединены и являются соответствующими адресными входами матрицы, первые выходы ассоциативных запоминающих элементов в соответствующих столбцах матрицы объединены и являются соответствующими информационными выходами матрицы, коммутационные элементы, входы которых подключены ко вторым выходам соответствующих ассоциативных запоминающих элементов, а выходы соответственно объединены и являются соответствующими выходами результатов опроса, дополнительно введены четвертые входы ассоциативных запоминающих элементов, подключенные к внешнему входу синхронизации "CLOCK", n×m элементов-селекторов, содержащих 2 мультиплексора, имеющих два входа данных и один адресный вход каждый, элемент И-НЕ и имеющих 4 входа и 2 выхода, первые и вторые входы которых являются соответственно первыми и вторыми информационными входами соответствующих столбцов матрицы, третьи входы подключены к первым выходам ассоциативных запоминающих элементов соответствующей строки матрицы, четвертые входы подключены к внешнему входу "РЕЖИМ", первые и вторые выходы являются соответственно вторыми и третьими информационными входами ассоциативных запоминающих элементов соответствующей строки матрицы, элементы И в структуру соответствующих ассоциативных запоминающих элементов, первые входы которых подключены к первым входам соответствующих ассоциативных запоминающих элементов, вторые входы подключены к четвертым входам соответствующих ассоциативных запоминающих элементов, маскирующий элемент, содержащий элемент И, двоичный счетчик и элемент ИЛИ-НЕ, первый вход которого подключен к внешнему входу синхронизации "CLOCK", второй вход - к внешнему входу "РЕЖИМ", третий вход - к внешнему входу "СБРОС", а выход является индикатором произошедших реконфигураций матрицы из двухмерного вида в одномерный и обратно, элемент И, первый вход которого подключен к выходу результата опроса n-й строки матрицы, второй вход - к выходу маскирующего элемента, а выход является маскируемым выходом опроса n-й строки матрицы, ограничительный резистор, соединенный с третьим входом nm-ого элемента-селектора и источником питания.

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

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

Задача поиска начал вхождений формулируется следующим образом. Пусть в общем двоичном алфавите ={0,1} заданы образец О и битовая строка S как последовательности бит длиной в m и n символов соответственно, при этом m<n. Требуется найти все позиции начал вхождений О в S.

Сущность традиционной задачи определения вхождений битового образца О в обрабатываемой битовой строке S сводится к поиску всех начал вхождений (начальных позиций) битового образца О, что в худшем случае приводит к n×m сравнениям битов и цикличности операции поиска, при этом осуществляется возврат на первый бит образца О для сравнения с очередным битом строки S при несовпадении. Последовательный характер поиска обусловлен одномерной структурой данных образца и битовой строки.

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

Ассоциативный поиск всех начал вхождений обеспечивается путем представления исходной битовой строки S длиной до p=n×m разрядов в виде двухмерной матрицы из n строк по m разрядов в каждой строке, где m соответствует разрядности битового образца О. При таком представлении битовой строки S битовый образец О длиной в m разрядов подается на информационные входы ассоциативной запоминающей матрицы и параллельно сравнивается по n строкам матрицы, что демонстрируется на фиг.1 для S=1100101011001100 и O=1001. Ассоциативный поиск всех начал вхождений состоит из m-1-циклов, включающих параллельное сравнение и сдвиг битовой строки на 1 разряд в сторону начальной позиции. В текущем цикле процесса поиска после сравнения - положительного (фиг.1в) или отрицательного (фиг.1а, 1д, 1ж) - выполняется сдвиг битовой строки S на 1 разряд в сторону начальной позиции (фиг.1б, 1г, 1е) и осуществляется следующий цикл параллельного сравнения образца О по n строкам матрицы. В случае положительного сравнения фиксируется начальная позиция одного из вхождений битового образца О в битовую строку S. При втором и последующих циклах параллельного сравнения результат опроса n-ой строки матрицы не учитывается, т.к. последний фрагмент битовой строки S не совпадает (меньше) с разрядностью битового образца О. Для обнаружения всех начал вхождений битового образца О в исходную битовую строку S потребуется не более чем m-1 сдвигов.

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

Матрица (фиг.2) состоит из n×m ассоциативных запоминающих элементов 1 (n - количество битовых строк, необходимых для представления входной битовой строки, m - количество разрядов битового образца) с входами с первого 2 по четвертый 5 и с выходами с первого 6 по второй 7, коммутационных элементов 10, представляющих собой 1-n-полюсники, элементов-селекторов 12 с входами с первого 13 по четвертый 16 и с выходами с первого 17 по второй 18, маскирующего элемента 36 с входами с первого 37 по третий 39 и с выходом 40, элемента И 44, первый вход которого подключен к выходу результата опроса n-й строки матрицы, второй вход - к выходу 40 маскирующего элемента 36, а выход является маскируемым выходом опроса n-й строки матрицы 11n, ограничительного резистора 27, соединенного с третьим входом 15 nm-ого элемента-селектора 12 и источником питания и имеет адресные входы 81÷8 n, первые 19 и вторые 20 информационные входы, внешний вход "РЕЖИМ", определяющий двумерный или одномерный вид структуры матрицы, внешний вход синхронизации "CLOCK", внешний вход "СБРОС", информационные выходы 91 ÷9m, выходы 111÷11n результатов опроса.

Ассоциативный запоминающий элемент 1 (фиг.3) состоит из RS-триггера 21 с инверсными входами установки в "1" и "0", элемента И 22, элементов И-НЕ с первого 23 по третий 25, элемента 2И-ИЛИ 26. Первый вход элемента И 22 подключен к первому входу 2 ассоциативного запоминающего элемента 1, второй вход элемента И 22 подключен к четвертому входу 5 ассоциативного запоминающего элемента 1, а выход элемента И 22 подключен к первому входу элемента И 25, ко второму входу элемента И-НЕ 23, ко второму входу элемента И-НЕ 24. Первый вход элемента И-НЕ 23 подключен ко второму входу 3 ассоциативного запоминающего элемента 1, а выход элемента И-НЕ 23 подключен к входу S RS-триггера 21. Первый вход элемента И-НЕ 24 подключен к третьему входу 4 ассоциативного запоминающего элемента 1, а выход элемента И-НЕ 24 подключен к входу R RS-триггера 21. Выход Q RS-триггера 21 подключен ко второму входу элемента И-НЕ 25, а также к первому входу элемента 2И-ИЛИ 26, выход RS-триггера 21 подключен к третьему входу элемента 2И-ИЛИ 26. Выход элемента И-НЕ 25 является первым выходом 6 ассоциативного запоминающего элемента 1. Второй вход элемента 2И-ИЛИ 26 подключен ко второму входу 3 ассоциативного запоминающего элемента 1, четвертый вход элемента 2И-ИЛИ 26 подключен к третьему входу 4 ассоциативного запоминающего элемента 1, а выход элемента 2И-ИЛИ 26 является вторым выходом 7 ассоциативного запоминающего элемента 1.

Коммутационный элемент 10 (фиг.3) состоит из регистра 28 и n-элементов И-НЕ 32 и имеет n-входов данных 29 регистра 28, входы сигналов записи 30 и установки в начальное состояние 31 регистра 28, n-выходов полученного результата опроса ассоциативного запоминающего элемента 1. Первый вход каждого из n-элементов И-НЕ 32 подключен ко второму выходу 7 ассоциативного запоминающего элемента 1, а второй вход каждого из n-элементов И-НЕ 32 подключен к соответствующему выходу данных регистра 28, а выход каждого из n-элементов И-НЕ 32 является соответствующим выходом коммутационного элемента 10.

На фиг.3 также представлены ограничительные элементы 27 в виде резисторов, подключенных к n-выходам коммутационного элемента 10, к первому выходу 6 ассоциативного запоминающего элемента 1 и к источникам питания.

Элемент-селектор 12 (фиг.4) состоит из двух мультиплексоров 33 и 34, имеющих два однобитовых входа данных и один однобитовый адресный вход каждый, двухвходового элемента И-НЕ 35. При этом адресные входы мультиплексоров 33 и 34 подключены к четвертым входам 16 соответствующих элементов-селекторов 12, т.е. к внешнему входу "РЕЖИМ". Первые входы данных мультиплексоров 33 подключены к первым входам 13 соответствующих элементов-селекторов 12, первые входы данных 14 мультиплексоров 34 подключены ко вторым входам соответствующих элементов-селекторов 12, вторые входы данных мультиплексоров 33 подключены к третьим входам 15 соответствующих элементов-селекторов 12 через инвертирующий элемент И-НЕ 35, вторые входы данных мультиплексоров 34 напрямую подключены к третьим входам 15 соответствующих элементов-селекторов 12, выходы мультиплексоров 33 и 34 являются соответственно первыми 17 и вторыми 18 выходами элементов-селекторов 12.

Маскирующий элемент 36 (фиг.5) состоит из двухвходового элемента И 41, двоичного счетчика 42 с разрядностью m, элемента ИЛИ-НЕ 43 с m-входами. Первый вход элемента И 41 подключен к первому входу 37 маскирующего элемента 36, второй вход элемента И 41 подключен ко второму входу 38 маскирующего элемента 36. Первый вход двоичного счетчика 43 подключен к выходу элемента И 41, второй вход двоичного счетчика 43 подключен к третьему входу маскирующего элемента 36, a m-выходов счетчика подключены к m-входам элемента ИЛИ-НЕ 43. Выход элемента ИЛИ-НЕ 43 подключен к выходу 40 маскирующего элемента 36.

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

При записи битовых данных в матрицу по заданному адресу строки матрицы на первые 19 и вторые 20 информационные входы матрицы и, следовательно, на первые 13 и вторые 14 входы всех элементов-селекторов 12 соответствующей строки матрицы поступает одна из следующих комбинаций сигналов: 10 - код единицы, 01 - код нуля, 00 - код маски. При этом на четвертый вход 16 соответствующих элементов-селекторов 12 подается сигнал "РЕЖИМ"=0, что осуществляет подключение первых 13 и вторых 14 входов элементов-селекторов 12 к первым 17 и вторым 18 выходам элементов-селекторов 12 и соответственно ко вторым 3 и третьим 4 информационным входам ассоциативных запоминающих элементов 1 соответствующей строки матрицы. Затем на соответствующий адресный вход 2 ассоциативных запоминающих элементов 1 соответствующей строки матрицы подается высокий логический уровень, на соответствующие четвертые входы 5 ассоциативных запоминающих элементов 1 соответствующей строки матрицы подается сигнал синхронизации "CLOCK"=1, инициируя тем самым запись фрагмента битовой строки в m разрядов по адресу строки матрицы, задаваемому по одному из входов 8 1÷8n.

При считывании битовых данных из матрицы по адресу, задаваемому по одному из входов 81÷8n, на первые 19 и вторые 20 информационные входы матрицы и, следовательно, на первые 13 и вторые 14 входы всех элементов-селекторов 12 соответствующей строки матрицы поступает следующая комбинация сигналов: 00 - код маски, что обеспечивает перевод RS-триггеров ассоциативных запоминающих элементов 1 соответствующей строки матрицы в режим хранения. При этом на четвертый вход 16 соответствующих элементов-селекторов 12 подается сигнал "РЕЖИМ"=0, что осуществляет подключение первых 13 и вторых 14 входов элементов-селекторов 12 к первым 17 и вторым 18 выходам элементов-селекторов 12 и соответственно ко вторым 3 и третьим 4 входам ассоциативных запоминающих элементов 1 соответствующей строки матрицы. Затем на соответствующие адресные входы 2 ассоциативных запоминающих элементов 1 соответствующей строки матрицы подается высокий логический уровень, на соответствующие четвертые входы 5 ассоциативных запоминающих элементов 1 соответствующей строки матрицы подается сигнал синхронизации "CLOCK"=1, инициируя тем самым считывание m-разрядного фрагмента битовой строки в инверсном коде с первых выходов 6 ассоциативных запоминающих элементов 1 соответствующей строки матрицы.

Перед выполнением ассоциативного поиска выполняется настройка ассоциативной запоминающей матрицы, заключающаяся в предварительной записи в регистры 28 всех коммутационных элементов 10 настроечных кодов, обеспечивающих подключение вторых выходов 7 соответствующих ассоциативных запоминающих элементов 1 к соответствующим выходам 11 результатов опроса. В общем случае настроечный код может быть как униполярным, обеспечивающим подключение выхода 7 ассоциативного запоминающего элемента 1 к одному выбранному выходу 11 результатов опроса, так и k-полярным (k=1n), где k - число выходов 11 результатов опроса матрицы, к которым подключается выход 7 ассоциативного запоминающего элемента 1. В рассматриваемой ассоциативной запоминающей матрице при поиске начал вхождений образца по строкам матрицы настроечный код коммутационных элементов 10 соответствующих строк матрицы имеет следующий вид: 291=100..0, 292=010..0, ...., 29n =000..1, что позволяет получить инверсное значение выходов 7 соответствующих ассоциативных запоминающих элементов 1 на выходах 11 результатов опросов соответствующих строк матрицы.

Также перед выполнением ассоциативного поиска на третий вход 39 маскирующего элемента 36 подается сигнал "СБРОС"=1, инициируя сброс двоичного счетчика 42 и получение на выходе 40 маскирующего элемента 36 значения логической "1".

При осуществлении циклического ассоциативного маскируемого поиска начал вхождений на первые 19 и вторые 20 информационные входы матрицы и, следовательно, на первые 13 и вторые 14 входы всех элементов-селекторов 12 соответствующей строки матрицы поступает одна из следующих комбинаций сигналов: 10 - код единицы, 01 - код нуля. При этом на четвертый вход 16 соответствующих элементов-селекторов 12 подается сигнал "РЕЖИМ"=0, что осуществляет подключение первых 13 и вторых 14 входов элементов-селекторов 12 к первым 17 и вторым 18 выходам элементов-селекторов 12 и соответственно ко вторым 3 и третьим 4 входам ассоциативных запоминающих элементов соответствующей строки матрицы. Затем на соответствующие четвертые входы 5 ассоциативных запоминающих элементов 1 соответствующей строки матрицы подается сигнал синхронизации "CLOCK=1", инициируя сравнение с содержимым триггера 21 соответствующего ассоциативного запоминающего элемента 1. Если происходит совпадение, то второй выход 7 ассоциативного запоминающего элемента 1 сохраняет уровень логического "0" и, следовательно, на выходе(ах) 11 результатов опроса матрицы, к которому(ым) подключен выход 7 этого ассоциативного запоминающего элемента 1, сохраняется уровень логической "1". Если происходит несовпадение, то на выходе 7 такого ассоциативного запоминающего элемента 1 появляется уровень логической "1", устанавливающий в "0" этот (эти) выход(ы) 11. При этом если была произведена хотя бы одна операция реконфигурации матрицы, на выходе 11n результатов опроса ассоциативных запоминающих элементов 1 n-ой строки матрицы получается значение логического "0" в результате установки на выходе маскирующего элемента 36 значения логического "0".

При осуществлении операции реконфигурации матрицы на третьи входы 15 всех элементов-селекторов 12 соответствующей строки матрицы подается сигнал с первых выходов 6 соответствующих ассоциативных запоминающих элементов 1, на четвертые входы 16 всех элементов-селекторов 12 соответствующей строки матрицы подается сигнал "РЕЖИМ"=1, что позволяет получить инверсные и прямые значения сигналов с третьих входов 15 элементов-селекторов 12 на соответственно первых 17 и вторых 18 выходах элементов-селекторов 12, подключенных соответственно ко вторым 3 и третьим 4 входам ассоциативных запоминающих элементов 1 соответствующей строки матрицы. Затем на соответствующие четвертые входы 5 ассоциативных запоминающих элементов 1 всех строк матрицы подается сигнал синхронизации "CLOCK"=1, инициируя запись новых логических уровней ассоциативных запоминающих элементов 1 из предыдущих по строке/столбцу матрицы ассоциативных запоминающих элементов 1 и инкремент двоичного счетчика 42 маскирующего элемента 36. Тем самым осуществляется переход матрицы из двухмерного вида в одномерный и реконфигурация матрицы по направлению к первому элементу.

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

Ассоциативная запоминающая матрица, содержащая n×m ассоциативных запоминающих элементов, первые входы которых в соответствующих строках матрицы объединены и являются соответствующими адресными входами матрицы, первые выходы ассоциативных запоминающих элементов в соответствующих столбцах матрицы объединены и являются соответствующими информационными выходами матрицы, коммутационные элементы, входы которых подключены ко вторым выходам соответствующих ассоциативных запоминающих элементов, а выходы соответственно объединены и являются соответствующими выходами результатов опроса, отличающаяся тем, что в нее введены четвертые входы ассоциативных запоминающих элементов, подключенные к внешнему входу синхронизации "CLOCK", n×m элементов-селекторов, содержащих 2 мультиплексора, имеющих два входа данных и один адресный вход каждый, элемент И-НЕ и имеющих 4 входа и 2 выхода, первые и вторые входы которых являются соответственно первыми и вторыми информационными входами соответствующих столбцов матрицы, третьи входы подключены к первым выходам ассоциативных запоминающих элементов соответствующей строки матрицы, четвертые входы подключены к внешнему входу "РЕЖИМ", первые и вторые выходы являются соответственно вторыми и третьими информационными входами ассоциативных запоминающих элементов соответствующей строки матрицы, элементы И в структуру соответствующих ассоциативных запоминающих элементов, первые входы которых подключены к первым входам соответствующих ассоциативных запоминающих элементов, вторые входы подключены к четвертым входам соответствующих ассоциативных запоминающих элементов, маскирующий элемент, содержащий элемент И, двоичный счетчик и элемент ИЛИ-НЕ, первый вход которого подключен к внешнему входу синхронизации "CLOCK", второй вход - к внешнему входу "РЕЖИМ", третий вход - к внешнему входу "СБРОС", а выход является индикатором произошедших реконфигураций матрицы из двухмерного вида в одномерный и обратно, элемент И, первый вход которого подключен к выходу результата опроса n-й строки матрицы, второй вход - к выходу маскирующего элемента, а выход является маскируемым выходом опроса n-й строки матрицы, ограничительный резистор, соединенный с третьим входом nm-го элемента-селектора и источником питания.



 

Наверх