search

dmlc / dgl

Python package built to ease deep learning on graph, on top of existing DL frameworks.
http://dgl.ai
Apache License 2.0
13.23k stars 2.99k forks source link

[Feature] GPU traversal #1050

Open yzh119 opened 4 years ago

yzh119 commented 4 years ago

🚀 Feature

GPU traversal (dfs/bfs/topological/...)

Motivation

Currently we only implement single thread traversal on CPU, it's not efficient and the frontiers cannot be generated on-the-fly with message passing.

Pitch

This feature is important for users who are dealing with graphs with a large number of nodes(edges), e.g. @nforest is working on program analysis where dgl traversal becomes their bottleneck.

There has been many literatures working on Graph Traversal on GPU, to name a few:

  1. Gunrock: GPU Graph Analytics, TOPC
  2. GPU-based Graph Traversal on Compressed Graphs, SIGMOD
  3. ...

we can borrow the ideas from these papers and make a traversal on GPU that could generate frontiers on-the-fly with the execution of message function and reduce function. As the design of our built-in function is based on (a minimized) gunrock, I suppose it would not be too hard to implement a gunrock-like traversal algorithm.

jermainewang commented 4 years ago

I mentioned this feature in my RFC #1120 here. I feel at the moment it is too early to work on this unless you have some quick and efficient solutions in mind. I will re-label it as help wanted and we could revisit this once we have more concrete ideas.

jermainewang commented 4 years ago

BTW, it might worth integrating cugraph into DGL.

VoVAllen commented 4 years ago

I agree. Traditional graph algorithms are also useful. Providing such interfaces could attract more users.