СПОСОБ ПАРАЛЛЕЛЬНОГО ПОИСКА И ЗАМЕНЫ СТРОКИ И ОДНОРОДНАЯ ЗАПОМИНАЮЩАЯ МАТРИЦА ДЛЯ ЕГО РЕАЛИЗАЦИИ Российский патент 2014 года по МПК G11C15/00 

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

Известен способ реализации замены строки (Эйсымонт Л.К. Компьютеры для обработки символьной информации / Л.К. Эйсымонт // Зарубежная радиоэлектроника. - 1990. - №4. - С.3-28), заключающийся в реализации операции замены строки на одномерной списковой структуре путем логической вставки символов в конец списка и соответствующем изменении указателей элементов списка. Недостатком данного способа являются избыточные затраты времени на исключение из одномерной списковой структуры логически не адресуемых элементов, связанные с необходимостью последовательного просмотра всех элементов списка.

Известно устройство поиска и замены произвольных вхождений в словах текста, содержащее блок памяти слов и подстановок, блок памяти вхождений, компаратор, блок хранения адреса вхождений, блок управления (патент №RU 2250493 C2, МПК G06F 17/30, опубликован 2005.04.20). Недостатком этого устройства является последовательное сравнение анализируемых символов и последовательная замена символов подстановки с помощью реверсивных регистров сдвига, что приводит к непродуктивным затратам времени на реализацию операций поиска и замены.

Также известно устройство параллельного поиска и замены вхождений в обрабатываемых словах, содержащее блок памяти вхождений, блок памяти обрабатываемых слов, блок анализа поиска, блок памяти замены, блок замены, блок хранения результата (патент №RU 2296366 C1, МПК G06F 17/30, опубликован 2007.03.27). Недостатками этого устройства являются избыточные аппаратные затраты на отдельные блоки анализа поиска и замены, реализующие операции поиска вхождений и замены, а также избыточные затраты времени на возвратную запись модифицированного фрагмента или фрагмента слова из регистра замены в основное ОЗУ.

Наиболее близким к предлагаемому способу является способ (патент №84615, МПК G11C 15/00, опубликован. 10.07.2009), заключающийся в циклической реконфигурации исходной структуры данных из одномерного в двумерный вид и установлении отношений следования между элементами структуры данных, что позволяет совмещать последовательные и параллельные процессы над всеми элементами структуры данных. Недостатком данного подхода является ограниченность реализации операции замены строки-образца на строку-модификатор в обрабатываемой исходной строке ввиду отсутствия возможности локальной вставки элементов в строку или локального удаления элементов строки, что необходимо при проведении операции замены.

Наиболее близким устройством к заявленному является ассоциативная запоминающая матрица (патент №84615, МПК G11C 15/00, опубликован. 10.07.2009), состоящая из n×m ассоциативных запоминающих элементов, содержащих n×m бит исходной битовой строки S длиной k=n×m бит, n×m коммутационных элементов, представляющих собой 1-n-полюсники, n×m элементов-селекторов, маскирующего элемента, элемента И. При проведении ассоциативного поиска обеспечивается гибкая реконфигурация ассоциативной запоминающей матрицы за счет динамического перестроения соединений ассоциативных запоминающих элементов матрицы по направлению к первому элементу и повышение быстродействия операции поиска всех вхождений битового образца в битовую строку за счет исключения операций повторной загрузки данных в ассоциативную матрицу.

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

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

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

Техническая задача решается тем, что в однородную запоминающую матрицу для параллельного поиска и замены строки (далее - матрицу), содержащую n×m ассоциативных запоминающих элементов, четвертые входы ассоциативных запоминающих элементов подключены к внешнему входу синхронизации "CLOCK", первые выходы ассоциативных запоминающих элементов в соответствующих столбцах матрицы объединены и являются соответствующими информационными выходами матрицы, n×m коммутационных элементов, входы которых подключены ко вторым выходам соответствующих ассоциативных запоминающих элементов, а выходы коммутационных элементов соответственно объединены и являются соответствующими выходами результатов опроса, n×m элементов-селекторов, первые и вторые входы которых являются соответственно первыми и вторыми информационными входами матрицы в соответствующих столбцах, третьи входы элементов-селекторов подключены к первым выходам ассоциативных запоминающих элементов соответствующей строки матрицы, при этом третьи входы элементов-селекторов крайнего правого столбца матрицы подключены к первым выходам соответствующих ассоциативных запоминающих элементов крайнего левого столбца матрицы, расположенных строкой ниже, четвертые входы элементов-селекторов подключены к внешнему входу "РЕЖИМ", первые и вторые выходы n×m элементов-селекторов являются соответственно вторыми и третьими информационными входами ассоциативных запоминающих элементов соответствующей строки матрицы, маскирующий элемент, первый вход которого подключен к внешнему входу синхронизации "CLOCK", второй вход - к внешнему входу "РЕЖИМ", третий вход - к внешнему входу "СБРОС", а выход является индикатором произошедших реконфигураций матрицы из двухмерного вида в одномерный и обратно, элемент И, первый вход которого подключен к выходу результата опроса n-й строки матрицы, второй вход - к выходу маскирующего элемента, а выход является маскируемым выходом опроса n-й строки матрицы, ограничительный резистор, соединенный с третьим входом nm-го элемента-селектора и источником питания, дополнительно введен преобразователь кода, имеющий первый однобитовый управляющий вход, второй однобитовый управляющий вход, третий информационный вход разрядностью n бит, информационный выход разрядностью n бит и состоящий из n ячеек, на первый вход преобразователя кода поступает внешний сигнал «СТАРТ 1», на второй вход преобразователя кода поступает внешний сигнал «СТАРТ 2», третьи входы являются внешними адресными входами матрицы, а выходы преобразователя кода являются внутренними адресными входами, каждый из которых подается на первые входы ассоциативных запоминающих элементов в соответствующей строке матрицы, каждая ячейка преобразователя кода, кроме 1-й и n-й ячеек, имеет три однобитовых входа и три однобитовых выхода, первый вход i-й ячейки соединен с первым выходом i-1-й ячейки (i=2÷n), а на первый вход 1-й ячейки подается внешний сигнал «СТАРТ 1», второй вход j-й ячейки соединен с вторым выходом j+1-й ячейки (j=1÷n-1), а на второй вход n-й ячейки подается внешний сигнал «СТАРТ 2», информационные входы преобразователя кода являются третьими входами n ячеек, информационные выходы преобразователя кода являются третьими выходами n ячеек.

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

Задача замены строки формулируется следующим образом. Пусть в рабочем алфавите A={0,1} заданы объекты:

- строка-образец О длиной m символов, где О∈А^*, О=o₁o₂…o_m;

- строка-модификатор P длиной r символов, где P∈A^*, P=p₁p₂…p_r, 0<r≤2m;

- обрабатываемая строка S длиной k символов, где S∈A^*, S=s_1s2…s_k, (k≤n·m), n - натуральное число.

Требуется осуществить замену вхождения O на P в S, т.е. разработать такой алгоритм, что справедливо

∃i((O(1,m)=S(i,i+m-1))|(S=s₁s₂…s_i-1p₁p₂…p_rs_i+m…s_k), 1≤i≤w, w=k-m+1,

где k>0, m>0, w>0.

При реализации операции замены подстрок следует рассмотреть три варианта соотношения длин образца O и модификатора P:

1) m<r;

2) m=r;

