СПОСОБ И АССОЦИАТИВНОЕ МАТРИЧНОЕ УСТРОЙСТВО ДЛЯ ОБРАБОТКИ СТРОКОВЫХ ДАННЫХ Российский патент 2015 года по МПК G11C15/00 

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

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

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

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

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

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

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

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

Техническая задача решается тем, что разработано ассоциативное матричное устройство для обработки строковых данных (далее - устройство), содержащее n×m ассоциативных запоминающих элементов, имеющих по четыре входа и два выхода каждый элемент, четвертые входы ассоциативных запоминающих элементов подключены к внешнему входу синхронизации "CLOCK", третьи входы ассоциативных запоминающих элементов подключены к внешнему входу "СБРОС", вторые входы ассоциативных запоминающих элементов подключены к выходам соответствующих по столбцу элементов-селекторов, первые входы ассоциативных запоминающих элементов подключены к адресным входам в соответствующей строке матрицы, первые выходы ассоциативных запоминающих элементов в соответствующих столбцах матрицы объединены и являются соответствующими информационными выходами матрицы, первые выходы ассоциативных запоминающих элементов первой строки матрицы являются информационными выходами матрицы, n×m коммутационных элементов, первые входы которых подключены ко вторым выходам соответствующих ассоциативных запоминающих элементов, вторые входы коммутационных элементов подключены к внешнему входу "СБРОС", третьи входы коммутационных элементов подключены к внешнему входу синхронизации "CLOCK", а выходы коммутационных элементов соответственно объединены и являются соответствующими выходами результатов опроса, n×m элементов-селекторов, первые входы которых являются соответственно первыми информационными входами ассоциативного матричного устройства в соответствующих столбцах, вторые входы элементов-селекторов подключены к первым выходам ассоциативных запоминающих элементов соответствующей строки матрицы, при этом вторые входы элементов-селекторов крайнего правого столбца матрицы подключены к первым выходам соответствующих ассоциативных запоминающих элементов крайнего левого столбца матрицы, расположенных строкой ниже, третьи входы n×m элементов-селекторов подключены к внешнему входу "РЕЖИМ", четвертые входы элементов-селекторов подключены к внешнему входу "СДВИГ", пятые входы элементов-селекторов, кроме n-й строки матрицы, подключены в соответствующем столбце к первым выходам ассоциативных запоминающих элементов, расположенных строкой ниже в матрице, пятые входы элементов-селекторов n-й строки матрицы являются внешним входами устройства, выходы 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 - схема ячейки преобразователя кода.

Устройство содержит следующие внешние входы и выходы: информационные входы 19₁-19_m для подачи m-разрядного поискового слова-образца или записываемого слова, входы 20₁-20_m для записи поразрядного слова в последнюю строку матрицы ассоциативных запоминающих элементов, информационные выходы 21₁-21_m для выдачи поразрядного слова из первой строки матрицы ассоциативных запоминающих элементов, информационные выходы 9₁-9_m опроса строк матрицы ассоциативных запоминающих элементов, информационные выходы 11₁-11_n результата поиска по образцу, адресные входы 46₁-46_m, управляющие однобитовые входы: синхронизации «CLOCK», сброса «СБРОС», последовательного сдвига влево «СДВИГ», управления реконфигурацией «РЕЖИМ», однобитовые сигналы «СТАРТ 1», «СТАРТ 2» для формирования маски.

Задача обработки строковых данных имеет формализацию в виде последовательности выполняемых операций:

- поиск по образцу;

- замены строки.

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

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

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

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

Требуется найти первое вхождение О в S, т.е. определить такую позицию p, при которых справедливо выражение

∃i∀j/[S(i)=O(j)],

где i=р…p+m-1, j=1…m, «=» - равенство i-го и j-го символов.

С найденной позиции р требуется выполнить осуществить замену строки O на строку P, т.е. разработать такой алгоритм, что справедливо

∃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: m<r.

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

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

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

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

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

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

