Seminars & Events

Mathematics and Computer Science Division
"Large-Scale Graph Traversal Algorithms on Multi-core Clusters"

DATE: February 8, 2012
TIME: 10:30 AM - 11:30 AM
SPEAKER: Huiwei Lu, Postdoc Interviewee
LOCATION: Building 240, Conference Center, Room 1406 , Argonne National Laboratory
HOST: Pavan Balaji

Description:
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 algorithms: exploiting different levels of parallelism to provide latency hiding and maximize memory bandwidth; reducing communication in distributed BFS to improve its scalability.

Save the event to your calendar [schedule.ics]