- Программно-аппаратное проектирование для эффективного сопоставления регулярных шаблонов в памяти (arXiv)
Автор: Lingkun Kong, Qixuan Yu, Agnishom Chattopadhyay, Alexis Le Glaunec, Yi Huang, Konstantinos Mamouras, Kaiyuan Yang.
Аннотация: регулярное сопоставление с образцом используется во многих областях приложений, включая обработку текста, биоинформатику и сетевую безопасность. Шаблоны обычно выражаются с помощью расширенного синтаксиса регулярных выражений, которые включают вычислительно сложную конструкцию ограниченной итерации или подсчета, которая описывает повторение шаблона фиксированное количество раз. Мы разрабатываем дизайн специализированной аппаратной архитектуры в памяти для выполнения NFA, которая объединяет элементы счетчика и битового вектора. Дизайн вдохновлен теоретической моделью недетерминированных счетных автоматов (NCA). Ключевой особенностью нашего подхода является то, что мы статически анализируем регулярные выражения, чтобы определить границы объема памяти, необходимого для выполнения подсчета. Результаты этого анализа используются компилятором регулярных выражений для аппаратного обеспечения, чтобы сделать соответствующий выбор элементов счетчика или битового вектора. Мы оцениваем производительность нашей аппаратной реализации на симуляторе на основе параметров схемы, собранных с помощью моделирования SPICE с использованием 28-нм техпроцесса TSMC. Мы находим, что использование счетчика и битового вектора быстро превосходит развертывание решений на порядки величины с небольшими квантификаторами подсчета. Эксперименты, касающиеся реалистичных рабочих нагрузок, показывают снижение энергопотребления до 76 % и уменьшение занимаемой площади на 58 % по сравнению с традиционными процессорами NFA с памятью.
2. Неперекрывающееся (дельта, гамма) - приближенное сопоставление с образцом (arXiv)
Автор: Youxi Wu, Bojing Jian, Yan Li, He Jiang, Xindong Wu.
Аннотация: Сопоставление с образцом можно использовать для расчета поддержки шаблонов, и это ключевой вопрос в последовательном анализе шаблонов (или анализе шаблонов последовательности). Неперекрывающееся сопоставление с образцом означает, что два вхождения не могут использовать один и тот же символ в последовательности в одной и той же позиции. Приблизительное сопоставление с образцом допускает некоторый шум данных и является более общим, чем точное сопоставление с образцом. В настоящее время неперекрывающееся приближенное сопоставление с образцом основано на расстоянии Хэмминга, которое нельзя использовать для измерения локального приближения между подпоследовательностью и образцом, что приводит к большим отклонениям в результатах сопоставления. Чтобы решить эту проблему, мы представляем схему неперекрывающегося дельта- и гамма-аппроксимированного сопоставления с образцом (NDP), которая использует (дельта, гамма)-расстояние для получения приблизительного сопоставления с образцом, где локальное и глобальное расстояния не превышают дельта и гамма. соответственно. Сначала мы преобразуем задачу NDP в локальное приближенное сетевое дерево, а затем строим эффективный алгоритм, называемый локальным приближенным сетевым деревом для NDP (NetNDP). Мы предлагаем новый подход, называемый минимальным корневым расстоянием, который позволяет нам определить, есть ли у узла корневые пути, удовлетворяющие глобальному ограничению, и отсечь недопустимые узлы и отношения родитель-потомок. NetNDP находит самый правый абсолютный лист максимального корня, ищет самое правое вхождение из самого правого абсолютного листа и удаляет это вхождение. Мы повторяем вышеуказанные шаги до тех пор, пока не будет новых вхождений. Многочисленные эксперименты используются для проверки работоспособности предложенного алгоритма.
