Julian Shun

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

ACM Doctoral Dissertation Award

USA - 2015

citation

For his dissertation, "Shared-Memory Parallelism Can Be Simple, Fast, and Scalable," nominated by Carnegie Mellon University.

Press Release