Матричное устройство для быстрого поиска вхождений и обработки данных

Изобретение относится к области вычислительной техники. Технический результат направлен на уменьшение времени поиска вхождений образца в тексте. Матричное устройство для быстрого поиска вхождений и обработки данных, содержащее первый и второй блоки хранения и сравнения ассоциативных признаков, блок памяти логических векторов, операционный блок и блок матричного поиска, при этом в состав блока матричного поиска введены однобитовый управляющий вход «Запись сравнений» для записи результатов сравнения i-го символа образца (i=1-n) и j-го символа текста (j=1-m) в поисковые ячейки блока матричного поиска, являющийся девятым управляющим входом устройства, а также однобитовый управляющий вход «Запись результатов» для записи результатов поиска вхождений в триггер позиций поиска. 5 ил.

 

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

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

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

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

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

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

Решение технической задачи достигается тем, что в матричное устройство для быстрого поиска вхождений и обработки данных (далее - устройство), содержащее первый и второй блоки хранения и сравнения ассоциативных признаков, блок памяти логических векторов, операционный блок и блок матричного поиска, причем информационные входы первого и второго блоков хранения и сравнения ассоциативных признаков являются соответственно первым и вторым информационными входами устройства, а выходы блоков хранения и сравнения ассоциативных признаков соединены соответственно с первым и вторым адресными входами блока памяти логических векторов, входы задания режимов первого и второго блоков хранения и сравнения ассоциативных признаков и вход записи-считывания блока памяти логических векторов являются соответственно первым, вторым и третьим входами задания режимов устройства, а четвертый, пятый, шестой входы задания режимов устройства соответственно соединены с тремя входами кодов операций операционного блока, первый выход которого является первым выходом устройства, первый вход начальной установки устройства подключен к входу начальной установки операционного блока и первому входу блока матричного поиска, второй вход начальной установки - к входам начальной установки первого и второго блоков хранения и сравнения ассоциативных признаков, первый и второй выходы блока памяти логических векторов подключены соответственно к первому и второму информационным входам операционного блока, второй выход которого («Запись строк») подключен ко второму входу блока матричного поиска, два информационных входа которого являются внешними третьим и четвертым входами устройства, а первый выход блока матричного поиска является вторым выходом устройства, содержащее в составе блока матричного поиска n p-разрядных регистров хранения символов образца, образующих третий p×n-разрядный информационный вход устройства, причем i-ая группа разрядов (i=1-n) подается на третий p-разрядный вход i-го регистра кода символа образца, и m p-разрядных регистров хранения символов текста, образующих четвёртый p×m-разрядный информационный вход устройства, причем j-ая группа разрядов (j=1-m) подается на третий p-разрядный вход j-го регистра кода символа текста, первый вход начальной установки устройства подключен к первым входам n регистров хранения символов образца и m регистров хранения символов текста, а также к первым входам k триггеров позиций, выходы триггеров позиций являются k-разрядным выходом блока матричного поиска и образуют второй выход устройства, вход «Запись строк» соединен со вторыми входами n регистров для хранения кодов символов образца и вторыми входами m регистров для хранения кодов символов текста соответственно, отличающееся тем, что в состав блока матричного поиска дополнительновведены однобитовый управляющий вход «Запись сравнений» для записи результатов сравнения i-го символа образца (i=1-n) и j-го символа текста (j=1-m) в поисковые ячейки блока матричного поиска, являющийся девятым управляющим входом устройства, а также однобитовый управляющий вход «Запись результатов» для записи результатов поиска вхождений в триггера позиций, являющийся десятым управляющим входом устройства, также введены в составе блока матричного поиска n×k поисковых ячеек (k=m-n+1 – количество диагоналей в матрице), имеющих по 4 входа и 1 выход каждая ячейка, и k блоков параллельного вычисления логической функции конъюнкции, при этом каждый такой v-ый блок имеет n входов и 1 выход (v=1..k), выход v-го блока соединен с третьим входом v-го триггера позиций, n выходов поисковых ячеек v-ой диагонали матрицы соединены с n входами v-го блока параллельного вычисления логической функции конъюнкции, каждый такой блок состоит из n-входового элемента И, n выходов поисковых ячеек v-й диагонали блока матричного поиска ((v,1), (v,2)), ((v,3), … … (v,n-2)), ((v,n-1), (v,n)) соединены со входами n-входового элемента И в составе v-го блока параллельного вычисления логической функции конъюнкции; на первые входы (i,v)-й поисковых ячеек n строк матрицы (i=1-n), (v=1-k) подаются p-разрядные выходы n регистров хранения символов образца, на вторые входы (j,t)-й поисковых ячеек m столбцов матрицы (j=1-m), (t=1-n) подаются p-разрядные выходы m регистров хранения символов текста, однобитовый управляющий вход «Запись сравнений» соединен с третьими входами n×k поисковых ячеек, однобитовый управляющий вход «Запись результатов» подключен ко вторым входам k триггеров позиций, первый вход начальной установки подключён к четвертым входам n×k поисковых ячеек; в состав поисковой ячейки входят D-триггер с тремя входами и схема сравнения на равенство p-разрядных кодов i-го символа образца (i=1-n) и j-го символа текста (j=1-m), причем первый вход поисковой ячейки является первым входом схемы сравнения на равенство, второй вход поисковой ячейки является вторым входом схемы сравнения на равенство, третий вход поисковой ячейки соединен со вторым входом D-триггера, четвертый вход поисковой ячейки соединен с первым входом D-триггера, третий вход D-триггера соединен с выходом схемы сравнения на равенство p-разрядных кодов i-го символа образца (i=1-n) и j-го символа текста (j=1-m) в составе поисковой ячейки, прямой выход D-триггера является выходом поисковой ячейки; каждая двухвходовая схема сравнения на равенство в составе поисковой ячейки состоит из p двухвходовых элементов суммы по модулю два с инверсией, на первые входы которых подается соответствующий разряд из i-ой р-разрядной группы третьего входа блока матричного поиска, а на вторые входы двухвходовых элементов суммы по модулю два с инверсией - соответствующий разряд из j-ой р-разрядной группы четвертого входа блока матричного поиска, выходы всех двухвходовых элементов суммы по модулю два с инверсией соединены с p-входовым элементом И, выход которого является выходом двухвходовой схемы сравнения на равенство, который подается на третий вход D-триггера.

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

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

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

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

