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.

Parasol Home | Research | People | General info | Seminars | Resources  

Parasol Laboratory, 425 Harvey R. Bright Bldg, 3112 TAMU, College Station, TX 77843-3112 
parasol-admin@cse.tamu.edu      Phone 979.458.0722     Fax 979.458.0718 

Department of Computer Science and Engineering | Dwight Look College of Engineering Dwight Look College of Engineering | Texas A&M University
Privacy statement: Computer Science and Engineering Engineering TAMU
Web Accessibility Policy and Law - Web Accessibility and Usability Standards  -   Contact Webmaster