Laxman Dhulipala

Digital Library

ACM Paris Kanellakis Theory and Practice Award

USA - 2023

citation

For their groundbreaking contributions to algorithm engineering, which has revolutionized large-scale graph processing on shared-memory machines.

Starting in 2013, Blelloch, Dhulipala, and Shun embarked on a journey to explore how to analyze huge graphs with billions of vertices and hundreds of billions of edges on relatively inexpensive shared-memory multiprocessors. Their journey led to the creation of a series of frameworks, starting with Ligra, followed by the Graph-Based Benchmark Suite (GBBS), and finally Aspen. These frameworks make it much easier for programmers to efficiently solve a wide variety of graph problems.

They have obtained many outstanding results, in which their provably efficient algorithms running on an inexpensive multi-core shared-memory machine are faster than all prior algorithms, even those running on much bigger and more expensive computers. Examples of such results include clustering, clique counting, and various forms of graph connectivity. These ideas and implementations are being used in industry to handle real-world problems and have also had a profound impact on research in the field.

A major factor in the success and influence of the work of Blelloch, Dhulipala, and Shun is the simplicity and elegance of the Ligra parallel programming abstraction. In a nutshell, the Ligra interface is a domain-specific language that lets users express graph programs in terms of two high-level concepts: mapping over vertices and mapping over edges that are naturally parallel and are commonly used to describe graph algorithms.

Building upon Ligra, the subsequent work on GBBS augmented this interface with richer primitives with provable parallel costs and showed how to implement over twenty fundamental graph problems using it, showing that the resulting implementations ran in a matter of seconds to minutes on graphs with hundreds of billions of edges. This is not only faster than all previous practical results on such large graphs, but also orders of magnitude cheaper in terms of computing and memory.

For the setting of streaming graphs, which model graphs that change in real-time, they developed Aspen, a graph-streaming system that uses new purely functional data structures to enable low-latency updates and snapshots on massive graph datasets.

The ideas of Blelloch, Dhulipala, and Shun have taken a deep root in the academic and industry communities and had a transformative impact on the theory and practice of the area of shared memory parallel algorithms.

Press Release

2023 ACM Paris Kanellakis Theory and Practice Award

Guy E. Blelloch, Carnegie Mellon University; Laxman Dhulipala, University of Maryland; and Julian Shun, Massachusetts Institute of Technology, receive the ACM Paris Kanellakis Theory and Practice Award for contributions to algorithm engineering, including the Ligra, GBBS, and Aspen frameworks which revolutionized large-scale graph processing on shared-memory machines.

Beginning in 2013, Blelloch, Dhulipala and Shun began to explore how to analyze huge graphs (billions of vertices and hundreds of billions of edges) on relatively inexpensive shared-memory multiprocessors. They built several frameworks (Ligra, Ligra +, Julienne, GBBS, and Aspen) that make it much easier for programmers to efficiently solve a wide variety of graph problems. They have obtained many truly outstanding results in which their provably efficient algorithms running on an inexpensive multi-core shared-memory machine are faster than any prior algorithms, even those running on much bigger and more expensive machines. Examples of such results include clustering, clique counting, and various forms of connectivity. These ideas and implementations are being used in industry to handle real-world problems and have also had tremendous impact on research in the field.

One important upshot of this work was the paradigm-changing demonstration that shared-memory computers are an ideal platform for analyzing large graphs. At the time Ligra was first developed, the predominant approach used to analyze large graphs was distributed systems such as Pregel (developed by Google). This was overturned when, for many important large real-world graph problems, the Ligra approach turned out to be much more efficient in terms of energy, cost, and end-to-end running time.

Their work on graph processing also allows algorithms with provable performance guarantees in the PRAM model to live up to their theoretical performance in practice. Recently, the nominees addressed the emerging setting of processing streaming graphs, which models graphs that change in real time and developed Aspen, a novel graph streaming system that uses new purely functional data structures to enable low-latency updates and snapshots on massive graph datasets.