Scalable Parallel Algorithms

Abstract: Recent hardware advances have brought multicore parallel machines to the mainstream. Although the progress in hardware advance seems promising, it does not provide “free” performance improvement as the increasing number of cores. For many applications, including seemingly straightforward ones in the sequential setting, state-of-the-art parallel implementations can be slower than a sequential algorithm. Many reasons contribute to the performance issues, such as the “parallel” overhead in space and thread synchronization, and the unparallelizable components in conventional sequential algorithms (such as specific data structures and iterative processes).

In this talk, we share our recent work in improving the scalability of parallel graph algorithms. We select three examples: Strongly Connected Components (SCC), Bi-connected Components (BCC), and Influence Maximization (IM). For all three applications, we observe that existing parallel solutions can have poor scalability and can be slower than a sequential solution on certain graphs. Some of the applications suffer from multiple of the aforementioned challenges. Our solution tackles these issues by designing theoretically-efficient algorithms with practical considerations. Tested on more than 20 graphs with various sizes and degree distributions, our algorithms outperform the state-of-the-art solutions for each problem on almost all graphs due to better parallelism and strong theoretical guarantees.

Bio: Yihan Sun is an Assistant Professor in the Computer Science and Engineering (CSE) Department at the University of California, Riverside (UCR). She received her Ph.D. degree from Carnegie Mellon University in 2019, advised by Guy Blelloch. Prior to that, she received her Bachelor’s degree in Computer Science from Tsinghua University in 2014.

Her research interests include broad topics in the theory and practice of parallel computing, including algorithms, data structures, frameworks, implementations, programming tools and their applications. Much of her work aims at bridging the gap between theory and practice of parallel computing. She is a recipient of the NSF CAREER Award in 2023, and the Google Research Scholar program in 2024. Her work has won the Best Paper Awards at PPoPP’23 and ESA’23, and the Outstanding Paper Awards of SPAA’20 and SPAA’24. https://www.cs.ucr.edu/~yihans/