|
|
Julian Shun 信哲文
Assistant Professor
Douglas T. Ross Career Development Professor of Software Technology
Electrical Engineering and Computer Science
Computer Science and Artificial Intelligence Laboratory
Massachusetts Institute of Technology
Office: 32-G736
Email: jshun at mit.edu
Address
|
|
I am an assistant professor at MIT in
the
EECS department and a principal investigator in
CSAIL. Prior to
that, I was a
Miller Research Fellow at UC Berkeley working with Michael Mahoney. I obtained
my Ph.D. from Carnegie Mellon University, and was advised by Guy Blelloch.
Research Interests
I am interested in the theory and practice
of parallel and high-performance computing. I work on designing efficient algorithms and data structures with strong theoretical guarantees and good empirical performance. I also work on designing high-level programming frameworks that make it easier for programmers to write efficient parallel code.
Recent domains of interest include graph analytics, computational geometry, and string processing. Below is a description of my recent projects.
Large-scale Graph Processing
I am very interested in
developing algorithms for large-scale graph processing. Graph
algorithms have many applications, ranging from analyzing social
networks to finding patterns in biological networks.
We have developed
Ligra, a lightweight graph
processing framework for shared memory. The project was motivated by
the fact that the largest publicly available real-world graphs all fit
in shared memory. When graphs fit in shared memory, processing them
using Ligra can give performance improvements of up to orders of
magnitude compared to distributed-memory graph processing systems. We
have also developed Ligra+, an extension of Ligra that uses graph
compression techniques to process large graphs with less
memory. We have used Ligra/Ligra+ to design and evaluate
parallel algorithms for graph eccentricity estimation as well as local graph clustering.
In our framework Julienne, we extended Ligra to support algorithms that use bucketing to improve performance. We have built the Aspen framework for streaming graph processing that supports graph updates and queries concurrently with low latency.
Recently, we extended Ligra to support efficient parallel hypergraph algorithms.
- Julian Shun
Practical Parallel Hypergraph Algorithms
Proceedings of the ACM SIGPLAN Symposium on Principles and
Practice of Parallel Programming (PPoPP), pp. 232-249, 2020.
- Laxman Dhulipala, Guy Blelloch, and Julian Shun
Low-Latency Graph Streaming Using Compressed Purely-Functional Trees
Proceedings of the ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI), pp. 918-934, 2019.
Distinguished Paper Award
Source code
- Laxman Dhulipala, Guy Blelloch, and Julian Shun
Julienne: A Framework for Parallel Graph Algorithms using
Work-efficient Bucketing
Proceedings of the ACM Symposium on Parallelism in
Algorithms and Architectures (SPAA), pp. 293-304, 2017.
- Julian Shun, Farbod Roosta-Khorasani, Kimon Fountoulakis, and Michael Mahoney
Parallel Local Graph Clustering
Proceedings of the VLDB Endowment, 9(12), pp. 1041-1052, 2016.
- Julian Shun
An Evaluation of Parallel Eccentricity Estimation Algorithms on Undirected Real-World Graphs
Proceedings of the ACM Conference on Knowledge Discovery and Data Mining (KDD), pp. 1095-1104, 2015.
- Julian Shun, Laxman Dhulipala,
and Guy
Blelloch
Smaller and Faster: Parallel Processing of Compressed Graphs with Ligra+
Proceedings of the IEEE Data Compression Conference (DCC), pp. 403-412, 2015.
- Julian Shun and Guy Blelloch
Ligra: A Lightweight
Graph Processing Framework for Shared Memory
Proceedings of the ACM SIGPLAN Symposium on Principles and
Practice of Parallel Programming (PPoPP), pp. 135-146, 2013.
Webpage for Ligra/Ligra+
Source code
We have designed the Sage graph processing system that supports efficient graph algorithms on non-volatile main memory (NVRAM). We introduce the Parallel Semi-Asymmetric Model (PSAM) for NVRAM graph algorithms, in which the graph is stored as a read-only data structure (in NVRAM), and the amount of mutable memory is kept proportional to the number of vertices.
We have designed the GraphIt domain specific language (DSL) for graph computations where programmers specify the algorithm using an algorithm language, and performance optimizations are specified using a separate scheduling language. The algorithm language simplifies the expression of algorithms, while exposing opportunities for optimizations. The scheduling language enables programmers to easily search a large space of optimizations to find the combinations of optimizations that give the best performance.
- Ajay Brahmakshatriya, Yunming Zhang, Changwan Hong, Shoaib Kamil, Julian Shun, and Saman Amarasinghe
Compiling Graph Applications for GPUs with
GraphIt
Proceedings of the International Symposium on Code Generation and Optimization (CGO), pp. 55-69, 2021.
Best Paper Award
- Yunming Zhang, Ajay Brahmakshatriya, Xinyi Chen, Laxman Dhulipala, Shoaib Kamil, Saman Amarasinghe, and Julian Shun
Optimizing Ordered Graph Algorithms with Graphlt
Proceedings of the International Symposium on Code Generation and Optimization (CGO), pp. 158-170, 2020.
- Yunming Zhang, Mengjiao Yang, Riyadh Baghdadi, Shoaib Kamil, Julian Shun, and Saman Amarasinghe
GraphIt: A High-Performance Graph DSL
Proceedings of Object-Oriented Programming, Systems, Languages & Applications (OOPSLA), pp. 121:1-121:30, 2018.
Website
We have developed practical algorithms with strong theoretical
guarantees for many fundamental graph algorithms, such as connected
components, minimum spanning forest, triangle computations, maximum
flow, maximal independent set, maximal matching, and butterfly computations. Many of these algorithms have been integrated into our Graph Based Benchmark Suite (GBBS).
We have also designed the Kaskade system that automatically derives materialized graph views to speed up graph query evaluation.
- Laxman Dhulipala, Quanquan Liu, Julian Shun, and Shangdi Yu
Parallel Batch-Dynamic k-Clique Counting
Proceedings of the SIAM Symposium on Algorithmic Principles of Computer Systems (APOCS), pp. 129-143, 2021.
- Changwan Hong, Laxman Dhulipala, and Julian Shun
Exploring the Design Space of Static and Incremental Graph Connectivity Algorithms on GPUs
Proceedings of International Conference on Parallel Architectures and Compilation Techniques (PACT), pp. 55-69 2020.
Source code
- Laxman Dhulipala, Changwan Hong, and Julian Shun
ConnectIt: A Framework for Static and Incremental Parallel Graph Connectivity Algorithms
Proceedings of the VLDB Endowment, 14(4), pp. 653-667, 2020.
Source code
- Laxman Dhulipala, Jessica Shi, Tom Tseng, Guy Blelloch, and Julian Shun
The Graph Based Benchmark Suite (GBBS)
Proceedings of the Joint Workshop on Graph
Data Management Experiences & Systems (GRADES) and Network Data Analytics
(NDA), pp. 1-8, 2020.
Website
- Joana M. F. da Trindade, Konstantinos Karanasos, Carlo Curino, Samuel Madden, and Julian Shun
Kaskade: Graph Views for Efficient Graph Analytics
Proceedings of the
IEEE International Conference on Data Engineering (ICDE), pp. 193-204, 2020.
- Jessica Shi and Julian Shun
Parallel Algorithms for Butterfly Computations
Proceedings of the SIAM Symposium on Algorithmic Principles of Computer Systems (APOCS), pp. 16-30, 2020.
Source code
- Laxman Dhulipala, Guy Blelloch, and Julian Shun
Theoretically Efficient Parallel Graph Algorithms Can Be Fast and Scalable
ACM Transactions on Parallel Computing
(TOPC), 2021.
Best Paper Award of SPAA 2018, Special Issue in TOPC 2021
Website
-
Niklas Baumstark, Guy Blelloch, and Julian Shun
Efficient Implementation of a Synchronous Parallel Push-Relabel Algorithm
Proceedings of the European Symposium on Algorithms (ESA), pp. 106-117, 2015.
- Julian Shun and Kanat Tangwongsan
Multicore Triangle Computations Without Tuning
Proceedings of the IEEE International Conference on Data Engineering (ICDE), pp. 149-160, 2015.
Source code
- Julian Shun, Laxman Dhulipala, and Guy Blelloch
A Simple
and Practical Linear-Work Parallel Algorithm for Connectivity
Proceedings of the ACM Symposium on Parallelism in Algorithms and
Architectures (SPAA), pp. 143-153, 2014.
Source code
- Aapo Kyrola, Julian Shun, and Guy Blelloch
Beyond
Synchronous: New Techniques for External Memory Graph
Algorithms
Proceedings of the International Symposium on Experimental Algorithms (SEA),
pp. 123-137, 2014.
Computational Geometry
I am interested in designing parallel algorithms for problems in computational geometry that are both theoretically-efficient and practical. We have developed state-of-the-art parallel algorithms for DBSCAN (density-based spatial clustering of applications with noise) which are scalable and significantly faster than prior work. We have also designed the first parallel batch-dynamic data structure for maintain the closest pair, and presented the first experimental evaluation of parallel closest pair algorithms.
- Yiqiu Wang, Shangdi Yu, Yan Gu, and Julian Shun
An Experimental Study of a New Parallel Batch-Dynamic Closest Pair Data Structure
To appear in Proceedings of the International Symposium on Computational Geometry (SoCG), 2021.
- Yiqiu Wang, Yan Gu, and Julian Shun
Theoretically-Efficient and Practical Parallel DBSCAN
Proceedings of the ACM SIGMOD International Conference on Management of Data (SIGMOD), pp. 2555-2571, 2020.
Source code
Parallel In-Place Algorithms
I am interested in designing parallel algorithms that are in-place, in that they use space sublinear in the input size. In-place algorithms not only reduce memory usage, which is important for processing large data sets, but can also improve locality and performance by reducing data movement.
Write-efficient Algorithms
I am interested in designing
efficient parallel algorithms for memories with asymmetric costs of
reading and writing (e.g., NVRAM). We have developed models for
accounting for read-write asymmetry. Using the models, we have
designed write-efficient algorithms for a number of primitives
including sorting, filter, reduce, Fast Fourier transform,
breadth-first search, list ranking, tree contraction, minimum spanning
forest, and planar convex hull.
- Guy Blelloch, Laxman Dhulipala, Phillip Gibbons, Yan Gu, Charles McGuffey, and Julian Shun
The Read-Only Semi-External Model
Proceedings of the SIAM Symposium on Algorithmic Principles of Computer Systems (APOCS), pp. 70-84, 2021.
- Laxman Dhulipala, Charles McGuffey, Hongbo Kang, Yan Gu, Guy Blelloch, Phillip Gibbons, and Julian Shun
Sage: Parallel Semi-Asymmetric Graph Algorithms for NVRAMs
Proceedings of the VLDB Endowment, pp. 1598-1613, 2020.
- Guy Blelloch, Phillip Gibbons, Yan Gu, Charles McGuffey, and Julian Shun
The Parallel Persistent Memory Model
Proceedings of the ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pp. 247-258, 2018.
- Guy Blelloch, Yan Gu, Julian Shun, and Yihan Sun
Parallel Write-Efficient Algorithms and Data Structures for Computational Geometry
Proceedings of the ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pp. 235-246, 2018.
- Naama Ben-David, Guy Blelloch, Jeremy Fineman, Phillip Gibbons, Yan Gu, Charles McGuffey, and Julian Shun
Implicit Decomposition for Write-Efficient Connectivity Algorithms
Proceedings of the IEEE International Parallel and Distributed Processing Symposium (IPDPS), pp. 711-722, 2018.
- Guy Blelloch, Jeremy Fineman, Phillip Gibbons, Yan Gu, and Julian Shun
Efficient Algorithms with Asymmetric Read and Write Costs
Proceedings of the European Symposium on Algorithms (ESA), pp. 14:1-14:18, 2016.
- Naama Ben-David, Guy Blelloch, Jeremy Fineman, Phillip Gibbons, Yan Gu, Charles McGuffey, and Julian Shun
Parallel Algorithms for Asymmetric Read-Write Costs
Proceedings of the ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pp. 145-156, 2016.
- Guy Blelloch, Jeremy Fineman, Phillip Gibbons, Yan Gu, and Julian Shun
Sorting with Asymmetric Read and Write Costs
Proceedings of the ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pp. 1-12, 2015.
Transaction Processing
We have designed Chiller, a new approach to data partitioning and transaction execution, which aims to minimize data contention for both local and distributed transactions.
Deterministic Parallel Programming
I am interested in
developing tools that many it easier for others to do parallel
programming. In particular, we have developed algorithms, data
structures and tools for deterministic parallel
programming. Determinism is very important in parallel programming as
it allows for ease of debugging, reasoning about correctness and
performance.
- Guy Blelloch, Yan Gu, Julian Shun, and Yihan Sun
Randomized Incremental Convex Hull is Highly Parallel
Proceedings of the ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pp. 103-115, 2020.
- Guy Blelloch, Yan Gu, Julian Shun, and Yihan Sun
Parallelism in Randomized Incremental Algorithms
Journal of the ACM, Vol. 67 Issue 5, Article No. 27, 2020.
- Yu Xia, Xiangyao Yu, William Moses, Julian Shun, and Srini Devadas
LiTM: A Lightweight Deterministic Software Transactional Memory System
Proceedings of the International Workshop on Programming Models and Applications for Multicores and Manycores (PMAM), pp. 1-10, 2019.
Invited to Special Issue
Source code
- Julian Shun, Yan Gu, Guy Blelloch, Jeremy Fineman, and Phillip Gibbons
Sequential Random
Permutation, List Contraction and Tree Contraction are Highly
Parallel
Proceedings of the ACM-SIAM Symposium on Discrete
Algorithms (SODA), pp. 431-448, 2015.
- Julian Shun and Guy Blelloch
Phase-concurrent Hash
Tables for Determinism
Proceedings of the ACM Symposium on Parallelism in Algorithms and
Architectures (SPAA), pp. 96-107, 2014.
- Julian Shun, Guy Blelloch, Jeremy Fineman, and Phillip Gibbons
Reducing Contention
Through Priority Updates
Proceedings of the ACM Symposium on Parallelism in Algorithms and
Architectures (SPAA), pp. 152-163, 2013.
- Guy Blelloch, Jeremy Fineman, and Julian
Shun
Greedy Sequential Maximal
Independent Set and Matching are Parallel on Average
Proceedings of the ACM Symposium on Parallelism in Algorithms and
Architectures (SPAA), pp. 308-317, 2012.
MIS Source Code
Maximal Matching Source Code
- Guy Blelloch, Jeremy Fineman,
Phillip Gibbons, and Julian Shun
Internally
Deterministic Parallel Algorithms Can Be Fast
Proceedings of the ACM SIGPLAN Symposium on Principles and
Practice of Parallel Programming (PPoPP), pp. 181-192, 2012.
Website
Parallel String/Text Algorithms and Data Structures
We have
developed practical parallel algorithms with theoretical guarantees
for several important algorithms and data structures in string/text
processing. These have important applications in bioinformatics, data
compression, and information retrieval.
- Julian Shun
Improved Parallel Construction of Wavelet Trees and Rank/Select Structures
Information and Computation, 2020.
Special Issue of DCC 2017-2018
- Julian Labeit, Julian Shun,
and Guy
Blelloch
Parallel lightweight wavelet tree, suffix array and FM-index construction
Journal of Discrete Algorithms, Vol. 43, pp. 2-17, 2017.
Special Issue of DCC 2016
Source code
- Julian Shun
Parallel Wavelet Tree Construction
Proceedings of the IEEE Data Compression Conference (DCC), pp. 63-72, 2015.
Capocelli Prize for Best Student Paper
Source code
- Julian Shun
Fast Parallel
Computation of Longest Common Prefixes
Proceedings of the ACM/IEEE International Conference for High
Performance Computing, Networking, Storage and Analysis (SC),
pp. 387-398, 2014.
- Julian Shun and Guy Blelloch
A Simple Parallel
Cartesian Tree Algorithm and its Application to Parallel Suffix Tree
Construction
ACM Transactions on Parallel Computing (TOPC), Vol. 1 Issue 1,
Article No. 8, 2014.
Source code
- Julian Shun and Fuyao Zhao (joint first author)
Practical Parallel
Lempel-Ziv Factorization
Proceedings of the IEEE Data Compression Conference (DCC),
pp. 123-132, 2013.
Source code
Parallel Semisorting
We have designed an efficient parallel
algorithm for semisorting (where equal-valued keys are contiguous but
different keys are not necessarily in sorted order). This is a useful
primitive in many applications, for example in performing database
joins and in performing the shuffle phase in the MapReduce paradigm.
- Yan Gu,
Julian Shun, Yihan Sun,
and Guy
Blelloch
A Top-Down Parallel Semisort
Proceedings of the ACM Symposium on Parallelism in Algorithms and Architectures (SPAA), pp. 24-34, 2015.
Problem Based Benchmark Suite (PBBS)
We have developed
a
benchmark
suite of fundamental problems along with parallel algorithms for
solving them. The benchmarks are solely defined by the problem
specification and input/output formats, without any reference to the
algorithm, programming language or machine used. Please contribute
your own implementations to the benchmark suite! The following paper
contains descriptions of the benchmarks and experiments using them:
Ph.D. Thesis