3 ms·

I was about to share this with the team at OmniSci (GPU analytics platform) and realized the authors included our very own Saman Ashkiani and adviser John Owens

I was about to share this with the team at OmniSci (GPU analytics platform) and realized the authors included our very own Saman Ashkiani and adviser John Owens. Having fast dynamic data structures on the GPU is of huge utility. People think that you can't make these sorts of things efficient due to thread divergence, but if you do it right, the massive flops and memory bandwidth of a GPU can really work in your favor.

espeed 8y ago
Hi Todd - Has your team looked at GraphBLAS [1] yet for MapD [2] now that Tim Davis has released a 2.0 reference C implementation (included in SuiteSparse 5.3) [3]? There is a GraphBLAS 2.0 CPU implementation in RedisGraph now [4] and official GraphBLAS 2.x GPU implementations are in the works. [1] GraphBLAS http://graphblas.org http://graphblas.org [2] OmniSci MapD DB https://github.com/omnisci/mapd-core https://github.com/omnisci/mapd-core [3] SuiteSparse::GraphBLAS http://faculty.cse.tamu.edu/davis/suitesparse.html http://faculty.cse.tamu.edu/davis/suitesparse.html [4] Previous Discussion https://news.ycombinator.com/item?id=18099520 https://news.ycombinator.com/item?id=18099520
- tmostak 8y ago
  I've definitely been hearing about the project but didn't know it was being ported to GPU, that's great news. How does this compare to things like Gunrock?
  - ctchocula 8y ago
    Hi Todd! Our recent work implements a subset of GraphBLAS operations for GPU and compares them to Gunrock in breadth-first-search [1]. Our implementation of a subset of GraphBLAS is comparable to Gunrock performance for power law graphs, but are worse for mesh graphs. Gunrock uses a different load-balancer in Advance for those graphs and the load-balancer we use in the analogous operation (matrix-vector multiplication) isn't as optimized for mesh graphs. We definitely want to collect data in more applications than just BFS, so we're working on that now. The code is open-source, so feel free to check it out! [2] [1] https://arxiv.org/pdf/1804.03327.pdf https://arxiv.org/pdf/1804.03327.pdf [2] https://github.com/owensgroup/push-pull https://github.com/owensgroup/push-pull
sytelus 8y ago
What kind of scenarios will this be useful? I suspect main bottleneck here is GPU bandwidth so this will be great when large merge operations are needed but I still can’t tell what kind of applications will see the major improvement.
- tmostak 8y ago
  If by GPU bandwidth you mean GPU memory bandwidth, being able to operate at memory bandwidth is typically a huge win over CPU, not only because of the big difference between GPU and CPU bandwidth (900 GB/sec vs 150-200 GB/sec), but also because it is often harder to hit CPU bandwidth because a lack of FLOPs/higher difficulty vectorizing certain algorithms on CPU. Imagine being able to keep a dynamic dictionary on the GPU to support dictionary-encoded strings or enforcing of unique ids. We do these sorts of things on the CPU now, and have made them relatively fast, but making them faster with GPU-acceleration could significantly speed up import, a major focus of ours. We also currently build our hash maps on the fly for joins, and can cache the hash table when it makes sense, but have to rebuild from scratch when there are updates or deletes. We could likely build on this sort of data structure to be able to not start from scratch every time there is an update/delete. Sure there are lots of other uses, just thinking off the top of my head.

espeed 8y ago

Hi Todd - Has your team looked at GraphBLAS [1] yet for MapD [2] now that Tim Davis has released a 2.0 reference C implementation (included in SuiteSparse 5.3) [3]? There is a GraphBLAS 2.0 CPU implementation in RedisGraph now [4] and official GraphBLAS 2.x GPU implementations are in the works. [1] GraphBLAS http://graphblas.org http://graphblas.org [2] OmniSci MapD DB https://github.com/omnisci/mapd-core https://github.com/omnisci/mapd-core [3] SuiteSparse::GraphBLAS http://faculty.cse.tamu.edu/davis/suitesparse.html http://faculty.cse.tamu.edu/davis/suitesparse.html [4] Previous Discussion https://news.ycombinator.com/item?id=18099520 https://news.ycombinator.com/item?id=18099520

tmostak 8y ago
I've definitely been hearing about the project but didn't know it was being ported to GPU, that's great news. How does this compare to things like Gunrock?
- ctchocula 8y ago
  Hi Todd! Our recent work implements a subset of GraphBLAS operations for GPU and compares them to Gunrock in breadth-first-search [1]. Our implementation of a subset of GraphBLAS is comparable to Gunrock performance for power law graphs, but are worse for mesh graphs. Gunrock uses a different load-balancer in Advance for those graphs and the load-balancer we use in the analogous operation (matrix-vector multiplication) isn't as optimized for mesh graphs. We definitely want to collect data in more applications than just BFS, so we're working on that now. The code is open-source, so feel free to check it out! [2] [1] https://arxiv.org/pdf/1804.03327.pdf https://arxiv.org/pdf/1804.03327.pdf [2] https://github.com/owensgroup/push-pull https://github.com/owensgroup/push-pull

sytelus 8y ago

What kind of scenarios will this be useful? I suspect main bottleneck here is GPU bandwidth so this will be great when large merge operations are needed but I still can’t tell what kind of applications will see the major improvement.

tmostak 8y ago
If by GPU bandwidth you mean GPU memory bandwidth, being able to operate at memory bandwidth is typically a huge win over CPU, not only because of the big difference between GPU and CPU bandwidth (900 GB/sec vs 150-200 GB/sec), but also because it is often harder to hit CPU bandwidth because a lack of FLOPs/higher difficulty vectorizing certain algorithms on CPU. Imagine being able to keep a dynamic dictionary on the GPU to support dictionary-encoded strings or enforcing of unique ids. We do these sorts of things on the CPU now, and have made them relatively fast, but making them faster with GPU-acceleration could significantly speed up import, a major focus of ours. We also currently build our hash maps on the fly for joins, and can cache the hash table when it makes sense, but have to rebuild from scratch when there are updates or deletes. We could likely build on this sort of data structure to be able to not start from scratch every time there is an update/delete. Sure there are lots of other uses, just thinking off the top of my head.