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

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.

Carnegie Mellon Graduate Earns ACM Doctoral Dissertation Award

Julian Shun has won the 2015 ACM Doctoral Dissertation Award presented by ACM for providing evidence that, with appropriate programming techniques, frameworks and algorithms, shared-memory programs can be simple, fast and scalable. In his dissertation Shared-Memory Parallelism Can Be Simple, Fast, and Scalable, he proposes new techniques for writing scalable parallel programs that run efficiently both in theory and in practice.

While parallelism is essential to achieving high performance in computing, writing efficient and scalable programs can be very difficult. Shun’s three-pronged approach to writing parallel programs that he outlines in his thesis includes:

  1. proposing tools and techniques for deterministic parallel programming;
  2. the introduction of Ligra, the first high-level shared-memory framework for parallel graph traversal algorithms; and
  3. presenting new algorithms for a variety of important problems on graphs and strings that are both efficient in theory and practice.

Shun is a post-doctoral researcher at the University of California, Berkeley, where he was awarded a Miller Research Fellowship. He earned his Ph.D. at Carnegie Mellon University, which nominated him for the ACM Doctoral Dissertation Award. He earned a B.A. in Computer Science from the University of California, Berkeley, where he was ranked first in the 2008 graduating class of computer science students. During the 2013-2014 academic year, he was the recipient of a Facebook Graduate Fellowship.

He will receive the Doctoral Dissertation Award and its $20,000 prize at the annual ACM Awards Banquet on June 11 in San Francisco. Financial sponsorship of the award is provided by Google Inc.

Honorable Mention

Honorable mention for the 2015 ACM Doctoral Dissertation Award went to Aaron Sidford of the Massachusetts Institute of Technology, and Siavash Mirarab of the University of Texas at Austin. They will share a $10,000 prize, with financial sponsorship provided by Google Inc.

In Sidford’s dissertation, Iterative Methods, Combinatorial Optimization, and Linear Programming Beyond the Universal Barrier, he considers the fundamental problems in continuous and combinatorial optimization that occur pervasively in practice, and shows how to improve upon the best-known theoretical running times for solving these problems across a broad range of parameters. Sidford uses and improves techniques from diverse disciplines including spectral graph theory, numerical analysis, data structures, and convex optimization to provide the first theoretical improvements in decades for multiple classic problems ranging from linear programming to linear system solving to maximum flow. Sidford is presently a postdoctoral researcher at Microsoft New England. He received a Ph.D. in Computer Science from the Massachusetts Institute of Technology, which nominated him for this award.

Mirarab’s dissertation, Novel Scalable Approaches for Multiple Sequence Alignment and Phylogenomic Reconstruction, addresses the growing need to analyze large-scale biological sequence data efficiently and accurately. To address this challenge, Mirarab introduces several methods: PASTA, a scalable and accurate algorithm that can align data sets up to one million sequences; statistical binning, a novel technique for reducing noise in estimation of evolutionary trees for individual parts of the genome; and ASTRAL, a new summary method that can run on 1,000 species in one day and has outstanding accuracy. These methods were essential in analyzing very large genomic datasets of birds and plants. Mirarab is currently an Assistant Professor of Electrical and Computer Engineering at the University of California, San Diego. He obtained a Ph.D. in Computer Science from the University of Texas at Austin, which nominated him for this award.