Ассоциативное матричное устройство (фиг. 2) состоит из n×m ассоциативных запоминающих элементов 1 (n - количество битовых строк, необходимых для представления входной битовой строки, m - количество разрядов битового образца) с входами с первого 2 по четвертый 5 и с выходами с первого 6 по второй 7, четвертые входы 5 ассоциативных запоминающих элементов 1 подключены к внешнему входу синхронизации "CLOCK", третьи входы 4 ассоциативных запоминающих элементов 1 подключены к внешнему входу "СБРОС", вторые входы 3 ассоциативных запоминающих элементов 1 подключены к выходам 18 соответствующих по столбцу элементов-селекторов 12, первые входы 2 ассоциативных запоминающих элементов 1 подключены к адресным входам 8₁-8_n в соответствующей строке матрицы, первые выходы ассоциативных запоминающих элементов 1 в соответствующих столбцах матрицы объединены и являются соответствующими информационными выходами устройства 9₁-9_m, первые выходы 6 ассоциативных запоминающих элементов 1 первой строки матрицы являются внешними выходами 21₁-21_m устройства, n×m коммутационных элементов 10, представляющих собой 1-n-полюсники, первые входы коммутационных элементов 10 подключены ко вторым выходам 7 соответствующих ассоциативных запоминающих элементов 1, вторые входы коммутационных элементов 10 подключены к внешнему входу "СБРОС", третьи входы коммутационных элементов подключены к внешнему входу синхронизации "CLOCK", а выходы коммутационных элементов 10 соответственно объединены и являются соответствующими выходами результатов опроса 11₁-11_n, n×m элементов-селекторов 12, первые входы 13 в соответствующих столбцах матрицы являются соответственно первыми информационными входами 19₁-19_m ассоциативного матричного устройства, вторые входы элементов-селекторов 12 подключены к первым выходам ассоциативных запоминающих элементов 1 соответствующей строки матрицы, при этом вторые входы элементов-селекторов 12 крайнего правого столбца матрицы подключены к первым выходам соответствующих ассоциативных запоминающих элементов 1 крайнего левого столбца матрицы, расположенных строкой ниже, третьи входы n×m элементов-селекторов 12 подключены к внешнему входу "РЕЖИМ", четвертые входы n×m элементов-селекторов 12 подключены к внешнему входу "СДВИГ", пятые входы элементов-селекторов 12, кроме n-й строки матрицы, подключены в соответствующем столбце к первым выходам ассоциативных запоминающих элементов 1, расположенных строкой ниже в матрице, пятые входы элементов-селекторов 12 n-й строки матрицы являются внешним входами 20₁-20_m устройства, выходы n×m элементов-селекторов 12 являются входами ассоциативных запоминающих элементов 1 соответствующей строки матрицы, маскирующего элемента 36 с входами с первого 37 по третий 39 и с выходом 40, элемента И 44, первый вход которого подключен к выходу результата опроса n-й строки матрицы, второй вход - к выходу 40 маскирующего элемента 36, а выход является маскируемым выходом опроса n-й строки матрицы 11_n, ограничительного резистора 32, соединенного со вторым входом 14 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 состоит из двухвходового элемента И 22, D-триггера 23, двухвходового элемента И-НЕ 24, двухвходового элемента И-НЕ 25. Первый вход элемента И 22 подключен к первому входу 2 ассоциативного запоминающего элемента 1, второй вход элемента И 22 подключен к четвертому входу 5 ассоциативного запоминающего элемента 1, а выход элемента И 22 подключен к входу синхронизации D-триггера, информационный вход которого подключен ко второму входу 3 ассоциативного запоминающего элемента 1, а третий вход 4 ассоциативного запоминающего элемента 1 подключен к асинхронному входу сброса D-триггера и асинхронному входу сброса регистра 28 в коммутационном элементе 10, прямой выход D-триггера подключен к двум входам элемента И-НЕ 24 и к первому входу элемента И-НЕ 25, на второй вход которого подан второй вход 3 ассоциативного запоминающего элемента 1, выход элемента И-НЕ 24 через резистивный элемент 26, подключенный к источнику питания, является первым выходом 6 ассоциативного запоминающего элемента 1, второй выход 7 которого является выходом элемента И-НЕ 25.

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

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

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

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

