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

41–50 of 77 posts

Re: The One Billion Row Challenge in CUDA

#41

Post by candido_heavyai »

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

I am testing a gh200 and the speed you can access the system memory is amazing.. Assuming you have already encoded the station into a smallint and the size of the dataset would be around 6gb that on such system takes just 20 ms to be transfered (I am sure about that because I'm observing transfer a 9.5gb that took about 33ms right now).

Re: The One Billion Row Challenge in CUDA

#42

Post by jbochi »

petermcneeley wrote: post #38
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 :)

qq: Would this be in CUDA?

Not sure what I can share publicly, but we use TPUs as well: https://cloud.google.com/blog/products/compute/announcing-cl...

Re: The One Billion Row Challenge in CUDA

#43

Post by konstantinua00 »

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

1 billion rows is "small dataset"?

Re: The One Billion Row Challenge in CUDA

#44

Post by [deleted] »

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…

[deleted]

Re: The One Billion Row Challenge in CUDA

#45

Post by ww520 »

petermcneeley wrote: post #37
ww520 wrote: post #36

Earlier quoted context omitted.

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.

The key can be up to 100 bytes. The key in the hashmap is in cache. The key being compared is from main memory. Basically the whole file in memory is being gone through and compared. With 1 billion rows it’s about 16GB data in memory for a 16-byte average row. That’s approaching the memory bandwidth limit for a second, making it a memory bound problem.

Re: The One Billion Row Challenge in CUDA

#46

Post by fulafel »

candido_heavyai wrote: post #40

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 negl…

The 1brc benchmark has the data in a RAM disk[0], there's no disk IO.

[0] https://github.com/gunnarmorling/1brc#evaluating-results

Re: The One Billion Row Challenge in CUDA

#47

Post by fpgamlirfanboy »

jbochi wrote: post #42
petermcneeley wrote: post #38

Earlier quoted context omitted.

qq: Would this be in CUDA?

Not sure what I can share publicly, but we use TPUs as well: https://cloud.google.com/blog/products/compute/announcing-cl...

It's funny - former Google devs (whom I just maintain a good relationship with their former employer) are ideally positioned to profitably take advantage of the arb of TPU over GPU.

Re: The One Billion Row Challenge in CUDA

#48

Post by bee_rider »

fpgamlirfanboy wrote: post #47
jbochi wrote: post #42

Earlier quoted context omitted.

Not sure what I can share publicly, but we use TPUs as well: https://cloud.google.com/blog/products/compute/announcing-cl...

It's funny - former Google devs (whom I just maintain a good relationship with their former employer) are ideally positioned to profitably take advantage of the arb of TPU over GPU.

Google should improve their abstractions until there isn’t room for that anymore, haha.

Re: The One Billion Row Challenge in CUDA

#49

Post by _zoltan_ »

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"?

eh, it's just two columns. 12 or 13GB IIRC.

Re: The One Billion Row Challenge in CUDA

#50

Post by emcq »

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 3GB/s range, perhaps there is another second or so of optimization left there (which would roughly work out to the 1.4s in-memory time).

Because you have a lot of variable width row reads this will be more difficult on a GPU than CPU.

[1] https://www.dannyvankooten.com/blog/2024/1brc/

Post reply on HN