Комментарии 7
Эх, еще бы сравнить все эти реализации с нормальным Ахо-Корасиком с префиксными ссылками и полным конечным автоматом, хоть и в один поток. Я предполагаю, что для любого большого количества паттернов оно будет в те же 5-10 раз быстрее GPU-шной рализации. А если еще и тестовые данные неудачно подобрать (мало разных символов), то вообще в десятки раз быстрее.
Без этого делать выводы о полезности CUDA в этой области преждевременно. Взяли какой-то урезанный алгоритм, который можно распараллелить, и получили что он параллелится, да. Но насколько это дало пользу по сравнению с потерями от урезания алгоритма — вопрос остался неисследованным.
Последовательный классический АК работает линейно, при последовательной реализации АК без сходов, асимптотика O(NM), где N — длина текста, M — средняя глубина поиска по префиксному дереву. Мы пользуемся идеей, что M будет не слишком велико и коэффициент параллельности его перекроет.
Ускорение 5-10 раз по сравнению с GPU я бы не стал раньше времени ожидать. АК на большом количестве признаков тоже будет деградировать. Локальность памяти для RAM никто не отменял.
Ну ведь в АК без сходов тоже идет ветвление и прыжки по префиксному дереву. Со сходами дерево будет занимать немного больше памяти из-за дополнительных переходов. Так что проблемы из-за локальности памяти есть и тут и там.
Да, про 5-10 раз в среднем я переборщил, наверно. Думаю, в 2 раза в средних случаях будет быстрее. В статье GPU лучше чем CPU (однопоточное) всего в 4 раза при в большинстве слечаев. Если средняя глубина хотя бы 8 символов — вот и 2 раза будет. Но, опять же, для сложных неудачных тестов, например днк с длинными паттернами средняя длина совпадения будет весьма большой.
Конечно, в очень специфичных случаях, если все паттерны короткие — то есть смысл параллелить. Но это надо отдельно указывать при сравнении.
В статье я лишь хочу сказать, что данный подход имеет место быть и может дать прирост в производительности. Ограничения эффективной применимости требуют дополнительного исследования.
Как обычно, реквестирую сравнение с hyperscan от Intel и с https://github.com/mischasan/aho-corasick
Multi-pattern matching на GPU миф или реальность