Результат интеллектуальной деятельности: Матричное устройство параллельного поиска составного образца

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

Известно устройство для параллельного поиска и обработки данных [Патент 72771 Российская Федерация, МПК G06 F 12/00. опубл. 27.04.2008, Бюл. №12], состоящее из двух блоков хранения и сравнения ассоциативных признаков, блока памяти логических векторов, операционного блока и блока матричного поиска, выполняющее параллельную обработку совокупности характеристических векторов, объединенных в двумерную матрицу поиска. Недостатком данного устройства является ограниченная функциональность – устройство позволяет осуществлять только поиск вхождений образца, состоящего только из одной подстроки. Характеристическая матрица поиска имеет геометрическую форму параллелограмма, а связи между смежными элементами диагоналей имеют локальный характер, что не позволяет этому устройству решать задачу поиска составного образца в анализируемой последовательности.

Известны способ и устройство поиска составного образца в последовательности [Патент №2549525 РФ, МПК G06F 12/00, G06F 17/30. 013; опубл. 20.01.2015, Бюл. №12], состоящий из блока хранения и сравнения ассоциативных признаков, блока памяти логических векторов, операционного блока, блока поиска составного образца, содержащего в составе каждой строки характеристической матрицы поисковых ячеек последовательность двухвходовых элементов ИЛИ, позволяющих вычислять стартовые значения поисковых ячеек для поиска составного образца. Недостатком данного способа и устройства является последовательный характер вычисления стартовых значений, что приводит к непродуктивным затратам времени на поиск составного образца.

Устройством-прототипом является устройство параллельного поиска составного образца [Патент№ 163442 РФ, МПК G06 F 12/00, опубл. 20.07.2016 г., Бюл. №20], состоящий из блока хранения и сравнения ассоциативных признаков, блока памяти логических векторов, операционного блока, блока параллельного поиска составного образца, содержащего, в том числе, блок многовходовых элементов ИЛИ с избыточным количеством элементов и входов, что приводит к увеличению аппаратных затрат на вычисление стартовых значений ячеек строк матрицы.

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

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

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

Матричное устройство параллельного поиска составного образца (фиг. 1) содержит блоки 1₁ и 1₂ хранения и сравнения ассоциативных признаков, блок 2 памяти логических векторов, операционный блок 3, блок 4 параллельного поиска составного образца, информационные входы 4₁, 4₂, 4₃ и 4₄, информационные выходы 5₁, 5₂, входы 6₁–6₆ задания режима работы, входы 7₁ и 7₂ начальной установки.

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

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

Блок 4 параллельного поиска составного образца содержит элемент 31 задержки, состоящий из m пар инверторов, n регистров 32₁-32_n для хранения кодов символов составного образца, m регистров 33₁-33_m для хранения кодов символов текста, характеристической матрицы поисковых ячеек 34₁₁-34_nm, и n-1 блоков 40 многовходовых элементов ИЛИ с регулярной структурой, k триггеров 37 позиций, причем регистр 32_i (i=1-n) и регистр 33_j (j=1-m) содержат первый и второй управляющие входы, третий p-разрядный информационный вход и один выход соответственно. Первые и вторые входы n регистров 32 для хранения кодов символов составного образца и первые и вторые входы m регистров 33 для хранения кодов символов текста соединены соответственно с первым и вторым управляющими входами блока 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). Второй управляющий вход «Запись строк» блока 4 параллельного поиска составного образца также соединен со входом элемента 31 задержки, выход элемента 31 задержки соединен со вторыми входами триггеров 37₁-37_k позиций, выходы которых образуют информационный k-разрядный выход 5₂ блока 4 параллельного поиска составного образца, выходы поисковых ячеек 34_nn-34_nm n-й строки характеристической матрицы соединены с третьими входами триггеров 37₁-37_k позиций. Первый управляющий вход 7₁ блока 4 параллельного поиска составного образца также соединен с первыми входами триггеров 37₁-37_k позиций.

Характеристическая матрица поисковых ячеек 34₁₁-34_nm имеет размер n×k ячеек (k=m-n+1 - количество диагоналей в матрице), причем каждая поисковая ячейка 34_ij имеет три входа и один выход и содержит двухвходовую схему 35_ij сравнения на равенство p-разрядных кодов символов составного образца и текста и двухвходовой элемент 36 И, каждая двухвходовая схема 35_ij сравнения на равенство в составе поисковой ячейки 34_ij состоит из p-входового элемента 39 И, а также 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 сравнения на равенство, выход которой является первым входом двухвходового элемент 36 И, второй вход которого является третьим входом поисковой ячейки 34_ij, выходом которой является выход двухвходового элемента 36 И.

