Show HN: A Simple GPU Hash Table
nosferalatu.com
Show HN: A Simple GPU Hash Table
1–10 of 18 posts
Re: Show HN: A Simple GPU Hash Table
#2That is a most awesome thing you did there. Thank you very much for sharing!
Re: Show HN: A Simple GPU Hash Table
#3This is just mind blowingly cool
Re: Show HN: A Simple GPU Hash Table
#4Concerning: “...as the table is linearly searched, the slot index must be wrapped at each slot. The cost of a modulo operation at each slot quickly adds up.” As you linearly search, you don’t need to re-modulo; you just have to set the index to zero if it has reached the end of the table, so it’s a simple compare-and-conditionally-assign operation.
Re: Show HN: A Simple GPU Hash Table
#5I wonder if this technique can be used to implement order independent transparency on GPU in a performant manner.
Really great algorithm regardless!
Explanatory Edit:
Visually correct alpha blending requires all blended pixels to be known at the blend time but the way real time graphic pipelines work is too lossy to achieve that. Intermediate pixel are lost on each fragment step.
In current game engines, when a semi-transparent object is rendered, it can only know the previous blended state of the pixel it is writing into. So instead of being able to do something like `blend(p1, p2, p3, p4, ...)`, you work around it with a blend model that looks like `blend(..., blend(p4, blend(p3, blend(p2, p1))))`. A common working (partially) solution uses a linked list of pixel colors, encoded in a texture (src: NVidia RnD) to be able to preserve these colors until the final image is rendered. It is still costly in terms of computation and space. There are other solutions but each has its own, unavoidable drawbacks.
So I figured as a newbie, maybe this hash table can store pixel location as key and a linked list of colors as value to mitigate for the computation cost of NVidia's algorithm. The space cost is still there though. Or maybe I'm entirely wrong.
Re: Show HN: A Simple GPU Hash Table
#6How does the performance compare to other implementation either for GPU or not?
Re: Show HN: A Simple GPU Hash Table
#7A 32-bit key and 32-bit value are some serious constraints. The whole point of hash tables is usually that you have variable length keys or values.
If you have more than 32GB of RAM (which is not rare nowadays) you can directly map all 32-bit values into a 32GB chunk of memory and be probably faster than this GPU solution on regular CPUs.
Re: Show HN: A Simple GPU Hash Table
#8My understanding is that pcie devices incur a very high latency for getting data to and from them, due to the pcie device itself and setting up a dma descriptor. Sadly this article doesn't look into that.
Can someone comment on what sort of latency would be involved in something like this? For example, latency to send to pcie device, latency to react to and manipulate the data in a warp(Nvidia?), and latency to send the data back to the host system?
Re: Show HN: A Simple GPU Hash Table
#9A 32-bit key and 32-bit value are some serious constraints. The whole point of hash tables is usually that you have variable length keys or values. If you have more than 32GB of RAM (which is not rare nowadays) you can directly map all 32-bit values into a 32GB chunk of memory and be probably faster than this GPU solution on regular CPUs.
Even so, GPU-based hash tables are useful in that they can be used to speed up various kinds of simulations for video games and animation:
https://wickedengine.net/2018/05/21/scalabe-gpu-fluid-simula...
https://developer.nvidia.com/gpugems/gpugems3/part-i-geometr...
Re: Show HN: A Simple GPU Hash Table
#10Awesome!
> The table uses power-of-two sizes instead of prime numbers because pow2/AND masking is a fast single instruction and the modulo operator is much slower.
I was under the impression that the idea of prime number hash table sizes being faster was shredded a couple decades ago? Maybe by Bob Jenkins?