Upcoming Events

Large-Scale Graph Traversal Algorithms on Multi-core Clusters

February 8, 2013 10:30AM to 11:30AM
Presenter 
Huiwei Lu, Postdoc Interviewee
Location 
Building 240, Room 1406
Type 
Seminar
Series 
Abstract:
There is an ever-increasing need for exploring large-scale graph data sets in computational sciences, social networks, and business analytics. One of the most widely used graph searching algorithms is breadth-first search (BFS), which serves as a building block for a great many graph algorithms such as minimum spanning tree, betweenness centrality, and shortest paths. However, BFS is notoriously known challenging to optimize because of its poor locality and low computation to communication ratio. In this talk I will present several of our findings to improve the efficiency of BFS algori thms: exploiting different levels of parallelism to provide latency hiding and maximize memory bandwidth; reducing communication in distributed BFS to improve its scalability.