dmlc / dmlc/dgl

[Feature] GPU traversal

Open
#1,050 3 comments 0 reactions 0 assignees View on GitHub
help wanted
Dominant language
Python
Stars
14.3k
Forks
3.1k
PR merge metrics
No merged PRs in 30d

Description

## 🚀 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](https://arxiv.org/pdf/1701.01170.pdf), TOPC
2. [GPU-based Graph Traversal on Compressed Graphs](https://www.comp.nus.edu.sg/~sham/publications/sigmod_gcgt.pdf), 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.

Contributor guide

No contributing guide indexed for this repository

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.