Характеристическая матрица поисковых ячеек 34₁₁-34_nm имеет геометрическую форму параллелограмма, в которой в каждой строке располагается k поисковых ячеек, сдвинутых относительно следующей строки ячеек вправо на 1 позицию, начиная с ячеек первой строки 34₁₁-34_1k. Такая форма матрицы обеспечивает направление поиска по диагоналям, проходящим через ячейки от первой строки к последней строке включительно. Также в каждую строку характеристической матрицы, кроме последней строки, входит блок 40 многовходовых элементов ИЛИ с регулярной структурой, имеющий k входов и k выходов, состоящий из k-1 элементов 41 ИЛИ: начального двухвходового элемента 41₂ ИЛИ, следующего трехвходового элемента 41₃ ИЛИ, четырехвходового элемента 41₄ ИЛИ и т.д. k-входового элемента 41_k ИЛИ, обеспечивающих параллельное вычисление стартовых значений ячеек в пределах строки.

Z-й вход блока 40 многовходовых элементов ИЛИ с регулярной структурой, кроме z=2, соединен с первым входом соответствующего элемента 41₂– 41_k ИЛИ (z=1-k), второй вход блока 40 многовходовых элементов ИЛИ с регулярной структурой соединен со вторым входом двухвходового элемента 41₂ ИЛИ, выход v-го элемента 41_v ИЛИ является
v-ым выходом блока 40 многовходовых элементов ИЛИ с регулярной структурой и соединен с v+1 входом каждого из элементов 41_v+1 – 41_k-1 ИЛИ (v=2 – k-1), выход k-го элемента 41_k ИЛИ является k-ым выходом блока 40 многовходовых элементов ИЛИ с регулярной структурой, первый вход блока 40 многовходовых элементов ИЛИ с регулярной структурой является его первым выходом и соединен с вторым входом каждого из элементов 41₃ – 41_k ИЛИ.

K выходов поисковых ячеек i-ой строки характеристической матрицы поисковых ячеек, кроме i=n (последняя строка), соединены с соответствующими k входами i-го блока 40 многовходовых элементов ИЛИ с регулярной структурой, k выходов которого соединены с соответствующими третьими входами поисковых ячеек i+1-й строки характеристической матрицы поисковых ячеек.

На третьи входы поисковых ячеек 34₁₁-34_1k, расположенных в первой строке характеристической матрицы поисковых ячеек, подано значение логической «1», выходы поисковых ячеек 34_nn-34_nm, расположенных в последней (n-й) строке характеристической матрицы поисковых ячеек, соединены с третьими входами триггеров 37₁-37_k позиций.

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

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

В алгоритме режима "Операция" операция поиска составного образца, обозначаемая как «ПСО» и имеющая собственный код операции, имеет временную особенность, связанную с организацией блоков 40₁-40_n-1 многовходовых элементов ИЛИ с регулярной структурой.

Пусть устройство выполняет режим «Операция» с кодом операции «ПСО». На вход 7₁ «Начальная установка» операционного блока 3 и блока 4 параллельного поиска составного образца подается импульсный сигнал начальной установки, который сбрасывает в нулевое состояние регистр 22 команд по его входу 1, регистр 30 по его входу 1, а также k триггеров 37 позиций по их входу 1, n регистров 32 по их входу 1 и m регистров 33 по их входу 1. После окончания действия сигнала начальной установки на вход 6₆ режима работы операционного блока 3 подается код операции «ПСО», который обнаруживается дешифратором 23 команд и со второго выхода операционного блока 3 на второй вход «Запись строк» блока 4 параллельного поиска составного образца подается импульсный сигнал. Данный импульсный сигнал по входу «Запись строк» блока 4 параллельного поиска составного образца подается соответственно на вторые входы разрешения записи n регистров 32 для хранения кодов символов составного образца и на вторые входы разрешения записи m регистров 33 для хранения кодов символов текста, обеспечивая тем самым запись n символов составного образца и m символов текста в параллельном коде с входов 4₃ и 4₄ устройства. Также импульсный сигнал по входу «Запись строк» блока 4 параллельного поиска составного образца через элемент 31 задержки подается соответственно на вторые входы разрешения записи k триггеров 37 позиций. Элемент 31 задержки, выполненный в виде m пар инверторов, необходим для завершения процессов поиска составного образца по диагоналям характеристической матрицы, состоящей из поисковых ячеек 34₁₁ – 34_nm. Поиск начинается с ячеек первой строки характеристической матрицы. Начальный k-битовый характеристический вектор, равный 11…1, подается на третьи входы поисковых ячеек первой строки характеристической матрицы и определяет тем самым направление параллельного поиска по всем диагоналям характеристической матрицы от поисковых ячеек первой строки до поисковых ячеек последней строки включительно. Применение n-1 блоков 40 многовходовых элементов ИЛИ с регулярной структурой, имеющих k-1 элементов ИЛИ, сокращает время вычисления стартовых точек до (k-1)/2τ_ИЛИ, где τ_ИЛИ – время задержки на элементе 41 ИЛИ. По завершении процессов поиска импульсный сигнал с выхода элемента 31 задержки через время T^’=m2τ_инв (2τ_инв – время задержки на паре инверторов) записывает k-битовый результат поиска составного образца в триггера 37₁-37_k позиций. Выходы триггеров 37₁-37_k позиций являются k-разрядным выходом блока 4 параллельного поиска составного образца и образуют второй выход устройства 5₂.

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

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