3) m>r.

Первый вариант (m<r) включает последовательность шагов замещения, вставки и удаления символов из обрабатываемой строки, второй и третий варианты основаны на процессах замещения или удаления символов из обрабатываемой строки соответственно. Данное обстоятельство позволяет рассматривать первый вариант, как общий случай реализации операции замены подстрок.

Параллельная замена строки обеспечивается путем представления исходной битовой строки S длиной до k=n×m разрядов в виде двухмерной матрицы из n строк по m разрядов в каждой строке, где m соответствует разрядности битового образца. На фиг.1 представлено пошаговое выполнение операции замены для случая m<r при S=1101100111100110, O=1001 и P=110001. Модификатор P представляется в виде двух подстрок P₁, P₂ по m символов каждый. При этом выравнивание символов в P₂ выполняется по правому краю, а не заполненные разряды P₂ дополняются 0 (на фиг.1 такие разряды для наглядности отмечены символом «x»).

Параллельная замены строки на матрице реализуется следующим образом. Битовая подстрока P₁ длиной в m символов подается на информационные входы матрицы и в параллельном коде замещает данные в i-й строке матрицы, где i-номер строки матрицы, выбранной для операции замены. Управление номером строки матрицы осуществляется на основе внешней маски строк M₁, содержащей единственную логическую «1» в i-ой позиции (i=2 на фиг.1а). После замещения первой подстроки P₁ выполняется загрузка нового значения маски M₁ (фиг.1б), которая своими логическими «1» выделяет «верхнюю» часть матрицы. На основе установленного значения маски M₁ с подачей m тактовых импульсов выполняется сдвиг влево на m бит над элементами строки S только в выделенной части матрицы (фиг.1в). Процессы, отраженные на фиг.1в, приводят к освобождению i-ой строки матрицы для дальнейших преобразований, а выдвигаемые первые m символов строки S поступают на информационный выход матрицы.

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

