Distributed-Memory Parallel Algorithms for Graph Traversal and Genome Assembly 

presented by Aydin Buluc from Lawrence Berkeley National Lab, 2:30p, CS 2205 Multimedia Lab

Graph theory is used to model large-scale complex systems in various domains, and has applications in many subfields of scientific computing. Buluc will describe parallel algorithms for exploring and traversing very large graphs arising in genomics and social network analysis. Buluc will first present a distributed-memory breadth-first search algorithm based on the recently discovered direction optimization idea. This algorithm reduces communication costs by 8X and scales to over 110K cores of a Cray XC30 supercomputer, traversing close to a trillion edges per second. Then, Buluc will present distributed-memory parallelization of de Bruijn graph construction and traversal, which is a key component of most de novo genome assemblers. Results show unprecedented performance and efficient scaling on up to 15,360 cores of a Cray XC30 supercomputer, on human genome as well as the challenging wheat genome, with performance improvement from days to seconds.

The talk will conclude by describing efforts to standardize the Graph BLAS, which are building blocks for graph algorithms in the language of linear algebra. The emergence of a standard set of algorithmic building blocks will free up researchers to innovate and diversify at the level of higher-level algorithms and graph analytics applications. The rationale for Graph BLAS, requirements, existing tools, and best practices will be covered.

Bio:  Aydın Buluç is a research scientist at the Computational Research Division of the Lawrence Berkeley National Laboratory (LBNL). His research interests include parallel computing, combinatorial scientific computing, high performance graph analysis, sparse matrix computations, computational genomics and neuroscience. Previously, he was a Luis W. Alvarez postdoctoral fellow at LBNL and a visiting scientist at the Simons Institute for the Theory of Computing. He received his PhD in Computer Science from the University of California, Santa Barbara in 2010 and his BS in Computer Science and Engineering from Sabanci University, Turkey in 2005. Dr. Buluç is the recipient of a DOE Early Career Award in 2013. He is also a founding associate editor of the ACM Transactions on Parallel Computing. As a graduate student, he spent a semester at the Mathematics Department of MIT, and a summer at the CSRI institute of Sandia National Labs, in New Mexico. Dr. Buluç is a member of the SIAM and the ACM.