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

21–30 of 77 posts

Re: The One Billion Row Challenge in CUDA

#21

Post by mandarax8 »

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…

> Atomic operations are limited to 32-bits.

I'm using 64bit atomics at work, are you on an old version of cuda or are some operations only supported on 32bit?

Re: The One Billion Row Challenge in CUDA

#22

Post by jodleif »

taspeotis wrote: post #20
formerly_proven wrote: post #11

Well that's a very pessimistic C++ baseline - using iostreams. The CUDA solution presented here seems to me like it's a bit of an old-timey approach, treating the GPU as an accelerator. The implementation first prepares a million tasks, then submits them as kernel invocations which perform the work. The first phase already takes over two seconds, the second phase takes over ten seconds. Resulting runtime is 16s, 60x…

Yeah has terrible performance, and also I find the use of a map rather than an unordered_map a bit suspect.

Its much easier to improve is the baseline is terrible

Re: The One Billion Row Challenge in CUDA

#23

Post by _zoltan_ »

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…

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 :-)

Re: The One Billion Row Challenge in CUDA

#24

Post by tspeterkim »

tromp wrote: post #14
tspeterkim wrote: post #9

Earlier quoted context omitted.

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.

He's proposing to skip the whole computation of the parts[] array and within the kernel, replace for (int i = 0; i by something like long long split_size = size / num_parts; long long offset = bx * split_size; while (buffer[offset++] != '\n') ; for (int i = 0; buffer[offset+i] != '\n'; i++) { char c = buffer[offset + i]; (ignoring how to deal with buffer_offset for now).

  for (int i = 0; buffer[offset+i] != '\n'; i++) {
This would only process the current line, though. Here, each thread processes ~split_size bytes (multiple lines).

Even if were to read multiple lines, how would a thread know when to stop? (at which offset?)

And when it does, it should communicate where it stopped with the other threads to prevent re-reading the buffer. My brain's hurting now.

Re: The One Billion Row Challenge in CUDA

#25

Post by tspeterkim »

mandarax8 wrote: post #21
tspeterkim wrote: post #7

Earlier quoted context omitted.

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…

> Atomic operations are limited to 32-bits. I'm using 64bit atomics at work, are you on an old version of cuda or are some operations only supported on 32bit?

I misspoke. (got confused with the key limit in my link above)

Atomics work up to 128-bits (https://docs.nvidia.com/cuda/cuda-c-programming-guide/#atomi...).

Regardless, it's still less than 100 bytes, which is the max length of city strings.

Re: The One Billion Row Challenge in CUDA

#26

Post by tspeterkim »

muep wrote: post #13

Instead of desiring atomic maps, would it work here to give each task its own map and then merge those after the parallel processing has ended? I have have absolutely no experience of CUDA, so no idea how applicable that approach would be. However, it seemed pretty practical and effective when I tried a parallel implementation of this challenge on plain CPUs.

This is the possible optimization that I mention at the end of the blog - using a private map for each thread block.

The catch is that this map must fit in shared memory, which is pretty limited on all current hardware: ~100KB.

I originally thought that my map (stats array) was too big to fit into this shared memory. Now, however, I realize it can. It'll interesting to see how much speedup (or not!) this optimization can bring.

Re: The One Billion Row Challenge in CUDA

#27

Post by tspeterkim »

_zoltan_ wrote: post #16

I think this is very slow for some reason. I'll bookmark this and try on an A100 and a H100 box and then will try with multigpu on larger data.

Please do.

My hope with this blog was to rile up other CUDA enthusiasts. Making them wanna bring in bigger and better hardware that I don't have access to.

+ Someone in the CUDA MODE community got 6 seconds on a 4090.

Re: The One Billion Row Challenge in CUDA

#28

Post by 15155 »

_zoltan_ wrote: post #23
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…

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.

Re: The One Billion Row Challenge in CUDA

#29

Post by tromp »

tspeterkim wrote: post #24
tromp wrote: post #14

Earlier quoted context omitted.

He's proposing to skip the whole computation of the parts[] array and within the kernel, replace for (int i = 0; i by something like long long split_size = size / num_parts; long long offset = bx * split_size; while (buffer[offset++] != '\n') ; for (int i = 0; buffer[offset+i] != '\n'; i++) { char c = buffer[offset + i]; (ignoring how to deal with buffer_offset for now).

for (int i = 0; buffer[offset+i] != '\n'; i++) { This would only process the current line, though. Here, each thread processes ~split_size bytes (multiple lines). Even if were to read multiple lines, how would a thread know when to stop? (at which offset?) And when it does, it should communicate where it stopped with the other threads to prevent re-reading the buffer. My brain's hurting now.

It can compute both the starting offset for itself and next_offset for (bx+1)...

Re: The One Billion Row Challenge in CUDA

#30

Post by kevincox »

tspeterkim wrote: post #24
tromp wrote: post #14

Earlier quoted context omitted.

He's proposing to skip the whole computation of the parts[] array and within the kernel, replace for (int i = 0; i by something like long long split_size = size / num_parts; long long offset = bx * split_size; while (buffer[offset++] != '\n') ; for (int i = 0; buffer[offset+i] != '\n'; i++) { char c = buffer[offset + i]; (ignoring how to deal with buffer_offset for now).

for (int i = 0; buffer[offset+i] != '\n'; i++) { This would only process the current line, though. Here, each thread processes ~split_size bytes (multiple lines). Even if were to read multiple lines, how would a thread know when to stop? (at which offset?) And when it does, it should communicate where it stopped with the other threads to prevent re-reading the buffer. My brain's hurting now.

Yeah, this is a bug in their quick example code. Basically think that you simply give each thread a start and stop offset with simple byte division. Then each thread handles the first line that starts after the start offset up to but excluding the first line that starts after its end offset. So there will be a small amount of "overread" at the boundaries but this is probably negligible.

    let chunk_size = buf.length / threads;
    let start_byte = chunk_size * bx;
    let end_byte = start_byte + chunk_size;
    
    let i = start_byte;
    while (buffer[i++] != '\n') {} // Skip until the first new row.

    while (i
Basically you first roughly split the data with simple byte division. Then each thread aligns itself to the underling data chunks. This alignment can be done in parallel across all threads rather than being part of a serial step that examines every byte before the parallel work starts. You need to take care that the alignment each thread does doesn't skip or duplicate any rows, but for simple data formats like this I don't think that should be a major difficulty.
Post reply on HN