2 ms·
> It’s often said that GPU is bad at data structures, but I’d turn that around. Most, but not all, data structures are bad at GPU. An extreme example is a linke
by dragontamer 8y ago
> It’s often said that GPU is bad at data structures, but I’d turn that around. Most, but not all, data structures are bad at GPU. An extreme example is a linked list, which is still considered reasonable on CPU, and is the backbone of many popular data structures. Not only does it force sequential access, but it also doesn’t hide the latency of global memory access, which can be as high as 1029 cycles on a modern GPU such as Volta.
You're almost correct here, from my understanding. But... I still feel like its important to note that Pointer-jumping exists, and linked-list like structures (linked lists, trees, and graphs) can be traversed in parallel in many cases.
https://en.wikipedia.org/wiki/Pointer_jumping https://en.wikipedia.org/wiki/Pointer_jumping
For pointer-jumping in GPUs / SIMD systems, I know that "Data Parallel Algorithms" discusses the technique as applied to a "reduce" operation aka a "scan": https://dl.acm.org/citation.cfm?id=7903 https://dl.acm.org/citation.cfm?id=7903
The requirement (not fully discussed in the 'Data Parallel Algorithms' article) is that you still need an array of nodes to be listed off by the SIMD system. But this array of nodes does NOT need to be sorted.
As such, you can accomplish a "GPU Reduce" over a linked list in O(lg(n)) steps (assuming an infinite-core machine). This is way slower than the O(lg(n)) array traversal, but you're at least within the same asymptotic class.