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

51–60 of 77 posts

Re: The One Billion Row Challenge in CUDA

#51

Post by pama »

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

Yes, GDS will accelerate the IO to the GPU. I’d love to see the above C code compared to hyperoptimized GPU code on the right hardware, but I don’t want to accidentally nerd snipe myself :-) The unfortunate part of this particular benchmark is that once you have the data in the right place in your hardware there is very little compute left. The GPU code would probably have constant performance with an additional couple thousand operations on each row whereas CPU would slow down.

https://docs.nvidia.com/gpudirect-storage/overview-guide/ind...

Re: The One Billion Row Challenge in CUDA

#52

Post by trashtensor »

jbochi wrote: post #35

Pretty cool. Shameless plug: My team at Anthropic is hiring people that can write accelerator kernels. Please reach out to @gmail.com if you want to make state of the art models faster :)

not looking for a job at this time but i do this kind of work - what is the name of the team that you are working on / typically works on this?

Re: The One Billion Row Challenge in CUDA

#53

Post by PeterisP »

konstantinua00 wrote: post #43
_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 :-)

1 billion rows is "small dataset"?

The meaningful boundary between small data and large data is the difference whether the whole dataset/processing is expected to fit in the RAM of a single common machine. From that perspective, 1 billion rows a borderline case, which can be small or large depending on how large the rows are - and in this particular challenge the rows are tiny.

Re: The One Billion Row Challenge in CUDA

#54

Post by ww520 »

emcq wrote: post #50
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…

The 1.4s is _after_ having the file loaded into RAM by the kernel. Because this is mostly I/O bound, it's not a fair comparison to skip the read time. If you were running on a M3 mac you'd might get less than 100ms if the dataset was stored in RAM. If you account for time loading from disk, the C implementation would be more like ~5s as reported in the blog post [1]. Speculating that their laptop's SSD may be in the…

Also this uses 16 threads while the contest restricts to running in 8 cores. Needs to compare the benchmarks in the same environment to make a fair comparison.

Re: The One Billion Row Challenge in CUDA

#55

Post by belter »

konstantinua00 wrote: post #43
_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 :-)

1 billion rows is "small dataset"?

Just the click stream data of four 15 year old's, chilling out on the living room while watching TikTok videos....

Re: The One Billion Row Challenge in CUDA

#56

Post by pama »

emcq wrote: post #50
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…

The 1.4s is _after_ having the file loaded into RAM by the kernel. Because this is mostly I/O bound, it's not a fair comparison to skip the read time. If you were running on a M3 mac you'd might get less than 100ms if the dataset was stored in RAM. If you account for time loading from disk, the C implementation would be more like ~5s as reported in the blog post [1]. Speculating that their laptop's SSD may be in the…

The performance report followed the initial request: run 6 times and remove the best and worst outliers, so the mmap optimization is fair game. Agreed that the C code has room left for some additional optimization.

Re: The One Billion Row Challenge in CUDA

#57

Post by pama »

ww520 wrote: post #54
emcq wrote: post #50

Earlier quoted context omitted.

The 1.4s is _after_ having the file loaded into RAM by the kernel. Because this is mostly I/O bound, it's not a fair comparison to skip the read time. If you were running on a M3 mac you'd might get less than 100ms if the dataset was stored in RAM. If you account for time loading from disk, the C implementation would be more like ~5s as reported in the blog post [1]. Speculating that their laptop's SSD may be in the…

Also this uses 16 threads while the contest restricts to running in 8 cores. Needs to compare the benchmarks in the same environment to make a fair comparison.

The AMD Ryzen 4800U has 8 cores total so the author follows the contest restriction. This CPU supports hyperthreading. (I’d be very interested in seeing hyperoptimized CUDA code using unlimited GPU cores FWIW.)

Re: The One Billion Row Challenge in CUDA

#58

Post by emcq »

pama wrote: post #56
emcq wrote: post #50

Earlier quoted context omitted.

The 1.4s is _after_ having the file loaded into RAM by the kernel. Because this is mostly I/O bound, it's not a fair comparison to skip the read time. If you were running on a M3 mac you'd might get less than 100ms if the dataset was stored in RAM. If you account for time loading from disk, the C implementation would be more like ~5s as reported in the blog post [1]. Speculating that their laptop's SSD may be in the…

The performance report followed the initial request: run 6 times and remove the best and worst outliers, so the mmap optimization is fair game. Agreed that the C code has room left for some additional optimization.

If we are going to consider using prior runs of the program having the file loaded in RAM by the kernel fair, why stop there?

Let's say I create a "cache" where I store the min/mean/max output for each city, mmap it, and read it at least once to make sure it is in RAM. If the cache is available I simply write it to standard out. I use whatever method to compute the first run, and I persist it to disk and then mmap it. The first run could take 20 hours and gets discarded.

By technicality it might fit the rules of the original request but it isn't an interesting solution. Feel free to submit it :)

Re: The One Billion Row Challenge in CUDA

#59

Post by pama »

emcq wrote: post #58
pama wrote: post #56

Earlier quoted context omitted.

The performance report followed the initial request: run 6 times and remove the best and worst outliers, so the mmap optimization is fair game. Agreed that the C code has room left for some additional optimization.

If we are going to consider using prior runs of the program having the file loaded in RAM by the kernel fair, why stop there? Let's say I create a "cache" where I store the min/mean/max output for each city, mmap it, and read it at least once to make sure it is in RAM. If the cache is available I simply write it to standard out. I use whatever method to compute the first run, and I persist it to disk and then mmap it…

Having write access to storage or spawning persistent daemons is an extra requirement and that is often not available in practice when evaluating contest code :-)

This is a fun project for learning CUDA and I enjoyed reading about it——I just wanted to point out that the performance tuning in this case is really on the parsing, hashing, memory transfers, and IO. Taking IO out of the picture using specialized hardware or Linux kernel caching still leaves an interesting problem to solve and the focus should be on minimizing the memory transfers, parsing, and hashing.

Post reply on HN