Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

The One Billion Row Challenge in CUDA

tspeterkim.github.io

Post reply on HN
Print view View original

31–40 of 77 posts

Re: The One Billion Row Challenge in CUDA

#31

Post by Sesse__ »

tspeterkim wrote: post #7
MuffinFlavored wrote: post #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 ?

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/SimpleGPUH…

If the set of cities is known (as your binary search algorithm assumes), you can insert all of them first, on the CPU. That will resolve all collisions ahead of time, making the structure of the hash table essentially read-only. (Of course, you would still need atomics for the values.)

Re: The One Billion Row Challenge in CUDA

#32

Post by Sesse__ »

konstantinua00 wrote: post #12
konstantinua00 wrote: post #10

am I reading correctly that your AtomicMin stops only when CAS succeeds? can you not stop early if extracted value becomes smaller than val?

also, iirc, floats' comparison is compatible with signed integers' comparison due to representation? so just using cuda's AtomicMin for ints would be enough

Positive finite floats compare like ints. If you can have negative values, things get slightly more complicated, since they use sign-magnitude (you basically shift the sign bit to the right and use that as an XOR mask on all the other bits). If you need to care about -0.0 == +0.0 and NaN != NaN, most bets are off. :-)

Re: The One Billion Row Challenge in CUDA

#33

Post by _zoltan_ »

15155 wrote: post #28
_zoltan_ wrote: post #23

Earlier quoted context omitted.

this is true for small datasets. on large datasets, once loaded into GPU memory, cross GPU shuffling with NVLink is going to be much faster than CPU to RAM. on the H100 boxes with 8x400Gbps, IO with GDS is also pretty fast. for truly IObound tasks I think a lot of GPUs beats almost anything :-)

Try an array of FPGAs.

I've never been a fan plus good luck getting 800GB/s across.

Re: The One Billion Row Challenge in CUDA

#34

Post by dan-robertson »

15155 wrote: post #28
_zoltan_ wrote: post #23

Earlier quoted context omitted.

this is true for small datasets. on large datasets, once loaded into GPU memory, cross GPU shuffling with NVLink is going to be much faster than CPU to RAM. on the H100 boxes with 8x400Gbps, IO with GDS is also pretty fast. for truly IObound tasks I think a lot of GPUs beats almost anything :-)

Try an array of FPGAs.

Why does that help with IO bandwidth?

Re: The One Billion Row Challenge in CUDA

#36

Post by ww520 »

pama wrote: post #17

There are some good ideas for this type of problem here: https://github.com/dannyvankooten/1brc After you deal with parsing and hashes, basically you are IO limited, so mmap helps. The C code takes less than 1.4s without any CUDA access. Because there is no compute to speak of, other than parsing and a hashmap, a reasonable guess is that even for the optimal CUDA implementation, the starting of kernels and transfer o…

Actually on modern systems it’s pure compute plus memory bounded. For this problem hashmap lookup is the biggest bottleneck. Parsing takes time away as well but not as bad as hashmap.

Re: The One Billion Row Challenge in CUDA

#37

Post by petermcneeley »

ww520 wrote: post #36
pama wrote: post #17

There are some good ideas for this type of problem here: https://github.com/dannyvankooten/1brc After you deal with parsing and hashes, basically you are IO limited, so mmap helps. The C code takes less than 1.4s without any CUDA access. Because there is no compute to speak of, other than parsing and a hashmap, a reasonable guess is that even for the optimal CUDA implementation, the starting of kernels and transfer o…

Actually on modern systems it’s pure compute plus memory bounded. For this problem hashmap lookup is the biggest bottleneck. Parsing takes time away as well but not as bad as hashmap.

From what I can tell the number of unique elements is pretty small. This would mean the hash map will sit in cache. Parsing is likely the bottleneck; I dont see any use of SIMD in the linked code.

Re: The One Billion Row Challenge in CUDA

#39

Post by Aznable »

The query itself it's a perfect hash (assuming the station is dictionary encoded) and takes around 100ms on a gh-200 (the Gpu is a single h100 with 132 SMs) with a query that's concurrency constrained.

The same level of performance can be obtained using an Ada like an L40s or and RTX 4090.

The transfer across the nvlink connecting the Cpu and GPU on a gh-200 after the parse and encoding of the source CSV takes a negligible amount of time given the 500 gb/sec of system memory bandwidth and the 900 GB /sec interconnection between Cpu and Gpu.

So the problem is disk bandwidth that's going to limit the performance of the Gpu kernel. The faster solution should be parse the Csv with a gpu kernel using namp and Managed memory (?) encode the station into a interger or a small integer. The min and max value can be used to create keyless perfect hash table for each SM to limit the concurrency on global memory using 32bit atomic operations for min, max, count and sum and then do a final reduction on the Gpu.

I don't think that is needed more then 1 modern gpu for this, especially if you are on a modern hardware like the gh-200.

I'm running this kind of aggregates on a gh-200 using 10 Billion of records having the data in Gpu or Cpu memory using our software (heavydb) for testing purposes in the last two weeks

Re: The One Billion Row Challenge in CUDA

#40

Post by candido_heavyai »

The query itself it's a perfect hash (assuming the station is dictionary encoded) and takes around 100ms on a gh-200 (the Gpu is a single h100 with 132 SMs) with a query that's concurrency constrained.

The same level of performance can be obtained using an Ada like an L40s or and RTX 4090.

The transfer across the nvlink connecting the Cpu and GPU on a gh-200 after the parse and encoding of the source CSV takes a negligible amount of time given the 500 gb/sec of system memory bandwidth and the 900 GB /sec interconnection between Cpu and Gpu.

So the problem is disk bandwidth that's going to limit the performance of the Gpu kernel. The faster solution should be parse the Csv with a gpu kernel using namp and Managed memory (?) encode the station into a interger or a small integer. The min and max value can be used to create keyless perfect hash table for each SM to limit the concurrency on global memory using 32bit atomic operations for min, max, count and sum and then do a final reduction on the Gpu.

I don't think that is needed more then 1 modern gpu for this, especially if you are on a modern hardware like the gh-200.

I'm running this kind of aggregates on a gh-200 using 10 Billion of records having the data in Gpu or Cpu memory using our software (heavydb) for testing purposes in the last two weeks

Post reply on HN