Блок 4 матричного поиска содержит n регистров 32₁-32_n для хранения кодов символов образца, m регистров 33₁–33_m для хранения кодов символов текста, матрицу поисковых ячеек 34₁₁–34_nm , k триггеров 37 позиций, k блоков параллельного вычисления логической функции конъюнкции, причем регистр 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). Выходы поисковых ячеек v-ой диагонали 34_v1–34_vn соединены с n входами v-го блока 41_v параллельного вычисления логической функции конъюнкции (v=1-k).

Матрица поисковых ячеек 34₁₁–34_nm состоит из n×k ячеек (k=m-n+1 – количество диагоналей в матрице) и k блоков 41₁ – 41_k параллельного вычисления логической функции конъюнкции, причем каждая поисковая ячейка 34_ij имеет четыре входа и один однобитовый выход, каждая поисковая ячейка 34_ij содержит двухвходовую схему 35 сравнения на равенство p-разрядных кодов символов образца и текста, D-триггер 40, каждая двухвходовая схема 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 является выходом ячейки 34_ij. Однобитовый третий вход поисковой ячейки 34_ij соединен с управляющим входом «Запись сравнений» устройства, однобитовый четвертый вход поисковой ячейки 34_ij соединен с первым входом 7₁ начальной установки устройства.

Матрица поисковых ячеек 34₁₁–34_nm имеет геометрическую форму параллелограмма, в которой в каждой строке располагается k поисковых ячеек, сдвинутых относительно следующей строки ячеек влево на 1 позицию, начиная с ячеек последней строки 34_nn–34_nm. Такая форма матрицы обеспечивает организацию параллельного поиска по k диагоналям поисковых ячеек, соединённых с k блоками 41₁–41_k параллельного вычисления логической функции конъюнкции.

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

