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.

[muneshchauhan]

I wonder why no mention of GPU multicores are not mentioned in the talk?

[seebe]

at 45:20 he said pure data flow model showstopper applied to graph. eventually some type of control flow emerges for graph algorithm.

[MoTheG]

there is somekind of volume pumping
and papershifting going on, the offsites didn't deactivate their mics.

in a dataflow model, isn't there a lot of datapassing because the context/progress has to be passed with the data? there is no locality to the current state of processing.? is that what he said at 45:20 ?

[NuncNuncNuncNunc]

Google, how about community driven caption correction as a youtube app.

"breadth first search" and "naive" were fairly consistently incorrect & "huddle" may have been "how to"

[beardymonger]

Put the computer generated CC for some fun ;-)

I guess the accent didn't help either.