Abstract presented below for Aydin Buluc from Lawrence Berkeley National Lab: 

Distributed-Memory Parallel Algorithms for Graph Traversal and Genome Assembly

Graph theory is used to model large-scale complex systems in various domains, and has applications in many subfields of scientific computing. I will describe parallel algorithms for exploring and traversing very large graphs arising in genomics and social network analysis.

I 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, I 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.

I will conclude my talk by describing our 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. I will cover the rationale for Graph BLAS, requirements, existing tools, and best practices.

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.