Заключительный шаг операции замены подстрок связан с загрузкой нового значения маски строк M₁ (фиг.1д), которая своими логическими «1» выделяет «нижнюю» часть матрицы. На основе установленного значения маски M₁ с подачей 2m-r тактовых импульсов выполняется сдвиг влево на 2m-r бит над элементами строки S только в выделенной части матрицы (фиг.1е). Процессы, отраженные на фиг.1е, приводят к удалению 2m-r незначащих разрядов из i-ой строки матрицы и формированию корректного результата.

В случае, если r=m, то операция замены строки сводится лишь к выполнению шага замещения в параллельном коде модификатора Р вместо образца О (фиг.1а). В случае, если r<m, то операция замены строки выполняется в два шага: шаг замещения строки-образца на строку-модификатор (фиг.1а) и шаг сдвига влево на m-r бит над элементами строки S только в «нижней» части матрицы (фиг.1е).

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

Матрица (фиг.2) состоит из n×m ассоциативных запоминающих элементов 1 (n - количество битовых строк, необходимых для представления входной битовой строки, m - количество разрядов битового образца) с входами с первого 2 по четвертый 5 и с выходами с первого 6 по второй 7, n×m коммутационных элементов 10, представляющих собой 1-n-полюсники, n×m элементов-селекторов 12 с входами с первого 13 по четвертый 16 и с выходами с первого 17 по второй 18, маскирующего элемента 36 с входами с первого 37 по третий 39 и с выходом 40, элемента И 44, первый вход которого подключен к выходу результата опроса n-й строки матрицы, второй вход - к выходу 40 маскирующего элемента 36, а выход является маскируемым выходом опроса n-й строки матрицы 11_n, ограничительного резистора 27, соединенного с третьим входом 15 nm-го элемента-селектора 12 и источником питания, преобразователя кода 45, состоящего из ячеек 53₁÷53_n, каждая ячейка 53₂÷53_n-1 имеет первый 47, второй 50 и третий 49 входы, а также первый 51, второй 48 и третий 52 выходы, ячейка 53₁ имеет такие же входы и выходы, как и выше обозначенные ячейки 53₂÷53_n-1, кроме второго выхода 48, ячейка 53_n имеет такие же входы и выходы, как и выше обозначенные ячейки 53₂÷53_n-1, кроме первого выхода 51, матрица имеет внешние адресные входы 46₁÷46_n, внутренние адресные входы 8₁÷8_n, первые 19 и вторые 20 информационные входы, внешний вход "РЕЖИМ", определяющий двумерный или одномерный вид структуры матрицы, внешний вход синхронизации "CLOCK", внешний вход "СБРОС", информационные выходы 9₁÷9_m, выходы 11₁÷11_n результатов опроса, внешний управляющий вход «СТАРТ 1», который соединен с первым входом 47 ячейки 53₁, внешний управляющий вход «СТАРТ 2», который соединен со вторым входом 50 ячейки 53_n.

