# Is this problem statement good for a GPU?

I am used to using GPU hardware for large scale matrix operations and vectorizing mathematical operations on a continuous space which has been discretized for numerical computation, but this is a completely different problem and I would like to know if it is suitable for a GPU.

Suppose I have a string X of length N and a string Y of length M, such that N < M. I can use, for example, the Python statement if( X in Y ) to find if X is a substring of Y. Now, suppose that I have a string X and 10 million strings {Y_i}. Is it possible (worth it) to put this type of problem on a GPU? Rather than having this be 10 million operations, we could do it in one operation on a GPU, right?

The reason I am asking is that, in reality, I have maybe 10 Billion strings {X_i} and need to, for each string, compare it to every string in {Y_i} and am wondering if I can make it so that finding X in any of {Y_i} will be a GPU kernel for when these sets get incredibly large.

• Do you always need to check whether $X \subset Y_i$ for all $i$-s or do you just need to find a few strings $Y_j$ such that $X \subset Y_j$? In the latter case you would get the most speedup by ordering the sets $Y_i$ properly rather than parallelizing. – Jakub Klinkovský May 11 '17 at 19:14