АППАРАТНО-ОРИЕНТИРОВАННЫЙ МЕТОД УСКОРЕННОГО ПОИСКА ВХОЖДЕНИЙ ОБРАЗЦА НА ОСНОВЕ СТРУКТУРНО-ПРОЦЕДУРНЫХ ВЫЧИСЛЕНИЙ
Аннотация
Операция поиска вхождений образца в тексте является общезначимой в современных вы-
числительных средствах при решении проблемно-поисковых задач. Наибольший интерес пред-
ставляют аппаратно-программные решения, имеющие однородную структуру и регулярные связи
между вычислительными блоками. Целью работы является сокращение временных затрат на
поиск вхождений на основе применения параллельного поиска в ассоциативной памяти и метода
распараллеливания по итерациям. Предлагаемый метод использует ассоциативную память для
параллельного поиска вхождений и динамическую реконфигурации структуры исходной строки из
одномерного вида в матричную форму. Вовлечение в реконфигурацию всех элементов влечет из-
быточные затраты внутренней блочной памяти на последовательный просмотр частичных вхо-
ждений по одному множеству стартовых позиций, кратных длине образца (второй символьный
операнд. Вместо этого предложен метод совмещения во времени поиска частичных вхождений по
двум наборам подстрок, кратных длине образца, с одновременным пропорциональным уменьшени-
ем элементов разрядного среза ассоциативной памяти по каждому набору, что позволяет на те-
кущем шаге поиска обрабатывать несколько символов образца. Количественные оценки времени
поиска определяются количеством операций сравнения и записи подстрок в общем цикле работы,
а также пропорциями времени данных операций. Показано, что для образцов более 10 элементов
временной выигрыш составляет примерно в 1,8-2 раза. Данный эффект получен за счет исключе-
ния шагов последовательного сдвига с переходами между граничными элементами строк. Разра-
ботанный метод обеспечивает конвейерную обработку потока строковых операндов с совмеще-
нием просмотра на текущем шаге поиска неединичного множества символов обрабатываемой
строки. Сокращение времени поиска обеспечивается введением конвейера, количество ступеней которого зависит от коэффициента редукции размера разрядного среза, что позволяет аппарат-
но реализовать структурно-процедурный подход, применяемый в реконфигурируемых вычисли-
тельных системах
