АППАРАТНО-ОРИЕНТИРОВАННЫЙ МЕТОД УСКОРЕННОГО ПОИСКА ВХОЖДЕНИЙ ОБРАЗЦА НА ОСНОВЕ СТРУКТУРНО-ПРОЦЕДУРНЫХ ВЫЧИСЛЕНИЙ

Аннотация

Операция поиска вхождений образца в тексте является общезначимой в современных вы- числительных средствах при решении проблемно-поисковых задач. Наибольший интерес пред- ставляют аппаратно-программные решения, имеющие однородную структуру и регулярные связи между вычислительными блоками. Целью работы является сокращение временных затрат на поиск вхождений на основе применения параллельного поиска в ассоциативной памяти и метода распараллеливания по итерациям. Предлагаемый метод использует ассоциативную память для параллельного поиска вхождений и динамическую реконфигурации структуры исходной строки из одномерного вида в матричную форму. Вовлечение в реконфигурацию всех элементов влечет из- быточные затраты внутренней блочной памяти на последовательный просмотр частичных вхо- ждений по одному множеству стартовых позиций, кратных длине образца (второй символьный операнд. Вместо этого предложен метод совмещения во времени поиска частичных вхождений по двум наборам подстрок, кратных длине образца, с одновременным пропорциональным уменьшени- ем элементов разрядного среза ассоциативной памяти по каждому набору, что позволяет на те- кущем шаге поиска обрабатывать несколько символов образца. Количественные оценки времени поиска определяются количеством операций сравнения и записи подстрок в общем цикле работы, а также пропорциями времени данных операций. Показано, что для образцов более 10 элементов временной выигрыш составляет примерно в 1,8-2 раза. Данный эффект получен за счет исключе- ния шагов последовательного сдвига с переходами между граничными элементами строк. Разра- ботанный метод обеспечивает конвейерную обработку потока строковых операндов с совмеще- нием просмотра на текущем шаге поиска неединичного множества символов обрабатываемой строки. Сокращение времени поиска обеспечивается введением конвейера, количество ступеней которого зависит от коэффициента редукции размера разрядного среза, что позволяет аппарат- но реализовать структурно-процедурный подход, применяемый в реконфигурируемых вычисли- тельных системах