Efficient Implementation of Key Graph Algorithms

Project Details

Combinatorial algorithms in general and graph algorithms in particular play a critical enabling role in numerous scientific applications. However, the irregular memory access nature of these algorithms makes them some of the hardest algorithmic kernels to implement on parallel systems. With tens of billions of hardware threads and deep memory hierarchies, the exascale computing systems pose extreme challenges in scaling graph algorithms. ExaGraph, the co-design center on combinatorial algorithms, was established to design and develop methods and techniques for the efficient implementation of key combinatorial (graph) algorithms chosen from a diverse set of exascale applications that cover computational biology, chemistry, earth system sciences, and the electric power grid.

Algebraic and combinatorial methods have a complementary and mutually enabling role in the advancement of computational science and engineering. ExaGraph brings together the algorithmic design and software development activities from a combinatorial and an algebraic perspective. This approach has enabled the ExaGraph team to develop scalable algorithms and implementations for a range of graph algorithms, including weighted matching, coloring, clustering (i.e., community detection), partitioning, and influence maximization. Recent efforts have resulted in the successful porting of the algorithms to many-core accelerator (i.e., GPU) architectures with significant speedups for several graph problems. The efforts of the ExaGraph team have benefitted several exascale applications through scalable implementations of different combinatorial algorithms to enable scientific discovery at scale. In addition to applications, efforts of ExaGraph also benefit from the benchmarking of exascale hardware and software systems, the scaling of novel artificial intelligence and machine learning methods, and the training and development of the next generation of scientists.

Principal Investigator(s):

Mahantesh Halappanavar, Pacific Northwest National Laboratory

Collaborators:

Pacific Northwest National Laboratory, Lawrence Berkeley National Laboratory, Purdue University, Sandia National Laboratories

National Nuclear Security Administration logo U.S. Department of Energy Office of Science logo