CUDA Grep
cs.cmu.edu
cs.cmu.edu
Also, they didn't ignore the key detail, they mention it: "This is without taking into account the overhead of transferring data to the GPU."
Fair point, it's more support for this HN post[2] making the case for memory-mapping files to GPU.
> This is a neat project, but there is a reason we are not using the GPU for regex matching.
I think it's more interesting that it's a general facility for running automata on a GPU, as it's opening up the universe of things that can be accelerated by a GPU. For instance, Numba[1] is a library to run arbitrary math code, and it has a feature for generating code to run on the GPU.
[1]: http://numba.pydata.org/numba-doc/latest/cuda/index.html
Yes you are right, you should not replace grep for one off regexes due to the latency of the io operations. As far as I recall, memory throughput however is much higher on house than on CPUs (or at least this was true in 2012). Our intended use cases for this sort of a grep were cases where you are finding many needles in enormous haystacks such as: Looking for malicious machine code in executables that you download off of the internet (virus scanning), or searching for certain genetic sequences in DNA code. I believe we discussed this in our final presentation, but perhaps we left it out of the written report.
Yes we probably should have included the numbers to show why you wouldn't want to use this instead of grep for simple tasks. I am sorry we missed it.
(Also, you'd want BLAST for DNA instead of grep, but perhaps this was an intentional simplification)
My last K-mer counter I wrote was CPU/Memory bound (big enough size strings means big hash tables to store this stuff in, or using something like a bloom filter (Jellyfish's approach), not IO bound.
Anyway, for anyone who wants to write something fun, fasta parsers / k-mer counters are a good weekend project.
here was my work in the area (shameless plug, though i'm not in the field anymore)
https://github.com/mutantturkey/dna-utils.
just tested again against a 400mbish genome fasta file from ncbi and it's still clearly an cpu/memory issue with huge hash tables. See below (4^x is the potential combinations of K-mers). K=9 is done with a 4^9 array (sane in memory), 4^12 is a sparse array (stored as a a std::unordered_map, because it's too large to allocate that much space in memory). One is obviously way slower
calvin@bison:~/src/dna-utils$ time ./kmer_total_count -k 9 -i 3816_ref_Abrus_2018_chrUn.fa.2 >/dev/null
real 0m4.235s
user 0m4.116s
sys 0m0.108s
calvin@bison:~/src/dna-utils$ time ./kmer_total_count -k 12 -i 3816_ref_Abrus_2018_chrUn.fa.2 >/dev/null
real 0m25.524s
user 0m25.292s
sys 0m0.152s
calvin@bison:~/src/dna-utils
If we are using something more 'grep'-like, it's for large quantities of data, and in many cases we could treat these as a stream. So as long as the bandwidth to the GPU is sufficient, a little stall at the beginning would represent an undue hardship, if the results come back faster.
https://www.microsoft.com/en-us/microsoft-365/windows/micros...
[0] https://www.dfrws.org/sites/default/files/session-files/pres...
Also, IO bound? Again, no. My consumer MBP can read at 3.2GB/s. Good luck doing regex on that in real time on a CPU. This is a CPU bound operation for a typical high end configuration.
Does this make sense for a 1MB file? probably not. But anything well beyond that it will be way faster.
Here's a great talk about how you should think about GPU performance: https://www.nvidia.com/content/GTC-2010/pdfs/2238_GTC2010.pd...
To give some context: PCIe 3.0 x16 achieves about 11-12 GB/s. So, transfers for benchmarked 53MB file would add ~4.8 ms (per direction, assuming pinned host memory)
Now, they could also pursue a streaming approach, processing in "micro-batches". I.e., pipelining input transfers (HOST->GPU), GPU-based processing, and transfer of results (GPU->HOST), as pursued by [1] (disclaimer: I'm a co-author). This lower's processing latency. Since the interconnect is full-duplex, it would just limit the processing rate to about ~11 GB/s (i.e., 5 ms for mentioned 53MB). To be fair, though, input has to be sufficiently large, such that there are (a) enough micro-batches to overlap transfer and compute and (b) the micro-batches can be chosen to be still large enough to exploit full parallelism of the GPU.
I remember another story where someone claimed to be faster than grep. Turned out the comparison was unfair because if this distinction. I believe LANG=C is enough to turn grep into ASCII mode.
[0] https://github.com/BurntSushi/ripgrep [1] https://github.com/ggreer/the_silver_searcher
Even though it's now an Intel project targeting CPUs, it grew out of a startup trying run regex matching on parallel hardware.
The first commit to ag - README.md - was in Nov. 2011; https://github.com/ggreer/the_silver_searcher/commit/0121e6b... . The earliest versioned commit tag was 0.3 in March 2012 - https://github.com/ggreer/the_silver_searcher/tree/0.3 . I think that lack of comparison is okay.
The first commit to ripgrip was in 2016. https://github.com/BurntSushi/ripgrep/commit/9d1e619ff359b6e...
Said another way: a state machine. True regular languages can be defined by a simple state machine, which is relatively much faster than the extended regular-like language that perl exposes.
Fun trivia: DFAs and NFAs are computationally equivalent. Any NFA can be converted into an equivalent DFA.
https://en.wikipedia.org/wiki/Deterministic_finite_automaton
If you can convert a nondeterministic automata to a deterministic one, doesn't that mean they are all deterministic?
It's a representation for state machines in which state transitions are apparently ambiguous: a given state in the NFA can, for exactly the same input, go into multiple other states. This is a very convenient representation for pattern matching.
The way the ambiguity resolves itself is not through randomness, but by the understanding that the machine is in all of the possible states at the same time. Then, in a concrete implementation in a programming language, we represent that situation by using a set of states as the run-time state.
E.g. when the input symbol b is received, some NFA machine goes from state { 0, 3, 5 } to { 1, 3, 7, 8 }; i.e. it is in NFA states 0, 3 and 5, which transition to 1, 3, 7, 8 when b is seen.
NFA graphs can be executed directly by an NFA simulator which calculates these transitions on the fly.
We can also statically figure out all the state sets there can be and their transitions.Then we re-label these sets as the simple states of a deterministic automaton. E.g. { 0, 3, 5 } is dubbed S0, { 1, 3, 7, 8} is dubbed S1. There is a transition from S0 to S1 on b. We can work through all the possible transitions, ferret out all the subsets and their transitions to build a simple machine. That is the "subset construction".
> ...not as powerful as regex libs built with a non-regular language...
Is there something that perl regex's can do, in non-crazy everyday use-cases, that can't be done by something like re2?
I don't think it's proven that they can't be added on to an automata based regular expression engine. Nobody has figured it out yet though.
The various features in PERL allow you to emulate context-free languages. There is a proof somewhere, but it's trivial to see you can use backreferences to parse languages with well-nested parens.
Languages of well-nested parens are known to be non-regular, and thus impossible to write with regular expressions.
Also note that knowing if an arbitrary context-free language is regular is undecidable. That doesn't mean you can't try to optimize down some PERL grammar to a regex, but your optimization will never be complete.
Are you reffering to the programming language or PCRE? I would expect PCRE to be a simple superset of the regex grammar, and thus the optimization is complete and trivial: the appearance of any PCRE constructs denies the use of the DFA engine; otherwise, use the DFA.
I don’t see how you could ever optimize out eg a backreference (converting to some equivalent regex) without already having parsed the subject text and determining it to be unnecessary. In which case, I don’t see how the inability to determine regularity of a context-free grammar is relevant (if you’re referring to the context-free nature of PCRE’s grammar, its not clear to me why you should care where the regex input grammar itself is regular/context-free, and why you’d want to convert PCRE to a regular grammar; optimizing a regex search shouldn’t care about the grammar defining the search)
That includes basic things like capture groups. That doesn't mean you can't use automata in a regex-plus implementation, though.
I can't find the paper, but I think there is a hybrid engine that tries to get the best of both worlds; constant space where possible and using additional space to provide more features.
You might have meant to say that you can't use backreferences.
Nothing is stopping you from enhancing opencl as a language, building useful libraries, writing documentation, holding conferences to build an ecosystem around opencl, and evangelizing the technology, just like nvidia did for cuda.
All the popular frameworks run on CUDA, and from what I hear openCL sucks to use.
If they had used opencl they may have been using an immature product, that might really have been apple only at the time (or apple and IBM?). I don't know thie history but 8-9 years ago (when the research work may have started) nvidia was tpushing the cuda idea (almost entirely alone - AMD still playing catchup).