

Julian Shun
Ph.D. student School of Computer Science Carnegie Mellon
University Email ID: jshun Domain: cs.cmu.edu
C.V.

I am a Ph.D. student in
the
Computer
Science Department at Carnegie Mellon University. I am fortunate
to be advised by
Guy Blelloch. I am also fortunate to be supported
by
a
Facebook Graduate Fellowship for 20132014. I
obtained my bachelor's degree in Computer Science from UC Berkeley.
Research Interests
I am interested in all aspects of parallel
computing, especially parallel graph processing frameworks,
algorithms, data structures and tools for deterministic parallel
programming. Below is a description of my recent projects.
(For certain papers, the authors are listed alphabetically,
following the convention in mathematics and theoretical computer
science, and others are listed by contribution.)
Largescale Graph Processing
I am very interested in
developing algorithms for largescale graph processing. Graph
algorithms have many applications, ranging from analyzing social
networks to finding patterns in biological networks.
I have developed
Ligra, a lightweight graph
processing framework for shared memory. The project was motivated by
the fact that the largest publicly available realworld graphs all fit
in shared memory. When graphs fit in sharedmemory, processing them
using Ligra can give performance improvements of up to orders of
magnitude compared to distributedmemory graph processing systems. As
an extension, I am currently working on supporting graph compression
techniques in Ligra, so that it can support large graphs with less
memory.
I have also developed algorithms with strong theoretical guarantees
for many fundamental graph algorithms, such as connected components,
minimum spanning forest, maximal independent set and maximal
matching. I have implemented these algorithms for the shared memory
multicore setting and also for external memory.
 (by contribution) Julian Shun and Kanat Tangwongsan.
Multicore Triangle Computations Without Tuning
To appear in Proceedings of the IEEE International Conference on Data Engineering (ICDE), 2015.
 (by contribution) Julian Shun, Laxman Dhulipala and Guy Blelloch.
A Simple
and Practical LinearWork Parallel Algorithm for Connectivity
Proceedings of the ACM Symposium on Parallelism in Algorithms and
Architectures (SPAA), pp. 143153, 2014.
Source code
 (by contribution) Aapo Kyrola, Julian Shun and Guy Blelloch.
Beyond
Synchronous: New Techniques for External Memory Graph
Algorithms
Proceedings of the Symposium on Experimental Algorithms (SEA),
pp. 123137, 2014.
 (by alphabetical order) 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. 308317, 2012.
Parallel Text Algorithms and Data Structures
I have developed
algorithms for several important algorithms and data structures in
text processing. These have important applications in bioinformatics,
data compression, information retrieval among many others. The
algorithms are the stateoftheart for shared memory multicore
machines.
Problem Based Benchmark Suite (PBBS)
I 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 by sending them to me!
The following papers contain descriptions of the benchmarks and
experiments using them:
 (by contribution) Julian Shun, Guy Blelloch, Jeremy Fineman,
Phillip Gibbons, Aapo Kyrola, Harsha Vardhan Simhadri and Kanat Tangwongsan.
Brief Announcement: The
Problem Based Benchmark Suite
Proceedings of the ACM Symposium on Parallelism in Algorithms and
Architectures (SPAA), pp. 6870, 2012.
Website
 (by alphabetical order) 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. 181192, 2012.
Deterministic Parallel Programming
I am interested in
developing tools that many it easier for others to do parallel
programming. In particular, I 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.
 (by contribution) Julian Shun, Yan Gu, Guy Blelloch, Jeremy Fineman and Phillip Gibbons.
Sequential Random
Permutation, List Contraction and Tree Contraction are Highly
Parallel
To appear in Proceedings of the ACMSIAM Symposium on Discrete
Algorithms (SODA), 2015.
 (by contribution) Julian Shun and Guy Blelloch.
Phaseconcurrent Hash
Tables for Determinism
Proceedings of the ACM Symposium on Parallelism in Algorithms and
Architectures (SPAA), pp. 96107, 2014.
 (by contribution) 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. 152163, 2013.
 (by alphabetical order) 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. 308317, 2012.
 (by alphabetical order) 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. 181192, 2012.