CUDA grep

I know you guys are eyeballs deep in your data, so what's obvious to you may not be obvious to a reader. From what I can tell, your performance numbers are reported as an average per regex. But you're calculating that without including the string copying cost; you're only timing the cost of performing the computation on the GPU.

You show the overhead in absolute numbers. It seems small compared to the cost of processing the whole file, but I need to know the cost for grep to process that whole file as well. Basically, you show me a number, but you don't explain the significance of this number.

In my experience, the best way to deal with such issues is to always report entire-application performance. (This can be in addition to other numbers, of course.) That way I can say "Ah, calling grep took x seconds on average, calling their program took y seconds on average, and y < x, so they've improved performance." If you report entire-application performance, your reader doesn't need to understand the particulars to at least determine if your technique is a performance win.

Since people seem really interested in this, mburman and I are going to spend the day fixing up this project.

This was a final project for 15-418 in Spring of 2012 (that was a great class). We need to update it for the newer versions of CUDA, and we'll probably clean up some of our code since we're both better programmers now.

Pull-requests always welcome!

Admittedly, I assumed this was already the case after reading the article title, since parsing each line in parallel would present a great deal of parallelism with growing filesizes. Indeed, they also came to the same conclusion:

we realized that it was a much better idea to parallelize across the lines of the input file against which we had to match regexs

That was also a great choice for future scalability, as no doubt you would get greater parallelism with a growing input file (while also allowing opportunities to speed up more complex expressions).

http://dolores.sp.cs.cmu.edu/15418_spr13/

Which answers the first question that comes to mind 'why would anyone do this, for an i/o bound process'. For homework, of course.

It seems like this is only fast on large files, though, because the text needs to be copied from the main RAM memory to the GPU, which introduces latency. I wonder what latency would be like if this algorithm was instead run on the kind of unified memory architecture that you see in e.g. the PS2 and XBox One.

Also, I don't quite follow why they're compiling the finite automata on the GPU. To me their explanation that they didn't want to copy the automaton node per node sort of sounds like there's a lot of room for optimization here. E.g. maybe the regular expressions could be compiled to OpenCL code.

Then again, they did also find that pattern matching is a memory bound problem so maybe emitting native code is pointless. Anyone know if there are regular expression engines that compile emit native x86 code?

> Searching for hay in the haystack is not a common use case for a regular expression matcher.

Where'd that conclusion come from? Surely "does this pattern exist anywhere in this string?" with the answer "no" can't be that that unusual...I'm pretty sure I do this fairly often, in fact.

EDIT: just realized I probably misinterpreted. Looking at the context more, I suppose they're referring to the frequency of matches, not their presence or absence. However, is 'grep -v commonpattern' (another not-too-unusual use-case) kind of equivalent?

There's a NFA implementation called iNFAnt, which explores multiple paths through the NFA simultaneously, avoiding backtracking normally required in NFAs.