Julian Shun

Julian Shun

Email: jshun at cs.cmu.edu


I will start as a Miller Research Fellow at UC Berkeley in Fall 2015. I obtained my Ph.D. from the Computer Science Department at Carnegie Mellon University, where I was fortunate to be advised by Guy Blelloch. I was also fortunate to be supported by a Facebook Graduate Fellowship for 2013-2014. My Ph.D. thesis is available here. 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.)

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. I 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. I have also developed Ligra+, an extension of Ligra that uses graph compression techniques to process large graphs with less memory. Recently, I have used Ligra/Ligra+ to implement and evaluate various parallel algorithms for graph eccentricity estimation. I have also developed practical algorithms with strong theoretical guarantees for many fundamental graph algorithms, such as connected components, minimum spanning forest, triangle computations, maximal independent set and maximal matching. I have implemented these algorithms for the shared memory multicore setting and also for external memory.

Parallel String/Text Algorithms and Data Structures

I 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, information retrieval among many others.

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.

Sorting and Related Problems

I am interested in designing efficient algorithms for sorting and semisorting (where equal-valued keys are contiguous but different keys are not necessarily in sorted order), which are fundamental problems in computing. I have designed efficient sorting algorithms for memories with asymmetric costs of reading and writing, as well as a practical and theoretically-efficient parallel algorithm for semisorting.

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! The following paper contains descriptions of the benchmarks and experiments using them: