tspeterkim

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 < end_byte) {

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.

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.

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.

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.

  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.

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.

The PMPP book is great. I reread the histogram chapter after finishing the blog, and realized I could use privatization. You got me!

By coarsening, do you mean making the threads handle more file parts, and reducing the number of private copies (of histogram or stats here) to globally commit at the end?

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/SimpleGPUHashTable.html)

Atomic operations are limited to 32-bits.

Agreed. I tried reducing across cities first.

The problem was that the work of gathering all the temperatures for each city (before I could launch the reduction CUDA kernels) required a full parsing through the input data.

My final solution would be slower than the C++ baseline since the baseline already does the full parsing anyways.

Thanks Daniel. The main blocker is me not able to fully grasp the backward pass. (trying to understand Appendix B.2 in the original paper)

I need to get more comfortable with matrix derivatives before I can confidently reimplement it in the same minimal way as I did with the forward pass.