Каждый блок 41_v параллельного вычисления логической функции конъюнкции (v=1-k) состоит n-входового элемента 42 И. N выходов поисковых ячеек v-й диагонали блока матричного поиска ((v,1), (v,2)), ((v,3), … … (v,n-2)), ((v,n-1), (v,n)) соединены со входами n-входового элемента 42 И в составе v-го блока параллельного вычисления логической функции конъюнкции, выход v-го элемента 42 И является выходом блока 41_v параллельного вычисления логической функции конъюнкции.

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

С учетом появления дополнительных управляющих входов «Запись сравнений» и «Запись результатов» описание режима «Операция» имеет следующий вид.

Пусть устройство выполняет режим «Операция» с кодом операции «ПВ». На вход 7₁ «Начальная установка» операционного блока 3 и блока 4 матричного поиска подается импульсный сигнал начальной установки, который сбрасывает в нулевое состояние: регистр 22 команд по его входу 1, регистр 30 по его входу 1, а также k триггеров 37 позиций по их входу 1, n регистров 32 по их входу 1 и m регистров 33 по их входу 1, D-триггеров в составе поисковых ячеек 34₁₁–34_nm, имеющих форму параллелограмма. После окончания действия сигнала начальной установки на вход 6₆ режима работы операционного блока 3 подается код операции «ПВ», который обнаруживается дешифратором 23 команд и со второго выхода операционного блока 3 на второй вход «Запись строк» блока 4 матричного поиска подается импульсный сигнал. Данный импульсный сигнал по входу «Запись строк» блока 4 матричного поиска подается соответственно на вторые входы разрешения записи n регистров 32 для хранения кодов символов образца и на вторые входы разрешения записи m регистров 33 для хранения кодов символов текста, обеспечивая тем самым запись n символов образца и m символов текста в параллельном коде с информационных входов 4₃ и 4₄ устройства. Сигнал по управляющему входу «Запись сравнений» обеспечивает запись результатов сравнений n символов образца и m символов текста в D-триггера поисковых ячеек 34₁₁–34_nm, образуя начальную матрицу поиска, представляющую собой двоичную матрицу параллельных сравнений ij-ых символов образца и текста (i=1…n, j=1…m). Выходы поисковых ячеек, расположенных по k диагоналям матрицы 34₁₁–34_nm, параллельно подаются на входы блоков 41₁–41_k параллельного вычисления логической функции конъюнкции, тем самым сокращая время поиска вхождений по k диагоналям матрицы поисковых ячеек 34₁₁–34_nm. По сигналу на управляющем входе «Запись результатов» обеспечивается запись выходов блоков 41₁–41_k параллельного вычисления логической функции конъюнкции в k триггеров 37₁–37_k позиций.

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

