Running Large Graph Algorithms: Evaluation of Current State-Of-the-Art and Lessons Learned

Google Tech Talk February 11, 2010 ABSTRACT Presented by Dr. Andy Yoo, Lawrence Livermore National Laboratory. Graphs have gained a lot of attention in recent years and have been a focal point in many emerging disciplines such as web mining, computational biology, social network analysis, and national security, just to name a few. These so-called scale-free graphs in the real world have very complex structure and their sizes already have reached unprecedented scale. Furthermore, most of the popular graph algorithms are computationally very expensive, making scalable graph analysis even more challenging. To scale these graph algorithms, which have different run-time characteristics and resource requirements than traditional scientific and engineering applications, we may have to adopt vastly different computing techniques than the current state-of-art. In this talk, I will discuss some of the findings from our studies on the performance and scalability of graph algorithms on various computing environments at LLNL, hoping to shed some light on the challenges in scaling large graph algorithms. Andy Yoo is a computer scientist in the Center for Applied Scientific Computing (CASC). His current research interests are scalable graph algorithms, high performance computing, large-scale data management, and performance evaluation. He has worked on the large graph problems since 2004. In 2005, he developed a scalable graph search algorithm and demonstrated it by searching a graph with billions of edges on IBM BlueGene/L, then the largest and fastest supercomputer. Andy was nominated for 2005 Gordon Bell award for this work. He is currently working on finding right combination of architecture, systems, and programming model to run large graph algorithms. Andy earned his Ph.D. degree in Computer Science and Engineering from the Pennsylvania State University in 1998. He joined LLNL in 1998. Andy is a member of the ACM, IEEE and the IEEE Computer Society, and SIAM.