Преобразователь кода строго соответствует устройству-прототипу в структурном и в функциональном отношении, состоит из однородных ячеек 53₁÷53_n, каждая из которых состоит из двухвходовых элементов И 54, И 55 и трехвходового элемента ИЛИ 56 (фиг. 6). Первый вход элемента И 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 или четвертых 17 входов элементов-селекторов 12 к выходу 18 соответственно в зависимости от значений внешних входов «РЕЖИМ» и «СДВИГ». Если входы «РЕЖИМ» = 0 и «СДВИГ» = 0, то к выходу 18 подключается вход 13, т.е. обеспечивается ассоциативный поиск вхождений или запись в параллельном коде строки-модификатора на двумерном представлении S. Если входы «РЕЖИМ» = 0 и «СДВИГ» = 1, то к выходу 18 подключается вход 17, т.е. выполняется межстрочный сдвиг на двумерном представлении S (параллельный сдвиг влево). Если вход РЕЖИМ = 1, то к выходу 17 подключается вход 14, т.е. выполняется последовательный сдвиг влево на одномерном представлении S. Элементы-селекторы 12 (фиг. 4) содержат мультиплексоры 35, которые обеспечивают ввод в ассоциативные запоминающие элементы 1 бит образца О (для ассоциативного поиска вхождений), бит модификатора Р (для замещения/вставки в параллельном коде) или бит от соседнего справа ассоциативного запоминающего элемента 1 (для последовательного сдвига влево).

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

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

При считывании битовых данных из матрицы на третьи входы 46₁÷46_n преобразователя кода 45 подается адрес строки, из которой необходимо произвести чтение, при этом на внешние входы «СТАРТ 1» и «СТАРТ 2» преобразователя кода 45 подаются значения логического «1», что приводит к подключению третьих входов 46₁÷46_n преобразователя кода к внутренним адресным входам 8₁÷8_n матрицы со значениями 1…1, которые разрешают выполнять параллельный сдвиг влево по всем строкам матрицы. Затем устанавливаются входы «РЕЖИМ» = 0 и «СДВИГ» = 1, что приводит к подключению выходов 18 элементов-селекторов 12 через входы 17 к первым выходам ассоциативных запоминающих элементов 1, расположенных строкой ниже в матрице, при этом входы 17 элементов-селекторов 12 последней строки матрицы подключены к внешним входам 20₁-20_m. С подачей n тактовых импульсов по внешнему входу синхронизации «CLOCK» осуществляется построчное считывание матрицы по внешнему выходу 21₁-21_m, начиная с первой строки матрицы.

Перед выполнением ассоциативного поиска выполняется настройка матрицы, заключающаяся в предварительной записи в регистры 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 подаются значения логической «1», что приводит к подключению третьих входов 46₁÷46_n преобразователя кода к внутренним адресным входам 8₁÷8_n матрицы со значениями 1…1, которые разрешают вести поиск по всем строкам матрицы.

При осуществлении циклического ассоциативного поиска вхождений на информационные входы 19 устройства и, следовательно, на первые входы 13 всех элементов-селекторов 12 соответствующей строки матрицы поступает логическая «1» или логический «0». При этом на четвертый вход 16 соответствующих элементов-селекторов 12 подается сигнал "РЕЖИМ" = 0, что осуществляет подключение первых входов 13 элементов-селекторов 12 к выходам 18 элементов-селекторов 12 и соответственно ко вторым входам 3 ассоциативных запоминающих элементов 1 соответствующей строки матрицы. Затем на соответствующие четвертые входы 5 ассоциативных запоминающих элементов 1 соответствующей строки матрицы подается сигнал синхронизации "CLOCK = 1", инициируя сравнение с содержимым триггера 23 соответствующего ассоциативного запоминающего элемента 1 на двухвходовом элементе И-НЕ 25, первый вход которого подключен к выходу D-триггера 23, второй вход элемента И-НЕ 25 подключен ко входу 3 ассоциативного запоминающего элемента 1. Если происходит совпадение, то выход элемента И-НЕ 25, являющийся вторым выходом 7 ассоциативного запоминающего элемента 1, сохраняет уровень логического "0" и, следовательно, на выходе(ах) 11 результатов опроса матрицы, к которому(ым) подключен выход 7 этого ассоциативного запоминающего элемента 1, сохраняется уровень логической "1". Если происходит несовпадение, то на выходе 7 такого ассоциативного запоминающего элемента 1 появляется уровень логической "1", устанавливающий в "0" этот (эти) выход(ы) 11. При этом если была произведена хотя бы одна операция реконфигурации матрицы, на выходе 11_n результатов опроса ассоциативных запоминающих элементов 1 n-й строки матрицы получается значение логического "0" в результате установки на выходе маскирующего элемента 36 значения логического "0".

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

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

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

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

