9 ms·

They ignored a key detail in their benchmark. They did not include the time it took to transfer the input file from memory to the GPU, (the GPU cores can only o

by sjf 7y ago

They ignored a key detail in their benchmark. They did not include the time it took to transfer the input file from memory to the GPU, (the GPU cores can only operate on graphics memory). This is easily going to be the most time consuming part. They also didn't include any IO operations in their timing, so instead of a 10x speedup, it is more likely to be a couple of percent faster as grep is going to be IO bound. This is a neat project, but there is a reason we are not using the GPU for regex matching.

cma 7y ago
Some GPUs have integrated memory with the CPU and don't need to do the transfer, it could still speed things up there couldn't it? 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."
- alfalfasprout 7y ago
  Yeah, but integrated GPUs wouldn't be usable with CUDA.
  - cma 7y ago
    Nvidia makes several with integrated memory. Nintendo Switch is based on one etc.
  - Athas 7y ago
    I have not been able to inspect the code (dead links), but from the description of their approach, they do not depend on anything particularly fancy from CUDA. An OpenCL implementation seems just as feasible.
  - 2a96eb7d685a49c 7y ago
    Do Nvidia Tegra SOCs work in that way?
  - justinmeiners 7y ago
    Perhaps on PCs, but plenty of mobile and consoles use a shared memory architecture.
  - shaklee3 7y ago
    The tegra products are all integrated.
- bkase 7y ago
  Oh good, I'm glad we did mention this!
ben509 7y ago
> They did not include the time it took to transfer the input file from memory 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 http://numba.pydata.org/numba-doc/latest/cuda/index.html [2]: https://news.ycombinator.com/item?id=11892030 https://news.ycombinator.com/item?id=11892030
- shaklee3 7y ago
  CUDA already has this built in (for many years) using UVM. That won't take away the bottleneck of the transfer, but it does make it transparent to the user by handling all the paging/copies.
  - mzs 7y ago
    I thought that just made GPU memory map equal to CPUs' and you need much for VM (like paging).
bkase 7y ago
One of the authors here: 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.
- jldugger 7y ago
  But getting any of that data off disk will typically be the bottleneck. (Also, you'd want BLAST for DNA instead of grep, but perhaps this was an intentional simplification)
  - calvinmorrison 7y ago
    well if you're looking for certain motifs or k-mers (https://en.wikipedia.org/wiki/K-mer https://en.wikipedia.org/wiki/K-mer), it's mostly scanning through pre-processed FASTA files. 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 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
lmeyerov 7y ago
Or you can flip your assumptions and run 10X faster... everywhere. It was a tough investment, but we went GPU-first via Apache Arrow & Nvidia RAPIDS. (In this case, I'd look at RAPIDS / NVStrings before this.)
randyrand 7y ago
Totally disagree. Moving memory to the GPU can be parallelized while doing the computation. For larger files that can fully saturate the gpu's bandwidth, it's completely negligible. "Easily the most time consuming part", no. Not even close. 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.pdf https://www.nvidia.com/content/GTC-2010/pdfs/2238_GTC2010.pd...
ejbs 7y ago
> They did not include the time it took to transfer the input file from memory to the GPU 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. [1] https://arxiv.org/pdf/1905.13415.pdf https://arxiv.org/pdf/1905.13415.pdf

by sjf 7y ago

cma 7y ago

Some GPUs have integrated memory with the CPU and don't need to do the transfer, it could still speed things up there couldn't it? 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."

alfalfasprout 7y ago
Yeah, but integrated GPUs wouldn't be usable with CUDA.
- cma 7y ago
  Nvidia makes several with integrated memory. Nintendo Switch is based on one etc.
- Athas 7y ago
  I have not been able to inspect the code (dead links), but from the description of their approach, they do not depend on anything particularly fancy from CUDA. An OpenCL implementation seems just as feasible.
- 2a96eb7d685a49c 7y ago
  Do Nvidia Tegra SOCs work in that way?
- justinmeiners 7y ago
  Perhaps on PCs, but plenty of mobile and consoles use a shared memory architecture.
- shaklee3 7y ago
  The tegra products are all integrated.
bkase 7y ago
Oh good, I'm glad we did mention this!

ben509 7y ago

> They did not include the time it took to transfer the input file from memory 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 http://numba.pydata.org/numba-doc/latest/cuda/index.html [2]: https://news.ycombinator.com/item?id=11892030 https://news.ycombinator.com/item?id=11892030

shaklee3 7y ago
CUDA already has this built in (for many years) using UVM. That won't take away the bottleneck of the transfer, but it does make it transparent to the user by handling all the paging/copies.
- mzs 7y ago
  I thought that just made GPU memory map equal to CPUs' and you need much for VM (like paging).

bkase 7y ago

One of the authors here: 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.

jldugger 7y ago
But getting any of that data off disk will typically be the bottleneck. (Also, you'd want BLAST for DNA instead of grep, but perhaps this was an intentional simplification)
- calvinmorrison 7y ago
  well if you're looking for certain motifs or k-mers (https://en.wikipedia.org/wiki/K-mer https://en.wikipedia.org/wiki/K-mer), it's mostly scanning through pre-processed FASTA files. 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 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

lmeyerov 7y ago

Or you can flip your assumptions and run 10X faster... everywhere. It was a tough investment, but we went GPU-first via Apache Arrow & Nvidia RAPIDS. (In this case, I'd look at RAPIDS / NVStrings before this.)

randyrand 7y ago

Totally disagree. Moving memory to the GPU can be parallelized while doing the computation. For larger files that can fully saturate the gpu's bandwidth, it's completely negligible. "Easily the most time consuming part", no. Not even close. 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.pdf https://www.nvidia.com/content/GTC-2010/pdfs/2238_GTC2010.pd...

ejbs 7y ago

> They did not include the time it took to transfer the input file from memory to the GPU 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. [1] https://arxiv.org/pdf/1905.13415.pdf https://arxiv.org/pdf/1905.13415.pdf