SCHEDULE: NOV 15-20, 2015

When viewing the Technical Program schedule, on the far righthand side is a column labeled "PLANNER." Use this planner to build your own schedule. Once you select an event and want to add it to your personal schedule, just click on the calendar icon of your choice (outlook calendar, ical calendar or google calendar) and that event will be stored there. As you select events in this manner, you will have your own schedule to guide you through the week.

A Work-Efficient Algorithm for Parallel Unordered Depth-First Search

SESSION: Graph Algorithms and Benchmarks

EVENT TYPE: Papers

EVENT TAG(S): Performance, Graphs, Data-Intensive Computing, Algorithms

TIME: 1:30PM - 2:00PM

SESSION CHAIR(S): Umit Catalyurek

AUTHOR(S):Umut Acar, Arthur Chargueraud, Mike Rainey

ROOM:18CD

ABSTRACT:

With the increasing processing power of multicore computers, parallel graph search using shared memory machines has become increasingly feasible and important. There has been a lot of progress on parallel breadth-first search, but less attention has been given to algorithms for unordered or loosely ordered traversals. We present a parallel algorithm for unordered depth-first-search on graphs. We prove that the algorithm is work-efficient in a realistic, implementation-ready algorithmic model that includes important scheduling costs. This work-efficiency result applies to all graphs, including those with high diameter and high out-degree. The key components of this result include a new data structure and a new amortization technique for controlling excess parallelism. We present an implementation and experiments that show that the algorithm performs well on a range of graphs and can lead to significant improvements over comparable algorithms.

Chair/Author Details:

Umit Catalyurek (Chair) - Ohio State University|

Umut Acar - Carnegie Mellon University

Arthur Chargueraud - French Institute for Research in Computer Science and Automation

Mike Rainey - French Institute for Research in Computer Science and Automation

  Click here to download .ics calendar file

  Click here to download .vcs calendar file

  Click here to add event to your Google Calendar

Paper provided by the ACM Digital Library

Paper also available from IEEE Computer Society