The One Billion Row Challenge in CUDA: from 17 minutes to 17 seconds

Re:The One Billion Row Challenge in CUDA: from 17 minutes to... by tspeterkim on Saturday April 13, 2024 @11:44PM (#40028476)

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.

[ Parent | on HN ]

Re:The One Billion Row Challenge in CUDA: from 17 minutes to... by convivialdingo on Sunday April 14, 2024 @09:54AM (#40031050)

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

[ Parent | on HN ]

Re:The One Billion Row Challenge in CUDA: from 17 minutes to... by mandarax8 on Sunday April 14, 2024 @10:23AM (#40031255)

> Atomic operations are limited to 32-bits.

I'm using 64bit atomics at work, are you on an old version of cuda or are some operations only supported on 32bit?

[ Parent | on HN ]

Re:The One Billion Row Challenge in CUDA: from 17 minutes to... by tspeterkim on Sunday April 14, 2024 @10:35AM (#40031371)

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.

[ Parent | on HN ]

Re:The One Billion Row Challenge in CUDA: from 17 minutes to... by Sesse__ on Sunday April 14, 2024 @10:55AM (#40031532)

If the set of cities is known (as your binary search algorithm assumes), you can insert all of them first, on the CPU. That will resolve all collisions ahead of time, making the structure of the hash table essentially read-only. (Of course, you would still need atomics for the values.)

[ Parent | on HN ]