Второй этап - параллельный межстрочный сдвиг влево в матрице над ее «верхней» частью - содержательно соответствует вышеописанному состоянию считывания битовых данных. Вместе с тем различие в задании значения по внутренним адресным входам 8₁÷8_n и использование двух управляющих сигналов «РЕЖИМ», «СДВИГ» для параллельного межстрочного сдвига влево в матрице определяют необходимость детально описать второй этап.

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

При осуществлении параллельного межстрочного сдвига влево над выделенной частью матрицы устанавливаются входы «РЕЖИМ» = 0 и «СДВИГ» = 1, что приводит к подключению выходов 18 элементов-селекторов 12 через входы 17 к первым выходам ассоциативных запоминающих элементов 1, расположенных строкой ниже в матрице, при этом входы 17 элементов-селекторов 12 последней строки матрицы подключены к внешним входам 20₁-20_m устройства. Затем на соответствующие четвертые входы 5 ассоциативных запоминающих элементов 1 всех строк матрицы с учетом сформированного значения на входах где 1÷i - «верхняя» часть матрицы, один раз подается сигнал синхронизации "CLOCK" = 1, инициируя межстрочный сдвиг и выдачу первой строки матрицы на внешние входы 21₁-21_m. Тем самым осуществляется освобождение строки матрицы для следующих этапов за один сигнал "CLOCK" = 1.

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

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

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

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

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

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

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

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

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

2. Ассоциативное матричное устройство для обработки строковых данных содержит n×m ассоциативных запоминающих элементов, имеющих по четыре входа и два выхода каждый элемент, четвертые входы ассоциативных запоминающих элементов подключены к внешнему входу синхронизации "CLOCK", третьи входы ассоциативных запоминающих элементов подключены к внешнему входу "СБРОС", вторые входы ассоциативных запоминающих элементов подключены к выходам соответствующих по столбцу элементов-селекторов, первые входы ассоциативных запоминающих элементов подключены к адресным входам в соответствующей строке матрицы, первые выходы ассоциативных запоминающих элементов в соответствующих столбцах матрицы объединены и являются соответствующими информационными выходами матрицы, первые выходы ассоциативных запоминающих элементов первой строки матрицы являются информационными выходами матрицы, n×m коммутационных элементов, первые входы которых подключены ко вторым выходам соответствующих ассоциативных запоминающих элементов, вторые входы коммутационных элементов подключены к внешнему входу "СБРОС", третьи входы коммутационных элементов подключены к внешнему входу синхронизации "CLOCK", а выходы коммутационных элементов соответственно объединены и являются соответствующими выходами результатов опроса, n×m элементов-селекторов, первые входы которых являются соответственно первыми информационными входами ассоциативного матричного устройства в соответствующих столбцах, вторые входы элементов-селекторов подключены к первым выходам ассоциативных запоминающих элементов соответствующей строки матрицы, при этом вторые входы элементов-селекторов крайнего правого столбца матрицы подключены к первым выходам соответствующих ассоциативных запоминающих элементов крайнего левого столбца матрицы, расположенных строкой ниже, третьи входы n×m элементов-селекторов подключены к внешнему входу "РЕЖИМ", четвертые входы элементов-селекторов подключены к внешнему входу "СДВИГ", пятые входы элементов-селекторов, кроме n-й строки матрицы, подключены в соответствующем столбце к первым выходам ассоциативных запоминающих элементов, расположенных строкой ниже в матрице, пятые входы элементов-селекторов n-й строки матрицы являются внешним входами устройства, выходы 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».