будет ли эффективно использоваться gpu для задачи с конечным автоматом?

Помогите, пожалуйста, новичку, понять нужно ли ему GPU.

Есть конечный автомат (набор состояний и правил перехода из одного состояния в другое при обработке буквы. Например, автомат имеет три состояния 1,2,3 и правила: 1->2, если обрабатывается буква A, 2->3, если обрабатывается буква B, 1->3, если обрабатывается буква C. Если обрабатываемая буква не описана в правилах для текущего состояния, то автомат переходит в состояние 1. Запуская в такой автомат слово AB получаем состояние 3, запуская слово ACСCA получаем состояние 2[1->2->1->3->1->2]). Есть миллион слов. Нужно узнать достигается ли заданное состояние при обработке слова автоматом и установить все пары (слово, позиция в слове, на котором достигнуто данное состояние).

Автомат имеет размер не больше 1Кб. Слова разного размера -- от 16 букв до 24 тысяч. Разных букв всего 18.

Задача хорошо паралеллится: взяли миллион тредов (в смысле CPU) и каждому дали по слову.

Можно ли эффективно использовать GPU для этой задачи? Если да, то какова эффективная стратегия?

Forums: 

Основная проблема тут в том,

Основная проблема тут в том, что все треды на одном SM (в случае NVidia, но в OpenCL так же, думаю что и у AMD так же) исполняют одну и ту же инструкцию. Поэтому ветвления неэффективны, пока часть тредов исполняет одну ветку if-а, вторая часть -простаивает.

Если можно конечный автомат представить в виде таблицы разумного размера, чтобы не было ветвлений, а по текущей букве и текущему состоянию таблично вычислялось бы следущее - то все будет отлично. Если писать КА в виде длинного набора if-ов, то будет плохо.

спасибо за ответ!

С 18 буквами не сложно представить автомат таблицей. Но if все равно неизбежен вроде как -- надо же проверить, что достигнутое состояние именно то, которое требуется. И этот if будет выполняться после каждого перехода. М-да.

Ну подождите, вы же можете

Ну подождите, вы же можете сделать проверку тоже таблицей, у которой в нужном индексе - единица, в остальных - нули и инкрементить результат на каждой букве:
result+= table[state];
В result у вас будет число достижений состояний в процессе обработки.

Я задачу представляю очень примерно, наверное там еще какие-то проблемы будут. Например, слова разной длины, ну так выгоднее заранее их разбить так, чтобы один thread block работал со словами одинаковой длины.