3 ms·

Nice! It's interesting from the perspective of maintenance too. You can bet most constants like warp sizes will change, so you get into things like having prof

Nice! It's interesting from the perspective of maintenance too. You can bet most constants like warp sizes will change, so you get into things like having profiles, autotuners, or not sweating the small stuff. We went more extreme, and nowadays focus on several layers up: By accepting the (high!) constant overheads of tools like RAPIDS cuDF , we get in exchange the ability to easily crank code with good saturation on the newest GPUs and that any data scientist can edit and extend. Likewise, they just need to understand basics like data movement and columnar analytics data reps to make GPU pipelines. We have ~1 CUDA kernel left and many years of higher-level. As an example, this is one of the core methods of our new graph query language GFQL (think cypher on pandas/spark, w optional GPU runtime), and it gets Graph500 level performance on cheapo GPUs just by being data parallel with high saturation per step: https://github.com/graphistry/pygraphistry/blob/master/graphistry/compute/hop.py https://github.com/graphistry/pygraphistry/blob/master/graph... . Despite ping-ponging a ton because cudf doesn't (yet) coalesce GPU kernel calls, V1 competes surprisingly high, and is easy to maintain & extend.

trentnelson 2y ago
Had any exposure to r=2 hypergraph implementations on the GPU? Ideally with an efficient way to determine if the graph is acyclic? (The CPU algos for doing this work great on CPUs but are woeful on GPUs.)
- lmeyerov 2y ago
  Pretty good - r=2 is a regular graph afaict, and basically anything that maps to a frontier-based pattern works well. Ex: level synchronous bfs during topological sort. For the 'easy' way we do in gfql, which is basically vector ops on bulk wavefronts, we can do massive cypher traversals like you're asking, like 100M edges touched in a result substep, and on a tiny GPU. There are other such bulk patterns we want to add such as Pregel style, which open other algorithms here. In practice we can often just call cudf/cugraph as building blocks so haven't had the pressure to do so yet. The weak spot I find is more like small OLTP lookups. Ex: Imagine a taxi routing traffic service pinging for one car to do a couple hops out, where you just want a KV store in cheap RAM. But if you are batching those queries, like in a heavy city, and going deeper on them, maybe more interesting.

trentnelson 2y ago

Had any exposure to r=2 hypergraph implementations on the GPU? Ideally with an efficient way to determine if the graph is acyclic? (The CPU algos for doing this work great on CPUs but are woeful on GPUs.)

lmeyerov 2y ago
Pretty good - r=2 is a regular graph afaict, and basically anything that maps to a frontier-based pattern works well. Ex: level synchronous bfs during topological sort. For the 'easy' way we do in gfql, which is basically vector ops on bulk wavefronts, we can do massive cypher traversals like you're asking, like 100M edges touched in a result substep, and on a tiny GPU. There are other such bulk patterns we want to add such as Pregel style, which open other algorithms here. In practice we can often just call cudf/cugraph as building blocks so haven't had the pressure to do so yet. The weak spot I find is more like small OLTP lookups. Ex: Imagine a taxi routing traffic service pinging for one car to do a couple hops out, where you just want a KV store in cheap RAM. But if you are batching those queries, like in a heavy city, and going deeper on them, maybe more interesting.