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

11–20 of 77 posts

Re: The One Billion Row Challenge in CUDA

#11

Post by formerly_proven »

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 faster than iostreams.

This is similar to how GPU acceleration is bolted on in a ton of commercial software, you look at hotspots and then move just those over to the accelerator. For example outsourcing some linear algebra in a FEM solver. That's a sensible approach for trying to accelerate legacy software, but it's not very effective and leads to poor utilization ("copy mat, copy mat, copy mat copy copy copy mat" - Dave Cutler about GPU acceleration). I think a) you can do all of this on the GPU b) this should be limited by PCIe bandwidth for getting the file contents into VRAM. The 1BRC data set is 14 GB. So this is processing that file at about 1 GB/s using both CPU and GPU.

Re: The One Billion Row Challenge in CUDA

#12

Post by konstantinua00 »

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

Re: The One Billion Row Challenge in CUDA

#13

Post by muep »

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.

Re: The One Billion Row Challenge in CUDA

#14

Post by tromp »

tspeterkim wrote: post #9
kevincox wrote: post #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 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.

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

Re: The One Billion Row Challenge in CUDA

#15

Post by speps »

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.

Looks like TFA already uses partitioning per thread.

Re: The One Billion Row Challenge in CUDA

#17

Post by pama »

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 of data to the GPU would likely add a noticeable bottleneck and make the optimal CUDA code slower than this pure C code.

Re: The One Billion Row Challenge in CUDA

#18

Post by SJC_Hacker »

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.

You can definitely have thread local storage

Re: The One Billion Row Challenge in CUDA

#19

Post by convivialdingo »

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…

You could hash the city names using something like a djb2a algorithm?

Re: The One Billion Row Challenge in CUDA

#20

Post by taspeotis »

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.
Post reply on HN