Home research People General Info Seminars Resources Intranet
Time - Thursday, September 22, 2016, 4:00 pm
Location - 302 HRBB

Fast Approximate Distance Queries in Unweighted Graphs using Bounded Asynchrony

Adam Fidel
Parasol Laboratory, Department of Computer Science
Texas A&M University


We introduce a new parallel algorithm for approximate breadth-first ordering of an unweighted graph by using bounded asynchrony to parametrically control both the performance and error of the algorithm. This work is based on the k-level asynchronous (KLA) paradigm that trades expensive global synchronizations in the level-synchronous model for local synchronizations in the asynchronous model, which may result in redundant work. Instead of correcting errors introduced by asynchrony and redoing work as in KLA, in this work we control the amount of work that is redone and thus the amount of error allowed, leading to higher performance at the expense of a loss of precision. Results of an implementation of this algorithm are presented on up to 32,768 cores, showing 2.27x improvement over the exact KLA algorithm with minimal error on several graph inputs.


Adam Fidel is a PhD student in the Department of Computer Science and Engineering at Texas A&M University working with Dr. Nancy Amato and Dr. Lawrence Rauchwerger in the Parasol Lab. He received his Bachelor of Science in Computer Science from Texas Tech University in 2010. His research interests include parallel programming, high-performance computing and parallel graph algorithms. More information about Adam can be found at http://parasol.tamu.edu/people/afidel.