dmlc/dgl

[Feature] GPU traversal

Open

#1,050 opened on Nov 27, 2019

View on GitHub
 (3 comments) (0 reactions) (0 assignees)Python (12,665 stars) (2,928 forks)batch import
help wanted

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, 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.

Contributor guide

Tech stack
pythonccpp
Domain
backendperformance
Issue type
feature
DifficultyEstimated implementation difficulty for a new contributor, from 1 for very small changes to 5 for expert-level work.
5
Estimated timeA rough time range for an experienced contributor to investigate, implement, test, and prepare a pull request.
over 1 week
Activity statusHow available the issue appears right now: fresh, active, stale, blocked, or waiting on maintainer input.
stale
ClarityHow clearly the issue explains the expected change, acceptance criteria, and next step.
mostly clear
Prerequisites
GPU programminggraph algorithmsCUDADGL internals
Newbie friendlinessA 1-100 score estimating how approachable this issue is for first-time contributors.
10
Research direction
The issue references Gunrock and other GPU graph traversal papers. Start by studying the Gunrock paper and its design, then investigate DGL's built in function design which is based on a minimized Gunrock. The implementation needs to generate frontiers on the fly with message passing. Look into the codebase for existing traversal implementations (e.g., CPU) and the built in function API. Consider implementing a GPU based BFS as a starting point.