The development of capable exascale systems was made possible by a collaborative interdisciplinary co-design strategy. The Exascale Computing Project (ECP) established collaborations among software developers and hardware technology experts in co-design centers such as ExaGraph, thereby fostering a participatory development process to meet the complex and often conflicting needs of current and future exascale applications. The co-design teams worked closely with application developers to deliver efficient and reliable software products that are integral to the unprecedented results generated on exascale supercomputers such as Frontier.
Graph algorithms play a critical role in enabling many computational solutions to modern scientific problems. These algorithms can be used to analyze and manipulate mathematical structures consisting of multiple, connected nodes. Working with graph algorithms, researchers can solve network and optimization problems in fields ranging from bioinformatics and computational chemistry to wind energy and control of power grids. However, creating graph algorithms that efficiently scale in performance on large parallel computational systems such as supercomputers is extremely difficult. Creating efficient graph algorithms that can leverage next-generation supercomputers such as Frontier and Aurora requires breakthrough research in computational science and engineering and enables the massively complex simulations needed to address key issues in renewable energy, pharmaceutical and materials design, genomic research, and many other scientific fields.
The ECP’s ExaGraph co-design center was created to discover and implement the most powerful and multifunctional graph algorithms to date. The ExaGraph team collaborated with application developers to produce novel algorithms that can be easily integrated into numerous programs with varying scientific aims. The resulting software suite represents the best—and often the only—tool for solving many classes of extreme-scale combinatorial problems.
The ExaGraph team significantly improved the applicability of graph algorithms in computationally intense problems. Among the several software innovations that support these improvements, approximation algorithms have been critical; ExaGraph has scaled combinatorial graph analysis by creating algorithms that closely approximate solutions rather than calculating them precisely. This change causes the amount of work needed for a parallel computing system to solve a problem to scale linearly with the problem’s size—rather than exponentially—thereby enabling supercomputers to solve immense problems while retaining precision and feasible simulation times. ECP approximation algorithms—along with innovations in areas such as graph partitioning and influence maximization—are essential for graph algorithms to perform at exascale.
ExaGraph’s contributions to computational science and the engineering of scalable graph algorithms have precipitated dramatic improvements to simulation capabilities in key areas of scientific and social interest. Using advanced graph algorithms on exascale-class supercomputers, researchers will produce innovative methods and technologies that support sustainability and improved quality of life.
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.