Repository-Metriken
- Stars
- (12.665 Stars)
- PR-Merge-Metriken
- (Keine gemergten PRs in 30 T)
Beschreibung
🚀 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:
- Gunrock: GPU Graph Analytics, TOPC
- GPU-based Graph Traversal on Compressed Graphs, SIGMOD
- ...
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.