Есть такой kernel. Выполняется на линейном гриде 4096x1 из линейных блоков 128x1x1, если я ничего не путаю. automat лежит в памяти девайса и занимает sizeof(int)*N*18 памяти, используется всеми нитями. Int-ы тут особенно не нужны, для book и для automat хватило бы и однобайтного типа данных. Куда можно положить automat, чтобы оптимизировать работу программы? И что еще можно оптимизировать?

//N ~ 100
__global__ void searchTemplate(int* book, int* c_end, int* n_end, int* automat, int N, int K, int* res)
{
    int state=0;
    int idx = blockDim.x*blockIdx.x + threadIdx.x;
    int out_x = idx * (N-K) - K;
    for (int i=c_end[idx]; i<=n_end[idx]; i++)
    {
        state = automat[ state * 18 + book[i] ];
        if (state > K)
            res[out_x + state] = i;
    }
}