Матричное устройство для параллельного поиска вхождений и обработки данных Российский патент 2021 года по МПК G06F12/00 G06F9/38 

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

Известна система поиска слов (образцов) в произвольном тексте [. Кулик, Б.А. Система поиска слов в произвольном тексте / Б.А. Кулик // Программирование. 1987. №1. С.49-50.], основанная на хранении текста в виде так называемых характеристических векторов длиной в m бит каждый вектор, где m – длина текста. Каждый элемент характеристического вектора принимает значение логической «1» или «0» в зависимости от того, присутствует ли текущий символ образца в тексте в данной позиции. При таком представлении исходных данных операция поиска вхождения сводится к последовательной обработке битовых векторов. Данная система может быть реализована на основе операции побитового логического умножения двух логических векторов со сдвигом перемножаемых бит на одну позицию. Результатом поиска на характеристических векторах является m-ый характеристический вектор, в котором логические «1» соответствуют позициям вхождения последнего символа образца.

Недостаток данной системы заключается в последовательной обработке n векторов (n – длина образца), что приводит к избыточным затратам времени за счет n-кратного обращения к памяти кодов символов образца для вычисления текущего характеристического вектора.

Также известен алгоритм СДВИГ-И [Максимов, В. Алгоритмы поиска, или как искать неизвестно что / В. Максимов // Монитор. 1995. №6. С. 10-15.

] для поиска слов в тексте. Он основан на поиске всех возможных префиксов образца в тексте с помощью векторов-столбцов длиной в n бит каждый. Каждый элемент такого вектора-столбца принимает значение логической «1» или «0» в зависимости от того, присутствует ли текущий префикс образца в тексте в данной позиции. При такой организации исходных данных операция поиска вхождения сводится к последовательной обработке битовых векторов-столбцов (битовых срезов).

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

Известно устройство [А.с. СССР №1485254 , МКИ G06 F 12/00. Устройство для адресации по содержанию блока памяти , опубл. 07.06.89, Бюл. №21. ] для адресации по содержанию блока памяти, состоящее из двух блоков ассоциативных признаков, блока памяти логических векторов и операционного блока. Работа устройства основана на обработке элементов двух множеств (признаков и объектов) с помощью логических векторов-строк или векторов столбцов. Вектор-строка является характеристическим вектором, описывающим определенное подмножество признаков, принадлежащих множеству объектов. В качестве элементарных операций над векторами реализованы логические операции умножения, сложения, суммы по модулю 2, инверсии и т.д., а также операции идентификации объекта.

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

Устройством-прототипом является устройство для параллельного поиска и обработки данных [. Пат. №72771 Российская Федерация, МПК G06F 12/00. опубл. 27.04.2008, Бюл. № 12. ], состоящее из двух блоков ассоциативных признаков, блока памяти логических векторов, операционного блока и блока матричного поиска. Данное устройство в режиме «Операция» может выполнять поиск вхождений образца в тексте (операция «Поиск вхождений») на основе параллельной обработки элементов диагоналей блока матричного поиска, матрица поисковых ячеек в составе которого имеет форму параллелограмма.

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

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

Уменьшение времени на параллельный поиск вхождений образца в тексте реализуется проверкой в диагоналях битовой матрицы результатов сравнений двоичной комбинации « …10… », начиная ее поиск с последней строки данной матрицы. Такие двоичные комбинации, обнаруженные во всех диагоналях матрицы, являются признаком отрицательного результата поиска вхождений образца в тексте, что позволяет досрочно прекратить поиск.

Решение технической задачи достигается тем, что в матричное устройство для параллельного поиска вхождений и обработки данных (далее - устройство), содержащее первый и второй блоки хранения и сравнения ассоциативных признаков, блок памяти логических векторов, операционный блок и блок матричного поиска, причем информационные входы первого и второго блоков хранения и сравнения ассоциативных признаков являются соответственно первым и вторым информационными входами устройства, а выходы блоков хранения и сравнения ассоциативных признаков соединены соответственно с первым и вторым адресными входами блока памяти логических векторов, входы задания режимов первого и второго блоков хранения и сравнения ассоциативных признаков и вход записи-считывания блока памяти логических векторов являются соответственно первым, вторым и третьим входами задания режимов устройства, а четвертый, пятый, шестой входы задания режимов устройства соответственно соединены с тремя входами кодов операций операционного блока, первый выход которого является первым выходом устройства, первый вход начальной установки устройства подключен к входу начальной установки операционного блока и первому входу блока матричного поиска, второй вход начальной установки - к входам начальной установки первого и второго блоков хранения и сравнения ассоциативных признаков, первый и второй выходы блока памяти логических векторов подключены соответственно к первому и второму информационным входам операционного блока, второй выход которого («Запись строк») подключен ко второму входу блока матричного поиска, два информационных входа которого являются внешними третьим и четвертым входами устройства, а первый выход блока матричного поиска является вторым выходом устройства , введен в составе блока матричного поиска второй (информационный) выход размером n×k бит (k=m-n+1 – количество диагоналей в матрице) для выдачи результатов сравнения i-го символа образца (i=1-n) и j-го символа текста (j=1-m), введен матричный блок проверки, имеющий два входа и один однобитовый выход, при этом первый вход матричного блока проверки соединен с первым входом начальной установки устройства, второй вход матричного блока проверки соединен со вторым выходом блока матричного поиска, матричный блок проверки состоит из n×k двухвходовых элементов ИЛИ-НЕ, расположенных в форме параллелограмма, k многовходовых элементов ИЛИ (на n разрядов каждый), k RS-триггеров, 1 многовходового элемента И (на k разрядов), выходы от n двухвходовых элементов ИЛИ-НЕ v-й диагонали (v=1-k) матричного блока проверки соединены со входами v-го многовходового элемента ИЛИ, выход которого соединен с S-входом v-го RS-триггера, а R-вход v-го RS-триггера соединен с первым входом начальной установки устройства, прямой выход v-го RS-триггера соединен с v-м входом многовходового элемента И, выход которого является выходом матричного блока проверки, а также третьим выходом устройства, выход (i,v)-го двухвходового элемента ИЛИ-НЕ (i=1-n, v=1-k) матричного блока проверки, кроме двухвходовых элементов ИЛИ-НЕ первой строки матрицы двухвходовых элементов ИЛИ-НЕ, соединен со вторым входом (i-1,v-1)-го двухвходового элемента ИЛИ-НЕ, первые входы двухвходовых всех элементов ИЛИ-НЕ матричного блока проверки, соединены с одноименными однобитовыми входами n×k-разрядного второго входа матричного блока проверки, т.е. первый вход (i,v)-го двухвходового элемента ИЛИ-НЕ соединен с (i,v)-м однобитовым входом в составе второго входа матричного блока проверки, вторые входы двухвходовых элементов ИЛИ-НЕ_nn–ИЛИ-НЕ_nm, расположенных в n-й строке матрицы двухвходовых элементов ИЛИ-НЕ, соединены со входом стартового значения, равного логическому «0», что необходимо для задания направления проверки от последней строки матричного блока проверки к его первой строке; в состав блока матричного поиска введены однобитовый управляющий вход («Запись сравнений») для записи результатов сравнения i-го символа образца (i=1-n) и j-го символа текста (j=1-m) в поисковые ячейки блока матричного поиска, являющийся девятым управляющим входом устройства, а также однобитовый управляющий вход («Запись результатов»), являющийся десятым управляющим входом устройства; в состав каждой поисковой ячейки блока матричного поиска введен D-триггер с тремя входами, а также в состав каждой поисковой ячейки введены четвертый и пятый однобитовые входы и второй однобитовый выход, при этом четвертый однобитовый вход поисковой ячейки соединен с однобитовым управляющим входом «Запись сравнений» и со вторым входом D-триггера, пятый однобитовый вход поисковой ячейки соединен с первым входом начальной установки устройства и с первым входом D-триггера, третий (информационный) вход D-триггера соединен с выходом схемы сравнения на равенство p-разрядных кодов i-го символа образца (i=1-n) и j-го символа текста (j=1-m) в составе поисковой ячейки, прямой выход D-триггера соединен с первым входом двухвходового элемента И в составе поисковой ячейки и является вторым выходом поисковой ячейки, второй вход двухвходового элемента И соединен с третьим входом поисковой ячейки, выход двухвходового элемента И является первым выходом поисковой ячейки, вторые однобитовые выходы n×k поисковых ячеек образуют второй (информационный) n×k-разрядный выход блока матричного поиска для выдачи матрицы результатов сравнений, первый выход (i,v)-й поисковой ячейки (i=1-n, v=1-k), кроме i=1 (первая строка матрицы результатов сравнений), соединен с третьим входом (i-1,v-1)-й поисковой ячейки, кроме i=n (последняя строка матрицы результатов сравнений), первый выход поисковой ячейки (1,v), расположенной в первой строке матрицы, соединен с третьим (информационным) входом v-го триггера позиции, на третьи входы поисковых ячеек (n,n) – (n,m), расположенных в последней строке матрицы, подается значение логической «1», задавая тем самым направление поиска по соответствующей диагонали от последней строки матрицы к первой строке включительно, на первые входы (i,v)-й поисковых ячеек n строк матрицы (i=1-n), (v=1-k) подаются p-разрядные выходы n регистров хранения символов образца, на вторые входы (j,t)-й поисковых ячеек m столбцов матрицы (j=1-m), (t=1-n) подаются p-разрядные выходы m регистров хранения символов текста, первый вход начальной установки устройства соединен со вторыми входами n регистров хранения символов образца и вторыми входами m регистров хранения символов текста; вход «Запись строк» блока матричного поиска соединен со вторыми входами n регистров для хранения кодов символов образца и вторыми входами m регистров для хранения кодов символов текста соответственно, первый информационный вход блока матричного поиска разрядностью p×n бит предназначен для параллельной записи образца в n регистров кодов символов образца, он состоит из n групп разрядов по p разрядов каждая группа, кодирующих символы образца, причем i-ая группа разрядов (i=1-n) подается на третий p-разрядный вход регистра кода символа образца, второй информационный вход блока матричного поиска разрядностью p×m бит предназначен для параллельной записи текста в m регистров кодов символов текста, он состоит из m групп разрядов по p разрядов каждая группа, кодирующих символы текста, причем j-ая группа разрядов (j=1-m) подается на третий p-разрядный вход регистра кода символа текста, первый вход (первый вход начальной установки устройства) блока матричного поиска соединен с первыми входами k триггеров позиций и с первыми входами n регистров кодов символов образца, а также с первыми входами m регистров кодов символов текста, вход («Запись результатов») блока матричного поиска соединен со вторыми входами k триггеров позиций, первые выходы k поисковых ячеек первой строки матрицы блока матричного поиска соединены с третьими (информационными входами) k триггеров позиций, выходы триггеров позиций являются k-разрядным выходом блока матричного поиска и образуют второй выход устройства.

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

Устройство содержит блоки 1₁ и 1₂ хранения и сравнения ассоциативных признаков, блок 2 памяти логических векторов, операционный блок 3, блок 4 матричного поиска, матричный блок 8 проверки, информационные входы устройства 4₁, 4₂, 4₃ и 4₄, первый и второй информационные выходы устройства 5₁ и 5₂ соответственно, третий выход устройства 10, десять управляющих однобитовых входов: входы 6₁-6₆ задания режима работы, входы 7₁ и 7₂ начальной установки, входы «Запись сравнений», «Запись результатов».

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

Блок 4 матричного поиска содержит четыре управляющих входа: «Начальная установка» 7₁ (первый вход), «Запись строк» (второй вход), «Запись сравнений» (третий вход), «Запись результатов» (четвертый вход), а также два информационных входа для подачи символов образца и текста в параллельном коде через информационные входы 4₃ и 4₄ устройства. Блок 4 матричного поиска содержит первый информационный выход, являющийся вторым выходом 5₂ устройства, и второй информационный выход 9 для выдачи n×k бит матрицы результатов сравнений. При этом второй управляющий вход («Запись строк») блока 4 соединен со вторым выходом операционного блока 3, а второй информационный выход 9 блока 4 соединен со вторым входом матричного блока проверки.

Блок 4 матричного поиска содержит n регистров 32₁-32_n для хранения кодов символов образца, m регистров 33₁–33_m для хранения кодов символов текста, матрицу поисковых ячеек 34₁₁–34_nm и k триггеров 37 позиций, причем регистр 32_i (i=1-n) и регистр 33_j (j=1-m) содержат первый и второй управляющие входы, третий p-разрядный информационный вход и один p-разрядный выход соответственно. Первые и вторые входы n регистров 32 для хранения кодов символов образца, а также первые и вторые входы m регистров 33 для хранения кодов символов текста соединены соответственно с первым 7₁ и вторым («Запись строк») управляющими входами блока 4 матричного поиска, информационный вход 4₃ которого разрядностью p×n бит предназначен для параллельной записи образца в регистры 32₁–32_n и состоит из n групп разрядов по p разрядов каждая группа, кодирующих символы образца, причем i-ая группа разрядов (i=1-n) подается на третий p-разрядный вход регистра 32_i (i=1-n), информационный вход 4₄ блока 4 матричного поиска разрядностью p×m бит предназначен для параллельной записи текста в регистры 33₁-33_m и состоит из m групп разрядов по p разрядов каждая группа, кодирующих символы текста, причем j-ая группа разрядов (j=1-m) подается на третий p-разрядный вход регистра 33_j (j=1-m).

Матрица поисковых ячеек 34₁₁–34_nm имеет размер n×k ячеек (k=m-n+1 – количество диагоналей в матрице), причем каждая поисковая ячейка 34_ij имеет пять входов и два выхода, каждая поисковая ячейка 34_ij содержит двухвходовую схему 35 сравнения на равенство p-разрядных кодов символов образца и текста, D-триггер 40 и двухвходовой элемент 36 И, каждая двухвходовая схема 35_ij сравнения на равенство в составе поисковой ячейки 34_ij состоит из p двухвходовых элементов 38₁–38_p суммы по модулю два с инверсией, на первые входы которых подается соответствующий разряд из i-ой р-разрядной группы информационного входа 4₃ блока 4 матричного поиска, а на вторые входы двухвходовых элементов 38₁–38_p суммы по модулю два с инверсией - соответствующий разряд из j-ой р-разрядной группы информационного входа 4₄ блока 4 матричного поиска, все выходы двухвходовых элементов 38₁-38_p суммы по модулю два с инверсией в составе двухвходовой схемы 35_ij сравнения на равенство соединены с p-входовым элементом 39 И, выход которого является выходом двухвходовой схемы 35_ij сравнения на равенство. Первый и второй p-разрядные входы поисковой ячейки 34_ij соответственно соединены с первым и вторым p-разрядными входами двухвходовой схемы 35_ij сравнения на равенство, выход которой соединен с третьим входом D-триггера 40, первый вход которого соединен с пятым входом поисковой ячейки 34_ij, а второй вход D-триггера 40 соединен с четвертым входом поисковой ячейки 34_ij, прямой выход D-триггера 40 соединен с первым входом двухвходового элемента 36 И и является вторым выходом поисковой ячейки 34_ij, второй вход двухвходового элемента 36 И соединен с третьим входом поисковой ячейки 34_ij, а выход двухвходового элемента 36 И является первым выходом поисковой ячейки 34_ij. Четвертый однобитовый вход поисковой ячейки 34_ij соединен с управляющим входом «Запись сравнений» устройства, пятый однобитовый вход поисковой ячейки 34_ij соединен с первым входом 7₁ начальной установки устройства. Вторые выходы всех поисковых ячеек 34₁₁–34_nm образуют второй (информационный) выход 9 блока матричного поиска для выдачи матрицы результатов сравнений.

Матрица поисковых ячеек 34₁₁–34_nm имеет геометрическую форму параллелограмма, в которой в каждой строке располагается k поисковых ячеек, сдвинутых относительно следующей строки ячеек влево на 1 позицию, начиная с ячеек последней строки 34_nn–34_nm. Такая форма матрицы обеспечивает направление поиска по диагоналям, проходящим через ячейки от последней строки к первой строке включительно. Первые p-разрядные входы k поисковых ячеек i-ой строки матрицы (i=1-n) соединены с p-разрядным выходом регистра 32_i. P-разрядный выход регистра 33_j (j=1-m) соединен со вторыми p-разрядными входами всех поисковых ячеек, входящих в j-ый столбец матрицы. Первый выход поисковой ячейки 34_iv (i=1-n, v=1-k), кроме i=1 (первая строка матрицы), соединен с третьим входом поисковой ячейки 34_i-1v-1, кроме i=n (последняя строка матрицы). Первый выход поисковой ячейки 34_1v, расположенной в первой строке матрицы, соединен с третьим (информационным входом) 3 триггера 37_v позиции. На третьи входы поисковых ячеек
34_nn –34_nm, расположенных в последней строке матрицы, подается значение логической «1», задавая тем самым направление поиска по соответствующей диагонали от последней строки матрицы к первой строке включительно.

Триггера 37₁–37_k позиций хранят положительный результат поиска вхождений в виде k-разрядного кода, в котором значениями логических «1» отмечены позиции начала вхождения образца в текст. Триггер 37_v позиции (v=1-k) содержит три входа (первый и второй управляющие, третий одноразрядный информационный вход) и один выход. Первый вход (вход 7₁ начальной установки) блока 4 матричного поиска соединен с первыми входами k триггеров 37 позиций. Четвертый вход («Запись результатов») блока 4 матричного поиска соединен со вторыми входами k триггеров 37 позиций. Выходы триггеров 37₁-37_k позиций являются k-разрядным выходом блока 4 матричного поиска и образуют второй выход устройства 5₂.

Матричный блок 8 проверки, имеет размер n×k двухвходовых элементов 80 ИЛИ=НЕ (k=m-n+1 – количество диагоналей в матрице), k многовходовых элементов 81 ИЛИ (на n разрядов каждый), k RS-триггеров 82, 1 многовходового элемента 83 И (на k разрядов).

Матрица двухвходовых элементов 80₁₁–80_nm ИЛИ-НЕ имеет геометрическую форму параллелограмма, в которой в каждой строке располагается k двухвходовых элементов ИЛИ-НЕ, сдвинутых относительно следующей строки элементов ИЛИ-НЕ влево на 1 позицию, начиная с элементов ИЛИ-НЕ последней строки 80_nn–80_nm. Такая форма матрицы двухвходовых элементов 80₁₁–80_nm ИЛИ-НЕ обеспечивает направление проверки по диагоналям, проходящим от последней строки к первой строке включительно. Выходы n двухвходовых элементов 80 ИЛИ-НЕ v-й диагонали (v=1-k) матричного блока 8 проверки соединены со входами v-го многовходового элемента 81 ИЛИ, выход которого соединен с S-входом v-го RS-триггера 82, а R-вход v-го
RS-триггера 82 соединен с первым входом 7₁ начальной установки устройства, прямой выход v-го RS-триггера 82 соединен с v-м входом многовходового элемента 83 И, выход которого является выходом матричного блока 8 проверки, а также третьим выходом устройства, значение логической «1» на котором является признаком обнаружения отрицательного результата поиска, выход (i,v)-го двухвходового элемента 80 ИЛИ-НЕ (i=1-n, v=1-k) матричного блока 8 проверки, кроме двухвходовых элементов 80 ИЛИ-НЕ первой строки матрицы двухвходовых элементов ИЛИ-НЕ, соединен со вторым входом
(i-1,v-1)-го двухвходового элемента 80 ИЛИ-НЕ, первые входы всех двухвходовых элементов 80₁₁–80_nm ИЛИ-НЕ матричного блока 8 проверки, соединены с одноименными однобитовыми входами n×k-разрядного второго входа 9 матричного блока проверки, т.е. первый вход (i,v)-го двухвходового элемента ИЛИ-НЕ соединен с (i,v)-м однобитовым входом в составе второго входа 9 матричного блока 8 проверки, вторые входы двухвходовых элементов
80_nn–80_nm ИЛИ-НЕ, расположенных в n-й строке матрицы двухвходовых элементов ИЛИ-НЕ, соединены со входом стартового значения, равного логическому «0», что необходимо для задания направления проверки от последней строки матричного блока 8 проверки к его первой строке.

Данное устройство, как и устройство-прототип, работает в режимах «Запись» и «Операция». Режим "Запись" строго соответствует алгоритму, описанному в устройстве-прототипе.

С учетом появления блока 8, новых элементов в составе блока 4, а также новых входов и выходов по сравнению с устройством-прототипом в алгоритм режима "Операция" при выполнении операции «Поиск вхождений» («ПВ») вносятся изменения.

Пусть устройство выполняет режим «Операция» с кодом операции «ПВ». В операционный блок 3, блок 4 матричного поиска и матричный блок 8 проверки через вход 7₁ подается импульсный сигнал начальной установки, который сбрасывает в нулевое состояние регистр 22 команд по его входу 1, регистр 30 по его входу 1, а также k триггеров 37 позиций по их входу 1, n регистров 32 по их входу 1 и m регистров 33 по их входу 1, а также n×k
D-триггеров 40 в составе n×k поисковых ячеек 34 блока 4 матричного поиска и k RS-триггеров 82 в составе матричного блока проверки. После окончания действия сигнала начальной установки на вход 6₆ режима работы операционного блока 3 подается код операции «ПВ», который обнаруживается дешифратором 23 команд и со второго выхода операционного блока 3 на второй вход «Запись строк» блока 4 матричного поиска подается импульсный сигнал. Данный импульсный сигнал по входу «Запись строк» блока 4 матричного поиска подается соответственно на вторые входы разрешения записи n регистров 32 для хранения кодов символов образца и на вторые входы разрешения записи m регистров 33 для хранения кодов символов текста, обеспечивая тем самым запись n символов образца и m символов текста в параллельном коде с входов 4₃ и 4₄ устройства. В поисковых ячейках 34₁₁ – 34_nm блока 4 матричного поиска схемы 35₁₁ – 35_nm сравнения на равенство формируют матрицу результатов сравнений n символов образца с m символами текста размером n×k бит, которые по входу «Запись сравнений» записываются в D-триггера поисковых ячеек 34₁₁ – 34_nm. Выходы всех D-триггеров формируют второй информационный выход 9 для выдачи n×k бит матрицы результатов сравнений.

Операция с кодом «ПВ» выполняется параллельно в двух матрицах: матрице поисковых ячеек 34₁₁–34_nm блока 4 матричного поиска с формированием на выходе 5₂ положительного результата поиска и матрице элементов 80₁₁–80_nm ИЛИ-НЕ матричного блока 9 проверки с формированием признака отрицательного поиска на однобитовом выходе 10.

Поиск в матрице поисковых ячеек 34₁₁–34_nm начинается с ячеек последней строки матрицы. Начальный k-битовый характеристический вектор, равный 11…1, подается на третьи входы поисковых ячеек последней строки матрицы и определяет тем самым направление параллельного поиска по всем диагоналям матрицы от поисковых ячеек последней строки до поисковых ячеек первой строки включительно с записью положительного результата в триггера 37₁ – 37_k позиций по управляющему входу «Запись результатов.

Проверка в матрице двухвходовых элементов 80₁₁–80_nm ИЛИ-НЕ начинается с ячеек последней строки матрицы. Начальный k-битовый вектор, равный 00 …0, подается на вторые входы двухвходовых элементов ИЛИ-НЕ последней строки матрицы и определяет тем самым направление параллельной проверки по всем диагоналям матрицы от двухвходовых элементов ИЛИ-НЕ последней строки до двухвходовых элементов ИЛИ-НЕ первой строки. Проверка связана с обнаружением комбинации « …10… » в составе всех диагоналей матрицы, состоящих из n двухвходовых элементов ИЛИ-НЕ. Если на выходе (jv)-го двухвходового элемента ИЛИ-НЕ (1≤j≤n, v=1-k) формируется логическая «1», то она через многовходовой элемент 81_v ИЛИ поступает на S-вход RS-триггера 82_v, прямой выход которого подключен к многовходовому элементу 83 И.

В случае, если в процессе проверки все RS-триггера 82₁–82_k переключатся в состояние логической «1», то на выходе многовходового элемента 83 И появляется логическая «1», являющаяся признаком отрицательного результата поиска вхождений, которая поступает на однобитовый выход 10 устройства.

Выполнение алгоритма в режиме «Операция» на остальных операциях строго соответствует устройству-прототипу.

Изобретение относится к вычислительной технике. Технический результат заключается в уменьшении времени параллельного поиска вхождений образца в тексте за счет обнаружения признака отрицательного результата поиска. Матричное устройство для параллельного поиска вхождений и обработки данных содержит блоки 11 и 12 хранения и сравнения ассоциативных признаков, блок 2 памяти логических векторов, операционный блок 3, блок 4 матричного поиска, матричный блок 8 проверки, информационные входы устройства 41, 42, 43 и 44, первый и второй информационные выходы устройства 51 и 52 соответственно, третий выход устройства 10, десять управляющих однобитовых входов: входы 61-66 задания режима работы, входы 71 и 72 начальной установки, входы «Запись сравнений», «Запись результатов». 7 ил.

Матричное устройство для параллельного поиска вхождений и обработки данных (далее - устройство), содержащее первый и второй блоки хранения и сравнения ассоциативных признаков, блок памяти логических векторов, операционный блок и блок матричного поиска, причем информационные входы первого и второго блоков хранения и сравнения ассоциативных признаков являются соответственно первым и вторым информационными входами устройства, а выходы блоков хранения и сравнения ассоциативных признаков соединены соответственно с первым и вторым адресными входами блока памяти логических векторов, входы задания режимов первого и второго блоков хранения и сравнения ассоциативных признаков и вход записи-считывания блока памяти логических векторов являются соответственно первым, вторым и третьим входами задания режимов устройства, а четвертый, пятый, шестой входы задания режимов устройства соответственно соединены с тремя входами кодов операций операционного блока, первый выход которого является первым выходом устройства, первый вход начальной установки устройства подключен к входу начальной установки операционного блока и первому входу блока матричного поиска, второй вход начальной установки - к входам начальной установки первого и второго блоков хранения и сравнения ассоциативных признаков, первый и второй выходы блока памяти логических векторов подключены соответственно к первому и второму информационным входам операционного блока, второй выход которого («Запись строк») подключен ко второму входу блока матричного поиска, два информационных входа которого являются внешними третьим и четвертым входами устройства, а первый выход блока матричного поиска является вторым выходом устройства, отличающееся тем, что в устройство дополнительно введен в составе блока матричного поиска второй информационный выход размером n×k бит (k=m-n+1 - количество диагоналей в матрице) для выдачи результатов сравнения i-го символа образца (i=1-n) и j-гo символа текста (j=1-m), введен матричный блок проверки, имеющий два входа и один однобитовый выход, при этом первый вход матричного блока проверки соединен с первым входом начальной установки устройства, второй вход матричного блока проверки соединен со вторым выходом блока матричного поиска, матричный блок проверки состоит из n×k двухвходовых элементов ИЛИ-НЕ, расположенных в форме параллелограмма, k многовходовых элементов ИЛИ на n разрядов каждый, k RS-триггеров, 1 многовходового элемента И на k разрядов, выходы от n двухвходовых элементов ИЛИ-НЕ v-й диагонали (v=1-k) матричного блока проверки соединены со входами v-го многовходового элемента ИЛИ, выход которого соединен с S-входом v-го RS-триггера, a R-вход v-го RS-триггера соединен с первым входом начальной установки устройства, прямой выход v-го RS-триггера соединен с v-м входом многовходового элемента И, выход которого является выходом матричного блока проверки, а также третьим выходом устройства, выход (i, v)-го двухвходового элемента ИЛИ-НЕ (i=1-n, v=1-k) матричного блока проверки, кроме двухвходовых элементов ИЛИ-НЕ первой строки матрицы двухвходовых элементов ИЛИ-НЕ, соединен со вторым входом (i-1, v-1)-го двухвходового элемента ИЛИ-НЕ, первые входы двухвходовых всех элементов ИЛИ-НЕ матричного блока проверки соединены с одноименными однобитовыми входами n×k-разрядного второго входа матричного блока проверки, т.е. первый вход (i, v)-го двухвходового элемента ИЛИ-НЕ соединен с (i, v)-м однобитовым входом в составе второго входа матричного блока проверки, вторые входы двухвходовых элементов ИЛИ-HE_nn-ИЛИ-HE_nm, расположенных в n-й строке матрицы двухвходовых элементов ИЛИ-НЕ, соединены со входом стартового значения, равного логическому «0», что необходимо для задания направления проверки от последней строки матричного блока проверки к его первой строке; в состав блока матричного поиска введены однобитовый управляющий вход («Запись сравнений») для записи результатов сравнения i-го символа образца (i=1-n) и j-го символа текста (j=1-m) в поисковые ячейки блока матричного поиска, являющийся девятым управляющим входом устройства, а также однобитовый управляющий вход («Запись результатов»), являющийся десятым управляющим входом устройства; в состав каждой поисковой ячейки блока матричного поиска введен D-триггер с тремя входами, а также в состав каждой поисковой ячейки введены четвертый и пятый однобитовые входы и второй однобитовый выход, при этом четвертый однобитовый вход поисковой ячейки соединен с однобитовым управляющим входом «Запись сравнений» и со вторым входом D-триггера, пятый однобитовый вход поисковой ячейки соединен с первым входом начальной установки устройства и с первым входом D-триггера, третий информационный вход D-триггера соединен с выходом схемы сравнения на равенство р-разрядных кодов i-го символа образца (i=1-n) и j-го символа текста (j=1-m) в составе поисковой ячейки, каждая двухвходовая схема сравнения на равенство в составе поисковой ячейки состоит из р двухвходовых элементов суммы по модулю два с инверсией, на первые входы которых подается соответствующий разряд из i-й р-разрядной группы третьего входа блока матричного поиска, а на вторые входы двухвходовых элементов суммы по модулю два с инверсией -соответствующий разряд из j-й р-разрядной группы четвертого входа блока матричного поиска, выходы всех двухвходовых элементов суммы по модулю два с инверсией соединены с р-входовым элементом И, выход которого является выходом двухвходовой схемы сравнения на равенство, прямой выход D-триггера соединен с первым входом двухвходового элемента И в составе поисковой ячейки и является вторым выходом поисковой ячейки, второй вход двухвходового элемента И соединен с третьим входом поисковой ячейки, выход двухвходового элемента И является первым выходом поисковой ячейки, вторые однобитовые выходы n×k поисковых ячеек образуют второй информационный n×k-разрядный выход блока матричного поиска для выдачи матрицы результатов сравнений, первый выход (i, v)-й поисковой ячейки (i=1-n, v=1-k), кроме i=1, т.е. первой строки матрицы результатов сравнений, соединен с третьим входом (i-1, v-1)-й поисковой ячейки, кроме i=n, т.е. последней строки матрицы результатов сравнений, первый выход поисковой ячейки (1, v), расположенной в первой строке матрицы, соединен с третьим информационным входом v-го триггера позиции, на третьи входы поисковых ячеек (n, n) - (n, m), расположенных в последней строке матрицы, подается значение логической «1», задавая тем самым направление поиска по соответствующей диагонали от последней строки матрицы к первой строке включительно, на первые входы (i, v)-й поисковых ячеек n строк матрицы (i=1-n), (v=1-k) подаются р-разрядные выходы n регистров хранения символов образца, на вторые входы (j, t)-й поисковых ячеек m столбцов матрицы (j=1-m), (t=1-n) подаются р-разрядные выходы m регистров хранения символов текста, первый вход начальной установки устройства соединен со вторыми входами n регистров хранения символов образца и вторыми входами m регистров хранения символов текста; вход «Запись строк» блока матричного поиска соединен со вторыми входами m регистров для хранения кодов символов образца и вторыми входами m регистров для хранения кодов символов текста соответственно, первый информационный вход блока матричного поиска разрядностью р×n бит предназначен для параллельной записи образца в n регистров кодов символов образца, он состоит из n групп разрядов по р разрядов каждая группа, кодирующих символы образца, причем i-я группа разрядов (i=1-n) подается на третий р-разрядный вход регистра кода символа образца, второй информационный вход блока матричного поиска разрядностью р×m бит предназначен для параллельной записи текста в m регистров кодов символов текста, он состоит из m групп разрядов по р разрядов каждая группа, кодирующих символы текста, причем j-я группа разрядов (j=1-m) подается на третий р-разрядный вход регистра кода символа текста, первый вход блока матричного поиска, являющийся первым входом начальной установки устройства, соединен с первыми входами k триггеров позиций и с первыми входами n регистров кодов символов образца, а также с первыми входами m регистров кодов символов текста, вход «Запись результатов» блока матричного поиска соединен со вторыми входами k триггеров позиций, первые выходы k поисковых ячеек первой строки матрицы блока матричного поиска соединены с третьими информационными входами k триггеров позиций, выходы триггеров позиций являются k-разрядным выходом блока матричного поиска и образуют второй выход устройства.