No
Yes
View More
View Less
Working...
Close
OK
Cancel
Confirm
System Message
Delete
Schedule
An unknown error has occurred and your request could not be completed. Please contact support.
Scheduled
Wait Listed
Personal Calendar
Speaking
Conference Event
Meeting
Interest
Schedule TBD
Conflict Found
This session is already scheduled at another time. Would you like to...
Loading...
Please enter a maximum of {0} characters.
Please enter a maximum of {0} words.
must be 50 characters or less.
must be 40 characters or less.
Session Summary
We were unable to load the map image.
This has not yet been assigned to a map.
Search Catalog
Reply
Replies ()
Search
New Post
Microblog
Microblog Thread
Post Reply
Post
Your session timed out.
This web page is not optimized for viewing on a mobile device. Visit this site in a desktop browser to access the full set of features.
2017 GTC San Jose

S7469 - Parallel Depth-First Search on GPU

Session Speakers
Session Description

The Depth-First Search (DFS) algorithm is a fundamental building block used in many higher level applications, such as topological sort and connectivity and planarity testing of graphs. We'll briefly review prior results and propose two novel variations of parallel DFS on DAGs. The first traverses the graph three times in a breadth-first search-like fashion. The second assigns a weight to each edge, such that the shortest path from root to a node corresponds to the DFS path. The parallel algorithm visits all nodes in the graph multiple times and as a result computes the DFS parent relationship, pre- (discovery) and post-order (finish) time for every node. In some cases, the parallel DFS on GPU can outperform sequential DFS on CPU by up to 6x. However, the performance of the algorithm depends highly on the structure of the graph, and is related to the length of the longest path and the degree of nodes in the graph.


Additional Session Information
All
Talk
Algorithms HPC and Supercomputing
25 minutes
Session Schedule