Ассоциативный запоминающий элемент (фиг.3) 1 строго соответствует устройству-прототипу в структурном и в функциональном отношении и состоит из 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, выход Q RS-триггера 21 подключен к третьему входу элемента 2И-ИЛИ 26. Выход элемента И-НЕ 25 является первым выходом 6 ассоциативного запоминающего элемента 1. Второй вход элемента 2И-ИЛИ 26 подключен ко второму входу 3 ассоциативного запоминающего элемента 1, четвертый вход элемента 2И-ИЛИ 26 подключен к третьему входу 4 ассоциативного запоминающего элемента 1, а выход элемента 2И-ИЛИ 26 является вторым выходом 7 ассоциативного запоминающего элемента 1.

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

На фиг.4 также представлены ограничительные элементы 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, а m-выходов счетчика подключены к m-входам элемента ИЛИ-НЕ 43. Выход элемента ИЛИ-НЕ 43 подключен к выходу 40 маскирующего элемента 36.

Преобразователь кода (фиг.6) состоит из однородных ячеек 53₁÷53_n, каждая из которых состоит из двухвходовых элементов И 54, И 55 и трехвходового элемента ИЛИ 56. Первый вход элемента И 54 подключен ко второму внешнему входу 50 ячейки 53, второй вход элемента И 54 подключен инверсно к третьему внешнему входу 49 ячейки 53. Выход элемента И 54 является вторым внешним выходом 48 ячейки 53 и подключен к первому входу элемента ИЛИ 56. Первый вход элемента И 55 подключен к первому внешнему входу 47 ячейки 53, второй вход элемента И 55 инверсно подключен к третьему внешнему входу 49 ячейки 53. Выход элемента И 55 является первым внешним выходом 51 ячейки 53 и подключен к третьему входу элемента ИЛИ 56, а выход элемента ИЛИ 56 является третьим внешним выходом 52 ячейки 53. Второй вход элемента ИЛИ 56 подключен к третьему внешнему входу 49 ячейки 53. Для ячейки 53₁ на первый внешний вход 47 подается внешний сигнал «СТАРТ 1», а для ячейки 53_n на второй внешний вход 50 подается внешний сигнал «СТАРТ 2».

Сущность динамической реконфигурации, воплощенная на фиг.2, сводится к подключению первых 13 и вторых 14 входов или третьих входов 15 элементов-селекторов 12 к их выходам 17 и 18 соответственно в зависимости от значения внешнего входа РЕЖИМ. Если вход РЕЖИМ=0, то к выходам 17 и 18 подключаются входы 13 и 14 соответственно, т.е. обеспечивается ассоциативный поиск вхождений или запись в параллельном коде модификатора на двумерном представлении S. Если вход РЕЖИМ=1, то к выходам 17 и 18 подключаются вход 15, т.е. обеспечивается сдвиг влево на одномерном представлении S. Элементы-селекторы 12 (фиг.3) содержат два мультиплексора 33 и 34, которые обеспечивают ввод в ассоциативные запоминающие элементы 1 бит образца O (для ассоциативного поиска вхождений), бит модификатора P (для замещения/вставки в параллельном коде) или бит от соседнего справа ассоциативного запоминающего элемента (для сдвига влево).

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

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

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

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

Также перед выполнением ассоциативного поиска на третий вход 39 маскирующего элемента 36 подается сигнал "СБРОС"=1, инициируя сброс двоичного счетчика 42 и получение на выходе 40 маскирующего элемента 36 значения логической "1". На внешние входы «СТАРТ 1» и «СТАРТ 2» преобразователя кода 45 подаются значения логического «0», что приводит к подключению третьих входов 46₁÷46_n преобразователя кода к внутренним адресным входам 8₁÷8_n матрицы со значениями 1…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. При этом если была произведена хотя бы одна операция реконфигурации матрицы, на выходе 11_n результатов опроса ассоциативных запоминающих элементов 1 n-ой строки матрицы получается значение логического "0" в результате установки на выходе маскирующего элемента 36 значения логического "0".

Перед выполнением операции реконфигурации на внешние входы «СТАРТ 1» и «СТАРТ 2» преобразователя кода 45 подаются значения логического «0», что приводит к подключению третьих входов 46₁÷46_n преобразователя кода к внутренним адресным входам 8₁÷8_n матрицы со значениями 1…1, которые разрешают вести реконфигурацию по всем строкам матрицы.

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

