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

61–70 of 77 posts

Re: The One Billion Row Challenge in CUDA

#61

Post by gunnarmorling »

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…

This actually doesn't fit the rules. I've designed the challenge so that disk I/O is not part of the measured runtime (initially, by relying on the fact that the first run which would pull the file into the page cache will be the slowest and thus discarded, later on by loading the file from a RAM disk). But keeping state between runs is explicitly ruled out as per the README, for the reason you describe.

Re: The One Billion Row Challenge in CUDA

#62

Post by petermcneeley »

ww520 wrote: post #45
petermcneeley wrote: post #37

Earlier quoted context omitted.

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.

This really depends on number of unique keys. If they sit in L1-L2: the bandwidth of these caches is an order of magnitude greater than main memory.

This problem is quite a Nerd Snipe so it a good thing that I dont have a computer with more than 16 GB or I might end up trying it myself.

Re: The One Billion Row Challenge in CUDA

#63

Post by ww520 »

pama wrote: post #57
ww520 wrote: post #54

Earlier quoted context omitted.

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

Good to know. I didn’t know the contest has no limit on hyperthread.

Re: The One Billion Row Challenge in CUDA

#64

Post by nwallin »

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

> on large datasets, once loaded into GPU memory,

You're yada-yada-yadaing the best part.

If the disk can process the data at 1GB/s, the CPU can process the data at 2GB/s, the GPU can process the data at 32GB/s, then the CPU can process the data at 1GB/s and the GPU can process the data at 1GB/s.

(also, personally, "large dataset" is a short way to say "doesn't fit in memory". if it fits in memory it's small, if it doesn't fit in memory it's large. but that's just my opinion. I generally avoid calling something a "large" or "small" dataset because it's an overloaded term that means different things to different people.)

Re: The One Billion Row Challenge in CUDA

#66

Post by dkersten »

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.

Standard library maps/unordered_maps are themselves notoriously slow anyway. A flat_hash_map from abseil or parallel-hashmaps[1] would be better.

[1] https://github.com/greg7mdp/parallel-hashmap

Re: The One Billion Row Challenge in CUDA

#67

Post by fulafel »

ww520 wrote: post #63
pama wrote: post #57

Earlier quoted context omitted.

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

Good to know. I didn’t know the contest has no limit on hyperthread.

1brc in the contest had SMT disabled [0]. (hyperthreading is an intel marketing name and trademark for their implementation of smt, but the benchmark was run on an amd cpu)

[0] https://github.com/gunnarmorling/1brc/issues/189#issuecommen...

Re: The One Billion Row Challenge in CUDA

#68

Post by pama »

pama wrote: post #51
_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 :-)

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

This would be the code to beat. Ideally with only 8 cores but any number of cores is also very interesting.

https://github.com/gunnarmorling/1brc/discussions/710

Re: The One Billion Row Challenge in CUDA

#69

Post by tspeterkim »

kevincox wrote: post #30
tspeterkim wrote: post #24

Earlier quoted context omitted.

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

I tried this out today. While it works (no longer a pre-split step required), it makes the CUDA kernel run ridiculously slow. I believe it's because of the while loop:

  while (i
Comparing it to my original solution, 50X divergent branches are introduced! (ncu profiling)

The only difference between the two is that the for loop could deterministically iterate, yet this while loop iterates for an unknown amount (at kernel launch time).

I admit, I don't perfectly understand the reason. But this is the most likely culprit.

Re: The One Billion Row Challenge in CUDA

#70

Post by _zoltan_ »

pama wrote: post #51
_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 :-)

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

so you'd rather nerd snipe others, gotcha ;) :D
Post reply on HN