June 17-21, 2012

Hamburg, Germany

Contribution Details

Name: Understanding Parallelism in Graph Traversal on Multi-core Clusters
Time: Tuesday, June 19, 2012
9:30 AM - 10:00 AM
Room:   Hall C2.2
CCH - Congress Center Hamburg
Speakers:   Huiwei Lv, Chinese Academy of Sciences
Abstract:   There is an ever-increasing need for exploring large-scale graph data sets in computational sciences, social networks, and business analytics. However, due to irregular and memory-intensive nature, graph applications are notoriously known for their poor performance on parallel computer systems. In this paper we propose a new hybrid MPI/Pthreads breadth-first search (BFS) algorithm featuring with (i) overlapping computation and communication by separating them into multiple threads, (ii) maximizing multi-threading parallelism on multi-cores with massive threads to improve throughputs, and (iii) exploiting pipeline parallelism using lock-free queues for asynchronous communication. By comparing it with traditional MPI-only BFS algorithm, we learned several valuable lessons that would help to understand and exploit parallelism in graph traversal applications. Experiments show our algorithm is 1.9x faster than the MPI-only version, capable of processing 1.45 billion edges per second on a 32-node SMP cluster. At a large scale, our algorithm is 1.49x than the MPI-only BFS algorithm in Combina-tionrial BLAS Library with 6,144 cores.  
  • Tutorial Pass
  • HPC in Asia Workshop Pass
  • Conference Pass
  • Conference Pass or Exhibition Pass
    Satellite Event marked with * requires separate pass
  • Morning & Afternoon Coffee Breaks
    Midday Lunch Break
Program may be subject to changes.