Затем на соответствующие четвертые входы 5 ассоциативных запоминающих элементов 1 всех строк матрицы подается сигнал синхронизации "CLOCK"=1, инициируя запись новых логических уровней ассоциативных запоминающих элементов 1 из предыдущих по строке/столбцу матрицы ассоциативных запоминающих элементов 1 и инкремент двоичного счетчика 42 маскирующего элемента 36. Тем самым осуществляется переход матрицы из двухмерного вида в одномерный вид и сдвиг влево элементов матрицы по направлению к первому элементу.

Состояние замены осуществляется в четыре этапа: замещение первого фрагмента строки-модификатора, m реконфигураций матрицы (m сдвигов влево) над «верхней» частью матрицы, вставка второго фрагмента строки-модификатора, 2m-r реконфигураций матрицы (2m-r сдвигов влево) над «нижней» частью матрицы, т.е. удаление незначащих элементов.

Первый этап - замещение первого фрагмента строки-модификатора - строго соответствует вышеописанному состоянию битовой записи данных в строку матрицы, адрес которой задается по входам 46₁÷46_n, имеющим единственную логическую «1», которая соответствует адресу замещаемой строки, поэтому подробное описание первого этапа не приводится. При равенстве длин образца и модификатора замена строки завершается на первом этапе.

Второй этап - m реконфигураций матрицы (m сдвигов влево) над «верхней» частью матрицы - содержательно соответствует вышеописанному состоянию реконфигурации, выполняемому m раз. Вместе с тем различие в задании значения по внутренним адресным входам 8₁÷8_n определяет необходимость детально описать второй этап.

Перед выполнением операции реконфигурации преобразователь кода 45 получает следующие значения: на внешние входы 46₁÷46_n поступает код с единственной логической «1», соответствующей адресу изменяемой строки матрицы, входы «СТАРТ 1»=1 и «СТАРТ 2»=0, что приводит к формированию следующего значения на входах $$8_1÷8_n=\underset{i}{\underbrace{1\dots 1}}0\dots 0$$ , где 1÷i - «верхняя» часть матрицы. Таким образом, на втором этапе выделяется только часть матрицы, над которой далее будет выполняться реконфигурация, т.е. сдвиг влево.

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

Затем на соответствующие четвертые входы 5 ассоциативных запоминающих элементов 1 всех строк матрицы подается сигнал синхронизации "CLOCK"=1, инициируя запись новых логических уровней ассоциативных запоминающих элементов 1 из предыдущих по строке/столбцу матрицы ассоциативных запоминающих элементов 1 и инкремент двоичного счетчика 42 маскирующего элемента 36. Тем самым осуществляется переход матрицы из двухмерного вида в одномерный вид и сдвиг влево элементов в выделенной части матрицы по направлению к первому элементу «верхней» части матрицы.

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

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

Четвертый этап - 2m-r реконфигураций матрицы (2m-r сдвигов влево) над «нижней» частью матрицы - содержательно соответствует вышеописанному состоянию реконфигурации, выполняемому 2m-r раз. Вместе с тем различие в задании значения по внутренним адресным входам 8₁÷8_n определяет необходимость детально описать четвертый этап.

Перед выполнением операции реконфигурации преобразователь кода 45 получает следующие значения: на внешние входы 46₁÷46_n поступает код с единственной логической «1», соответствующей адресу изменяемой строки матрицы, входы «СТАРТ 1»=0 и «СТАРТ 2»=1, что приводит к формированию следующего значения на входах $$8_1÷8_n=0\dots 0\underset{n-i}{\underbrace{1\dots 1}}$$ , где n-i÷n - «нижняя» часть матрицы. Таким образом, на четвертом этапе выделяется только часть матрицы, над которой далее будет выполняться реконфигурация, т.е. сдвиг влево.

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

Затем на соответствующие четвертые входы 5 ассоциативных запоминающих элементов 1 всех строк матрицы подается сигнал синхронизации "CLOCK"=1, инициируя запись новых логических уровней ассоциативных запоминающих элементов 1 из предыдущих по строке/столбцу матрицы ассоциативных запоминающих элементов 1 и инкремент двоичного счетчика 42 маскирующего элемента 36. Тем самым осуществляется переход матрицы из двухмерного вида в одномерный вид и сдвиг влево элементов в выделенной части матрицы по направлению к первому элементу «нижней» части матрицы.

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

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

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

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

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

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