The One Billion Row Challenge in CUDA
tspeterkim.github.io
The One Billion Row Challenge in CUDA
1–10 of 77 posts
Re: The One Billion Row Challenge in CUDA
#2> GPU Hash Table?
How bad would performance have suffered if you sha256'd the lines to build the map? I'm going to guess "badly"?
Maybe something like this in CUDA: https://github.com/Cyan4973/xxHash ?
Re: The One Billion Row Challenge in CUDA
#3Interesting approach.
I wonder if one could use a reduce operation across the cities or similar rather than atomic operations? GPUs are amazing at reduce operations.
Re: The One Billion Row Challenge in CUDA
#4The Programming Massively Parallel Processors textbook has a chapter on histograms. You have basically mentioned the main trick though (privatization).
For this problem I think coursening would also help (so everything isn’t queued up on the copy to global memory)
Re: The One Billion Row Challenge in CUDA
#5> These offsets are obtained iteratively, stepping through the entire file buffer by the desired split size (= total file size / desired number of parts), and marking the position of a new line character:
In many cases it is better to just pass the raw byte offsets to the workers, then they can skip to the first newline and progress until the next newline after their "end offset". This way the launcher doesn't need to access the input data at all.
This can be ineffective when boundaries are not self-describing or when the minimum processable chunk is near the expected batch size (as you will have significant swings in batch size) but I think would work quite well for this case.
Re: The One Billion Row Challenge in CUDA
#6Interesting approach. I wonder if one could use a reduce operation across the cities or similar rather than atomic operations? GPUs are amazing at reduce operations.
Agreed. I tried reducing across cities first.
The problem was that the work of gathering all the temperatures for each city (before I could launch the reduction CUDA kernels) required a full parsing through the input data.
My final solution would be slower than the C++ baseline since the baseline already does the full parsing anyways.
Re: The One Billion Row Challenge in CUDA
#7> GPU Hash Table? How bad would performance have suffered if you sha256'd the lines to build the map? I'm going to guess "badly"? Maybe something like this in CUDA: https://github.com/Cyan4973/xxHash ?
So performance would increase since hashing is faster than binary-searching.
However, the problem of collisions across threads and dealing with concurrent map key insertions still remains. e.g. when two different cities produce the same hash (one at each thread), how can we atomically compare 100 byte city strings and correctly do collision-solving (using linear probe, for example - https://nosferalatu.com/SimpleGPUHashTable.html)
Atomic operations are limited to 32-bits.
Re: The One Billion Row Challenge in CUDA
#8The Programming Massively Parallel Processors textbook has a chapter on histograms. You have basically mentioned the main trick though (privatization). For this problem I think coursening would also help (so everything isn’t queued up on the copy to global memory)
The PMPP book is great. I reread the histogram chapter after finishing the blog, and realized I could use privatization. You got me!
By coarsening, do you mean making the threads handle more file parts, and reducing the number of private copies (of histogram or stats here) to globally commit at the end?
Re: The One Billion Row Challenge in CUDA
#9> These offsets are obtained iteratively, stepping through the entire file buffer by the desired split size (= total file size / desired number of parts), and marking the position of a new line character: In many cases it is better to just pass the raw byte offsets to the workers, then they can skip to the first newline and progress until the next newline after their "end offset". This way the launcher doesn't need t…
By "launcher", do you mean the CUDA kernel? How can it avoid accessing the input data since it needs access to the characters based on the offsets?
I also already pass these offsets to the threads as `Part* parts`.
I also probably didn't understand your suggestion and am drawing a blank here. So pls feel free to elaborate and correct me.
Re: The One Billion Row Challenge in CUDA
#10am I reading correctly that your AtomicMin stops only when CAS succeeds?
can you not stop early if extracted value becomes smaller than val?