Матричное устройство для быстрого поиска вхождений и обработки данных, содержащее первый и второй блоки хранения и сравнения ассоциативных признаков, блок памяти логических векторов, операционный блок и блок матричного поиска, причем информационные входы первого и второго блоков хранения и сравнения ассоциативных признаков являются соответственно первым и вторым информационными входами устройства, а выходы блоков хранения и сравнения ассоциативных признаков соединены соответственно с первым и вторым адресными входами блока памяти логических векторов, входы задания режимов первого и второго блоков хранения и сравнения ассоциативных признаков и вход записи-считывания блока памяти логических векторов являются соответственно первым, вторым и третьим входами задания режимов устройства, а четвертый, пятый, шестой входы задания режимов устройства соответственно соединены с тремя входами кодов операций операционного блока, первый выход которого является первым выходом устройства, первый вход начальной установки устройства подключен к входу начальной установки операционного блока и первому входу блока матричного поиска, второй вход начальной установки - к входам начальной установки первого и второго блоков хранения и сравнения ассоциативных признаков, первый и второй выходы блока памяти логических векторов подключены соответственно к первому и второму информационным входам операционного блока, второй выход которого («Запись строк») подключен ко второму входу блока матричного поиска, два информационных входа которого являются внешними третьим и четвертым входами устройства, а первый выход блока матричного поиска является вторым выходом устройства, содержащее в составе блока матричного поиска n p-разрядных регистров хранения символов образца, образующих третий p×n-разрядный информационный вход устройства, причем i-ая группа разрядов (i=1-n) подается на третий p-разрядный вход i-го регистра кода символа образца, и m p-разрядных регистров хранения символов текста, образующих четвёртый p×m-разрядный информационный вход устройства, причем j-ая группа разрядов (j=1-m) подается на третий p-разрядный вход j-го регистра кода символа текста, первый вход начальной установки устройства подключен к первым входам n регистров хранения символов образца и m регистров хранения символов текста, а также к первым входам k триггеров позиций, выходы триггеров позиций являются k-разрядным выходом блока матричного поиска и образуют второй выход устройства, вход «Запись строк» соединен со вторыми входами n регистров для хранения кодов символов образца и вторыми входами m регистров для хранения кодов символов текста соответственно, отличающееся тем, что в состав блока матричного поиска дополнительновведены однобитовый управляющий вход «Запись сравнений» для записи результатов сравнения i-го символа образца (i=1-n) и j-го символа текста (j=1-m) в поисковые ячейки блока матричного поиска, являющийся девятым управляющим входом устройства, а также однобитовый управляющий вход «Запись результатов» для записи результатов поиска вхождений в триггера позиций, являющийся десятым управляющим входом устройства, также введены в составе блока матричного поиска n×k поисковых ячеек (k=m-n+1 – количество диагоналей в матрице), имеющих по 4 входа и 1 выход каждая ячейка, и k блоков параллельного вычисления логической функции конъюнкции, при этом каждый такой v-й блок имеет n входов и 1 выход (v=1...k), выход v-го блока соединен с третьим входом v-го триггера позиций, n выходов поисковых ячеек v-й диагонали матрицы соединены с n входами v-го блока параллельного вычисления логической функции конъюнкции, каждый такой блок состоит из n-входового элемента И, n выходов поисковых ячеек v-й диагонали блока матричного поиска ((v,1), (v,2)), ((v,3), … … (v,n-2)), ((v,n-1), (v,n)) соединены со входами n-входового элемента И в составе v-го блока параллельного вычисления логической функции конъюнкции; на первые входы (i,v)-й поисковых ячеек n строк матрицы (i=1-n), (v=1-k) подаются p-разрядные выходы n регистров хранения символов образца, на вторые входы (j,t)-й поисковых ячеек m столбцов матрицы (j=1-m), (t=1-n) подаются p-разрядные выходы m регистров хранения символов текста, однобитовый управляющий вход «Запись сравнений» соединен с третьими входами n×k поисковых ячеек, однобитовый управляющий вход «Запись результатов» подключен ко вторым входам k триггеров позиций, первый вход начальной установки подключён к четвертым входам n×k поисковых ячеек; в состав поисковой ячейки входят D-триггер с тремя входами и схема сравнения на равенство p-разрядных кодов i-го символа образца (i=1-n) и j-го символа текста (j=1-m), причем первый вход поисковой ячейки является первым входом схемы сравнения на равенство, второй вход поисковой ячейки является вторым входом схемы сравнения на равенство, третий вход поисковой ячейки соединен со вторым входом D-триггера, четвертый вход поисковой ячейки соединен с первым входом D-триггера, третий вход D-триггера соединен с выходом схемы сравнения на равенство p-разрядных кодов i-го символа образца (i=1-n) и j-го символа текста (j=1-m) в составе поисковой ячейки, прямой выход D-триггера является выходом поисковой ячейки; каждая двухвходовая схема сравнения на равенство в составе поисковой ячейки состоит из p двухвходовых элементов суммы по модулю два с инверсией, на первые входы которых подается соответствующий разряд из i-й р-разрядной группы третьего входа блока матричного поиска, а на вторые входы двухвходовых элементов суммы по модулю два с инверсией - соответствующий разряд из j-й р-разрядной группы четвертого входа блока матричного поиска, выходы всех двухвходовых элементов суммы по модулю два с инверсией соединены с p-входовым элементом И, выход которого является выходом двухвходовой схемы сравнения на равенство, который подается на третий вход D-триггера.